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

Description

The present invention relates to a document classification apparatus that collects topics described by people from the document information published on the network for each theme and enables browsing in cluster units, and in particular, during a period desired by the user. The present invention relates to a document classification apparatus that presents clusters that are grouped by theme with a desired granularity for matching documents.

  In recent years, with the development of computer networks such as the Internet, a large amount of computerized information has been transmitted. For this reason, when it is desired to acquire information on a certain topic, a great effort is required to browse each published Web page from a plurality of information sources.

  Conventionally, in the field of natural language processing and information retrieval technology, a technology is known in which an electronic document is represented by a vector of words appearing in the document, and documents having similar word vectors are made into a cluster. It has been.

In such a conventional technique, a document is expressed as a vector using the word appearance frequency (hereinafter referred to as “document vector”), and the similarity between documents applies the cosine similarity between the document vectors. . In other words, the document vector of the document _{d n}

によって表す。なお、ｖは、単語集合Ｗ＝｛ｗ_１，ｗ_２，…，ｗ_Ｖ｝中の単語の総数を示し、ｘ_ｎｉは文書ｄ_ｎにおける単語ｗ_ｉの重みを示す。このときに、文書ｄ_ｊとｄ_ｋとの類似度を、各文書ベクトルがなす角

Is represented by Incidentally, v is word set _{W = {w 1, w 2} , ..., w V} indicates the total number of words _{in, x ni} denotes the weight of a word _{w i} in the document _{d n.} At this time, the angle formed by each document vector _represents the similarity between the documents d _j and d _k.

で示す。また、単語ｗ_ｉの重みは、単語の文書内での出現頻度、ｔｆ（term frequency）をそのまま利用する場合があり、また、ｔｆに、ｉｄｆ（単語出現数を全文書数で割った値の対数）を乗算したｔｆ・ｉｄｆ（term frequency/inverse document）を利用する場合がある。

It shows with. In addition, word weight of w _i is the frequency of occurrence of in the document of the word, there is a case to be used as it is tf (term frequency), also, to tf, idf (the word number of occurrences of value divided by the total number of documents In some cases, tf · idf (term frequency / inverse document) multiplied by logarithm) is used.

  Then, clustering processing is performed based on the similarity. There are various clustering methods, but a method is known in which similar documents are sequentially gathered as one cluster, and processing is stopped when it is determined that they are not similar using a threshold (for example, Patent Documents). 1). In this method, processing is started in advance with one document as one cluster, and the processing time of clustering is shortened by creating a table in which the most similar clusters are accumulated.

  Therefore, for example, when document information for one month is divided into one week, and when it is desired to see a topic in each period, a document set is divided into one week, and clustering processing is executed using each as an input document. As a result, the generated clusters are independent for each period, and it is difficult to associate clusters in different periods. In other words, there is a problem that a certain cluster cannot present the history of changes in time series.

On the other hand, a method is also conceivable in which a cluster is generated using all document information for one month, and only a document in a specified period is presented from the generated cluster. In this method, it is possible to associate clusters with each other in different periods. However, when calculating the similarity between clusters, the similarity is also calculated for documents outside the period that should not be used. There is a problem of lack of accuracy.
Japanese Patent No. 3675682

  In other words, in the above conventional example, when a period from the start time to the end time and a threshold value regarding the distance between documents are given, a cluster cannot be generated in a short time from the stored documents. There's a problem.

  In the present invention, a tree structure is generated in advance for all stored documents, a cluster for all periods is generated based on a threshold related to the distance between given documents, and a period from the start time to the end time is specified. Only documents having time information included in the period are detected, and a period designation cluster constituted by the detected documents is generated.

Another object of the present invention is to provide a document classification device, a document classification method, a program, and a recording medium that can provide an appropriate cluster in a short period when the threshold value is changed or the period is changed. To do.

