JP4769151B2 - Document set analysis apparatus, document set analysis method, program implementing the method, and recording medium storing the program - Google Patents

Description

  The present invention relates to data mining technology.

  Currently, techniques for performing search and data mining on a document set (also referred to as a document data set) including text such as a news article such as a web page or a blog article are widely known.

  In this technology, when a user handles a large amount of documents, a document that the user wants to know the main topics existing in the document collection or wants to access a group of information related to a specific topic in the document collection. Often has a request to get information related to.

  The following methods are known as implementation methods for realizing these requirements.

  One is a method using a clustering algorithm (see, for example, Non-Patent Document 1). In this method, documents related to similar topics (or topic words) are expressed by expressing each document as a word vector and using similarities between vectors (such as cosine similarity) to integrate similar vectors. Identify as a cluster. The above-described request is realized by regarding each individual cluster as a set of information related to a specific topic.

  As another realization method, a method using topic word extraction (for example, see Patent Document 1) is known. This method uses a technique for extracting a keyword related to a specific topic in the document set from the document set based on the appearance frequency and distribution of the keywords. The above request is realized by regarding a document including a specific keyword extracted by the technique as a set of documents related to a specific topic.

As a related technique, a method of calculating the centrality of each node (document) by regarding the document as a node (for example, PageRank (for example, see Non-Patent Document 2)) is known. In order to specify a set of documents, a search engine (for example, see Non-Patent Document 3) existing on the web is also widely known. A technique for expressing a document as a word vector (for example, see Non-Patent Document 4) is also widely known.
JP 2005-208838 A (paragraphs [0066] to [0144]). D. Cutting, D.C. Karger, J .; Pedersen, and J.M. Tukry, “Scatter / Gather: a cluster-based approach to browsing large document collections”, Proc. of SIGIR 1992, ACM, June 1992, pp 318-329. S. Brin, and L.L. Page, “The anatomy of a large-scale hypertextual Web Search Engine”, Proc. of WWW7, Elsevier science, April 1998, pp 107-117. NTT Resonant Co., Ltd., “Portal Site goo”, [online], 2006, NTT Resonant Co., Ltd., [searched July 31, 2006], Internet <URL: http: // / Www. goo. ne. jp /> Kita Kenji, Tsuda Kazuhiko, Isogo Miki, “Information Retrieval Algorithm”, Kyoritsu Shuppan, January 2002.

  The following problems are known in the technology for realizing a request for acquiring information related to the above-described document.

  In the method using the clustering algorithm described above, it is assumed that all documents belong to any cluster. On the other hand, in real data, there are documents that belong to the so-called “others” that are not related to other documents. Therefore, appropriate clustering cannot always be performed, and as a result, much information is acquired for the above request. There are problems such as including noise.

  In the method using topic word extraction described above, the rules for making documents into one set are very simple whether or not they contain keywords, so a set of useful documents is always created. Not necessarily. For example, one keyword output by this method is often related to a plurality of topics, and conversely, one topic is often related to a plurality of keywords.

  The present invention has been made on the basis of the above-described problems, and identifies only a document set having a strong connection, classifies the document set into a cluster, and clearly analyzes the role of each document in the cluster. An object of the present invention is to provide a document set analysis apparatus, a document set analysis method, a program in which the method is implemented, and a recording medium storing the program.

In order to solve the above-described problem, the invention described in claim 1 is a document set analysis apparatus that specifies the role of a document based on the relationship between documents in the document set managed by the document data management means. The document set specifying unit that specifies the document set based on the document set specifying condition input from the input unit, and the similarity that evaluates the similarity regarding the topic word between the documents included in the specified document set An evaluation unit; a relationship extraction unit that extracts a relationship between documents based on the degree of similarity evaluated by the similarity evaluation unit; and a document based on the relationship between documents extracted by the relationship extraction unit As an index indicating the degree of relevance between documents other than the document, a centrality determination unit that calculates the centrality of the document, a relevance between documents obtained by the relationship extraction unit, and a center of each document To sex Therefore, a graph structure construction means for expressing the relationship between documents by two-dimensional coordinates, expressing the centrality by the coordinates of the third dimension with respect to the two-dimensional coordinates, and expressing the document set by a three-dimensional graph structure; A vertex node extracting means for extracting, as a vertex node, a document node having a maximal centrality score in the document set in the obtained graph structure; and the extracted vertex node and the vertex node connected thereto And a node node group specifying a document node group composed of one or more document nodes whose centrality score is lower than the centrality score of the vertex node and is not minimal means, together with the nodes to impart a label that indicates that those forming the role of topical words of the document set to the extracted top node, the identified peaks And labeling means the node group to the node group that imparts a label indicating that it is intended to form a part of a set of documents having a relevance to the topic words, as forming a part of the topic word A document node indicating a labeled vertex node, an information output means for visualizing and outputting a document node group indicating a group of mountain nodes labeled as a document set having a relationship with the topic word ; It is characterized by providing.

