Method and apparatus for cluster exploration and visualization

• US 6,100,901 A
• Filed: 06/22/1998
• Issued: 08/08/2000
• Est. Priority Date: 06/22/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mohda, Dharmendra Shantilal, Spangler, William Scott, Vaithyanathan, Shivakumar, Martin, David Charles
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US09/102,087
• Time in Patent Office: 778 Days
• Field of Search: 345/440, 345/427, 707/6
• US Class Current: 345/440
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/66 of image moments or centre of gravity

Abstract

A method and apparatus for visualizing a multi-dimensional data set in which the multi-dimensional data set is clustered into k clusters, with each cluster having a centroid. Then, either two distinct current centroids or three distinct non-collinear current centroids are selected. A current 2-dimensional cluster projection is generated based on the selected current centroids. In the case when two distinct current centroids are selected, two distinct target centroids are selected, with at least one of the two target centroids being different from the two current centroids. In the case when three distinct current centroids are selected, three distinct non-collinear target centroids are selected, with at least one of the three target centroids being different from the three current centroids. An intermediate 2-dimensional cluster projection is generated based on a set of interpolated centroids, with each interpolated centroid corresponding to a current centroid and to a target centroid associated with the current centroid. Each interpolated centroid is interpolated between the corresponding current centroid and the target centroid associated with the current centroid. Alternatively, the intermediate 2-dimensional cluster projection is generated based on an interpolated 2-dimensional nonlinear cluster projection that is based on the selected current centroids and the selected target centroids.

Claims

1. A method for visualizing a multi-dimensional data set, the method comprising the steps of:

clustering the multi-dimensional data set into k clusters, each cluster having a centroid;

selecting one of two distinct current centroids and three distinct non-collinear current centroids;

generating a current 2-dimensional cluster projection based on the selected current centroids;

selecting two distinct target centroids when two distinct current centroids are selected, at least one of the two target centroids being different from the two current centroids;

selecting three distinct non-collinear target centroids when three distinct non-collinear current centroids are selected, at least one of the three target centroids being different from the three current centroids; and

generating an intermediate 2-dimensional cluster projection based on the current centroids and the target centroids.

2. The method according to claim 1, further comprising the step of associating each current centroid with a target centroid, and

wherein the step of generating the intermediate 2-dimensional cluster projection is based on a set of interpolated centroids, each interpolated centroid of the set of interpolated centroids corresponding to a current centroid and to the target centroid associated with the current centroid, and each interpolated centroid being interpolated between the corresponding current centroid and the associated target centroid.

3. The method according to claim 2, wherein the set of interpolated centroids varies between the current centroids and the target centroids based on a value of an interpolation parameter.

4. The method according to claim 3, wherein step of generating the intermediate 2-dimensional cluster projection is repeated for different values of the interpolation parameter.

5. The method according to claim 4, wherein the value of the interpolation parameter is monotonically increased when repeatedly generating the intermediate 2-dimensional cluster projection, thereby generating a holistic image of the multi-dimensional data set with respect to the current centroids and the target centroids.

6. The method according to claim 5, further comprising the steps of:

defining the selected target centroids to be new current centroids;

selecting two distinct new target centroids when two new current centroids are defined from the selected target centroids, at least one of the two distinct new target centroids being different from the two new current centroids;

selecting three distinct non-collinear new target centroids when three distinct non-collinear new current centroids are defined from the selected target centroids, at least one of the three distinct non-collinear new target centroids being different from the three distinct non-collinear new current centroids;

associating each new current centroid with a new target centroid; and

generating the intermediate 2-dimensional cluster projection based on a set of new interpolated centroids, each interpolated centroid of the new set of interpolated centroids corresponding to a new current centroid and to the new target centroid associated with the new current centroid, and each new interpolated centroid being interpolated between the corresponding new current centroid and t he associated new target centroid.

7. The method according to claim 6, where in the steps of defining new current centroids, selecting new target centroids, associating each new current centroid with a new target centroid, and generating the intermediate 2-dimensional cluster projection are performed repeatedly, thereby generating a holistic image of the multi-dimensional data set with respect to each set of current centroids and the associated target centroids.

