0
$\begingroup$

I defined the distance between each observation and its centroid by:

dist=sum((X[,i]-Y[,j])^2)
# X is a 2*n observations matrix, Y is a 2*k centroids matrix
# n is the number of observations

Then I created a variable energy which represents the sum of dist for all observations.

I did that for k varying from 1 to 20 and I got these graphs: (It is energy vs. k)

Why increasing k can increase the sum of squared residuals?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your axes are labeled x and y, but you say x and y are the data points and centroids. What do the plots represent; is it energy vs. k? Also, a nice feature of the site is that you can embed images directly into your post by clicking the image button (no need to link to external image hosting sites). $\endgroup$
    – user20160
    Commented Mar 3, 2018 at 23:22
  • $\begingroup$ You are right, it is energy vs k. I edited my post, thank you. $\endgroup$
    – Louis Ansuez
    Commented Mar 3, 2018 at 23:30
  • $\begingroup$ What you're seeing is most likely the result of suboptimal solutions, as @CarlRynegardh pointed out. Just to add one more point, the true error must decrease monotonically with $k$. $\endgroup$
    – user20160
    Commented Mar 3, 2018 at 23:39
  • $\begingroup$ K-means is a non-deterministic algorithm; it is quite possible for this to occur. If you run it 20 or 30 times and average the results for each $K$, this effect will typically disappear or at least get much smaller. $\endgroup$
    – jbowman
    Commented Mar 4, 2018 at 1:42

1 Answer 1

Reset to default
3
$\begingroup$

I will assume that the plot shows the sum of within distances of k-means. That is the sum of distances of every point to their closest cluster center. The optimization of K-Means does not guarantee a global minimum. You are much more likely to find local minima. As you increase k you might be unlucky and find a bad one. You could use a smart initialization strategy like k-means++, or run k-means several times with random initalizations for the cluster centers for each k and pick the solution with lowest within cost. Using a smart initialization strategy will also speed up the computations and make you converge to the solution faster.

The results of K-Means is dependent on the cluster initialization.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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