JPH08221447A - Document automatic classifier - Google Patents

Abstract

(57) [Summary] [Purpose] As many words as possible to be classified (effective words) are retained to increase the probability that a word included in a document to be classified matches any of the saved effective words. To reduce the processing cost on the vector space by reducing the number of basic words as the axis of the vector space expressing the document as much as possible. [Structure] The effective word extraction unit 25 is a document database 24.
In addition, a plurality of valid documents are extracted from all the documents stored in advance by dividing the plurality of documents into the categories and registered in the valid word dictionary 26. The base word extraction unit 27
From the effective words registered in the effective word dictionary 26, as few base words as axes of the vector space expressing the document are extracted. Each effective word registered in the effective word dictionary 26 is provided with correlation information with the base word. Vector representation part 2
2 represents a document input as a classification target as a vector having a small dimension based on the correlation information between the effective word and the base word, and the identification determination unit 23 calculates the distance between documents in the vector space. Go to determine which category the document belongs to.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic document classification device for classifying input documents into given categories.

[0002]

2. Description of the Related Art As one of automatic document classification methods, a document is represented by a vector having a given finite number of words as an axis, and a distance between documents is calculated in the vector space to obtain a document. There is known a method of discriminating which one of given cadegos belongs. In this method, the base word, which is the axis of the vector expression, is extracted from the document group that is already divided and stored for each category.

[0003]

In this case, considering the cost of various mathematical processes on the vector space, it is better that the dimension of the vector space, that is, the number of base words is smaller, which is effective for classification. It is desirable to choose as few words as possible as base words. However, if the number of base words is small, the probability that one of the base words is included in the newly input document is low, and many words in the document become unknown words to the classifier. Therefore, there is a problem that the classification accuracy decreases. On the contrary, if the number of base words is increased in order to reduce unknown words, there is a problem that the processing cost in the vector space becomes high.

The present invention has been made under such a background, and an object thereof is to retain as many words (effective words) effective for classification as possible and to save words included in a document to be classified. In addition to increasing the probability of matching with any of the valid words, the number of base words serving as the axis of the vector space expressing the document can be minimized to reduce the processing cost on the vector space.

[0005]

In order to achieve the above object, the invention according to claim 1 classifies a document into any category by expressing the document by a vector having a finite number of words (base words) as axes. In the automatic document classification apparatus for determining whether or not a plurality of documents are divided into the categories in advance and stored, and a word effective for automatically classifying an input document is stored in the document database as an effective word. Effective word extracting means for extracting from the document, an effective word dictionary in which the effective words extracted by the effective word extracting means are registered, and an effective word in which a base word as an axis of vector expression of the document is registered in the effective word dictionary And a base word extracting means for extracting from the

In order to achieve the above object, in the invention according to claim 2, the effective word extracting means according to claim 1 has variations in appearance frequency depending on categories in a plurality of documents stored in the document database. It is configured to extract the word as a valid word.

In order to achieve the above object, in the invention according to claim 3, the base word extracting means according to claim 1 has the effectiveness for classification from the effective words registered in the effective word dictionary. A word that is high and has a low correlation with other base words is extracted as a base word.

To achieve the above object, in the invention according to claim 4, the effective word registered in the effective word dictionary according to claim 1 is provided with correlation information with the base word.

In order to achieve the above object, in the invention according to claim 5, among the effective words registered in the effective word dictionary according to claim 4, synonyms are provided with the same correlation information. ing.

[0010]

According to the invention described in claims 1 to 5, by registering a sufficient number of valid words in the valid word dictionary, the words included in the document to be classified match any of the valid words to be registered. The probability increases, and it is possible to prevent the information held by the document from leaking as much as possible. Further, by extracting as few basic words as possible from the effective words registered in the effective word dictionary by the basic word extracting means, the contents of the document to be classified are expressed as points on a vector space of low dimension. It is possible to reduce the processing cost on the vector space.

According to a second aspect of the present invention, the effective word extracting means according to the first aspect extracts words having a variation in appearance frequency depending on a category in a plurality of documents stored in the document database as effective words. As a result, the words that characterize the category are extracted as effective words.

