In data mining and machine learning fields, k-means++ is an algorithm for choosing the initial values/centroids (or "seeds") for the k-means clustering algorithm. It was proposed in 2007 by David Arthur and Sergei Vassilvitskii, as an approximation algorithm for the NP-hard k-means problem—a way of avoiding the sometimes poor clusterings found by the standard k-means algorithm. It is similar to the first of three seeding methods proposed, in independent work, in 2006 by Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (The distribution of the first seed is different.)
Background The k-means problem is to find cluster centers that minimize the intra-class variance, i.e. the sum of squared distances from each data point being clustered to its cluster center (the center that is closest to it). Although finding an exact solution to the k-means problem for arbitrary input is NP-hard, the standard approach to finding an approximate solution (often called Lloyd's algorithm or the k-means algorithm) is used widely and frequently finds reasonable solutions quickly. However, the k-means algorithm has at least two major theoretic shortcomings:
First, it has been shown that the worst case running time of the algorithm is super-polynomial in the input size. Second, the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering. The k-means++ algorithm addresses the second of these obstacles by specifying a procedure to initialize the cluster centers before proceeding with the standard k-means optimization iterations. With the k-means++ initialization, the algorithm is guaranteed to find a solution that is O(log k) competitive to the optimal k-means solution.
Example of a suboptimal clustering
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 R 2 {\displaystyle \mathbb {R} ^{2}} that form an axis-aligned rectangle whose width is greater than its height.
If k = 2 {\displaystyle 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. Consider now extending the rectangle in a horizontal direction to any desired 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.
Improved initialization algorithm The intuition behind this approach is that spreading out the k initial cluster centers is a good thing: the first cluster center is chosen uniformly at random from the data points that are being clustered, after which each subsequent cluster center is chosen from the remaining data points with probability proportional to its squared distance from the point's closest existing cluster center. The exact algorithm is as follows:
Choose one center uniformly at random among the data points. For each data point x not chosen yet, compute D(x), the distance between x and the nearest center that has already been chosen. 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. This ensures that a very dissimilar point to the previously selected centroid is selected as the next centroid. 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. Pseudocode The below pseudocode outlines an implementation of k-means++. The kmeans() function performs the standard k-means clustering procedure.
function kmeans++ (k, points) is // Initialize list of centroids with one randomly selected point centroids ← empty list firstIndex ← random integer from 0 to length(points) - 1 centroids.append(points[firstIndex])
// Choose remaining k - 1 centroids while length(centroids) < k do distancesSquared ← empty list
// For each point, compute squared distance to nearest selected centroid for i ← 0 to length(points) - 1 do point ← points[i] minDistance ← distance(point, centroids[0]) for j ← 1 to length(centroids) - 1 do d ← distance(point, centroids[j]) if d < minDistance THEN minDistance ← d distancesSquared.append(minDistance * minDistance)
// Choose next centroid with probability proportional to D(x)^2 total ← sum of distancesSquared threshold ← random number from 0 to total cumulative ← 0 for i ← 0 to length(points) - 1 do cumulative ← cumulative + distancesSquared[i] if cumulative >= threshold THEN centroids.append(points[i]) break
// Run k-means clusters ← kmeans(k, points, centroids) return clusters
… excerpt ends here. Continue reading the full article.
