JP4774016B2 - Information search method, information search program, and information search device - Google Patents

Description

  The present invention relates to an information search method, an information search program, and an information search device.

A set in which the relationship between elements as information is defined by distance, dissimilarity or similarity is defined as information space Ω. The distance between any two elements x and yεΩ in the information space Ω is defined by a distance function d (x, y). The distance function in the information space Ω satisfies the following equation.
d (x, y) ≧ 0 (1)
d (x, y) = d (y, x) (2)
d (x, y) = 0 if x = y Expression (3)
Equation (1) is called a non-negative condition, and Equation (2) is called a symmetry condition. In an information search set (also called a searched set or a search target set) X⊂Ω that is also a subset of the information space, a set R (q) of elements having the smallest distance from the query qεΩ that is an element of the information space ⊂X is represented by Equation (4).

In the information space, the distance between the elements satisfies the following expressions (5) and (6) in addition to the non-negative number condition and the symmetry condition, and is defined as a distance space Ωd.
d (x, y) = 0 iff x = y Expression (5)
d (x, y) + d (y, z) ≧ d (x, y) (6)
Equation (5) is called a reflection condition, and equation (6) is called a triangle inequality.

  Conventionally, TLAESA (Tree Linear Approximating and Eliminating Search Algorithm) is an information search method for searching information similar to an input query from an information search set for elements similar to a query that is an element (information) of a metric space. (For example, Non-Patent Document 1). TLAESA searches for information by performing pre-processing before a query is input and post-processing after the query is input. The pre-processing includes a step of selecting a plurality of elements (referred to as a base prototype) in the information search set (searched set), calculating the distance between them and all other elements, and all elements of the information search set. And constructing a binary tree. Post-processing is a process that calculates the distance between the query and the selected base prototype immediately after the query is input, and a triangle that indicates the magnitude relationship between the three elements that is one of the properties of the metric space. The process includes searching using the inequality and the binary tree while reducing the search space. TLAESA effectively uses triangular inequalities to reduce search space and reduce search costs. Here, the search cost is a value used when evaluating the efficiency of information search, and is the number of times of similarity calculation or distance calculation between a query and an element of a search target set.

As described above, as an information search method for reducing the search space using the triangle inequality, in addition to TLAESA, LAESA (Linear Approximation and Eliminating Search Algorithm: see, for example, Non-Patent Document 2) and AESA (Approximating and Eliminating) Search Algorithm: For example, see Non-Patent Document 3) has been proposed.
`` A fast branch & bound nearest neighbor classifier in metric space '', Luisa Mico, Jose Oncina, Rafael C. Carrasco, Pattern Recognition Letters vol.17, p.731-p.739 1996 `` A new version of the Nearest-Neighbour Approximating and Eliminating Search Algorithm (AESA) with linear preprocessing time and memory requirements '', Luisa Mico, Jose Oncina, Pattern Recognition Letters vol.15, p.9-p.7 January 1994 `` An algorithm for finding nearest neighbors in (approximately) constant average time '', E. Vidal Pattern Recognition Letters vol.4, p.145-p.157 July 1986

  By the way, for example, when searching for a document similar to the input document from the document file group, that is, when the document is a set to be searched, when calculating the similarity or the distance defining the relationship between documents. The feature quantity extracted from the used document may be high-dimensional. This is because a word vector composed of different words appearing in a document is used as a feature amount of the document, and one element of the word vector is one-dimensional, and therefore, an information search set (also called a search target set or a searched set). This is because there are as many dimensions as the number of different words that occur in all the document files.

Next, problems in TLAESA will be described with reference to FIGS. 17 and 18.
Note that the information search set in FIGS. 17 and 18 is a set whose elements are document files of newspaper articles for 10 years.
Here, the distance between elements in the information search set is calculated by the following procedure. First, a document described in each document file is subjected to morphological analysis, unnecessary stop words are deleted, and words are extracted from the document (document file). Here, a stop word is a word that is ignored as a search word because it is a common word in information search and is inappropriate as a search word. In Japanese, hiragana and katakana single-letter words are stop words. Then, each extracted word is weighted by a tf-idf (term frequency-inverted document frequency) method. As a result, the resulting weighted word vector is used as the feature amount of the document file. Then, the document file of the information search set is used as an element, and the distance between elements is defined using the cosine distance with respect to the feature amount. When a word vector is used as a feature amount, the cosine similarity is widely used as a similar or dissimilar measure.
The number of elements (number of document files) used in this example is 64585, and the weighted word vector as the feature amount is 51030 dimensions. This can be said that the dimension of the metric space is 51030.

FIG. 17 is a diagram showing a cumulative distribution of distances between the pair elements by randomly selecting 1 × 10 ⁶ pair elements (two elements) from the information search space.
In FIG. 17, the horizontal axis indicates the distance between the pair elements, and the vertical axis indicates the cumulative value of the ratio of the pair elements having the corresponding distance to the entire pair elements.
Note that the distance is standardized so that the distance between the farthest elements in the information search set is 1.0 using a cosine distance.
FIG. 17 shows that the number of elements having a distance of 0.8 or less is very small, and most pair elements exist in the vicinity of 1.0. Specifically, it is shown that the proportion of pair elements having a distance of 0.98 or more is 90% of the total (thick line in FIG. 17).
That is, it can be seen from FIG. 17 that the elements are sparse in the information search set whose elements are the document files of newspaper articles for 10 years.