According to a third aspect of the present invention, the base word extraction means according to the first aspect has a high degree of effectiveness for classification from the valid words registered in the valid word dictionary, and other base words. The content of the document can be expressed as a point on a vector space with a low dimension by extracting as few basic words as possible that have a low correlation with.

According to a fourth aspect of the present invention, the effective word registered in the effective word dictionary is provided with correlation information with the base word, and by the correlation information between the effective word and the base word, The information of the effective word can be reflected on the vector space having the base word as an axis.

In the invention of claim 5, among the effective words registered in the effective word dictionary of claim 4, synonyms are given the same correlation information, and synonyms are different from each other. , Are represented as the same vector.

[0015]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a block diagram showing the hardware arrangement of an automatic document classification apparatus according to an embodiment of the present invention. In FIG. 1, 11 is a central processing unit, 12 is a ROM, and 13 is an R.
AMs and 14 are disk devices, which are connected by a bus 15 so that data and control signals can be mutually transferred.

The ROM 12 is preset with a control program for performing a series of automatic document classification processing in accordance with the control procedures shown in the flow charts of FIGS. 3, 5, and 8. The central processing unit 11 performs this control. Automatic document classification processing is performed while using the RAM 13 as a work area or the like according to a program.

FIG. 2 is a functional block diagram showing the functions of the automatic document classification apparatus according to the embodiment of the present invention. In FIG. 2, 21 is a document classification unit, 22 is a vector expression unit, and 23.
Is an identification determination unit, 24 is a document database, 25 is an effective word extraction unit, 26 is an effective word dictionary, 27 is a base word extraction unit, 28
Is a synonym dictionary.

The document database 24, the effective word dictionary 26, and the synonym dictionary 28 are constructed on the disk device 14 of FIG. Further, the document database 24 holds documents classified into categories C ₁ , C ₂ , ..., _CM (M is the number of categories) given in advance by the user. Also,
Document classification unit 21 (vector expression unit 22, identification determination unit 2
3), the effective word extraction unit 25 and the base word extraction unit 27 are configured by the central processing unit 11, the ROM 12, and the RAM 13. Vector representation unit 2 of document classification unit 21
2 is a vector representation of the contents of a document related to an input with a minimum number of base words as an axis, and the identification determination unit 23 calculates the distance between documents in the vector space, and the document is classified into the category C ₁ , C ₂ , ..., C _M are identified and determined.

Next, the effective word extraction processing by the effective word extraction unit 25 will be described with reference to the flowchart shown in FIG.

First, the effective word extracting section 25 morphologically analyzes all the documents stored in the document database 24 to extract words (step S301), and stores the extracted words in the list L (step S302). And the word list L
An arbitrary word W is extracted from (step S303). Then, the effectiveness E (W) for document classification of the word W is calculated (step S304). Here, the effectiveness is evaluated by the following method. That is, of the documents belonging to the category C _K , the ratio pk of the number of documents containing the word W
Calculate (W). This is normalized so that the total sum of all the categories is 1 as in Expression 1.

[0022]

[Equation 1] An example of pk (W) is shown in FIGS. 4 (a) and 4 (b). As shown in FIG. 4A, when there is a difference in the number of documents including the word W depending on the category, the word W is
It is considered to characterize a category with a high proportion, and can be said to be an effective word for classification. On the other hand, when the proportion of documents including the word W does not differ depending on the category as shown in FIG. 4B, it is considered that the classification is not effective for classification. In order to evaluate such distribution bias, entropy H (W) is calculated as follows, for example.

[0023]

[Equation 2] Here, H (W) takes a value of 0 to 1, and the larger the deviation of the distribution (effective for classification), the smaller the value, and the smaller the deviation (effective for the distribution), the larger the value of H (W). Effectiveness E
(W) is defined as E (W) = 1-H (W).

