Text mining device, method thereof, and program

• US 8,612,207 B2
• Filed: 03/17/2005
• Issued: 12/17/2013
• Est. Priority Date: 03/18/2004
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Sakao, Yousuke, Satoh, Kenji, Akamine, Susumu
• Primary Examiner(s): COLUCCI, MICHAEL C
• Application Number:
  US10/593,375
• Publication Number:
  US 20070233458A1
• Time in Patent Office: 3,197 Days
• Field of Search: 704/2, 704/9, 704/260, 704/1, 704/6, 704/10, 704/235, 704/270, 704/7, 704/246, 704/251, 704/255, 704/257, 714/37, 715/234, 715/260, 715/273, 709/206, 707/741
• US Class Current: 704/9
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Language analysis means 21 analyzes texts read from a text DB 11, and generates a sentence structure as the analysis result. Similar-structure generation adjustment means 25 generates, from an input of an input device, a determination item for determining whether or not the structures are identical every type of differences between the sentence structures. Similar-structure determination adjustment means 26 generates, from an input of the input device 6, a determination item for determining whether or not the difference between attribute values is ignored every type of attribute values. Similar-structure generating means 22 generates a similar structure of a partial structure forming the sentence structure obtained by language analysis means 21 in accordance with the determination item from the similar-structure generation adjustment means 25, and sets the generated similar structure as an equivalent class of the partial structure on the generation source. Frequent-similar-pattern detection means 24 ignores the attribute value in accordance with the determination item given from the similar-structure determination adjustment means 26, detects the frequent pattern on the basis of a set of equivalent classes from the similar-structure generating means 22, and outputs the frequent pattern to an output device 3.

Claims

1. A text mining apparatus comprising:

means for generating a sentence structure from an input document, the sentence structure representing a dependency among words;

means for generating a similar structure of patterns having a similar meaning of a partial structure of the sentence structure by performing predetermined conversion operation, including at least change in connection of branches in a graph structure, of the partial structure; and

means for determining the patterns having the similar meaning as the identical pattern and detecting the patterns,

wherein the means for generating the similar structure comprises;

means for performing parallel modification of the sentence structure, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one, said means for performing parallel modification of the sentence structure generating the similar structure;

means for generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

means for performing non-directional branching of a directional branch of the sentence structure and the plurality of new partial structures to produce new similar structures;

means for replacing a synonym in the sentence structure and the plurality of new partial structures by referring to a synonym dictionary to produce new similar structures; and

means for performing non-ordering of ordering trees of the sentence structure and the plurality of new partial structures to produce new similar structures, and wherein

the means for generating the similar structure uses the new similar structures as an equivalent class of the plurality of new partial structures of the sentence structure.

2. A text mining apparatus according to claim 1, further comprising:

a storage unit that stores a set of documents as a text mining object; and

an analyzing unit that inputs and analyzes the document of the storage unit and obtains the sentence structure,

wherein the analyzing unit analyzes the document, and generates the sentence structure containing a clause having a node and indicating at least a dependency as a directional branch from the node on a modifier to the node on a modifiee.

3. A text mining apparatus comprising:

a storage unit that stores a set of documents as a text mining object;

an analyzing unit that reads and analyzes the document from the storage unit and obtains a sentence structure representing a dependency among words;

a similar-structure generating unit that performs predetermined modification operation, including at least change in connection of branches in a graph structure, of the partial structure of the sentence structure obtained by the analysis of the analyzing unit, and generates a similar structure of patterns having a similar meaning; and

a pattern detecting unit that uses the similar structure generated by the similar-structure generating unit as an equivalent class of the partial structure on the generation source, and detects the pattern,

wherein the similar-structure generating unit comprises;

means for performing parallel modification of the sentence structure, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one, said means for performing parallel modification of the sentence structure generating the similar structure;

means for generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

means for performing non-directional branching of a directional branch of the sentence structure and the plurality of new partial structures to produce new similar structures;

