Text analysis techniques

• US 20040059736A1
• Filed: 09/23/2002
• Published: 03/25/2004
• Est. Priority Date: 09/23/2002
• Status: Active Grant

• Current Assignee: Battelle Memorial Institute
• Original Assignee: Battelle Memorial Institute
• Inventors: Naucarrow, Catherine, Nakamura, Grant C., Turner, Alan E., Hetzler, Elizabeth G., Tanasse, Theodore E., Havre, Susan L., MacGregor, Margaret, Willse, Alan R., Hope, Lawrence L.
• Granted Patent: US 7,158,983 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

One embodiment of the present invention includes means determining a concept representation for a set of text documents based on partial order analysis and modifying this representation if it is determined to be unidentifiable. Furthermore, the embodiment includes means for labeling the representation, mapping documents to it to provide a corresponding document representation, generating a number of document signatures each of a different type, and performing several data processing applications each with a different one of the document signatures of differing types.

Claims

1. A method, comprising:

selecting a set of text documents;

selecting a number of terms included in the set;

establishing a multidimensional document space with a computer system as a function of the terms;

performing a bump hunting procedure with the computer system to identify a number of document space features, the features each corresponding to a composition of two or more concepts of the documents; and

deconvolving the features with the computer system to separately identify the concepts.

2. The method of claim 1, which includes providing a concept representation corresponding to an acyclic graph with a number of nodes each corresponding to one of the concepts and different levels to represent related concepts of differing degrees of specificity.

3. The method of claim 2, which includes identifying a number of different multilevel groups in accordance with a mathematically determined degree of desired fit of the different multilevel groups.

4. The method of claim 1, which includes determining the multidimensional document space in accordance with frequency of each of the terms in each of the text documents.

5. The method of claim 1, which includes determining a plurality of different signature vectors from the concepts for different text processing applications.

6. The method of claim 1, wherein said deconvolving includes performing a latent variable analysis as a function of the features and the terms to identify the concepts.

7. The method of claim 6, wherein, said deconvolving includes:

identifying one of a number of first level concepts of the text documents by determining each of the terms that is associated with one of the features; and

establishing one of several second level concepts of the text documents by identifying at least one of the terms found in each member of a subset of the first level concepts.

8. The method of claim 7, which includes:

providing a concept representation of the text documents, the representation including the first level concepts and the second level concepts with the subset of the first level concepts being subordinate to the one of the second level concepts;

testing identifiability of the concept representation; and

providing a modified concept representation in response to said testing if the concept representation is nonidentifiable.

9. A method, comprising:

performing a routine with a computer system, including;

extracting terminological features from a set of text documents;

establishing a representation of a number of concepts of the text documents as a function of the features, the representation corresponding to an arrangement of several levels to indicate different degrees of concept specificity; and

identifying a number of different related groups of the concepts, the groups each being mathmatically determined as a function of a degree of separateness from the concept representation.

10. The method of claim 9, wherein the groups are determined with an iterative gradient descent procedure.

11. The method of claim 9, wherein the degree of separateness is determined relative to a likelihood function for the concept representation.

12. The method of claim 9, which includes providing a visualization of the concept representation in the form of an acyclic directed graph, the graph including a number of nodes each corresponding to one of the concepts, the nodes being selectively linked to indicate relationships between the concepts.

13. The method of claim 9, wherein the groups each correspond to a different facet of the concept representation, and which includes preparing a number of different document signatures each from a different one of the groupings.

14. A method, comprising:

performing a routine with a computer system, including;

extracting terminological features from a set of text documents;

establishing a representation of a number of concepts of the text documents as a function of the terminological features, the representation hierarchically indicating different degrees of specificity among related members of the concepts and corresponding to an acyclic graph organization;

determining the representation is nonidentifiable;

in response to said determining, constraining one or more processing parameters of the routine; and

providing a modified concept representation after said constraining, the modified concept representation being identifiable.

15. The method of claim 14, wherein said constraining one or more processing parameters of the routine includes limiting the modified concept representation to a quantity of levels.

16. The method of claim 14, wherein said constraining one or more processing parameters of the routine includes limiting the modified concept representation to a strict hierarchy form in which each one of the concepts is subordinate to at most one other of the concepts.

17. The method of claim 14, wherein said constraining one or more processing parameters of the routine includes mapping the representation into a number of multilevel subgroupings each corresponding to an acyclic graph arrangement.

18. The method of claim 14, wherein said extracting is performed by executing a bump hunting procedure and the concepts are determined by executing a deconvolution procedure with respect to the features.

19. A method, comprising:

performing a routine with a computer system, including;

extracting terminological features from a set of text documents;

establishing a representation of a number of concepts of the text documents as a function of the terminological features, the representation hierarchically indicating different degrees of specificity among related ones of the concepts in correspondence to different levels of an acyclic graph organization;