8. The method according to claim 7, further comprising the steps of:

calculating an average least-squares reconstruction error for at least one 2-dimensional cluster projection;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing each average least-square reconstruction error an d the average least-square construction error based on the truncated singular value decomposition of the data set.

9. The method according to claim 8, further comprising the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

10. The method according to claim 1, where in t he step of generating the intermediate 2-dimensional cluster projection generates an interpolated 2-dimensional nonlinear cluster projection based on the selected current centroids and the selected target centroids.

11. The method according to claim 10, wherein intermediate 2-dimensional cluster projection is further based on a value of an interpolation parameter.

12. The method according to claim 11, wherein step of generating the intermediate 2-dimensional cluster projection is repeated for different values of the interpolation parameter.

13. The method according to claim 12, wherein the value of the interpolation parameter is monotonically increased when repeatedly generating the intermediate 2-dimensional cluster projection, thereby generating a holistic image of the multi-dimensional data set with respect to the current centroids and the target centroids.

14. The method according to claim 13, the step of repeatedly generating the intermediate 2-dimensional cluster projection for different values of the interpolation parameter generates a plurality of 2-dimensional cluster projections that follows a geodesic path between the current centroids and the target centroids.

15. The method according to claim 13, further comprising the steps of:

defining the selected target centroids to be new current centroids;

selecting two distinct new target centroids when two new current centroids are defined from the selected target centroids, at least one of the two distinct new target centroids being different from the two new current centroids;

selecting three distinct non-collinear new target centroids when three distinct non-collinear new current centroids are defined from the selected target centroids, at least one of the three distinct non-collinear new target centroids being different from the three distinct non-collinear new current centroids; and

generating the intermediate 2-dimensional cluster projection based on the new current centroids and the new target centroids.

16. The method according to claim 15, where in the steps of defining new current centroids, selecting new target centroids and generating the intermediate 2-dimensional cluster projection are performed repeatedly, thereby generating a holistic image of the multi-dimensional data set with respect to each set of current centroids and the target centroids.

17. The method according to claim 16, further comprising the steps of:

calculating a n average least-squares reconstruction error for at least one 2-dimensional cluster projection;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing each average least-square reconstruction error and the average least-square construction error based on the truncated singular value decomposition of the data set.

18. The method according to claim 17, further comprising the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

19. The method according to claim 1, further comprising the steps of:

calculating an average least-squares reconstruction error for a 2-dimensional cluster projection when two distinct current centroids are selected;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

20. The method according to claim 19, further comprising the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

21. 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 for visualizing a multi-dimensional data set, the method comprising the steps of;

clustering the multi-dimensional data set into k clusters, each cluster having a centroid;

selecting one of two distinct current centroids and three distinct non-collinear current centroids;

generating a current 2-dimensional cluster projection based on the selected current centroids;

selecting two distinct target centroids when two distinct current centroids are selected, at least one of the two target centroids being different from the two current centroids;

selecting three distinct non-collinear target centroids when three distinct non-collinear current centroids are selected, at least one of the three target centroids being different from the three current centroids; and

generating an intermediate 2-dimensional cluster projection based on the current centroids and the target centroids.

22. The program storage device according to claim 21, wherein the method further comprises the step of associating each current centroid with a target centroid, and

wherein the step of generating the intermediate 2-dimensional cluster projection is based on a set of interpolated centroids, each interpolated centroid of the set of interpolated centroids corresponding to a current centroid and to the target centroid associated with the current centroid, and each interpolated centroid being interpolated between the corresponding current centroid and the associated target centroid.

23. The program storage device according to claim 22, wherein the set of interpolated centroids varies between the current centroids and the target centroids based on a value of an interpolation parameter.

24. The program storage device according to claim 23, wherein step of generating the intermediate 2-dimensional cluster projection is repeated for different values of the interpolation parameter.

25. The program storage device according to claim 24, wherein the value of the interpolation parameter is monotonically increased when repeatedly generating the intermediate 2-dimensional cluster projection, thereby generating a holistic image of the multi-dimensional data set with respect to the current centroids and the target centroids.