FIG. 18 is a diagram showing a cumulative distribution of lower bounds of distances under the same conditions as in FIG.
The lower bound of the distance was calculated using the same pair elements as in FIG. 17 and 200 elements selected at random (corresponding to the base prototype of TLAESA).
In FIG. 18, the horizontal axis represents the lower bound value of the distance calculated by such a method, and the vertical axis represents the cumulative value of the ratio of the lower bound value of the distance to the lower bound of all the calculated distances.
In FIG. 18, it is shown that most of the lower bound of the distance is below 0.4. In particular, the lower bound of a distance of 0.138 or less accounts for 90% of the total. The search space is reduced by comparing an element having a large lower bound with a search target set, that is, a target element for calculating a distance to the query, as compared with a distance between the query and a certain element at a certain point in the information search process. This is done by removing it from the set. Assume that the distance between a query and an element at a certain point in the information search process is 0.98. As shown in FIG. 18, since there is almost no element having a lower bound of distance greater than 0.98, there is almost no element to be reduced at this point. In this way, when the feature amount of an element is high-dimensional, the distance between a certain element in the information search set and the query is calculated, and the element whose lower bound of the distance is larger than the comparison target distance is removed from the information search set, and the search space The way to reduce does not work effectively.

Thus, in an information search set such as a document file in which the number of dimensions of the metric space is large, the reduction of the search space using the lower bound of the distance calculated from the triangle inequality does not function effectively.
That is, even if TLAESA, LAESA, AESA, or the like is applied to an information search set in which the number of dimensions of the metric space is large, such as a document file, the search space is hardly reduced. Each time the distance to the query is calculated, there arises a problem that efficient information search is not performed.
Further, in TLAESA and the like, the triangle inequality is used as described above, and this assumes that the metric space is an information search set. Therefore, it is difficult to directly apply an algorithm based on a pruning method that uses a triangle inequality such as TLAESA to reduce search space for information that is not a metric space.

  An object of the present invention is to be able to search for information even when the information search set is a high-dimensional metric space or an information space.

  The present invention has been made to solve the above-described problem, and the information search method according to claim 1 is an information search for searching for information similar to a query from an information search set stored in a storage unit. An information search method in an apparatus, wherein the information search method includes a network generation process and an information search process. The network generation process is performed by a network generation unit of the information search apparatus in the information search set. An arbitrary two elements are linked directly or indirectly via an element other than the two elements, thereby generating a one-component network and storing it in the storage unit, and the information search The processing is performed by the search processing unit of the information search device, wherein (a1) an element that is directly linked to the predetermined first element of the network And the element having the highest similarity with the query is selected as the second element, and (a2) the similarity between the second element and the query is stored in the storage unit. If it is greater than the predetermined set similarity, the similarity between the second element and the query is stored in the storage unit as a new set similarity, and (a3) the second element is An element directly linked to the third element is obtained from the storage unit as the third element, and (a4) among the elements directly linked to the third element, the past The element that has never become the second element and the element having the highest similarity to the query is selected as a new second element, and the new second element By performing the process (a2), an element similar to the query is obtained. And as a way to perform the information searching process of search, a.

  According to such a method, a search is performed using a network of one component in which elements are linked by a link, and a trigonometric inequality that is a property of a metric space is not used. Even when the information search set is not a metric space, the information search can be performed.

  Furthermore, the information search method according to claim 2 is the information search method according to claim 1, wherein the network generation process is performed by the network generation unit including an element x that is an arbitrary element in the information search set, The degree of similarity with each element other than the element x is calculated, and among elements other than the element x, a predetermined number of elements set in advance are obtained in descending order of the degree of similarity with the element x. The method of generating the nearest element network Γ (x) for the element x by linking the element with the element x is performed for all elements in the information search set.

  According to such a method, since the network between elements in the information search set can be a collection of nearest neighbor element networks linked to a predetermined number of elements existing in the vicinity of an arbitrary element x, A network having a small average shortest path length can be generated. By using such a network for information search, search costs can be reduced.

  The information search method according to claim 3 is the information search method according to claim 2, wherein the search processing unit includes an element x0 that is an arbitrary element in the information search set. When the query q is input via the input unit, the nearest neighbor element network Γ (x0) and the arbitrary element xmax for the element are acquired from the storage unit, and (b1) A = Γ ( x0) Calculate sets A and B that satisfy {x0}, B = {x0}, (b2) obtain an element x1 satisfying the following expression (8) from the set AB,

  (Where ρ (a, b) is the similarity between elements a and b in the information search set, | A | is the number of elements in the set A, and AB is elements A and B Γ (a) is the nearest element network (b3) ρ (x1, q)> ρ (xmax, q) for the element a, and the element x1 is set as a new element xmax, and (b4) A∪Γ (x1) is substituted for A, B 、 {x1} is substituted for B, (b5) The processing of (b2) to (b4) is repeated, and | A | exceeds a predetermined value β. Alternatively, when the query matches the element x1, the element xmax is output as the final output element.

  According to such a method, information search can be performed using a network having one component and a small average shortest path length, so that search cost can be reduced.

  The information search program according to claim 4 is a program that causes a computer to execute the information search method according to any one of claims 1 to 3.

  According to such a program, a search is performed using a network of one component in which elements are linked by links, and a trigonometric inequality that is a property of metric space is not used. Even when the information search set is not a metric space, the information search can be performed. Further, since the network between elements in the information search set can be a set of nearest neighbor element networks linked to a predetermined number of elements existing in the vicinity of an arbitrary element x, the average shortest path length is small. A network can be created. By using such a network for information search, search costs can be reduced.

  The information search device according to claim 5 is an information search device that searches for information similar to a query from an information search set held in a storage unit, and the information search device includes a network generation unit, A search processing unit, wherein the network generation unit directly or indirectly through any element other than the two elements between any two elements in the information search set It has a function of generating a one-component network by link connection and holding it in the storage unit. The search processing unit is (a1) directly link-connected to a predetermined first element of the network. And from the storage unit, the element having the highest similarity with the query is selected as the second element, and (a2) the second element and the query If the similarity is greater than a predetermined setting similarity held in the storage unit, the similarity between the second element and the query is held in the storage unit as a new setting similarity, (A3) The second element is a third element, and an element that is directly linked to the third element is acquired from the storage unit, and (a4) the third element is directly connected to the third element. Among the linked elements, an element that has never become the second element in the past and has the highest similarity with the query is selected as a new second element. By performing the process (a2) for the new second element, the apparatus has a function of searching for an element similar to the query.

  According to such an information search apparatus, since a search is performed using a network of one component in which elements are linked by links and the triangular inequality that is the property of the metric space is not used, the information search set has a high dimension. Information search can be performed even in a metric space or when the information search set is not a metric space.

  According to the present invention, it is possible to search for information even when the information search set is a high-dimensional metric space or an information space.

  The best mode for carrying out the present invention (hereinafter referred to as “embodiment”) will be described in detail below with reference to the drawings.

(System configuration)
FIG. 1 is a diagram illustrating a configuration example of an information search system according to the present embodiment.
In the information search system 12, an information search device 1 that searches for information and a terminal 11 that transmits a query to the information search device 1 include a physical area such as a WAN (Wide Area Network) or a LAN (Local Area Network). Connected via a network 10.

The information search apparatus 1 includes a processing unit 2 that processes information, a storage unit 3 that stores information to be searched, an input unit 4 to which information is input, and an output that outputs information search results and the like. Part 5. The storage unit 3 includes at least one of various storage media such as an HD (Hard Disk), a non-volatile memory, and a RAM (Random Access Memory), and depends on the configuration of the computer on which the program is installed. It consists of a combination of
The query transmitted from the terminal 11 is sent to the processing unit 2 via the physical network 10 and the input unit 4. Further, the user may directly input a query to the processing unit 2 through the input unit 4.
The processing unit 2 includes a network generation unit 21 that performs network generation processing and a search processing unit 22 that performs information search processing. Here, the network refers to a network between elements when the elements in the information search set are connected by a link.

  The processing unit 2 and the network generation unit 21 and the search processing unit 22 in the processing unit 2 are configured such that an information search program stored in a storage device such as an HD or a ROM (Read Only Memory) (not shown) is stored in a RAM (not shown). This is realized by being developed and executed by a CPU (Central Processing Unit) (not shown).

(Neighboring element network generation processing)
First, the outline of the network generation process will be described with reference to FIG. 1 and along FIG.
FIG. 2 is a diagram showing an overview of network generation processing according to the present embodiment.
In FIG. 2, reference numeral 100 denotes an element in the information search set, that is, information stored in the storage unit 3 and to be searched. Here, specifically, the element is, for example, a text file such as a newspaper or a patent gazette, or a document file by XML (Extensive Markup Language).
First, the network generation unit 21 calculates the similarity between the elements 100. In the present embodiment, the similarity refers to the cosine similarity, but is not limited thereto, and is based on a calculation formula based on a general distance definition represented by the Minkowski distance, or a similarity other than the cosine similarity. A calculation formula may be used.
Then, as illustrated in FIG. 2A, the network generation unit 21 selects an arbitrary element 100 (symbol x) among the elements 100.
Then, as illustrated in FIG. 2B, the network generation unit 21 selects k elements 100 having a high similarity with the element x and the number of neighboring elements input in advance. That is, the network generation unit 21 selects k elements 100 from the elements 100 other than the element x in descending order of similarity to the element x. The number k of neighboring elements is a parameter necessary for a one-component network in which all elements 100 in the generated network are connected by links.

Here, the component is a subset of the information search set, and any two elements 100 of a set are connected by at least one link or link connection. However, the link connection is a link between the first element 100 and the second element 100, a link between the second element 100 and the third element 100,..., (N-1) th. A series of links such as a link between the element 100 and the n-th element 100. In such a case, the first element 100 and the nth element 100 are indirectly connected by link connection.
For example, “a network is one component” means “a network in which any two elements 100 are connected to each other by a link or link connection”.

The number k of neighboring elements can be obtained by using test data or the like and using the search cost as an evaluation function (described later in FIGS. 7, 8, 12 and 13). In FIG. 2, k = 3.
As shown in FIG. 2B, the network generation unit 21 forms an element group Nk (x) for the element x by establishing a link between the selected k elements 100 and the element x. .

After performing this process for each element 100, the network generation unit 21 refers to the element group Nk (y) for the element y other than the element x as shown in FIG. An element y whose element x is included in the group Nk (y) is extracted.
Then, the network generation unit 21 calculates the union of the element group Nk (x) and the element y by linking the element x and the element y shown in FIGS. 2 (b) and 2 (c). To do. This procedure is called undirected. This union becomes the nearest neighbor element network Γ (x) for the element x shown in FIG. The nearest neighbor element network Γ (x) generated by such a procedure is a network in claims, and is a network having non-directivity. Here, the network having non-directivity is a network composed of elements connected by an undirected link that is a link with no definition of a start point and an end point.

When the network generation unit 21 calculates the nearest element network for each element 100 according to such a procedure, the nearest element network has the following properties.
That is, the nearest element network Γ (x0) for an arbitrary element x0 is acquired, and an element x1 other than the element x0 in the nearest element network Γ (x0) is acquired. Then, the nearest element network Γ (x1) for the obtained element x1 is obtained, and the element x2 other than the element x1 in the nearest element network Γ (x1) is obtained. Next, an information search is performed by repeating the procedure of obtaining the nearest element network Γ (x2) for the obtained element x2 and obtaining the element x3 other than the element x2 in the nearest element network Γ (x2). All elements 100 in the set can be traced. That is, as shown by a broken line in FIG. 2D, a one-component network in which all elements 100 in the information search set are directly or indirectly connected by a link can be generated. Here, the elements constituting the nearest element network Γ (x) for the element x are elements that are directly linked to the element x. For example, in FIG. 2D, the element 101 and the element 102 are directly linked. The element 101 and the element 104 are indirectly coupled via the element 102 and the element 103. Thus, any two elements of the generated network are linked directly or indirectly. In this way, the one-component network generated by connecting the nearest element networks is described as a neighborhood element network Γ (not shown).

  In this way, in the neighborhood element network Γ, all the elements 100 in the information search set are linked by a link (one component), and thus the element 100 closer to the query than the arbitrary element 100 is sequentially acquired according to the link. Thus, the information search is not interrupted when the information search is performed.

Next, the flow of network generation processing will be described with reference to FIG. 3 while referring to FIG. 1 and FIG.
FIG. 3 is a flowchart showing a flow of network generation processing according to the present embodiment.
3 is a process performed when, for example, a new information search set is set as a search target or when new information (element) is added to the information search set.
First, the number k of neighboring elements, the element 100 (see FIG. 2), and the feature quantity list of the element 100 are input to the information search apparatus 1 via the input unit 4 of the information search apparatus 1 (S101) and stored. Stored in part 3.
The network generation unit 21 acquires the feature amount of the element 100 from the storage unit 3, and for each element x (xεX) that is the element 100 of the search target set X, the similarity with the other elements 100 is Calculation is performed by using the acquired feature amount (S102).
Then, when the network generation unit 21 obtains the number k of neighboring elements from the storage unit 3, based on the calculated similarity, k network elements Nk (x) having high similarity are obtained for each element x. (S103: refer to FIG. 2B) and stored in the storage unit 3. That is, the element x and each element constituting the element group Nk (x) are link-coupled. The element group Nk (x) is a set of k elements in descending order from the element having the highest similarity to the element x.
Next, the network generation unit 21 determines whether or not the process of step S103 has been performed on all the elements x in the search target set X (S104). The determination is made, for example, by adding a flag to the element x that has been processed in step S103, and determining whether or not this flag is assigned to all the elements 100 by the network generation unit 21.
As a result of step S104, when it is determined that the process of step S103 is not performed for all the elements x (S104 → No), the network generation unit 21 returns to the process of step S103.
As a result of step S104, when it is determined that the process of step S103 is performed for all the elements x (S104 → Yes), the network generation unit 21 proceeds to the process of step S105.

Next, the network generation unit 21 acquires the element group Nk (y) stored in the storage unit 3 for the element y (yεX), and the element y itself is not included in Nk (x). , Element x finds element y included in Nk (y) (see FIG. 2C). Then, the network generation unit 21 associates such an element y with Nk (x) and stores it in the storage unit 3, thereby link-linking the element x and the element y, and an undirected link to the element x. Is set (S105: see FIG. 2D).
That is, the nearest neighbor element network Γ (x) shown in Expression (7) is calculated.

Then, the network generation unit 21 determines whether or not the process of step S105 has been performed on all elements y in the search target set X (S106). The determination is made, for example, by adding a flag to the element y after step S105 and determining whether or not this flag is attached to all the elements 100 by the network generation unit 21.
As a result of step S106, when it is determined that the process of step S105 is not performed for all elements y (S106 → No), the network generation unit 21 returns to the process of step S105.
As a result of step S106, when it is determined that the process of step S105 has been performed on all elements y (S106 → Yes), the network generation unit 21 ends the process.

FIG. 4 is a diagram illustrating a storage state in the storage unit of the neighborhood element network calculated by the network generation unit.
In FIG. 4, reference numeral 200 denotes an element number of an element that is the center of the nearest element network (center element: element x in FIG. 2D, where the center element itself is not included in the nearest element network). Yes, reference numeral 201 denotes an element number of an element (symbol Γ (x) in FIG. 2D) that constitutes a nearest neighbor element network with respect to the central element. Here, it is assumed that a unique element number is assigned in advance for each element.
For example, the elements constituting the nearest element network with respect to the element with the element number “1” are the element numbers “3”, “5”, and “7”. The elements constituting the nearest element network with respect to the element with the element number “2” are the element numbers “3”, “6”, “8”, “9”, and “11”. In addition, the elements forming the nearest element network with respect to the element with the element number “3” are the element numbers “1”, “2”, “9”, and “10”.
The number of elements constituting the nearest neighbor element network is different because the number of elements y in FIG. 2C is different for each element.

  According to such a network generation process, a neighborhood element network is generated as a set of nearest neighbor element networks, which is a set of a predetermined number of neighborhood elements, so that a network with a small average shortest path length can be generated. Here, the path length is the number of links between any two nodes in the information search set. Also, according to such a network generation process, for every element in the information search set, there is a nearest element network with each element as a central element, so the nearest neighbor network with any element as a central element By acquiring, it is possible to generate a nearest neighbor element network in which all elements in the information search set are connected by links.

  Also, an element y that is an arbitrary element different from the element x in the information search set is acquired, and among elements different from the element y, a predetermined number of elements are acquired in descending order of similarity to the element y. When the set of the acquired elements is the nearest neighbor element network Γ (y), and the element x is included in the elements of the nearest neighbor element network Γ (y), the element y and the nearest neighbor element network Γ (x) The undirected link is set by using the union set of and the nearest neighbor element network for the element x. By setting the undirected link, the element x is included in the nearest element network for the element y, but it is avoided that the element y is not included in the nearest element network for the element x. It is possible to generate a neighborhood element network in which all elements in the information search set are connected by links.

(Information search process)
Next, the outline of the information search process will be described along FIG. 5 with reference to FIG.
FIG. 5 is a diagram showing an outline of the information search process according to the present embodiment.
In FIG. 5, as in FIG. 2, the code is an element in the information search set (expressed by a white circle or a black circle), that is, information stored in the storage unit 3 and to be searched.
In addition, it is assumed that a one-component neighborhood element network in which all elements are connected by links shown by broken lines in FIG.
The search processing unit 22 sets a predetermined element or an arbitrary element as a starting element x0. Then, the nearest neighbor element network Γ (x0) for the origin element x0 is acquired from the storage unit 3.
Subsequently, the search processing unit 22 sets the starting element x0 as an element of the expanded element set B (B = {x0}), and uses the obtained union of the nearest neighbor element network Γ (x0) and the expanded element set B as the degree of similarity. It is obtained as a calculation element set A (A = Γ (x0)｝ {x0}). Here, the expanded element set is a set made up of elements x when the similarity calculation between the elements of the nearest neighbor element network Γ (x) for a certain element x and the query is executed. When an element that is directly linked from the element x is expressed as a child element of the element x, it is a set of elements for which the similarity between the child element and the query is calculated. On the other hand, the similarity calculation element set is a set of elements for which similarity calculation with a query is executed. Hereinafter, the expanded element set A is simply expressed as set A, and the similarity calculation element set B is simply expressed as set B.
And the search process part 22 extracts the element with the largest similarity with the query which is not illustrated among the elements which comprise the difference set of the set A and the set B. FIG. The difference set is a set of elements that have already been subjected to similarity calculation with the query and have not yet been expanded (similarity calculation between the child element and the query has not been performed).
In this case, it is assumed that the element x1 is extracted by the search processing unit 22 as illustrated in FIG.

Next, assuming that the similarity ρ (x1, q)> similarity ρ (xmax, q) is satisfied, the search processing unit 22 converts the element x1 into the element xmax ( The element xmax is updated and held. Further, when the element x1 does not satisfy the condition, the element xmax is not updated. The search processing unit 22 acquires, from the storage unit 3, the nearest element network Γ (x1) (element connected by a link indicated by a solid line in FIG. 5C) with respect to the element x1. Here, the similarity ρ (xmax, q) is the set similarity in the claims, and the information search unit holds the set similarity by holding the element xmax.
Then, the search processing unit 22 sets a new set A as a union of a set composed of elements of the element group Γ (x1) constituting the nearest neighbor element network for the element x1 and the set A. Further, the search processing unit 22 sets the element x1 as a new set B in addition to the elements of the set B shown in FIG. Then, the search processing unit 22 extracts the element having the highest similarity with the query from the elements constituting the difference set between the new set A and the set B, and sets the element as the new element x1. (FIG. 5C): Γ (x1 → x1) That is, as shown in FIG.5C, the search processing unit 22 extracts a new element x1.

When the similarity ρ (x1, q)> similarity ρ (xmax, q) is satisfied, the search processing unit 22 holds the element x1 as a new element xmax (not shown). To do. Then, the search processing unit 22 sums the set A and the set A composed of elements of the nearest element network Γ (x1) for the element x1 (elements connected by links indicated by solid lines in FIG. 5D). The set is a new set A, and the element x1 is added to the elements of the set B shown in FIG. Then, from the elements constituting the difference set between the new set A and the set B, the element having the highest similarity with the query is extracted (FIG. 5D).
Such processing is repeated, and when the number of elements in the set A exceeds the upper limit cost β (first termination condition), or the similarity between the element x1 and the query becomes 1 (extracts elements that match the query) : Second end condition), the element xmax is set as the final output element. However, whether or not the second end condition is set depends on the information search set.

Next, the flow of the information search process will be described along FIG. 6 with reference to FIGS. 1 and 5.
FIG. 6 is a flowchart showing a flow of information search processing according to the present embodiment.
The storage unit 3 of the information search device 1 stores the cost upper limit β input in advance through the input unit 4, a list of elements and features, the starting element x 0, and the nearest neighbor element network calculated by the network generation process Γ (x) is stored for each element.
First, the search processing unit 22 acquires the starting element x0 (x0εX) from the storage unit, and acquires the nearest neighbor element network Γ (x0) for the starting element x0 from the storage unit 3 (S201). That is, the information search apparatus 1 makes the nearest neighbor element network Γ (x0) resident on a memory such as a RAM.
Next, the query q is input to the information search apparatus 1 via the input unit 4 (S202). The input of the query may be input from the terminal 11 via the physical network 10 or may be input directly from the input unit 4. In the present embodiment, the search processing unit 22 acquires the nearest neighbor element network Γ (x0) for the starting element x0 from the storage unit 3 and then inputs the query q. The search processing unit 22 may acquire the nearest neighbor element network Γ (x0) with respect to the starting element x0 from the storage unit 3.
Next, the search processing unit 22 calculates the similarity ρ (x0, q) between the starting point element x0 and the query q (S203) and stores it in the storage unit 3. Note that the search processing unit 22 may acquire the nearest neighbor element network Γ (x0) for the starting element x0 from the storage unit 3 at this time. Here, ρ (·) is a similarity function such as a cosine similarity function, for example, and the properties of ρ (a, b) = ρ (b, a) ∈ [0,1], a, b∈X Have However, the arbitrary element a has the highest similarity with itself and ρ (a, a) = 1.

Then, the search processing unit 22 calculates a set A = Γ (x0) ∪ {x0} and a set B = {x0} (S204: FIG. 5A).
Next, the search processing unit 22 calculates the number of elements | A | in the set A, and | A |> the upper limit cost β, or the similarity (set similarity) between the query q and the element xmax is 1. That is, it is determined whether or not ρ (xmax, q) = 1 (the query and the element match) is satisfied (S205). Here, | · | is the number of elements of the corresponding set. The initial element of element xmax is not particularly limited, but element x0 or the like may be substituted. Here, the calculated ρ (xmax, q) is stored in the storage unit 3.
When | A |> β or ρ (xmax, q) = 1 is satisfied as a result of step S205 (S205 → Yes), the search processing unit 22 outputs the element xmax as the final output element x2 (S206). ), The process is terminated. In the present embodiment, in the process of step S204, it is determined that | A |> the upper limit cost β or the similarity between the query q and the element xmax is 1, but in addition to this, the search process The unit 22 may monitor a timer or the like (not shown) and determine whether or not a predetermined calculation time has been exceeded.