The invention described in claim 2 is a computer-executed document set analysis method for specifying a role of a document based on a relationship between documents in a document set managed by the document data management means, the input means A document set specifying step for specifying the document set based on a document set specifying condition input from the above, a similarity evaluation step for evaluating a similarity level related to a topic word between the documents included in the specified document set, A relationship extracting step for extracting a relationship between documents based on the similarity evaluated by the similarity evaluating unit; and a document and a document other than the document based on the relationship between documents extracted by the relationship extracting unit. as an indicator of relevance in height between the document and the center judgment step of calculating the center of the document, and the association between the document obtained by the relation extracting means, each sentence Based on the centrality of the document, the relationship between documents is expressed in two-dimensional coordinates, the centrality is expressed in the third dimension of the two-dimensional coordinates, and the document set is expressed in a three-dimensional graph structure. A structure construction step, a vertex node extraction step for extracting, as a vertex node, a document node having a maximum centrality score in the document set in the obtained graph structure, the extracted vertex node, A mountain that identifies a group of document nodes that is connected to a vertex node and has one or more document nodes that have a centrality score lower than the centrality score of the vertex node and that is not minimal. and Jo nodes specifying step, the node with respect to the extracted vertices node confers a label that indicates that those forming the role of topical words of the document set Both labeled step of applying a label which indicates that said corresponding node group versus specified mountain-like nodes is that those forming the role of a set of documents having a relevance to the topic words, the Visualizing a document node indicating a vertex node labeled as a topic word, and a document node indicating a mountain node labeled as a document set having a relationship with the topic word And an information output step for outputting.

The invention described in claim 3 is a document set analysis program, wherein the document set analysis method according to claim 2 is described as a computer program executable by a computer.

The invention described in claim 4 is a recording medium, wherein the document set analysis method described in claim 2 is described as a computer program executable by a computer, and the computer program is recorded.

According to the first and second aspects of the present invention, the relationship between documents based on centrality can be acquired.

Further, according to claim 1, 2 of the invention, can obtain a graph structure based on the relationship between documents.

According to the invention of claim 3 , the document set analysis method of claim 2 can be described as a computer program.

According to the fourth aspect of the present invention, a computer program that implements the document set analysis method according to the second aspect can be recorded on a recording medium.

As described above, according to the inventions of claims 1 and 2 , the role of the document can be clearly analyzed based on the relevance of the document.

Further, according to the first and second aspects of the invention, only a document set having a strong connection can be specified.

According to the invention of claim 3 , it is possible to provide a computer program in which the document set analysis method according to claim 2 is implemented.

