Information exploration systems and method

• US 20070112755A1
• Filed: 11/15/2005
• Published: 05/17/2007
• Est. Priority Date: 11/15/2005
• Status: Active Grant

• Current Assignee: Kldiscovery Ontrack, LLC (KLDiscovery, Inc.)
• Original Assignee: Kroll Ontrack Incorporated (KLDiscovery, Inc.)
• Inventors: Thompson, Kevin, Sommer, Matthew
• Granted Patent: US 7,676,463 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Disclosed information exploration system and method embodiments operate on a document set to determine a document cluster hierarchy. An exclusionary phrase index is determined for each cluster, and representative phrases are selected from the indexes. The selection process may enforce pathwise uniqueness and balanced sub-cluster representation. The representative phrases may be used as cluster labels in an interactive information exploration interface.

Claims

1. A computer-implemented information exploration method that comprises:

processing a set of documents to identify a hierarchy of clusters; and

selecting for each cluster in the hierarchy of clusters one or more phrases from the set of documents as representative phrases for that cluster.

2. The method of claim 1, wherein the selecting comprises:

selecting a predetermined number of phrases that are pathwise unique.

3. The method of claim 1, wherein the selecting comprises:

selecting a predetermined number of phrases having a balanced representation of any subordinate clusters.

4. The method of claim 1, wherein the selecting comprises:

determining a score for each phrase; and

selecting a predetermined number of highest-scoring phrases.

5. The method of claim 4, wherein the score is a function of phrase length absent any stop words.

6. The method of claim 4, wherein the score is a function of at least one factor in the set consisting of document coverage, leaf cluster coverage, phrase frequency, and phrase-vector-to-cluster-centroid similarity.

7. The method of claim 1, wherein the selecting comprises:

constructing a phrase-to-leaf node index for the hierarchy of clusters.

8. The method of claim 7, wherein the selecting further comprises:

constructing a suffix tree for each leaf node in the hierarchy of clusters.

9. The method of claim 1, further comprising:

providing an interactive user interface that represents the set of documents as one or more clusters that can be selected to smaller clusters, each of which can be selected in turn to reveal still smaller clusters.

10. The method of claim 9, wherein the user interface provides a corresponding representation for each displayed cluster, wherein the representation comprises the representative phrases for the cluster.

11. The method of claim 10, wherein the representation for a displayed cluster comprises a hypertext link.

12. The method of claim 9, wherein the user interface displays titles of documents in a user-selected cluster if the user-selected cluster has no subordinate clusters in the hierarchy of clusters.

13. The method of claim 1, wherein the processing comprises a bisecting K-means clustering operation.

14. The method of claim 1, wherein the processing comprises at least one clustering operation from a set consisting of suffix tree clustering, divisive hierarchical clustering, agglomerative hierarchical clustering, K-means clustering, Buckshot clustering, Fractionation clustering.

15. The method of claim 1, wherein the processing comprises:

calculating a pseudo-document vector for each document in the set of documents; and

computing the hierarchy of clusters from the pseudo-document vectors.

16. The method of claim 7, wherein the representative phrases for any given cluster are indicated by the phrase-to-leaf node index to be absent from any leaf nodes that are not descendants of the given cluster.

17. An information exploration system that comprises:

a display;

a user input device;

a memory that stores software; and

a processor coupled to the memory to execute the software, wherein the software configures the processor to interact with a user via the display and user input device, and wherein the software further configures the processor to;

process a set of documents to identify a hierarchy of clusters;

determine a phrase index for the hierarchy of clusters;

select one or more phrases from the phrase index as representative phrases for each cluster in the hierarchy of clusters; and

displaying the representative phrases as cluster labels on the display.

18. The information exploration system of claim 17, wherein the representative phrases are selected to be pathwise unique.

19. The information exploration system of claim 17, wherein the representative phrases are exclusionary.

20. The information exploration system of claim 17, wherein as part of selecting representative phrases for a cluster, the software configures the processor to provide a balanced representation of immediate sub-clusters of that cluster.

21. The information exploration system of claim 17, wherein as part of selecting representative phrases for each cluster, the software configures the processor to determine a score for each phrase.

22. The information exploration system of claim 21, wherein the score is a function of at least one factor in the set consisting of document coverage, leaf-node coverage, phrase frequency, and phrase-vector-to-cluster-centroid similarity.

23. Application instructions on an information carrier medium, wherein the instructions, when executed, effect an information exploration interface, the application instructions comprising:

a clustering process that determines a hierarchy of clusters for a set of documents;

a cluster-naming process that selects representative phrases for each cluster in the hierarchy of clusters; and

an exploration process that interactively displays the representative phrases to a user.

24. The application instructions of claim 23, wherein the cluster-naming process selects representative phrases by:

determining a phrase-to-leaf node index for the hierarchy of clusters;

scoring each phrase in the phrase index; and

selecting representative phrases from the phrase index, wherein the representative phrases for any given cluster are indicated by the phrase-to-leaf node index to be absent from any leaf nodes that are not descendants of the given cluster.

25. The application instructions of claim 24, wherein the scores are a function of at least one factor in the set consisting of document coverage, leaf-node coverage, phrase frequency, and phrase-vector-to-cluster-centroid distance.

26. The application instructions of claim 23, wherein as part of selecting representative phrases, the application instructions ensure that the representative phrases are pathwise unique.

27. The application instructions of claim 23, wherein as part of selecting representative phrases, the application instructions ensure that the representative phrases are also balanced representations of sub-clusters.

28. A computer-implemented information exploration method that comprises:

processing a set of documents to identify a set of mutually exclusive clusters;

creating a phrase index for the set of mutually exclusive clusters; and

selecting one or more phrases from the phrase index as representative phrases for each cluster in the set of mutually exclusive clusters.

29. The method of claim 28, wherein the representative phrases for any given cluster are indicated by the phrase index to be absent from clusters that are not descendants of the given cluster.

30. The method of claim 28, wherein the selecting comprises:

determining a score for each phrase; and

selecting a predetermined number of highest-scoring phrases that satisfy an exclusivity criterion.