Computer-Implemented System And Method For Generating Document Groupings For Display

• US 20160078126A1
• Filed: 11/23/2015
• Published: 03/17/2016
• 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
• Granted Patent: US 9,619,551 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 computer-implemented system and method for generating document groupings is provided. A lexicon of terms extracted from a set of documents is generated. The lexicon includes a frequency of each extracted term within each document in the set. Concepts each having two or more of the extracted terms are generated. A subset of the documents in the set is selected based on the term frequencies. The subset of documents is grouped into clusters based on the concepts. A similarity of each document cluster is calculated with one or more documents based on a distance by summing the frequency of each term in that document and a weight of the cluster for each of the terms. The weights are updated until a rate of change for each cluster becomes constant.

Claims

1. A computer-implemented system for generating document groupings, comprising:

a lexicon of terms extracted from a set of documents and comprising a frequency of each extracted term within each document;

concepts each comprising two or more of the extracted terms;

a selection module to select a subset of the documents in the set based on the term frequencies;

a grouping module to group the subset of documents into clusters based on the concepts;

a similarity module to calculate a similarity of each document cluster with at least one document based on a distance by summing the frequency of each term in that document and a weight of the cluster for each of the terms; and

an update module to update the weights until a rate of change for each cluster becomes constant.

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

an identification module to identify one or more of the clusters as meaningful by defining a variance and selecting those clusters having one or more documents with inner products that fall within the variance as meaningful; and

a display to present those documents identified as meaningful.

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

a representation module to represent semantic content of each document by mapping the terms in that document in order of decreasing frequency.

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

a representation module to represent latent semantics of the document set by mapping each term in the document set against a total frequency occurrence, wherein the total frequency occurrence is calculated as a sum of the term frequencies within each document in the set.

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

a parameter selection module to select a median value and edge conditions for the total frequency occurrences of the terms; and

a document subset module to generate the subset of documents from those documents in the set that satisfy the edge conditions.

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

a further document subset module to re-center the median value and to generate a different subset of documents for grouping.

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

a determination module to set the edge conditions based on a size of the documents.

8. A system according to claim 7, wherein larger documents have tighter edge conditions than shorter documents.

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

a calculation module to calculate the distance using the following equation;

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

a change module to calculate the rate of change by determining a first derivative of the inner products over successive iterations.

11. A computer-implemented method for generating document groupings, comprising:

generating a lexicon of terms extracted from a set of documents and comprising a frequency of each extracted term within each document;

generating concepts each comprising two or more of the extracted terms;

selecting a subset of the documents in the set based on the term frequencies;

grouping the subset of documents into clusters based on the concepts;

calculating a similarity of each document cluster with at least one document based on a distance by summing the frequency of each term in that document and a weight of the cluster for each of the terms; and

updating the weights until a rate of change for each cluster becomes constant.

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

identifying one or more of the clusters as meaningful, comprising;

defining a variance; and

selecting those clusters having one or more documents with inner products that fall within the variance as meaningful; and

displaying those documents identified as meaningful.

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

representing semantic content of each document by mapping the terms in that document in order of decreasing frequency.

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

representing latent semantics of the document set by mapping each term in the document set against a total frequency occurrence, wherein the total frequency occurrence is calculated as a sum of the term frequencies within each document in the set.

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

selecting a median value and edge conditions for the total frequency occurrences of the terms; and

generating the subset of documents from those documents in the set that satisfy the edge conditions.

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

re-centering the median value; and

generating a different subset of documents for grouping.

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

setting the edge conditions based on a size of the documents.

18. A method according to claim 17, wherein larger documents have tighter edge conditions than shorter documents.

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

calculating the distance using the following equation;

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

calculating the rate of change by determining a first derivative of the inner products over successive iterations.