4
$\begingroup$

K-Means is an iterative clustering method which randomly assigns initial centroids and shifts them to minimize the sum of squares. One problem is that, because the centroids are initially random, a bad starting position could cause the algorithm to converge at a local optimum.

K-Means++ was designed to combat this - It chooses the initial centroids using a weighted method which makes it more likely that points further away will be chosen as the initial centroids. The idea is that while initialization is more complex and will take longer, the centroids will be more accurate and thus fewer iterations are needed, hence it will reduce overall time. (Source)

In fact, the people who devised K-Means++ tested how fast it could cluster data, and found that it was twice as fast. (Source)

However, some basic tests in R show that K-Means++ requiring fewer iterations than K-Means does not make up for the extra time taken to initialize, even for normal sized datasets.

The test:

I tested it with datasets sized from 100 to a few thousand points. The data is named 'comp' in the code. If you want to test it, you can use whatever dataset you want.

K-Means

First, we do the clustering:

k <- kmeans(comp, 2, nstart=1, iter.max=100, algorithm = "Lloyd")

Next, the sum of squares can be added to a list

results <- k$withinss

Now, if we put the clustering in a loop, which adds to the 'results' list every time it loops, we can see how many times it has looped in a certain amount of time

repeat {
k <- kmeans(comp, 2, nstart=1, iter.max=10, algorithm = "Lloyd")

results <- c(results, k$withinss)
}

(I did it in this inefficient way because I initially used this code to test the accuracy i.e which method had the average total Sum of Squares)

If we let the loop run for 60s, we find that the list is 132,482 objects long. (it looped 66241 times since each time adds two objects to the list).

K-Means++

Now compare that with ++ initialisation.

#Set-up
library(LICORS)
k <- kmeanspp(comp, k = 2, start = "random", iter.max = 100, nstart = 1)

results <- k$withinss

#Loop
repeat {
k <- kmeanspp(comp, k = 2, start = "random", iter.max = 100, nstart = 1)

results <- c(results, k$withinss)
}

The 'results' list ended up having 22712 objects (it looped 11356 times).

K-Means was over 5 times faster than K-Means++, so this is clearly not just a measurement error. The ratio changes depending on the dataset I use for the test, but I've tried everything up to datasets with thousands of points, and the results consistently show that K-Means++ is slower.

My first thought was that maybe the package I used (LICORS) has inefficient code for performing K-Means, but then I saw that LICORS actually uses the default kmeans function after ++ initialization. In other words: Everything was the same except for the method of initialization, and ++ was slower. (another package for K-Means++ called flexclust which uses different code was even slower!)

Perhaps the dataset needs to have tens of thousands of points for K-Means++ to be faster? In this case, it would be very misleading for every source I've seen to say that K-Means++ is faster. Perhaps I've misunderstood something, or there's something wrong with the test?

Can any experts here (such as Tim, who claims here that K-Means++ is faster) explain these results?

$\endgroup$
  • $\begingroup$ Note that there is some work on faster alternatives to kmeans++ initialization for very large datasets. For example, this paper proposes an algorithm called AFK-MC2 which approximates kmeans++ initialization using MCMC. $\endgroup$ – Dougal Jul 17 '18 at 16:35
3
$\begingroup$

kmeans in R is pretty good Fortran code.

I haven't looked at the package you got kmeanspp from, but I wouldn't expect it to be of the same quality. If it uses R code to do the initialization that can hurt badly.

So in the end, you haven't been benchmarking kmeans vs. kmeans++, but you have been showing that the quality of R packages varies a lot, and the R interpreter is substantially slower than Fortran/C/C++ functions, and you therefore cannot rely on such benchmarks.

The low performance of flexclust is probably because it uses even more R code?

$\endgroup$
  • $\begingroup$ +1. I am dishearten on how sometimes people think that high-performance code (or even plain old Fortran/C/C++) magically happens. kmeanspp is exclusively written in R btw... $\endgroup$ – usεr11852 says Reinstate Monic Dec 7 '15 at 7:41
  • $\begingroup$ Well, YangLi indicated it is a R function to do the initialization, then uses regular kmeans. It may be necessary to rewrite the kmeans++ initialization in Fortran to get a fair benchmark. it may also be helpful to measure initialization time and actual run time independently. $\endgroup$ – Anony-Mousse Dec 7 '15 at 7:49
  • $\begingroup$ Obviously yes. kmeans is not part of the code written for kmeanspp though. :) $\endgroup$ – usεr11852 says Reinstate Monic Dec 7 '15 at 7:52
  • $\begingroup$ +1 and Accepted. I was wondering if I had the mathematical theory wrong, but it looks like I'll just have to rewrite in Fortran to do a fairer test. $\endgroup$ – Yang Li Dec 7 '15 at 19:16
2
$\begingroup$

Why is K-Means++ SLOWER than random initialization K-Means?

I would argue that it depends. First recall the difference between the two:

K-means ++

K-means++ involves a somewhat intensive initialization step where:

  1. Choose on center uniformly at random among the data points
  2. For each data point, compute the distance $D(x)$ 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 the above steps until $k$ centers have been chosen
  5. Proceed with standard $k$-means

K-means

  1. Jump straight here --> Randomly initialize $k$ centers
  2. Repeat until convergence:
    • For every obervation $i$, assign it to the closest cluster center: $$ c^{(i)} := \arg min_{j} \ || x^{(i)} - \mu_j ||^2_2$$
    • For every cluster $j$, update its value as the mean of assigned observations $$ \mu_j := \frac{\sum_{i=1}^m \mathcal{I}\{ c^{(i)} = j\} x^{(i)} }{\sum_{i=1}^m \mathcal{I}\{ c^{(i)} = j\}} $$

An intuitive interpretation of relative speeds

Steps 2 and 3 involve computing the euclidean distance between all points $k$ times before the actual algorithm even starts. It must also calculate the proportional probabilities for each point, and implementations often add an inner loop which performs "trials" and selects the best result. All these steps are performed across the entire dataset, which can be quite slow.

On the other hand, where k-means++ gains in speed is in the convergence of step 6. But that is dependent on the structure of your dataset, not necessarily on its size.

See here for the Sklearn implementation - around lines 100

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.