JP5457946B2 - Related word calculation device, related word calculation method, and related word calculation program - Google Patents

Description

  The present invention relates to a technique for calculating related words based on word co-occurrence frequencies.

  A synonym calculation device according to the related art (for example, Patent Document 1) uses at least two types of association degree dictionaries, initializes word groups based on one association degree dictionary, and reflects at least two types of associations. Create a synonym dictionary. Then, a synonym group is created by merging word groups based on these relevance dictionaries.

Japanese Patent No. 3553795

  The prior art aims at creating synonym groups. In the related art, when a related word having a broader meaning than a synonym is obtained, a simple related word such as a higher-level concept word or the same kind of word is used in the countermeasure of simply changing the threshold value to a relatively large value. In addition, there is a problem that unrelated words are integrated.

  In addition, the feature amount for each word is represented by a vector, each word is defined as an individual group as an initial state, and the distance between the group and the vector center of gravity of the word included in the group is calculated, and two groups are calculated. There is a clustering technique that calculates a similar distance assuming a group after integration, and sequentially integrates the groups with the smallest increase in distance before and after integration. Even in this method, by setting a threshold for the amount of increase in group distance, words that are close to each other are integrated. However, if the threshold is increased, unrelated words are also integrated. Exists.

The invention Oite grouping of words, in addition to processing the distance between the groups to integrate smallest group pairs in integration, integration groups of both if the two groups are not suitable conditions for integration Exclude from As a result, related words in a wider range than synonyms can be obtained with high accuracy.

The related word calculation device according to the present invention is a related word calculation device for grouping words, which is created based on the co-occurrence frequency of each word from a statistical information database storing co-occurrence frequency information between words. and grouping means for forming groups of each word based on the vector of each word, upon the integration of the two groups as the distance between the calculated arbitrary from the values of two groups based on the vectors of the group to which the created a calculation for calculating the amount of increase in diffusivity performed for the set of all the groups, the ratio of the diffusivity of each group before integration with the calculated distance calculated respectively, the value of the two ratios is either a set of inter-group calculation means excluded from the integration of both groups of groups also exceeds the threshold, integrated between groups from the set of groups left by the exclusion If the distance between the selected groups is less than a threshold value, the pair of groups is provided to the grouping means while the distance is a threshold value. In the case of the above, a grouping determination unit that outputs data of each group of the pair is provided.

An aspect of the related word calculation method of the present invention is a related word calculation method for grouping words, wherein the grouping means calculates the co-occurrence frequency of each word from a statistical information database storing co-occurrence frequency information between words. A step of creating a group of each word based on a vector of each word created based on, and a calculation means between groups as a distance between any two groups from a value calculated based on the vector of each created group Performing a calculation to calculate the amount of increase in diffusivity during the integration of the two groups for all groups, and calculating the ratio between the calculated distance and the diffusivity of each group before integration, and excluded from step integrating both groups of pairs of groups value of the two ratios is greater than the both the threshold, grouping determination means, remaining by the exclusion The group pair that minimizes the distance between the groups when the group is integrated from the set of selected groups is selected. If the distance between the selected groups is less than the threshold, the group pair is selected. And providing to the grouping means, and outputting the data of each group of the pair when the distance is greater than or equal to a threshold value.

  In the above invention, in the group integration in which the distance in the integration is the minimum, even if two correct groups are not integrated due to the effect of the incorrect integration, the above-mentioned erroneous integration is applied by applying other integration conditions. By excluding group integration from the target, related terms in a wider range than synonyms can be calculated with higher accuracy.

  In addition, this invention can also be made into the aspect of the related word calculation program which makes a computer function as each means which comprises the said related word calculation apparatus.

  According to the above invention, related words in a wider range than synonyms can be obtained with high accuracy.

The block diagram of the related word calculation apparatus which concerns on embodiment of invention. The flowchart figure explaining the operation example of the related word calculation apparatus which concerns on 1st embodiment of invention. The flowchart figure explaining the operation example of the related word calculation apparatus which concerns on 2nd embodiment of invention. The figure which showed an example of word statistical information data. The figure which showed an example of vector data. The figure which showed an example of group data (at the time of initialization). The figure which showed an example of group data. The figure which showed an example of the distance data of the group from which the distance with respect to each group becomes the minimum. The figure which showed an example of the group before performing a group exclusion based on the ratio of the increase of the spreading | diffusion degree at the time of integration, and a spreading | diffusion degree. The figure which showed an example of the group after performing the exclusion of a group based on the ratio of the increase of the spreading | diffusion degree at the time of integration, and a spreading | diffusion degree.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings, but the present invention is not limited to the following embodiments.

