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

• US 7,191,175 B2
• Filed: 02/13/2004
• Issued: 03/13/2007
• 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
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US10/778,416
• Publication Number:
  US 20050182764A1
• Time in Patent Office: 1,124 Days
• Field of Search: 707/1, 707/2, 707/6, 707/10, 707/200, 707/5, 345/440
• 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/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

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 of the best fit candidate spines that are sufficiently unique from each other of the best fit candidate spines and to place each the-identified best fit candidate spine that was identified as sufficiently unique in a visual display space; and

a remaining candidate spine placer to place each of the best fit candidate spines that were not identified as sufficiently unique in the visual display space next to an anchor cluster on the best fit candidate spine that is most similar and which was already placed in the visual display space.

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 each of the candidate spines 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 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 of the clusters 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 of the best fit candidate spines; and

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

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

a concept score aggregator to aggregate a concept score for each of the concepts 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 in each of the best fit candidate spines already placed in the visual display space and each of the clusters in a best fit candidate spine that was not identified as sufficiently unique, and to identify anchor cluster candidate having acceptable similarity to the clusters in the best fit candidate spine that was not identified as sufficiently unique.

14. A system according to claim 13, wherein the similarity is calculated as a cosine over the anchor cluster candidate and each of the clusters in the best fit candidate spine that was not identified as sufficiently unique.

15. A system according to claim 13, wherein the best fit candidate spine that was not identified as sufficiently unique 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 best fit candidate spine that was not identified as sufficiently unique is adjusted if overlapping with at least one other cluster already placed in the visual display space.

17. A system according to claim 15, wherein the best fit candidate spine that was not identified as sufficiently unique is labeled as containing at least one anchor cluster candidate following placement in the visual display space.

18. A system according to claim 15, wherein the best fit candidate spine that was not identified as sufficiently unique is placed along a vector originating from the anchor cluster with an angle comprising at least one of

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 of the best fit candidate spines that are sufficiently unique from each other of the best fit candidate spines and placing each best fit candidate spine that was identified as sufficiently unique in a visual display space; and

placing each of the best fit candidate spines that were not identified as sufficiently unique in the visual display space next to an anchor cluster on the best fit candidate spine that is most similar and which was already placed in the visual display space.

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 each of the candidate spines 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 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 of the clusters 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 of the best fit candidate spines; and

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

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

aggregating a concept score for each of the concepts 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 in each of the best fit candidate spines already placed in the visual display space and each of the clusters in a best fit candidate spine that was not identified as sufficiently unique; and

identifying the anchor cluster candidate having acceptable similarity to the clusters in the best fit candidate spine that was not identified as sufficiently unique.

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

calculating the similarity as a cosine over the anchor cluster candidate and each of the clusters in the best fit candidate spine that was not identified as sufficiently unique.

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

placing the best fit candidate spine that was not identified as sufficiently unique 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 best fit candidate spine that was not identified as sufficiently unique if overlapping with at least one other cluster already placed in the visual display space.

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

labeling the best fit candidate spine that was not identified as sufficiently unique as containing at least one anchor cluster candidate following placement in the visual display space.

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

placing the best fit candidate spine that was not identified as sufficiently unique along a vector originating from the anchor cluster with an angle comprising at least one of

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 of the best fit candidate spines that are sufficiently unique from each other of the best fit candidate spines and means for placing each best fit candidate spine that was identified as sufficiently unique in a visual display space; and

means for placing each of the best fit candidate spines that were not identified as sufficiently unique in the visual display space next to an anchor cluster on the best fit candidate spine that is most similar and which was already placed in the visual display space.