JPH1027125A - Document classifying device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To adequately classify many documents which are linked complicatedly like hypertexts by generating an initial document cluster on the basis of link relation and document distances, taking a cluster analysis based upon the document distances, and classifying the documents. SOLUTION: A document storage part 11 stores electronized documents and a link relation storage part 12 stores the link relation among the documents stored in the document storage part 11. A distance calculating processing part 13 calculates the document distances from the appearance frequencies of words included in the respective documents stored in the document storage part 11 and then a document classifying processing part 14 generates the initial document cluster on the basis of the stored link relation and the obtained document distances and takes the cluster analysis based upon the document distances to classify the documents stored in the document storage part 11. Then an output processing part 15 outputs the classification result of the document classifying processing part 14.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a document classifying apparatus for classifying a large number of electronic documents existing on a network system, and more particularly to a classifying apparatus for classifying a large number of complicatedly linked documents such as hypertexts. And a document classifying device.

[0002]

2. Description of the Related Art With the spread of the Internet today, electronic documents on computer systems located at physically distant locations can be easily accessed via a network. Such electronic documents are
It is possible to embed link information for referring to another electronic document in a document, and the electronic document in which the link information is embedded can be linked to another electronic document by following the link information. Can be easily reached. The form of an electronic document in which such link information is embedded is generally called hypertext.

[0003] In a network system such as the Internet, as the number of accessible electronic documents increases in a large amount, it is becoming difficult to search for a desired document from the large amount of electronic documents based only on link information.

As one method for solving such a problem, systems for providing a search service for electronic documents published on the Internet are increasing. In these search systems, a collective keyword search can be performed on a large number of documents. That is, by searching for electronic documents published on the Internet as much as possible in advance and obtaining the contents of each document, it is possible to perform such a collective keyword search. I have.

[0005] Further, in such a search system, there is a system in which each document is classified into several categories according to its contents, thereby further improving search efficiency. In this case, the user of the system can perform a keyword search centering on a category considered to include a desired document, and improvement in search efficiency can be expected.

There are two methods for classifying documents: a manual method and a method for automatically performing calculations based on the distance between documents. When classifying a large number of documents, the latter method is advantageous in terms of efficiency.

(Prior Art 1) As a method for classifying such documents, for example, a document "Luhn, HP, 'A statisti
cal approach to mechanised encoding and searching
of library information ', IBM journal of research a
As discussed in “nd development, 1, 309-17 (1957)”, there is a method of weighting words based on the frequency of occurrence of each word included in a document. In this case, particularly, a word having a high weight can be regarded as a keyword representing the document.

(Prior Art 2) A method of obtaining the inter-document distance from the weight of words is described in, for example, the document "Salton, G. and
McGill, NJ, 'Introduction to modern informatio
n retrieval ', NewYork, McGraw-Hill (1983) ", and is used in some document classification systems.

In such a document classification system,
Assuming that the weight Ru of each word Ru is set for the document Pi, the document vector Vpi of the document Pi is defined as follows. However, when the word Ru does not exist in the document Pi, “0” is set to the weight Wiu. If the word Ru exists, the weight Wiu is a real value equal to or greater than “0”. Ωiu * = Wiu / (max Wiu) (1-1) Vpi * = (Ωi1 *, Ωi2 *,..., Ωim *) (1-2) Vpi = Vpi * / | Vpi * | = (Ωi1 , Ωi2,..., Ωim) (1-3) Here, the total number of different words is m,
Also, Ωiu (0 ≦ Ωiu ≦ 1) is redefined as the weight Wiu of each word Ru for the document Pi. Then, the distance d (Pi, Pj) between the document Pi and the document Pj in this case
｛(0 ≦ d (Pi, Pj) ≦ 1) is defined as d (Pi, Pj) = 2 (arccos (Vpi · Vpj)) / π (1-4) as an angle between both document vectors I do.

(Prior Art 3) A document can be classified by using a cluster analysis method based on the inter-document distance obtained as described above. For the cluster analysis technique, for example, reference can be made to the document “Tanaka, Tarumi, Wakimoto,“ Statistical Analysis Handbook II, Multivariate Analysis ”, pp. 226-257, Kyoritsu Shuppan (1984)”. Since the technique of cluster analysis is a well-known technique, description thereof is omitted here.

[0011]

