JP2003067412A - Method for extracting feature item from data - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a keyword extracting method which can extract keywords even from a short sentence with comparatively high precision. SOLUTION: Words which appear frequently are extracted from words in sentences in step S2-2, and keywords are selected from among the words based on the deviation of the co-occurrence probability distribution between each word and the words which appear frequently are provided in step S2-3. The χ<2> test is used for verifying the significance in the deviation.

Description

Detailed Description of the Invention

[0001]

TECHNICAL FIELD The present invention relates to a method for extracting characteristic items from data. In particular, the present invention relates to a method for extracting keywords from text.

[0002]

BACKGROUND OF THE INVENTION As a keyword extraction method from a document,
TFIDF is well known. In this method, the appearance tendency of words in documents included in the same category is extracted as df, and the characteristic word is extracted by comparing it with the tf value of the data itself. This method can be used if the size of the target data is above a certain level.
It can be applied alone. However, when the amount of data is small, there is a problem that it is difficult to apply.

In addition, studies have also been conducted to discriminate general words from important words by the χ ² test. However, even in this research, a method of accurately obtaining a keyword with a small amount of data has not been realized.

[0004]

SUMMARY OF THE INVENTION The present invention has been made in view of the above circumstances, and a characteristic item extracting method capable of extracting a characteristic item with relatively high accuracy even with a small amount of data. The purpose is to provide.

[0005]

According to a first aspect of the present invention, there is provided a characteristic item extraction method including the following steps. (1) A step of extracting a frequent item from the items in the data, (2) A step of extracting a characteristic item from the item based on the bias of the co-occurrence probability distribution of each item and the frequent item.

According to a second aspect of the present invention, in the feature item extraction method according to the first aspect, the data is a sentence or a part thereof, and the item is a single word or a plurality of words.

A third aspect of the present invention is the feature item extraction method according to the second aspect, wherein the co-occurrence probability is calculated based on co-occurrence in the same sentence.

According to a fourth aspect of the present invention, in the feature item extraction method according to the second aspect, the co-occurrence probability is calculated based on the co-occurrence within a prescribed number of words before and after the frequent item.

According to a fifth aspect of the present invention, in the characteristic item extracting method according to any one of the second to fourth aspects, the frequent items are clustered by grouping together those items having a relatively high probability of appearing in the same sentence. However, the bias of the co-occurrence probability distribution is calculated between each item and the clustered frequent item.

According to a sixth aspect of the present invention, in the characteristic item extraction method according to any one of the first to fifth aspects, the "based on the bias of the co-occurrence probability distribution of each item and the frequent item,
Extracting a characteristic item from the item "
It includes the following steps. (A) Obtaining information indicating a frequency distribution of each frequent item in the data, (b) Obtaining information indicating a frequency distribution of co-occurrence degrees between the frequent item and each item, (c) Each Obtaining a bias of the co-occurrence probability distribution based on information indicating the frequency distribution of the frequent items and information indicating the frequency distribution of the co-occurrence degree.

According to a seventh aspect of the extraction method of the sixth aspect, the "information indicating the frequency distribution of each frequent item" is added.
Is information indicating the appearance probability of each frequent item.

An eighth aspect of the present invention is the feature item extraction method according to any one of the first to seventh aspects, wherein the bias of the co-occurrence probability distribution is calculated as the magnitude of the χ ² value in the following equation. . However, in this expression, w: item, g: frequent item, G: set of all frequent items p _g : appearance probability of frequent item (g), n _w : set of item (w) and all frequent item (G) The total number of co-occurrence frequencies with frequent items inside, cooc (w, g): co-occurrence frequency of item (w) and frequent items (g).

A ninth aspect of the present invention is p _g = (frequency of appearance of frequent items (g)) / (total frequency of appearance of all frequent items (g) belonging to set (G)) in claim 8, and n _w is
The feature item extraction method is the total number of co-occurrence frequencies of the item (w) and the frequent item (g) in the set (G).

A tenth aspect is the same as the eighth aspect, wherein p _g =
(Total number of words in sentence where frequent item (g) appears) / (total number of words in entire document), and n _w is the item
(w) is a characteristic item extraction method that is the total number of words of the appearing sentence.