evaluating a selected document relative to the representation; and

generating a number of different document signatures for the selected document with the representation.

20. The method of claim 19, wherein said extracting is performed by executing a bump hunting procedure and the concepts are determined by executing a deconvolution procedure with respect to the features.

21. The method of claim 19, which includes identifying several different group of related concepts, the groups each corresponding to several of the different levels of the representation.

22. The method of claim 21, wherein said generating includes preparing each of the different document signatures in accordance with a different one of the groups.

23. The method of claim 19, wherein said generating includes preparing each of the different documents signatures for a different text data processing application.

24. The method of claim 23, wherein the different text data application is one or more of the group consisting of event detection, document summarization, document clustering, document filtering, querying, and synonym analysis.

25. The method of claim 19, wherein:

said extracting includes determining the terminological features as a function of a set of terms contained in the set of text documents; and

said evaluating includes mapping the selected document to the concept representation as a function of any terms of the selected document contained in the set of terms.

26. A method, comprising:

selecting a set of text documents;

representing the documents with a number of terms;

identifying a number of multiterm features of the text documents as a function of frequency of each of the terms in each of the documents;

relating the multiterm features and the terms with one or more data structures corresponding to a sparse matrix;

performing a latent variable analysis as a function of the terms to determine a number of concepts of the text documents from the one or more data structures; and

providing a concept representation corresponding to a multilevel acyclic graph organization in which each node of the graph corresponds to one of the concepts.

27. The method of claim 26, wherein the latent variable analysis includes deconvolving the features to determine the concepts.

28. The method of claim 26, wherein the latent variable analysis includes:

identifying one of the concepts in a first level of the concept representation by determining each of the terms that is associated with one of the features; and

establishing one of the concepts in a second level of the concept representation by identifying at least one of the terms found in each member of a subset of the concepts in the first level.

29. The method of claim 28, wherein the concept representation indicates the one of the concepts in the first level is related and subordinate to the one of the concepts in the second level.

30. The method of claim 26, which includes:

determining a number of related subsets of the concepts, the subsets each spanning several levels of the concept representation and each corresponding to a different facet of the representation;

testing identifiability of the concept representation; and

providing several different document signatures from the concept representation.

31. A method, comprising:

performing a routine with a computer system, including;

determining a number of multiterm features of a set of text documents as a function of a number of terms included in the set of text documents;

identifying one of a number of first level concepts of the text documents by determining each of the terms that is identified with one of the features;

establishing one of several second level concepts of the text documents by identifying one of the terms found in each member of a subset of the first level concepts; and

providing a concept representation of the text documents, the representation including the first level concepts and the second level concepts with the subset of the first level concepts being subordinate to the one of the second level concepts.

32. The method of claim 31, which includes establishing one of several third level concepts of the text documents by identifying at least one of the terms found in each member of a subset of the second level concepts.

33. The method of claim 32, wherein the subset of the second level concepts are subordinate to the one of the third level concepts in the concept representation.

34. The method of claim 31, which includes labeling the one of the first level concepts with each of the terms this is only identified with the one of the features.

35. The method of claim 31, wherein the subset of first level concepts includes the one of the first level concepts.

36. The method of claim 35, wherein said establishing includes determining a number of other subsets each including the one of the first level concepts by correspondingly identifying other of the terms that are included in each member of a respective one of the other subsets.

38. The method of claim 36, wherein said determining includes executing a bump hunting procedure to determine the multiterm features.

39. The method of claim 36, which includes determining a number of different document signatures from the concept representation with the computer system.

40. The method of claim 36, which includes determining a number of related subsets of the concepts, the subsets each spanning several levels of the concept representation and each corresponding to a different representation facet.

37. The method of 36, which includes labeling the one of the second level concepts with the one of the terms and the other of the terms.

41. A method, comprising:

identifying a number of events;

providing a visualization of the events with a computer system, the visualization including a number of visualization objects each representing a different one of the events;

positioning each of the visualization objects along a first axis to indicate timing of each of the events relative to one another with a corresponding initiation time and a corresponding termination time of each of the events being represented by an initiation point and termination point of each of the visualization objects along the first axis; and

dimensioning each of the visualization objects between the corresponding initiation point and the corresponding termination point along the first axis to indicate event duration and along a second axis to indicate relative strength of the different one of the events.

42. The method of claim 41, wherein said identifying includes relating each of the events to a combination of terms.

43. The method of claim 42, wherein the visualization objects are each comprised of a number of components, the components each corresponding to one of the terms of the combination for the respective one of the visualization objects.

44. The method of claim 43, wherein the components of the respective one of the visualization objects are each differently colored in the visualization.

45. The method of claim 41, which includes providing graphic user interfacing with the visualization to select a time window for display of event details.

