Clustering mixed attribute patterns

• US 6,260,038 B1
• Filed: 09/13/1999
• Issued: 07/10/2001
• Est. Priority Date: 09/13/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Martin, David C., Modha, Dharmendra Shantilal, Vaithyanathan, Shivakumar
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Corrielus, Jean M
• Application Number:
  US09/394,883
• Time in Patent Office: 666 Days
• Field of Search: 707/7, 707/6, 707/101, 707/2, 707/5, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A technique for clustering data points in a data set that is arranged as a matrix having n objects and m attributes. Each categorical attribute of the data set is converted to a 1-of-p representation of the categorical attribute. A converted data set A is formed based on the data set and the 1-of-p representation for each categorical attribute. The converted data set A is compressed using, for example, a Goal Directed Projection compression technique or a Singular Value Decomposition compression technique, to obtain q basis vectors, with q being defined to be at least m+1. The transformed data set is projected onto the q basis vectors to form a data matrix having at least one vector, with each vector having q dimensions. Lastly, a clustering technique is performed on the data matrix having vectors having q dimensions.

Claims

1. A method performed by a computer for clustering data points in a data set, the data set being arranged as a matrix having n objects and m attributes, the method comprising the steps of:

converting each categorical attribute of the data set to a 1-of-p representation of the categorical attribute;

forming a converted data set A based on the data set and the 1-of-p representation for each categorical attribute;

compressing the converted data set A to obtain q basis vectors, with q being defined to be at least m+1;

projecting the converted data set onto the q basis vectors to form a data matrix having at least one vector, each vector having q dimensions; and

performing a clustering technique on the data matrix having vectors having q dimensions.

2. The method according to claim 1, wherein the step of compressing uses a Goal Directed Projection compression technique.

3. The method according to claim 1, wherein the step of compressing uses a Singular Value Decomposition compression technique.

4. The method according to claim 1, wherein the step of compressing the converted data set includes the steps of:

partitioning the objects into k cohesive groups, with k being less than m; and

computing a distance from each object to a centroid of each group.

5. The method according to claim 4, wherein the step of partitioning uses a k-means technique for clustering the data points of the converted data set.

6. The method according to claim 5, wherein the k-means techique uses one of a Euclidean metric, a city-block metric and a cosine similarity metric for a distance measure.

7. The method according to claim 5, wherein the step of clustering uses an expectation maximization clustering technique.

8. The method according to claim 5, wherein the step of partitioning uses a sample of the converted data set.

9. The method according to claim 5, wherein the step of computing the distance from each data point to the centroid of each group uses a different distance measure for each prototype vector.

10. The method according to claim 1, wherein the step of compressing the converted data set includes the steps of:

subtracting a mean of the converted data set from each object of the converted data set;

partitioning the objects into k cohesive groups, with k being less than m; and

computing a distance from each object to a centroid of each group.

11. The method according to claim 1, wherein the data set includes at least one attribute having a categorical portion and a corresponding real portion,

wherein the step of converting each categorical attribute includes the steps of:

separating the categorical portion of each respective attribute from the corresponding real portion of the attribute, and

converting the categorical portion of each attribute to a 1-of-p representation,

wherein the step of compressing the converted data set A compresses the converted categorical portion of each attribute,

the method further comprising the step of combining each vector having q dimensions with the associated real portion of each attribute before the step of projecting the converted data set, and

wherein the step of performing the clustering technique is performed on a data matrix resulting from the step of combining each vector having q dimensions with the corresponding real portion of each attribute.

12. The method according to claim 1, wherein the data set includes at least one attribute having a categorical portion and a corresponding real portion,

wherein the step of converting each categorical attribute includes the steps of:

separating the categorical portion of each respective attribute from the corresponding real portion of the attribute,

converting the categorical portion of each respective attribute to a 1-of-p representation, and

combining the 1-of-p representation of the categorical portion and the corresponding real portion of each respective attribute, and

