JP5324903B2 - Similarity calculation apparatus, method and program, data search system and method - Google Patents

Description

  The present invention relates to a technique for calculating a similarity that is an index indicating how similar two data are to each other, and a technique for providing a significant search result to a user using the similarity.

A technique described in Non-Patent Document 1 is known as a technique for calculating a similarity that is an index indicating how similar two Web pages are to each other.
In the technique described in Non-Patent Document 1, the link structure of Web page A and the link structure of Web page B are extracted, and the higher the similarity between the two link structures, the higher the similarity between Web pages A and B. give.
Atsushi Kurihara, 3 others, “Similarity between Web pages using link information”, Computer Software, Japan Software Science Society, November 22, 2001, Vol. 18, No. 6, p. 15-26

The technique of Non-Patent Document 1 determines the similarity without considering the actions of users who actually access these Web pages A and B.
The present invention relates to a similarity calculation device, method, and program for calculating similarity in consideration of a user's action that actually accesses data such as a web page, and data that provides a significant search result to the user using the similarity. It is an object to provide a search system and method.

The similarity calculation apparatus according to an aspect of the present invention uses an access log read from an access log storage unit in which an access log related to access to each data by each user is used, and each data accessed by each user is The difference N _list between the order of access by the user and the order in which the user i accesses the data n, and the order in which the user i accesses the data m thereafter, with the two different data as data n and m. An access order difference calculating unit for _obtaining (n, m), and an access time difference for _obtaining a difference t _margin (n, m) between a time when user i accesses data n and a time when user i subsequently accesses data m a calculation unit, the access order difference _n list (n, m) and access time difference _{t margin} (n, m) for Monotonically decreasing function _{f 1,} the access order difference _N list (n, m) and access time difference _{t margin} (n, m) by obtaining a calculation result of entering the access pattern based on the access pattern of the data n, m look including an access pattern similarity calculation section for obtaining the similarity alpha _n-m, when both the access pattern similarity alpha _n-m and access pattern similarity alpha _m-n is higher than a predetermined threshold value, the data A similarity determining unit that determines that n and data m are similar is further included .

  A data search device according to the present invention includes a similarity calculation device and a search device. The search device is similar to data corresponding to a query and a data information acquisition unit that acquires information about data corresponding to the received query. A similar data information acquisition unit that acquires information about the data to be obtained from the similarity calculation device, and an output unit that outputs information about the similar data together with information about the data corresponding to the query.

  By calculating the similarity based on the access order difference and access time difference obtained by referring to the access log related to the access to each data by each user, the similarity is considered in consideration of the action of the user who actually accesses the data. Can be calculated.