When the condition is not satisfied as a result of step S205 (S204 → No), the search processing unit 22 calculates a difference set between the set A and the set B (S207), and calculates the difference y between the element y of the difference set and the query q. The similarity ρ (y, q) is calculated (S208).
Then, the search processing unit 22 determines whether or not the process of step S208 has been performed for all elements y (yεX) in the difference set between the set A and the set B (S209). The determination is performed, for example, by adding a flag to the element y after step S208 and determining whether or not the flag is attached to all the elements by the search processing unit 22.

As a result of step S209, when it is determined that the process of step S208 has not been performed for all elements y (S209 → No), the search processing unit 22 returns to the process of step S208.
As a result of step S209, when it is determined that the process of step S208 is performed for all elements y (S209 → Yes), the search processing unit 22 proceeds to the process of step S210.

  Next, the search processing unit 22 obtains an element x1 of Expression (8) (S210: FIG. 5B).

That is, the search processing unit 22 calculates an element w having the maximum similarity ρ (w, q), and sets this element w as an element x1 (x1εX). At the same time, the search processing unit 22 stores the similarity ρ (x1, q) related to the element x1 obtained by the expression (8) in step S210 in the storage unit 3.
Then, the search processing unit 22 acquires the similarity ρ (xmax, q) and the similarity ρ (x1, q) from the storage unit 3, and the similarity ρ (x1, q)> similarity ρ (xmax, q) It is determined whether or not (S211).
As a result of step S211, when the similarity ρ (x1, q)> similarity ρ (xmax, q) is not satisfied (S211 → No), the search processing unit 22 proceeds to the process of step S213.
As a result of step S211, when the similarity ρ (x1, q)> similarity ρ (xmax, q) (S211 → Yes), the search processing unit 22 sets the element x1 as a new element. xmax is held (S212: FIG. 5C). As described above, the similarity ρ (xmax, q) is the set similarity in the claims, and the information search unit holds the element xmax, thereby holding the set similarity.
Next, when the search processing unit 22 obtains the nearest neighbor element network Γ (x1) for the element x1 from the storage unit 3, the search processing unit 22 calculates the set A ′ = A∪Γ (x1) and the set B ′ = B∪ {x1}. Then, set A ′ is a new A and B ′ is a new B (A ← A ′, B ← B ′: S213: FIG. 5C). That is, the set A ′ is assigned to the set A, and the set B ′ is assigned to the set B.
Then, the search processing unit 22 returns to the process of step S205.

  In this embodiment, a query in which the same information exists in the elements of the information search set may be input, or a query in which the same information does not exist in the elements of the information search set is input. May be.