In the document classification system according to the above-mentioned conventional technology, there is a further problem to be solved as follows. In other words, in the document classification system according to (Prior Art 1) or (Prior Art 2), the inter-document distance obtained mechanically is not set in consideration of the meaning and content of the document. Therefore, it is difficult to say that such a document classification based on the inter-document distance sufficiently reflects the semantic content of the document. For this reason, it is still difficult for a user to find a desired document from a large amount of electronic documents.

SUMMARY OF THE INVENTION The present invention has been made to solve such a problem, and an object of the present invention is to appropriately classify a large number of complicatedly linked documents such as hypertext. It is an object of the present invention to provide a document classification device capable of performing the above.

[0013]

In order to achieve the above object, a document classifying apparatus according to the present invention comprises: a document storage means (11) for storing a plurality of digitized documents; Link relation storing means (12) for storing a link relation between a plurality of stored documents, and distance calculating means for calculating an inter-document distance from the appearance frequency of a word included in each document stored in the document storing means (13) generating an initial document cluster based on the link relation stored in the link relation storage means and the inter-document distance obtained from the distance calculation means, performing a cluster analysis based on the inter-document distance, Document classification means (14) for classifying a plurality of documents stored in the document storage means, and output means (15) for outputting a result classified by the document classification means.

In the document classifying apparatus having such features, the document storage means (11) stores a plurality of digitized documents, and the link relation storage means (12)
The link relation between a plurality of documents stored in the document storage means is stored. When the distance calculating means (13) calculates the inter-document distance from the frequency of appearance of words contained in each document stored in the document storing means, the document classifying means (14) sets the link relation stored in the link relation storing means. And generating an initial document cluster based on the inter-document distance obtained from the distance calculation means, performing a cluster analysis based on the inter-document distance, and classifying the plurality of documents stored in the document storage means. Then, the output unit (15) outputs the result classified by the document classification unit.

As described above, in the document classifying apparatus of the present invention, when classifying a document in the form of a hypertext using the cluster analysis technique, the link information described in the document is used. Since the link relationship between documents is basically set for a document that is semantically close (small distance) to the document created by the document creator, both the link relationship information and the inter-document distance are set. Perform a cluster analysis using. As a result, a document classification reflecting the intention of the creator of the document, that is, a document classification according to the semantic content of the document can be realized.

[0016]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be specifically described below with reference to the drawings. FIG.
FIG. 1 is a block diagram illustrating a configuration of a main part of a document classification device according to an embodiment of the present invention. In FIG. 1, 11 is a document storage unit, 12 is a link relation storage unit, 13 is a distance calculation processing unit,
Reference numeral 14 denotes a document classification processing unit, and reference numeral 15 denotes an output processing unit.

In the document classifying apparatus of this embodiment, the document storage unit 11 stores a large number of electronic documents, and a link relation storage unit 12 corresponds to each of the stored documents. Stores the link relation information between the documents (the location of the referenced document and its document identifier). The distance calculation processing unit 13 analyzes each document stored in the document storage unit 11 and calculates the inter-document distance from the appearance frequency of words included in the document. The calculation of the distance between documents is
For example, the calculation is performed by the same method (algorithm) as the above-described document classification system (prior art 2).

When the inter-document distance is calculated in this manner, the document classification processing unit 14 uses the link relation information stored in the link relation storage unit 12 and the inter-document distance obtained from the distance calculation processing unit 13. Then, an initial document cluster is generated, and a cluster analysis based on the inter-document distance is performed. Then, the plurality of documents stored in the document storage unit 11 are classified. The classified results are displayed and output to the user in an easily viewable display form via a graphical user interface by the output processing unit 15. Thus, for example, only documents belonging to the same group are displayed from a large number of documents according to the result of the cluster analysis, so that the user can easily find a desired document.

FIG. 2 is a block diagram showing a configuration of a main part of a document classification system connected to a wide area network according to another embodiment of the present invention. 2, reference numeral 20 denotes a wide area network, 21 denotes a document acquisition processing unit, 22 denotes a document storage unit, 23 denotes a link relation storage unit, 24 denotes an independent word extraction processing unit, 25 denotes a word weight setting processing unit, and 26 denotes a distance between documents. A calculation processing unit, 27 is a document classification processing unit, and 28 is an output processing unit. In the document classification system shown in FIG. 2, with respect to documents in the form of hypertext distributed and existing on the wide area network 20, these documents are acquired, and these electronic information are obtained from link information embedded in the documents. Document classification is performed on the contents of the document.

The wide area network 20 is, for example, the Internet in which a plurality of network systems are connected to each other.
It is configured by a program module that obtains a large amount of documents that can be accessed at 0. When one of the electronic documents stored on the computer system connected to the wide area network 20 is specified, the program module “acquires the contents of the specified electronic document,
An operation of identifying link information indicating another document embedded in the electronic document and retrieving another document indicated by the link information ”is performed recursively, and connected to the wide area network 20. Acquire electronic documents distributed on a plurality of computer systems.

A large number of documents acquired by the document acquisition processing section 21 are stored in the document storage section 22. In this case, the document storage unit 22 stores the document acquired by the document acquisition processing unit 21 as a pair with link information that specifies the document.
Also, in the link relation storage unit 23, the document storage unit 22
The presence / absence of a link relationship between the documents stored in the document is stored.

The independent word extraction processing unit 24 includes a document storage unit 22
The self-sustained words (words) are extracted from the document stored in the document by using a morphological analysis algorithm. Thereby, words are cut out from the document. The word weight setting processing unit 25 sets weights (importance) for all the independent words for each document based on the extraction result by the independent word extraction processing unit 24. Then, the inter-document distance calculation processing unit 26 calculates the distance between all two items of the document stored in the document storage unit 22 based on the weight set by the word weight setting processing unit 25. .

When the distance between the documents is calculated in this manner, the document classification processing unit 27 links the link relation storage unit 23
Based on the presence or absence of a link relationship stored in the document and the inter-document distance calculated by the inter-document distance calculation processing unit 26.
Classify documents by cluster analysis. As for the classified result, the classification result of the document classification processing unit 27 is displayed by the output processing unit 28. The output processing unit 28 collects, for example, documents belonging to the same group in a display format that is easy for the user to view using a graphical user interface, and outputs and displays the documents as a document classification result.

Generally, in an electronic document in the form of a hypertext, in order to distinguish a content portion of a document from link information (location of another document on a network and a document identifier), the link information includes link information. Tag indicating that the Therefore, by detecting a character string that matches the tag in the document, the document acquisition processing unit 21 identifies the link information from the document.

FIG. 3 is a flowchart showing the algorithm of the document acquisition processing of the document acquisition processing section 21. The operation of the document acquisition processing unit will be described with reference to the flowchart shown in FIG. When the link information of one document on the wide area network is designated as the initial condition and the document acquisition process is started, the process starts here. First, in step 31, as the initial condition, the link information (existing position on the network) And the document with the specified document identifier) as the document D
In the next step 32, the link information of the document D is added to the head of the list S, and the head of the list S is set as the current list position P. Next, in the next step 33, it is determined whether or not there is link information corresponding to the list position P of the list S. If the link information does not exist in this determination, it means that the document acquisition processing by the list operation here has ended, and the processing ends.

If it is determined in step S33 that the link information exists, the process proceeds to step S34, where the document content of the document D corresponding to each link information is acquired based on the link information. Next, in step 35, the link information of the document D and the content of the document are paired and stored in the document storage unit 22 (FIG. 4). Then, the next step 36
, All the link information (D1, D2,..., Dn) described in the document D is identified.

Next, at step 37, if there is link information that does not exist in the list S among the link information (D1, D2,..., Dn), the link information is linked to the list S. Next, in step 38, the document D and each link information (D1, D
2,..., Dn) are stored in the link information storage unit 23. Then, in step 39, the current list position P is set as the position next to the list position P in the list S, and the process returns to step 33 for processing on the next document. In step 33, as described above, it is determined whether or not there is link information corresponding to the list position P of the list S. In this determination processing, if link information exists, the processing from step 34 is performed. Is repeated, and if there is no link information, it means that the document acquisition processing by the list operation has been completed here, and the processing is terminated.

As described above, the other documents linked in the document are recursively acquired by the processing of the document acquisition processing unit 21. As a result, the obtained contents of each document are stored in the document storage unit 22 together with the link information of the document. Further, information on the link relation between the documents is stored in the link relation storage unit 23.

FIG. 4 is a diagram for explaining the relationship between the document contents stored in the document storage unit 22 and the link information. As shown in FIG. 4, the document storage unit stores the document content 42 of the acquired document and the link information (D1, D2,..., Dn) 41 in association with each other.

FIG. 5 is a diagram for explaining link relation information stored in the link relation storage unit 23. As shown in FIG. 5, the link relation storage processing unit 23 stores
Stored in the form of a dimensional matrix table. The row headings and column headings in the table correspond to the link information (D1, D2,..., Dn) stored in the document storage unit 22, and a circle indicates that there is a link relationship between the documents specified by the link information. , And the case where there is no link relationship is indicated by an x mark.