wherein the step of compressing the converted data set A compresses the combined categorical 1-of-p representation of the categorical portion and the corresponding real portion of each respective attribute.

13. The method according to claim 1, further comprising a step of computer visualizing the data points of the clustered data matrix set based on selected attributes of the data set.

14. The method according to claim 1, further comprising a step of computer mining the data points of the clustered data matrix based on selected attributes of the data set.

15. The method according to claim 1, further comprising a step of computer summarizing the clustered data matrix based on selected attributes of the data set.

16. A program storage device comprising:

a storage area; and

information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps comprising;

converting each categorical attribute of a data set to a 1-of-p representation of the categorical attribute, the data set being arranged as a matrix having n objects and m attributes;

forming a converted data set A based on the data set and the 1-of-p representation for each categorical attribute;

compressing the converted data set A to obtain q basis vectors, with q being defined to be at least m+1;

projecting the converted data set onto the q basis vectors to form a data matrix having at least one vector, each vector having q dimensions; and

performing a clustering technique on the data matrix having vectors having q dimensions.

17. The program storage device according to claim 16, wherein the step of compressing uses a Goal Directed Projection compression technique.

18. The program storage device according to claim 16, wherein the step of compressing uses a Singular Value Decomposition compression technique.

19. The program storage device according to claim 16, wherein the step of compressing the converted data set includes the steps of:

partitioning the objects into k cohesive groups, with k being less than m; and

computing a distance from each object to a centroid of each group.

20. The program storage device according to claim 19, wherein the step of partitioning uses a k-means technique for clustering the data points of the converted data set.

21. The program storage device according to claim 20, wherein the k-means technique uses one of a Euclidean metric, a city-block metric and a cosine similarity metric for a distance measure.

22. The program storage device according to claim 20, wherein the step of clustering uses an expectation maximization clustering technique.

23. The program storage device according to claim 20, wherein the step of partitioning uses a sample of the converted data set.

24. The program storage device according to claim 20, wherein the step of computing the distance from each data point to the centroid of each group uses a different distance measure for each prototype vector.

25. The program storage according to claim 16, wherein the step of compressing the converted data set includes the steps of:

subtracting a mean of the converted data set from each object of the converted data set;

partitioning the objects into k cohesive groups, with k being less than m; and

computing a distance from each object to a centroid of each group.

26. The program storage device according to claim 16, wherein the data set includes at least one attribute having a categorical portion and a corresponding real portion,

wherein the step of converting each categorical attribute includes the steps of:

separating the categorical portion of each respective attribute from the corresponding real portion of the attribute, and

converting the categorical portion of each attribute to a 1-of-p representation,

wherein the step of compressing the converted data set A compresses the converted categorical portion of each attribute,

the method further comprising the step of combining each vector having p dimensions with the associated real portion of each attribute before the step of projecting the transformed data set, and

wherein the step of performing the clustering technique is performed on a data matrix resulting from the step of combining each vector having q dimensions with the corresponding real portion of each attribute.

27. The program storage device according to claim 16, wherein the data set includes at least one attribute having a categorical portion and a corresponding real portion,

wherein the step of converting each categorical attribute includes the steps of:

separating the categorical portion of each respective attribute from the corresponding real portion of the attribute,

converting the categorical portion of each respective attribute to a 1-of-p representation, and

combining the 1-of-p representation of the categorical portion and the corresponding real portion of each respective attribute, and

wherein the step of compressing the converted data set A compresses the combined categorical 1-of-p representation of the categorical portion and the corresponding real portion of each respective attribute.

28. The program storage device according to claim 16, further comprising a step of computer visualizing the data points of the data set based on selected attributes of the data set.

29. The program storage device according to claim 16, further comprising a step of computer mining the data points of the clustered data matrix based on selected attributes of the data set.

30. The program storage device according to claim 16, further comprising a step of computer summarizing the clustered data matrix based on selected attributes of the data set.