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;
/**
* DivisiveLocalClusterer 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.
*
* Specifically, DivisiveLocalClusterer greedily chooses the cluster to split
* based on an evaluation of only the cluster being split. Because of this local
* search of the world, DivisiveLocalClusterer has poor performance in
* determining the number of clusters in the data set. As such, only the methods
* where the exact number of clusters are recommended.
*
* This greedy strategy can also lead to drilling down clusters into small
* parts, and works best when only a small number of clusters are needed.
*
* @author Edward Raff
*/
public class DivisiveLocalClusterer extends KClustererBase
{
private static final long serialVersionUID = 8616401472810067778L;
private KClusterer baseClusterer;
private ClusterEvaluation clusterEvaluation;
public DivisiveLocalClusterer(KClusterer baseClusterer, ClusterEvaluation clusterEvaluation)
{
this.baseClusterer = baseClusterer;
this.clusterEvaluation = clusterEvaluation;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public DivisiveLocalClusterer(DivisiveLocalClusterer toCopy)
{
this(toCopy.baseClusterer.clone(), toCopy.clusterEvaluation.clone());
}
@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)
{
if(designations == null)
designations = 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[clusters][];
/**
* Stores the index from the sub data set into the full data set
*/
final int[][] originalPositions = new int[clusters][dataSet.getSampleSize()];
/**
* Stores the dissimilarity of the splitting of the cluster with the same index value. Negative value indicates not set
*/
final double[] splitEvaluation = new double[clusters];
PriorityQueue clusterToSplit = new PriorityQueue<>(clusters,
(Integer t, Integer t1) -> Double.compare(splitEvaluation[t], splitEvaluation[t1])
);
clusterToSplit.add(0);//We must start out spliting the one cluster of everyone!
Arrays.fill(designations, 0);
//Create initial split we will start from
baseClusterer.cluster(dataSet, 2, parallel, designations);
subDesignation[0] = Arrays.copyOf(designations, designations.length);
for(int i = 0; i < originalPositions[0].length; i++)
originalPositions[0][i] = i;
List dpSubC1 = new ArrayList<>();
List dpSubC2 = new ArrayList<>();
/*
* TODO it could be updated to use the split value to do a search range
* and stop when a large jump occurs. This will perform poorl and
* underestimate the number of clusters, becase it will decend one path
* as splitting clusters improves untill it gets to the correct cluster
* size. Popping back up will then casue an increase, which will cause
* the early termination.
*/
for(int k = 1; k < clusters; k++)
{
int useSplit = clusterToSplit.poll();
int newClusterID = k;
dpSubC1.clear();
dpSubC2.clear();
//Split the data set into its two sub data sets
for(int i = 0; i < subDesignation[useSplit].length; i++)
{
int origPos = originalPositions[useSplit][i];
if(subDesignation[useSplit][i] == 0)
{
dpSubC1.add(dataSet.getDataPoint(origPos));
continue;//We will asigng cluster '1' to be the new cluster number
}
dpSubC2.add(dataSet.getDataPoint(origPos));
designations[origPos] = newClusterID;
}
computeSubClusterSplit(subDesignation, useSplit, dpSubC1,
dataSet, designations, originalPositions,
splitEvaluation, clusterToSplit, parallel);
computeSubClusterSplit(subDesignation, newClusterID, dpSubC2,
dataSet, designations, originalPositions,
splitEvaluation, clusterToSplit, parallel);
}
return designations;
}
/**
* Takes the data set and computes the clustering of a sub cluster, and
* stores its information, and places the result in the queue
*
* @param subDesignation the array of arrays to store the designation array
* for the sub clustering
* @param originalCluster the originalCluster that we want to store the
* split information of
* @param listOfDataPointsInCluster the list of all data points that belong
* to originalCluster
* @param fullDataSet the full original data set
* @param fullDesignations the designation array for the full original data
* set
* @param originalPositions the array of arrays to store the map from and
* index in listOfDataPointsInCluster to its index in the full data
* set.
* @param splitEvaluation the array to store the cluster evaluation of the
* data set
* @param clusterToSplit the priority queue that stores the cluster id and
* sorts based on how good the sub splits were.
*/
private void computeSubClusterSplit(final int[][] subDesignation,
int originalCluster, List listOfDataPointsInCluster, DataSet fullDataSet,
int[] fullDesignations, final int[][] originalPositions,
final double[] splitEvaluation,
PriorityQueue clusterToSplit, boolean parallel)
{
subDesignation[originalCluster] = new int[listOfDataPointsInCluster.size()];
int pos = 0;
for(int i = 0; i < fullDataSet.getSampleSize(); i++)
{
if(fullDesignations[i] != originalCluster)
continue;
originalPositions[originalCluster][pos++] = i;
}
//Cluster the sub cluster
SimpleDataSet dpSubC1DataSet = new SimpleDataSet(listOfDataPointsInCluster);
try
{
baseClusterer.cluster(dpSubC1DataSet, 2, parallel, subDesignation[originalCluster]);
splitEvaluation[originalCluster] = clusterEvaluation.evaluate(subDesignation[originalCluster], dpSubC1DataSet);
clusterToSplit.add(originalCluster);
}
catch (ClusterFailureException ex)
{
splitEvaluation[originalCluster] = Double.POSITIVE_INFINITY;
}
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
return cluster(dataSet, lowK, parallel, designations);
}
@Override
public DivisiveLocalClusterer clone()
{
return new DivisiveLocalClusterer(this);
}
}
Ads help maintain this website.