[Similarity Calculation Apparatus and Method]
An embodiment of a similarity calculation apparatus and method according to the present invention will be described. FIG. 1 is a functional block diagram illustrating a similarity calculation device, and FIG. 4 is a flowchart illustrating a similarity calculation method.

  The similarity calculation apparatus and method calculates the similarity between two data. “Data” refers to information such as a web page, image data, sound data, moving image data, data used by an arbitrary application, and the like, and means a character string for specifying the information. When the data is a Web page, a URL (Uniform Resource Locator) corresponds to a character string for specifying the Web page. When the data is other data than the web page, the file name of the data corresponds to a character string for specifying the data. Hereinafter, a case where the data is a Web page will be described as an example. That is, the similarity calculation apparatus 100 and method described below calculate the similarity between two Web pages.

  The access log storage unit 1 stores an access log related to access to each data by each user. The access log may be anything as long as it can calculate an access order difference and an access time difference, which will be described later. For example, each line of the access log includes information for specifying the accessed user (user ID, user group ID, etc.), information for specifying the accessed data (URL, etc.), and the time when the user accessed the data. Information at least.

  Specifically, an Internet service provider can use an access log automatically taken when the subscriber connects to the Internet. An access log automatically taken by a proxy server such as a company or a school may be used as an access log that is a basis for calculating an access order difference and an access time difference. In addition, when the data is a file stored in a file server, an access log automatically taken when a user connects to the file server may be used.

  The user may be one user or a user (in other words, a user group) composed of a plurality of users. That is, the access log stored in the access log storage unit 1 may store access from a plurality of users as access from the same user (user group).

  The similarity calculation device 100 may or may not have the access log storage unit 1. That is, the similarity calculation device 100 only needs to be able to access the access log storage unit 1 arranged outside the similarity calculation device 100 such as a server in which an access log is stored.

  The access order assigning unit 2 uses the access log read from the access log storage unit 1 to determine the order in which each user has accessed each data accessed by each user (step S1). Information regarding the access order (also referred to as access order) is sent to the access order difference calculation unit 3. The access order is described, for example, like an access pattern file shown in FIG.

  An example of processing of the access order assigning unit 2 will be described with reference to FIG. The access order assignment unit 2 reads an access log of a user who has not yet created an access pattern file (step S12). For example, when the access log is taken for each row, all the rows related to the user's access are extracted from the access logs stored in the access log storage unit 1, and the user is joined by combining them. Create an access log file for. If the user is represented by an IP address assigned to a terminal used by the user or a hash value thereof, a row is extracted using the user's IP address or the hash value as a key, for example.

  The access frequency calculation unit 10 calculates the frequency of accessing each data from the access log read from the access log storage unit 1 and sends only the pages accessed more than a predetermined number of times to the access order assignment unit 2. (Step S11). That is, data whose access count is smaller than a predetermined count may be excluded from the similarity determination target. For example, when the access log is taken for each row, the access frequency calculation unit 10 extracts only the rows related to the data accessed a predetermined number of times or more from the access logs stored in the access log storage unit 1. To be.

  The session dividing unit 21 of the access order assigning unit 2 divides an access sequence for user data into sessions (step S13). A session is a sequence of access to data by the same user, and means a sequence of access in which the time until access to the next data is shorter than a predetermined time. The session dividing unit 21 determines whether or not the time difference between the time when the user accesses certain data and the time when the next data is accessed exceeds a predetermined threshold value Thsession, and the time difference exceeds the threshold value Thsession. In some cases, the session is divided by determining that the session is divided between the access to the certain data and the access to the next data.

  The access order assigning unit 2 assigns an access order for each session. That is, the access order assigning unit 2 selects a session that has not yet been given an access order, and assigns an access order to the session (step S14). For example, an access number “000001” is assigned to the first access in the session, and an access number obtained by sequentially adding 1 is assigned to each subsequent access in the session. Then, it is determined whether the access order is assigned to all sessions (step S16), and the process of step S14 is repeated until the access order is assigned to all sessions. Thereby, an access pattern file illustrated in FIG. 10 is created. Note that the elapsed time granting unit 22 of the access order granting unit 2 may grant the elapsed time from the session start time to each access after step S14 (step S15).

  Thereafter, the access order assigning unit 2 determines whether an access pattern file has been created for each of all users, and returns to the process of step S12 if it has not been created. When access pattern files for all users have been created, the similarity calculation apparatus ends the process of step S1 and proceeds to the process of step S2 (FIG. 4).

The access order difference calculation unit 3 sets two different data as data n and m, and uses the determined access order to change the user i (i = 1,..., I and I are the total number of users) into the data n. A difference N _list (n, m) between the access order and the order in which the user i subsequently accesses the data m is obtained (step S2, FIG. 4). For example, the total number of users appearing in the access log stored in the access log storage unit 1 is I. As in this example, when the access order is given for each session, the access order difference calculation unit 3 determines the order in which the user i accesses the data n and the same session as the access to the data n thereafter. The difference N _list (n, m) from the order in which the user i accesses the data m is obtained. Thus, the access order difference N _list (n, m) is calculated for each session of each user. Information about the calculated access order difference N _list (n, m) is sent to the access pattern similarity calculation unit 5.

