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

• US 20050182764A1
• Filed: 02/13/2004
• Published: 08/18/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,191,175 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 system and method for arranging concept clusters in thematic neighborhood relationships in a two-dimensional visual display space is presented. A set of clusters is selected from a concept space. The concept space includes a multiplicity of clusters with concepts visualizing document content based on extracted concepts. A theme in each of a plurality of the clusters is identified. Each theme includes at least one such concept ranked within the cluster. A plurality of unique candidate spines is logically formed. Each candidate spine includes clusters commonly sharing at least one such concept. The clusters are assigned to one such candidate spine having a substantially best fit. Each such sufficiently unique best fit candidate spine is identified and placed in a visual display space. Each non-identified best fit candidate spine is placed in the visual display space relative to an anchor cluster on one such identified best fit candidate spine.

Claims

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

a set of clusters selected from a concept space comprising a multiplicity of clusters with concepts visualizing document content based on extracted concepts;

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; and

a spine placer, comprising;

a candidate spine selector to logically form a plurality of unique candidate spines comprising clusters commonly sharing at least one such concept;

a candidate spine assigner to assign one or more of the clusters to one such candidate spine having a substantially best fit;

a best fit candidate spine placer to identify each such best fit candidate spine sufficiently unique from each other such best fit candidate spine and to place the identified best fit candidate spine in a visual display space; and

a remaining candidate spine placer to place each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on one such identified best fit candidate spine.

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

a concept scorer to determine a cumulative score for one or more of the concepts for each of the plurality of clusters; and

a concept ranker to rank the concepts by the cumulative score in at least one of descending and ascending order.

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

a concept evaluator to evaluate each of the plurality of concepts against an acceptance criteria to qualify as the theme of the cluster.

4. A system according to claim 3, 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.

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

a candidate spine evaluator to evaluate such candidate spine against an acceptance criteria.

6. A system according to claim 5, 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.

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

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

a spine fit selector to select the spine fit comprising a maximum spine fit as the substantially best fit.

8. A system according to claim 7, wherein the spine fit is calculated in accordance to an equation:

9. A system according to claim 1, wherein each such best fit candidate spine containing only one such cluster is discarded.

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

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

a similarity evaluator to evaluate a similarity between the best fit candidate spine and each other such other such best fit candidate spine.

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

a concept score aggregator to aggregate a concept score for each such concept contained in each cluster in the best fit candidate spine; and

a concept score normalizer to normalize each aggregated concept score.

12. A system according to claim 10, wherein the similarity is calculated as a cosine over the spine concept score vectors.

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

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

14. A system according to claim 13, wherein the similarity is calculated as a cosine over the anchor cluster candidate and one such cluster in the spine.

15. A system according to claim 13, wherein the non-identified best fit candidate spine is placed in the visual display space along a vector originating from the anchor cluster.

16. A system according to claim 15, wherein the placement of the non-identified best fit candidate spine is adjusted if overlapping with at least one other cluster already placed.

17. A system according to claim 15, wherein the non-identified best fit candidate spine is labeled as containing at least one anchor cluster candidate following placement.

18. A system according to claim 15, wherein the non-identified best fit candidate spine is placed along a vector originating from the anchor cluster with an angle comprising at least one

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

selecting a set of clusters from a concept space comprising a multiplicity of clusters with concepts visualizing document content based on extracted concepts;

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 commonly sharing at least one such concept and assigning one or more of the clusters to one such candidate spine having a substantially best fit;

identifying each such 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

placing each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on one such identified best fit candidate spine.

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

determining a cumulative score for one or more of the concepts for each of the plurality of clusters; and

ranking the concepts by the cumulative score in at least one of descending and ascending order.

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

evaluating each of the plurality of concepts against an acceptance criteria to qualify as the theme of the cluster.

22. A method according to claim 21, 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.

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

evaluating such candidate spine against an acceptance criteria.

24. A method according to claim 23, 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.

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

determining a spine fit between the concept in each such 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.

26. A method according to claim 25, wherein the spine fit is calculated in accordance to an equation:

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

discarding each such best fit candidate spine containing only one such cluster.

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

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

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

29. A method according to claim 28, further comprising:

aggregating a concept score for each such concept contained in each cluster in the best fit candidate spine; and

normalizing each aggregated concept score.

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

calculating the similarity as a cosine over the spine concept score vectors.

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

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

identifying the at least one such anchor cluster candidate with acceptable similarity as the anchor cluster.

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

calculating the similarity as a cosine over the anchor cluster candidate and one such cluster in the spine.

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

placing the non-identified best fit candidate spine in the visual display space along a vector originating from the anchor cluster.

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

adjusting placement of the non-identified best fit candidate spine if overlapping with at least one other cluster already placed.

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

labeling the non-identified best fit candidate spine as containing at least one anchor cluster candidate following placement.

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

placing the non-identified best fit candidate spine along a vector originating from the anchor cluster with an angle comprising at least one of

$\mathrm{\sigma <br><br>}\pm <br><br>\frac{\mathrm{\Pi <br><br>}}{3},$

where 0≦

σ

<

Π

.

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

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

means for selecting a set of clusters from a concept space comprising a multiplicity of clusters with concepts visualizing document content based on extracted concepts;

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 commonly sharing at least one such concept and means for assigning one or more of the clusters to one such candidate spine having a substantially best fit;

means for identifying each such 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; and

means for placing each non-identified best fit candidate spine in the visual display space relative to an anchor cluster on one such identified best fit candidate spine.