Systems and methods for cluster analysis with relational truth

• US 9,116,981 B2
• Filed: 07/05/2012
• Issued: 08/25/2015
• Est. Priority Date: 07/05/2012
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Denney, Bradley Scott, Dusberger, Dariusz T.
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US13/542,433
• Publication Number:
  US 20140012848A1
• Time in Patent Office: 1,146 Days
• Field of Search: 706/45
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/367 Ontology

Abstract

Systems and methods for measuring similarity between a set of clusters and a set of object labels, wherein at least two of the object labels are related, receive a first set of clusters, wherein the first set of clusters was formed by clustering objects in a set of objects into clusters of the first set of clusters according to a clustering procedure; and calculate a similarity index between the first set of clusters and a set of object labels based at least in part on a relationship between two or more object labels in the set of object labels.

Claims

1. A method for measuring similarity between a set of clusters and a set of object labels, wherein at least two of the object labels are related, the method comprising:

receiving a first set of clusters, wherein the first set of clusters was formed by clustering objects in a set of objects into clusters of the first set of clusters according to a clustering procedure; and

calculating a similarity index between the first set of clusters and a set of object labels based at least in part on a relationship between two or more object labels in the set of object labels,

wherein the object labels are semantic labels,

wherein the relationship between the two or more object labels is based at least in part on a semantic distance, and

wherein the semantic distance is defined by a semantic ontology that includes the object labels.

2. The method of claim 1, wherein the semantic ontology includes a hierarchy of object labels.

3. The method of claim 1, further comprising:

calculating an expected value of the similarity index, wherein the expected value of the similarity index is a value of the similarity index one would expect to obtain, on average, between a randomly generated second set of clusters and the object labels; and

adjusting the calculated similarity index by a penalty factor based at least in part on the expected value of the similarity index.

4. The method of claim 3, wherein the expected value of the similarity index is based at least in part on the relationship between the two or more object labels.

5. A system for measuring similarity between a set of clusters and a corresponding set of object labels, the system comprising:

one or more non-transitory computer-readable media configured to store computer-executable instructions; and

one or more processors configured to cause the system to

receive a set of object clusters, wherein the set of object clusters includes two or more clusters,

receive a set of object labels, and

generate a similarity index between the set of clusters and the set of object labels based at least in part on a relationship between two or more object labels in the set of object labels,

wherein the object labels are semantic labels,

wherein the relationship between the two or more object labels is based at least in part on a semantic distance, and

wherein the semantic distance is defined by a semantic ontology that includes the object labels.

6. The system of claim 5, wherein generating the similarity index comprises:

generating a similarity measurement for a first cluster and a first object label, wherein the similarity measurement is based on a number of objects shared by the first cluster and the first object label; and

adjusting the similarity measurement based on a relationship between the first object label and another object label.

7. The system of claim 6, wherein generating the similarity index further comprises adjusting a similarity measurement for the first cluster and the first object label based on the relationship between the two or more object labels.

8. The system of claim 5, wherein the semantic ontology is organized in a hierarchy.

9. The system of claim 5, wherein generating the similarity index comprises:

generating a similarity measurement for a first cluster and a first object label, wherein the similarity measurement is based on a number of objects excluded by both the first cluster and the first object label; and

adjusting the similarity measurement based on the relationship between the two or more object labels.

10. The system of claim 5, wherein the similarity index is further based on a relationship between a first object label of a first object in a cluster and a second object label of a second object in the cluster.

11. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing devices, cause the one or more computing devices to perform operations comprising:

receiving a set of clusters of objects, wherein the set of clusters includes two or more clusters of objects;

receiving a set of object labels of objects, wherein the set of object labels includes two or more labels; and

calculating a similarity index between the set of clusters and the set of object labels based at least in part on a relationship between two or more object labels in the set of object labels,

wherein the object labels are semantic labels,

wherein the relationship between the two or more object labels is based at least in part on a semantic distance, and

wherein the semantic distance is defined by a semantic ontology that includes the object labels.

12. The one or more non-transitory computer-readable media of claim 11, wherein the similarity index is based on a relationship between respective object labels of two differently-labeled objects in a cluster.

13. The one or more non-transitory computer-readable media of claim 11, wherein the similarity index is based at least in part on a Rand Index.

14. The one or more non-transitory computer-readable media of claim 13, wherein the similarity index is calculated according to

15. The one or more non-transitory computer-readable media of claim 11, wherein the similarity index is based at least in part on a relationship-based cluster purity measure.