K - Means Clustering

Often times to make sense of the data we must categorize or cluster it. It  is highly desirable to have automatic ways of doing. K-means is one of such algorithm for clustering. Given a n data points and k clusters, k-means can divide all the data into k clusters. The intuition behind k-means is very simple.
We want to divided the data in k cluster such that data points in each cluster are closer to each other than data points in other clusters. More precisely speaking closer here implies minimize the within-cluster sum of square. Now I will try to explain the algorithm without getting too technical

You start by randomly choosing k data points from the input and name them cluster heads. This cluster heads sort of represents the cluster, so all data points with in the cluster should be (in the ideal case) closer to their cluster heads then to other cluster heads. (Closer is simply can be simply described square of distance between the data point and the cluster head). We then divide all the data points into k cluster based on the distance of a data point from a cluster head. Since we being by choosing random cluster heads, the clustering is not optimal (in fact, it is probably useless). So next we compute a new cluster heads based on the newly computed clusters and recompute the compute the cluster. This new cluster heads may divide the data better than the previous iterations but we can still do better. So we re compute the cluster and reform the cluster. In fact, it is possible that this process (of cluster head computation and cluster formation) may go on for quite a while, so we need a backup termination condition. People usually specify a limit on number of iteration or desired accuracy for the cluster.

Here is example implementation of k-means cluster. This uses the jung library
Here we  have data set with elements { 0, 1, 2, 2, 1, 3, 9, 8, 10 , 7 }. After the computation this program with output

0    Cluster size : 4
    cluster head for cluster at : 8.5
    cluster elements : 10.0 9.0 8.0 7.0
1    Cluster size : 6
    cluster head for cluster at : 1.5
    cluster elements : 3.0 1.0 0.0 2.0 1.0 2.0

______________________________________________________________________________
package thundering.typhoons.example;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import edu.uci.ics.jung.algorithms.util.DiscreteDistribution;
import edu.uci.ics.jung.algorithms.util.KMeansClusterer;
import edu.uci.ics.jung.algorithms.util.KMeansClusterer.NotEnoughClustersException;

public class KMeansExample {

    protected KMeansClusterer kmc;
    protected Map object_locations;
    private static int numberOfCluster = 2;
    private static double convergence_threshold = 0.05;
    private static int max_iterations = 200;

    public static void main(String[] args) throws Exception {
        KMeansExample kme = new KMeansExample();
        kme.setUp();
        kme.testCluster();

    }

    public void setUp() {
        Object[] objects = new Object[10];
        for (int i = 0; i < objects.length; i++)
            objects[i] = new Object();
        double[][] locations = { { 0 }, { 1 }, { 2 }, { 2 }, { 1 }, { 3 }, { 9 }, { 8 }, { 10 } , { 7 } };
        object_locations = new HashMap();
        for (int i = 0; i < objects.length; i++)
            object_locations.put(objects[i], locations[i]);

        kmc = new KMeansClusterer(max_iterations, convergence_threshold);
    }

    public void testCluster() {
        Collection clusters = null;
        try {
            clusters = kmc.cluster(object_locations, numberOfCluster);
        } catch (NotEnoughClustersException nece) {
            System.out
                    .println("unexpected System.out.printlnure: NotEnoughClustersException thrown");
        }

        Iterator iter = clusters.iterator();
        for (int j = 0; j < numberOfCluster; j++) {
            Map<Object, double[]> cluster = (Map) iter.next();

            double[] centroid = DiscreteDistribution.mean(cluster.values());
            System.out.println(j + "\tCluster size : " + cluster.size());

            for (double d : centroid) {
                System.out.println("\tcluster head for cluster at : " + d);
            }
            System.out.print("\tcluster elements :");
            for (double[] val : cluster.values()) {
                for (double d : val) {
                    System.out.print(" " + d);
                }
            }
            System.out.println();

        }
    }
}
______________________________________________________________________________