Clustering and classification of multimedia data

• US 20070271287A1
• Filed: 05/16/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: Ohwa, Tsunayuki, Plutowski, Mark, Purang, Khemdut, Acharya, Chiranjit, Usuki, Takashi
• Granted Patent: US 7,774,288 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

Abstract

Records including category data is clustered by representing the data as a plurality of clusters, and generating a hierarchy of clusters based on the clusters. Records including category data are classified into folders according to a predetermined entropic similarity condition.

Claims

1. A computerized method comprising:

representing records as a hierarchy of clusters, wherein category data is defined in a vector space comprising multiple attributes, and wherein the records comprise category data.

2. The method of claim 1, further comprising:

successively merging clusters together according to a predetermined entropic similarity condition.

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

determining a cluster pair that has an entropic similarity characteristic value that satisfies the predetermined entropic similarity condition; and

merging the selected cluster pair into a single cluster.

4. The method of claim 3, further comprising:

representing the merged cluster pair in a hierarchy layer; and

mapping non-merged clusters into the hierarchy layer.

5. The method of claim 3, wherein selecting a cluster pair comprises selecting a cluster pair that has a minimum entropic divergence.

6. The method of claim 3, wherein selecting a cluster pair comprises selecting a cluster pair that has a maximum entropic proximity.

7. The method of claim 1, further comprising:

mapping each record onto a system ontology; and

cleaning at least one record.

8. The method of claim 7, wherein cleaning a record comprises at lease one of removing terms from attributes of the record, splitting attributes of the record into a plurality of sub-attributes, and replacing terms in attributes of the record.

9. The method of claim 1, further comprising:

generating a distance matrix representing possible combinations of clusters present within a current hierarchy layer.

10. A machine-readable medium having executable instructions to a cause a machine to perform a method comprising:

representing records as a hierarchy of clusters, wherein category data is defined in a vector space comprising multiple attributes, and wherein the records comprise category data.

11. The machine-readable medium of claim 10, wherein the method further comprises:

successively merging clusters together according to a predetermined entropic similarity condition.

12. The machine-readable medium of claim 11, wherein the method further comprises:

determining a cluster pair that has an entropic similarity characteristic value that satisfies the predetermined entropic similarity condition; and

merging the selected cluster pair into a single cluster.

13. The machine-readable medium of claim 12, wherein the method further comprises:

representing the merged cluster pair in a hierarchy layer; and

mapping non-merged clusters into the hierarchy layer.

14. The machine-readable medium of claim 12, wherein selecting a cluster pair comprises selecting a cluster pair that has a minimum entropic divergence.

15. The machine-readable medium of claim 12, wherein selecting a cluster pair comprises selecting a cluster pair that has a maximum entropic proximity.

16. The machine-readable medium of claim 10, wherein the method further comprises:

mapping each record onto a system ontology; and

cleaning at least one record.

17. The machine-readable medium of claim 16, wherein cleaning a record comprises at lease one of removing terms from attributes of the record, splitting attributes of the record into a plurality of sub-attributes, and replacing terms in attributes of the record.

18. The machine-readable medium of claim 10, wherein the method further comprises:

generating a distance matrix representing possible combinations of clusters present within a current hierarchy layer.

19. A computerized system comprising:

a processor coupled to a memory through a bus; and

a process executed from the memory by the processor to cause the processor to;

represent records as a hierarchy of clusters, wherein category data is defined in a vector space comprising multiple attributes, and wherein the records comprise category data.

20. The system of claim 19, wherein the process further causes the process to:

successively merge clusters together according to a predetermined entropic similarity condition.

21. The method of claim 20, wherein the process further causes the process to:

determine a cluster pair that has an entropic similarity characteristic value that satisfies the predetermined entropic similarity condition; and

merge the selected cluster pair into a single cluster.

22. The system of claim 21, wherein the process further causes the process to:

represent the merged cluster pair in a hierarchy layer; and

map non-merged clusters into the hierarchy layer.

23. The system of claim 21, wherein selecting a cluster pair comprises selecting a cluster pair that has a minimum entropic divergence.

24. The system of claim 21, wherein selecting a cluster pair comprises selecting a cluster pair that has a maximum entropic proximity.

25. The system of claim 19, wherein the process further causes the process to:

map each record onto a system ontology; and