After the effectiveness E (W) is calculated in this manner, it is determined whether or not the effectiveness E (W) is larger than the threshold value h (step S305). When the effectiveness E (W) is larger than the threshold value h, the word W is regarded as a valid word,
The effective word dictionary 26 is registered (step S306). On the other hand, when the validity E (W) is less than or equal to the threshold value h, step S306 is skipped and the process proceeds to step S307, so that the word W is not regarded as a valid word and is not registered in the valid word dictionary 26. To do so. In this embodiment, the threshold h is appropriately set to extract as many valid words as possible within the range in which document classification can be effectively performed, and the valid word dictionary 2 is extracted.
I am going to register in 6.

When the above processing is completed, the word W is deleted from the word list L (step S307). Then, it is determined whether or not the word list L is empty (step S30
8) If it is not empty, the process returns to step S303, the same process is performed for the next word, and if the word list L is empty, the valid word extraction process is terminated.

Next, the basic word extraction process will be described. It is desirable that the base words are combinations that have high effectiveness for classification and have low correlation with each other. For example, it is assumed that "exchange rate", "maximum value", "economy", "goods tech", "inflation" ... Are registered in the effective word dictionary 26 as effective words. Each of these can be said to be a word that well characterizes the category of "economy". However, since "exchange rate" and "highest price" often appear in the same document, it is redundant to adopt both of them as base terms. Rather, it is better to select "exchange", "goods tech", "inflation", etc. as base terms and add correlation information of "maximum value" and "exchange" in the effective word dictionary 26.

The base word extraction processing based on such an idea will be described with reference to the flowchart shown in FIG.

The base word extraction unit 27 firstly detects the effective word dictionary 2
The co-occurrence probabilities of the words (valid words) registered in No. 6 are calculated from the documents stored in the document database 24 (step S501). Co-occurrence probability r of word W to word W '
(W, W ') is

[0029]

## EQU3 ## r (W, W ') = (number of documents containing W and W'at the same time) / (number of documents containing W)

Next, as an initial setting, the base word list B holding the selected base words and the base word candidate list C holding the base word candidates are emptied, respectively, and the number n of the selected base words is set to "0". (Step S502). Then, of the words registered in the effective word dictionary 26, all the words except the words held in the base word list B are held in the base word candidate list C as base word candidates, and the base word evaluation value is held. The maximum value max of is initialized to "0" (step S503).

Then, an arbitrary word W is extracted from the basic word candidate list C (step S504), and the evaluation value E ^* (W) as the basic word of this word W is calculated (step S).
405). The evaluation value E ^* (W) is obtained as follows.

That is, the list B of the selected base words
However, when it is still empty, the evaluation value E ^* (W) = effectiveness E
(W). Already the base words W ^b ₁ , W ^b ₂ , W ^b ₃ , ...
When W ^b _n is selected, the evaluation value E ^* (W) as the base word of the word W becomes higher as the effectiveness E (W) for document classification of the word W itself becomes higher, and the evaluation value E ^* (W) becomes higher. Words W ^b ₁ , W ^b ₂
, W ^b ₃ , ..., W ^b _n , the higher the correlation, the lower the evaluation value E ^* (W) of the word W is determined as follows.

[0033]

[Equation 4] E ^* (W) = E (W) × (1-r (W, W
^b ₁ )) × (1-r (W, W ^b ₂ )) ... (1-r (W,
W ^b _n )) Next, the evaluation value E ^* (W) calculated in step S405.
Is greater than the maximum value max (step S
506) If larger, set the word W to the next base word candidate W ^* , and set the maximum value max to the evaluation value E of the word W.
^* Update to (W) (step S507), then step S
Proceed to 508. On the other hand, the evaluation value E ^* (W) is the maximum value max.
If it is below, the process of step S507 is skipped and the process proceeds to step S508.

In step S508, the word W is deleted from the base word candidate list C. Then, the base word candidate list C
Is checked to be empty (step S509). If it is not empty, the process returns to step S504 and the same evaluation is performed for the remaining valid words (base word candidates). If the basic word candidate list C is empty, the basic word candidate W ^* is added to the basic word list B and the basic word number n is incremented by 1 (step S
510).

