In k-means clustering, why sum of squared errors (SSE) always decrease per iteration? How can prove it by mathematical derivation of formulas?

k : number of clusters

m : number of examples

$c_h$ : index of cluster to which example

$X_h$ is currently assigned

$U_{i}$ : cluster centroid of cluster to which example $X_{ij}$ has been assigned

$n_{i}$ : example number of cluster to which example $X_{ij}$ has been assigned

(1) Randomly initialize cluster centroids $U_1,U_2,...,U_k$

(2) For h = 1 to m: $c_h$:= index of cluster centroid closest to $X_h$

$$c_h = \mathop{argmin}_{i\in{[1,k]}}||X_h-U_i||\ ,\ h\in[1,m]$$

count example number in i cluster by C function $$n_i=C(i) = \sum_{h=1}^m [c_h=i]\ ,\ i\in[1,k]$$

(3) For i = 1 to k: $$\sum_{i=1}^{k}n_i=m$$

$SSE=\displaystyle\sum_{i=1}^{k}\sum_{j=1}^{n_i}||X_{ij}-U_i||^2 =\sum_{j=1}^{n_1}||X_{1j}-U_1||^2+\sum_{j=1}^{n_2}||X_{2j}-U_2||^2+...+\sum_{j=1}^{n_k}||X_{kj}-U_k||^2$

$$ \begin{eqnarray} \frac{\partial{SSE}}{\partial{U_i}} &=&\frac{\partial(\sum_{j=1}^{n_1}||X_{1j}-U_1||^2+\sum_{j=1}^{n_2}||X_{2j}-U_2||^2+...+\sum_{j=1}^{n_k}||X_{kj}-U_k||^2)}{\partial{U_i}}\\ &=&\displaystyle\sum_{j=1}^{n_i}2||X_{ij}-U_i||^1\frac{X_{kj}-U_k}{||X_{kj}-U_k||}\\ &=&2\displaystyle\sum_{j=1}^{n_i}(U_i-X_{ij})\\ &=&2\displaystyle\sum_{j=1}^{n_i}U_i-2\displaystyle\sum_{j=1}^{n_i}X_{ij}\\ &=&2n_iU_i-2\displaystyle\sum_{j=1}^{n_i}X_{ij}=0\\ &&n_iU_i=\displaystyle\sum_{j=1}^{n_i}X_{ij}\\ &&U_i=\frac{1}{n_i}\displaystyle\sum_{j=1}^{n_i}X_{ij} \end{eqnarray} $$

(4) Repeat(2),(3)

Why sum of squared errors (SSE) always decrease?


I find it difficult to follow your question because of the notation (for instance, what are "examples"? Do you mean data points?). Anyway, maybe the following example will clarify your question.

The k-means method is iterative; let's assume we have reached iteration i and the results at this point look like that (point for data and crosses for cluster centroids):

first plot

The algorithm has done a good job so far and we can have a look at the estimates

# sse by cluster (all functions defined below)
sse_by_cluster <- ssefun(df= mydata, vars= c("a", "b"), cl= "cluster")
       a        b 
7.020118 8.541280
# sse
# between_SS / total_SS

But obviously there is one data point that would be better represented by the other cluster. I marked the data point in the following plot:

second plot

Now let's go to iteration i + 1. The k-means algorithm tries to find the closest cluster for the data points (this is what your step 2 says if I get it right). In this case the marked data point would be shifted to the black cluster because this cluster is much closer. This done we end up with new cluster centroids and new estimates (step 3 in your question). Let's first have a quick look at the plot

third plot

And now we can check the estimates

# sse by cluster (function defined below)
sse_by_cluster <- ssefun(df= mydata, vars= c("a", "b"), cl= "cluster")
       a        b 
7.138251 6.870824 
# sse
# between_SS / total_SS (here higher values are better)

As you can see repeating step 2 and 3 indeed decreased the sse. Why is this? sse is the squared sum of the differences of each values from its cluster centroid. The data point we talk about is now in iteration i + 1 much closer to its cluster centroid, hence, the sse is lower. In this example, we reached a optimum result. If there was another data point that could be shifted to another group that is closer, the sse would descrease another time and the cluster centroids would chnage again, too by repeating step 2 and step 3. This happens again and again until there is too little improvement to go on or the number of iterations has been reached. I hope that helped. The R code to reproduce he example is below.

# function to determine sse by group
# provide name of data frame, name of the two  variables and the cluster-variable
sse_fun <- function(df, vars, cl){
# calculate mean by cluster
clustermeans <- aggregate(df[ , vars], by=list(df[,cl]), 

# for every cluster x calculate the sum of squared differences from the cluster centroid
sse <- sapply(1:k, function(x){
  sse <- sum(
    c((df[df[ ,cl]== x, vars[1]] - 
clustermeans[clustermeans$Group.1 == x, vars[1]])**2,
      (df[df[, cl]== x, vars[2]] - 
clustermeans[clustermeans$Group.1 == x, vars[2]])**2))
names(sse) <- vars

# function to determine betweenss/totalss
btw_tot_fun <- function(df, vars, sse){
ratio <- 1 - sse/ sum(c((df[ , vars[1]] - mean(df[ , vars[1]]))**2, (df[ , vars[2]] - mean(df[ , vars[2]]))**2))

# generate data
n <- 20
k <- 2
mydata <- data.frame(a= rnorm(n), b= rnorm(n))

# K-Means Cluster Analysis
fit <- kmeans(mydata, k) # k cluster solution
# append cluster assignment
mydata$cluster <- as.factor(fit$cluster)

# for both first plots and the first estimates simply run this peace of code
#mydata$cluster[5] <- 2

sse_by_cluster <- sse_fun(df= mydata, vars= c("a", "b"), cl= "cluster")
sse <-  sum(sse_by_cluster)

btw_tot <- btw_tot_fun(mydata, c("a", "b"), sse)

# see results
fit # compare to the results from kmeans function (works only for the i+1 estimates that I wrote down because that are the estimates for the final result)

# plot
plot(mydata$a, mydata$b, col=mydata$cluster, xlab= "a", ylab= "b")
points(clustermeans[1, "a"], clustermeans[1, "b"], col= "black", pch = 3, cex= 2)
points(clustermeans[2, "a"], clustermeans[2, "b"], col= "red", pch = 3, cex= 2)

It does not always decrease.

It just never increases.

A proof is likely based on contradiction. Assume that the previous cluster assignment was better. Then at least one point was better, but then that point was not assigned to the closest center. For the other step you already have the proof that the arithmetic mean is the minimum for a fixed partition.


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.