System and method for thematically grouping documents into clusters

• US 8,015,188 B2
• Filed: 10/04/2010
• Issued: 09/06/2011
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Kawai, Kenji, Gallivan, Dan
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US12/897,710
• Publication Number:
  US 20110022597A1
• Time in Patent Office: 337 Days
• Field of Search: 707/738, 707/750, 707/777
• US Class Current: 707/738
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for thematically grouping documents into clusters is provided. Concepts are extracted from a plurality of documents. The concepts include nouns or noun phrases. A number of occurrences for each concept are determined within each document. A bounded range is applied to the concepts and a subset of the concepts is selected by removing the concepts that fall outside the bounded range. The bounded range includes upper edge conditions and lower edge conditions. Themes are generated from the subset of concepts by identifying two or more concepts with common semantic meaning. Clusters of the documents are generated based on the themes.

Claims

1. A system for thematically grouping documents into clusters, comprising:

an extraction module to extract from a plurality of documents, concepts comprising at least one of nouns and noun phrases;

a frequency determination module to determine a number of occurrences for each concept within each document;

a threshold module to select the documents having the concepts with the occurrences that satisfy a bounded range comprising upper edge conditions and lower edge conditions;

a theme generator module to generate themes for the selected documents from the subset of concepts by identifying two or more concepts with common semantic meaning; and

a cluster module to generate clusters of the selected documents based on the themes; and

a processor to execute the modules.

2. A system according to claim 1, further comprising:

a document module to remove duplicate documents from the clusters.

3. A system according to claim 2, further comprising:

a reclustering module to recluster the remaining documents in the clusters.

4. A system according to claim 1, wherein the clusters each comprise documents with related themes.

5. A system according to claim 1, further comprising:

a total occurrence module to determine total occurrences for each concept by totaling the occurrences for that concept across all the documents; and

a lexicon to map the concepts against the total occurrences.

6. A system according to claim 1, further comprising:

a graph module to generate a histogram for each document comprising the concepts extracted from that document and the concept occurrences, wherein the concepts are mapped in order of decreasing frequency to generate a curve representative of semantic content for that document.

7. A system according to claim 1, further comprising:

a document module to determine a number of the documents that each include a common concept; and

a graph module to generate a corpus graph of the number of documents and common concepts.

8. A system according to claim 1, further comprising:

a calculation module to determine inner products for at least one document based on the occurrences for one or more of the concepts in that document and a cluster concept weighting for the same concept in at least one of the clusters; and

a document module to identify documents having the smallest inner products as most relevant to the theme represented by the at least one cluster.

9. A system according to claim 1, further comprising:

a database record for each concept comprising a concept identifier, string, and occurrence frequency.

10. A system according to claim 1, wherein the documents comprise at least one of electronic messages, word processing documents, and hypertext documents.

11. A method for thematically grouping documents into clusters, comprising the steps of:

extracting from a plurality of documents, concepts comprising at least one of nouns and noun phrases;

determining a number of occurrences for each concept within each document;

selecting the documents having the concepts with the occurrences that satisfy a bounded range comprising upper edge conditions and lower edge conditions;

generating themes for the selected documents from the subset of concepts by identifying two or more concepts with common semantic meaning; and

generating clusters of the selected documents based on the themes,

wherein the steps are performed by a suitably programmed computer.

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

removing duplicate documents from the clusters.

13. A method according to claim 12, further comprising:

reclustering the remaining documents in the clusters.

14. A method according to claim 11, wherein the clusters each comprise documents with related themes.

15. A method according to claim 11, further comprising:

determining total occurrences for each concept by totaling the occurrences for that concept across all the documents; and

mapping the concepts against the total occurrences via a lexicon.

16. A method according to claim 11, further comprising:

generating a histogram for each document comprising the concepts extracted from that document and the concept occurrences, wherein the concepts are mapped in order of decreasing frequency to generate a curve representative of semantic content for that document.

17. A method according to claim 11, further comprising:

determining a number of the documents that each include a common concept; and

generating a corpus graph of the number of documents and common concepts.

18. A method according to claim 11, further comprising:

determining inner products for at least one document based on the occurrences for one or more of the concepts in that document and a cluster concept weighting for the same concept in at least one of the clusters; and

identifying documents having the smallest inner products as most relevant to the theme represented by the at least one cluster.

19. A method according to claim 11, further comprising:

generating a database record for each concept comprising a concept identifier, string, and occurrence frequency.

20. A method according to claim 11, wherein the documents comprise at least one of electronic messages, word processing documents, and hypertext documents.