A specific example of the processing of the access order difference calculation unit 3 will be described with reference to FIG. The access order difference calculation unit 3 selects a user who has not calculated the access order difference N _list (n, m) (step S21). The selected user is expressed as user i.

The access order difference calculation unit 3 selects a session for which the user i's access order difference N _list (n, m) has not been calculated, and in the session based on the access order given by the access order assignment unit 2, A difference N _list (n, m) between the order in which the user i accesses the data n and the order in which the user i accesses the data m is obtained (step S22). As illustrated in the access pattern 1 of FIG. 11, the data n is http://aaa.bbb.com/content01.html, the access order is 1, and the data m is http://aaa.bbb.com. If /content02.html and the access order is 100, the access order difference N _list (n, m) = 100-1 = 99.

By determining whether or not the access order difference N _list (n, m) in all sessions of user i has been calculated (step S23), the access order difference N _list (n, m) in each session of user i is calculated. Step S22 is repeated until it is done.

The access order difference calculation unit 3 determines whether or not the access order difference N _list (n, m) has been calculated for all users (step S24). If not, the process returns to step S21. If the access order difference N _list (n, m) is calculated for all users, the process proceeds to step S3.

The access time difference calculation unit 4 obtains a difference t _margin (n, m) between the time when the user i accesses the data n and the time when the user i subsequently accesses the data m by using the access log (steps). S3). The calculated access time difference t _margin (n, m) is sent to the access pattern similarity calculation unit 5.

A specific example of the processing of the access time difference calculation unit 4 will be described with reference to FIG. The access order difference calculation unit 3 selects a user who has not calculated the access time difference t _margin (n, m) (step S31). The selected user is expressed as user i.

The access time difference calculation unit 4 selects a session for which the access time difference t _margin (n, m) of the user i has not been calculated, the time when the user i accessed the data n in the session, and the user i thereafter _Obtains an access time difference t _margin (n, m) which is a difference from the time when the data m is accessed (step S32). The access time difference t _margin (n, m) may be obtained by referring to the access log read from the access log storage unit 1, or the elapsed time from the session start time in each access in step S15 (FIG. 5). If it is given, it may be obtained by referring to the elapsed time from the session start time.

By determining whether or not the access time difference t _margin (n, m) in all sessions of user i has been calculated (step S33), the access time difference t _margin (n, m) in each session of user i is calculated. Step S32 is repeated until it is done.

The access order difference calculation unit 3 determines whether or not the access time difference t _margin (n, m) has been calculated for all users (step S34). If not, the process returns to step S31. If the access time difference t _margin (n, m) is calculated for all users, the process proceeds to step S4.

In step S22 and step S32, when there are a plurality of data n and data m in the same session, all combinations of data n and data m accessed after the data n in the same session are included. An access order difference N _list (n, m) and an access time difference t _margin (n, m) are calculated for each. That is, when there is data n and data m as illustrated in FIG. 12 in the same session, the access order difference N _list (n, m) from the data n in the access order 1 to the data m in the access order 2 And access time difference t _margin (n, m), access order difference N _list (n, m) and access time difference t _margin (n, m) for access order 1 data n to access order 4 data m, access An access order difference N _list (n, m) and an access time difference t _margin (n, m) are calculated from the data n of the order 3 to the data m of the access order 4.

The access order difference N _list (n, m) and the access time difference t _margin (n, m) can be an index indicating the degree of relevance between the data n and the data m. That is, when the access order difference N _list (n, m) and the access time difference t _margin (n, m) are large as in the access pattern 1 of FIG. 11, it is determined that the relationship between the data n and the data m is low. On the other hand, when the access order difference N _list (n, m) and the access time difference t _margin (n, m) are small as in the access pattern 2 of FIG. 11, the data n and the data m are related to each other. Can be determined to be high.

The access pattern similarity calculation unit 5 calculates the access order difference N _list (n, m) and the monotonically decreasing function f ₁ for the access order difference N _list (n, m) and the access time difference t _margin (n, m). By _obtaining a calculation result obtained by inputting the access time difference t _margin (n, m), an access pattern similarity α _n−m based on the access pattern for the data n, _m is obtained (step S4). The monotone decreasing function f ₁ is given as, for example, a composite function of a monotone decreasing function f ₂ and a monotone increasing function f ₃ described later.

