Method and System for Subspace Bounded Recursive Clustering of Categorical Data

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

• 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
• Granted Patent: US 8,055,597 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 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

A computerized method of representing a dataset includes obtaining a dataset, the dataset defining an attribute space; decomposing the attribute space into a plurality of attribute subspaces; generating a parent taxonomy of the obtained dataset with respect to one of the plurality of attribute subspaces, the parent taxonomy organizing the obtained dataset into a plurality of data subsets; generating a child taxonomy with respect to another one of the plurality of attribute subspaces, the child taxonomy organizing each of the plurality of data subsets within the parent taxonomy into at least one data subset; iteratively repeating generating the child taxonomy until a predetermined termination condition is satisfied, wherein the child taxonomy of a preceding iteration is the parent taxonomy of the current iteration; and assigning category labels to the data subsets.

Claims

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

obtaining a dataset, the dataset defining an attribute space;

decomposing the attribute space into a plurality of attribute subspaces;

generating a parent taxonomy of the obtained dataset with respect to one of the plurality of attribute subspaces, the parent taxonomy organizing the obtained dataset into a plurality of data subsets;

generating a child taxonomy with respect to another one of the plurality of attribute subspaces, the child taxonomy organizing each of the plurality of data subsets within the parent taxonomy into at least one data subset;

iteratively repeating generating the child taxonomy until a predetermined termination condition is satisfied, wherein the child taxonomy of a preceding iteration is the parent taxonomy of the current iteration; and

assigning category labels to the data subsets.

2. The method of claim 1, further comprising decomposing the attribute space into a plurality of attribute subspaces such that two attribute subspaces share an attribute.

3. The method of claim 1, further comprising decomposing the attribute space into a plurality of attribute subspaces such that two attribute subspaces do not share an attribute.

4. The method of claim 1, wherein generating a child taxonomy comprises decomposing each data subset of the parent taxonomy into a set, wherein each set comprises at least one data subset.

5. The method of claim 4, wherein decomposing each data subset comprises performing a clustering process with respect to the data subset.

6. The method of claim 5, wherein performing a clustering process comprises performing a hierarchical clustering process with respect to the data subset.

7. The method of claim 6, wherein performing a hierarchical clustering process comprises performing a hierarchical agglomerative clustering process with respect to the data subset.

8. The method of claim 6, wherein performing a hierarchical clustering process comprises selecting a layer of clusters as the set.

9. The method of claim 1, further comprising:

removing the parent taxonomy; and

replacing the removed parent taxonomy with the child taxonomy.

10. The method of claim 1, further comprising:

retaining the parent taxonomy; and

linking data subsets within the parent taxonomy with sets of data subsets within the child taxonomy.

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

obtaining a dataset, the dataset defining an attribute space;

decomposing the attribute space into a plurality of attribute subspaces;

generating a parent taxonomy of the obtained dataset with respect to one of the plurality of attribute subspaces, the parent taxonomy organizing the obtained dataset into a plurality of data subsets;

generating a child taxonomy with respect to another one of the plurality of attribute subspaces, the child taxonomy organizing each of the plurality of data subsets within the parent taxonomy into at least one data subset;

iteratively repeating generating the child taxonomy until a predetermined termination condition is satisfied, wherein the child taxonomy of a preceding iteration is the parent taxonomy of the current iteration; and

assigning category labels to the data subsets.

12. The computer program product claim 11, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect:

decomposing the attribute space into a plurality of attribute subspaces such that two attribute subspaces share an attribute.

13. The computer program product claim 11, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect:

decomposing the attribute space into a plurality of attribute subspaces such that two attribute subspaces do not share an attribute.

14. The computer program product claim 11, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect generating a child taxonomy by decomposing each data subset of the parent taxonomy into a set, wherein each set comprises at least one data subset.

15. The computer program product claim 14, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect decomposing each data subset by performing a clustering process with respect to the data subset.

16. The computer program product claim 15, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect performing a clustering process by performing a hierarchical clustering process with respect to the data subset.

17. The computer program product claim 16, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect a hierarchical clustering process by performing a hierarchical agglomerative clustering process with respect to the data subset.

18. The computer program product claim 16, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect a hierarchical clustering process by selecting a hierarchy layer as the set.

19. The computer program product claim 11, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect:

removing the parent taxonomy; and

replacing the removed parent taxonomy with the child taxonomy.

20. The computer program product claim 11, wherein the computer usable medium has computer readable code embodied therein for causing a computer to effect:

retaining the parent taxonomy; and

linking data subsets within the parent taxonomy with sets of data subsets within the child taxonomy.