According to invention of Claim 4 , the recording medium which recorded the computer program which mounted the document set analysis method of Claim 2 can be provided.

  This can contribute to the data mining technology field.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. The document set analysis apparatus according to the present embodiment identifies topics (that is, topic words) existing in the searched news articles, clusters the documents related to the identified topics, and further converts the documents in the clusters into It is a device that performs document analysis to clarify the position of each document.

  The configuration of the document set analysis apparatus in this embodiment will be described with reference to FIG.

  The document set analysis apparatus includes a document set specification unit 10, a similarity evaluation unit 20, a relationship extraction unit 30, a centrality determination unit 40, an information analysis unit 50, an information output unit 60, document data management means (for example, a document DB (Database). )) 70. Further, the information analysis unit 50 includes a graph structure construction unit 51, a vertex node extraction unit 52, a mountain node group identification unit 53, and a labeling unit 54.

  The document set specifying unit 10 includes a document data management unit 70 based on a specification or request including a document set specifying condition for specifying a document set (for example, a specification or request from a user) or a predetermined document set specifying condition. To specify a document set composed of a plurality of documents. The document set specifying condition may be input by an input means (for example, a keyboard device) provided in advance.

  The similarity evaluation unit 20 evaluates the similarity between the documents in the document set with respect to the topic (or topic word). For example, the similarity between documents can be determined by evaluating each document with a word vector and using the cosine similarity (for example, see Non-Patent Document 1), or constructing a language model based on one document and the other document. It is conceivable to perform an evaluation based on the language model of how much probability is generated from the language model.

  The relationship extraction unit 30 specifies a relationship as to whether or not there is a relationship between documents based on the similarity between documents evaluated by the similarity evaluation unit 20. For example, when the relationship between documents is expressed as a matrix A, it may be defined as the following equation.

Here, TopSim _p (i) indicates a set of documents included in p documents having high similarity to the document i. In general, when all the similarities are used, since a low similarity tends to be noise, a link is set only between documents having a high similarity. Sim (i, j) indicates the cosine similarity between the document i and the document j when the document is expressed as a word vector with log tf-idf weight (for example, Non-Patent Document 4). The log tf-idf weight is a weight of each element when each document is expressed by a vector.

  Furthermore, when all the similarities are used as described above, there is a link having a clearly smaller weight than other links. Therefore, it is conceivable to remove a link that transitions with a very low probability among outlinks. This operation is shown by the following equation.

