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();

        }
    }
}
______________________________________________________________________________

Jaro Winkler Distance

Jaro Winkler Distance calculates a normalized score on the similarity of two strings. It is based on the number of matching characters in the string pair and the number of transpositions. The score is between 0 (no similarity) and 1(exact match). Transposition implies that adjoining letters can be swapped. Also it gives more weightage to beginning of the string. Used in finding record linkage/data linkage.

For example:

JaroWinkler (sun , sun) = 1.0
JaroWinkler (sun , snu) = 0.5555555820465088
JaroWinkler (sun , sunday) = 0.8833333253860474

The first thing to notice is that unlike other distance metrics such as Hamming Distance, Levenshtein Distance, Damerau-Levenshtein Distance, the Jaro Winkler Distance gives out a real number between 0 to 1. 0 indicating that the strings are totally dissimilar where as 1 represents two strings being completely similar. Since we now the maximum similarity/dissimilarity this metric may be more useful in clustering strings as compared to other distance metrics.

The code uses org.apache.lucene libraries but there are other libraries that can also compute the Jaro Winkler Distance

______________________________________________________________________________

import org.apache.lucene.search.spell.JaroWinklerDistance;

public class DistanceDemo {

static String str1 = "sun";

static String str2 = "snu";

static String str3 = "sunday";

public static void main(String[] args) {

double similarity = 0;

JaroWinklerDistance jd = new JaroWinklerDistance();

similarity = jd.getDistance(str1,str1);

System.out.println("JaroWinkler Distance distance between "+str1+" and "+str1+" : "+similarity);

similarity = jd.getDistance(str1,str2);

System.out.println("JaroWinkler distance between "+str1+" and "+str2+" : "+similarity);

similarity = jd.getDistance(str1,str3);

System.out.println("JaroWinkler distance between "+str1+" and "+str3+" : "+similarity);

}

}

______________________________________________________________________________

Damerau-Levenshtein Distance

Damerau-Levenshtein Distance is similar to Levenshtein distance. Originally, invented to detect short spelling mistakes in strings. Allows all the edits that are allowed in Levenshtein distance, additionally allows swapping of adjacent characters. Uses: in DNA re-sequencing, Fraud Detection.

For example

Damerau-Levenshtein (sun , sun) = 0
Damerau-Levenshtein (sun , son) = 1
Damerau-Levenshtein (sun , snu) = 1

Levenshtein (sun , sun) = 0
Levenshtein (sun , son) = 1
Levenshtein (sun , snu) = 2

The code uses Ling-Pipe library, the library has a license attached to it that can be accessed here

______________________________________________________________________________
import com.aliasi.spell.EditDistance;
import com.aliasi.util.Distance;


public class DistanceDemo {
static String str1 = "sun";
static String str2 = "son";
static String str3 = "snu";


public static void main(String[] args) {

Distance<CharSequence> damerauLevensteinWithTranspose  = new EditDistance(true);
Distance<CharSequence> damerauLevensteinWithOutTranspose  = new EditDistance(false);

double distancewt = damerauLevensteinWithTranspose.distance(str1,str1);
double distancewot = damerauLevensteinWithOutTranspose.distance(str1,str1);
System.out.println("Levenshtein distance between "+str1+" and "+str1+" : "+distancewt);
System.out.println("Damerau Levenshtein (transpose allowed) distance between "+str1+" and "+str1+" : "+distancewot);

distancewt = damerauLevensteinWithTranspose.distance(str1,str2);
distancewot = damerauLevensteinWithOutTranspose.distance(str1,str2);
System.out.println("Levenshtein distance between "+str1+" and "+str2+" : "+distancewt);
System.out.println("Damerau Levenshtein (transpose allowed) distance between "+str1+" and "+str2+" : "+distancewot);

distancewt = damerauLevensteinWithTranspose.distance(str1,str3);
distancewot = damerauLevensteinWithOutTranspose.distance(str1,str3);
System.out.println("Levenshtein distance between "+str1+" and "+str3+" : "+distancewt);
System.out.println("Damerau Levenshtein (transpose allowed) distance between "+str1+" and "+str3+" : "+distancewot);


}


}

______________________________________________________________________________

Levenshtein Distance

Levenshtein Distance measures the minimum number of changes needed to change one String into another. Change can be a single character modification including deletion, insertion or substitution. Unlike the previously mentioned Hamming distance, this can compute distance between two unequal length strings. Used in spell-checker applications.

For example:

Levenshtein (sun , sun) = 0
Levenshtein (sun , son) = 1

Levenshtein (sun , moon) = 3

The Code uses the org.apache.commons.lang3.StringUtils library that can be downloaded from here
Two function can be used for computing the distance:

• StringUtils.getLevenshteinDistance(String,String)
• StringUtils.getLevenshteinDistance(String,String,Threshold)

The threshold can be used to limit the distance calculation upto a certain limit
______________________________________________________________________________

import org.apache.commons.lang3.StringUtils;


public class DistanceDemo {
static String str1 = "sun";
static String str2 = "son";
static String str3 = "moon";


public static void main(String[] args) {


int distance = StringUtils.getLevenshteinDistance(str1,str1);

if (distance != -1) {
System.out.println("Levenshtein distance between "+str1+" and "+str1+" : "+distance);
}else{
System.out.println("Cannot compute the Levenshtein distance betwen "+str1+" and "+str1);
}

distance = StringUtils.getLevenshteinDistance(str1, str2);

if (distance != -1) {
System.out.println("Levenshtein distance between "+str1+" and "+str2+" : "+distance);
}else{
System.out.println("Cannot compute the Levenshtein distance betwen "+str1+" and "+str2);
}

distance = StringUtils.getLevenshteinDistance(str1, str3);

if (distance != -1) {
System.out.println("Levenshtein distance between "+str1+" and "+str3+" : "+distance);
}else{
System.out.println("Cannot compute the Levenshtein distance betwen "+str1+" and "+str3);
}
}

}______________________________________________________________________

