SYSTEM AND METHOD FOR GROUPING THEMATICALLY-RELATED CLUSTERS INTO A TWO-DIMENSIONAL VISUAL DISPLAY SPACE

• US 20090046100A1
• Filed: 10/20/2008
• Published: 02/19/2009
• Est. Priority Date: 02/13/2004
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: FTI Consulting Technology LLC (FTI Consulting Incorporated)
• Inventors: Evans, Lynne Marie
• Granted Patent: US 7,720,292 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• 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/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Concepts are extracted from content of documents. Clusters each include one or more of the concepts. A theme is identified in each of the clusters and includes at least one such concept within the cluster. Spines of the clusters that share at least one theme in common are formed. The spines having a theme unique from any other spine already placed into a visual display space are placed. Anchor clusters are identified on the placed spines. Spine groups are generated. A similarity of at least one of the spines not placed and each placed spine is evaluated. The unplaced spine is placed at the anchor cluster in the placed spine with the closest similarity. A similarity of at least one of the clusters not selected and each anchor cluster is evaluated. The non-selected cluster is placed proximate to the anchor cluster with the closest similarity. The spine groups are displayed.

Claims

1. A system for grouping thematically-related clusters into a two-dimensional visual display space, comprising:

an extraction module to extract concepts from content of documents stored electronically;

a clustering module to select a set of clusters from a multiplicity of clusters each comprising one or more of the concepts;

a theme generator to identify a theme in each of the clusters that comprises at least one such concept within the cluster;

a spine placement module to form spines of the clusters sharing at least one theme in common;

a comparison module to compare the spines and to place only those spines having a theme unique from any other such spine already placed into a visual display space;

a candidate anchor cluster module to identify candidate anchor clusters on the placed spines that each comprise at least one open edge;

a spine group generator to generate spine groups, comprising;

a spine similarity evaluator to evaluate a similarity of at least one of the spines not placed in the visual display space and each of the placed spines and to place the at least one unplaced spine at the open edge of one of the candidate anchor clusters comprised in the placed spine with the closest similarity; and

a cluster similarity evaluator to evaluate a similarity of at least one of the clusters not selected and each of the candidate anchor clusters comprised in the placed spines and to place the non-selected cluster proximate to the candidate anchor cluster with the closest similarity; and

a display to display the spine groups in the visual display space.

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

a new spine generator to generate a new spine group by selecting a largest cluster on the at least one unplaced spine when the at least one unplaced spine is insufficiently similar with the placed spines.

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

a cluster selection module to select a cluster on the at least one unplaced spine that is most similar to the candidate anchor cluster of the placed spine with the closest similarity; and

a cluster grafting module to graft the selected cluster along a vector defined from a center of the candidate anchor cluster.

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

a criteria module to assign a maximum line criteria to the vector;

an angle module to change an angle of the vector from the center of the candidate anchor cluster when the placement of the at least one unplaced spine exceeds the maximum line criteria; and

the cluster grafting module to graft the selected cluster of the at least one unplaced spine at the candidate anchor cluster of the placed spine along the vector at the changed angle.

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

a cluster placement module to place the non-selected cluster in an area of the visual display space that is separate from the placed spines when the non-selected cluster is insufficiently similar to the candidate anchor clusters.

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

a score module to determine a group concept score vector for each spine group by aggregating the concepts for the common theme.

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

a spine group placement module to place one or more of the spine groups circumferentially about a central shape within a sector having minimum and maximum angles.

8. A system according to claim 7, wherein each placed spine group is sufficiently unique from any other such spine group already placed into the visual display space.

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

a spine group similarity module to determine a similarity of at least one of the spine groups not placed into the visual display space and each of the placed spine groups; and

a spine group selection module to place the unplaced spine group at the central shape at an angle of the placed spine group with the closest similarity.

10. A system according to claim 9, wherein the central shape comprises a circle with a radius calculated in accordance with an equation:

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

a spine group rotation module to rotate the unplaced spine group about the central shape when the unplaced spine group and the placed spine group overlap.

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

a spine group translation module to perform at least one of translating the unplaced spine group outwards and rotating the unplaced spine group in an opposite direction about the central shape when the unplaced spine group exceeds at least one of the minimum and maximum angles.

13. A computer-implemented method for grouping thematically-related clusters into a two-dimensional visual display space, comprising:

extracting concepts from content of documents stored electronically;

selecting a set of clusters from a multiplicity of clusters each comprising one or more of the concepts;

identifying a theme in each of the clusters that comprises at least one such concept within the cluster;

forming spines of the clusters sharing at least one theme in common;

comparing the spines and placing only those spines having a theme unique from any other such spine already placed into a visual display space;

identifying candidate anchor clusters on the placed spines that each comprise at least one open edge;

generating spine groups, comprising;

evaluating a similarity of at least one of the spines not placed in the visual display space and each of the placed spines;

placing the at least one unplaced spine at the open edge of one of the candidate anchor clusters comprised in the placed spine with the closest similarity;

evaluating a similarity of at least one of the clusters not selected and each of the candidate anchor clusters comprised in the placed spines; and

placing the non-selected cluster proximate to the candidate anchor cluster with the closest similarity; and

displaying the spine groups in the visual display space.

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

generating a new spine group by selecting a largest cluster on the at least one unplaced spine when the at least one unplaced spine is insufficiently similar with the placed spines.

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

selecting a cluster on the at least one unplaced spine that is most similar to the candidate anchor cluster of the placed spine with the closest similarity; and

grafting the selected cluster along a vector defined from a center of the candidate anchor cluster.

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

assigning a maximum line criteria to the vector;

changing an angle of the vector from the center of the candidate anchor cluster when the placement of the at least one unplaced spine exceeds the maximum line criteria; and

grafting the selected cluster of the at least one unplaced spine at the candidate anchor cluster of the placed spine along the vector at the changed angle.

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

placing the non-selected cluster in an area of the visual display space that is separate from the placed spines when the non-selected cluster is insufficiently similar to the candidate anchor clusters.

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

determining a group concept score vector for each spine group by aggregating the concepts for the common theme.

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

placing one or more of the spine groups circumferentially about a central shape within a sector having minimum and maximum angles.

20. A method according to claim 19, wherein each placed spine group is sufficiently unique from any other such spine group already placed into the visual display space.

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

determining a similarity of at least one of the spine groups not placed into the visual display space and each of the placed spine groups; and

placing the unplaced spine group at the central shape at an angle of the placed spine group with the closest similarity.

22. A method according to claim 21, wherein the central shape comprises a circle with a radius calculated in accordance with an equation:

23. A method according to claim 21, further comprising:

rotating the unplaced spine group about the central shape when the unplaced spine group and the placed spine group overlap.

24. A method according to claim 23, further comprising:

performing at least one of translating the unplaced spine group outwards and rotating the unplaced spine group in an opposite direction about the central shape when the unplaced spine group exceeds at least one of the minimum and maximum angles.