Here, l _{i, q} represents the total value of the transition probabilities obtained by arranging the outlinks from the node i in descending order of the transition probabilities and adding until the threshold q is exceeded. TopLink _q (i) indicates a set of link destination nodes of links to be added.

  The centrality determination unit 40 regards the relationship between documents obtained by the relationship extraction unit 30 as a graph structure in which the document is regarded as a node and the relationship between documents is an edge with a weight (ie, similarity between documents). And the centrality of each node (document) is calculated. For the above-described centrality, it is conceivable to use a simple method for calculating the number of links, PageRank (see Non-Patent Document 2), or the like.

  The graph structure construction unit 51 converts the graph structure indicating the relationship between documents based on the relationship between the documents and the centrality score of each document obtained by the centrality determination unit 40 into a two-dimensional plane (for example, xy). A three-dimensional graph structure is constructed in which the centrality score of each document is assigned to the third dimension (eg, z-axis). FIG. 2 is a conceptual diagram of this three-dimensional graph structure. Note that FIG. 2 will be described later.

  The vertex node extraction unit 52 is higher than the node other than itself (corresponding to the document in a one-to-one correspondence) connected from the graph structure constructed by the graph structure construction unit 51 by the edge (ie, edge) connecting the nodes. A node with centrality is extracted as a vertex.

  The mountain-shaped node group identification unit 53 traces the graph structure in the direction of decreasing centrality from the vertex node extracted by the vertex node extraction unit 52, and identifies a mountain composed of nodes. That is, the documents are clustered by the processing up to the mountain node group specifying unit 53.

  The labeling unit 54 labels the vertex nodes extracted by the vertex node extraction unit 52, the mountain nodes centered on the peaks identified by the mountain node group identification unit 53, and the relationship between them. Do.

  Here, the graph structure and centrality will be described. According to the definition of centrality score, nodes in areas where there are many edges have a high score. Based on the graph structure, when a model in which a person walks across nodes (a model in which a user browses nodes along a graph) is considered, in such an area with high centrality, there are many transitions within the area, and between nodes Is also highly relevant. That is, the area is composed of nodes related to the same topic. Therefore, each mountain in FIG. 2 is considered to correspond to a different topic.

  Further, it is considered that each document has a characteristic depending on the position of the node included in the mountain in FIG. In the following, the characteristics of a document corresponding to each node will be described. Further, a method for identifying a role in a document set will be described for each node having each characteristic.

  The node in the first stage in FIG. 2 is a node at the top of the mountain (for example, corresponding to a node indicated by reference signs a1 and b1), and only one node exists in one mountain. Since these nodes are nodes having the highest state transition from the surrounding nodes and are the nodes most closely related to the surrounding nodes, it can be said that these nodes are documents that best express the topic. That is, the document indicated by the vertex node specifies the topic of the area. Hereinafter, the label of the document (node) that identifies the topic in this area is set as the core document (or core node).

  Nodes in the second stage are nodes close to the vertex (for example, nodes indicated by symbols a2, a3, a4 and b2, b3 in FIG. 2). These nodes are nodes that can be reached from a core node directly or indirectly by following only a bidirectional link. Bidirectional links are linked to each other and show high relevance. These nodes have many state transitions with the core node, and the content of the document is also highly related to the core document. Hereinafter, a label of a document (node) having a high relationship with the core document is referred to as a supplemental document (or supplemental node).

  The node at the third stage is a node linked to a core node or a supplemental node, such as nodes indicated by reference symbols a5, a6, a7, and b4 in FIG. It is a node that has a higher probability of transition to a core node or supplemental node of a specific topic than state transition to an external node or self-transition. These nodes are not necessarily the center of the topic, but include information related to the topic, and are often nodes that contain highly novel information such as information around the topic. Hereinafter, a label of a document (node) that often includes highly novel information such as information around the topic is referred to as a subtopic document (or subtopic node).

  The node at the final stage is a node that does not have a strong relationship with any topic node. For example, it is a node indicated by reference numeral c1 in FIG. This node has few similar nodes and high self-transition probability. Hereinafter, a label of a document (node) having few similar nodes and a high self-transition probability is referred to as an outlier document (outlier node). By allowing the outlier document to exist, it is possible to prevent other documents from forcibly belonging to any cluster and causing noise.

  Based on the above method, each node is labeled as follows.

  First, for each node, information indicating what topic each node is related to and the role of the document when expressing the topic is labeled (ie, core node). As given.

  Next, a label (that is, a supplemental node) as a cluster of documents related to the topic expressed by the vertex node is assigned to the mountain-shaped node group.

  Then, the combinations of mountain nodes are labeled (ie, subtopic nodes or outlier nodes) based on their connected state, with high relevance of topics expressed by the two mountains.

  The information output unit 60 displays (visualizes) the contents of the document set to the user by using the relationship between nodes, the centrality of each node, and the role in the document set obtained by the information analysis unit 50. ) Visualization is performed with a display device, for example.

  FIG. 3 is an example of visualization using a three-dimensional image (for example, a 3D (Dimension) map). FIG. 3 is a visualization of a document set of search results obtained using a search keyword (ie, topic word) “earthquake” for newspaper articles. A node indicated by a symbol CN in FIG. 3 is a core node.

  In FIG. 3, mountain-shaped portions are seen, but each mountain indicates an individual topic, and documents corresponding to nodes belonging to each mountain are a document group related to each topic.

  FIG. 4 shows an enlarged image of a part of FIG. On this enlarged image, it can be seen that the two peaks are connected by a supplemental node (for example, a node indicated by the symbol SN). This indicates that the two mountains are highly related. In fact, these two mountains touch on earthquakes that occurred in Japan, and show that it is possible to discover the relationship between topics using the proposed method.

  For example, one mountain-shaped structure in FIG. 4 represents one topic “the Great Hanshin Earthquake” or “the Great Kanto Earthquake”. The central part of the mountain is the main content of the event that actually occurred (for example, the occurrence of an earthquake), otherwise the information that accompanies the main topic (for example, post-earthquake fires, reconstruction) Node corresponding to support news).

  The document data management means 70 is a document data storage device (for example, a device including a hard disk device or a memory) having a search function that can specify a document set in accordance with conditions such as a search keyword designated by a user and a document last update date. It is. The document data management means 70 may be constructed by collecting information in advance from a web or the like. It is also conceivable to use a search engine (see Non-Patent Document 3) existing on the web as the document data management means 70 as it is.

  A document set analysis method according to this embodiment will be described with reference to FIG.

  First, a document set specifying condition designated by the user or predetermined is read from the input means (S101). The input means can be assumed to be a keyboard device, for example.

  Next, the document set specifying unit 10 specifies a set of documents that meet the document set specifying condition (S102).

  Next, the similarity evaluation unit 20 calculates the similarity between each document pair in the document group specified by the document set specifying unit 10 (S103).

  Next, the relationship extraction unit 30 extracts a pair having strong relevance based on the calculated similarity, and specifies relevance with weight (S104).

  Next, the centrality determination unit 40 creates an index (for example, PageRank) based on the information specified by the similarity evaluation unit 20 and the relationship extraction unit 30, and specifies the centrality of each node (S105). ).

  Next, the graph structure construction unit 51 arranges nodes (corresponding to documents one-to-one) in a three-dimensional space based on information obtained from the similarity evaluation unit 20, the relationship extraction unit 30, and the centrality determination unit 40. The constructed graph structure is constructed (S106).

  Next, the vertex node extraction unit 52 extracts a vertex node based on the graph structure obtained by the graph structure construction unit 51 (S107).

  Next, the mountain-shaped node group specifying unit 53 extracts a mountain-shaped node group from the graph structure obtained by the graph structure construction unit 51 and the vertex obtained by the vertex node extraction unit 52 (S108).

  Next, the labeling unit 54 uses the information obtained by the graph structure construction unit 51, the vertex node extraction unit 52, and the mountain node group identification unit 53 to determine the relationship between nodes, mountain nodes, and node groups. Then, labeling is performed (S109).

