Method and System for Seed Based Clustering of Categorical Data

• US 20070271292A1
• Filed: 07/12/2006
• Published: 11/22/2007
• Est. Priority Date: 05/16/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc., Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Plutowski, Mark, Acharya, Chiranjit, Usuki, Takashi, Ohwa, Tsunayuki
• Granted Patent: US 7,664,718 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A computerized method of representing a dataset with a taxonomy includes augmenting a dataset containing a plurality of records with a plurality of predetermined exemplars; representing the plurality of records and predetermined exemplars within the augmented dataset as a plurality of clusters in an initial taxonomy layer; generating a truncated hierarchy of cluster sets based on clusters within the initial taxonomy layer, wherein clusters within the truncated hierarchy contain no more than a predetermined number of exemplars; and labeling clusters within the truncated hierarchy.

Claims

1. A computerized method of representing a dataset with a taxonomy, comprising:

augmenting a dataset containing a plurality of records with a plurality of predetermined exemplars;

representing the plurality of records and predetermined exemplars within the augmented dataset as a plurality of clusters in an initial taxonomy layer;

generating a truncated hierarchy of cluster sets based on clusters within the initial taxonomy layer, wherein clusters within the truncated hierarchy contain no more than a predetermined number of exemplars; and

labeling clusters within the truncated hierarchy.

2. The method of claim 1, wherein the predetermined number of exemplars is one exemplar.

3. The method of claim 1, wherein generating the truncated hierarchy comprises successively merging clusters together according to a predetermined entropic similarity condition.

4. The method of claim 3, wherein successively merging clusters together comprises:

characterizing pairs of each of the plurality of clusters according to a predetermined entropic similarity metric;

determining which cluster pairs have an entropic similarity characteristic that satisfies the predetermined entropic similarity condition;

selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition and that contains no more than the predetermined number of exemplars; and

merging the selected cluster pair into a single cluster.

5. The method of claim 4, further comprising:

creating a new dendrogram layer, the new taxonomy layer including the merged cluster pair;

isomorphically mapping all non-merged clusters into the new taxonomy layer; and

repeating the characterizing, determining, selecting, merging, creating, and isomorphically mapping until the number of clusters in the new taxonomy layer is equal to the number of predetermined exemplars within the augmented dataset.

6. The method of claim 4, wherein selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition comprises selecting a cluster pair that has a minimum entropic divergence.

7. The method of claim 4, wherein selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition comprises selecting a cluster pair that has a maximum entropic proximity.

8. The method of claim 1, further comprising:

representing an uppermost layer of the truncated hierarchy as an intermediate taxonomy layer; and

generating a non-truncated hierarchy from clusters within the intermediate taxonomy layer, wherein clusters within the non-truncated hierarchy contain more than the predetermined number of exemplars.

9. The method of claim 8, wherein generating the non-truncated hierarchy comprises successively merging pairs of clusters together according to a predetermined entropic similarity condition.

10. A computer program product comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect:

augmenting a dataset containing a plurality of records with a plurality of predetermined exemplars;

representing the plurality of records and predetermined exemplars within the augmented dataset as a plurality of clusters in an initial taxonomy layer;

generating a truncated hierarchy of cluster sets based on clusters within the initial taxonomy layer, wherein clusters within the truncated hierarchy contain no more than a predetermined number of exemplars; and

labeling clusters within the truncated hierarchy.

11. The computer program product of claim 10, wherein the predetermined number of exemplars is one exemplar.

12. The computer program product of claim 10, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect generating the truncated hierarchy by successively merging pairs of clusters together according to a predetermined entropic similarity condition.

13. The computer program product of claim 12, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect:

characterizing pairs of each of the plurality of clusters according to a predetermined entropic similarity metric;

determining which cluster pairs have a entropic similarity characteristic that satisfies the predetermined entropic similarity condition;

selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition and that contains no more than the predetermined number of exemplars; and

merging the selected cluster pair into a single cluster.

14. The computer program product of claim 13, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect:

creating a new dendrogram layer, the new taxonomy layer including the merged cluster pair;

isomorphically mapping all non-merged clusters into the new taxonomy layer; and

repeating the characterizing, determining, selecting, merging, creating, and isomorphically mapping until the number of clusters in the new taxonomy is equal to the number of predetermined exemplars within the augmented dataset.

15. The computer program product of claim 13, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition by selecting a cluster pair that has a minimum entropic divergence.

16. The computer program product of claim 13, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect selecting a cluster pair characterized by a value of the predetermined entropic similarity metric that satisfies the predetermined entropic similarity condition by selecting a cluster pair that has a maximum entropic proximity.

17. The computer program product of claim 10, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect:

representing an uppermost layer of the truncated hierarchy as an intermediate taxonomy layer; and

generating a non-truncated hierarchy from clusters within the intermediate taxonomy layer, wherein clusters within the non-truncated hierarchy contain more than the predetermined number of exemplars.

18. The computer program product of claim 17, further comprising a computer usable medium having computer readable code embodied therein for causing a computer to effect generating the non-truncated hierarchy comprises successively merging pairs of clusters together according to a predetermined entropic similarity condition.