Here, the monotone decreasing function means a function f that satisfies f (x ₁ ) ≧ f (x ₂ ) with respect to arbitrary x ₁ , x ₂ (where x ₁ <x ₂ ). Similarly, the monotonically increasing function means a function f that satisfies f (x ₁ ) ≦ f (x ₂ ) with respect to arbitrary x ₁ , x ₂ (where x ₁ <x ₂ ).

First, the first integration unit 51 of the access pattern similarity calculation unit 5 calculates the access order difference to the monotonically decreasing function f ₂ for the access order difference N _list (n, m) and the access time difference t _margin (n, m). A calculation result obtained by inputting N _list (n, m) and the access time difference t _margin (n, m) is obtained. For example, f ₂ is given by the following equation where A is a predetermined positive real number and e is a Napier number.

As in this example, when the access order difference N _list (n, m) and the access time difference t _margin (n, m) are calculated for each session of each user, Using the access order difference N _list (n, m) and the access time difference t _margin (n, m), the above calculation results are obtained. When two or more access order differences N _list (n, m) and access time differences t _margin (n, m) are calculated in the same session, the respective access order differences N _list (n, m) ) And the access time difference t _margin (n, m), respectively, to obtain the above calculation results. The calculation result is sent to the second integration unit 52 of the access pattern similarity calculation unit 5.

The second integration unit 52 obtains the access pattern similarity α _n−m by obtaining a calculation result obtained by inputting the calculation result to the monotonically increasing function f ₃ for each calculation result. For example, a value obtained by adding the calculation results is defined as an access pattern similarity α _n−m . In addition, the maximum value of each calculation result may be the access pattern similarity α _nm . When the maximum value is used, similar page determination can be performed in consideration of a hidden connection between data based on a specific access pattern of a certain user.

The access pattern similarity α _n−m obtained in this way is calculated only from the access logs to the data n and m of each user, and the action of the user who actually accessed the data is taken into consideration. Moreover, there is an advantageous effect that the similarity can be calculated without performing a relatively heavy process of considering the contents of the data n and m.

In the above example, the access order assigning unit 2 divides the access sequence of the user i into sessions and assigns an access order for each session. However, an access order that increases one by one may be given to each access constituting the access sequence of the user i without dividing the session.
Note that the similarity between the data n and m may be obtained in consideration of the distance similarity based on the distance between character strings that specify data.

The distance calculation unit 61 (FIG. 1) calculates the distance L _nm between the character string that specifies the data n and the character string that specifies the data m (step S51, FIG. 8). The calculated distance L _nm is sent to the distance similarity calculation unit 62. The character string specifying data is a URL (Uniform Resource Locator) when the data is a Web page. As the distance L _nm , for example, the Levenshtein distance is adopted (for example, see Reference 1).
[Reference 1] [Search on December 4, 2008], Internet <URL: http://en.wikipedia.org/wiki/Levenshtein_distance>
The Levenshtein distance defines a distance between two character strings based on how many times a character string is added, deleted, or replaced with respect to one character string. The number of additions, deletions, and replacements of the character is the distance between the two character strings.

  For example, in the character string similarity pattern 1 in FIG. 13, the character “1” of the character string “http://aaa.bbb.com/content01.html” is converted into the character “2”, that is, one time. The character string “http://aaa.bbb.com/content02.html” can be formed by the replacement. Therefore, the Levenshtein distance between both character strings in the character string similarity pattern 1 is 1.

In the character string similarity pattern 2 in FIG. 13, the character “c” in the character string “http://aaa.bbb.com/content01.html” is changed to the character “a”, and the character “o” is changed to the character “ In “a”, by replacing the character “n” with the character “a” and deleting the characters “t”, “e”, “n”, “t”, “0”, “1”, ie three replacements and 6 The character string “http://aaa.bbb.com/aaa.html” can be configured by deleting the times. Therefore, the Levenshtein distance between both character strings in the character string similarity pattern 2 is 9.

