Taxonomy discovery

• US 20070156665A1
• Filed: 07/06/2004
• Published: 07/05/2007
• Est. Priority Date: 12/05/2001
• Status: Abandoned Application

• Current Assignee: Science Applications International Corporation
• Original Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Inventors: Wnek, Janusz
• Application Number:
  US10/883,746
• Publication Number:
  US 20070156665A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Discovering a taxonomy of a subset of a collection of documents by preprocessing a document collection; calculating a vector space for the preprocessed document collection; and grouping and labeling at least a first level of a taxonomy of a subset of the collection.

Claims

1. A computer-based method for generating a taxonomy of a collection of documents, comprising:

generating a term-by-document matrix for the collection of documents;

generating a vector for each document in the collection of documents based on the term-by-document matrix;

identifying document clusters based on similarity comparisons between pairs of the vectors;

identifying labels for the document clusters based on generalized entities included in documents of the document clusters; and

storing the labels in an electronic format accessible to a user.

2. The computer-based method of claim 6, wherein identifying labels for the document clusters based on generalized entities included in documents of the document clusters comprises:

determining a preliminary group in a first level of the hierarchical document clusters;

labeling the preliminary group;

refining the preliminary group; and

removing the documents assigned to the preliminary group from consideration for membership in other groups in the first level of the hierarchical document cluster.

6. The computer-based method of claim 1, wherein identifying document clusters based on similarity comparisons between pairs of the vectors comprises:

identifying hierarchical document clusters based on similarity comparisons between pairs of the vectors.

7. The method of claim 1, wherein identifying document clusters based on similarity comparisons between pairs of the vectors comprises:

identifying a first document and a second document as members of a first document cluster if a similarity between the vector corresponding to the first document and the vector corresponding to the second document exceeds a threshold.

8. The method of claim 1, wherein identifying labels for the document clusters based on generalized entities included in documents of the document clusters comprises:

sorting entities based on at least one of (i) a number of documents that include the respective entities, (ii) a number of words included in the respective entities, and (iii) a frequency of occurrence of the respective entities.

9. The method of claim 1, wherein identifying labels for the document clusters based on generalized entities included in documents of the document clusters comprises:

excluding one or more entities included on an exclusion list.

10. The method of claim 1, wherein identifying labels for the document clusters based on generalized entities included in documents of the document clusters comprises:

excluding one or more entities as a label for a first document cluster if the one or more entities are included in a predetermined number of documents not included in the first document cluster.

11. The method of claim 1, further comprising:

displaying the labels to a user in a concept hierarchy.

3. A computer program product comprising a computer usable medium having computer readable program code stored therein that causes an application program for generating a taxonomy of a collection of documents to execute on an operating system of a computer, the computer readable program code comprising:

computer readable first program code for causing the computer to generate a term-by-document matrix for the collection of documents,

computer readable second program code for causing the computer to generate a vector for each document in the collection of documents based on the term-by-document matrix;

computer readable third program code for causing the computer to identify document clusters based on similarity comparisons between pairs of the vectors;

computer readable fourth program code for causing the computer to identify labels for the document clusters based on generalized entities included in documents of the document clusters; and

computer readable fifth program code for causing the computer to store the labels in an electronic format accessible to a user.

4. The method computer program product of claim 12, wherein the computer readable fourth program code further comprises:

code for causing the computer to determine a preliminary group in a first level of the hierarchical document cluster;

code for causing the computer to label the preliminary group;

code for causing the computer to refine the preliminary group; and

code for causing the computer to remove documents assigned to the preliminary group from consideration for membership in other groups in the first level of the hierarchical document cluster.

12. The computer program product of claim 3, wherein the computer readable third program code comprises:

code for causing the computer to identify hierarchical document clusters based on similarity comparisons between pairs of the vectors.

13. The computer program product of claim 3, wherein the computer readable fourth program code comprises:

code for causing the computer to identify a first document and a second document as members of a first document cluster if a similarity between the vector corresponding to the first document and the vector corresponding to the second document exceeds a threshold.

14. The computer program product of claim 3, wherein the computer readable fourth program code comprises:

code for causing the computer to sort entities based on at least one of (i) a number of documents that include the respective entities, (ii) a number of words included in the respective entities, and (iii) a frequency of occurrence of the respective entities.

15. The computer program product of claim 3, wherein the computer readable fourth program code comprises:

code for causing the computer to exclude one or more entities included on an exclusion list.

16. The computer program product of claim 3, wherein the computer readable fourth program code comprises:

code for causing the computer to exclude one or more entities as a label for a first document cluster if the one or more entities are included in a predetermined number of documents not included in the first document cluster.

17. The computer program product of claim 3, further comprising code to cause the computer to display the labels to a user in a concept hierarchy.

5. A system for generating a taxonomy of a collection of documents, comprising:

a plurality of processors that each communication with at least one other processor in the plurality of processors over a network; and

a computer program product comprising a computer usable medium having computer readable program code stored therein that causes an application program for generating a taxonomy of a collection of documents to execute on at least one of the processors in the plurality of processors, wherein the computer program product includes

computer readable first program code for causing the computer to generate a term-by-document matrix for the collection of documents;

computer readable second program code for causing the computer to generate a vector for each document in the collection of documents based on the term-by-document matrix,

computer readable third program code for causing the computer to identify document clusters based on similarity comparisons between pairs of the vectors,

computer readable fourth program code for causing the computer to identify labels for the document clusters based on generalized entities included in documents of the document clusters,

computer readable fifth program code for causing the computer to transmit the labels over the network.

18. The system of claim 5, wherein the computer readable fourth program code further comprises:

code for causing the computer to determine a preliminary cluster in a first level of the hierarchical document cluster;

code for causing the computer to label the preliminary group;

code for causing the computer to refine the preliminary group; and

code for causing the computer to remove documents assigned to the preliminary group from consideration for membership in other groups in the first level of the hierarchical document cluster.

19. The system of claim 5, wherein the computer readable third program code comprises:

code for causing the computer to identify hierarchical document clusters based on similarity comparisons between pairs of the vectors.

20. The system of claim 5, wherein the computer readable third program code comprises:

code for causing the computer to identify a first document and a second document as members of a first document cluster if a similarity between the vector corresponding to the first document and the vector corresponding to the second document exceeds a threshold.