Convergence in Hartigan-Wong k-means method and other algorithms

Question

I have been trying to understand the different k-means clustering algorithms mainly that are implemented in the stats package of the R language.

I understand the Lloyd's algorithm and MacQueen's online algorithm. The way I understand them is as follows:

Lloyd's Algorithm:

Initially ‘k’ random observations are chosen that will serve as the centroids of the ‘k’ clusters. Then the following steps occur in iteration till the centroids converge.

1. The Euclidean distance between each observation and the chosen centroids is calculated.
2. The observations that are closest to each centroids are tagged within ‘k’ buckets.
3. The mean of all the observations in each bucket serves as new centroids.
4. The new centroids replace the old centroids and the iteration goes back to step 1 if the old and new centroids have not converged.

The conditions to converge are the following: the old and the new centroids are exactly identical, the difference between the centroids is small (of the order of 10^-3) or the maximum number of iterations (10 or 100) are reached.

MacQueen's Algorithm:

This is an online version where the first 'k' instances are chosen as centroids.

Then each instance is placed in buckets depending on which centroid is closest to that instance. The respective centroid is recalculated.

Repeat this step till each instance is placed in the appropriate bucket.

This algorithm only has one iteration and the loop goes on for 'x' instances

Hartigan-Wong Algorithm:

1. Assign all the points/instances to random buckets and calculate the respective centroid.
2. Starting from the first instance find the nearest centroid and assing that bucket. If the bucket changed then recalculate the new centroids i.e. the centroid of the newly assigned bucket and the centroid of the old bucket assignment as those are two centroids that are affected by the change
3. Loop through all the points and get new centroids.
4. Do a second iteration of points 2 and 3 which performs sort of a clean-up operation and reassigns stray points to correct buckets.

So this algorithm performs 2 iterations before we see the convergence result.

Now, I am unsure if what I think in point 4 in the Hartigan-Wong algorithm is the correct method of the algorithm. My question is, if the following method for Hartigan-Wong is the correct method to implement k-means? Are there only two iterations for this method? if not, what is the condition for convergence (when to stop)?

Another possible implementation explanation what I understand is.

1. Assign all the points/instances to random buckets and calculate the respective centroid.
2. Starting from the first instance find the nearest centroid and assign that bucket. If the bucket changed then recalculate the new centroids i.e. the centroid of the newly assigned bucket and the centroid of the old bucket assignment as those are two centroids that are affected by the change.
3. Once there is a change in the bucket for any point, go back to the first instance and repeat the steps again.
4. The iteration ends when all the instances are iterated and none of the points change buckets.

This way there are a lot of iterations that start from the beginning of the dataset again and again every time when an instance changes buckets.

Any explanations would be helpful and please let me know if I my understanding for any of these methods is wrong.

Answer 1

H-W's algorithm, from the 1979 paper, takes as input initial clusters. However, the authors suggest a method for obtaining them in their last section. They write that it is guaranteed that no cluster will be empty after the initial assignment in the subroutine. It goes as follows:

1. Compute the overall mean $\bar{x}$.
2. Order the observations with respect to their distance to $\bar{x}$, that is $||x_i - \bar{x}||_2$ (in ascending order I guess?).
3. Take the points in position $\{ 1 + (L-1) [M/K] \}$, where $L=1, \dots, K$, as initial centroids. ($[\ \cdot\ ]$ most probably refer to the floor function, hence the $1$ at the beginning.)

As for the main algorithm, it is described in a paper called Hartigan's K-Means Versus Lloyd's K-Means-Is It Time for a Change? by N Slonim, E Aharoni, K Crammer, published in 2013 by AJCAI. Note that this version simply uses a random initial partition. It goes as follows.

For the vectors $x \in \mathcal{X}$ and a target number of clusters $K$,

1. Set $\mathcal{C}$ to be a random partition of $\mathcal{X}$ into $K$ clusters and compute the centroid vector associated to each $C \in \mathcal{C}$, denote them $v_C$.

2. Scan $\mathcal{X}$ in a random order, and for all $x \in \mathcal{X}$

   2.1 Set the stopping indicator to $s = 1$

   2.1. Tentatively remove $x$ from its cluster $C$, letting $C^{-} = C \setminus \{ x \}$.

   2.2 Find \begin{align*} C^+ = \Big\{ \mathrm{argmin}_{C^* \in (\mathcal{C} \setminus C) \cup C^{-}}\ \frac{1}{n} d(x,v_C^*) + \frac{1}{n} \sum_{y \in C^*} [d(y,v_{C^* \cup x}) - d(y,v_{C^*})] \Big\} \cup \{ x \} \end{align*}

   2.3 If $C^{+} \neq C$, then reset $C \leftarrow C^{-}$ and $C^* \leftarrow C^{+}$ and update their respective vectors $v_{C}$ and $v_{C^*}$. Also reset $s \leftarrow 0$.

3. If $s=0$, go back to 2.

Here I make a slight abuse of notation letting $C^*$ be the solution of the $\mathrm{argmin}$ in 2.2. This step, 2.2, simply computes the change in the loss obtained if $x$ is added to $C^*$, as opposed to it staying alone in its own cluster (once removed). $d$ stands for distance. Finally, the particular ways to compute the updated vectors $v_C$, $v_{C^* \cup \{x \}}$ and so on is provided in the paper cited above. They can be done in linear time.

I think the answers to all your questions are implicit in the above algorithm... However, I still have to make sure this implementation of the algorithm is standard. In particular if it is the one implemented in R. Any comments/edit are welcomed.