[Embodiment 1]
(Overview)
The related term calculation apparatus according to the first embodiment integrates both groups in a case where two groups are not suitable for integration, in addition to the process of integrating the group pair that minimizes the distance between the groups in the integration. Exclude from

(Device configuration)
The related word calculation apparatus 100 of this embodiment shown in FIG. 1 includes a word statistical information database 110, a vector creation unit 120, a grouping unit 130, an inter-group calculation unit 140, a grouping determination unit 150, a work area 160, and a group. It consists of a data pace 170.

  The function units 110 to 170 of the related word calculation device 100 are realized by hardware resources of a computer, for example. That is, the related word calculation device 100 includes hardware resources related to a computer such as a CPU, a memory, a storage device (for example, a hard disk drive device), an input device, and an output device. Then, the functional units 110 to 170 are implemented by cooperation of these hardware resources with software resources (OS, applications, etc.).

  The word statistical information database 110 stores in advance co-occurrence frequency information between words as illustrated in FIG. The illustrated word statistical information database stores co-occurrence information of word 1 and word 2 and appearance frequency data.

  The vector creation unit 120 creates a vector of each word based on the co-occurrence frequency of each word extracted from the word statistical information database 110. The created vector of each word is output to the work area 160.

  The grouping unit 130 creates a group of each word based on the created vector of each word. In the initial processing stage, the grouping unit 130 creates group data for each word based on the vector elements extracted from the work area 160 and outputs the data to the work area 160. When the grouping determination unit 150 determines that two groups can be grouped, the grouping unit 130 integrates the two groups, updates the group data, and reflects the group data in the work area 160.

  The inter-group calculation unit 140 performs a calculation for calculating the distance between any two groups from the values calculated based on the vectors of the groups held in the work area 160, and based on the distances. Groups whose value exceeds the threshold are excluded from grouping.

  The grouping determination unit 150 selects a pair of groups that minimizes the distance between the groups when the groups are integrated from the set of groups left by the exclusion. When the distance between the selected groups is less than the threshold, the group pair is provided to the grouping unit 130. On the other hand, if the distance is greater than or equal to the threshold value, the data of each group in the pair is output to the group database 170.

(Description of processing flow)
The processing flow (S100 to S160) of the related word calculation device 100 will be described based on a specific example with reference to FIG.

  S100: The vector creation unit 120 creates a vector of each word based on the co-occurrence frequency of each word stored in the word statistical information database 110 and outputs it to the work area 160.

  Specifically, for example, based on the data in the word statistical information database 110 shown in FIG. 4, a vector whose element is the co-occurrence frequency of the word w2 with respect to the word w1 shown in FIG. 5 is created. Individual identifiers (IDs) are assigned to the words w1,..., Wn in the vector data 5 shown in FIG. A vector characterizing the word w1 is represented by each element of the co-occurrence words w1,..., Wn for the target word w1. Further, in order to perform normalization so that the sum of the vector values of each word becomes 1, processing for dividing each vector element by the sum of all the vectors of each word is performed. The created vector is output to the work area 160.

  S <b> 110: The grouping unit 130 extracts each word vector created in S <b> 100 from the work area 160, creates a group of each word, and outputs the group to the work area 160.

  In the initial processing of S110, group data 6 illustrated in FIG. 6 is created in order to make each word a single group. The identifier gID column of each word group in the group data 6 stores an identifier that matches the identifier ID of each word in the vector data 5 shown in FIG. 5, and the identifier ID in the vector data 5 is stored in the word list column. The target word corresponding to is stored. Further, the group data 6 also stores the calculated degree of diffusion of each group provided for S120 (operation processing by the inter-group calculation unit 140). The vector data 5 is treated as a vector corresponding to each group in the subsequent steps.

  S120: The inter-group calculation unit 140 extracts a vector of each group created in S110 from the work area 160, and calculates a distance between any two groups from a value calculated based on this vector for all groups. This is done for

  As an index of the distance between groups, for example, “amount of increase in diffusivity associated with integration of two groups” can be cited. If the degree of diffusion is smaller, the degree of data bias becomes higher. Since group integration works in a direction to increase the value of diffusion, the smaller the increase in diffusion during integration, the more the group characteristics are retained. It becomes easy and it becomes the optimal state in all groups. Note that the method is not limited to the method using the degree of diffusion as long as similar results can be obtained depending on the degree of group cohesion and the degree of distinction between groups.

  For example, when the vector data 5 shown in FIG. 5 is used for the diffusivity K (A) of the group A, the vector tf (A, i) (i = 1,..., N) for the group A and the number of words belonging to A In the case of NA, it is calculated from the diffusivity of each vector element by the calculation according to the following equation (1). Note that the diffusivity K (B) of the group B provided for the later-described equation (3) can also be calculated by the same calculation.

  The degree of diffusion K (AB) after the integration of group A and group B is calculated by the calculation according to the following equation (2).

  Then, the amount of increase D (A, B) of the diffusivity when the group A and the group B are integrated is calculated by the following equation (3).