means for replacing a synonym in the sentence structure and the plurality of new partial structures by referring to a synonym dictionary to produce new similar structures; and

means for performing non-ordering of ordering trees in the sentence structure and the plurality of new partial structures to produce new similar structures , and wherein

the similar-structure generating unit generates the new similar structures of the sentence structure and sets the new similar structures as an equivalent class of the plurality of new partial structures of the sentence structure.

4. A text mining apparatus according to claim 3, wherein the pattern detecting unit uses the new similar structures as the equivalent class of the plurality of new partial structures on the generation source, and detects the pattern.

5. A text mining apparatus according to claim 3, further comprising:

means for adjusting the operation so that a user determines how similar patterns are identical and detecting the pattern.

6. A text mining apparatus comprising:

a storage unit that stores a set of documents as a text mining object;

an analyzing unit that reads and analyzes the document from the storage unit and obtains a sentence structure representing a dependency among words;

a similar-structure generation adjustment unit that generates a first determination item for determining, from a user input, whether or not the structures are identical ones for every type of differences between the sentence structures;

a similar-structure determination adjustment unit that generates a second determination item for determining, from a user input, whether or not the structures are identical ones for every type of differences between attribute values;

a similar-structure generating unit that performs predetermined conversion operation of a partial structure of the sentence structure obtained by the analyzing unit in accordance with the first determination item generated by the similar-structure generation adjustment unit and generates similar structures having a similar meaning of the partial structure; and

a similar-pattern detecting unit that uses the similar structure generated by the similar-structure generating unit as an equivalent class of the partial structure on the generation source and detects the frequent pattern by ignoring the difference between the attribute values in accordance with the second determination item of the similar-structure determination adjustment unit,

wherein the similar-structure generating unit comprises;

means for performing parallel modification of the sentence structure when the first determination item determines the parallel modification, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one, said means for performing parallel modification of the sentence structure generating the similar structure;

means for generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

means for performing non-directional branching of a directional branch of the sentence structure and the plurality of new partial structures when the first determination item determines the non-directional branching of the directional branch to produce new similar structures;

means for replacing a synonym in the sentence structure and the plurality of new partial structures by referring to a synonym dictionary when the first determination item includes replacement of the synonym to produce new similar structures; and

means for performing non-ordering of ordering trees of the sentence structure and the plurality of new partial structures when the first determination item determines the non-ordering of the ordering trees to produce new similar structures, and wherein

the similar-structure generating unit generates the new similar structures of the sentence structure and sets the new similar structures as the equivalent class of the plurality of new partial structures of the sentence structure.

7. A text mining apparatus according to claim 6, wherein the analyzing unit analyzes the document, and generates the sentence structure containing a clause having a node and indicating at least a dependency as a directional branch from the node on a modifier to the node on a modifiee determination, and

the attribute value includes the surface case and/or the information about the attached word, added to the sentence structure.

8. A text mining apparatus according to claim 6, wherein the similar-pattern detecting unit detects a frequent similar pattern.

9. A text mining method comprising:

a step of generating, using a computer, a sentence structure from an input document, the sentence structure representing a dependency among words;

a step of generating, using the computer, a similar structure of patterns having a similar meaning of a partial structure of the sentence structure by performing predetermined conversion operation, including at least change in connection of branches in a graph structure, of the partial structure; and

a step of determining the patterns having the similar meaning as the identical pattern and detecting the patterns,

wherein the step of generating the similar structure comprises;

a step of performing parallel modification of the sentence structure, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one, said step of performing parallel modification of the sentence structure generating the similar structure;

a step of generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

a step of performing non-directional branching of a directional branch of the sentence structure and the plurality of new partial structures to produce new similar structures;

a step of replacing a synonym in the sentence structure and the plurality of new partial structures by referring to a synonym dictionary to produce new similar structures; and

a step of performing non-ordering of ordering trees in the sentence structure and the plurality of new partial structures to produce new similar structures, and thereby the step of generating the similar structure setting new similar structures as an equivalent class of the plurality of new partial structures.