The distance similarity calculation unit 62 obtains a distance similarity β _n−m by obtaining a calculation result obtained by inputting the calculated distance L _n−m to the monotonously decreasing function f ₄ for the distance L _n−m ( Step S52). The obtained distance similarity β _nm is sent to the similarity integration unit 7. For example, f ₄ is given by the following equation where B is a predetermined positive real number and e is a Napier number.

Similarity integration section 7 has entered the similarity alpha _n-m and the distance similarity beta _n-m monotonically increasing function f ₅ for access pattern similarity alpha _n-m and the distance similarity beta _n-m By obtaining the calculation result, the similarity R _nm is obtained (step S7, FIG. 4). For example, f ₅ is given by the following equation, where k _α and k _β are predetermined positive real numbers. For example, k _α = k _β = 1.

As described above, the similarity between the data n and m may be obtained in consideration of the distance similarity based on the distance between character strings that specify data.
Note that the similarity between the data n and m may be obtained in consideration of the similarity between the content of the data n and the content of the data m. For example, when each of the data n and m includes text, the similarity of content is considered as follows.

  The first noun extraction unit 71 extracts each noun included in the text of the data n. If the data is a Web page, the character string enclosed by the <body> tag is acquired from the source of the data n, and the HTML tag is deleted. Then, the first N characters are acquired, where N is a predetermined positive integer. Morphological analysis is performed on the first N characters, and each noun included in the first N characters is extracted. The extracted nouns are sent to the duplicate noun count calculator 73.

The second noun extraction unit 72 extracts each noun included in the text of the data m in the same manner as the first noun extraction unit 71. The extracted nouns are sent to the duplicate noun count calculator 73.
The duplicate noun number calculation unit 73 calculates the number of duplicate nouns, which is the number of nouns common to the noun extracted by the first noun extraction unit 71 and the noun extracted by the second noun extraction unit 72, and is similar in content. Degree γ _nm . The calculated content similarity γ _nm is sent to the similarity integration unit 7.

The similarity integration unit 7 calculates the access pattern similarity α _n− calculated as the monotonically increasing function f ₆ for the access pattern similarity α _n−m , the distance similarity β _n−m, and the content similarity γ _{n−m. The} similarity R _n-m is obtained by obtaining a calculation result obtained by inputting _m , the calculated distance similarity β _n-m, and the calculated content similarity γ _n-m .

For example, when α _n−m + β _nm is greater than or _equal to a predetermined threshold Th3 and the content similarity γ _n−m is also greater than or equal to the predetermined threshold Th4, the similarity R _n−m = α _n−m + β _n−m ,
Otherwise, the similarity R _nm is set to 0. Thereby, the degree of similarity about a series of data etc. written about the same subject can be made high.

Access pattern similarity alpha _n-m or similarity R _n-m may be provided with a similar determination unit 8 determines whether more than a predetermined threshold value. If the access pattern similarity α _n−m or the similarity R _n−m is equal to or greater than a predetermined threshold, the similarity determination unit 8 determines that the data n and m are similar and outputs information indicating that effect. . Otherwise, the similarity determination unit 8 determines that the data n and m are not similar and outputs information indicating that.

Further, the similarity determination unit 8 has an access pattern similarity α _n−m or similarity R _{n−m that} is _{equal to} or greater than a predetermined threshold Th1, and the access pattern similarity α _m−n or similarity R _m−n is If the threshold value Th2 is equal to or greater than the predetermined threshold Th2, the data n and m may be determined to be similar and information indicating that may be output. The threshold value Th1 and the threshold value Th2 do not necessarily match.

