k-means clustering and Voronoi sets

In the context of https://latex.codecogs.com/gif.latex?k-means, we want to partition the space of our observations into https://latex.codecogs.com/gif.latex?k classes. each observation belongs to the cluster with the nearest mean. Here “nearest” is in the sense of some norm, usually the https://latex.codecogs.com/gif.latex?\ell_2 (Euclidean) norm.

Consider the case where we have 2 classes. The means being respectively the 2 black dots. If we partition based on the nearest mean, with the https://latex.codecogs.com/gif.latex?\ell_2 (Euclidean) norm we get the graph on the left, and with the https://latex.codecogs.com/gif.latex?\ell_1 (Manhattan) norm, the one on the right,

Points in the red region are closer to the mean in the upper part, while points in the blue region are closer to the mean in the lower part. Here, we will always use the standard https://latex.codecogs.com/gif.latex?\ell_2 (Euclidean) norm. Note that the graph above is related to Voronoi diagrams (or Voronoy, from Вороний in Ukrainian, or Вороно́й in Russian) with 2 points, the 2 means.

In order to illustrate the https://latex.codecogs.com/gif.latex?k-means clustering algorithm (here Lloyd’s algorithm) consider the following dataset

set.seed(1)
pts <- cbind(X=rnorm(500,rep(seq(1,9,by=2)/10,100),.022),Y=rnorm(500,.5,.15))
plot(pts)

Here, we have 5 groups.  So let us run a 5-means algorithm here.

  • we draw randomly 5 points in the space (intial values for the means), https://latex.codecogs.com/gif.latex?\boldsymbol{\mu}_1^{(1)},\cdots,\boldsymbol{\mu}_k^{(1)}
  • in the assignment step, we assign each point to the nearest mean

https://latex.codecogs.com/gif.latex?S_i^{(t)}%20=%20\big%20\{%20\boldsymbol{x}_j%20:%20\big%20\|%20\boldsymbol{x}_j%20-%20\boldsymbol{\mu}^{(t)}_i%20\big%20\|^2%20\leq%20\big%20\|%20\boldsymbol{x}_j%20-%20\boldsymbol{\mu}^{(t)}_{i%27}%20\big%20\|^2%20\%20\forall%20i%27\in\{1%20,\cdots,%20k\}%20\big\}

  • in the update step, we compute the new centroids of the clusters

https://latex.codecogs.com/gif.latex?%20%20%20%20\boldsymbol{\mu}^{(t+1)}_i%20=%20\frac{1}{|S^{(t)}_i|}%20\sum_{\boldsymbol{x}_j%20\in%20S^{(t)}_i}%20\boldsymbol{x}_j

To visualize it, see

The code the get the clusters is

kmeans(pts, centers=5, nstart = 1, algorithm = "Lloyd")

Observe that the assignment step is based on computations of Voronoi sets. This can be done in R using

library(tripack)
V <- voronoi.mosaic(means[,1],means[,2])
P <- voronoi.polygons(V)
points(V,pch=19)
plot(V,add=TRUE)

This is what we can visualize below

The code to visualize the https://latex.codecogs.com/gif.latex?k means, and the https://latex.codecogs.com/gif.latex?k clusters (or regions), use

km1 <- kmeans(pts, centers=5, nstart = 1, algorithm = "Lloyd")
library(tripack)
library(RColorBrewer)
CL5 <- brewer.pal(5, "Pastel1")
V <- voronoi.mosaic(km1$centers[,1],km1$centers[,2])
P <- voronoi.polygons(V)
plot(pts,pch=19,xlim=0:1,ylim=0:1,xlab="",ylab="",col=CL5[km1$cluster])
points(km1$centers[,1],km1$centers[,2],pch=3,cex=1.5,lwd=2)
plot(V,add=TRUE)

Here, starting points are draw randomly. If we run it again, we might get

or

On that dataset, it is difficult to get cluster that are the five groups we can actually see. If we use

set.seed(1)
A <- c(rep(.2,100),rep(.2,100),rep(.5,100),rep(.8,100),rep(.8,100))
B <- c(rep(.2,100),rep(.8,100),rep(.5,100),rep(.2,100),rep(.8,100))
pts <- cbind(X=rnorm(500,A,.075),Y=rnorm(500,B,.075))

we usually get something better

Colors are obtained from clusters of the https://latex.codecogs.com/gif.latex?k-means function, but additional lines are obtained using as outputs of Voronoi diagrams functions.


4 thoughts on “k-means clustering and Voronoi sets”

  1. I play around with this kind of stuff in connection with the Vehicle Routing Problem (It’s on wikipedia). I use (capacitated) k-means to initialise routes. I have a procedure to choose the initial seeds:
    – First two seeds are the nodes that are furthest apart
    – Next seed is the one that maximises the sum of the distances to the first 2 (i.e. furthest from the ones we already have)
    – Next seed maximises sum of distances to first 3
    – etc
    In a quick test, this procedure at least gave me a seed in each cluster – but still, the k-means clusters crossed the obvious boundaries.
    Interestingly, solving an uncapacitated VRP with the depot at (0.5, -1) gave me the clusters you are after 🙂 Ahh, the interchangeability of NP-hard problems 🙂

  2. Hello, I am interested un this subject. I am a student and I investigate Clustering methods, specificaly k-means algorithm. -i fiind it very interesting that you never get the 5 clusters right. Could I maybe chat with you about this someday?

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.