What are the advantages of the pre-defined initial centroids in clustering ?

Question

In many clustering techniques, the values of initial centroids (center) play an important role to draw the results of the clustering process.

Could someone please tell me what are exactly the meaning of initial centroids and what are the advantages to pre-define the initial centroids at the first step in clustering process?

Answer 1

The Problem

To find a optimal clustering is a hard task. In fact, it is NP-hard to solve. In the classical k-means algorithm you choose $k$ centroids at random from the data. This can lead to a) slow convergence and b) sub-optimal clustering. Wikipedia has a nice example on this:

To illustrate the potential of the k-means algorithm to perform arbitrarily poorly with respect to the objective function of minimizing the sum of squared distances of cluster points to the centroid of their assigned clusters, consider the example of four points in $\mathcal{R}^2$ that form an axis-aligned rectangle whose width is greater than its height.

If $k = 2$ and the two initial cluster centers lie at the midpoints of the top and bottom line segments of the rectangle formed by the four data points, the k-means algorithm converges immediately, without moving these cluster centers. Consequently, the two bottom data points are clustered together and the two data points forming the top of the rectangle are clustered together—a suboptimal clustering because the width of the rectangle is greater than its height.

Now, consider stretching the rectangle horizontally to an arbitrary width. The standard k-means algorithm will continue to cluster the points suboptimally, and by increasing the horizontal distance between the two data points in each cluster, we can make the algorithm perform arbitrarily poorly with respect to the k-means objective function.

A popular solution

Do avoid this, you can use the popular k-means++ alorithm that chooses the staring points better. The idea is to first select a centroid at random and then place the remaining $k-1$ ones such that they are maximally far away from another. In this way we try to cover the whole data set.

The algorithm is as follows:

1. Choose one center uniformly at random from among the data points.
2. For each data point $x$, compute $D(x)$, the distance between x and the nearest center that has already been chosen.
3. Choose one new data point at random as a new center, using a weighted probability distribution where a point $x$ is chosen with probability proportional to $D(x)^2$.
4. Repeat Steps 2 and 3 until $k$ centers have been chosen. Now that the initial centers have been chosen, proceed using standard k-means clustering.

Answer 2

K-means needs starting centers, these are the initial centroids.

Usually, these are chosen randomly, or e.g. with k-means++.

However, it may be desirable to instead predefine them:

• if you have prior knowledge of where the centers should be (this can substantially reduce the number of iterations)
• if you have earlier centroids and want to continue (e.g. because you stopped early, or because you have new data)
• to test new initialization strategies
• for reproducibility, to avoid randomness if you use k-means.