In the information search processing according to the present embodiment, information search is performed using a small world network having a small average shortest path length between elements. Therefore, when a metric space is defined for an information search set, a distance between elements is large. That is, an information search with a low search cost can be performed even for an information search set in which elements are sparse and the search space cannot be reduced by a triangle inequality. That is, the search space can be reduced.
In addition, since it is not premised on the definition of the distance between elements, an efficient information search can be performed even for an information search set in which a metric space cannot be defined. For example, an information search set in which the similarity between two arbitrary elements is defined by the cosine similarity is not a metric space. Furthermore, it uses a neighborhood element network that connects local element networks, which are local element collections, so that the entire information search can be a collection of searches in the lightest neighborhood element network. Can reduce the burden of unnecessary processing.
Since the element searched once is searched for information excluded from the search target after the next time, an efficient information search can be performed.

(Network characteristics)
Here, the nature of the network suitable for the present embodiment will be described.
First, in order to perform information search efficiently, the network in the present embodiment is desirably a network having a relatively small order that is a value having a strong correlation with the number k of neighboring elements. It is a one-component network in which all elements in the information search set are combined by making the order relatively small, and it is desirable that the order be relatively small. The average order in the neighborhood element network used in this embodiment is defined by Expression (9).

Furthermore, the network in the present embodiment needs to be connected by a relatively short link between an arbitrary origin element and a final output element. This is because information search with a low search cost is performed.
The average shortest path length, which is an average value in the entire neighborhood element network used in this embodiment, is defined by Expression (10).

  Here, dΓ (x, y) is the shortest path length in an arbitrary element in the network.

