package jsat.clustering.hierarchical;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.DataPoint;
import jsat.clustering.*;
import jsat.clustering.evaluation.ClusterEvaluation;
/**
* DivisiveGlobalClusterer is a hierarchical clustering method that works by
* splitting the data set into sub trees from the top down. Unlike many top-up
* methods, such as {@link SimpleHAC}, top-down methods require another
* clustering method to perform the splitting at each iteration. If the base
* method is not deterministic, then the top-down method will not be
* deterministic.
*
* Like many HAC methods, DivisiveGlobalClusterer will store the merge order of
* the clusters so that the clustering results for many k can be obtained.
* It is limited to the range of clusters successfully computed before.
*
* Specifically, DivisiveGlobalClusterer greedily chooses the cluster to split
* based on an evaluation of all resulting clusters after a split. Because of this global
* search of the world, DivisiveLocalClusterer has can make a good estimate of
* the number of clusters in the data set. The quality of this result is
* dependent on the accuracy of the {@link ClusterEvaluation} used. This quality
* comes at the cost of execution speed, as more and more large evaluations of
* the whole dataset are needed at each iteration. If execution speed is more
* important, {@link DivisiveLocalClusterer} should be used instead, which
* requires only a fixed number of evaluations per iteration.
*
* @author Edward Raff
*/
public class DivisiveGlobalClusterer extends KClustererBase
{
private static final long serialVersionUID = -9117751530105155090L;
private KClusterer baseClusterer;
private ClusterEvaluation clusterEvaluation;
private int[] splitList;
private int[] fullDesignations;
private DataSet originalDataSet;
public DivisiveGlobalClusterer(KClusterer baseClusterer, ClusterEvaluation clusterEvaluation)
{
this.baseClusterer = baseClusterer;
this.clusterEvaluation = clusterEvaluation;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public DivisiveGlobalClusterer(DivisiveGlobalClusterer toCopy)
{
this.baseClusterer = toCopy.baseClusterer.clone();
this.clusterEvaluation = toCopy.clusterEvaluation.clone();
if(toCopy.splitList != null)
this.splitList = Arrays.copyOf(toCopy.splitList, toCopy.splitList.length);
if(toCopy.fullDesignations != null)
this.fullDesignations = Arrays.copyOf(toCopy.fullDesignations, toCopy.fullDesignations.length);
this.originalDataSet = toCopy.originalDataSet.shallowClone();
}
@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 lowK, int highK, boolean parallel, int[] designations)
{
if(designations == null)
designations = new int[dataSet.getSampleSize()];
/**
* Is used to copy the value of designations and then alter to test the quality of a potential new clustering
*/
int[] fakeWorld = new int[dataSet.getSampleSize()];
/**
* For each current cluster, we store the clustering results if we
* attempt to split it into two.
*
* Each row needs to be re-set since the clustering methods will use the length of the cluster size
*/
final int[][] subDesignation = new int[highK][];
/**
* Stores the index from the sub data set into the full data set
*/
final int[][] originalPositions = new int[highK][dataSet.getSampleSize()];
/**
* List of Lists for holding the data points of each cluster in
*/
List> pointsInCluster = new ArrayList<>(highK);
for(int i = 0; i < highK; i++)
pointsInCluster.add(new ArrayList<>(dataSet.getSampleSize()));
/**
* Stores the dissimilarity of the splitting of the cluster with the
* same index value. Negative value indicates not set.
* Special values:
*
* - NEGATIVE_INFINITY : value never used
* - -1 : clustering computed, but no current global evaluation
* - >=0 : cluster computed, current value is the evaluation for using this split
*
*/
final double[] splitEvaluation = new double[highK];
Arrays.fill(splitEvaluation, Double.NEGATIVE_INFINITY);
/**
* Records the order in which items were split
*/
splitList = new int[highK*2-2];
int bestK = -1;
double bestKEval = Double.POSITIVE_INFINITY;
//k is the current number of clusters, & the ID of the next cluster
for(int k = 1; k < highK; k++)
{
double bestSplitVal = Double.POSITIVE_INFINITY;
int bestID = -1;
for (int z = 0; z < k; z++)//TODO it might be better to do this loop in parallel
{
if(Double.isNaN(splitEvaluation[z]))
continue;
else if (splitEvaluation[z] == Double.NEGATIVE_INFINITY)//at most 2 will hit this per loop
{//Need to compute a split for that cluster & set up helper structures
List clusterPointsZ = pointsInCluster.get(z);
clusterPointsZ.clear();
for (int i = 0; i < dataSet.getSampleSize(); i++)
{
if (designations[i] != z)
continue;
originalPositions[z][clusterPointsZ.size()] = i;
clusterPointsZ.add(dataSet.getDataPoint(i));
}
subDesignation[z] = new int[clusterPointsZ.size()];
if(clusterPointsZ.isEmpty())//Empty cluster? How did that happen...
{
splitEvaluation[z] = Double.NaN;
continue;
}
SimpleDataSet subDataSet = new SimpleDataSet(clusterPointsZ);
try
{
baseClusterer.cluster(subDataSet, 2, parallel, subDesignation[z]);
}
catch(ClusterFailureException ex)
{
splitEvaluation[z] = Double.NaN;
continue;
}
}
System.arraycopy(designations, 0, fakeWorld, 0, fakeWorld.length);
for(int i = 0; i < subDesignation[z].length; i++)
if (subDesignation[z][i] == 1)
fakeWorld[originalPositions[z][i]] = k;
try
{
splitEvaluation[z] = clusterEvaluation.evaluate(fakeWorld, dataSet);
}
catch (Exception ex)//Can occur if one of the clusters has size zeros
{
splitEvaluation[z] = Double.NaN;
continue;
}
if (splitEvaluation[z] < bestSplitVal)
{
bestSplitVal = splitEvaluation[z];
bestID = z;
}
}
//We now know which cluster we should use the split of
for (int i = 0; i < subDesignation[bestID].length; i++)
if (subDesignation[bestID][i] == 1)
designations[originalPositions[bestID][i]] = k;
//The original clsuter id, and the new one should be set to -Inf
splitEvaluation[bestID] = splitEvaluation[k] = Double.NEGATIVE_INFINITY;
//Store a split list
splitList[(k-1)*2] = bestID;
splitList[(k-1)*2+1] = k;
if(lowK-1 <= k && k <= highK-1)//Should we stop?
{
if(bestSplitVal < bestKEval)
{
bestKEval = bestSplitVal;
bestK = k;
// System.out.println("Best k is now " + k + " at " + bestKEval);
}
}
}
fullDesignations = Arrays.copyOf(designations, designations.length);
//Merge the split clusters back to the one that had the best score
for (int k = splitList.length/2-1; k >= bestK; k--)
{
if (splitList[k * 2] == splitList[k * 2 + 1])
continue;//Happens when we bail out early
for (int j = 0; j < designations.length; j++)
if (designations[j] == splitList[k * 2 + 1])
designations[j] = splitList[k * 2];
}
originalDataSet = dataSet;
return designations;
}
/**
* Returns the clustering results for a specific k number of clusters
* for a previously computed data set. If the data set did not compute up to
* the value k null will be returned.
* @param targetK the number of clusters to get the result for.
* @return an array containing the assignments for each cluster in the
* original data set.
* @throws ClusterFailureException if no prior data set had been clustered
*/
public int[] clusterSplit(int targetK)
{
if(originalDataSet == null)
throw new ClusterFailureException("No prior cluster stored");
int[] newDesignations = Arrays.copyOf(fullDesignations, fullDesignations.length);
//Merge the split clusters back to the one that had the best score
for (int k = splitList.length/2-1; k >= targetK; k--)
{
if (splitList[k * 2] == splitList[k * 2 + 1])
continue;//Happens when we bail out early
for (int j = 0; j < newDesignations.length; j++)
if (newDesignations[j] == splitList[k * 2 + 1])
newDesignations[j] = splitList[k * 2];
}
return newDesignations;
}
@Override
public DivisiveGlobalClusterer clone()
{
return new DivisiveGlobalClusterer(this);
}
}
Ads help maintain this website.