I'm trying to plot all the steps of a k-means algorithm with r, but I can't.
The k-means algorithm works in this way:
- Step 1. Initialize the center of the clusters
- Step 2. Assign the closest initial centers to each data point
- Step 3. Set the position of each cluster to the mean of all data points belonging to that cluster
- Step 4. Assign the closest cluster to each data point
- Step 5. Repeat steps 3-4 until convergence
I plot the dataset and initial centers of clusters (Step 1). Too, I can plot the new cluster centers and show which point belongs to each cluster (Step 3 and 4). But I don't know how to plot the Step 2. I need the very first initial centers membership of each point, before the first iteration, but kmeans() doesn't give it you. How could I calculate this?
Here is my code:
set.seed(2009)
points1 <- data.frame(x=rnorm( 50,1,0.1), y=rnorm(50,5,0.1))
points2 <- data.frame(x=rnorm( 50,5,0.1), y=rnorm(50,5,0.1))
points3 <- data.frame(x=rnorm(200,3,0.8),y=rnorm(200,3,0.8))
df <- rbind(points1, points2, points3)
p <- ggplot(df, aes(x, y))
p + geom_point(size=7, color="grey") + labs(title="Initial configuration")
y <- c(4.88871745,4.88099143,3.69713723)
x <- c(0.75606015,1.26736958,3.04961545)
kcenters <- data.frame(x,y)
p + geom_point(size=7, color="grey") +
geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x") +
labs(title="Initial centers")
dfCluster <- kmeans(df, centers=kcenters, iter.max=1)
p + geom_point(size=7, aes(colour=as.factor(dfCluster$cluster))) +
geom_point(data=data.frame(dfCluster$center), aes(x, y), size=7,
color="black", shape="x") +
theme(legend.position="none") +
labs(title="First iteration")
My goal would be to show the initial center membership of each point in "Initial centers" plot.
Edit:
I think I did not explain myself properly.
On this website there is a simulation showing what I would like to get:
http://www.onmyphd.com/?p=k-means.clustering
When you click the "Iteration" button the first time (click1), the initial centers are placed. Pressing a second time (click 2), points are assigned to closer center, and painted with different colors. When you click the third time (click3), new centers are calculated, and when you press for the fourth time (click4), points are assigned to closer center again.
When you run kmeans() and stop it at the first iteration, you get the new centers of the clusters ( click3 ), dfCluster$center, and cluster membership of each point (click4), dfCluster$cluster, but you do not get the initial center membership of each point (click 2), which is exactly what I'm looking for.
I finally accomplished what I wanted: a step-by-step k-means. Sorry if the code it's not perfect, I'm a newbie with R.
#How does k-means work
library(ggplot2)
set.seed(2009)
points1<-data.frame(x=rnorm(50,1,0.1),y=rnorm(50,5,0.1))
points2<-data.frame(x=rnorm(50,5,0.1),y=rnorm(50,5,0.1))
points3<-data.frame(x=rnorm(200,3,0.8),y=rnorm(200,3,0.8))
df<-rbind(points1,points2,points3)
#plot initial points
p <- ggplot(df, aes(x, y))
p + geom_point(size=7, color="grey")
#set initial centers
kcenters<-df[c(49,26,297),]
#plot centers
p + geom_point(size=7, color="grey") + geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x")
#assignment (to calculate distances to initial centers and to allocate points to the cluster to which they are closest)
library(reshape)
distances <- melt(as.matrix(dist(df,diag=T,upper = T)), varnames = c("row", "col"))
dist_center1<-subset(distances,col==49,select = value)
dist_center2<-subset(distances,col==26,select = value)
dist_center3<-subset(distances,col==297,select = value)
dist_centers<-data.frame(dist_center1,dist_center2,dist_center3)
colnames(dist_centers)<-c("dist_center1","dist_center2","dist_center3")
dist_centers$cluster<-apply(dist_centers, 1, which.min)
df<-cbind(df,dist_centers)
#plot assignment
p + geom_point(size=7, aes(colour=as.factor(df$cluster))) + geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x") + theme(legend.position="none")
#calculate new centers
x<-tapply(df$x,df$cluster,mean)
y<-tapply(df$y,df$cluster,mean)
kcenters<-data.frame(x,y)
#plot new centers
p + geom_point(size=7, aes(colour=as.factor(df$cluster))) + geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x") + theme(legend.position="none")
And then, you can continue the procedure slightly adjusting the code above:
#assignment
df<-rbind(df[,1:2],kcenters)
row.names(df) <- NULL
distances <- melt(as.matrix(dist(df,diag=T,upper = T)), varnames = c("row", "col"))
dist_center1<-subset(distances,col==301,select = value)
dist_center2<-subset(distances,col==302,select = value)
dist_center3<-subset(distances,col==303,select = value)
dist_centers<-data.frame(dist_center1,dist_center2,dist_center3)
colnames(dist_centers)<-c("dist_center1","dist_center2","dist_center3")
dist_centers$cluster<-apply(dist_centers, 1, which.min)
df<-cbind(df[1:300,],dist_centers[1:300,])
#plot assignment
p + geom_point(size=7, aes(colour=as.factor(df$cluster))) + geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x") + theme(legend.position="none")
#calculate new centers
x<-tapply(df$x,df$cluster,mean)
y<-tapply(df$y,df$cluster,mean)
kcenters<-data.frame(x,y)
#plot new centers
p + geom_point(size=7, aes(colour=as.factor(df$cluster))) + geom_point(data=kcenters, aes(x, y), size=7, color="black", shape="x") + theme(legend.position="none")
If you run kmeans() with the same initial centers and stop it on first iteration, dfCluster<-kmeans(df,centers=kcenters, iter.max = 1), you get the follow centers:
> dfCluster$centers
x y
1 1.129419 4.905327
2 2.928011 2.880839
3 4.715513 4.766608
These centers do not match with the ones I get in the first iteration of my procedure (#calculate new centers). I have to run it for 14 times (#assigment and #calculate new centers) to obtain them. I don't know the meaning of "iteration" in the kmeans() procedure. Does anybody know?