D (A, B) = K (AB) − (K (A) + K (B)) (3)
The above calculation is performed for all groups. Then, as illustrated in FIG. 8, the data of the group set that minimizes the increase (D) is selected for each group on the gID (A) side and stored in the work area 160. When gID (A) and gID (B) are exchanged to form the same pair, only a pair having a smaller group identifier of gID (A) is selected to avoid duplication.

  S130: The inter-group calculation unit 140 extracts a group whose value based on the distance (difference increase amount D) calculated in S120 exceeds a threshold value from the work area 160, and excludes the group from integration.

  Compare the diffusion amount K (A), K (B) of the two groups A, B before integration with the increase D (A, B) of the diffusion degree K (AB) when the groups A, B are integrated. The value of D may occupy most of K (A) or K (B). In this case, since the difference in the word appearance status of each group is large, even if the determination of whether or not to perform the integration in the grouping determination unit 150 in S150 described later is satisfied, the semantically different groups are integrated. The Therefore, as a value based on the distance (difference increase amount D) calculated in S120, “D (A, B) / K ( A) "and" D (A, B) / K (B) ". When the ratios “D (A, B) / K (A)” and “D (A, B) / K (B)” exceed a predetermined threshold, they are excluded from the processing targets. A set of remaining groups from which groups exceeding the threshold are excluded is output to the work area 160.

  S140: The grouping determination unit 150 selects a group pair that minimizes the distance between groups stored in the work area 160 obtained in S120, from the set of remaining groups obtained by the exclusion in S130. .

  S150: The grouping determination unit 150 determines whether the pair of groups selected in S140 can be integrated based on the value of the distance between the groups.

  Specifically, it is determined whether integration is possible by determining whether the distance between groups satisfies a predetermined threshold. If the distance value is less than the threshold (Yes), it is determined that integration is possible, and the group pair is provided to S160 to continue the integration process. On the other hand, when the value of the distance is greater than or equal to the threshold (No), the group pair is used in S170 to end the integration process.

  S160: The grouping unit 130 updates the vector of the word set of the group data and the data of the diffusion degree by integrating the pair of groups provided from S150.

  In updating the group data, the vector data is integrated into a group having a small identifier ID which is a group number, and the appearance frequency of words is added. The words in the word list of the group data to be integrated belong to the group with the smaller group number, and the diffusivity of the smaller group is updated to the value after integration. If a word belonging to a group is empty, the group is already integrated and is not necessary for the subsequent processing, and is therefore excluded from the processing target. The group data 6 updated in this way is provided to S120.

  S170: When the grouping determination unit 150 determines in step S150 that the distance is equal to or greater than the threshold (No), the grouping determination unit 150 ends the integration process of S120 to S160. Then, the group data 7 obtained by integrating the words as illustrated in FIG. 7 obtained by the integration process is extracted from the work area 160 and output to the group database 170.

(Effect of Embodiment 1)
As described above, according to the present embodiment, in the grouping of words, in addition to the integration of the group that minimizes the distance between the groups in the integration, the two groups are not suitable for the integration. Are excluded from consolidation. As a result, related words in a wider range than synonyms can be obtained with high accuracy.

  In particular, as in S <b> 130, the ratio of the diffusivity of each of the two groups and the ratio of the distance between the groups is calculated for all groups, and the group whose distance exceeds the threshold is excluded from the integration targets. As a result, integration of related terms depending on the spread of the group is realized.

  In S130, the ratio between the amount of increase in diffusivity during integration and the diffusivity of each group “D (A, B) / K (A)” and “D (A, B) / K (B)” is predetermined. A difference between when the threshold value is exceeded and before the exclusion from the integration processing target will be described with reference to FIGS. 9 and 10. Here, when the threshold value of the ratio between the amount of increase in diffusivity at the time of integration and the diffusivity of each group is “0.3”, and the threshold value of the distance between two groups in the grouping determination unit 150 is “4” The case of will be described.

  Before removal based on the threshold value of the ratio between the amount of increase in diffusivity during integration and the diffusivity of each group, as shown in FIG. 9A and FIG. It is included. The illustrated numerical value indicates the value of the group diffusion degree K, and the numerical value in parentheses indicates the value of the increase amount D of the diffusion degree at the time of integration.

  Considering the case of exclusion by the ratio threshold, the groups to which “train”, “number”, and “large” illustrated in FIG. 9C belong are K (A) = 3.7 and K (B) = 2. .8, D (A, B) = 0.9, the value of the ratio is D (A, B) / K (B) = 0.32, which exceeds the threshold “0.3”. If it is excluded from the integration targets based on this threshold, “train” is not integrated into the group to which “number” and “many” belong, as shown in FIG.

  As shown in FIG. 10A, “train” belongs to a group including words related to railways in preference to “bus stop” and “route bus”. Accordingly, “bus stop” and “route bus” belong to a group including a bus including “limousine bus” and a word related to movement of public transportation as illustrated in FIG.

  As described above, the “train”, the “bus stop”, and the “route bus” are appropriately integrated by the integration process depending on the amount of increase in diffusion.