[0015] The eleventh aspect of the present invention includes a CPU and a storage unit that can be used by the CPU, the storage unit includes a frequent item extraction module and a characteristic item determination module, and the frequent item extraction module is a data item. The operation of extracting frequent items from the items in
Software for causing a PU to perform, wherein the characteristic item determination module causes the CPU to perform an operation of extracting a characteristic item from the item based on a bias of a co-occurrence probability distribution of each item and a frequent item. It is a feature item extraction system.

A twelfth aspect of the present invention is a computer-readable or computer-readable program that causes a computer to execute the functions of the steps in the characteristic item extraction methods according to the first to tenth aspects.

A thirteenth aspect is the frequent item extraction module in the characteristic item extraction system according to the eleventh aspect.

A fourteenth aspect is the characteristic item determination module in the characteristic item extraction system according to the eleventh aspect.

[0019]

BEST MODE FOR CARRYING OUT THE INVENTION A characteristic item extraction method according to an embodiment of the present invention will be described below with reference to the accompanying drawings. In the examples below, text is used as an example of data. In this case, as the characteristic item,
It becomes a keyword.

First, the configuration of the characteristic item extraction system used for implementing this method will be described. This system includes a CPU 1, an interface unit 2 and a CP.
The storage unit 3 usable by U1 and the communication unit 4 are provided. Such a system can be composed of, for example, a personal computer or a workstation.

The interface unit 2 has a function of interfacing between an operator and a computer, and includes, for example, an input device such as a keyboard and a mouse and an output device such as a display.

The storage unit 3 includes document data 31, a frequently-used word (corresponding to frequently-used item) extraction module 32, and a keyword (corresponding to characteristic item) determination module 33. The document data 31 is the data of the text to be extracted. The frequent word extraction module 32 is software that causes the CPU 1 to perform “an operation of extracting a frequent word from a word (corresponding to an item) in a sentence (corresponding to data)”. The keyword determination module 33 is software that causes the CPU 1 to perform “an operation of extracting a characteristic item from an item based on the bias of the co-occurrence probability distribution of each item and the frequent item”. Details of the operation of each module will be described in the description of the extraction method described later. The storage unit 3 can be configured by any hardware, for example, a hard disk. The software used for implementing the present embodiment, including the modules 32 and 33, can be recorded in any computer-usable or readable recording medium.

The communication unit 4 is used for communication with an external computer, and is, for example, a network card or a modem.

Next, a keyword (feature item) extraction method according to this embodiment will be described. First, the overall procedure will be described with reference to FIG.

(Step S2-1) In this step,
Get word information in a sentence. First, a sentence (or a part thereof) is decomposed into sentence units and word (word) units, and the decomposition result is recorded in the document data 31. Here, the type of language does not matter. For example, when the language is Japanese, the decomposition into word units can be performed using a normal morphological analysis. Also, idioms (word sequences) that appear more than once in a sentence
Is also understood as a word. That is, in this embodiment, the word is meant to include an idiom. For example, "optimization
If the word "problem" appears more than once in a sentence, it is understood as "optimization" and "problem", and also as the idiom "optimization problem". Also, in the sentence 3
You may grasp a compound word (sequence of words) that appears more than once as one word. Furthermore, an upper limit of the number of words that make up a phrase may be set. Further, it is possible to perform processing such that when the sequence of words "optimization problem" is grasped as a compound word "optimization problem", it is not grasped as separate words "optimization""problem".