Then, it is checked whether or not the number of base words n has reached a number L (a small number of 7 in this embodiment) preset by the user (step S511). If not, step S5.
Returning to 03, the next base word candidate is selected. Number of base words n
When reaches the set number L, the extraction of L base words is completed.

Correlation information between the base word thus extracted and each word registered in the effective word dictionary 26 is added to the effective word dictionary 26. This is each word W in the effective word dictionary 26.
In contrast, the co-occurrence probability r (W, W ^b _i ) of the word W with respect to the base word W ^b _i (i = 1, 2, ... L) is described. In addition, the synonym dictionary 28 is used to give the same correlation information to synonymous effective words. For example, the word W
And W ′ are synonyms, and the effectiveness E (W) of the word W is greater than the effectiveness E (W ′) of the word W ′, the word W,
In all W ′, the base word W ^b _{i of the} word W (i = 1, 2,
The co-occurrence probability r (W, W ^b _i ) for L) is described as correlation information.

FIG. 6 shows an example of contents of the effective word dictionary 26 created from a document group classified into two categories of "politics" and "economy" by such a method. Further, FIG. 7 also shows an example of contents of the synonym dictionary 28.

FIG. 6 shows an example of an effective word dictionary when "foreign exchange", "prime minister", "summit", ... (7 words in total) are selected as base words. For example, the correlation information (co-occurrence probability) with the base word of the effective word “forex” registered in the effective word dictionary 26 is (1.0, 0.1, 0.0, 0.3, 0.0,
0.4, 0.0), the first base word is "forex", and the co-occurrence probability is "1.0". Also, the correlation information with the base word of the effective word "Kakukaku" is (0.0, 0.9, 0.
0,0.0,0.1,0.1,0.0,0.4), which has a low correlation with the first base word "forex"("0.
0)) and the second base word “Prime” has a high correlation (“0.9”). Further, as shown in FIG. 7, since the words “forex” and “foreign exchange” are registered as synonyms in the synonym dictionary 28, they are registered in the effective word dictionary 26 as shown in FIG. The correlation information (co-occurrence probability) with the base word of the word "foreign exchange" is exactly the same as "forex" (1.0, 0.1, 0.0, 0.3, 0.
0, 0.4, 0.0).

Next, the vector expression processing by the vector expression unit 22 will be described with reference to the flowchart shown in FIG.

The vector expression unit 22 first initializes the L-dimensional vector x to 0 (step S801). Then, the target document is subjected to morphological analysis (step S80).
2) Create a word list D consisting of a set of words W included in the document and their frequencies f (step S).
803), any one (W, f) is extracted from the word list D (step S804).

Then, the word W is subtracted from the effective word dictionary 26 (step S805), and it is checked whether or not the word W is registered in the effective word dictionary 26 (step S806). If not, the process proceeds to step S804. Return. On the other hand, if the word W is registered in the effective word dictionary 26, the vector expression w of the word W is generated based on the dictionary information (step S807). The vector expression w is defined as follows. This expression is basically the same as that used in (Yuasa et al., “Automatic Classification of Documents by Noun Co-occurrence Relationships Automatically Extracted from Large Amount of Document Data”, Natural Language Processing 98-11, 1993).

[0042]

## EQU5 ## w = (r (W, W ^b ₁ ), r (W, W ^b ₂ ),
... r (W, W ^b _n )) r (W, W ^b _i ) is the co-occurrence probability of the word W with respect to the i-th base word W ^b _i , which is the effective word dictionary 2 as described above.
6 are described.

Next, the vector x is updated as x ← x + f · w (step S808). And the pair (W,
f) is deleted from the word list D (step S809),
It is checked whether or not the word list D is empty (step S
810). If it is not empty, the process returns to step S804 and the same process is performed for the next word. If the word list D is empty, the process ends.

In this way, the content of the document can be represented by an L-dimensional (L << N) vector by using the effective word dictionary 26 of N words. That is, as many effective words as possible for classification are registered in the dictionary as much as possible, from which a small number of basic words that are the axes of the vector space expressing the document are extracted and registered in the basic word and effective word dictionary 26. By providing the effective word dictionary 26 with the correlation information with each effective word, it is possible to increase the probability that the word included in the document input as the classification target matches any of the effective words registered in the dictionary, and By expressing the document as a vector with a small dimension based on the correlation information of the base words, the processing cost on the vector space is reduced.

