ML-Class Ex 7 – kMeans clustering

ML-Class Ex 7 - kMeans clustering

Posted by ygc on December 24, 2011 Leave a comment (2) Go to comments

The K-means algorithm is a method to automatically cluster similar data examples together.

The intuition behind K-means is an iterative procedure that starts by guessing the initial centroids, and then refines this guess by repeatedly assigning examples to their closest centroids and then recomputing the centroids based on the assignments.

This algorithm was implemented as follows:

^?View Code RSPLUS

kMeansInitCentroids <- function(X, K) {
    rand.idx <- sample(1:nrow(X), K)
    centroids <- X[rand.idx,]
    return(centroids)
}
 
findClosestCentroids <- function(X, centroids) {
    ## finding closest centroids
 
    # set K
    K <- nrow(centroids)
 
    idx <- sapply(1:nrow(X), function(i) {
        which.min(
                  sapply(1:K, function(j) {
                      sum(
                          (X[i,]-centroids[j,])^2
                          )
                  })
                  )
    })
    return(idx)
}
 
computeCentroids <- function(X, idx, K) {
    centroids <- sapply(1:K, function(i) colMeans(X[idx == i,]))
    centroids <- t(centroids)
    return(centroids)
}
 
runkMeans <- function(X, K, max.iter = 10, plot=F, plot.progress=F) {
    initCentroids <- kMeansInitCentroids(X, K)
    K <- nrow(initCentroids)
    centroids <- initCentroids
    preCentroids <- centroids
    for (i in 1:max.iter) {
        idx <- findClosestCentroids(X, centroids)
        centroids <- computeCentroids(X, idx, K)
        if (plot.progress) {
            preCentroids <- rbind(preCentroids, centroids)
        }
    }
    xx <- data.frame">data.frame(X, cluster=as.factor(idx))
    if(plot) {
        p <- ggplot(xx, aes(V1, V2))+geom_point(aes(color=cluster))
        if (plot.progress) {
            preCentroids <- data.frame">data.frame(preCentroids,
                                       idx=rep(1:3, max.iter+1))
            p <- p+geom_point(data=preCentroids,
                              aes(x=V1, y=V2)) +
                geom_path(data=preCentroids,
                          aes(x=V1, y=V2, group=idx))
        }
        print(p)
    }
    return(xx)
}

After implemented this algorithm, I applied it to the dataset provided in ML-Class Ex 7.

^?View Code RSPLUS

## dataset was converted from ML-class exercise 7  ex7data2.mat.
X <- read.delim("d:/ex7data2.txt", header=F)
K <- 3
xx <- runkMeans(X,K, plot=TRUE, plot.progress=TRUE)