Viewing multi-dimensional data through hierarchical visualization

• US 7,777,743 B2
• Filed: 03/28/2003
• Issued: 08/17/2010
• Est. Priority Date: 04/19/2002
• Status: Expired due to Fees

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Duan, Baofu, Pao, Yoh-Han, Meng, Zhuo
• Primary Examiner(s): PAPPAS, PETER
• Application Number:
  US10/402,519
• Publication Number:
  US 20030200191A1
• Time in Patent Office: 2,699 Days
• Field of Search: 345440-441, 345/619, 345/633, 345/620
• US Class Current: 345/428
• 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/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor

Abstract

A method for hierarchical visualization of multi-dimensional data is provided. A first dimension-reduction process is applied to a multi-dimensional data set to obtain a first visualization. A subset of the multi-dimensional data set associated with a selected region of the dimension-reduced first visualization is selected. A second dimension-reduction process is applied to the selected subset of the multi-dimensional data set to obtain at least one additional visualization.

Claims

1. A method for hierarchical visualization of multi-dimensional data, comprising:

receiving, with a computer processor, a multi-dimensional data set of data points dispersed into a plurality of categories, each respective category containing data points that share a common characteristic unique to the respective category;

applying, with a computer processor, a first dimension-reduction process to the multi-dimensional data set to obtain a current dimension-reduced visualization of the multi-dimensional data set;

displaying the current dimension-reduced visualization to a user, wherein displaying the current dimension-reduced visualization includes;

indicating, for each of the data points in the data set, a location based on a first set of dimensions associated with the current visualization; and

indicating a categorization of a plurality of the data points in the data set;

receiving user input that graphically selects a user-defined region of the current visualization, wherein the selected region comprises a mixed region that contains data points of different categories, including a first data point and a second data point, wherein a location of the first data point in the current visualization and a location of a second data point in the current visualization are separated by a first distance;

selecting, with a computer processor, a subset of the multi-dimensional data set, the subset including the data points contained within the selected region of the current dimension-reduced visualization;

applying, with a computer processor, an additional dimension-reduction process to the selected subset of the multi-dimensional data set to obtain a subsequent visualization; and

displaying the subsequent visualization to the user, wherein displaying the subsequent visualization includes indicating, for each of the data points located in the mixed region, a location based on a second set of dimensions associated with the subsequent visualization, and wherein a location of the first data point in the subsequent visualization and a location of the second data point in the subsequent visualization are separated by a second distance that is different from the first distance.

2. The method of claim 1, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 1 involving the present visualization to obtain a further subsequent visualization.

3. The method of claim 2, wherein each visualization has an associated angle of view and a view of the multi-dimensional data set is obtained at an angle of view associated with a selected one of the subsequent visualizations.

4. The method of claim 1, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 1 involving the present visualization until a subsequent dimension-reduced visualization having a desired level of separation of points is obtained.

5. The method of claim 4, wherein each visualization has an associated angle of view and a view of the multi-dimensional data set is obtained at an angle of view associated with the dimension-reduced visualization having the desired level of separation of points.

6. The method of claim 1, wherein the current visualization has a first angle of view, and the additional visualization has a second angle of view different from the first angle of view.

7. The method of claim 1, wherein the subsequent visualization is at a higher level of detail than the current visualization.

8. The method of claim 1, wherein the additional dimension-reduction process applies the same dimension reduction technique as used in the first dimension-reduction process.

9. The method of claim 1, wherein the first dimension-reduction process and the additional dimension reduction process apply respectively different dimension-reduction techniques.

10. The method of claim 1, wherein the additional dimension-reduction process includes applying a continuous dimension-reduction technique to obtain a sequence of dimension-reduced visualizations.

11. The method of claim 10 further comprising:

selecting two data points in the multi-dimensional data set for distance estimation,

wherein if the two data points appear to be separated by a distance in any one of the dimension-reduced visualizations, the two data points are separated by at least the distance in the original multi-dimensional space.

