Why increasing k can increase the sum of squared residuals ? K-means

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?

• 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). Commented Mar 3, 2018 at 23:22
• You are right, it is energy vs k. I edited my post, thank you. Commented Mar 3, 2018 at 23:30
• 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$. Commented Mar 3, 2018 at 23:39
• 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. Commented Mar 4, 2018 at 1:42