Using the Triangle Inequality to Accelerate-Means

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. 1