26. The program storage device according to claim 25, wherein the method further comprises the steps of:

defining the selected target centroids to be new current centroids;

selecting two distinct new target centroids when two new current centroids are defined from the selected target centroids, at least one of the two distinct new target centroids being different from the two new current centroids;

selecting three distinct non-collinear new target centroids when three distinct non-collinear new current centroids are defined from the selected target centroids, at least one of the three distinct non-collinear new target centroids being different from the three distinct non-collinear new current centroids;

associating each new current centroid with a new target centroid; and

generating the intermediate 2-dimensional cluster projection based on a set of new interpolated centroids, each interpolated centroid of the new set of interpolated centroids corresponding to a new current centroid and to the new target centroid associated with the new current centroid, and each new interpolated centroid being interpolated between the corresponding new current centroid and the associated new target centroid.

27. The program storage device according to claim 26, wherein the steps of defining new current centroids, selecting new target centroids, associating each new current centroid with a new target centroid, and generating the intermediate 2-dimensional cluster projection are performed repeatedly, thereby generating a holistic image of the multi-dimensional data set with respect to each set of current centroids and the associated target centroids.

28. The program storage device according to claim 27, wherein the method further comprises the steps of:

calculating an average least-squares reconstruction error for at least one 2-dimensional cluster projection;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing each average least-square reconstruction error and the average least-square construction error based on the truncated singular value decomposition of the data set.

29. The program storage device according to claim 28, wherein the method further comprises the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

30. The program storage device according to claim 21, the step of generating the intermediate 2-dimensional cluster projection generates an interpolated 2-dimensional nonlinear cluster projection based on the selected current centroids and the selected target centroids.

31. The program storage device according to claim 30, wherein intermediate 2-dimensional cluster projection is further based on a value of an interpolation parameter.

32. The program storage device according to claim 31, wherein step of generating the intermediate 2-dimensional cluster projection is repeated for different values of the interpolation parameter.

33. The program storage device according to claim 32, wherein the value of the interpolation parameter is monotonically increased when repeatedly generating the intermediate 2-dimensional cluster projection, thereby generating a holistic image of the multi-dimensional data set with respect to the current centroids and the target centroids.

34. The program storage device according to claim 33, the step of repeatedly generating the intermediate 2-dimensional cluster projection for different values of the interpolation parameter generates a plurality of 2-dimensional cluster projections that follows a geodesic path between the current centroids and the target centroids.

35. The program storage device according to claim 33, wherein the method further comprises the steps of:

defining the selected target centroids to be new current centroids;

selecting two distinct new target centroids when two new current centroids are defined from the selected target centroids, at least one of the two distinct new target centroids being different from the two new current centroids;

selecting three distinct non-collinear new target centroids when three distinct non-collinear new current centroids are defined from the selected target centroids, at least one of the three distinct non-collinear new target centroids being different from the three distinct non-collinear new current centroids; and

generating the intermediate 2-dimensional cluster projection based on the new current centroids and the new target centroids.

36. The program storage device according to claim 35, wherein the steps of defining new current centroids, selecting new target centroids and generating the intermediate 2-dimensional cluster projection are performed repeatedly, thereby generating a holistic image of the multi-dimensional data set with respect to each set of current centroids and the target centroids.

37. The program storage device according to claim 36, wherein the method further comprises the steps of:

calculating an average least-squares reconstruction error for at least one 2-dimensional cluster projection;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing each average least-square reconstruction error and the average least-square construction error based on the truncated singular value decomposition of the data set.

38. The program storage device according to claim 37, wherein the method further comprises the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

39. The program storage device according to claim 21, wherein the method further comprises the steps of:

calculating an average least-squares reconstruction error for a 2-dimensional cluster projection when two distinct current centroids are selected;

calculating an average least-squares reconstruction error based on a truncated singular value decomposition of the data set; and

comparing the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.

40. The program storage device according to claim 39, the method further comprises the step of displaying the comparison of the average least-square reconstruction error for the 2-dimensional cluster projection and the average least-square construction error based on the truncated singular value decomposition of the data set.