The present invention relates to a document storage unit that stores time information, a title, and the text of a document in association with a document ID that uniquely identifies the document, a distance threshold for generating a cluster, a start time, Using the input unit for inputting the end time and the body text of the document stored in the document storage unit, the distance between the document having time information older than the time information of the document and the document is similar to each other. The inter-document distance calculation unit that calculates based on the degree and the document having the shortest distance from the self-document among the documents having time information older than the time information of the self-document is set as a parent node, Compare the shortest distance document storage unit that stores the document ID and the shortest distance in association with the document ID of the document, the shortest distance stored in the shortest distance document storage unit, and the threshold received from the input unit. The shortest distance is not less than the threshold value. If this is the case, the shortest document and the self-document are made the same cluster, and if the shortest distance is larger than the threshold, the shortest document and the self-document are made different clusters, and the integration processing unit generates the cluster. Clusters integrated by the processing unit are stored in association with a cluster ID that uniquely identifies the cluster and a set of documents belonging to each cluster, and the documents that constitute the clusters stored in all the cluster storage units Among these, only documents having time information included in the designated period that is the period from the start time to the end time received from the input unit are detected, and a period designation cluster is generated from the detected documents. A period-designated cluster generation unit that stores the period-designated cluster generated by the period-designated cluster generation unit, The recording period specified cluster generation unit acquires a set of documents corresponding to the unprocessed cluster ID from the all cluster storage unit, and the time information of the parent node that is a document included in the specified period is the start time. If there are no documents before the present, or if the distance between a plurality of existing documents is less than or equal to the threshold, the specified period in the set of documents corresponding to the cluster ID A plurality of existing documents in the case where there are a plurality of documents that are included in the specified period and whose time information of the parent node is earlier than the start time. When the distance between each other is larger than the threshold value, a document included in the specified period in the set of documents corresponding to the cluster ID is set as a plurality of period specified clusters. Document classification device.

According to the present invention, a tree structure is generated in advance for all of the accumulated documents, a cluster for all periods is generated with a threshold regarding the distance between given documents, and a period from the start time to the end time is specified. In this case, only documents with time information included in the period are detected, and a period-designated cluster composed of the detected documents is generated, so when the threshold is changed or the period is changed As a result, it is possible to provide an appropriate cluster in a short period of time.

  The best mode for carrying out the invention is the following examples.