46. The method of claim 45, wherein the event details include a display of the combination of terms for each of the visualization objects included in the time window.

47. The method of claim 41, wherein the events are determined from a set of text documents.

48. The method of claim 47, wherein the events are determined with a concept representation of text documents.

49. A method, comprising:

providing a set of text documents;

evaluating time variation of a number of terms included in the documents;

generating a number of clusters corresponding to the documents with a computer system as a function of the terms; and

identifying a number of events as a function of a time variation of the clusters.

50. The method of claim 49, wherein said evaluating includes:

determining presence of a word in the documents for each of several different segments of a time period; and

establishing a degree of time variation of the word as a function of the one of the segments with a frequency of the word greater than other of the segments and a quantity of the documents including the word.

51. The method of claim 49, wherein said generating is performed with the terms having a selected level of time variation.

52. The method of claim 49, wherein said generating adjusts term weighting in accordance with said evaluating.

53. The method of claim 49, which includes:

displaying the events in a visualization including a number of visualization objects each representative of a different one of the events;

positioning each of the visualization objects along a first axis to indicate timing of each of the events relative to one another with a corresponding initiation time and a corresponding termination time of each of the events being represented by an initiation point and termination point of each of the visualization objects along the first axis; and

dimensioning each of the visualization objects between the corresponding initiation point and the corresponding termination point along the first axis to indicate event duration and along a second axis to indicate relative strength of the different one of the events.

54. The method of claim 49, wherein said generating is performed based on document signatures determined from a concept representation.

55. A method, comprising:

providing a number of textual documents arranged relative to a period of time;

identifying a feature with a time varying distribution among the documents;

evaluating presence of the feature for each of several different segments of the time period; and

detecting an event as a function of the one of the segments with a frequency of the feature greater than other of the segments and a quantity of the documents corresponding to the feature.

56. The method of claim 55, wherein the feature is a term.

57. The method of claim 55, wherein the feature is a document cluster.

58. The method of claim 55, which includes identifying a number of other events.

59. The method of claim 55, which includes providing an event visualization.

60. The method of claim 55, which includes preparing a document signature from a concept representation for event detection processing.

61. A method, comprising:

selecting a set of text documents;

designating several different dimensions of the documents;

characterizing each of the dimensions with a corresponding set of words;

for each of the dimensions, performing a clustering analysis of the documents based on the corresponding set of words; and

visualizing the clustering analysis for each of the dimensions.

62. The method of claim 61, wherein the different dimensions are selected based on several different document signatures representative of each of the documents.

63. The method of claim 61, wherein said selecting includes receiving input regarding the dimensions from an operator.

64. The method of claim 61, which includes:

pairing a number of the documents to provide a number of document pairs;

for each of the document pairs, comparing a first pair member to a second pair member; and

determining a degree of similarity based on said comparing for each of the document pairs.

65. A method, comprising:

in response to an input of one or more words in a computer system, providing a list of words with the computer system as a function of a number of context vectors for a set of text documents and the one or more words;

receiving another input responsive to the list;

reweighting a number of different entries corresponding to the context vectors with the computer system based on the second input;

providing an output of related words with the computer system based said reweighting; and

repeating said receiving, said reweighting, and said providing with the computer system.

66. The method of claim 65, which includes locating one or more of the text documents based on the related words after said repeating.

67. The method of claim 65, wherein said reweighting includes determining a profile of words of interest based on cooccurrence and variance.

68. The method of claim 65, wherein said reweighting includes applying a statistical discrimination test.

69. The method of claim 65, wherein the context vectors are comprised of different types, at least one of the types being provided as a document signature based on a concept representation.

70. The method of claim 65, which includes generating the context vectors based on a cooccurrence measure.

71. An apparatus, comprising:

means for determining a concept representation for a set of text documents based on partial order analysis;

means for modifying the concept representation if it is determined to be unidentifiable;

means for labeling the concept representation;

means for mapping documents to the concept representation to provide a corresponding document representation;

means for generating several document signature types from the document representation; and

means for performing a number of data processing applications each with a document signature of a different one of the document signature types determine from the document representation.

72. The apparatus of claim 71, wherein the different applications include at least one of event detection, event visualization, term relationship discovery;

and clustering.

73. An apparatus, comprising:

a device carrying logic executable with a computer system to extract terminological features from a set of text documents;

establish a representation of a number of concepts of the text documents as a function of the terminological features, the representation hierarchically indicating different degrees of specificity among related ones of the concepts in correspondence to different levels of an acyclic graph organization;

evaluate a selected document relative to the representation; and

generate a number of different document signatures for the selected document with the representation.

74. The apparatus of claim 73, wherein the device includes one or more components of a computer network.

75. The apparatus of claim 73, wherein the device includes a memory device accessible by the computer system.

76. The apparatus of claim 75, wherein the memory device is in the form of a removable disk.