That is, the similarity determination unit 8 determines that one or both of the similarity α _n−m and the similarity α _m−n are higher than a predetermined first threshold, or the similarity R _n−m and the similarity R _When one or both of _m−n is higher than a predetermined second threshold value, it may be determined that the data n and the data m are similar. Further, the similarity determination unit 8 determines the similarity α _n−. One or both of _m and similarity α _m−n are higher than a predetermined first threshold, and one or both of content similarity γ _n−m and content similarity γ _m−n are higher than a predetermined third threshold. If it is high, or one or both of the similarity R _n-m and the similarity R _m-n are higher than a predetermined second threshold, one of the content similarity γ _{n- m} and the content similarity γ _m-n Alternatively, when both are higher than a predetermined third threshold, it may be determined that the data n and the data m are similar. .

In this example, the access pattern similarity α _n-m or similarity R _n-m is calculated for the data n and m, which is one of the combinations of two different data, but the two different data included in the access log are calculated. Similarity may be calculated for each of all combinations to determine if they are similar. At this time, since the access pattern similarity α _n−m or similarity R _n−m does not necessarily match the access pattern similarity α _m−n or similarity R _m−n , access from the data n to the data m is performed. Whether not only the pattern similarity α _n−m or the similarity R _n−m but also the access pattern similarity α _m−n or the similarity R _m−n from the data m to the data _n is calculated, whether or not they are similar Such a determination may be made.

[Data search system and method]
An embodiment of a data search system and method according to the present invention will be described with reference to FIGS. FIG. 3 is a block diagram illustrating a data search system, and FIG. 9 is a flowchart illustrating a data search method.
The input unit 201 of the search device 200 acquires a query such as a search word from the user terminal 300 (step A1). The user terminal 300 is, for example, an information terminal device such as a mobile phone or a personal computer.

  The data information acquisition unit 202 of the search device 200 acquires information about data corresponding to the received query (step A2). The acquired information is sent to the similar data information acquisition unit 203. For example, when the data is a Web page, a Web page including a search word that is a query is acquired using any Web page search technology. The search device 200 may acquire information about data corresponding to a query using an external search engine 400 (for example, goo (registered trademark)), and if it has a search engine function inside, Information on data corresponding to the query may be acquired using the search engine function.

  The similar data information acquisition unit 203 acquires information about data similar to the data corresponding to the query from the similarity calculation device 100 (step A3).

  For example, the similarity calculation device 100 calculates the similarity for each of all combinations of two different data n and m included in the access log, and the similarity determination unit 8 determines that each combination of the data n and m is similar. Decide whether you want to do it. The search device 200 sends information about data corresponding to the query to the similarity calculation device 100. The similarity calculation device 100 sends information about data similar to the data corresponding to the query to the search device 200, and the similar data information acquisition unit 203 acquires the information.

  The output unit 204 of the search device 200 outputs information about data similar to the data corresponding to the query to the user terminal 300 together with information about the data corresponding to the query (step A4).

FIG. 14 is an example of a screen displayed on the display of the user terminal 300 based on information provided from the output unit 204 to the user terminal 300 when the data is a Web page. As in this example, for example, the user terminal 300 is provided with information about similar pages for each of the Web pages with higher search results.
Further, when there are a plurality of similar data regarding the data corresponding to the query, the plurality of similar data may be provided to the user terminal 300. Further, the similar data information acquisition unit 203 may send the information about the acquired similar data to the similarity calculation apparatus 100, further acquire information about the data similar to the similar data, and provide the information to the user terminal 300. Good.

  As a communication protocol between the search device 200 and the similarity calculation device 100 and a communication protocol between the search device 200 and the external search engine, a publicly available protocol such as POST can be used. Also, the format such as publicly available XML, HTML, structured table, etc. can be used.

  When the above configuration is realized by a computer, the processing contents of the functions of each unit of the similarity calculation device are described by a program. By executing this program on a computer, the functions of the above-described units are realized on the computer.

  That is, when the CPU sequentially reads and executes the program, the access order assigning unit 2, the session dividing unit 21, the elapsed time giving unit 22, the access order difference calculating unit 3, the access time difference calculating unit 4, and the access pattern similarity calculating unit 5, first integration unit 51, second integration unit 52, distance calculation unit 61, distance similarity calculation unit 62, similarity integration unit 7, first noun extraction unit 71, second noun extraction unit 72, duplicate noun count calculation Each of the unit 73 and the similarity determination unit 8 is realized. Further, the auxiliary storage device or the memory functions as the access log storage unit 1.

  The CPU functioning as each unit of the similarity calculation device performs processing on the data read from the memory or the auxiliary storage device, and stores the processed data in the memory or the auxiliary storage device. That is, data is exchanged between the units of the similarity calculation device via the memory or the auxiliary storage device.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  As an execution form different from the above-described embodiment, the computer may read the program directly from the portable recording medium and execute processing according to the program. Each time is transferred, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to a computer but has a property that is based on computer processing).