Hamming Distance

Hanming Distance gives an idea about the minimum number of edits required to transform one string to another. Note that for Hamming distance to work the strings must be of equal length.

For example,

Hamming Distance (  sun ,  son) = 1
Hamming Distance (  sun ,  sun) = 0

The code
______________________________________________________________________________

import thundering.typhoons.distance.Hamming;

public class DistanceDemo {
static String str1 = "sun";
static String str2 = "son";
static String str3 = "moon";
public static void main(String[] args) {


int distance = Hamming.getHammingDistance(str1, str1);

if (distance != -1) {
System.out.println("Hamming distance between "+str1+" and "+str1+" : "+distance);
}else{
System.out.println("Cannot compute the hamming distance betwen "+str1+" and "+str1);
}

distance = Hamming.getHammingDistance(str1, str2);

if (distance != -1) {
System.out.println("Hamming distance between "+str1+" and "+str2+" : "+distance);
}else{
System.out.println("Cannot compute the hamming distance betwen "+str1+" and "+str2);
}

distance = Hamming.getHammingDistance(str1, str3);

if (distance != -1) {
System.out.println("Hamming distance between "+str1+" and "+str3+" : "+distance);
}else{
System.out.println("Cannot compute the hamming distance betwen "+str1+" and "+str3);
}
}

}

package thundering.typhoons.distance;

public class Hamming {

public static int getHammingDistance(String str1, String str2) {

if (str1 == null || str2 == null) {
return Constants.CANNOT_COMPARE;
}

if (str1.length() != str2.length()) {
return Constants.CANNOT_COMPARE;
}

int distance = 0;
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
distance++;
}
}

return distance;

}


}
______________________________________________________________________________

output:
Hamming distance between sun and sun : 0
Hamming distance between sun and son : 1
Cannot compute the hamming distance betwen sun and moon

Clustering algorithm for strings

A specific instance of data clustering is string matching. A string can be described as a finite sequence of alphabets. In this particular scenario we wish to cluster together strings that are the most similar.

The word similar can be interpreted in a number of ways. For instance, consider the three words: sun, son, star. Based on the sequence of the symbols we can say that sun and son are more similar than sun and star. Essentially what we are trying to do is to find the distance between two strings in order to compare similarity. They are a number of well known ways of computing distance.

Hanming Distance: It gives an idea about the minimum number of edits required to transform one string to another. Note that for Hamming distance to work the strings must be of equal length. It is used in applications in communication systems, information theory, cryptography. For an example application click here

Levenshtein Distance: It measures the minimum number of changes needed to change one String into another. Change can be a single character modification including deletion, insertion or substitution. Unlike the previously mentioned Hamming distance, this can compute distance between two unequal length strings. Used in spell-checker applications. For an example application click here

Damerau-Levenshtein Distance: Similar to Levenshtein distance. Originally, invented to detect short spelling mistakes in strings. Allows all the edits that are allowed in Levenshtein distance, additionally allows swapping of adjacent characters. Uses: in DNA re-sequencing, Fraud Detection. For example application click here

Jaro Winkler Distance: Calculates a normalised score on the similarity of two strings. It is based on the number of matching characters in the string pair and the number of transpositions. The score is between 0 (no similarity) and 1(exact match). Transposition implies that adjoining letters can be swapped. Also it gives more weightage to beginning of the string. Used in finding record linkage/data linkage. For an example application click here

Parsing HTML files with JSOUP

Often times we need to obtain data from sources on internet, or it might just be the case that you have a some data that you wish to extract from an HTML file. So in such scenario you could write your own parser, which would be not very efficient and may be buggy or you could a existing library such as JSOUP to do the job. In my particular scenario, I had a HTML table like this one

______________________________________________________________________________

Table 1

A	B	C	100
D	E	F	200
G	H	I	300

Table 2

A1	B1	C1	100
D1	E1	F1	200
G1	H1	I1	300

______________________________________________________________________________

 My code for parsing these HTML tables is as follows:

______________________________________________________________________________

package thundering.typhoons.example;

import java.io.File;
import java.io.IOException;

import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.nodes.Element;
import org.jsoup.select.Elements;

public class Main {

    public static void main(String[] args) {

        String pathToHtmlFile = "test.htm";

        try {
            parse(pathToHtmlFile);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void parse(String pathToHtmlFile) throws IOException {
        Document doc;

        File input = new File(pathToHtmlFile);

        doc = Jsoup.parse(input, "UTF-8");

        Elements heads = doc.select("h1");
        for (Element head : heads) {
            System.out.println("Contains header : " + head.text());
        }

        Elements tables = doc.select("table");
        for (Element table : tables) {

            System.out.println("Reading table : " + table.text());
            int elemInTable = table.select("td").size();
            int tableRows = table.select("tr").size();
            int numberofCols = (elemInTable / tableRows);

            System.out.println("Number of rows " + tableRows + ", number of columns : " + numberofCols);

            int j;
            for (j = 0; j < (elemInTable / numberofCols); j++) {
                String[] cols = new String[numberofCols];
                int k;
                for (k = 0; k < numberofCols; k++) {
                    cols[k] = table.select("td").get(numberofCols * j + k)
                            .text();
                    System.out.print(cols[k]+" ");

                }
                System.out.println();
            }
        }
    }
}