jsat.clustering

Class GapStatistic

java.lang.Object

jsat.clustering.ClustererBase

jsat.clustering.KClustererBase

jsat.clustering.GapStatistic

All Implemented Interfaces:

java.io.Serializable, Clusterer, KClusterer, Parameterized

public class GapStatistic
extends KClustererBase
implements Parameterized

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 setSamples(int).
The Gap method can be applied to any distance metric and any clustering algorithm. However, it is significantly faster for the EuclideanDistance and was developed with the 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 K satisfying Gap(K) ≥ Gap(K+1) - sd(K+1) what the value of K to use. Instead the condition used is the smallest K such that Gap(K) ≥ Gap(K+1)- sd(K+1) and Gap(K) > 0.
In addition, if no value of 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 K that is capped at 100 when using the Clusterer.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

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
GapStatistic() Creates a new Gap clusterer using k-means as the base clustering algorithm
GapStatistic(GapStatistic toCopy) Copy constructor
GapStatistic(KClusterer base) Creates a new Gap clusterer using the base clustering algorithm given.
GapStatistic(KClusterer base, boolean PCSampling) Creates a new Gap clsuterer using the base clustering algorithm given.
GapStatistic(KClusterer base, boolean PCSampling, int B, DistanceMetric dm) Creates a new Gap clsuterer using the base clustering algorithm given.

Method Summary

Modifier and Type	Method and Description
GapStatistic	clone()
int[]	cluster(DataSet dataSet, boolean parallel, int[] designations) Performs clustering on the given data set.
int[]	cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations)
int[]	cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
DistanceMetric	getDistanceMetric()
double[]	getElogW() Returns the array of expected E[log(Wk)] scores computed from sampling new data sets.
double[]	getElogWkStndDev() Returns the array of standard deviations from the samplings used to compute getElogWkStndDev(), multiplied by sqrt(1+1/B).
double[]	getGap() Returns the array of gap statistic values.
double[]	getLogW() Returns the array of empirical log(Wk) scores computed from the data set last clustered.
int	getSamples()
boolean	isPCSampling()
void	setDistanceMetric(DistanceMetric dm) Sets the distance metric to use when evaluating a clustering algorithm
void	setPCSampling(boolean PCSampling) By default the null distribution is sampled from the bounding hyper-cube of the dataset.
void	setSamples(int B) The Gap statistic is measured by sampling from a reference distribution and comparing with the given data set.

Methods inherited from class jsat.clustering.ClustererBase

createClusterListFromAssignmentArray, getDatapointsFromCluster

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jsat.parameters.Parameterized

getParameter, getParameters

Methods inherited from interface jsat.clustering.KClusterer

cluster, cluster, cluster, cluster, cluster, cluster

Methods inherited from interface jsat.clustering.Clusterer

cluster, cluster, cluster, supportsWeightedData

Constructor Detail

GapStatistic

public GapStatistic()

Creates a new Gap clusterer using k-means as the base clustering algorithm

GapStatistic

public GapStatistic(KClusterer base)

Creates a new Gap clusterer using the base clustering algorithm given.

Parameters:

base - the base clustering method to use for any individual number of clusters

GapStatistic

public GapStatistic(KClusterer base,
                    boolean PCSampling)

Creates a new Gap clsuterer using the base clustering algorithm given.

Parameters:

base - the base clustering method to use for any individual number of clusters

PCSampling - true if the Gap statistic should be computed from a PCA transformed space, or false to go with the uniform bounding hyper cube.

GapStatistic

public GapStatistic(KClusterer base,
                    boolean PCSampling,
                    int B,
                    DistanceMetric dm)

Creates a new Gap clsuterer using the base clustering algorithm given.

Parameters:

base - the base clustering method to use for any individual number of clusters

PCSampling - true if the Gap statistic should be computed from a PCA transformed space, or false to go with the uniform bounding hyper cube.

B - the number of datasets to sample

dm - the distance metric to evaluate with

GapStatistic

public GapStatistic(GapStatistic toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

setDistanceMetric

public void setDistanceMetric(DistanceMetric dm)

Sets the distance metric to use when evaluating a clustering algorithm

Parameters:

dm - the distance metric to use

getDistanceMetric

public DistanceMetric getDistanceMetric()

Returns:

the distance metric used for evaluation

setPCSampling

public void setPCSampling(boolean PCSampling)

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.

Parameters:

PCSampling - true to sample from the projected data, false to do the default and sample from the bounding hyper-cube.

isPCSampling

public boolean isPCSampling()

Returns:

true to sample from the projected data, false to do the default and sample from the bounding hyper-cube.

setSamples

public void setSamples(int B)

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.

Parameters:

B - the number of data sets to sample

getSamples

public int getSamples()

Returns:

the number of data sets sampled

getGap

public double[] getGap()

Returns the array of gap statistic values. Index i of the returned array indicates the gap score for using i+1 clusters. A value of Double.NaN if the score was not computed for that value of K

Returns:

the array of gap statistic values computed, or null if the algorithm hasn't been run yet.

getLogW

public double[] getLogW()

Returns the array of empirical log(W_k) scores computed from the data set last clustered.
Index i of the returned array indicates the gap score for using i+1 clusters. A value of Double.NaN if the score was not computed for that value of K

Returns:

the array of empirical scores from the last run, or null if the algorithm hasn't been run yet

getElogW

public double[] getElogW()

Returns the array of expected E[log(W_k)] scores computed from sampling new data sets.
Index i of the returned array indicates the gap score for using i+1 clusters. A value of Double.NaN if the score was not computed for that value of K

Returns:

the array of sampled expected scores from the last run, or null if the algorithm hasn't been run yet

getElogWkStndDev

public double[] getElogWkStndDev()

Returns the array of standard deviations from the samplings used to compute getElogWkStndDev(), multiplied by sqrt(1+1/B).
Index i of the returned array indicates the gap score for using i+1 clusters. A value of Double.NaN if the score was not computed for that value of K

Returns:

the array of standard deviations from the last run, or null if the algorithm hasn't been run yet

cluster

public int[] cluster(DataSet dataSet,
                     boolean parallel,
                     int[] designations)

Description copied from interface: Clusterer

Performs clustering on the given data set. Parameters may be estimated by the method, or other heuristics performed.

Specified by:

cluster in interface Clusterer

Parameters:

dataSet - the data set to perform clustering on

parallel - true if multiple threads should be used to perform clustering. false if it should be done in a single threaded manner.

designations - the array which will contain the designated values. The array will be altered and returned by the function. If null is given, a new array will be created and returned.

Returns:

the int[]

cluster

public int[] cluster(DataSet dataSet,
                     int clusters,
                     boolean parallel,
                     int[] designations)

Specified by:

cluster in interface KClusterer

cluster

public int[] cluster(DataSet dataSet,
                     int lowK,
                     int highK,
                     boolean parallel,
                     int[] designations)

Specified by:

cluster in interface KClusterer

clone

public GapStatistic clone()

Specified by:

clone in interface Clusterer

Specified by:

clone in interface KClusterer

Specified by:

clone in class KClustererBase