Using the Triangle Inequality to Accelerate k-Means

Using the Triangle Inequality to Accelerate k-Means,Charles Elkan

Using the Triangle Inequality to Accelerate k-Means   (Citations: 129)
BibTex | RIS | RefWorks Download
The -means algorithm is by far the most widely used method for discovering clusters in data. We show how to accelerate it dramatically, while still always computing exactly the same result as the standard algorithm. The accelerated al- gorithm avoids unnecessary distance calculations by applying the triangle inequality in two differ- ent ways, and by keeping track of lower and up- per bounds for distances between points and cen- ters. Experiments show that the new algorithm is effective for datasets with up to 1000 dimen- sions, and becomes more and more effective as the number of clusters increases. For it is many times faster than the best previously known accelerated -means method.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: