Clustering system and method

• US 20080082531A1
• Filed: 09/28/2006
• Published: 04/03/2008
• Est. Priority Date: 09/28/2006
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Veritas Operating Corporation (Gen Digital Inc.)
• Inventors: Suarez, Eduardo
• Granted Patent: US 8,745,055 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

In order to clustering documents, document vectors are formed for each of a plurality of documents of a corpus and plurality of reference vectors is generated. The document vectors are then compared to the reference vectors to generate similarity values for each of the document vectors. The document vectors are then sorted based on the similarity values for the document vectors to form a sorted list. Clusters are then formed based on the similarity between adjacent document vectors in the sorted list.

Claims

1. A system for clustering documents, the system comprising:

a document vector generator operable to generate a document vector for each of a plurality of documents of a corpus;

a reference vector generator operable to generate a plurality of reference vectors;

a comparator operable to compare the document vectors to each of the reference vectors to generate similarity values for each of the document vectors;

a sorter operable to sort the document vectors based on the similarity values for the document vectors to form a sorted list; and

a cluster generator operable to form clusters of documents based on the similarity between adjacent document vectors in the sorted list.

2. The system of claim 1, wherein the document vector for a document comprises frequency values for respective terms of a set of terms found in that document.

3. The system of claim 2, wherein the frequency value for a term in a document vector is a TF-IDF score for that term in the document for that document vector.

4. The system of claim 2, wherein each reference vector comprises a random value for each of the set of terms, the set of terms comprising all terms for the documents of the corpus on which the document vectors are based.

5. The system of claim 1, wherein the terms include one or more of words, phrases, and groups of words or phrases.

6. The system of claim 1, wherein the sorter is operable to sort the document vectors in ascending order by similarity values.

7. The system of claim 1, wherein the sorter is operable to sort the document vectors in descending order by similarity values.

8. The system of claim 1, wherein the cluster generator is operable to form clusters of documents based on the similarity between adjacent document vectors in the sorted list by iterating through the sorted list successively to determine if a next document has at least a predetermined similarity to preceding document by the comparison of documents vectors.

9. The system of claim 8, wherein the cluster generator is operable, where a next document has at least a predetermined similarity to a preceding document, to add the next document to the cluster for the preceding document.

10. The system of claim 8, wherein the cluster generator is operable, where a next document does not have at least a predetermined similarity to a preceding document, to form a new cluster for that next document.

11. A computer implemented method of clustering documents, the method comprising:

generating document vectors for each of a plurality of documents of a corpus;

generating a plurality of reference vectors;

comparing the document vectors to each of the reference vectors to generate similarity values for each of the document vectors;

sorting the document vectors based on the similarity values for the document vectors to form a sorted list; and

forming clusters of documents based on the similarity between adjacent document vectors in the sorted list.

12. The method of claim 11, wherein the document vector for a document comprises frequency values for respective terms of a set of terms found in that document.

13. The method of claim 12, wherein the frequency value for a term in a document vector is a TF-IDF score for that term in the document for that document vector.

14. The method of claim 12, wherein each reference vector comprises a random value for each of the set of terms, the set of terms comprising all terms for the documents of the corpus on which the document vectors are based.

15. The method of claim 11, wherein the terms include one or more of words, phrases, and groups of words or phrases.

16. The method of claim 11, wherein the step of sorting the document vectors comprises sorting the document vectors in ascending order by similarity values.

17. The method of claim 11, wherein the step of sorting the document vectors comprises sorting the document vectors in descending order by similarity values.

18. The method of claim 17, wherein forming clusters of documents based on the similarity between adjacent document vectors in the sorted list comprises iterating through the sorted list successively to determine if a next document has at least a predetermined similarity to preceding document by the comparison of documents vectors.

19. The method of claim 18, wherein, where a next document has at least a predetermined similarity to a preceding document, the next document is added to the cluster for the preceding document.

20. The method of claim 18, wherein, where a next document does not have at least a predetermined similarity to a preceding document, a new cluster is formed for that next document.

21. A computer program product comprising program instructions, the program instructions being operable to implement a method of clustering documents, the method comprising:

generating document vectors for terms of each of a plurality of documents of a corpus;

generating a plurality of reference vectors;

comparing the document vectors to each of the reference vectors to generate similarity values for each of the document vectors;

sorting the document vectors based on the similarity values for the document vectors to form a sorted list; and

forming clusters of documents based on the similarity between adjacent document vectors in the sorted list.

22. Apparatus for clustering documents, the apparatus comprising:

means for generating document vectors for each of a plurality of documents of a corpus;

means for generating a plurality of reference vectors;

means for comparing the document vectors to each of the reference vectors to generate similarity values for each of the document vectors;

means for sorting the document vectors based on the similarity values for the document vectors to form a sorted list; and

means for forming clusters of documents based on the similarity between adjacent document vectors in the sorted list.