In addition, when the similarity between each of the neighboring element groups y∈Γ (x2) in the final output element x2 and the query q is relatively low, information search becomes difficult. This is because in order to reach the final output element x2 from the starting element x0, it is essential to pass through the element y in the vicinity of the final output element x2. That is, when the degree of similarity ρ (x2, q) and the degree of similarity ρ (x2, y) show high values, it is desirable that the degree of similarity ρ (y, q) also shows a high value. When this is generalized, the similarity ρ (x, y) and the similarity ρ (y, z) are high in the three elements x, y, z in y∈Γ (x) and z∈Γ (y). When a value is indicated, it is preferable that a high degree of similarity ρ (z, x) (x∈Γ (z)) such that x∈Γ (z) is high. That is, it is desirable that a link exists between arbitrary pair elements in the three elements x, y, and z.
The network cluster coefficient, which is a measure for quantitatively evaluating the relationship between the three elements, is defined by Expression (11). The higher the cluster coefficient, the higher the rate at which links exist between any pair of elements between any three elements.

The network characteristics suitable for this embodiment are: 1. The average order represented by equation (9) is small and the network is a one component. 2. the network has a relatively short average shortest path length; It is desirable that the network has a relatively large cluster coefficient.
A network having such characteristics is referred to as a small world network. The small world network includes the neighborhood element network described in the present embodiment. The consideration regarding the average shortest path length and the cluster coefficient in the neighborhood element network used in this embodiment will be described later with reference to FIGS. 15 and 16.

