package jsat.clustering;
import java.util.*;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.DataPoint;
import jsat.clustering.evaluation.IntraClusterSumEvaluation;
import jsat.clustering.evaluation.intra.SumOfSqrdPairwiseDistances;
import jsat.clustering.kmeans.HamerlyKMeans;
import jsat.clustering.kmeans.KMeans;
import jsat.linear.*;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.random.RandomUtil;
/**
* This class implements a method for estimating the number of clusters in a
* data set called the Gap Statistic. It works by sampling new datasets from a
* uniform random space, and comparing the sum of squared pairwise distances
* between the sampled data and the real data. The number of samples has a
* significant impact on runtime, and is controlled via {@link #setSamples(int)
* }.
* The Gap method can be applied to any distance metric and any clustering
* algorithm. However, it is significantly faster for the
* {@link EuclideanDistance} and was developed with the {@link KMeans}
* algorithm. Thus that combination is the default when using the no argument
* constructor.
*
* A slight deviation in the implementation from the original paper exists. The
* original paper specifies that the smallest {@code K} satisfying
* {@link #getGap() Gap}(K) ≥ Gap(K+1) - {@link #getElogWkStndDev() sd}(K+1)
* what the value of {@code K} to use. Instead the condition used is the
* smallest {@code K} such that Gap(K) ≥ Gap(K+1)- sd(K+1) and Gap(K) > 0.
*
* In addition, if no value of {@code K} satisfies the condition, the largest
* value of Gap(K) will be used.
*
* Note, by default this implementation uses a heuristic for the max value of
* {@code K} that is capped at 100 when using the
* {@link #cluster(jsat.DataSet) } type methods.
* Note: when called with the desired number of clusters, the result of the base
* clustering algorithm be returned directly.
*
* See: Tibshirani, R., Walther, G.,&Hastie, T. (2001). Estimating the
* number of clusters in a data set via the gap statistic. Journal of the
* Royal Statistical Society: Series B (Statistical Methodology), 63(2),
* 411–423. doi:10.1111/1467-9868.00293
*
* @author Edward Raff
*/
public class GapStatistic extends KClustererBase implements Parameterized
{
private static final long serialVersionUID = 8893929177942856618L;
@ParameterHolder
private KClusterer base;
private int B;
private DistanceMetric dm;
private boolean PCSampling;
private double[] ElogW;
private double[] logW;
private double[] gap;
private double[] s_k;
/**
* Creates a new Gap clusterer using k-means as the base clustering algorithm
*/
public GapStatistic()
{
this(new HamerlyKMeans());
}
/**
* Creates a new Gap clusterer using the base clustering algorithm given.
* @param base the base clustering method to use for any individual number
* of clusters
*/
public GapStatistic(KClusterer base)
{
this(base, false);
}
/**
* Creates a new Gap clsuterer using the base clustering algorithm given.
* @param base the base clustering method to use for any individual number
* of clusters
* @param PCSampling {@code true} if the Gap statistic should be computed
* from a PCA transformed space, or {@code false} to go with the uniform
* bounding hyper cube.
*/
public GapStatistic(KClusterer base, boolean PCSampling)
{
this(base, PCSampling, 10, new EuclideanDistance());
}
/**
* Creates a new Gap clsuterer using the base clustering algorithm given.
* @param base the base clustering method to use for any individual number
* of clusters
* @param PCSampling {@code true} if the Gap statistic should be computed
* from a PCA transformed space, or {@code false} to go with the uniform
* bounding hyper cube.
* @param B the number of datasets to sample
* @param dm the distance metric to evaluate with
*/
public GapStatistic(KClusterer base, boolean PCSampling, int B, DistanceMetric dm )
{
this.base = base;
setSamples(B);
setDistanceMetric(dm);
setPCSampling(PCSampling);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public GapStatistic(GapStatistic toCopy)
{
this.base = toCopy.base.clone();
this.B = toCopy.B;
this.dm = toCopy.dm.clone();
this.PCSampling = toCopy.PCSampling;
if(toCopy.ElogW != null)
this.ElogW = Arrays.copyOf(toCopy.ElogW, toCopy.ElogW.length);
if(toCopy.logW != null)
this.logW = Arrays.copyOf(toCopy.logW, toCopy.logW.length);
if(toCopy.gap != null)
this.gap = Arrays.copyOf(toCopy.gap, toCopy.gap.length);
if(toCopy.s_k != null)
this.s_k = Arrays.copyOf(toCopy.s_k, toCopy.s_k.length);
}
/**
* Sets the distance metric to use when evaluating a clustering algorithm
* @param dm the distance metric to use
*/
public void setDistanceMetric(DistanceMetric dm)
{
this.dm = dm;
}
/**
*
* @return the distance metric used for evaluation
*/
public DistanceMetric getDistanceMetric()
{
return dm;
}
/**
* By default the null distribution is sampled from the bounding hyper-cube
* of the dataset. The accuracy of the sampling can be made more accurate
* (and invariant) by sampling the null distribution based on the principal
* components of the dataset. This will also increase the runtime of the
* algorithm.
* @param PCSampling {@code true} to sample from the projected data, {@code
* false} to do the default and sample from the bounding hyper-cube.
*/
public void setPCSampling(boolean PCSampling)
{
this.PCSampling = PCSampling;
}
/**
*
* @return {@code true} to sample from the projected data, {@code
* false} to do the default and sample from the bounding hyper-cube.
*/
public boolean isPCSampling()
{
return PCSampling;
}
/**
* The Gap statistic is measured by sampling from a reference distribution
* and comparing with the given data set. This controls the number of sample
* datasets to draw and evaluate.
*
* @param B the number of data sets to sample
*/
public void setSamples(int B)
{
if(B <= 0)
throw new IllegalArgumentException("sample size must be positive, not " + B);
this.B = B;
}
/**
*
* @return the number of data sets sampled
*/
public int getSamples()
{
return B;
}
/**
* Returns the array of gap statistic values. Index {@code i} of the
* returned array indicates the gap score for using {@code i+1} clusters. A
* value of {@link Double#NaN} if the score was not computed for that value
* of {@code K}
* @return the array of gap statistic values computed, or {@code null} if
* the algorithm hasn't been run yet.
*/
public double[] getGap()
{
return gap;
}
/**
* Returns the array of empirical log(Wk) scores computed
* from the data set last clustered.
* Index {@code i} of the returned array indicates the gap score for using
* {@code i+1} clusters. A value of {@link Double#NaN} if the score was not
* computed for that value of {@code K}
* @return the array of empirical scores from the last run, or {@code null}
* if the algorithm hasn't been run yet
*/
public double[] getLogW()
{
return logW;
}
/**
* Returns the array of expected E[log(Wk)] scores
* computed from sampling new data sets.
* Index {@code i} of the returned array indicates the gap score for using
* {@code i+1} clusters. A value of {@link Double#NaN} if the score was not
* computed for that value of {@code K}
* @return the array of sampled expected scores from the last run, or
* {@code null} if the algorithm hasn't been run yet
*/
public double[] getElogW()
{
return ElogW;
}
/**
* Returns the array of standard deviations from the samplings used to compute
* {@link #getElogWkStndDev() }, multiplied by sqrt(1+1/B).
* Index {@code i} of the returned array indicates the gap score for using
* {@code i+1} clusters. A value of {@link Double#NaN} if the score was not
* computed for that value of {@code K}
* @return the array of standard deviations from the last run, or
* {@code null} if the algorithm hasn't been run yet
*/
public double[] getElogWkStndDev()
{
return s_k;
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 1, (int) Math.min(Math.max(Math.sqrt(dataSet.getSampleSize()), 10), 100), parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations)
{
return base.cluster(dataSet, clusters, parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
final int D = dataSet.getNumNumericalVars();
final int N = dataSet.getSampleSize();
if(designations == null || designations.length < N)
designations = new int[N];
//TODO we dont need all values in [1, lowK-1) in order to get the gap statistic for [lowK, highK]. So lets not do that extra work.
logW = new double[highK-1];
ElogW = new double[highK-1];
gap = new double[highK-1];
s_k = new double[highK-1];
IntraClusterSumEvaluation ssd = new IntraClusterSumEvaluation(new SumOfSqrdPairwiseDistances(dm));
//Step 1: Cluster the observed data
Arrays.fill(designations, 0);
logW[0] = Math.log(ssd.evaluate(designations, dataSet));//base case
for(int k = 2; k < highK; k++)
{
designations = base.cluster(dataSet, k, parallel, designations);
logW[k-1] = Math.log(ssd.evaluate(designations, dataSet));
}
//Step 2:
//use online statistics and run through all K for each B, so that we minimize the memory use
OnLineStatistics[] expected = new OnLineStatistics[highK-1];
for(int i = 0; i < expected.length; i++)
expected[i] = new OnLineStatistics();
//dataset object we will reuse
SimpleDataSet Xp = new SimpleDataSet(new CategoricalData[0], D);
for(int i = 0; i < N; i++)
Xp.add(new DataPoint(new DenseVector(D)));
Random rand = RandomUtil.getRandom();
//info needed for sampling
//min/max for each row/col to smaple uniformly from
double[] min = new double[D];
double[] max = new double[D];
Arrays.fill(min, Double.POSITIVE_INFINITY);
Arrays.fill(max, Double.NEGATIVE_INFINITY);
final Matrix V_T;//the V^T from [U, D, V] of SVD decomposation
if(PCSampling)
{
SingularValueDecomposition svd = new SingularValueDecomposition(dataSet.getDataMatrix());
//X' = X V , from generation strategy (b)
Matrix tmp = dataSet.getDataMatrixView().multiply(svd.getV());
for(int i = 0; i < tmp.rows(); i++)
for(int j = 0; j < tmp.cols(); j++)
{
min[j] = Math.min(tmp.get(i, j), min[j]);
max[j] = Math.max(tmp.get(i, j), max[j]);
}
V_T = svd.getV().transpose();
}
else
{
V_T = null;
OnLineStatistics[] columnStats = dataSet.getOnlineColumnStats(false);
for(int i = 0; i < D; i++)
{
min[i] = columnStats[i].getMin();
max[i] = columnStats[i].getMax();
}
}
//generate B reference datasets
for(int b = 0; b < B; b++)
{
for (int i = 0; i < N; i++)//sample
{
Vec xp = Xp.getDataPoint(i).getNumericalValues();
for (int j = 0; j < D; j++)
xp.set(j, (max[j] - min[j]) * rand.nextDouble() + min[j]);
}
if(PCSampling)//project if wanted
{
//Finally we back-transform via Z = Z' V^T to give reference data Z
//TODO batch as a matrix matrix op would be faster, but use more memory
Vec tmp = new DenseVector(D);
for (int i = 0; i < N; i++)
{
Vec xp = Xp.getDataPoint(i).getNumericalValues();
tmp.zeroOut();
xp.multiply(V_T, tmp);
tmp.copyTo(xp);
}
}
//cluster each one
Arrays.fill(designations, 0);
expected[0].add(Math.log(ssd.evaluate(designations, Xp)));//base case
for(int k = 2; k < highK; k++)
{
designations = base.cluster(Xp, k, parallel, designations);
expected[k-1].add(Math.log(ssd.evaluate(designations, Xp)));
}
}
//go through and copmute gap
int k_first = -1;
int biggestGap = 0;//used as a fall back incase the original condition can't be satisfied in the specified range
for (int i = 0; i < gap.length; i++)
{
gap[i] = (ElogW[i] = expected[i].getMean()) - logW[i];
s_k[i] = expected[i].getStandardDeviation() * Math.sqrt(1 + 1.0 / B);
//check original condition first
int k = i + 1;
if (i > 0 && lowK <= k && k <= highK)
if (k_first == -1 && gap[i - 1] >= gap[i] - s_k[i] && gap[i-1] > 0)
k_first = k - 1;
//check backup
if(gap[i] > biggestGap && lowK <= k && k <= highK)
biggestGap = i;
}
if(k_first == -1)//never satisfied our conditions?
k_first = biggestGap+1;//Maybe we should go back and pick the best gap k we can find?
if(k_first == 1)//easy case
{
Arrays.fill(designations, 0);
return designations;
}
return base.cluster(dataSet, k_first, parallel, designations);
}
@Override
public GapStatistic clone()
{
return new GapStatistic(this);
}
}
Ads help maintain this website.