In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.
In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary.
Needless to say, other modifications are possible without departing from the spirit of the present invention.

The functional block diagram which illustrates a similarity calculation apparatus. The functional block diagram which illustrates an access pattern similarity calculation part. The functional block diagram which illustrates a search system. The flowchart which illustrates a similarity calculation method. The flowchart of the example of step S1. The flowchart of the example of step S2. The flowchart of the example of step S3. The flowchart of the example of step S5. The flowchart which illustrates a search method. The figure which illustrates an access pattern table. The figure for demonstrating access pattern similarity. The figure for demonstrating the calculation when multiple combinations of data n and m appear in the same session. The figure which illustrates the information provided to a user. The figure for demonstrating Levenshtein distance.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Access log memory | storage part 2 Access order provision part 3 Access order difference calculation part 4 Access time difference calculation part 5 Access pattern similarity calculation part 51 First integration part 52 Second integration part 61 Distance calculation part 62 Distance similarity calculation part 7 Similarity integration unit 71 First noun extraction unit 72 Second noun extraction unit 73 Duplicate noun count calculation unit 8 Similarity determination unit 10 Access frequency calculation unit 100 Similarity calculation device 200 Search device 201 Input unit 202 Data information acquisition unit 203 Similar data Information acquisition unit 204 output unit

Claims (9)