If the language is Japanese, only nouns, verbs, adjectives, adjectives and unknown words are extracted as words. Further, general words such as “koto”, “things”, “do”, “naru” are deleted as unnecessary words. If the language is English, for example, delete unnecessary words known as Salton stop words. Thus, it is desirable to process unnecessary words regardless of language. If the language is Japanese, verbs, adjectives, and adjectives are in the original form of the word or the stem form. If the language is English, a processing called stemming is performed to remove ing and ed, which are inflection endings of verbs, and plural s.
Regardless of the language, it is desirable to process the inflection of words. In the present embodiment, a word that appears n times in the same sentence is directly understood as the appearance frequency of n times. However, if it appears n times in the same sentence, it can be grasped as one appearance frequency. For example, suppose the sentence "In Japanese, morphological analysis is performed and only nouns, verbs, and adjectives are written in the original form."
First, the sentence is written as "In Japanese, morpheme, noun, verb, adjective, protomorph, and write." Each word in this sentence is taken. The function of this step is
It is executed by the frequent word extraction module 32.

(Step S2-2): Corresponding to step (1) of claim 1, a frequently-used word is extracted from the word. The extraction of frequent words is performed as follows. That is, the appearance frequency is calculated for each word in the target sentence, and the word with the high frequency (for example, the top 10 words of 1000 words in the entire sentence) is set as the frequent word. Here, in the present embodiment, when grasping frequently-used words, those having a high probability of appearing together in the same sentence are clustered together. One frequent word in this embodiment indicates one group thus clustered.

An example of clustering of frequently-used words is shown below.
The Jaccard coefficient for the number of sentences in which word a and word b appear is the threshold value (0.5)
If it exceeds, the words a and b are in the same cluster (that is, the same frequent word). The Jaccard coefficient J (a, b) is given by the following formula, and indicates the degree of overlap between the sets of the word a and the word b.

However, S (a∩b) is the number of sentences in which both word a and word b appear, and S (a∪b) is the number of sentences in which word a or word b appears. As a clustering method, in addition to the method using Jaccard coefficient, the method using co-occurrence frequency of both words, the method using mutual information, and the similarity of distribution of co-occurrence with other words are used. There are ways. The method using the similarity of the distribution of co-occurrence with other words is, for example, word a and other words c, d,
If e, ..., x, y, z, word b and other words c, d, e, ..., x, y, z have similar co-occurrence distributions, word a and word b are in the same cluster It is what In other words, it is an operation of putting together two columns having similar distributions in the co-occurrence matrix. Note that clustering is performed after acquiring the frequency of co-occurrence degrees between words and frequently-used words, which will be described later, and the frequency of co-occurrence degrees of words belonging to the same cluster is added together to be one. . However, the timing of clustering is not limited to this, and may be performed before that. In this case, first, the co-occurrence degree is acquired in cluster units. By performing such clustering, similar words can be collectively counted when the co-occurrence degree is obtained, and the co-occurrence matrix (that is, the frequency distribution of the co-occurrence degree) has a more appropriate value.

An example will be described below. In Table 1, the top 10 most frequent words (a to j) in a document, their frequency of occurrence (frequency), and the probability of their occurrence (the frequency at which that frequent word is divided by the frequency of occurrence of all frequent words) And the distribution of.

[0031]

[Table 1]

This step S2-2 is executed by the frequent word extraction module 32.

(Step S2-3): Corresponding to step (2) of claim 1 In this step, a characteristic item is extracted from the words based on the bias of the co-occurrence probability distribution of each word and the frequent word. To do. This operation will be described in more detail with reference to FIG. Note that this step S2-3 is executed by the keyword determination module 33.

(Step S3-1) First, information indicating the frequency distribution of each frequent word is acquired. This information is, for example,
It is the frequency distribution of each frequent word and the (theoretical) occurrence probability of each frequent word. This information can be acquired in step S2-2. As described above, each step does not have to exist independently, and the function of the step may be substantially executed.

(Step S3-2) Next, the frequency distribution of the co-occurrence degree (that is, the number of times of co-occurrence) between each word and the frequent word is acquired. This step will be specifically described. In the same sentence,
By counting the frequency of each word that co-occurs with each frequent word,
A co-occurrence matrix as shown in Table 2 can be created. This is an example of the frequency distribution of co-occurrence.

[Table 2]

