Computer-implemented system and method for generating a display of document clusters

• US 8,650,190 B2
• Filed: 03/14/2013
• Issued: 02/11/2014
• 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: Gallivan, Dan
• Primary Examiner(s): Lewis, Cheryl
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US13/831,565
• Publication Number:
  US 20130212098A1
• Time in Patent Office: 334 Days
• Field of Search: None
• US Class Current: 707/731
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• 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/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computer-implemented system and method for generating a display of document clusters is described. Clusters of documents are presented in a multi-dimensional concept space. At least one document is selected from a collection of documents to be clusters. An angle θ of the document relative to a common origin of the multi-dimensional concept space is computed. The selected document is compared with each of the clusters. An angle σ from the common origin is determined for each cluster. A difference between the angle θ for the document and the angle σ for the cluster is determined. The difference is compared to the variance, and a new cluster is created when the difference exceeds the variance for all the clusters.

Claims

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

clusters of documents in a multi-dimensional concept space;

a selection module select at least one document from a collection of documents to be clustered;

a document angle module to compute an angle θ

of the document relative to a common origin of the multi-dimensional concept space;

a comparison to compare the selected document with each of the clusters, comprising;

a cluster angle module to calculate for each cluster, an angle σ

from the common origin

a similarity module to determine a difference between the angle θ

of the document and the angle σ

of the cluster; and

a variance determining module to apply a variance the difference; and

a cluster module to create a new cluster when the difference exceeds the variance for all the clusters.

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

a display placement module to place the selected document into one of the clusters when the difference between the selected document and that cluster is at least one of greater than or equal to the variance.

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

a cluster finalizing module to finalize one or more of the clusters comprising at least one of merging two or more of the clusters into a single cluster, splitting at least one of the clusters into two or more clusters, and removing those clusters that are outliers in relation to the remaining clusters.

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

a concept module to build a concept space over the document collection based on the clusters and any newly generated clusters.

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

a cluster formation module to form the clusters of documents in the multi-dimensional concept space by creating an initial cluster and adding additional clusters via a k-means clustering technique.

6. A system according to claim 1, wherein the documents are iteratively compared with the collection to the clusters.

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

a display module to place one or more of the clusters into the multi-dimensional concept space around the common origin.

8. A system according to claim 1, wherein the documents within each cluster share related terms and phrases.

9. A system according to claim 1, wherein the variance is defined as an upper bound on a distance between the documents and the clusters.

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

an update module to recalculate the angle σ

for each cluster when one of the documents is added or one of the documents is removed.

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

presenting clusters of documents in a multi-dimensional concept space and selecting at least one document from a collection of documents to be clustered;

computing an angle θ

of the document relative to a common origin of the multi-dimensional concept space;

comparing the selected document with each of the clusters, comprising;

calculating for each cluster, an angle σ

from the common origin;

determining a difference between the angle θ

for the document and the angle σ

for the cluster; and

comparing the difference to a variance; and

creating a new cluster when the difference exceeds the variance for all the clusters.

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

placing the selected document into one or more of the clusters when the difference between the selected document and that cluster is at least one of greater than or equal to the variance.

13. A method according to claim 11, further comprising at least one of:

merging two or more of the clusters into a single cluster;

splitting at least one of the clusters into two or more clusters; and

removing those clusters that are outliers in relation to the remaining clusters.

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

building a concept space over the document collection based on the clusters and any newly generated clusters.

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

forming the clusters of documents in the multi-dimensional concept space, comprising;

creating an initial cluster; and

adding additional clusters via a k-means clustering technique.

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

iteratively comparing each document in the collection to the clusters.

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

placing one or more of the clusters into the multi-dimensional concept space around the common origin.

18. A method according to claim 11, wherein the documents within each cluster share related terms and phrases.

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

defining the variance as an upper bound on a distance between the documents and the clusters.

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

recalculating the angle σ

for each cluster when one of the documents is added or one of the documents is removed.