[Embodiment 2]
(Overview)
The related word calculation apparatus 100 according to the second embodiment can perform integration even if two groups are not grouped in the group integration that minimizes the distance in the integration, if the integration is possible by considering other conditions. Perform integration of both groups.

  In the grouping determination process of S150 according to the first embodiment, even if it is determined that the distance between groups (the amount of increase in the degree of diffusion) is greater than or equal to the threshold value, the grouping is not so much as the group that has already been grouped. It may be possible to integrate with small groups that are not.

  Therefore, in the second embodiment, when it is determined in S150 that the distance between groups (the amount of increase in the degree of diffusion) is equal to or greater than the threshold, the number of elements in which the group vector elements are positive as a large group is greater than the threshold. As a small group, a pair of groups having the number of elements whose group vector elements are positive is smaller than a threshold value is subjected to integration processing. As a result, related words in a wider range than synonyms can be calculated more accurately.

(Device configuration)
The related word calculation apparatus 100 according to the second embodiment has the same device configuration as the related word calculation apparatus 100 according to the first embodiment except that the related word calculation apparatus 100 includes a grouping determination unit 150 that executes a processing procedure different from that of the first embodiment.

(Description of processing flow)
A processing flow (S100 to S180) of the related word calculation device 100 according to the second embodiment will be described with reference to FIG.

  S100: The vector creation unit 120 creates a vector of each word based on the co-occurrence frequency of each word stored in the word statistical information database 110 and outputs it to the work area 160.

  S <b> 110: The grouping unit 130 extracts each word vector created in S <b> 100 from the work area 160, creates a group of each word, and outputs the group to the work area 160.

  S120: The inter-group calculation unit 140 extracts a vector of each group created in S110 from the work area 160, and calculates a distance between any two groups from a value calculated based on this vector for all groups. This is done for Then, for each group, the data of the group having the smallest increase (D) is selected and stored in the work area 160.

  S130: The inter-group calculation unit 140 extracts a group whose value based on the distance (difference increase amount D) calculated in S120 exceeds a threshold value from the work area 160, and excludes the group from integration.

  S140: The grouping determination unit 150 selects a group pair that minimizes the distance between groups stored in the work area 160 obtained in S120, from the set of remaining groups obtained by the exclusion in S130. .

  S150: The grouping determination unit 150 determines whether the pair of groups selected in S140 can be integrated based on the value of the distance between the groups. Specifically, it is determined whether integration is possible by determining whether the distance between groups satisfies a predetermined threshold. If the distance value is less than the threshold (Yes), it is determined that integration is possible, and the group pair is provided to S160 to continue the integration process. On the other hand, when the distance value is equal to or greater than the threshold value (No), the group pair is provided to S180.

  S160: The grouping unit 130 updates the vector of the word set of the group data and the data of the diffusion degree by integrating the pair of groups provided from S150. The updated group data 6 is provided to S120.

  S180: The grouping determination unit 150 has a ratio of the number of elements in which the element values of all the vector elements of one group are positive among the pair of groups provided from S150 equal to or greater than a predetermined threshold, and the other group When the ratio of the number of elements having positive element values in all the vector elements is less than a predetermined threshold (Yes), the group pair is used in S160 to continue the integration process. On the other hand, when the condition for continuation of the integration process is not satisfied (No), the pair of the group is used in S170 to end the integration process.

  S170: If the grouping determination unit 150 determines in step S180 that the conditions for continuing the integration process are not satisfied (No), the grouping determination unit 150 ends the integration process of S120 to S180. Then, the group data 7 obtained by integrating the words as illustrated in FIG. 7 obtained by the integration process is extracted from the work area 160 and output to the group database 170.

