Generating representative exemplars for indexing, clustering, categorization and taxonomy

• US 20060242098A1
• Filed: 11/01/2005
• Published: 10/26/2006
• Est. Priority Date: 04/26/2005
• Status: Abandoned Application

• Current Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Original Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Inventors: Wnek, Janusz
• Application Number:
  US11/262,735
• Publication Number:
  US 20060242098A1
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06F 16/33 Querying

Abstract

A method for automatically selecting representative exemplars from a collection of documents. The method includes generating a representation of each document in the collection of documents in an abstract mathematical space, measuring a similarity between the representation of each document in the collection of documents and the representation of at least one other document in the collection of documents, identifying clusters of conceptually similar documents based on the similarity measurements, and identifying at least one exemplary document within each cluster.

Claims

1. A method for automatically selecting exemplary documents from a collection of documents, comprising:

generating a representation of each document in the collection of documents in an abstract mathematical space;

measuring a similarity between the representation of each document in the collection of documents and the representation of at least one other document in the collection of documents;

identifying clusters of conceptually similar documents based on the similarity measurements; and

identifying at least one exemplary document within each cluster.

2. The method of claim 1, wherein generating a representation of each document in an abstract mathematical space comprises generating a vector representation of each document in a Latent Semantic Indexing (LSI) space.

3. The method of claim 2, wherein measuring a similarity between the vector representation of each document in the collection of documents and the vector representation of at least one other document in the collection of documents comprises applying a cosine similarity measure.

4. The method of claim 1, wherein identifying clusters of conceptually similar documents based on the similarity measurements comprises:

(a) identifying a first document in the collection of documents;

(b) identifying a first subset of documents in the collection of documents, wherein each document in the first subset meets a similarity criterion with the first document, and wherein the similarity criterion is based on the similarity measurements; and

(c) identifying a first cluster of conceptually similar documents associated with the first document if the number of documents in the first subset is at least a minimum number.

5. The method of claim 4, wherein identifying at least one exemplary document within each cluster comprises:

identifying the first document as an exemplary document within the first cluster of conceptually similar documents.

6. The method of claim 4, further comprising:

(d) identifying a second document in the first subset of documents;

(e) identifying a second subset of documents in the collection of documents, wherein each document in the second subset meets a similarity criterion with the second document, and wherein the similarity criterion is based on the similarity measurements; and

(f) identifying a second cluster of conceptually similar documents associated with the second document if the number of documents in the second subset is at least the minimum number.

7. The method of claim 6, wherein identifying at least one exemplary document within each cluster comprises identifying one exemplary document, the identification of the one exemplary document comprising:

assigning a score to the first cluster of conceptually similar documents associated with the first document and a score to the second cluster of conceptually similar documents associated with the second document; and

identifying one of the first and second documents as the one exemplary document in the cluster based on the assigned scores.

8. The method of claim 4, further comprising:

(d) identifying a second document in the collection of documents that is not associated with a cluster of conceptually similar documents;

(e) identifying a second subset of documents in the collection of documents, wherein each document in the second subset meets a similarity criterion with the second document, and wherein the similarity criterion is based on the similarity measurements; and

(f) identifying a second cluster of conceptually similar documents associated with the second document if the number of documents in the second subset is at least a minimum number.

9. A computer program product for automatically selecting exemplary documents from a collection of documents, comprising:

a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on an operating system of a computer, said computer readable program code means comprising;

a computer readable first program code means for generating a representation of each document in the collection of documents in an abstract mathematical space;

a computer readable second program code means for measuring a similarity between the representation of each document in the collection of documents and the representation of at least one other document in the collection of documents;

a computer readable third program code means for identifying clusters of conceptually similar documents based on the similarity measurements; and

a computer readable fourth program code means for identifying at least one exemplary document within each cluster.

10. The computer program product of claim 9, wherein the computer readable first program code means comprises:

means for generating a vector representation of each document in a Latent Semantic Indexing (LSI) space.

11. The computer program product of claim 10, wherein the computer readable second program code means comprises:

means for applying a cosine similarity measure.

12. The computer program product of claim 9, wherein the computer readable third program code means for identifying clusters of conceptually similar documents based on the similarity measurements comprises:

means for identifying a first document in the collection of documents;

means for identifying a first subset of documents in the collection of documents, wherein each document in the first subset meets a similarity criterion with the first document, and wherein the similarity criterion is based on the similarity measurements; and

means for identifying a first cluster of conceptually similar documents associated with the first document if the number of documents in the first subset is at least a minimum number.

13. The computer program product of claim 12, wherein the computer readable fourth program code means for identifying at least one exemplary document within each cluster comprises:

means for identifying the first document as an exemplary document within the first cluster of conceptually similar documents.

14. The computer program product of claim 12, wherein the computer readable third program code means for identifying clusters of conceptually similar documents based on the similarity measurements further comprises:

means for identifying a second document in the first subset of documents;

means for identifying a second subset of documents in the collection of documents, wherein each document in the second subset meets a similarity criterion with the second document, and wherein the similarity criterion is based on the similarity measurements; and

means for identifying a second cluster of conceptually similar documents associated with the second document if the number of documents in the second subset is at least the minimum number.

15. The computer program product of claim 14, wherein the computer readable fourth program code means for identifying at least one exemplary document within each cluster comprises means for identifying one exemplary document, the means for identifying the one exemplary document comprising:

means for assigning a score to the first cluster of conceptually similar documents associated with the first document and a score to the second cluster of conceptually similar documents associated with the second document; and

means for identifying one of the first and second documents as the one exemplary document in the cluster based on the assigned scores.

16. The computer program product of claim 12, wherein the third computer readable program code means for identifying clusters of conceptually similar documents based on the similarity measurements, further comprises:

means for identifying a second document in the collection of documents that is not associated with a cluster of conceptually similar documents;

means for identifying a second subset of documents in the collection of documents, wherein each document in the second subset meets a similarity criterion with the second document, and wherein the similarity criterion is based on the similarity measurements; and

means for identifying a second cluster of conceptually similar documents associated with the second document if the number of documents in the second subset is at least a minimum number.

17. A computer-based method for automatically reducing a number of data objects that represent information included in a collection of data objects, comprising:

generating a representation of each data object in the collection of data objects in an abstract mathematical space;

measuring a similarity between the representation of each data object in the collection of data objects and the representation of at least one other data object in the collection of data objects;

identifying clusters of conceptually similar data objects based on the similarity measurements, wherein a number of data objects in each cluster is determined based on an adjustable clustering threshold; and

identifying at least one exemplary data object within each cluster, wherein a number of identified exemplary data objects is less than a number of data objects in the collection of data objects.

18. The method of claim 17, wherein identifying clusters of conceptually similar data objects based on the similarity measurements comprises identifying each exemplary data object individually, and wherein identifying each exemplary data object comprising at least one of (i) selecting a single data object in the collection of data objects as an exemplary data object and (ii) combining a plurality of data objects in the collection of data objects into an exemplary data object.

19. The method of claim 17, wherein a data object comprises a data object expressed in at least one of a human language, a plurality of human languages, a computer language, and a plurality of computer languages.

20. The method of claim 17, wherein a data object comprises a representation of at least one of text data, image data, voice data, video data, structured data, unstructured data, and relational data.