System and method for arranging concept clusters in thematic neighborhood relationships in a shaped two-dimensional visual display space

• US 20050192956A1
• Filed: 08/03/2004
• Published: 09/01/2005
• Est. Priority Date: 02/13/2004
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: Attenex Corp. (FTI Consulting Incorporated)
• Inventors: Evans, Lynne Marie
• Granted Patent: US 7,440,622 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/00 Pattern recognition
• 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: H05K 999/99 dummy group
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A set of clusters is selected from a concept space including clusters with concepts extracted to visualize document content. A theme is identified in each of the clusters. Each theme includes a concept ranked within the cluster. Unique candidate spines including clusters sharing at least one common theme are logically formed. The clusters are assigned to one such candidate spine having a substantially best fit. Each best fit candidate spine sufficiently unique from each other such best fit candidate spine is identified. The identified best fit candidate spine is placed in a visual display space. A similarity between each non-identified best fit candidate spine and each placed best fit candidate spine is evaluated. Each non-identified best fit candidate spine is placed in the visual display space relative to an anchor cluster on the placed best fit candidate spine that is sufficiently similar to the non-identified best fit candidate spine.

Claims

1. A system for arranging concept clusters in thematic neighborhood relationships in a shaped two-dimensional visual display space, comprising:

a clustering module to select a set of clusters from a concept space comprising a multiplicity of clusters with concepts extracted to visualize document content;

a theme generator to identify a theme in each of a plurality of the clusters, each theme comprising at least one such concept ranked within the cluster;

a spine placement module to logically form a plurality of unique candidate spines comprising clusters sharing at least one common theme and assigning one or more of the clusters to one such candidate spine having a substantially best fit, and to identify each best fit candidate spine sufficiently unique from each other such best fit candidate spine and placing the identified best fit candidate spine in a visual display space; and

a spine group placement module to evaluate a similarity between each non-identified best fit candidate spine and each placed best fit candidate spine and to place each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on the placed best fit candidate spine that is sufficiently similar to the non-identified best fit candidate spine.

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

an evaluator to evaluate each of the plurality of concepts against an acceptance criteria to qualify as the theme of the cluster, wherein the acceptance criteria comprises at least one of being contained in a seed theme of a cluster and being contained in a predetermined minimum of the documents.

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

an evaluator to evaluate such candidate spine against an acceptance criteria, wherein the acceptance criteria comprises the at least one such concept being contained in at least one of a plurality of the plurality of clusters and within a predetermined maximum of the plurality of clusters.

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

a best fit evaluator to determine a spine fit between the concept in each cluster and the at least one theme commonly shared by the clusters in each of the candidate spines, and to select the spine fit comprising a maximum spine fit as the substantially best fit, wherein the spine fit is calculated in accordance to an equation;

$F=\log <br><br>\left(\frac{v}{r^2}\right)\times <br><br>w$

where v is defined as a number of clusters containing each concept in the candidate spine, r is defined as a rank order of the concept, and w is defined as a bias factor.

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

a vector generator to generate a spine concept score vector for each best fit candidate spine, and to evaluate a similarity between the best fit candidate spine and each other such other such best fit candidate spine.

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

an evaluator to determine a cosine similarity between a spine for at least one anchor cluster candidate and a non-identified best fit candidate spine, and to identify the at least one such anchor cluster candidate with acceptable similarity as a spine for an anchor cluster.

7. A system according to claim 1, wherein the best fit candidate spines are ordered by length.

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

a list builder to build a list of the anchor clusters from the placed best fit candidate spines subject to an acceptance criteria.

9. A system according to claim 8, wherein the acceptance criteria for a strong anchor cluster comprises at least one of being placed in a best fit spine, containing a same concept, having at least one open edge, and having a similarity meeting a predefined threshold.

10. A system according to claim 8, wherein the acceptance criteria for a weak anchor cluster comprises at least one of being placed in a best fit spine, having at least one open edge, and having a similarity meeting a predefined threshold.

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

a selector to select an anchor cluster assigned to each non-identified best fit candidate spine that is not sufficiently similar to the placed best fit candidate spines.

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

an evaluator to evaluate a similarity between each cluster not assigned to one such candidate spine and each placed cluster, and to place each non-assigned cluster in the visual display space proximal to an anchor cluster on the placed candidate spine that is sufficiently similar.

13. A system according to claim 1, wherein at least one group of placed best fit candidate spines is oriented circumferentially to a central shape defined logically within the visual display space.

14. A system according to claim 13, wherein the logically-defined central shape comprises an elliptical shape.

15. A system according to claim 14, wherein the elliptical shape comprises a circle having a radius calculated in accordance to an equation:

16. A system according to claim 14, further comprising:

a selector to select a plurality of placed best fit candidate spine groups, to evaluate a similarity between each of the placed best fit candidate spine groups, and to locate each placed best fit candidate spine group spaced substantially regularly about the logically-defined central shape.

17. A system according to claim 16, further comprising:

an evaluator to evaluate a similarity between each non-selected placed best fit candidate spine group relative to each located placed best fit candidate spine group, and to orient each non-selected placed best fit candidate spine group that is sufficiently similar to one such located placed best fit candidate spine group.

18. A system according to claim 17, wherein the non-selected placed best fit candidate spine group is located to not overlap with the located placed best fit candidate spine groups within a sector defined for the located placed best fit candidate spine groups.

