Optimal taxonomy layer selection method

• US 7,640,220 B2
• Filed: 07/12/2006
• Issued: 12/29/2009
• Est. Priority Date: 05/16/2006
• Status: Expired due to Fees

• Current Assignee: 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: Acharya, Chiranjit
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Kennedy; Adrian L
• Application Number:
  US11/457,095
• Publication Number:
  US 20070271279A1
• Time in Patent Office: 1,266 Days
• Field of Search: None
• US Class Current: 706/45
• 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: 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 an optimal layer of a taxonomy includes obtaining a taxonomy including a hierarchical arrangement of layers, wherein each layer represents a cluster set containing at least one cluster, wherein each cluster represents at least one record within a dataset; identifying a range of taxonomy layers based on a measure of intra-cluster homogeneity of each cluster within the taxonomy; selecting a taxonomy layer within the identified range as an optimal layer of the taxonomy, the selecting being based on a measure of inter-cluster heterogeneity between clusters of a taxonomy layer within the identified range; and labeling clusters within the optimal layer of the taxonomy.

Claims

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

obtaining a taxonomy including a hierarchical arrangement of layers, wherein each layer represents a cluster set containing at least one cluster, wherein each cluster represents at least one record within a dataset;

identifying a range of taxonomy layers based on a measure of intra-cluster homogeneity of each cluster within the taxonomy;

selecting a taxonomy layer within the identified range as an optimal layer of the taxonomy, the selecting being based on a measure of inter-cluster heterogeneity between clusters of a taxonomy layer within the identified range; and

labeling clusters within the optimal layer of the taxonomy;

wherein selecting a taxonomy layer within the identified range as an optimal layer of the taxonomy comprises;

marking all taxonomy layers within the identified range having a measure of inter-cluster heterogeneity that satisfies a first predetermined condition;

selecting a marked taxonomy layer closest to a lower bound of the identified range; and

wherein the computerized method of representing a dataset with a taxonomy occurs within a physical computer.

2. The method of claim 1, wherein identifying a range of taxonomy layers comprises:

identifying a first taxonomy layer having a measure of intra-cluster homogeneity that satisfies a second predetermined condition as a lower bound of the range; and

identifying a second taxonomy layer having a measure of intra-cluster homogeneity that satisfies a third predetermined condition as an upper bound of the range.

3. The method of claim 2, wherein the second predetermined condition is satisfied when the measure of intra-cluster homogeneity for a taxonomy layer exhibits a first concavity.

4. The method of claim 3, wherein the measure of intra-cluster homogeneity comprises a value of a first order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

5. The method of claim 3, wherein the measure of intra-cluster homogeneity comprises a value of a second order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

6. The method of claim 2, wherein the third predetermined condition is satisfied when the measure of intra-cluster homogeneity for a taxonomy layer exhibits a beginning of an asymptotic tail.

7. The method of claim 6, wherein the measure of intra-cluster homogeneity comprises a value of a first order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

8. The method of claim 1, wherein the first predetermined condition is satisfied when the measure of inter-cluster heterogeneity for a taxonomy layer is locally concave or has a local minima.

9. The method of claim 1, wherein the third predetermined condition is satisfied when a first order differential of the measure of inter-cluster heterogeneity for a taxonomy layer is locally convex or has a local maxima.

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

obtaining a taxonomy including a hierarchical arrangement of layers, wherein each layer represents a cluster set containing at least one cluster, wherein each cluster represents at least one record within a dataset;

identifying a range of taxonomy layers based on a measure of intra-cluster homogeneity of each cluster within the taxonomy;

selecting a taxonomy layer within the identified range as an optimal layer of the taxonomy, the selecting being based on a measure of inter-cluster heterogeneity between clusters of a taxonomy layer within the identified range; and

labeling clusters within the optimal layer of the taxonomy;

wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect selecting a taxonomy layer within the identified range as an optimal layer of the taxonomy by;

marking all taxonomy layers within the identified range having a measure of inter-cluster heterogeneity that satisfies a first predetermined condition; and

selecting a marked taxonomy layer closest to a lower bound of the identified range.

11. The computer program product of claim 10, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect identifying a range of taxonomy layers by:

identifying a first taxonomy layer having a measure of intra-cluster homogeneity that satisfies a second predetermined condition as a lower bound of the range; and

identifying a second taxonomy layer having a measure of intra-cluster homogeneity that satisfies a third predetermined condition as an upper bound of the range.

12. The computer program product of claim 11, wherein the second predetermined condition is satisfied when the measure of intra-cluster homogeneity for a taxonomy layer exhibits a first concavity.

13. The computer program product of claim 12, wherein the measure of intra-cluster homogeneity comprises a value of a first order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

14. The computer program product of claim 12, wherein the measure of intra-cluster homogeneity comprises a value of a second order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

15. The computer program product of claim 11, wherein the third predetermined condition is satisfied when the measure of intra-cluster homogeneity for a taxonomy layer exhibits a beginning of an asymptotic tail.

16. The computer program product of claim 15, wherein the measure of intra-cluster homogeneity comprises a value of a first order differential of mutual information between an attribute space defined by the dataset and a taxonomy layer.

17. The computer program product of claim 10, wherein the first predetermined condition is satisfied when the measure of inter-cluster heterogeneity for a taxonomy layer is locally concave or has a local minima.

18. The computer program product of claim 10, wherein the first predetermined condition is satisfied when a first order differential of the measure of inter-cluster heterogeneity for a taxonomy layer is locally convex or has a local maxima.