the distance it contributes to RSS decreases. Second, it decreases in the recomputation step because the new centroid is the vector ~v for which RSSk reaches its minimum. where xm and vm are the mth components of their respective vectors. Setting the partial derivative to zero, we get: which is the componentwise definition of the centroid. Thus, we minimize RSSk when the old centroid is replaced with the new centroid. RSS, the sum of the RSSk, must then also decrease during recomputation. Since there is only a finite set of possible clusterings, a monotonically decreasing algorithm will eventually arrive at a (local) minimum. Take care, however, to break ties consistently, e.g., by assigning a document to the cluster with the lowest index if there are several equidistant centroids. Otherwise, the algorithm can cycle forever in a loop of clusterings that have the same cost. While this proves the convergence of K-means, there is unfortunately no guarantee that a global minimum in the objective function will be reached. This is a particular problem if a document set contains many outliers, documents that are far from any other documents and therefore do not fit well into any cluster. Frequently, if an outlier is chosen as an initial seed, then no other vector is assigned to it during subsequent iterations. Thus, we end up with a singleton cluster (a cluster with only one document) even though there is probably a clustering with lower RSS. Following Figure shows an example of a suboptimal clustering resulting from a bad choice of initial seeds. Effective heuristics for seed selection include Excluding outliers from the seed set; Trying out multiple starting points and choosing the clustering with lowest cost;
the distance it contributes to RSS decreases. Second, it decreases in the recomputation step because the new centroid is the vector ~v for which RSSk reaches its minimum. where xm and vm are the mth components of their respective vectors. Setting the partial derivative to zero, we get: which is the componentwise definition of the centroid. Thus, we minimize RSSk when the old centroid is replaced with the new centroid. RSS, the sum of the RSSk, must then also decrease during recomputation. Since there is only a finite set of possible clusterings, a monotonically decreasing algorithm will eventually arrive at a (local) minimum. Take care, however, to break ties consistently, e.g., by assigning a document to the cluster with the lowest index if there are several equidistant centroids. Otherwise, the algorithm can cycle forever in a loop of clusterings that have the same cost. While this proves the convergence of K-means, there is unfortunately no guarantee that a global minimum in the objective function will be reached. This is a particular problem if a document set contains many outliers, documents that are far from any other documents and therefore do not fit well into any cluster. Frequently, if an outlier is chosen as an initial seed, then no other vector is assigned to it during subsequent iterations. Thus, we end up with a singleton cluster (a cluster with only one document) even though there is probably a clustering with lower RSS. Following Figure shows an example of a suboptimal clustering resulting from a bad choice of initial seeds. Effective heuristics for seed selection include Excluding outliers from the seed set; Trying out multiple starting points and choosing the clustering with lowest cost;