Next, along with FIGS. 7 to 14, an example of the embodiment will be described.
7 to 11 are diagrams for a search problem in which the same information as the query is included in the elements of the information search set. FIGS. 12 to 14 show the same information as the query as the elements of the information search set. It is a figure with respect to the search problem which is not contained in.

FIG. 7 is a diagram illustrating a change in the number of components with respect to the number k of neighboring elements.
In FIG. 7, the horizontal axis indicates the value of the number k of neighboring elements, and the vertical axis indicates a value obtained by applying a common logarithm to the number of components.
Note that the information search set in FIG. 7 is a set having document files in newspaper articles for 10 years as elements. And the similarity between elements was computed with the following procedures. That is, each document file is subjected to morphological analysis, unnecessary words are deleted, and words are extracted. Then, the extracted words are weighted by the tf-idf method. As a result, the resulting weighted word vector is used as the feature amount of the document file.
Then, the document file is used as an element, and the similarity between elements is defined using a cosine similarity function.
The number of elements (number of document files) used in this example is 64585, and the number of dimensions in the metric space is 51030.
As shown in FIG. 7, the number of components is 1 at k = 6. That is, when k = 6, it is possible to generate a one-component neighborhood element network. That is, if k ≧ 6 or more, a one-component neighborhood element network can be generated.

