Identifying related objects using quantum clustering
View Patent ↗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.
1. A computing device having a processor and accessible computer readable storage media, the storage media having instructions thereon that when executed by the processor cause the computing device to perform a method for relating objects, the method comprising:
forming a directed graph of connected objects from a feature-object database,
wherein the feature-object database comprises,
a plurality of feature-object database keys, each feature-object database key comprising a feature value calculated from a feature extracted from an object; and
at least one feature-object database value corresponding to each feature-object database key, the at least one feature-object database value comprising an object identifier identifying an object having the feature corresponding to the corresponding feature-object database key; and
wherein the forming a directed graph comprises,
selecting keys from the feature object database, the selected keys having a plurality corresponding feature-object database values, and for each selected key, selecting the corresponding feature-object database values and adding the corresponding object identifiers as connected nodes in the directed graph of connected objects; and
calculating the number of shared features between pairs of objects, wherein a magnitude of an edge between two connected nodes is related to the number of shared features between the two objects represented by the connected nodes; and
identifying clusters each comprising a plurality of connected objects from the directed graph of connected objects.
2. The computing device of claim 1 wherein the calculating the number of shared features comprises incrementing a pair-count for each pair of object identifiers appearing as selected feature-object database values.
3. The computing device of claim 1 wherein the directed graph of connected objects is represented by a connected objects database, the connected objects database having keys comprising pairs of object identifiers and values comprising the number of shared features between the pair of objects identified by the corresponding connected objects database key.
4. The computing device of claim 1 wherein the identifying clusters comprises walking the directed graph of connected objects to determine which objects share a system defined or user defined number of features to be considered a cluster.
5. The computing device of claim 1 wherein the method for relating objects further comprising constructing the feature-object database, wherein the constructing comprises:
obtaining an object;
extracting features from the object;
calculating feature values for the extracted features;
building the feature-object database.
6. The computing device of claim 5 wherein at least some of the feature values are continuous and wherein the feature values are quantized, the quantizing comprising identifying the feature values as discrete or continuous and transforming the identified continuous feature values into discrete feature values.
7. The computing device of claim 5 wherein only a subset of extracted features are selected to build the feature-object database.
8. The computing device of claim 7 wherein the subset of extracted features is randomly selected from the set of all extracted features.
9. The computing device of claim 7 wherein the subset of extracted features is selected based upon a measure of how strongly the features are descriptive of the object from which they were extracted.
10. The computing device of claim 1 wherein each feature is extracted from an object selected from the group consisting of document files produced by word processors, text files, portable document format files, audio files, video files, still image files, mark-up files, and combinations thereof.
11. The computing device of claim 1 wherein each extracted feature comprises a word or groups of words.
12. A storage medium having instructions stored thereon which when executed by a processor cause the processor to perform the actions comprising:
forming a directed graph of connected objects from a feature-object database,
wherein the feature-object database comprises,
a plurality of feature-object database keys, each feature-object database key comprising a feature value calculated from a feature extracted from an object; and
at least one feature-object database value corresponding to each feature-object database key, the at least one feature-object database value comprising an object identifier identifying an object having the feature corresponding to the corresponding feature-object database key; and
wherein the forming a directed graph comprises,
selecting keys from the feature object database, the selected keys having a plurality corresponding feature-object database values, and for each selected key selecting the corresponding feature-object database values and adding the corresponding object identifiers as connected nodes in the directed graph of connected objects; and
calculating the number of shared features between pairs of objects,
wherein a magnitude of an edge between two connected nodes is related to the number of shared features between the two objects represented by the connected nodes; and
identifying clusters each comprising a plurality of connected objects from the directed graph of connected objects.
13. The storage medium of 12 wherein the calculating the number of share features comprises incrementing a pair-count for each pair of object identifiers appearing as selected feature-object database values.
14. The storage medium of claim 12 wherein the directed graph of connected objects is represented by a connected objects database, the connected objects database having keys comprising pairs of object identifiers and values comprising the number of shared features between the pair of objects identified by the corresponding connected objects database key.
15. The storage medium of claim 12 wherein the identifying clusters comprises walking the directed graph of connected objects to determine which objects share a system defined or user defined number of features to be considered a cluster.
16. The storage medium of claim 12 having further instructions stored thereon which when executed by a processor cause the processor to perform further action comprising constructing the feature-object database, wherein the constructing comprises:
obtaining an object;
extracting features from the object;
calculating feature values for the extracted features;
building the feature-object database.
17. The storage medium of claim 16 wherein at least some of the feature values are continuous and wherein the feature values are quantized, the quantizing comprising identifying the feature values as discrete or continuous and transforming the identified continuous feature values into discrete feature values.