clean at least one record.

26. The system of claim 25, wherein cleaning a record comprises at lease one of removing terms from attributes of the record, splitting attributes of the record into a plurality of sub-attributes, and replacing terms in attributes of the record.

27. The system of claim 19, wherein the process further causes the process to:

generate a distance matrix representing possible combinations of clusters present within a current hierarchy layer.

28. An apparatus comprising:

means for representing records as a plurality of clusters, wherein category data is defined in a vector space comprising multiple attributes, and wherein the records comprise category data; and

means for generating a hierarchy of clusters based on the plurality of clusters.

29. The apparatus of claim 28, wherein means for generating the hierarchy comprises means for successively merging clusters together according to a predetermined entropic similarity condition.

30. The apparatus of claim 29, wherein means for successively merging clusters together comprises:

means for selecting a cluster pair that has an entropic similarity characteristic that satisfies the predetermined entropic similarity condition; and

means for merging the selected cluster pair into a single cluster.

31. The apparatus of claim 28, further comprising:

means for representing the merged cluster pair as a new hierarchy layer; and

means for isomorphically mapping all non-merged clusters into the new taxonomy layer.

32. The apparatus of claim 30, wherein means for selecting a cluster pair comprises one of means for selecting a cluster pair that has a minimum entropic divergence and a maximum entropic proximity.

33. The apparatus of claim 28, wherein means for generating a hierarchy of clusters comprises:

means for computing a distance matrix including possible combinations of clusters present within a current taxonomy layer.

34. A computerized method comprising:

classifying records comprising category data into a plurality of folders according to a predetermined entropic similarity condition, wherein category data is defined in a vector space comprising multiple attributes.

35. The method of claim 34, wherein the plurality of folders is user-defined.

36. The method of claim 35, further comprising:

creating a distance matrix listing representing possible record and folder combinations.

37. The method of claim 35, further comprising:

assigning labels to folders within the plurality of folders.

38. The method of claim 34, further comprising:

creating a conditional likelihood matrix from the distance matrix, the conditional likelihood matrix representing a probability of occurrence of a folder relative to a given record.

39. The method of claim 36, wherein the record is classified in more than one folder.

40. The method of claim 34, further comprising:

creating a binary assignment matrix, wherein every record is classified in a single folder.

41. A machine-readable medium having executable instructions to cause a processor to perform a method, the method comprising:

classifying records into a plurality of folders according to a predetermined entropic similarity condition, wherein category data is defined in a vector space comprising multiple attributes, and wherein the records comprise category data.

42. The machine-readable medium of claim 41, wherein the plurality of folders is user-defined.

43. The machine-readable medium of claim 42, wherein the method further causes the processor to create a distance matrix listing representing possible record and folder combinations.

44. The machine-readable medium of claim 41, wherein the method further causes the processor to assign labels to the folders.

45. The machine-readable medium of claim 41, wherein the method further causes the processor to create a conditional likelihood matrix from the distance matrix listing probability of occurrence of folder, given a record.

46. The machine-readable medium of claim 43, wherein the record is classified in more than one folder.

47. The machine-readable medium of claim 43, wherein the method further causes the processor to create a binary assignment matrix, wherein every record is classified in a single folder.

48. An apparatus comprising:

means for determining a plurality of folders; and

means for classifying records into the plurality of folders according to a predetermined entropic similarity condition, wherein the records comprise category data.

49. The apparatus of claim 48, wherein initializing comprises means for receiving a user-defined plurality of folders.

50. The apparatus of claim 48, further comprising:

means for creating a distance matrix listing representing possible record and folder combinations;

means for assigning labels to folders; and

means for creating a conditional likelihood matrix from the distance matrix listing a probability of occurrence of a folder relative to a given folder.

51. A computer system comprising:

a processor coupled to a memory through a bus; and

a process executed from the memory by the processor to cause the processor to;

classify records into a plurality of folders according to a predetermined entropic similarity condition, wherein the records comprise category data.

52. The computer system of claim 51, wherein the process further causes the processor to receive a user-defined plurality of folders.

53. The computer system of claim 51, wherein the process further causes the processor to:

create a distance matrix representing possible record and folder combinations;

assign labels to the folders; and

compute a conditional likelihood matrix from the distance matrix listing a probability of occurrence of a folder relative to a given record.