package jsat.clustering.hierarchical;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.clustering.KClustererBase;
import jsat.clustering.dissimilarity.UpdatableClusterDissimilarity;
import jsat.math.OnLineStatistics;
import static jsat.clustering.dissimilarity.AbstractClusterDissimilarity.*;
import jsat.utils.IntPriorityQueue;
/**
*
* @author Edward Raff
*/
public class PriorityHAC extends KClustererBase
{
private static final long serialVersionUID = -702489462117567542L;
private UpdatableClusterDissimilarity distMeasure;
/**
* Stores the merge list, each merge is in a pair of 2 values. The final
* merge list should contain the last merged pairs at the front of the array
* (index 0, 1), and the first merges at the end of the array. The left
* value in each pair is the index of the data point that the clusters were
* merged under, while the right value is the index that was merged in and
* treated as no longer its own cluster.
*/
private int[] merges;
private DataSet curDataSet;
public PriorityHAC(UpdatableClusterDissimilarity dissMeasure)
{
this.distMeasure = dissMeasure;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public PriorityHAC(PriorityHAC toCopy)
{
this.distMeasure = toCopy.distMeasure.clone();
if(toCopy.merges != null)
this.merges = Arrays.copyOf(toCopy.merges, toCopy.merges.length);
this.curDataSet = toCopy.curDataSet.shallowClone();
}
@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, 2, (int)Math.sqrt(dataSet.getSampleSize()), parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations)
{
return cluster(dataSet, clusters, clusters, parallel, 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);
}
private void updateDistanceTableAndQueues(List P, int[] I, int k1, int k2, final double[][] distanceMatrix)
{
IntPriorityQueue Pk1 = P.get(k1);
for(int i = 0; i < P.size(); i++)
{
if(I[i] == 0 || i == k2 || i == k1)
continue;
IntPriorityQueue curTargetQ = P.get(i);
curTargetQ.remove(k1);
curTargetQ.remove(k2);
double dis = distMeasure.dissimilarity(k1, I[k1], k2, I[k2], i, I[i], distanceMatrix);
setDistance(distanceMatrix, i, k1, dis);
curTargetQ.add(k1);
Pk1.add(i);
}
}
private List setUpProrityQueue(int[] I, final double[][] distanceMatrix)
{
List P = new ArrayList(I.length);
for(int i = 0; i < I.length; i++)
{
//The row index we are considering
final int supremeIndex = i;
IntPriorityQueue pq = new IntPriorityQueue(I.length, new Comparator()
{
@Override
public int compare(Integer o1, Integer o2)
{
double d1 = getDistance(distanceMatrix, supremeIndex, o1);
double d2 = getDistance(distanceMatrix, supremeIndex, o2);
return Double.compare(d1, d2);
}
}, IntPriorityQueue.Mode.BOUNDED);
//Fill up the priority que
for(int j = 0; j < I.length; j++ )
{
if(i == j)
continue;
pq.add(j);
}
P.add(pq);
}
return P;
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, int[] designations)
{
this.curDataSet = dataSet;
merges = new int[dataSet.getSampleSize()*2-2];
/**
* Keeps track of the current cluster size for the data point. If zero,
* the data point has been merged and is no longer a candidate for
* future consideration. If non zero, it indicates the number of data
* points in its implicit cluster. All points start out in their own
* implicit cluster.
*/
int[] I = new int[dataSet.getSampleSize()];
Arrays.fill(I, 1);
this.curDataSet = dataSet;
/*
* Keep track of the average dist when merging, stop when it becomes abnormaly large
*/
OnLineStatistics distChange = new OnLineStatistics();
final double[][] distanceMatrix = createDistanceMatrix(dataSet, distMeasure);
//Create priority ques for each data point
List P = setUpProrityQueue(I, distanceMatrix);
//We will choose the cluster size as the most abnormal jump in dissimilarity from a merge
int clusterSize = lowK;
double maxStndDevs = Double.MIN_VALUE;
//We now know the dissimilarity matrix & Qs we can begin merging
//We will perform all merges, and store them - and then return a clustering level from the merge history
for(int k = 0; k < I.length-1; k++)
{
int k1 = -1, k2 = -1;
double dk1 = Double.MAX_VALUE, tmp;
for(int i = 0; i < P.size(); i++)
if( I[i] > 0 && (tmp = getDistance(distanceMatrix, i, P.get(i).element())) < dk1)
{
dk1 = tmp;
k1 = i;
k2 = P.get(i).element();
}
//Keep track of the changes in cluster size, and mark if this one was abnormall large
distChange.add(dk1);
if( (I.length - k) >= lowK && (I.length - k) <= highK)//IN the cluster window?
{
double stndDevs = (dk1-distChange.getMean())/distChange.getStandardDeviation();
if(stndDevs > maxStndDevs)
{
maxStndDevs = stndDevs;
clusterSize = I.length-k;
}
}
//We have now found the smalles pair in O(n), first we will update the Qs and matrix. k1 will be the new merged cluster
P.get(k1).clear();//This Q will need all new values
P.get(k2).clear();//This Q will no longer be used
updateDistanceTableAndQueues(P, I, k1, k2, distanceMatrix);
//Now we fix up designations
//Note which clusters were just merged
merges[k*2] = k2;
merges[k*2+1] = k1;
//Update counts
I[k1] += I[k2];
I[k2] = 0;
}
reverseMergeArray();
if(designations == null)
designations = new int[dataSet.getSampleSize()];
designations = assignClusterDesignations(designations, clusterSize);
return designations;
}
/**
* Reverses the merge array so that the front contains the last merges instead of the first.
* This is done so that creating new clusters is accessed in order which is cache friendly.
* This method must be called once before using {@link #assignClusterDesignations(int[], int) }
*/
private void reverseMergeArray()
{
for(int i = 0; i < merges.length/2; i++)
{
int tmp = merges[i];
merges[i] = merges[merges.length-i-1];
merges[merges.length-i-1] = tmp;
}
}
/**
* The PriorityHAC stores its merging order, so that multiple clusterings
* can of different sizes can be obtained without having to recluster the
* data set. This is possible in part because HAC is deterministic.
* This returns true if there is currently a data set and its merge
* order stored.
*
* @return true if you can call for more clusterings,
* false if no data set has been clustered.
*/
public boolean hasStoredClustering()
{
return curDataSet != null;
}
/**
* Returns the assignment array for that would have been computed for the
* previous data set with the desired number of clusters.
*
* @param designations the array to store the assignments in
* @param clusters the number of clusters desired
* @return the original array passed in, or null if no data set has been clustered.
* @see #hasStoredClustering()
*/
public int[] getClusterDesignations(int[] designations, int clusters)
{
if(!hasStoredClustering())
return null;
return assignClusterDesignations(designations, clusters);
}
/**
* Returns the assignment array for that would have been computed for the
* previous data set with the desired number of clusters.
*
* @param clusters the number of clusters desired
* @return the list of data points in each cluster, or null if no
* data set has been clustered.
* @see #hasStoredClustering()
*/
public List> getClusterDesignations(int clusters)
{
if(!hasStoredClustering())
return null;
int[] assignments = new int[curDataSet.getSampleSize()];
return createClusterListFromAssignmentArray(assignments, curDataSet);
}
/**
* Goes through the merge array in order from last merge to first, and sets the cluster assignment for each data point based on the merge list.
* @param designations the array to store the designations in, or null to have a new one created automatically.
* @param clusters the number of clusters to assume
* @return the array storing the designations. A new one will be created and returned if designations was null.
*/
private int[] assignClusterDesignations(int[] designations, int clusters)
{
return assignClusterDesignations(designations, clusters, merges);
}
/**
* Goes through the merge array in order from last merge to first, and sets the cluster assignment for each data point based on the merge list.
* @param designations the array to store the designations in, or null to have a new one created automatically.
* @param clusters the number of clusters to assume
* @param merges the array of merge pairs
* @return the array storing the designations. A new one will be created and returned if designations was null.
*/
protected static int[] assignClusterDesignations(int[] designations, int clusters, int[] merges)
{
int curCluster = 0;
Arrays.fill(designations, -1);
for(int i = 0; i < merges.length; i++)
{
if(designations[merges[i]] == -1)//it has not been assigned
{
if(curCluster < clusters)//It will be a top level cluster
designations[merges[i]] = curCluster++;
else
designations[merges[i]] = designations[merges[i-1]];//The new cluster is always in an odd index, so its parrent is the even index to the left
}
}
return designations;
}
@Override
public PriorityHAC clone()
{
return new PriorityHAC(this);
}
}
Ads help maintain this website.