(Effect of Embodiment 2)
As described above, in the group integration in which the distance in the integration is minimized, even if two groups are not integrated, if the integration is possible by considering other conditions, the two groups are used for the integration. Therefore, related words in a wider range than synonyms can be obtained with higher accuracy.

  In the second embodiment, a further limitation is imposed on the integration processing of a pair of groups including a group in which the number of elements in which the group vector elements are positive is greater than the threshold and a group in which the number of elements in which the group vector elements are positive is less than the threshold. May be provided. Specifically, in S180, the ratio of the number of elements in which the element values in all the vector elements of one selected group are positive is equal to or greater than a predetermined threshold value, and the element values in all the vector elements in the other group are positive. What is necessary is just to use for the update process of S160 the pair of the group whose ratio of the number of elements which are less than a predetermined threshold value, and the distance between groups is less than a threshold value. By this processing, related words in a wider range than synonyms can be calculated with even higher accuracy.

[Aspect as Program of the Present Invention]
A part or all of the functions of each of the functional units 120 to 150 in the related word calculation device 100 of the embodiment described above is configured by a computer program, and the related word calculation program is executed by the computer to realize the present invention. Can do. Moreover, the procedure in the related word calculation method of this embodiment can be comprised by the program of a computer, and this computer can be made to run this related word calculation program. Further, a program for realizing the above functions on a computer is recorded on a computer-readable recording medium such as FD (Floppy (registered trademark) Disk), MO (Magneto-Optical disk), ROM (Read Only Memory), It can be recorded on a memory card, CD (Compact Disk) -ROM, DVD (Digital Versatile Disk) -ROM, CD-R, CD-RW, HDD, removable disk, etc., and can be stored or distributed. is there. It is also possible to provide the above program through a network such as the Internet or electronic mail.

DESCRIPTION OF SYMBOLS 100 ... Related word calculation apparatus 110 ... Word statistics information database 120 ... Vector preparation part (vector preparation means)
130 ... Grouping unit (grouping means)
140 ... Inter-group calculation section (inter-group calculation means)
150 ... Grouping determination unit (grouping determination means)
160 ... work area 170 ... group database

Claims (5)

A related word calculation device for grouping words,
A grouping means for creating a group of each word based on a vector of each word created based on a co-occurrence frequency of each word from a statistical information database storing co-occurrence frequency information between words;
A calculation for calculating the amount of increase in diffusivity at the time of integration of the two groups as a distance between any two groups from a value calculated based on the generated vector of each group is performed for all sets of groups. And calculate the ratio between the calculated distance and the diffusivity of each group before integration, and exclude both groups in the group of groups whose two ratio values both exceed the threshold from the integration target Inter-group calculation means,
When a group pair that minimizes the distance between the groups is selected from the set of groups left by the exclusion and the distance between the selected groups is less than a threshold, the group A related word calculation apparatus comprising: a grouping determination unit that outputs the data of each group of the pair when the pair is provided to the grouping unit and the distance is equal to or greater than a threshold value. The grouping determining means is configured such that the ratio of the number of elements in which the element values in all vector elements of one group are positive in the pair of groups is equal to or greater than a predetermined threshold value and the element values in all vector elements of the other group the proportion of the number of elements to be positive is less than a predetermined threshold value, related word calculation device according pairs of said groups in claim 1, characterized in that in addition to the condition to be subjected to the grouping means. A related word calculation method for grouping words,
A step of creating a group of each word based on a vector of each word created based on the co-occurrence frequency of each word from a statistical information database in which the grouping means stores co-occurrence frequency information between words;
The inter-group calculating means calculates all the calculations for calculating the amount of increase in diffusivity when integrating the two groups as the distance between any two groups from the values calculated based on the created vector of each group. This is done for a group of groups, and the ratio between the calculated distance and the diffusivity of each group before integration is calculated separately, and both groups of the group of groups whose two ratio values both exceed the threshold are integrated. A step to be excluded from
The grouping determination means selects a pair of groups that minimizes the distance between the groups when the group is integrated from the set of groups left by the exclusion, and the distance between the selected groups is less than the threshold value. A pair of the group is provided to the grouping means, and if the distance is greater than or equal to a threshold value, data of each group of the pair is output. Method of calculation. In providing the group pair to the grouping means, the ratio of the number of elements in which the element values of all vector elements of one group are positive among the pair of groups is equal to or greater than a predetermined threshold and the other group 4. The method according to claim 3 , further comprising adding, as a condition for providing the group pair to the grouping means, that a ratio of the number of elements having positive element values in all vector elements is less than a predetermined threshold value. The related word calculation method described. A related word calculation program for causing a computer to function as each means constituting the related word calculation device according to claim 1 .

Images