12. The method of claim 1 further comprising utilizing a hierarchical cluster tree to automate generation of hierarchical visualizations by generating a visualization for each node of the cluster tree.

13. The method of claim 1, wherein the subset corresponds to a mixed region.

14. The method of claim 1, wherein the multidimensional data set includes non-numeric data and is preprocessed into numerical form prior to dimension reduction.

15. The method of claim 1, wherein the subsequent visualization is consulted with data from a test set by applying a mapping corresponding to the additional dimension-reduction process.

16. The method of claim 1, wherein the method is applied to classify the multi-dimensional data set according to one or more features associated with the data set.

17. The method of claim 1, wherein the multi-dimensional data set is collected from a production process, and the method is applied to obtain information for predicting product properties.

18. The method of claim 1, wherein the multidimensional data set corresponds to data collected from a system, and the method is applied to obtain information for diagnosing a problem in the system.

19. The method of claim 1, wherein the multidimensional data set corresponds to data collected from a system, and the method is applied to obtain information for predicting a problem, before the problem develops in the system.

20. The method of claim 1, wherein the multidimensional data set corresponds to data collected from a system, and the method is applied to obtain information for optimizing the system.

21. The method of claim 1, wherein the multidimensional data set corresponds to data collected from a system, and the method is applied to obtain information for searching the system.

22. The method of claim 1, wherein the subsequent visualization enables the user to determine the proximity of at least one data point in the selected region relative to other of the data points in the selected region with a greater degree of accuracy than the current visualization.

23. The method of claim 1, wherein:

the selected region comprises a third data point of an unknown categorization; and

the subsequent visualization enables the user to visually determine whether the first data point is included in a first category based on visual proximity of the third data point to other of the data points included in the first category.

24. A method for hierarchical visualization of multi-dimensional data, comprising:

selecting two data points in a multi-dimensional data set for distance estimation,

(a) applying, with a computer processor, a first dimension-reduction process to the multi-dimensional data set to obtain a first visualization, the first visualization displaying a first reduced-dimension distance between the two data points;

(b) selecting, with the computer processor, a subset of the multi-dimensional data set associated with a selected region of the dimension-reduced first visualization where more detail is desired;

(c) applying, with the computer processor, a second dimension-reduction process to the selected subset of the multi-dimensional data set to obtain at least one additional visualization, the at least one additional visualization displaying a second reduced-dimension distance between the two data points;

(d) displaying one or more of the visualizations; and

wherein;

if the two data points appear to be separated by a distance in any one of the dimension-reduced visualizations, the two data points are separated by at least the distance in the original multi-dimensional space;

at least one of the dimension reduction processes comprises a continuous dimension-reduction technique that includes principal component analysis; and

a largest one of the reduced-dimension distances is a lower bound estimate of an actual distance between the two selected data points in the original multidimensional space.

25. A non-transitory computer-readable medium encoded with a program of instructions executable by a computer to perform steps in a method for hierarchical visualization of multi-dimensional data, the method steps comprising:

receiving a multi-dimensional data set of data points dispersed into a plurality of categories, each respective category containing data points that share a common characteristic unique to the respective category;

applying a first dimension-reduction process to the multi-dimensional data set to obtain a current dimension-reduced visualization of the multi-dimensional data set;

displaying the current dimension-reduced visualization to a user, wherein displaying the current dimension-reduced visualization includes;

indicating, for each of the data points in the data set, a location based on a first set of dimensions associated with the current visualization; and

indicating a categorization of a plurality of the data points in the data set;

receiving user input that graphically selects a user-defined region of the current visualization, wherein the selected region comprises a mixed region that contains data points of different categories, including a first data point and a second data point, wherein a location of the first data point in the current visualization and a location of a second data point in the current visualization are separated by a first distance;

selecting a subset of the multi-dimensional data set, the subset including the data points contained within the selected region of the current dimension-reduced visualization;

applying an additional dimension-reduction process to the selected subset of the multi-dimensional data set to obtain a subsequent visualization; and

