JP5379749B2 - Document classification apparatus, document classification method, program thereof, and recording medium - Google Patents

Description

  The present invention relates to a document classification apparatus, a document classification method, a program thereof, and a recording medium, which are excellent in statistical reliability of classification criteria used for classification of documents and the like.

  When classifying a plurality of documents or the like, classification is performed based on the similarity of feature amounts using the difference in feature amounts of the documents. As a feature amount used for classification, a document vector whose element is a relative appearance frequency of each word included in a document is generally used, and each document is classified into a plurality of clusters based on the distance between the document vectors of each document. The distance between each document vector is defined based on the similarity of the relative appearance frequency of words included in each document. Specifically, for example, it is defined as the distance between the maximum likelihood values of the true posterior probability density distribution of the true value of the relative appearance frequency of the words included in each document. Then, clustering is performed so that document vectors having a close distance defined in this way belong to the same cluster.

JP 2008-234482 A

  When the distance between each document vector is defined only by the similarity of the relative appearance frequency of words included in each document, even if the relative appearance frequency is the same, the number of samples of each relative appearance frequency is different, that is, the appearance When the absolute value of the frequency is different, the probability density distribution is also different, and the statistical reliability is different. This difference is particularly problematic when the number of samples is small. Specifically, the statistical reliability is impaired due to the relatively large influence of words with low appearance frequency. This causes a problem that, for example, documents that should not be classified into the same cluster are classified into a single cluster. In order to avoid such a problem, a countermeasure (for example, Patent Document 1) of artificially removing words with low appearance frequency is conceivable, but new problems such as efficiency and cost arise.

  An object of the present invention is to provide a document classification apparatus, a document classification method, a program therefor, and a recording medium that can accurately classify a plurality of documents even when the documents are short, even if the documents are short. There is to do.

  The document classification device of the present invention is a device that clusters a plurality of documents, and includes a document vector generation unit, a distance calculation unit, and a clustering unit. The document vector generation unit generates a document vector having the relative appearance frequency of each word included in the document as an element for each document. The distance calculation unit calculates the distance between each document vector by using a distance scale in which the reliability of probability estimation is added to the distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency of words. The clustering unit classifies each document into a plurality of clusters based on the distance between each document vector.

  According to the document classification device, document classification method, program and recording medium of the present invention, according to the document classification device, document classification method, program and recording medium of the present invention, the distance between each document vector The distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency is calculated using a distance scale in which the reliability of probability estimation is added. Thereby, since the distance between the posterior probability density distributions is also taken into consideration, the statistical reliability of the classification criterion that has been lowered due to the influence of the words having a low appearance frequency can be improved. Therefore, when a plurality of documents are clustered, even if the documents are short, the documents can be accurately classified without human intervention.

2 is a block diagram illustrating a configuration example of a document classification device 100. FIG. FIG. 5 is a diagram showing an example of a processing flow of the document classification apparatus 100. The figure which modeled the distance of the posterior probability density distribution of two documents. The figure which shows the example of the processing flow in the clustering part.

  FIG. 1 is a block diagram illustrating a configuration example of a document classification apparatus 100 according to the present invention. FIG. 2 shows an example of the processing flow (S1 to S4). The document classification device 100 is a device that clusters a plurality of documents, and includes a document vector generation unit 110, a distance calculation unit 120, a clustering unit 130, and a result display unit 140.

  The document vector generation unit 110 generates a document vector having the relative appearance frequency of each word included in the document as an element for each document to be classified (S1). At this time, the words included in the document vector do not necessarily have to be all the words included in the document, but may be limited to characteristic main words by analyzing the words in the document in advance.

  The distance calculation unit 120 calculates the distance between each document vector by using a distance scale in which the reliability of probability estimation is added to the distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency of words (S2). . Thereby, since the distance between the posterior probability density distributions is also taken into consideration, the statistical reliability of the classification criterion that has been lowered due to the influence of the words having a low appearance frequency can be improved. Specifically, for example, the calculation is performed as follows.

  The true value p of the conditional probability P (w | h) when n words appear in the document h from the document vector of a document h and it is observed that the word w appears k times. The posterior probability of

It can be expressed as. Equation (1) is binomial posterior distribution by dividing

Can be expressed as

  When a sample is extracted independently from the appearance probability distribution of the word w in the two documents i and j, the statistical expectation value of the square of the difference can be expressed as a distance measure such as the following equation.

This distance measure d _{i, j} ^(w) reflects the reliability of probability estimation in addition to the distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency of the word w in the two documents i and j. . FIG. 3 schematically shows the distance between the probability density functions of x and y corresponding to the two documents i and j obtained by Expression (3). The probability density function of points randomly selected from the two binomial posterior probability density distributions in FIG. 3 follows each distribution, and the distance measure d _{i, j} ^(w) is the statistical expectation of the distance between the two selected points. Value.

