package jsat.clustering.hierarchical;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.clustering.KClustererBase;
import static jsat.clustering.dissimilarity.AbstractClusterDissimilarity.createDistanceMatrix;
import jsat.clustering.dissimilarity.ClusterDissimilarity;
import jsat.math.OnLineStatistics;
import jsat.utils.IntSet;
/**
* Provides a naive implementation of hierarchical agglomerative clustering
* (HAC). This means the clustering is built from the bottom up, merging points
* into clusters. HAC clustering is deterministic. The naive implementation runs
* in O(n3) time.
*
* NOTE: This implementation does not currently support parallel clustering.
*
*
* @author Edward Raff
*/
public class SimpleHAC extends KClustererBase
{
private static final long serialVersionUID = 7138073766768205530L;
/**
* notion behind the large stnd devs is that as the clustering progresses,
* the min value is (usually) monotonically rising, so we would like a
* bigger jump
*/
private double stndDevs = 3.5;
private ClusterDissimilarity dissMeasure;
public SimpleHAC(ClusterDissimilarity disMeasure)
{
this.dissMeasure = disMeasure;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public SimpleHAC(SimpleHAC toCopy)
{
this(toCopy.dissMeasure.clone());
this.stndDevs = toCopy.stndDevs;
}
@Override
public int[] cluster(DataSet dataSet, int[] designations)
{
return cluster(dataSet, 2, (int)Math.sqrt(dataSet.getSampleSize()), designations);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, designations);
}
@Override
public int[] cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations)
{
return cluster(dataSet, clusters, designations);
}
@Override
public int[] cluster(DataSet dataSet, int clusters, int[] designations)
{
return cluster(dataSet, clusters, clusters, designations);
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
return cluster(dataSet, lowK, highK, designations);
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, int[] designations)
{
if(designations == null)
designations = new int[dataSet.getSampleSize()];
//Keep track of the average dis when merging, stop when it becomes abnormaly large
OnLineStatistics disChange = new OnLineStatistics();
//Represent each cluster by a set of indices, intialy each data point is its own cluster
List> clusters = new ArrayList>(dataSet.getSampleSize());
for(int i =0; i < dataSet.getSampleSize(); i++)
{
Set set = new IntSet();
set.add(i);
clusters.add(set);
}
double[][] distanceMatrix = createDistanceMatrix(dataSet, dissMeasure);
while( clusters.size() > lowK)
{
double lowestDiss = Double.MAX_VALUE, tmp;
int a = 0, b = 1;
//N^2 search for the most similar pairing of clusters
for(int i = 0; i < clusters.size(); i++)
for(int j = i+1; j < clusters.size(); j++)
{
if( (tmp = dissMeasure.dissimilarity(clusters.get(i), clusters.get(j), distanceMatrix)) < lowestDiss)
{
lowestDiss = tmp;
a = i;
b = j;
}
}
if(clusters.size() <= highK)//Then we check if we should stop early
{
if(disChange.getMean() + disChange.getStandardDeviation() * stndDevs < lowestDiss)
break;//Abnormaly large difference, we assume we are forcing two real & sperate clusters into one group
}
disChange.add(lowestDiss);
//Merge clusters , a < b is gaurenteed by the loop structure
clusters.get(a).addAll(clusters.remove(b));
}
//Now that we have the assigments, we must set them
int curClusterID = 0;
for(Set clustering : clusters)
{
for(int index : clustering)
designations[index] = curClusterID;
curClusterID++;
}
return designations;
}
@Override
public SimpleHAC clone()
{
return new SimpleHAC(this);
}
}
Ads help maintain this website.