displaying the subsequent visualization to the user, wherein displaying the subsequent visualization includes indicating, for each of the data points located in the mixed region, a location based on a second set of dimensions associated with the subsequent visualization, and wherein a location of the first data point in the subsequent visualization and a location of the second data point in the subsequent visualization are separated by a second distance that is different from the first distance.

26. The non-transitory computer-readable medium of claim 25, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 25 involving the present visualization until a subsequent dimension-reduced visualization having a desired level of separation of points is obtained.

27. The non-transitory computer-readable medium of claim 25, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 25 involving the present visualization to obtain a further subsequent visualization.

28. A computer system, comprising:

a computer processor; and

a non-transitory computer-readable medium encoded with a program of instructions executable by the computer system to perform steps in a method for hierarchical visualization of multi-dimensional data, the method steps comprising;

receiving a multi-dimensional data set of data points dispersed into a plurality of categories, each respective category containing data points that share a common characteristic unique to the respective category;

applying a first dimension-reduction process to the multi-dimensional data set to obtain a current dimension-reduced visualization of the multi-dimensional data set;

displaying the current dimension-reduced visualization to a user, wherein displaying the current dimension-reduced visualization includes;

indicating, for each of the data points in the data set, a location based on a first set of dimensions associated with the current visualization; and

indicating a categorization of a plurality of the data points in the data set;

receiving user input that graphically selects a user-defined region of the current visualization, wherein the selected region comprises a mixed region that contains data points of different categories, including a first data point and a second data point, wherein a location of the first data point in the current visualization and a location of a second data point in the current visualization are separated by a first distance;

selecting a subset of the multi-dimensional data set, the subset including the data points contained within the selected region of the current dimension-reduced visualization;

applying an additional dimension-reduction process to the selected subset of the multi-dimensional data set to obtain a subsequent visualization; and

displaying the subsequent visualization to the user, wherein displaying the subsequent visualization includes indicating, for each of the data points located in the mixed region, a location based on a second set of dimensions associated with the subsequent visualization, and wherein a location of the first data point in the subsequent visualization and a location of the second data point in the subsequent visualization are separated by a second distance that is different from the first distance.

29. The computer system of claim 28, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 28 involving the present visualization until a subsequent dimension-reduced visualization having a desired level of separation of points is obtained.

30. The computer system of claim 28, further comprising using the subsequent visualization as the current visualization and repeating the steps of claim 28 involving the present visualization to obtain a further subsequent visualization.

31. A apparatus comprising a computer processor coupled to a memory wherein:

the memory receives a multi-dimensional data set of data points dispersed into a plurality of categories, each respective category containing data points that share a common characteristic unique to the respective category; and

the computer processor programmed to perform the steps of;

applying a first dimension-reduction process to the multi-dimensional data set to obtain a current dimension-reduced visualization of the multi-dimensional data set;

displaying the current dimension-reduced visualization to a user, wherein displaying the current dimension-reduced visualization includes;

indicating, for each of the data points in the data set, a location based on a first set of dimensions associated with the current visualization; and

indicating a categorization of a plurality of the data points in the data set;

receiving user input that graphically selects a user-defined region of the current visualization, wherein the selected region comprises a mixed region that contains data points of different categories, including a first data point and a second data point, wherein a location of the first data point in the current visualization and a location of a second data point in the current visualization are separated by a first distance;

selecting a subset of the multi-dimensional data set, the subset including the data points contained within the selected region of the dimension-reduced current visualization;

applying an additional dimension-reduction process to the selected subset of the multi-dimensional data set to obtain a subsequent visualization; and

displaying the subsequent visualization to the user, wherein displaying the subsequent visualization includes indicating, for each of the data points located in the mixed region, a location based on a second set of dimensions associated with the subsequent visualization, and wherein a location of the first data point in the subsequent visualization and a location of the second data point in the subsequent visualization are separated by a second distance that is different from the first distance.