10. A text mining method according to claim 9, further comprising:

a step of inputting and analyzing the document from a storage unit that stores a set of documents as a text mining object and generating the sentence structure containing a clause having a node and indicating at least a dependency as a directional branch from the node on a modifier to the node on a modifiee.

11. A text mining method comprising:

a step of analyzing a document from a storage unit that stores a set of documents as a text mining object and obtaining a sentence structure representing a dependency among words;

a step of performing predetermined modification operation, including at least change in connection of branches in a graph structure, of a partial structure of the sentence structure and generating, using a computer, a similar structure having patterns with a similar meaning;

a step of using the generated similar structures as an equivalent class of the partial structure on the generation source and detecting the pattern,

wherein the step of generating the similar structure comprises;

a step of performing parallel modification of the sentence structure, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one said step of performing parallel modification of the sentence structure generating the similar structure;

a step of generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

a step of performing non-directional branching of the directional branch of the sentence structure and the plurality of new partial structures to produce new similar structures;

a step of replacing a synonym in the sentence structure and the plurality of new partial structures by referring to a synonym dictionary to produce new similar structures; and

a step of performing non-ordering of ordering trees in the sentence structure and the plurality of new partial structures to produce new similar structures, and thereby the step of generating the similar structure generating the new similar structures of the sentence structure and setting the new similar structures as an equivalent class of the plurality of new partial structures.

12. A text mining method according to claim 11, further comprising:

a step of using the new similar structures as an equivalent class of the plurality of new partial structures on the generation source and detecting a frequent pattern.

13. A text mining method according to claim 11, further comprising:

a step of adjusting the operation so that a user determines how similar patterns are identical and detects the pattern.

14. A text mining method comprising:

a step of analyzing a document from a storage unit that stores a set of documents as a text mining object and obtaining a sentence structure representing a dependency among words;

a step of generating, from a user input, a first determination item for determining whether or not the structures are identical ones for every type of differences between sentence structures;

a step of generating, from a user input, a second determination item for determining whether or not the structures are identical ones for every type of differences between attribute values;

a step of performing predetermined modification operation of the partial structure of the sentence structure obtained by the analyzing unit and generating, using a computer, a similar structure having a similar meaning of the partial structure in accordance with the generated first determination item; and

a step of using the generated similar structure as an equivalent class of the partial structure on the generation source and detecting the pattern by ignoring the difference between the attribute values in accordance with the second determination item,

wherein the step of generating the similar structure comprises;

a step of performing parallel modification of the sentence structure when the first determination item determines the parallel modification, the parallel modification being structure modification including new branch generation for a particular one of nodes corresponding to the words put in a parallel relationship in the sentence structure so that the particular one is connected to each node connected by a branch from the node put in the parallel relationship for the particular one, said step of performing parallel modification of the sentence structure generating the similar structure;

a step of generating a plurality of new partial structures of the sentence structure from the partial structure and the similar structure;

a step of performing non-directional branching of a directional branch of the sentence structure and the plurality of new partial structures when the first determination item determines the non-directional branching of the directional branch to produce new similar structures;

a step of replacing a synonym of the sentence structure and the plurality of new partial structures by referring to a synonym dictionary when the first determination item determines the synonym replacement to produce new similar structures; and

a step of performing non-directional branching of ordering trees of the sentence structure and the plurality of new partial structures when the first determination item determines the non-directional branching of the ordering trees to produce new similar structures, and thereby the step of generating the similar structure generating the new similar structures of the sentence structure and setting the new similar structures as an equivalent class of the plurality of new partial structures.

15. A text mining method according to claim 14, wherein the step of obtaining the sentence structure generates the sentence structure containing a clause having a node and indicating at least a dependency as a directional branch from the node on a modifier to the node on a modifiee, and

the attribute value includes a surface case and/or the information about the attached word, added to the sentence structure.

16. A text mining method according to claim 14, wherein the frequent similar pattern is detected.