The present invention is not limited to the above embodiment, and for example, a method such as character type cutting is used without using morphological analysis when extracting a word from a document as described above. The speed of the extraction process may be increased. Further, in the above embodiment, the entropy calculation was used to evaluate the effectiveness for classifying words,
Other evaluation functions may be used as long as the distribution bias can be evaluated.

Further, the evaluation function of the base word is not limited to the one shown in the above embodiment, and other evaluation functions can be used as long as they take into consideration the effectiveness of the word itself and the correlation between the base words. You may use a function.

Further, in the above embodiment, the effective word dictionary is provided with the correlation information with all the base words for each word in the dictionary. It is also possible to add only the correlation information and reduce the scale of the effective word dictionary.

[0048]

As described above, according to the automatic document classifying apparatus of the present invention, as many effective words as possible for classification are registered in the dictionary as much as possible, and from these, an axis of a vector space expressing a document is selected. Extract as few base words as possible, and provide the effective word dictionary with the correlation information between these base words and each effective word registered in the effective word dictionary so that the words included in the document input as the classification target are stored in the dictionary. To reduce the processing cost on the vector space by increasing the probability of matching with any of the registered valid words and expressing the document as a vector with less dimensions based on the correlation information between the valid words and the base words. Is possible.

[Brief description of drawings]

FIG. 1 is a block diagram showing a hardware configuration of an automatic document classification device according to an embodiment of the present invention.

FIG. 2 is a functional block diagram showing functions of an automatic document classification device according to an embodiment of the present invention.

FIG. 3 is a flowchart showing a processing procedure of valid word extraction processing.

FIG. 4 is a diagram showing a ratio of documents containing a certain word for each category.

FIG. 5 is a flowchart showing a processing procedure of base word extraction processing.

FIG. 6 is a diagram showing an example of contents of a valid word dictionary.

FIG. 7 is a diagram showing an example of contents of a synonym dictionary.

FIG. 8 is a flowchart showing a processing procedure of vector expression processing.

[Explanation of symbols]

 11 ... Central processing unit 12 ... ROM 13 ... RAM 14 ... Disk device 15 ... Bus 21 ... Document classification unit 22 ... Vector expression unit 23 ... Identification determination unit 24 ... Document database 25 ... Effective word extraction unit 26 ... Effective word dictionary 27 ... Base word extraction unit 28 ... Synonym dictionary

 ─────────────────────────────────────────────────── ─── Continued Front Page (72) Inventor Takaya Ueda 3-30-2 Shimomaruko, Ota-ku, Tokyo Canon Inc. (72) Inventor Yuji Ikeda 3-30-2 Shimomaruko, Ota-ku, Tokyo Canon Incorporated (72) Inventor Minoru Fujita 3-30-2 Shimomaruko, Ota-ku, Tokyo Canon Inc.

Claims (5)

[Claims] 1. A document automatic classification apparatus for expressing a document by a vector having a finite number of words as an axis and determining to which category the document is classified. A database, effective word extraction means for extracting effective words for automatically classifying input documents from the documents stored in the document database, and effective words extracted by the effective word extraction means And an effective word dictionary, and a basic word extracting means for extracting a basic word serving as an axis of a vector expression of a document from the effective words registered in the effective word dictionary. . 2. The document according to claim 1, wherein the effective word extracting means extracts, as an effective word, a word whose appearance frequency varies depending on a category in a plurality of documents stored in the document database. Automatic classifier. 3. The base word extracting means extracts, as a base word, a word having a high degree of effectiveness for classification and a low correlation with other base words from the valid words registered in the valid word dictionary. The automatic document classification device according to claim 1, wherein: 4. The automatic document classification apparatus according to claim 1, wherein the effective word registered in the effective word dictionary is provided with correlation information with the base word. 5. The automatic document classification device according to claim 4, wherein among the effective words registered in the effective word dictionary, synonyms are provided with the same correlation information.