19. A system according to claim 18, wherein the non-selected placed best fit candidate spine group and the located placed best fit candidate spine groups are translated radially and outwards to avoid overlap.

20. A method for arranging concept clusters in thematic neighborhood relationships in a shaped two-dimensional visual display space, comprising:

selecting a set of clusters from a concept space comprising a multiplicity of clusters with concepts extracted to visualize document content;

identifying a theme in each of a plurality of the clusters, each theme comprising at least one such concept ranked within the cluster;

logically forming a plurality of unique candidate spines comprising clusters sharing at least one common theme and assigning one or more of the clusters to one such candidate spine having a substantially best fit;

identifying each best fit candidate spine sufficiently unique from each other such best fit candidate spine and placing the identified best fit candidate spine in a visual display space;

evaluating a similarity between each non-identified best fit candidate spine and each placed best fit candidate spine; and

placing each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on the placed best fit candidate spine that is sufficiently similar to the non-identified best fit candidate spine.

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

evaluating each of the plurality of concepts against an acceptance criteria to qualify as the theme of the cluster, wherein the acceptance criteria comprises at least one of being contained in a seed theme of a cluster and being contained in a predetermined minimum of the documents.

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

evaluating such candidate spine against an acceptance criteria, wherein the acceptance criteria comprises the at least one such concept being contained in at least one of a plurality of the plurality of clusters and within a predetermined maximum of the plurality of clusters.

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

determining a spine fit between the concept in each cluster and the at least one theme commonly shared by the clusters in each of the candidate spines; and

selecting the spine fit comprising a maximum spine fit as the substantially best fit, wherein the spine fit is calculated in accordance to an equation;

$F=\log <br><br>\left(\frac{v}{r^2}\right)\times <br><br>w$

where v is defined as a number of clusters containing each concept in the candidate spine, r is defined as a rank order of the concept, and w is defined as a bias factor.

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

generating a spine concept score vector for each best fit candidate spine; and

evaluating a similarity between the best fit candidate spine and each other such other such best fit candidate spine.

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

determining a cosine similarity between a spine for at least one anchor cluster candidate and a non-identified best fit candidate spine; and

identifying the at least one such anchor cluster candidate with acceptable similarity as a spine for an anchor cluster.

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

ordering the best fit candidate spines by length.

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

building a list of the anchor clusters from the placed best fit candidate spines subject to an acceptance criteria.

28. A method according to claim 27, wherein the acceptance criteria for a strong anchor cluster comprises at least one of being placed in a best fit spine, containing a same concept, having at least one open edge, and having a similarity meeting a predefined threshold.

29. A method according to claim 27, wherein the acceptance criteria for a weak anchor cluster comprises at least one of being placed in a best fit spine, having at least one open edge, and having a similarity meeting a predefined threshold.

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

selecting an anchor cluster assigned to each non-identified best fit candidate spine that is not sufficiently similar to the placed best fit candidate spines.

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

evaluating a similarity between each cluster not assigned to one such candidate spine and each placed cluster; and

placing each non-assigned cluster in the visual display space proximal to an anchor cluster on the placed candidate spine that is sufficiently similar.

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

orienting at least one group of placed best fit candidate spines circumferentially to a central shape defined logically within the visual display space.

33. A method according to claim 32, wherein the logically-defined central shape comprises an elliptical shape.

34. A method according to claim 33, wherein the elliptical shape comprises a circle having a radius calculated in accordance to an equation:

35. A method according to claim 33, further comprising:

selecting a plurality of placed best fit candidate spine groups;

evaluating a similarity between each of the placed best fit candidate spine groups; and

locating each placed best fit candidate spine group spaced substantially regularly about the logically-defined central shape.

36. A method according to claim 35, further comprising:

evaluating a similarity between each non-selected placed best fit candidate spine group relative to each located placed best fit candidate spine group; and

orienting each non-selected placed best fit candidate spine group that is sufficiently similar to one such located placed best fit candidate spine group.

37. A method according to claim 36, further comprising:

locating the non-selected placed best fit candidate spine group to not overlap with the located placed best fit candidate spine groups within a sector defined for the located placed best fit candidate spine groups.

38. A method according to claim 37, further comprising:

translating the non-selected placed best fit candidate spine group and the located placed best fit candidate spine groups radially and outwards to avoid overlap.

39. A computer-readable storage medium holding code for performing the method according to claim 20.

40. An apparatus for arranging concept clusters in thematic neighborhood relationships in a shaped two-dimensional visual display space, comprising:

means for selecting a set of clusters from a concept space comprising a multiplicity of clusters with concepts extracted to visualize document content;

means for identifying a theme in each of a plurality of the clusters, each theme comprising at least one such concept ranked within the cluster;

means for logically forming a plurality of unique candidate spines comprising clusters sharing at least one common theme and means for assigning one or more of the clusters to one such candidate spine having a substantially best fit;

means for identifying each best fit candidate spine sufficiently unique from each other such best fit candidate spine and means for placing the identified best fit candidate spine in a visual display space;

means for evaluating a similarity between each non-identified best fit candidate spine and each placed best fit candidate spine; and

means for placing each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on the placed best fit candidate spine that is sufficiently similar to the non-identified best fit candidate spine.