US5983224A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for reducing the computational requirements of K-means data clustering
Assignee: Hitachi America Ltd
•
Filing: 1997-10-31
•
Granted: 1999-11-09
•
Expires: 2017-10-31
Abstract
Abstract The present invention is directed to an improved data clustering method and apparatus for use in data mining operations. The present invention determines the pattern vectors of a k-d tree structure which are closest to a given prototype cluster by pruning prototypes through geometrical constraints, before a k-means process is applied to the prototypes. For each sub-branch in the k-d tree, a candidate set of prototypes is formed from the parent of a child node. The minimum and maximum distances from any point in the child node to any prototype in the candidate set is determined. The smallest of the maximum distances found is compared to the minimum distances of each prototype in the candidate set. Those prototypes with a minimum distance greater than the smallest of the maximum distances are pruned or eliminated. Pruning the number of remote prototypes reduces the number of distance calculations for the k-means process, significantly reducing the overall computation time.
Inventors
- 👤 Vineet Singh
- 👤 Sanjay Ranka
- 👤 Khaled Alsabti
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 09:49
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/244; G06F18/00; G06F18/20; G06F18/23; G06F18/232; G06F18/2321; G06F18/23213; G06F18/24; G06F18/243; G06F18/24323; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
217 words
A method for reducing the computation time in k-means data clustering operations over a data set containing a plurality of points by minimizing the number of distance calculations between said points for fast mining of database records to uncover relationships therebetween, wherein said method comprises: generating a k-d tree structure of subspaces, wherein each subspace includes a plurality of said points; generating a plurality of prototypes, wherein each of said prototypes has a centroid and is representative of a plurality of points, said prototypes being the seeds for generating clusters of said points; generating a candidate set having a plurality of said prototypes; computing the minimum and maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; identifying the minimum of the maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; eliminating all prototypes in the candidate set with a minimum distance greater than the minimum of the maximum distances calculated from the centroid of each of said prototypes in said candidate set to any point in said subspace; and checking the remaining number of prototypes in the candidate set, and if only one prototype remains, updating data storage means with data characteristics of the prototype.
Claim 2
Independent Claim
217 words
A method for reducing the computation time in k-means data clustering operations over a data set containing a plurality of points by minimizing the number of distance calculations between said points for fast mining of database records to uncover relationships therebetween, wherein said method comprises: generating a k-d tree structure of subspaces, wherein each subspace includes a plurality of said points; generating a plurality of prototypes, wherein each of said prototypes has a centroid and is representative of a plurality of points, said prototypes being the seeds for generating clusters of said points; generating a candidate set having a plurality of said prototypes; computing the minimum and maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; identifying the minimum of the maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; eliminating all prototypes in the candidate set with a minimum distance greater than the minimum of the maximum distances calculated from the centroid of each of said prototypes in said candidate set to any point in said subspace; and checking the remaining number of prototypes in the candidate set, and if only one prototype remains, updating data storage means with data characteristics of the prototype.
Claim 3
Dependent Claim
35 words
A method for reducing the computation time in k-means data clustering operations according to claim 1, further comprises computing a second set of subspaces using the dimensions for the first subspaces and a splitting dimension.
Claim 4
Independent Claim
222 words
A method for reducing the computation time in k-means data clustering operations over a data set containing a plurality of points by minimizing the number of distance calculations between said points for fast mining of database records to uncover relationships therebetween, wherein said method comprises: generating a k-d tree structure of subspaces, wherein each subspace includes a plurality of said points; generating a plurality of prototypes, wherein each of said prototypes has a centroid and is representative of a plurality of points, said prototypes being the seeds for generating clusters of said points; generating a candidate set having a plurality of said prototypes; computing the minimum and maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; identifying the minimum of the maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; eliminating all prototypes in the candidate set with a minimum distance greater than the minimum of the maximum distances calculated from the centroid of each of said prototypes in said candidate set to any point in said subspace; and checking the remaining number of prototypes in the candidate set, and if more than one prototype remains, assigning each point in a subspace to the closest prototype in the candidate set.
Claim 5
Independent Claim
222 words
A method for reducing the computation time in k-means data clustering operations over a data set containing a plurality of points by minimizing the number of distance calculations between said points for fast mining of database records to uncover relationships therebetween, wherein said method comprises: generating a k-d tree structure of subspaces, wherein each subspace includes a plurality of said points; generating a plurality of prototypes, wherein each of said prototypes has a centroid and is representative of a plurality of points, said prototypes being the seeds for generating clusters of said points; generating a candidate set having a plurality of said prototypes; computing the minimum and maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; identifying the minimum of the maximum distances from the centroid of each of said prototypes in said candidate set to any point in said subspace; eliminating all prototypes in the candidate set with a minimum distance greater than the minimum of the maximum distances calculated from the centroid of each of said prototypes in said candidate set to any point in said subspace; and checking the remaining number of prototypes in the candidate set, and if more than one prototype remains, assigning each point in a subspace to the closest prototype in the candidate set.
Claim 6
Dependent Claim
39 words
A method for reducing the computation time in k-means data clustering operations according to claim 3, further comprises performing a k-means data clustering operation over the data set containing a plurality of points using the prototypes that are remaining.
Claim 7
Independent Claim
173 words
A method for grouping a plurality of data points into disjoint clusters for fast mining of database records to uncover relationships therebetween, comprising: generating a plurality of nodes, wherein each node includes a plurality of said data points: generating a plurality of prototypes, wherein each of said prototypes is representative of a plurality of points; generating a set having a plurality of said prototypes in said set to any point in said node; computing the minimum and maximum distances from each of said prototypes in said set to any point in said node; determining the minimum of the maximum distances from each of said prototypes in said set to any point in said node; eliminating all prototypes in said set with a minimum distance greater than smallest of the maximum distances computed from each of said prototypes in said set to any point in said node; and determining the remaining number of prototypes in the candidate set, and if only one prototype remains, updating data storage means with data characteristics of the prototype.
Claim 8
Independent Claim
173 words
A method for grouping a plurality of data points into disjoint clusters for fast mining of database records to uncover relationships therebetween, comprising: generating a plurality of nodes, wherein each node includes a plurality of said data points: generating a plurality of prototypes, wherein each of said prototypes is representative of a plurality of points; generating a set having a plurality of said prototypes in said set to any point in said node; computing the minimum and maximum distances from each of said prototypes in said set to any point in said node; determining the minimum of the maximum distances from each of said prototypes in said set to any point in said node; eliminating all prototypes in said set with a minimum distance greater than smallest of the maximum distances computed from each of said prototypes in said set to any point in said node; and determining the remaining number of prototypes in the candidate set, and if only one prototype remains, updating data storage means with data characteristics of the prototype.
Claim 9
Independent Claim
176 words
A method for grouping a plurality of data points into disjoint clusters for fast mining of database records to uncover relationships therebetween, comprising generating a plurality of nodes, wherein each node includes a plurality of said data points; generating a plurality of prototypes, wherein each of said prototypes is representative of a plurality of points; generating a set having a plurality of said prototypes in said set to any point in said node; computing the minimum and maximum distances from each of said prototypes in said set to any point in said node; determining the minimum of the maximum distances from each of said prototypes in said set to any point in said node; eliminating all prototypes in said set with a minimum distance greater than smallest of the maximum distances computed from each of said prototypes in said set to any point in said node; and determining the remaining number of prototypes in said set, and if more than one prototype remains, assigning each point in a node to the closest prototype in said set.
Claim 10
Independent Claim
176 words
A method for grouping a plurality of data points into disjoint clusters for fast mining of database records to uncover relationships therebetween, comprising generating a plurality of nodes, wherein each node includes a plurality of said data points; generating a plurality of prototypes, wherein each of said prototypes is representative of a plurality of points; generating a set having a plurality of said prototypes in said set to any point in said node; computing the minimum and maximum distances from each of said prototypes in said set to any point in said node; determining the minimum of the maximum distances from each of said prototypes in said set to any point in said node; eliminating all prototypes in said set with a minimum distance greater than smallest of the maximum distances computed from each of said prototypes in said set to any point in said node; and determining the remaining number of prototypes in said set, and if more than one prototype remains, assigning each point in a node to the closest prototype in said set.
Claim 11
Dependent Claim
39 words
A method for grouping a plurality of data points into disjoint clusters according to claim 6, further comprises performing a k-means data clustering operation over the data set containing a plurality of points using the prototypes that are remaining.
References Cited (Backward Citations)
US5040133A
Cited
US5561722A
Cited
US5710916A
Cited
US5819266A
Cited
US5799301A
Cited
US5742811A
Cited
US5832182A
Cited
US5857179A
Cited
US5835891A
Cited
US5819258A
Cited
US5848404A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |