Identifying Related Objects Using Quantum Clustering

• US 20080059512A1
• Filed: 08/31/2007
• Published: 03/06/2008
• Est. Priority Date: 08/31/2006
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: OrcaTec LLC
• Inventors: Golbere, Brian, Roitblat, Herbert L.
• Granted Patent: US 8,010,534 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

Techniques for grouping related objects such as documents and files using quantum clustering are disclosed. A method may include constructing a feature-object database of multiple objects. The feature-object database may have quantized selected features as keys. A connected objects database maybe built. Clusters of connected objects may be identified in the connected objects database. The clusters of identified objects may be evaluated to determine groups of related objects. The method may be implemented on a computing device.

Claims

1. A method of clustering objects comprising:

constructing a feature-object database of multiple objects, wherein the constructing includes

obtaining an object

extracting features from the object

selecting features from the object

quantizing the selected features from the object

building the feature-object database having quantized selected features as keys

building a connected objects database

identifying clusters of connected objects

evaluating the clusters of identified objects to designate groups of related objects.

2. The method of claim 1 wherein the objects comprise documents or files.

3. The method of claim 1 further comprising:

building a directed graph of connected objects.

4. The method of claim 3 wherein the identifying clusters comprises:

walking the directed graph of connected objects to determine which objects share a system defined number of features to be considered a cluster.

5. The method of claim 1 wherein the quantizing comprises:

assigning value ranges for the features, each value range having a corresponding representative code.

6. The method of claim 5 wherein the quantizing further comprises:

preparing a synthetic vocabulary representing the features and the quantized values and incorporating the representative code.

7. A storage medium having instructions stored thereon which when executed by a processor cause the processor to perform actions comprising:

constructing a feature-object database of multiple objects, wherein the constructing includes

obtaining an object

extracting features from the object

selecting features from the object

quantizing the selected features from the object

building the feature-object database having quantized selected features as keys

building a connected objects database

identifying clusters of connected objects

evaluating the clusters of identified objects to designate groups of related objects.

8. The storage medium of claim 7 wherein the objects comprise documents or files.

9. The storage medium of claim 7 having further instructions stored thereon which when executed by a processor cause the processor to perform further actions comprising:

building a directed graph of connected objects.

10. The storage medium of claim 9 wherein the identifying clusters comprises:

walking the directed graph of connected objects.

11. The storage medium of claim 7 wherein the quantizing comprises:

assigning value ranges for the features, each value range having a corresponding representative code.

12. The storage medium of claim 11 wherein the quantizing further comprises:

preparing a synthetic vocabulary representing the features and the quantized values and incorporating the representative code.

13. A computing device comprising:

a processor, a memory, and a storage device, wherein the storage device includes a storage medium having instructions thereon which when executed cause the computing device to perform operations comprising;

constructing a feature-object database of multiple objects, wherein the constructing includes

obtaining an object

extracting features from the object

selecting features from the object

quantizing the selected features from the object

building the feature-object database having quantized selected features as keys

building a connected objects database

identifying clusters of connected objects

evaluating the clusters of identified objects to determine groups of related objects.

14. The computing device of claim 13 wherein the objects comprise documents or files.

15. The computing device of claim 13 wherein the storage medium has further instructions stored thereon which when executed the computing device to perform further actions comprising:

building a directed graph of connected objects.

16. The computing device of claim 15 wherein the identifying clusters comprises:

walking the directed graph of connected objects.

17. The computing device of claim 13 wherein the quantizing comprises:

assigning value ranges for the features, each value range having a corresponding representative code.

18. The computing device of claim 17 wherein the quantizing further comprises:

preparing a synthetic vocabulary representing the features and the quantized values and incorporating the representative code.

19. A method of identifying related documents by clustering a plurality of documents, the method comprising:

constructing a feature-document database of the plurality of documents, wherein the constructing includes

obtaining one of the plurality of documents as a current document

extracting words from the current document

selecting some of the words from the current document

quantizing the selected words from the object

building the feature-document database having quantized selected words as keys

building a connected documents database

identifying clusters of connected documents

evaluating the clusters of identified documents to determine groups of related documents.

20. The method of claim 19 wherein the constructing the feature-document database further comprises:

organizing the words in the current document into shingles

hashing each shingle

selecting some shingles to be features.

21. The method of claim 19 wherein constructing the feature-document database further comprises:

breaking the current document into paragraphs

constructing features from word groups that co-occur in a paragraph.

22. The method of claim 21 wherein the word groups comprise pairs or triples, and the words in the word groups need not be immediately adjacent.

23. The method of claim 19 further comprising:

building a directed graph of connected documents,

wherein the identifying clusters comprises walking the directed graph of connected documents.

24. The method of claim 19 wherein the quantizing comprises:

assigning value ranges for the features, each value range having a corresponding representative code.

25. The method of claim 24 wherein the quantizing further comprises:

preparing a synthetic vocabulary representing the features and the quantized values, and incorporating the representative code.