Then, the distance measure d _{i, j} indicating the similarity between the two documents i and j from the co-occurrence relationship of a plurality of words is converted into a binomial posterior distribution defined for each word based on the equations (2) and (3). Based on the following formula, it can be defined (see Reference 1).

  [Reference 1] Shinji Tamoto, Go Kawabata, “Clustering of Words Focusing on Concatenated Co-occurrence”, IEICE Technical Report, 1993, SP, Speech 93-125, p.55-62

The clustering unit 130 classifies each document into a plurality of clusters based on the distance between each document vector obtained by the distance calculation unit 120 (S3). Various methods can be applied as a clustering method. For example, when using the hierarchical clustering method based on the aggregation type, clustering can be performed by the procedure (S11 to S13) as shown in FIG. Note that {D _p | 1 ≦ p ≦ n} is a set of documents, {C _p | 1 ≦ p ≦ h} is a set of classifications, and a set of documents associated with each C _p is {K _pu | 1 ≦ u ≦ n _p }. In the initial state, C _p = {D _p }.

First, a distance d _c (C _p , C _q ) between C _p and C _q clusters is calculated, and two clusters having the closest distance are set as processing targets (S11). The distance between the clusters _{d c (C p, C q} ) is representative document _D p in the cluster, the distance of the document vector of _{D q d v (D p,} D q) and the representative document _{D p} is the _{C p} Of the documents, a document K _pt that minimizes Σ (1 ≦ s, t ≦ n _p , s ≠ t) d _v (K _ps , K _pt ) is set. Next, the C _p and C _q clusters are combined to generate a new cluster C _r (S12). If the number of clusters h has not reached the predetermined number, the process proceeds to S11, and if it has reached, the clustering process is terminated (S13).

  Then, the result display unit 140 displays the clustering result (S4). The display method is arbitrary. For example, each cluster classified by the clustering unit 130 and a list of labels of documents belonging to each cluster are displayed.

  As described above, according to the document classification device, the document classification method, the program, and the recording medium of the present invention, the distance between each document vector is the distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency of words. And a distance scale that takes into account the reliability of probability estimation. Thereby, since the distance between the posterior probability density distributions is also taken into consideration, the statistical reliability of the classification criterion that has been lowered due to the influence of the words having a low appearance frequency can be improved. Therefore, when a plurality of documents are clustered, even if the documents are short, the documents can be accurately classified without human intervention.

  Each of the above processes is not only executed in time series according to the description, but may also be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary. In addition, it can change suitably in the range which does not deviate from the meaning of this invention.

  Further, when the document classification device of the present invention is realized by a computer, the processing contents of the functions possessed by each part of the device are described by a program. The program is stored in, for example, a hard disk device, and necessary programs and data are read into a RAM (Random Access Memory) at the time of execution. The read program is executed by the CPU, whereby each processing content is realized on the computer. Note that at least a part of the processing content may be realized by hardware.

  The program describing the above processing functions can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, the magnetic recording device may be a hard disk device or a flexible Discs, magnetic tapes, etc. as optical disks, DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable) / RW (ReWritable), etc. As the magneto-optical recording medium, MO (Magneto-Optical disc) or the like can be used, and as the semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) or the like can be used.

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

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

Claims (6)

A document classification device for clustering a plurality of documents,
A document vector generation unit that generates, for each document, a document vector whose element is the relative frequency of occurrence of each word included in the document;
A distance calculation unit that calculates the distance between each document vector by using a distance scale in which the reliability of probability estimation is added to the distance between the maximum likelihood values of the posterior probability density distribution of the relative appearance frequency of words;
A clustering unit that classifies each document into a plurality of clusters based on the distance between each document vector;
A document classification device comprising: The document classification device according to claim 1,
The distance calculation unit
The posterior probability of the true value p of the conditional probability P (w | h) when n words appear in the document h from the document vector, and it is observed that the word w appears k times.

Binomial posterior distribution obtained by reducing

Is the statistical expectation value of the square of the difference between the probability distributions of the word w in the two documents i and j

And the distance d _{i, j} between the two documents _{i and j} is

A document classification apparatus characterized by obtaining using a distance scale defined in (1). A document classification method for clustering a plurality of documents,
A document vector generation step for generating, for each document, a document vector whose element is a relative frequency of occurrence of each word included in the document;
A distance calculation step of calculating a distance between each document vector using a distance scale in which reliability of probability estimation is added to a distance between maximum likelihood values of a posteriori probability density distribution of a relative appearance frequency of words;
A clustering step of classifying each document into a plurality of clusters based on the distance between each document vector;
Document classification method to execute. The document classification method according to claim 3,
The distance calculating step includes:
The posterior probability of the true value p of the conditional probability P (w | h) when n words appear in the document h from the document vector, and it is observed that the word w appears k times.

Binomial posterior distribution obtained by reducing

Is the statistical expectation value of the square of the difference between the probability distributions of the word w in the two documents i and j

And the distance d _{i, j} between the two documents _{i and j} is

A document classification method characterized by being obtained using a distance scale defined in 1.   A program for causing a computer to function as the document classification device according to claim 1.   A computer-readable recording medium in which a program for causing a computer to function as the document classification device according to claim 1 is recorded.

Images