This page explains very good how k-means works: http://mnemstudio.org/clustering-k-means-example-1.htm
Somewhere I heard that there is some algorithms, which use triangle inequality to speed up the process. In which step, and how exactly can use triangle inequality?
Using triangle inequality to find the bounds to avoid redundant distance calculations.
Let x be a point and let b and c be centers.
Lemma 1: If d(b,c)>=2d(x,b), then d(x,c)>=d(x,b)
If d(b,c)/2 >= d(x,b), then d(x,b) <= d(x,c), thus no need to calculate d(x,c).
If we know an upper bound u>=d(x,c), but u >d(b,c)/2, then we need compute d(x,b) and d(x,c)
Lemma 2: d(x,c)>=max{0, d(x,b)-d(b,c)} >=max{0, l'-d(b,c)}
where l' is a lower bound of d(x,b) in the previous iteration's calculation
The optimized algorithm is based on the fact that most distance calculations in standard K-means are redundant. If a point is far away from a center, it is not necessary to calculate the exact distance between the point and the center in order to know that the point should not be assigned to this center. Conversely, if a point is much closer to one center than to any other, calculating exact distances is not necessary to know that the point should be assigned to the first center.
Details are in the original paper about acceleration: Charles Elkan. Using the triangle inequality to accelerate k-means. In Tom Fawcett and Nina Mishra, editors, ICML, pages 147–153. AAAI Press, 2003.
Other references: Greg Hamerly, Making k-means even faster In proceedings of the 2010 SIAM international conference on data mining (SDM 2010), April 2010. pdf!