FIG. 8 is a diagram showing a change in average search cost with respect to the number k of neighboring elements.
In FIG. 8, the horizontal axis indicates the value of the number of neighboring elements k, and the vertical axis indicates the average search cost.
In FIG. 8, 100,000 pairs of elements (query and starting element pairs) are randomly selected from the elements of the document file of the newspaper articles for the 10 years described above, and this implementation is performed on the information search set described above. The result of having performed the information search process in a form is shown.
The cost upper limit is set to infinity. The average search cost is an average value of search costs when an information search is performed by changing a query and a starting point element for the same information search set.
As shown in FIG. 8, when the number of neighboring elements k = 20, the average search cost is the minimum 365.38. This value is 0.57% of the search cost when all elements are searched.

The reason why the average cost has the minimum value is considered as follows. The search cost in the present embodiment is a value that is substantially close to the product of the average order and the average step number. Here, the number of steps is the number of starting element x0 and element x1 (FIG. 5) traced until the final output element is calculated. That is, the number of black circles in FIG.
In general, the number k of neighboring elements is determined by the procedure shown in FIGS.

FIG. 9 is a diagram showing a change in the average order with respect to the number k of neighboring elements, and FIG. 10 is a diagram showing a change in the number of steps with respect to the number k of neighboring elements.
In FIG. 9, the horizontal axis indicates the number of neighboring elements k, and the vertical axis indicates the average order.
In FIG. 10, the horizontal axis indicates the number k of neighboring elements, and the vertical axis indicates the average value (Average) or median value (Median) of the number of steps.
9 and 10, when the average degree value is multiplied by the average value or the median value of the number of steps, it can be seen that the average search cost is minimized at k = 20.

FIG. 11 is a diagram showing the search cost and the arrival rate to the query for each number of neighboring elements k.
In FIG. 11, the horizontal axis indicates the search cost, and the vertical axis indicates the arrival rate.
The arrival rate is the ratio of the pair elements that have reached the query at the corresponding search cost when 100000 such pair elements (a pair of the query and the starting element) are selected.
The graph describes the cases where k = 10, 20, 40, and 60, respectively. In FIG. 8, paying attention to k = 20 having the lowest average search cost, the search cost is 291, the arrival rate is 50%, and the search cost is 633, the arrival rate is 90%. That is, among the selected pair elements, the pair element that has reached the query with a search cost of 291 is 50% of the selected pair elements, and the pair element that has reached the query with a search cost of 633 is the selected pair element. Indicates 90% of the elements.

  The total number of elements in this embodiment is 64585 as described above, and 1% of them is approximately 646. That is, if the information search processing of this embodiment is applied to the information search space of this embodiment example in the information search processing of this embodiment, even if the upper limit cost β is set to a value of about 1% of the total number of elements. It can be seen that the search succeeds with a probability of 90%.

Next, along with FIG. 12 to FIG. 14, an embodiment example when the present embodiment is applied to a search problem in which the same information as the query is not included in the elements of the information search set will be described.
The definitions of the terms in FIGS. 12 to 14 are the same as the terms in FIGS. 7 to 11.
FIG. 12 is a diagram illustrating a change in the number of components with respect to the number k of neighboring elements.
The conditions in FIG. 12 are as follows.
In FIG. 7 to FIG. 11, 6458 elements were uniformly selected from the used information search set (number of elements: 64585) and used as a query. The remaining 58127 elements were used as an information search set.
In FIG. 12, the horizontal axis indicates the value of the number k of neighboring elements, and the vertical axis indicates the value obtained by applying the common logarithm to the number of components.
As shown in FIG. 12, the number of components is 1 at k = 7. That is, it is possible to generate a one-component neighborhood element network with k = 7. That is, if k ≧ 7 or more, a one-component neighborhood element network can be generated.

FIG. 13 is a diagram showing a change in average search cost with respect to the number k of neighboring elements.
In FIG. 13, the horizontal axis indicates the value of the number k of neighboring elements, and the vertical axis indicates the average search cost.
The conditions in FIG. 13 are the same as the conditions in FIG.
The average search cost is an average value of search costs when an information search is performed by changing a query and a starting element for the same information search set.
As shown in FIG. 8, at k = 40, the average search cost is a minimum of 939.88. This value is 1.62% of the search cost when all elements are searched.
In general, the number k of neighboring elements is determined by the procedure shown in FIGS.

FIG. 14 is a diagram showing the search cost and the arrival rate to the query for each number of neighboring elements k.
In FIG. 14, the horizontal axis indicates the search cost, and the vertical axis indicates the arrival rate.
The arrival rate is obtained by dividing the distance between the currently searched element and the query by the distance between the starting element and the query.
The graph describes the cases where k = 10, 20, 40, and 60, respectively. In FIG. 13, focusing on k = 40 having the lowest average search cost, the search cost is 494, the reach is 50%, and the search cost is 1540, the reach is 90%.

  The total number of elements in this embodiment is 58127, and 3% of this is approximately 1744. That is, when the information search process of the present embodiment is applied to the information search space of the present embodiment example to the information search process of the present embodiment, the upper limit cost β (see FIG. 6) is a value of about 3% of the total number of elements. Even if it is set to, the search succeeds with a probability of 90%.

Next, the characteristics of the neighborhood element network used in this embodiment will be described with reference to FIGS. 15 and 16.
FIG. 15 is a diagram illustrating a change in average shortest path length with respect to the number k of neighboring elements in a random network, a neighboring element network, and a regular network.
Here, the random network is a network in which arbitrary elements in the information search set and elements are randomly combined. A regular network is a network in which connections between elements in an information search set are combined according to a predetermined rule.
The horizontal axis in FIG. 15 indicates the number of neighboring elements k, and the vertical axis indicates the average shortest path length.
As shown in FIG. 15, the average shortest path length of the neighboring element network (k-NN NW) at each neighboring element number k is considerably smaller than the average shortest path length of the regular network (Regular NW), and is a random network (Random NW). It has a value close to the average shortest path length.
In general, the average shortest path length in the small world network is preferably in the order of the expression (12).
log ₁₀ (average shortest path length of small world network / average shortest path length of random network) <1 formula (12)

FIG. 16 is a diagram illustrating changes in cluster coefficients with respect to the number k of neighboring elements in a random network, a neighboring element network, and a regular network.
The horizontal axis in FIG. 16 indicates the number k of neighboring elements, and the vertical axis indicates the cluster coefficient.
As shown in FIG. 16, the cluster coefficient of the neighborhood element network (k-NN NW) at each k is larger than the cluster coefficient of the random network (Random NW) and has a value close to the cluster coefficient of the regular network (Regular NW). .

It is a figure showing an example of composition of an information search system concerning this embodiment. It is a figure which shows the outline | summary of the network production | generation process which concerns on this embodiment. It is a flowchart which shows the flow of the network generation process which concerns on this embodiment. It is a figure which shows the memory | storage state in the memory | storage part of the neighborhood element network calculated by the network production | generation part. It is a figure which shows the outline | summary of the information search process which concerns on this embodiment. It is a flowchart which shows the flow of the information search process which concerns on this embodiment. It is a figure which shows the change of the number of components with respect to the number k of neighborhood elements. It is a figure which shows the change of the average search cost with respect to the number k of neighborhood elements. It is a figure which shows the change of the average order with respect to the number k of neighborhood elements. It is a figure which shows the change of the number of steps with respect to the number k of neighborhood elements. It is a figure which shows the search cost in each neighboring element number k, and the arrival rate to a query. It is a figure which shows the change of the number of components with respect to the number k of neighborhood elements. It is a figure which shows the change of the average search cost with respect to the number k of neighborhood elements. It is a figure which shows the search cost in each neighboring element number k, and the arrival rate to a query. It is a figure which shows the change of the average shortest path length with respect to the number k of neighborhood elements in a random network, a neighborhood element network, and a regular network. It is a figure which shows the change of the cluster coefficient with respect to the number k of neighborhood elements in a random network, a neighborhood element network, and a regular network. It is a figure which shows the cumulative distribution of the distance between this pair element by selecting 1 * 10 < ⁶ > pair elements (two elements) at random from information search space. It is a figure which shows the cumulative distribution of the lower bound of the distance on the conditions similar to FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Information search apparatus 2 Processing part 2 Network generation process part 3 Storage part 4 Input part 5 Output part 10 Network 11 Terminal 12 Information search system 21 Network generation part 22 Search process part

Claims (5)

An information search method in an information search apparatus for searching for information similar to a query from an information search set held in a storage unit,
The information search method includes a network generation process and an information search process,
The network generation process includes:
A network generation unit of the information search device;
A two-component network is created by directly linking between any two elements in the information search set, or indirectly through elements other than the two elements, and stored in the storage unit Let
The information search process includes:
The search processing unit of the information search device,
(A1) An element directly linked to the predetermined first element of the network is acquired from the storage unit, and the element having the highest similarity to the query among the elements is the second element Select as
(A2) If the similarity between the second element and the query is greater than a predetermined set similarity held in the storage unit, the similarity between the second element and the query is updated Is stored in the storage unit as a set similarity,
(A3) The second element is set as a third element, and an element that is directly linked to the third element is acquired from the storage unit,
(A4) Of the elements that are directly linked to the third element, elements that have never become the second element in the past and that have the largest similarity to the query An information search process for searching for an element similar to the query by performing the process (a2) on the new second element, and selecting the new second element;
The information search method characterized by performing. The network generation process is performed by the network generation unit.
Calculating the similarity between an element x that is an arbitrary element in the information search set and each element other than the element x;
Obtaining a predetermined number of elements set in advance in descending order of similarity to the element x among elements other than the element x, and linking the acquired element with the element x 2. The information search method according to claim 1, wherein the process of generating a nearest neighbor element network Γ (x) for the element x is performed for all elements in the information search set. The information search process includes:
The search processing unit
Obtaining the nearest element network Γ (x0) for an element x0, which is an arbitrary element in the information search set, and xmax, which is an arbitrary element, from the storage unit;
When the query q is input via the input unit,
(B1) A set A and a set B in which A = Γ (x0) ∪ {x0}, B = {x0} are calculated,
(B2) An element x1 satisfying the following expression (8) is acquired from the set AB,

Where ρ (a, b) is the similarity between elements a and b in the information search set, | A | is the number of elements in set A, and AB is elements A and B. Is the nearest element network (b3) ρ (x1, q)> ρ (xmax, q) for the element a, the element x1 is set as a new element xmax,
(B4) Substitute A∪Γ (x1) for A, Substitute B∪ {x1} for B,
(B5) The processes (b2) to (b4) are repeated,
3. The information search method according to claim 2, wherein when | A | exceeds a predetermined value β, or when the query matches the element x 1, the element xmax is output as a final output element.   An information search program that causes a computer to execute the information search method according to any one of claims 1 to 3. An information search device for searching for information similar to a query from an information search set held in a storage unit,
The information search apparatus includes a network generation unit and a search processing unit,
The network generation unit
A two-component network is created by directly linking between any two elements in the information search set, or indirectly through elements other than the two elements, and stored in the storage unit Has a function to
The search processing unit
(A1) An element directly linked to the predetermined first element of the network is acquired from the storage unit, and the element having the highest similarity to the query among the elements is the second element Select as
(A2) If the similarity between the second element and the query is greater than a predetermined set similarity held in the storage unit, the similarity between the second element and the query is updated Is stored in the storage unit as a set similarity,
(A3) The second element is set as a third element, and an element that is directly linked to the third element is acquired from the storage unit,
(A4) Of the elements that are directly linked to the third element, elements that have never become the second element in the past and that have the largest similarity to the query It has a function of selecting a new second element and searching for an element similar to the query by performing the process (a2) on the new second element. Information search device.

Images