Then, the node labeled, mountain-like nodes, to visualize the relationship between the nodes as a list or a 3D map (S110).

  As described above, according to the present embodiment, the degree of similarity between documents is specified from the document set given by the document set specifying condition, and a portion having strong connection between documents is weighted based on the degree of similarity. Based on this information, the centrality of each document is calculated based on the relationship between the documents in the form of a graph structure, and the document group is three-dimensionally calculated from the relationship between the documents obtained above and the centrality value of each document. By identifying the position of each document from its positional relationship, the “main topic” specification, “topic related document specification”, “ Among the documents related to the topic, the “role of each document”, “relation between topics”, and the like can be acquired.

  More specifically, in this embodiment, the mutual similarity between documents is evaluated based on a document set specified based on a request from a user, and the relationship between documents is specified based on the similarity. Based on this relationship, the centrality of each document is evaluated. By using both the relationship between documents and the centrality of individual documents, it is possible to detect specific topics in a document set, cluster documents belonging to a specific topic, and clarify the positioning of each document in the cluster. Realize.

  Also, based on the relationship between documents and the centrality value of each document, the document set is regarded as a three-dimensional graph structure, and by specifying the vertex and mountain-shaped node group, the document set It is possible to detect a specific topic, cluster a document belonging to a specific topic, and clarify the position of each document in the cluster.

  Note that the present invention can be realized by configuring some or all of the functions of each means in the document set analysis apparatus of the present embodiment with a computer program and executing the program using the computer. It is needless to say that the procedure in the document set analysis method of the above can be configured by a computer program and the program can be executed by the computer. For example, FD (Floppy (registered trademark) Disk), MO (Magneto-Optical disk), ROM (Read Only Memory), memory card, CD (Compact Disk), DVD (Digital Versatile D) sk), and recorded in a removable disk, or stored, it is possible or distribute. It is also possible to provide the above program through a network such as the Internet or electronic mail.

  Further, a computer program describing a method related to the document set analysis apparatus described above may be implemented to access a memory or an external storage device that stores input / output data required for the method related to the document set analysis apparatus. .

  Although the embodiments of the present invention have been described above, the present invention is not limited to the described embodiments, and various modifications can be made within the scope described in each claim.

  For example, the information analysis unit in the present embodiment is configured by means such as a graph structure construction unit to a labeling unit. However, the information analysis unit is not limited to these units, and a relation between a document group and a document is regarded as a graph structure. Other processing means are also conceivable. More specifically, the labeling unit may specify the role by further finely labeling (for example, five or more levels).