This table shows the top 10 most frequently used words (a to j in the table).
(G is the set of frequent words). The 10x10 matrix at the top is a symmetric matrix. The diagonal elements in this symmetric matrix represent the number of times each frequent word appears in the document. Further, this matrix handles words (to x) other than the frequently-used word in the downward direction. That is, this table shows the co-occurrence frequency of a certain word w which is not always a frequent word and a frequent word g ∈ G. An example of co-occurrence degree calculation will be described below. For example, assume the sentence "It was hot today. The Kanto region was hot yesterday." Here (it's hot today)
Co-occurs once in the first sentence. In the second sentence, (Yesterday, Kanto), (Yesterday, region), (Yesterday,
This means that (hot), (Kanto, local), (Kanto, hot), (local, hot) co-occur once.

In the co-occurrence matrix, each element of the row corresponding to word w is divided by the sum of the elements of that row (corresponding to the value of the total column in Table 2) to give word w and the frequent word g. A co-occurrence probability distribution with is obtained. Here, if the word w occurs independently of the frequent word g ∈ G, the probability distribution of the co-occurrence of the word w and the word g ∈ G is the probability distribution of Table 1 (that is, the probability distribution of the frequent word). It should be similar. On the other hand, if there is any semantic connection between the word w and the frequent word g ∈ G, the probability distribution will be biased. Here, the probability distribution only needs to represent the probability substantially, and the following calculation can be performed using the co-occurrence frequency as it is as a numerical value.

FIGS. 4 and 5 show the distribution of co-occurrence probabilities of a word and a frequent word, and the appearance probability of the frequent word alone (front in the figure).
An example of comparison of the distributions of is shown. Although all the words appear in the document only about 10 times, common words such as discussion and case are used at the same rate as any frequent word g ∈ G, while transformation L and Words such as hypotheses have a highly skewed distribution. These words preferentially co-occur with certain words, but rarely with other words. These biased words are considered to have some meaning in the document. In fact, the original document is "Conversion L, which is one of the conversion methods from Horn clauses to constraint expressions in hypothesis reasoning".
Since it is a paper that describes about transformation L and hypoth
Words such as eses are important words that occur less frequently in the paper.

(Step S3-3) Then, the χ ² value is calculated for all the words w. As mentioned above, if the distribution of the co-occurrence probabilities of a word deviates significantly from the reference appearance probability, it is considered that the word is a characteristic word and is likely to be an important word in the sentence. be able to. However, if the frequency of appearance of words is small, the deviation of the probability distribution becomes unreliable. For example, from Table 1, the appearance probability of the word a is 0.177. At this time, rather than that the word w ₁ with one appearance frequency co-occurs with the word a once (that is, with probability 1),
If the word w ₂ with 10 occurrences co-occurs with the word a 10 times (that is, with a probability of 1), the deviation from the standard should be large. Therefore, in order to evaluate the statistically significant deviation, χ ²
Use a test.

In this step, the occurrence probability of a frequent word alone (Table 1) is defined as the occurrence probability p _g (g ∈ G), and the total number of co-occurrence frequencies of the word w and the frequent word g is n _w (in Table 2). The co-occurrence frequency (corresponding to the value in the “total” column of the row corresponding to the word w), cooc (w, g) (the word w in Table 2 (a to x in the table))
The value of the row corresponding to or the frequent word g (a to j in the table)
(Corresponding to the value of the column corresponding to), the statistic amount χ ² is obtained for each word w by the following equation (1).

That is, the co-occurrence frequency co for each frequent word g
oc (w, g) corresponds to the frequency distribution of co-occurrence degrees in Table 1. Therefore, the co-occurrence frequency cooc (w, g) corresponds to “information indicating frequency distribution” in the present embodiment. Further, in the equation (1), n _w p _g represents the theoretical co-occurrence frequency for the frequent word g.

If χ ² (w)> χ _α ² , then "the frequent word g of word w
The number of co-occurrences with ∈ G (observation frequency) is (theory) probability of occurrence p _g ( _g ∈
The hypothesis H ₀ that "matches G)" is rejected at the significance level α. (Χ _α ² is usually obtained from the χ ² distribution table). Therefore, a word w with a large χ ² (w) can be judged as a word with a large deviation from the appearance probability. Such words are used as keywords (step S3-4).

As an example, Tables 3 and 4 show the top 10 words with high χ ² values and the top 10 words with low χ ² values, respectively. In addition,
These are based on 25 frequent words (Table 5) and measure the deviation of their distribution. As can be seen from the table, a word with a high χ ² value is a characteristic word (that is, it is likely to be directly related to the argument), and a word with a low χ ² value tends to be a general word.

[Table 3]

[Table 4]

[Table 5]

It can be said that the method of the present embodiment first obtains the overall tendency of the data itself, and then takes out items having characteristics that are significantly different from them.

[0045]

EXAMPLES Example 1 Using the method of the above embodiment,
Keywords were extracted from the following papers. For comparison, an example in which keywords are extracted from only frequently-used words is also shown. Paper: "SL Method: Suboptimal Solution Calculation of Cost-Based Hypothetical Reasoning by Combined Linear Programming and Nonlinear Programming" (Yutaka Matsuo,
Takeyuki Futa, Mitsuru Ishizuka: Journal of Japan Society for Artificial Intelligence Vol.13, No.6, p
p.953-961,1998)

[Table 6]

[Table 7]

To summarize the above paper, "We propose a method called the SL method for obtaining a suboptimal solution of cost-based hypothetical reasoning. The SL method first replaces the hypothetical reasoning problem with a linear programming problem and then performs an initial search with a simplex method. After deciding the point, the search is performed by minimizing the non-linear function around it. If the point falls into the local optimal solution, it is fixed. ”
Therefore, in the present embodiment, words such as “suboptimal solution” and “minimization of non-linear function” that are the main points in the paper can be successfully extracted by analyzing only the sentences in the paper.

(Example 2) The method of this embodiment was applied to Koizumi's public opinion speech obtained from the following URL. The results are as follows. http: //www.kantei.go.j
p / jp / koizumispeech / 2001 / 0507syosin.html

[Table 8]

[Table 9]

The content of the speech is wide-ranging, including structural reform, economics, and diplomacy, and the main theme of this speech, "Neon Genesis Restoration," is mentioned only twice. However, with the method of this embodiment, this word could be extracted as a keyword.

(Example 3) Asahi Shimbun July 1, 2001 The method of this embodiment was applied to the editorial "PL Baseball Club: Break the Hotbed of Violence". The results are as follows.

[Table 10]

[Table 11]

The above editorial is about the problem of violence in the baseball club and ironing in Japanese high school and college sports. The idea is that leaders should make efforts to improve the situation. Therefore, according to this embodiment,
It can be seen that appropriate keywords can be extracted.

It should be noted that the above description of the embodiment is merely an example, and does not show an essential structure of the present invention. As long as the configuration of each part can achieve the gist of the present invention,
Not limited to the above. For example, the characteristic item extraction system may be realized by cooperation of a plurality of computers. Further, the above-mentioned modules may be divided or integrated programs. As a method for determining the bias of the co-occurrence probability distribution between each item and the frequent item, other than the χ ² test, the method using Kalbach-Leibler information, the likelihood ratio test, Fisher's exact test, Kolmogorov・ There is a Smirnov test.

Further, in the above-mentioned embodiment, the co-occurrence degree is measured based on the fact that it is in the same sentence, but the range of the number of words before and after the frequent word (for example, the range of 5 words before and after) is used.
May be defined and the co-occurrence degree in that range may be measured. Further, the co-occurrence degree may be measured within the same sentence and within a prescribed number of words before and after the frequent word. Furthermore, the theoretical probability of occurrence of frequent words p _g (g ∈ G) is
(N is the total number of words in the sentence in which g appears) / (total number of words in the entire document), and n _w in the expression (1) can be the total number of words in the sentence in which the word w appears. In this way, χ ²
For the value, an accurate calculation result is obtained in consideration of the sentence length (that is, two words that co-occur in a short sentence are more closely related).

[0053]

As described above, according to the present invention, it is possible to provide a characteristic item extraction method capable of extracting a characteristic item with relatively high accuracy even with a small amount of data.

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic configuration of a keyword extraction system according to an embodiment of the present invention.

FIG. 2 is a flowchart showing a schematic procedure of a keyword extraction method according to an embodiment of the present invention.

FIG. 3 is a flowchart showing a procedure for keyword determination in the keyword extraction method according to the embodiment of the present invention.

FIG. 4 is a graph showing an example of bias of probability distribution in the present embodiment.

FIG. 5 is a graph showing another example of bias of probability distribution in the present embodiment.

[Explanation of symbols]

1 CPU 2 Interface section 3 storage 31 Document data 32 Frequent word (frequent item) extraction module 33 Keywords (feature item) decision module 4 Communication unit

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Mitsuru Ishizuka             3-28 Moegino, Aoba-ku, Yokohama-shi, Kanagawa F-term (reference) 5B056 BB64 HH00                 5B075 ND03 NR12 PR04 UU06

Claims (14)

[Claims] 1. A characteristic item extraction method comprising the following steps; (1) a step of extracting frequent items from items in data, (2) a co-occurrence probability distribution of each item and the frequent items. A feature item from the item based on the bias of the item. 2. The characteristic item extracting method according to claim 1, wherein the data is a sentence or a part thereof, and the item is a single word or a plurality of words. 3. The characteristic item extraction method according to claim 2, wherein the co-occurrence probability is calculated based on co-occurrence in the same sentence. 4. The characteristic item extraction method according to claim 2, wherein the co-occurrence probability is calculated based on co-occurrence within a prescribed number of words before and after the frequent item. 5. The frequent items are clustered by grouping together items having a relatively high probability of appearing in the same sentence, and the bias of the co-occurrence probability distribution is calculated by using each of the items and the clustering. 5. The characteristic item extraction method according to claim 2, wherein the characteristic item extraction method is performed between the extracted frequent items. 6. The "step of extracting a characteristic item from the item based on the bias of the co-occurrence probability distribution of each item and the frequent item" includes the following steps. 5. The characteristic item extraction method according to any one of 5; (a) a step of acquiring information indicating a frequency distribution of each frequent item in the data, (b) a frequency of co-occurrence degree between the frequent item and each item Acquiring information indicating distribution, (c) acquiring bias of the co-occurrence probability distribution based on information indicating frequency distribution of each frequent item and information indicating frequency distribution of the co-occurrence degree. 7. The feature item extraction method according to claim 6, wherein the “information indicating the frequency distribution of each frequent item” is information indicating the appearance probability of each frequent item. 8. The feature item extraction method according to claim 1, wherein the bias of the co-occurrence probability distribution is calculated as the magnitude of the χ ² value in the following equation. However, in this expression, w: item, g: frequent item, G: set of all frequent items p _g : appearance probability of frequent item (g), n _w : set of item (w) and all frequent item (G) The total number of co-occurrence frequencies with frequent items inside, cooc (w, g): co-occurrence frequency of item (w) and frequent items (g). 9. The method of claim 8, wherein p _g = (frequent items
(G) appearance frequency) / (Frequent items belonging to set (G))
(g) total appearance frequency), and n _w is an item
A characteristic item extraction method, which is the total number of co-occurrence frequencies of (w) and frequent items (g) in the set (G). 10. The method according to claim 8, wherein p _g = (total number of words of sentence in which frequent item (g) appears) / (total number of words of entire document), and n _w is that item (w) is A characteristic item extraction method characterized by being the total number of words of an appearing sentence. 11. A CPU and a storage unit usable by the CPU, the storage unit including a frequent item extraction module and a characteristic item determination module,
The frequent item extraction module is software that causes the CPU to perform an operation of extracting a frequent item from an item in data, and the characteristic item determination module is for biasing the co-occurrence probability distribution of each item and the frequent item. A characteristic item extraction system, which is software that causes the CPU to perform an operation of extracting a characteristic item from the item based on the above. 12. The computer according to any one of claims 1 to 10.
A computer-executable or readable program, characterized by causing the function of the step in the characteristic item extraction method described above to be executed. 13. The frequent item extraction module in the characteristic item extraction system according to claim 11. 14. The characteristic item determination module in the characteristic item extraction system according to claim 11.