An access order giving unit for determining the order in which each user has accessed each data accessed by each user using an access log read from an access log storage unit in which an access log relating to access to each data by each user is stored; ,
An access order difference calculation unit that obtains a difference N _list (n, m) between the order in which user i accesses data n and the order in which user i subsequently accesses data m, using two different data as data n and m ,
An access time difference calculation unit for _obtaining a difference t _margin (n, m) between a time when the user i accesses the data n and a time when the user i accesses the data m thereafter;
Access order difference _N list (n, m) and access time difference _{t margin} (n, m) monotonically decreasing function _{f 1} for, the access order difference _N list (n, m) and the access time difference _{t margin} (n , M), an access pattern similarity calculation unit for obtaining an access pattern similarity α _n−m based on the access pattern for the data n, m,
Including
It further includes a similarity determination unit that determines that the data n and the data m are similar when both the access pattern similarity α _n−m and the access pattern similarity α _m−n are higher than a predetermined threshold. ,
The similarity calculation apparatus characterized by the above. The similarity calculation apparatus according to claim 1,
The access pattern similarity calculation unit
The access order difference N _list (n, m) and the access time difference t _margin (n) are _added to the monotonically decreasing function f ₂ for the access order difference N _list (n, m) and the access time difference t _margin (n, m). , M), a first integration unit for obtaining a calculation result for each user i,
A second integration unit for obtaining the access pattern similarity α _n−m by obtaining a calculation result obtained by inputting the calculation result to the monotonically increasing function f ₃ for each calculation result;
The similarity calculation apparatus characterized by including. In the similarity calculation apparatus according to claim 2,
The session is a sequence of access to data by the same user, and in the access sequence, the time until access to the next data is shorter than a predetermined time,
The access order difference calculation unit calculates the difference N _list (n, m) between the order in which the user i accesses the data n and the order in which the user i accesses the data m in the same session as the access to the data n thereafter. Is a part seeking
The access time difference calculation unit calculates a difference t _margin (n, m) between a time when the user i accesses the data n and a time when the user i accesses the data m in the same session as the access to the data n thereafter. Is a part seeking
The first integration unit calculates the access order difference N _list (n, m) and the monotonically decreasing function f ₂ for the access order difference N _list (n, m) and the access time difference t _margin (n, m). It is a unit that obtains a calculation result obtained by inputting an access time difference t _margin (n, m) for each session of each user i.
The similarity calculation apparatus characterized by the above. In the similarity calculation device according to any one of claims 1 to 3,
A distance calculation unit that calculates a distance L _n−m between a character string that specifies data n and a character string that specifies data m;
A distance similarity calculation unit for obtaining a distance similarity β _n-m by obtaining a calculation result obtained by inputting the distance L _n-m to the monotone decreasing function f ₄ for the distance L _n-m ;
Obtaining a calculation result obtained by inputting the access pattern similarity α _n-m and the distance similarity β _n-m to the monotonically increasing function f ₅ for the access pattern similarity α _n-m and the distance similarity β _n-m A similarity integration unit for obtaining the similarity R _nm ,
Similarity calculation device. In the similarity calculation apparatus according to any one of claims 1 to 4,
The above data includes text,
A first noun extraction unit for extracting each noun included in the text of the data n;
A second noun extraction unit for extracting each noun included in the text of the data m;
Duplicate noun number, which is the number of nouns common to the noun extracted by the first noun extraction unit and the noun extracted by the second noun extraction unit, is calculated as the content similarity γ _n−m And a noun count calculator,
The similarity determination unit is configured such that one or both of the access pattern similarity α _n−m and the access pattern similarity α _m−n is higher than a predetermined first threshold, and the content similarity γ _n−m and the content similarity γ _{m When} one or both of _−n is higher than a predetermined third threshold, or one or both of the similarity R _n−m and the similarity R _m−n are higher than a predetermined second threshold. a unit that determines that data n and data m are similar when one or both of γ _{n− m} and content similarity γ _m−n are higher than a predetermined third threshold;
The similarity calculation apparatus characterized by the above. A similarity calculation device according to claim 5;
A data information acquisition unit that acquires information about data corresponding to the received query, a similar data information acquisition unit that acquires information about data similar to the data corresponding to the query from the similarity calculation device, and the query A search device including an output unit that outputs information about the similar data together with information about the data corresponding to
Data retrieval system including The access order assigning unit uses the access log read from the access log storage unit in which the access log related to the access to each data by each user is used to determine the order in which each user has accessed each data accessed by each user. A predetermined access order granting step;
The access order difference calculation unit sets the difference N _list (n, m) between the order in which the user i accesses the data n and the order in which the user i accesses the data m thereafter, assuming two different data as the data n and m. The required access order difference calculating step;
An access time difference calculating unit for calculating a difference t _margin (n, m) between a time when the user i accesses the data n and a time when the user i subsequently accesses the data m;
Access pattern similarity calculation unit, the access order difference _N list (n, m) and access time difference _{t margin} (n, m) monotonically decreasing function _{f 1} for, the access order difference _N list (n, m) and An access pattern similarity calculation step for obtaining an access pattern similarity α _n−m based on an access pattern for data n and m by _obtaining a calculation result obtained by inputting the access time difference t _margin (n, m);
Including
The similarity determining unit determines that the data n and the data m are similar when both the access pattern similarity α _n−m and the access pattern similarity α _m−n are higher than a predetermined threshold. A similarity calculation method further including a determination step. Each step of the similarity calculation method according to claim 7,
An output unit that outputs information about the similar data together with information about the data corresponding to the query;
A data information acquisition step in which the data information acquisition unit acquires information about data corresponding to the received query;
A similar data information acquisition unit that acquires information about data similar to data corresponding to the query;
Data search method including.   A similarity calculation program for causing a computer to function as the similarity calculation apparatus according to claim 1.

Images