Method and apparatus for reducing the computational requirements of K-means data clustering
Number of patents in Portfolio can not be more than 2000
United States of America Patent
Stats
-
Nov 9, 1999
Grant Date -
N/A
app pub date -
Oct 31, 1997
filing date -
Oct 31, 1997
priority date (Note) -
Expired
status (Latency Note)
Importance
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.
First Claim
Family
International Classification(s)
Cited Art Landscape
Patent Citation Ranking
Advertisement
Advertisement
Advertisement
Recipient Email Address
Recipient Email Address
Comment
Recipient Email Address
Add to Portfolio(s)
To add this patent to one, or more, of your portfolios, simply click the add button.
This Patent is in these Portfolios:
Add to additional portfolios:
Last Refreshed On:
Changes done successfully