As described above, the independent word extraction processing unit 24
Extracts a word from each document content stored in the document storage unit 22 using a known morphological analysis algorithm, and extracts an independent word from each document content. For the extracted independent words, the word weight setting processing unit 25 sets “1” to the independent words included in the document contents of each document, and sets the independent words not included in the document contents. Is set to “0”.

FIG. 6 is a diagram showing an example of the weighting result by the word weight setting processing unit 25. As described above, each document content of the document here is linked information (D1, D2,
, Dn), as shown in FIG. 6, independent word (WORD) included in each document content
1, WORD2, WORD3,..., WORDn), “1” is set to the independent word included in the document content of each document, and “0” is set to the independent word not included in the document content. Are set as link information (D1, D1
2,..., Dn) are associated with each document content.

The inter-document distance calculation processing unit 26 calculates the inter-document distance between all two items of the document stored in the document storage processing unit 22 based on the above-described equations (1-1) to (1-4). Calculate the distance of The calculated inter-document distance for each document is
Link information (D1, D1) associated with each document content
2,..., Dn). FIG.
9 shows an example of the calculation result of the inter-document distance by the inter-document distance calculation processing unit 26.

When the inter-document distance of each document obtained from the link information is calculated in this way, the document classification processing unit 27 classifies the document based on the link-related information and the calculated inter-document distance. The processing unit 27 generates an initial document cluster, performs cluster analysis based on the inter-document distance, and classifies each document stored in the document storage unit 22.

FIG. 8 is a flowchart showing an algorithm of the document classification processing by the document classification processing section 27. The document classification processing will now be described with reference to FIG. In the document classification process, when the process is started, in step 81, a process of creating an initial document cluster is performed. That is, referring to the presence or absence of the link relationship in the link relationship storage unit 23 and the calculation result of the inter-document distance calculation unit 26, there is a link relationship and the inter-document distance is equal to or less than a predetermined constant K (0 ≦ K ≦ 1). Let a pair of documents be a cluster. In this case, if three or more documents are connected in a row satisfying this condition, they are combined into one cluster.

Then, the process proceeds to a step 82, wherein the distance between the two terms of the obtained previous cluster and all the documents not belonging to the cluster is recalculated. Next, in step 83, two clusters or documents having the smallest value among the obtained inter-term distances are defined as one cluster. Then, in the next step 84, it is determined whether or not the total value of the number of clusters and the number of documents is equal to or smaller than a predetermined number N (1 ≦ N ≦ n: the total number n of documents). If
Since there is a document that has not been classified yet, in this case, the process returns to step 82, and the classification process based on the cluster analysis in steps 82 and 83 is repeatedly performed. As a result, in the determination processing of step 84, when it is confirmed that the total value of the number of clusters and the number of documents is equal to or smaller than the predetermined number N, the classification of the documents is completed here, and a series of processing ends. Then, as described below, the classified result is displayed by the output processing unit 28.

In the process of step 82,
The recalculation of the inter-document distance between the cluster and the documents that do not belong to the cluster is performed. In this case, the inter-document distance calculation between the documents is performed by using the equations (1-1) to ( This is performed according to 1-4). The distance between the cluster C and the document D is calculated by calculating the distance between all the documents belonging to the cluster C and the document D according to Expressions (1-1) to (1-4). I do. Between cluster C1 and cluster C2, cluster C1 and cluster C2
The distance of each document belonging to is calculated, and the average value is set as the distance.

The document classification algorithm by the document classification processing unit 27 uses the inter-document distance and the link relation together for setting an initial cluster for general cluster analysis. That is, documents having a link relationship and having a short inter-document distance are put together to form an initial cluster, and furthermore, by using the inter-document distance and the link relationship together, a link relationship having a deep semantic relationship is selectively used. It becomes possible. Further, by using the link relationship, more reliable classification can be performed as compared with the conventional cluster analysis based only on the inter-document distance information. As a result, cluster analysis (classification) that further reflects the semantic content of the document becomes possible.

Explaining in a concrete example, in the case of the numerical examples shown in FIGS. 4, 5, 6, and 7, K = 0.6
In this case, the closest inter-document distance is the distance “0.09” between the document D1 and the document D4, and the next closest inter-document distance is the distance “0.12” between the document D4 and the document D5. Since the next closest inter-document distance is the distance “0.27” between the document D2 and the document D3, the initial clusters are (D1, D4, D5) and (D2, D3).