The block diagram of the document set analysis apparatus in this embodiment. The three-dimensional structure conceptual diagram in this embodiment. The figure which shows an example of the visualization result in this embodiment. The enlarged view of an example of the visualization result in this embodiment. 6 is a flowchart illustrating a document set analysis method according to the present embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 ... Document set specific | specification part 20 ... Similarity evaluation part 30 ... Relation extraction part 40 ... Centrality determination part 50 ... Information analysis part 51 ... Graph structure construction part 52 ... Vertex node extraction part 53 ... Mountain-shaped node group specification part 54 ... Labeling unit 60 ... Information output unit 70 ... Document data management means a1, a2, a3, a4, a5, a6, a7, a8, b1, b2, b3, b4, c1 ... node CN, CN1, CN2 ... core node SN ... Supplemental node

Claims (4)

A document set analysis device that identifies a role of a document based on a relationship between documents in a document set managed by a document data management means,
Document set specifying means for specifying the document set based on the document set specifying condition input from the input means;
Similarity evaluation means for evaluating the degree of similarity related to topic words between the documents included in the specified document set;
A relationship extracting unit that extracts a relationship between documents based on the similarity evaluated by the similarity evaluating unit;
Based on the relationship between the documents extracted by the relationship extraction unit, the centrality determination unit that calculates the centrality of the document as an index indicating the high degree of relationship between the document and a document other than the document;
Based on the relation between documents obtained by the relation extracting means and the centrality of each document, the relation between documents is expressed by two-dimensional coordinates, and the centrality is expressed by the third-dimensional coordinates relative to the two-dimensional coordinates. And a graph structure construction means for representing the document set with a three-dimensional graph structure;
Vertex node extracting means for extracting, as a vertex node, a document node having a maximal centrality score in the document set in the obtained graph structure;
A document node group composed of the extracted vertex node and one or more document nodes connected to the vertex node and having a centrality score lower than the centrality score of the vertex node and not minimal and mountain-like nodes specifying means for specifying a mountain-shaped nodes a,
A label indicating that the node serves as a topic word of the document set is given to the extracted vertex node , and the node group is added to the identified mountain node group. Labeling means for assigning a label indicating that the document is a set of documents having relevance to a topic word ;
A document node indicating a vertex node labeled as the topic word, and a document node group indicating a mountain node group labeled as a document set having a relationship with the topic word Information output means for visualizing and outputting;
A document set analyzing apparatus comprising: A computer-executed document set analysis method for identifying a role of a document based on a relationship between documents in a document set managed by a document data management means,
A document set specifying step for specifying the document set based on the document set specifying condition input from the input means;
A similarity evaluation step for evaluating a similarity level related to a topic word between the documents included in the specified document set;
A relationship extracting step of extracting a relationship between documents based on the similarity evaluated by the similarity evaluation means;
A centrality determination step of calculating the centrality of the document as an index indicating the high degree of relationship between the document and a document other than the document based on the relationship between the documents extracted by the relationship extraction unit;
Based on the relation between documents obtained by the relation extracting means and the centrality of each document, the relation between documents is expressed by two-dimensional coordinates, and the centrality is expressed by the third-dimensional coordinates relative to the two-dimensional coordinates. And a graph structure construction step for expressing the document set with a three-dimensional graph structure;
A vertex node extracting step of extracting, as a vertex node, a document node having a maximum centrality score in the document set in the obtained graph structure;
A document node group composed of the extracted vertex node and one or more document nodes connected to the vertex node and having a centrality score lower than the centrality score of the vertex node and not minimal and mountain-like nodes specifying step of specifying a mountain-shaped nodes a,
A label indicating that the node serves as a topic word of the document set is given to the extracted vertex node , and the node group is added to the identified mountain node group. A labeling step for providing a label indicating that the document is a set of documents having relevance to a topic word ;
A document node indicating a vertex node labeled as the topic word, and a document node group indicating a mountain node group labeled as a document set having a relationship with the topic word An information output step for visualizing and outputting;
A document set analysis method characterized by comprising: A document set analysis program characterized in that the document set analysis method according to claim 2 is described as a computer program executable by a computer. 3. A recording medium, wherein the document set analysis method according to claim 2 is described as a computer program executable by a computer, and the computer program is recorded.

Images