In the first embodiment of the present invention, the distance between documents is obtained based on the similarity between documents, and it is assumed that documents having a shorter distance between documents are more similar. That is, the distance between the documents d _j and d _k is _represented by 1-Cos θ _{j, k} using each document similarity.

  New documents are transmitted one after another on the Internet, and updated time information and the like are added to the document and stored. Example 1 considers such a case.

  FIG. 1 is a flowchart showing the principle of the first embodiment of the present invention.

  In the first embodiment, not all distances between documents to be processed are calculated, but the distance is calculated only for documents to which a time older than the time of the document is given. Next, all documents are arranged in order of time, and a tree structure is formed by connecting between the own document and the closest document. In this case, a tree structure is generated with the oldest document as a root (S1).

  FIG. 2 is a diagram illustrating the principle of the first embodiment.

  In FIG. 2, the ● mark indicates one document, and the documents with newer times are arranged in order from the left to the right. When a document having a time older than that of the own document and having the shortest distance to the own document and the own document are connected by a line, a tree structure is generated as shown in FIG.

  Next, in the above tree structure, integration processing is performed in which documents whose distance between documents is equal to or less than a given threshold are grouped into the same cluster (S2).

  In the example shown in FIG. 2 (2), cluster 1 and cluster 2 are generated based on the distance threshold. Further, only the documents included in the designated period (hereinafter referred to as “designated period”) are presented to all the documents that have undergone the integration process (S3).

  In the example shown in FIG. 2 (3), if the period from time T1 to T2 is designated, only the document of ● is presented, and the document of ○ is not presented because it is out of the period.

  At this time, if a document in a cluster is older than the specified period, there may be a plurality of documents whose parent node is outside the period. The “parent node” is a document having the shortest distance from the self document among documents having time information older than the self document. In the above case, if the distance between a plurality of documents whose parent node is out of the period is equal to or smaller than the threshold, the same cluster is presented, and if the distance is larger than the threshold, it is presented as another cluster (dividing the cluster).

  As shown in FIG. 2 (3), in cluster 1, there are two documents whose parent node is outside the period (documents connected by dotted lines), the distance between these documents is calculated, and the calculated distance Depending on, decide whether to separate the clusters.

  FIG. 3 is a diagram illustrating the document classification device DC1 according to the first embodiment of the present invention.

  The document classification device DC1 is connected to the document storage unit 10, the input unit 20, and the cluster display unit 30.

  The document storage unit 10 stores time information, a title, and a text in a storage device in association with a document ID that uniquely identifies the document.

  The input unit 20 outputs a threshold for generating a cluster, a start time, and an end time.

  The cluster display unit 30 displays the cluster information (document time information, title, text) output from the document classification device DC1. That is, as shown in FIG. 10 (2), the cluster display unit 30 displays the time information and text extracted from the body when displaying the outline of the cluster. In this case, a title may be displayed.

  The document classification device DC1 includes an inter-document distance calculation unit 11, a shortest distance document storage unit 12, an integration processing unit 13, an all-cluster storage unit 14, a period designation cluster generation unit 15, and a period designation cluster accumulation unit 16. Have

  The inter-document distance calculation unit 11 uses the body text of the document stored in the document storage unit 10 and calculates a distance from a document having time information older than the time information of the own document based on the inter-document similarity. To do.

  Among the distances between the document having time information older than the time information of the document itself and the document of interest, the document ID of the document having the shortest distance and the shortest distance are stored in the storage device. The calculation time required for calculating the distance between documents is the square order of the number of documents.

  FIG. 4 is a diagram illustrating an example of data stored in the shortest distance document storage unit 12.

  As shown in FIG. 4A, the shortest distance document storage unit 12 includes a document ID 41 of each document, time information 42, a document ID 43 of a document having the shortest distance calculated by the inter-document distance calculation unit 11, and its The shortest shortest distance 44 is associated and stored in the storage device.

  FIG. 4B is a diagram illustrating a tree structure 40 representing information stored in the shortest distance document storage unit 12.

  The integration processing unit 13 compares the threshold received from the input unit 20 with the shortest distance 44 stored in the shortest distance document storage unit 12. First, one cluster composed of the latest document is generated, compared with the shortest distance 44 and the threshold value, and if the shortest distance is equal to or smaller than the threshold value, the shortest document is added to the same cluster as the own document. If the shortest distance is greater than the threshold, a new cluster of shortest documents is generated. Next, the document described in the shortest document 43 is searched from the document 41, and the shortest distance 44 of the corresponding document is compared with the threshold value. Once the root (the oldest document: document d1 in the example shown in FIG. 4) is reached, the latest document is selected from the document set in the document set that has not been compared with the threshold, and the shortest distance 44 And comparison with the threshold value is started.

  All the documents are compared with the threshold value, and the generated clusters are accumulated in the all-cluster accumulation unit 14.

  The all cluster storage unit 14 stores the clusters generated by the integration processing unit 13 for all the documents.

  In the first embodiment, the above-described processing for comparing the shortest distance with the threshold need only be executed once for all the documents, so that the processing is fast.

  Next, the operation when the data shown in FIG. 4 is stored in the shortest distance document storage unit 12 and 0.5 is input as the threshold value will be described.

  First, the latest document d10 is considered as an element of the cluster C1, and the latest document d10 is associated with the shortest distance 0.6, and this shortest distance 0.6 is compared with the threshold value 0.5. Since the shortest distance 0.6 of the document d10 is larger than the threshold value 0.5, a new cluster C2 is created, and d9 of the shortest document ID shown in FIG. 4A is stored as an element of this cluster C2.

  Subsequently, for d9 of the shortest document ID, the shortest distance 0.5 between the shortest document ID d2 and the threshold value 0.5 is compared in the same manner as described above, and the shortest distance 0.0 between the document IDd9 and the document IDd2 is compared. Since 5 is 0.5 or less, the document ID d2 is added to the cluster C2 to which the document ID d9 belongs.

  FIG. 5 is a diagram illustrating an example of data stored in the all-cluster storage unit 14 according to the first embodiment.

  The result of processing all the documents as described above is an example shown in FIG. As shown in FIG. 5A, the all cluster storage unit 14 stores a cluster ID 51 that uniquely indicates a cluster and a document set 52 that belongs to each cluster in association with each other. FIG. 5B is an example in which the example shown in FIG. 5A is displayed in a tree structure, and each document is connected to the shortest document having the shortest distance from the own document by a solid line.

  The period designation cluster generation unit 15 is included in the period (designation period) from the start time to the end time received from the input unit 20 among the documents constituting the clusters accumulated in the all cluster accumulation unit 14. A document having the time information is detected, and a period-designated cluster that is a cluster constituted only by the detected document is generated.

  The period designation cluster accumulation unit 16 accumulates the period designation cluster generated by the period designation cluster generation unit 15.

  FIG. 6 is a flowchart illustrating the operation of the period designation cluster generation unit 15 according to the first embodiment.

  First, all cluster IDs are acquired from the all-cluster storage unit 14, and processing for each cluster is sequentially performed. If there is an unprocessed cluster (S11), a set of document IDs corresponding to the unprocessed cluster ID is acquired from all cluster storage units 14 (S12).

  Next, it is checked whether or not there is a document included in the specified period by referring to the time information 42 of each document stored in the shortest distance document storage unit 12 (S13). A cluster in which no document exists within the specified period returns to S11 without performing the subsequent processing, and performs processing for the next cluster.

  If there is a document included in the specified period among the set of document IDs corresponding to the unprocessed cluster ID (S13), it is checked whether the cluster is divided based on the specified period (S13). S14). If the cluster is not divided (S14), all documents in the cluster are included in the period, and the document ID associated with the cluster ID being processed is stored in the period designation cluster storage unit 16 as it is. (S15).

  If the cluster is divided based on the specified period (S14), then in each document in the cluster, the parent node selects a document having time information before the start time output by the input unit 20 Then, it is checked whether there are a plurality of the selected documents. That is, it is checked whether there are a plurality of documents such as the documents d6, d8, and d9 in the cluster C2 shown in FIG. 8 (S16).

  The “parent node” is a document having the shortest distance from the self document among documents having time information older than the self document. In other words, a document having the shortest distance from the self document among documents having time information older than the self document is referred to as a “parent node” with respect to the self document.

  If there is only one document whose parent node time information is earlier than the start time (S16), it is included in the specified period in the document ID set associated with the cluster ID. Only the selected document is selected, and the selected document is associated with the cluster ID and stored in the period-designated cluster storage unit 16 (S17).

  If there are a plurality of documents whose parent node is outside the specified period, a division determination process (S18) is executed and compared with a threshold value to determine whether to divide the cluster.

  FIG. 7 is a flowchart illustrating the operation of the division determination process (S18) of the period designation cluster generation unit 15 according to the first embodiment.

  The division determination process (S18) is associated with the ID of a cluster including a plurality of documents that are child nodes of a parent node having time information before the specified time, the specified period, and the start time. And the time information of the document are input. First, a document ID that directly inherits the input cluster ID is determined.

  Here, a document that is most similar to a document having time information before the start time is selected from the cluster. Therefore, a document ID (provisional route) is selected based on the shortest distance 44 for each document ID stored in the shortest distance document storage unit 12 (S20).

  Next, in the set of sub-tree documents with the temporary route as the root, the document included in the specified period is associated with the cluster ID and stored in the period specified cluster storage unit 16 (S21). Then, a set of documents that are documents other than the temporary root and whose parent node time information is earlier than the start time is selected (S22), and the following processing is executed for this document set. The “provisional route” is a document whose own document is within a predetermined period and whose parent node is outside the period.

  First, if there is an unprocessed document in the document set (YES in S23), one unprocessed document is selected, and a distance from the temporary route is newly calculated (S24). When calculating the distance, the inter-document distance calculation unit 11 has already calculated the inter-document distance, and the calculated distance is stored and referred to, so that the inter-document distance is calculated each time, rather than Processing is fast.

  If the calculated distance is equal to or less than the specified threshold value (YES in S25), a document included in the specified period in the set of documents in the subtree whose root is the document ID being processed is a cluster ID. Are stored in the period-designated cluster storage unit 16 (S26).

  If the calculated distance is larger than the threshold (NO in S25), a new cluster ID is created (S27), and included in the specified period in the set of subtree documents rooted at the document ID being processed. The newly created cluster ID is associated with the existing document and accumulated in the period designation cluster accumulation unit 16 (S28).

  Here, the “newly created cluster ID” is a cluster other than the cluster IDs stored in all the cluster storage units 14. Further, in order for the newly created cluster ID to correspond to the cluster to which it originally belonged, the cluster ID being processed is stored in association with the newly generated cluster ID (S29).

  When the process for one document is completed, the process returns to S23, and the process is executed until there is no unprocessed document (NO in S23).

  Next, the process of the period designation cluster generation unit 15 will be described using actual data as an example.

  FIG. 8 is a diagram for explaining the processing in the period designation cluster generation unit 15.

  In FIG. 8, the solid line connecting the documents has a tree structure, and this cluster structure is stored in the all-cluster storage unit 14. In FIG. 8, a dotted line is a dotted line connecting two documents whose distances are to be calculated in S24.

  In the example shown in FIG. 8, as described in the explanation of the integration processing unit 13, the threshold value is set to 0.5, and based on the threshold value 0.5, the cluster C1, the cluster C2, and the cluster C3 are generated and exist. Yes.

  When start time = T1 and end time = T2 are given as the specified period, first, three cluster IDs: cluster C1, cluster C2, and cluster C3 are acquired from all cluster storage units 14 (S10). Subsequently, the following processing is executed for each cluster ID.

  As an unprocessed cluster ID (YES in S11), the cluster C1 is first selected, and a document d10 is acquired as a set of documents corresponding to the cluster C1 (S12). The cluster C1 is composed of only the document ID: d10, and the document d10 is a document included in the designated period (YES in S13). Since all document IDs are included within the specified period (NO in S14), the document d10 is stored in the period specified cluster storage unit 16 in association with the cluster C1.

  Next, the cluster C2 is selected (YES in S11), and a set of documents {d1, d2, d5, d6, d7, d8, d9} corresponding to the cluster C2 is acquired (S12). In cluster C2, there is a set of documents {d6, d7, d8, d9} included in the specified period (YES in S13). Depending on the period, sets {d1, d2, d5} and sets {d6, d7, d8, d9} (YES in S14).

  Therefore, it is checked whether there are a plurality of documents whose parent node time information is earlier than the start time T1 in the document set {d6, d7, d8, d9} included in the specified period. (S16), the parent node d5 of the document d6, the parent node d5 of the document d8, and the parent node d2 of the document d9 are before the start time T1, as shown in FIG. Since the parent nodes of the three documents d6, d8, and d9 are outside the designated period (YES in S16), the division determination process (S18) is executed.

  In the division determination process, first, the distance from the parent node is the shortest from the set {d6, d8, d9} of documents (child nodes) whose parent node time information is earlier than the designated start time. The document d6 is selected as the document (provisional route) (S20). This is called a temporary route. That is, the “provisional route” is a document having the shortest distance from the parent node from a set of documents (child nodes) whose parent node time information is earlier than the designated start time.

  Next, among the set of documents {d6, d7} included in the subtree having the temporary root d6 as a root, the documents d6 and d7 included in the designated period are associated with the cluster C2, It accumulates in the period designation cluster accumulation unit 16 (S21).

  Next, a set of documents d8 and d9 other than the temporary route d6 whose parent node time information is earlier than the start time T1 is selected (S22), and the following processing is performed for each document ID belonging to this set. Execute.

  First, when there is an unprocessed document in the document set {d8, d9} (YES in S23), an unprocessed document is selected and a distance from the temporary route d6 is calculated (S24). First, the document d8 is selected, and the distance from the temporary route (d6) is calculated. If the calculated distance is, for example, 0.25, the specified threshold value is 0.5 or less (YES in S25), and therefore, out of the set {d8} of documents included in the subtree having the document d8 as a root. In this example, since there is no child node in the document d8, only the document d8 is associated with the cluster C2 and stored in the period designation cluster storage unit 16 (S26). . The “child node” is a document that has time information that is newer than the time information of the own document and that is at the shortest distance from the own document.

  Next, the unprocessed document: d9 is processed (YES in S23). The distance to the temporary route d6 is calculated (S24). If the calculated distance is 0.6, for example, it is larger than the specified threshold value 0.5 (NO in S25), so a new cluster ID: cluster C4 is set. Create (S27).

  Of the set of documents {d9, d10} included in the subtree having the document d9 as a root, the document included in the designated period is only {d9}, and the document d9 corresponds to the cluster C4. In addition, it is stored in the period designation cluster storage unit 16 (S28). At the time of accumulation, the fact that it was the cluster C2 may be accumulated before the cluster C4 is divided (S29). Since the processing of the document set {d8, d9} is completed (NO in S23), the division determination processing is ended, and the process returns to S11 in FIG.

  In S11, the process is completed for the cluster IDs: cluster C1 and cluster C2, and an unprocessed cluster C3 is selected. A set {d3, d4} of documents corresponding to the cluster C3 is acquired to check whether there is a document included in the specified period. Since all the documents are before the start time ( (NO in S13), the process returns to S11.

  Since the processing has been completed for all the cluster IDs: cluster C1, cluster C2, and cluster C3, the processing of the period designation cluster generation unit 15 is terminated.

  FIG. 9 is a diagram illustrating an example of data accumulated in the period designation cluster accumulation unit 16 at the time when the processing is completed.

  Corresponding to the cluster ID 61, a document set 62, which is a set of only documents included in the specified period, is stored in the period specified cluster storage unit 16. In addition, in the division determination process, when a new cluster ID: cluster C4 is created, the cluster C2 that is the pre-division cluster ID is associated and stored.

  FIG. 10 is a diagram illustrating an example of a screen displayed by the cluster display unit 30 using information stored in the period designation cluster storage unit 16 and the document storage unit 10.

  FIG. 10 (1) displays the clustering results for two periods. The clustering results in the periods T0 to T1 are displayed in the area 71, and there are clusters C2 and C3. The clustering result in the period T1 to T2 is displayed in the area 72, and the cluster C1, the cluster C2, and the cluster C4 exist. Each cluster is displayed as a circle, and the IDs of documents belonging to the cluster are displayed in the circle.

  FIG. 10B shows an overview 80 of documents belonging to a cluster when the user selects a cluster on this screen.

  FIG. 10B shows an overview when the cluster C2 in the period T0 to T1 is selected. Each cluster is a clustering result using only documents within a period.

  Since a uniform cluster ID (same cluster ID) is assigned in different periods, it can be seen that the same number of documents exist in two periods and the topic continues in two periods. Further, it can be seen that the cluster C4 whose topic has changed slightly is derived from the cluster C2. Furthermore, it can be seen that the cluster C3 is a topic that occurs instantaneously during the period T0 to T1, and the cluster C1 is a topic that newly occurs during the period T1 to T2.

  Before the user specifies the threshold value or the period, the inter-document distance calculation unit 11 executes the process to create the shortest distance document storage unit 12, and then the user specifies the threshold value and the period. Then, by executing the processing by the integration processing unit 13 and the processing by the period designation cluster generation unit 15, it is possible to provide a cluster using only documents within the designated period in a short time and with high accuracy. .

  Further, when the user changes the period, the cluster for the corresponding period can be generated only by executing the process of the period designation cluster generation unit 15.

  In the above embodiment, each document is stored together with time information such as creation time and update time, and is classified only for documents belonging to an arbitrary period (specified period) designated by the user.

  That is, in the above embodiment, cluster creation and cluster change processing by specifying a period are performed by the following processing.

  (1) Among documents having time information older than the own document, a document having the shortest distance from the own document is defined as a “parent node” for the own document, and the distance is equal to or less than a specified threshold. A set of own documents is defined as one cluster.

  (2) Using all the documents, the cluster creation process (1) is executed only once, and the correspondence between each document and the cluster is stored in the storage unit.

  (3) When a period is specified, only documents within the specified period are classified for each cluster based on the correspondence relationship stored in (2) above. Documents outside the specified period are not processed.

  (4) Among the documents within the specified period belonging to the same cluster, when there are a plurality of documents whose parent node time information is out of the period, the documents having the oldest time information and other documents among these documents If the distance between the two documents is newly calculated and if it is less than or equal to the threshold value, it is determined that the two documents and each descendant node all belong to the same cluster. Otherwise, the two documents and each descendant node Is determined to belong to a different cluster.

  According to the above-described embodiment, when a tree structure is generated for all the stored documents and a threshold regarding the distance between documents is given, a cluster can be generated by searching all the documents once. it can.

  Further, according to the above embodiment, even when an arbitrary period is given, the distance between documents whose parent node time information is outside the period within the same cluster is calculated using the cluster information generated for all documents. By simply doing, it is possible to generate a cluster with high accuracy using only documents within the period.

  Furthermore, since clusters are generated for all documents, it is possible to associate clusters in different consecutive periods, and it is possible to present whether the clusters have become larger, smaller, or divided in different periods. it can.

  In the above embodiment, the processing target is the text of the document, but “title + text” including the title may be the processing target.

  That is, in the above-described embodiment, the document storage unit that stores time information, the title, and the text of the document in association with the document ID that uniquely identifies the document, the threshold of the distance for generating the cluster, and the start time And an input unit for outputting the end time, and the body text of the document stored in the document storage unit, and the distance between the document having time information older than the time information of the document and the document is determined between the documents. The inter-document distance calculation unit that calculates based on the similarity, the document ID of the document that has the shortest distance among the distances between the document having time information older than the time information of the own document and the own document, and A shortest distance document storage unit that stores the shortest distance, and an integrated processing unit that integrates documents in which the shortest distance stored in the shortest distance document storage unit is shorter than the threshold received from the input unit into one cluster And the integrated processing unit A specified period that is a period from the start time received from the input unit to the end time, among all the cluster storage units that store the integrated cluster and the documents that constitute the clusters stored in all the cluster storage units Only a document having time information included in the period is detected, a period designation cluster generation unit that generates a period designation cluster based on the detected document, and the period designation cluster generated by the period designation cluster generation unit is accumulated. It is an example of the document classification apparatus which has a period designation | designated cluster storage part.

  In this case, a set of documents corresponding to an unprocessed cluster ID is acquired from all the cluster storage units, and the documents included in the specified period are among documents having time information older than the own document. Division determination that determines whether or not to divide a cluster based on the threshold if there are multiple documents whose parent node time information is the document with the shortest distance from the own document before the start time. Execute the process.

  In the above case, the threshold value, the specified period, a document associated with the cluster ID of a cluster having a plurality of documents whose parent node is earlier than the start time, and the time information of the document are input. In the set of documents whose parent node time information is earlier than the start time, select a temporary route that is the document with the shortest distance from the parent node, and in the set of sub-tree documents whose root is the temporary route, The documents included in the specified period are associated with the cluster ID, stored in the period specified cluster storage unit, and a set of documents whose parent node is earlier than the start time is selected other than the temporary route. If there is an unprocessed document in the document set, one unprocessed document is selected, a distance from the temporary route is newly calculated, and if the calculated distance is equal to or less than the threshold, processing is performed. Documents inside A document included in the specified period in the set of sub-tree documents to be used as a start date is associated with a cluster ID and stored in the period specified cluster storage unit, and the calculated distance is greater than the threshold value. For example, a new cluster ID is created, and a cluster ID that is not stored in all the cluster storage units in a document included in the specified period in a set of documents in a subtree whose root is the document ID being processed. Are associated with each other and stored in the period-designated cluster storage unit.

  Moreover, the said Example can be grasped | ascertained as invention of a method. In other words, in the above-described embodiment, the time information, the title, and the text of the document are stored in the storage device in association with the document ID that uniquely identifies the document, and the distance for generating the cluster is determined. Using the input stage for inputting the threshold value, the start time and the end time, and the text of the document stored in the document storage stage, the document having time information older than the time information of the own document and the own document The distance is calculated based on the similarity between documents and stored in the storage device, and the distance between the document having time information older than the time information of the document and the document is The shortest distance document storage stage that stores the document ID of the document that is the shortest distance and the shortest distance in the storage device, and the shortest distance that is stored in the shortest distance document storage stage is the threshold received in the input stage. Shorter than Are integrated into one cluster and stored in a storage device, the cluster integrated in the integration processing step is accumulated in the storage device, and the clusters are accumulated in the cluster accumulation step. , Only documents having time information included in a specified period that is a period from the start time to the end time received in the input stage are detected, and the period is determined by the detected document. A document classification method comprising: a period designation cluster generation stage for generating a designation cluster and storing it in a storage apparatus; and a period designation cluster accumulation stage for accumulating the period designation cluster generated in the period designation cluster generation stage in a storage apparatus It is an example.

  Moreover, the said Example can be grasped | ascertained as invention of a program. That is, the said Example is an example of the program which makes a computer perform the method of any one of Claims 1-3.

Furthermore, the program may be recorded on a recording medium. That is, the said Example is an example of the computer-readable recording medium which recorded the program of Claim 7. In this case, CD, DVD, HD, semiconductor memory, etc. can be considered as the recording medium.

It is a flowchart which shows the principle of Example 1 of this invention. It is a figure explaining the principle of Example 1. FIG. 1 is a diagram illustrating a document classification apparatus DC1 that is Embodiment 1. FIG. It is a figure which shows the example of the data accumulate | stored in the shortest distance document storage part. 6 is a diagram illustrating an example of data stored in an all-cluster storage unit 14 in Embodiment 1. FIG. 6 is a flowchart illustrating an operation of a period designation cluster generation unit 15 according to the first embodiment. 6 is a flowchart illustrating an operation of a division determination process (S18) of a period designation cluster generation unit 15 according to the first embodiment. It is a figure explaining the process in the period designation cluster production | generation part 15. FIG. It is a figure which shows the example of the data accumulate | stored in the period designation | designated cluster storage part 16 at the time of a process being complete | finished. It is a figure which shows the example of a screen which the cluster display part 30 displays using the information accumulate | stored in the period designation | designated cluster storage part.

Explanation of symbols

DC1 ... Document classification device,
10: Document storage unit,
11 ... Document storage unit,
12 ... shortest distance document storage unit,
13 ... integrated processing unit,
14: All cluster storage units,
15 ... Period designation cluster generation unit,
16: Period-designated cluster storage unit,
20 ... input part,
30 ... Cluster display section,
40 ... Wooden structure.

Claims (6)

A document storage unit that stores time information, a title, and the text of the document in association with a document ID that uniquely identifies the document;
An input unit for inputting a distance threshold for generating a cluster, a start time, and an end time;
Inter-document distance calculation that uses the body text of the document stored in the document storage unit to calculate the distance between the document having time information older than the time information of the self-document and the self-document based on the similarity between documents. Part;
Among documents having time information older than the time information of the self-document, a document whose distance from the self-document is the shortest distance is a parent node, and the document ID of the parent node and the shortest distance are the document ID of the self-document. A shortest distance document accumulating unit that accumulates in association with;
The shortest distance stored in the shortest distance document storage unit is compared with the threshold value received from the input unit. If the shortest distance is less than or equal to the threshold value, the shortest document and the own document are regarded as the same cluster, and the shortest distance is stored. An integrated processing unit for generating a cluster by setting the shortest document and the self-document as separate clusters if is greater than the threshold;
An all-cluster storage unit that stores the cluster integrated by the integration processing unit in association with a cluster ID that uniquely identifies the cluster and a document set belonging to each cluster ;
Of the documents constituting the cluster stored in all cluster storage units, only documents having time information included in a specified period that is a period from the start time to the end time received from the input unit. A period designation cluster generation unit that detects and generates a period designation cluster based on the detected document;
A period-designated cluster storage unit that accumulates the period-designated cluster generated by the period-designated cluster generation unit;
Have
The period specified cluster generation unit
A set of documents corresponding to an unprocessed cluster ID is acquired from all the cluster storage units,
When there are no documents that are included in the specified period and the time information of the parent node is earlier than the start time, or the distance between a plurality of documents that exist even if there are a plurality is the threshold value If it is the following, one period designated cluster among the documents included in the designated period in the set of documents corresponding to the cluster ID,
When there are multiple documents that are included in the specified period and whose parent node time information is earlier than the start time, and the distance between the existing documents is greater than the threshold, A document classification apparatus characterized in that a document included in the specified period in a set of documents corresponding to a cluster ID is made into a plurality of period specified clusters . In claim 1,
The period specified cluster generation unit
When there are a plurality of documents whose parent node time information is earlier than the start time, select a temporary route that is a document with the shortest distance from the parent node in the set of the plurality of documents.
In a set of subtree documents rooted at the temporary route, the documents included in the specified period are set as one period specified cluster ,
Other than the temporary route, a set of documents whose parent node is earlier than the start time is selected. If there is an unprocessed document in the document set, one unprocessed document is selected. If the calculated distance is equal to or less than the threshold value, a document included in the specified period in the set of sub-tree documents rooted at the document being processed is temporarily stored. The same period specified cluster as the period specified cluster of the route,
If the calculated distance is larger than the threshold value, the documents included in the specified period in the set of subtrees whose root is the document ID being processed are separated from the period specified cluster of the temporary root. Document classifying apparatus characterized in that it is a period specified cluster . A document storage stage that stores time information, a title, and the text of the document in association with a document ID that uniquely identifies the document;
An input stage for inputting a distance threshold for generating a cluster, a start time, and an end time;
Inter-document distance calculation that uses the body text of the document stored in the document storage stage to calculate the distance between the document having time information older than the time information of the own document and the own document based on the similarity between documents. Stages;
Among documents having time information older than the time information of the self-document, a document whose distance from the self-document is the shortest distance is a parent node, and the document ID of the parent node and the shortest distance are the document ID of the self-document. The shortest distance document storage stage to be stored in association with
The shortest distance stored in the shortest distance document storage stage is compared with the threshold value input in the input stage, and if the shortest distance is equal to or less than the threshold value, the shortest document and the own document are regarded as the same cluster, and the shortest distance is stored. An integrated processing stage for generating a cluster by making the shortest document and the self-document separate from each other if the distance is larger than the threshold;
An all-cluster storage stage for storing the clusters integrated in the integration processing stage in association with a cluster ID that uniquely identifies the cluster and a document set belonging to each cluster ;
Of the documents that make up the cluster stored in all cluster storage stages, only documents that have time information included in the specified period that is the period from the start time to the end time input in the input stage And a period-specific cluster generation step of generating a period-specific cluster according to the detected document;
A period-designated cluster accumulation stage for accumulating the period-designated cluster generated in the period-designated cluster creation stage;
Have
The period specified cluster generation stage
A set of documents corresponding to an unprocessed cluster ID is acquired from the clusters accumulated in the all cluster accumulation stage ,
When there are no documents that are included in the specified period and the time information of the parent node is earlier than the start time, or the distance between a plurality of documents that exist even if there are a plurality is the threshold value If it is the following, one period designated cluster among the documents included in the designated period in the set of documents corresponding to the cluster ID,
When there are multiple documents that are included in the specified period and whose parent node time information is earlier than the start time, and the distance between the existing documents is greater than the threshold, A document classification method, wherein a document included in the specified period in a set of documents corresponding to a cluster ID is made into a plurality of period specified clusters . In claim 3,
The period specified cluster generation stage
When there are a plurality of documents whose parent node time information is earlier than the start time, select a temporary route that is a document with the shortest distance from the parent node in the set of the plurality of documents.
In a set of subtree documents rooted at the temporary route, the documents included in the specified period are set as one period specified cluster ,
Other than the temporary route, a set of documents whose parent node is earlier than the start time is selected. If there is an unprocessed document in the document set, one unprocessed document is selected. If the calculated distance is equal to or less than the threshold value, a document included in the specified period in the set of sub-tree documents rooted at the document being processed is temporarily stored. The same period specified cluster as the period specified cluster of the route,
If the calculated distance is larger than the threshold value, the documents included in the specified period in the set of subtrees whose root is the document ID being processed are separated from the period specified cluster of the temporary root. A method for classifying documents, characterized in that it is in the stage of making a specified cluster of periods .   The program which makes a computer perform the method of Claim 3 or Claim 4.   A computer-readable recording medium on which the program according to claim 5 is recorded.

Images