Next, the processing of the output processing unit 28 will be described. As described above, the output processing unit 28 collects documents belonging to the same group, for example, in a display format that is easy for the user to view using the graphical user interface, and outputs and displays the documents as a document classification result. A display form by such an output processing unit will be described by exemplifying a specific operation example. FIG. 9 to FIG. 13 show a change in a series of states of an operation screen when a user activates a document search device incorporated in the document classification device, searches for articles, and further classifies documents. Is shown. When the document search device is activated here, as shown in FIG.
The document search window screen 90 is displayed. The document search window screen 90 is provided with a keyword input field 91 for inputting a search keyword together with the search operation guide.

On the document search window screen 90, for example, as shown in FIG. 10, the user inputs keywords of "artificial brain", "qualitative inference", and "immune network" as keywords for searching articles. When an operation is performed, a search keyword is entered in the keyword input field 91 on the document search window screen 90. In this state, when the search button 92 is clicked with the pointer cursor 93, search processing is started, and the search processing is started. The result is displayed in the search result display field 94. As a result, as shown in FIG.
In the search result display field 94, for example, the titles of three documents of the hit document are displayed.

Next, the user activates the document classification device according to the present embodiment to further display a document closely related to the searched document. Therefore, as shown in FIG.
One of the documents displayed in the search result display field 94
When one of the documents 95 is designated (highlighted) by operating the pointer cursor 93 and the related document display button 96 is operated as shown in FIG. The example document classification device is activated. Then, a related document is obtained from the specified document by link information embedded therein, and a document classification process is performed by cluster analysis based on the inter-document distance, and documents belonging to the same group are displayed as related documents. It is displayed in the field 97.
In this way, when performing a document search, the user can efficiently search for documents including related documents.

[0043]

As described above, according to the document classification apparatus of the present invention, when performing a cluster analysis of a document in the form of a hypertext, the document is utilized by utilizing the link information described in the document. Document classification that reflects the will of the creator of the document. That is, it becomes possible to classify documents according to the semantic contents of the documents.

[Brief description of the drawings]

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

FIG. 2 is a block diagram showing a configuration of a main part of a document classification system coupled to a wide area network according to another embodiment of the present invention;

FIG. 3 is a flowchart showing an algorithm of a document acquisition process of a document acquisition processing unit 21;

FIG. 4 is a view for explaining the relationship between document content and link information stored in a document storage unit 22;

FIG. 5 is a view for explaining link relation information stored in a link relation storage unit 23;

FIG. 6 is a diagram illustrating an example of a weighting result by the word weight setting processing unit 25;

FIG. 7 is a diagram showing an example of a calculation result of an inter-document distance by an inter-document distance calculation processing unit 26;

FIG. 8 is a flowchart showing an algorithm of a document classification process by the document classification processing unit 27;

FIG. 9 is a diagram showing a first state of a series of state changes of an operation screen when a paper search is performed and a document classification is further performed;

FIG. 10 is a diagram showing a second state of a series of state changes of an operation screen when performing a paper search and further performing document classification;

FIG. 11 is a diagram showing a third state of a series of state changes of the operation screen when performing a paper search and further performing document classification;

FIG. 12 is a diagram showing a fourth state of a series of state changes on the operation screen when a paper search is performed and a document is further classified;

FIG. 13 is a diagram showing a fifth state of a series of state changes on the operation screen when a paper search is performed and a document is further classified.

[Explanation of symbols]

11: Document storage unit, 12: Link relation storage unit, 13: Distance calculation processing unit, 14: Document classification processing unit, 15: Output processing unit, 20: Wide area network, 21: Document acquisition processing unit,
22 Document storage unit 23 Link relation storage unit 24 Independent word extraction processing unit 25 Word weight setting processing unit 26 Document distance calculation processing unit 27 Document classification processing unit 28 Output processing unit .

Claims (1)

[Claims] 1. A document storage means for storing a plurality of digitized documents; a link relation storage means for storing a link relation between the plurality of documents stored in the document storage means; Distance calculating means for calculating an inter-document distance from the frequency of appearance of words contained in each of the stored documents; and a link relation stored in the link relation storing means and an inter-document distance obtained from the distance calculating means. Generating an initial document cluster, performing a cluster analysis based on the inter-document distance, classifying a plurality of documents stored in the document storage means, and outputting a result classified by the document classification means. And a document classification device.