US6100901A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for cluster exploration and visualization
Assignee: International Business Machines Corp
•
Filing: 1998-06-22
•
Granted: 2000-08-08
•
Expires: 2018-06-22
Abstract
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.
Inventors
- 👤 Dharmendra Shantilal Mohda
- 👤 David Charles Martin
- 👤 William Scott Spangler
- 👤 Shivakumar Vaithyanathan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 23:21
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/11; G06F; G06F18/00; G06F18/20; G06F18/21; G06F18/213; G06F18/23; G06F18/40; G06T7/60; G06T7/66
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
124 words
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.
Claim 2
Independent Claim
124 words
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.
Claim 3
Dependent Claim
78 words
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.
Claim 4
Dependent Claim
29 words
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.
Claim 5
Dependent Claim
24 words
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.
Claim 6
Dependent Claim
44 words
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.
Claim 7
Dependent Claim
172 words
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.
Claim 8
Dependent Claim
62 words
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.
Claim 9
Dependent Claim
66 words
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.
Claim 10
Dependent Claim
42 words
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.
Claim 11
Dependent Claim
36 words
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.
Claim 12
Dependent Claim
21 words
The method according to claim 10, wherein intermediate 2-dimensional cluster projection is further based on a value of an interpolation parameter.
Claim 13
Dependent Claim
24 words
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.
Claim 14
Dependent Claim
44 words
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.
Claim 15
Dependent Claim
43 words
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.
Claim 16
Dependent Claim
117 words
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.
Claim 17
Dependent Claim
51 words
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.
Claim 18
Dependent Claim
66 words
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.
Claim 19
Dependent Claim
42 words
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.
Claim 20
Dependent Claim
75 words
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.
Claim 21
Dependent Claim
42 words
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.
Claim 22
Dependent Claim
159 words
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.
Claim 23
Dependent Claim
159 words
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.
Claim 24
Dependent Claim
83 words
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.
Claim 25
Dependent Claim
31 words
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.
Claim 26
Dependent Claim
26 words
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.
Claim 27
Dependent Claim
46 words
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.
Claim 28
Dependent Claim
176 words
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.
Claim 29
Dependent Claim
63 words
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.
Claim 30
Dependent Claim
70 words
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.
Claim 31
Dependent Claim
47 words
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.
Claim 32
Dependent Claim
35 words
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.
Claim 33
Dependent Claim
23 words
The program storage device according to claim 30, wherein intermediate 2-dimensional cluster projection is further based on a value of an interpolation parameter.
Claim 34
Dependent Claim
26 words
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.
Claim 35
Dependent Claim
46 words
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.
Claim 36
Dependent Claim
45 words
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.
Claim 37
Dependent Claim
122 words
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.
Claim 38
Dependent Claim
52 words
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.
Claim 39
Dependent Claim
70 words
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.
Claim 40
Dependent Claim
47 words
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.
Claim 41
Dependent Claim
80 words
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.
Claim 42
Dependent Claim
46 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-08 | 2004-02-07 | 2004-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-08 | 2008-02-07 | 2008-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-08 | 2012-02-07 | 2012-08-08 | $7700.00 | Window Closed / Lapsed |