package jsat.clustering.kmeans;
import java.util.*;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.DataPoint;
import jsat.distributions.Normal;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.clustering.SeedSelectionMethods;
import jsat.linear.*;
import static java.lang.Math.*;
/**
* This class provides a method of performing {@link KMeans} clustering when the
* value of {@code K} is not known. It works by recursively splitting means
* up to some specified maximum.
* value.
*
* When the value of {@code K} is specified, the implementation will simply call
* the regular KMeans object it was constructed with.
*
* See: Hamerly, G.,&Elkan, C. (2003). Learning the K in K-Means. In
* seventeenth annual conference on neural information processing systems (NIPS)
* (pp. 281–288). Retrieved from
* here
*
*
* @author Edward Raff
*/
public class GMeans extends KMeans
{
private static final long serialVersionUID = 7306976407786792661L;
private boolean trustH0 = true;
private boolean iterativeRefine = true;
private int minClusterSize = 25;
private KMeans kmeans;
public GMeans()
{
this(new HamerlyKMeans());
}
public GMeans(KMeans kmeans)
{
super(kmeans.dm, kmeans.seedSelection, kmeans.rand);
this.kmeans = kmeans;
kmeans.setStoreMeans(true);
}
public GMeans(GMeans toCopy)
{
super(toCopy);
this.kmeans = toCopy.kmeans.clone();
this.trustH0 = toCopy.trustH0;
this.iterativeRefine = toCopy.iterativeRefine;
this.minClusterSize = toCopy.minClusterSize;
}
/**
* Each new cluster will be tested for normality, with the null hypothesis
* H0 being that the cluster is normal. If this is set to {@code true} then
* an optimization is done that once a center fails to reject the null
* hypothesis, it will never be tested again. This is a safe assumption when
* {@link #setIterativeRefine(boolean) } is set to {@code false}, but
* otherwise may not quite be true.
*
* When {@code trustH0} is {@code true} (the default option), G-Means will
* make at most O(k) runs of k-means for the final value of k chosen. When
* {@code false}, at most O(k2) runs of k-means will occur.
*
* @param trustH0 {@code true} if a centroid shouldn't be re-tested once it
* fails to split.
*/
public void setTrustH0(boolean trustH0)
{
this.trustH0 = trustH0;
}
/**
*
* @return {@code true} if cluster that fail to split wont be re-tested.
* {@code false} if they will.
*/
public boolean getTrustH0()
{
return trustH0;
}
/**
* Sets the minimum size for splitting a cluster.
* @param minClusterSize the minimum number of data points that must be present in a
* cluster to consider splitting it
*/
public void setMinClusterSize(int minClusterSize)
{
if(minClusterSize < 2)
throw new IllegalArgumentException("min cluster size that could be split is 2, not " + minClusterSize);
this.minClusterSize = minClusterSize;
}
/**
*
* @return the minimum number of data points that must be present in a
* cluster to consider splitting it
*/
public int getMinClusterSize()
{
return minClusterSize;
}
/**
* Sets whether or not the set of all cluster centers should be refined at
* every iteration. By default this is {@code true} and part of how the
* GMeans algorithm is described. Setting this to {@code false} can result
* in large speedups at the potential cost of quality.
* @param refineCenters {@code true} to refine the cluster centers at every
* step, {@code false} to skip this step of the algorithm.
*/
public void setIterativeRefine(boolean refineCenters)
{
this.iterativeRefine = refineCenters;
}
/**
*
* @return {@code true} if the cluster centers are refined at every
* step, {@code false} if skipping this step of the algorithm.
*/
public boolean getIterativeRefine()
{
return iterativeRefine;
}
@Override
public int[] cluster(DataSet dataSet, int[] designations)
{
return cluster(dataSet, 1, Math.max(dataSet.getSampleSize()/20, 10), designations);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 1, Math.max(dataSet.getSampleSize()/20, 10), parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
final int N = dataSet.getSampleSize();
//initiate
if(lowK >= 2)
{
designations = kmeans.cluster(dataSet, lowK, parallel, designations);
means = new ArrayList(kmeans.getMeans());
}
else//1 mean of all the data
{
if(designations == null || designations.length < N)
designations = new int[N];
else
Arrays.fill(designations, 0);
means = new ArrayList(Arrays.asList(MatrixStatistics.meanVector(dataSet)));
}
int[] subS = new int[designations.length];
int[] subC = new int[designations.length];
Vec v = new DenseVector(dataSet.getNumNumericalVars());
double[] xp = new double[N];
//tract if we should stop testing a mean or not
List dontRedo = new ArrayList(Collections.nCopies(means.size(), false));
//pre-compute acceleration cache instead of re-computing every refine call
List accelCache = dm.getAccelerationCache(dataSet.getDataVectors(), parallel);
double thresh = 1.8692;//TODO make this configurable
int origMeans;
do
{
origMeans = means.size();
for(int c = 0; c < origMeans; c++)
{
if(dontRedo.get(c))
continue;
//2. Initialize two centers, called “children” of c.
//for now lets just let k-means decide
List X = getDatapointsFromCluster(c, designations, dataSet, subS);
final int n = X.size();//NOTE, not the same as N. PAY ATENTION
if(X.size() < minClusterSize || means.size() == highK)
continue;//this loop with force it to exit when we hit max K
SimpleDataSet subSet = new SimpleDataSet(X);
//3. Run k-means on these two centers in X. Let c1, c2 be the child centers chosen by k-means
subC = kmeans.cluster(subSet, 2, parallel, subC);
List subMean = kmeans.getMeans();
Vec c1 = subMean.get(0);
Vec c2 = subMean.get(1);
/* 4.
* Let v = c1 − c2 be a d-dimensional vector that connects the two
* centers. This is the direction that k-means believes to be
* important for clustering. Then project X onto v:
* x'_i = /||v||^2. X' is a 1-dimensional representation of
* the data projected onto v. Transform X' so that it has mean 0 and
* variance 1.
*/
c1.copyTo(v);
v.mutableSubtract(c2);
double vNrmSqrd = Math.pow(v.pNorm(2), 2);
if(Double.isNaN(vNrmSqrd) || vNrmSqrd < 1e-6)
continue;//can happen when cluster is all the same item (or nearly so)
for(int i = 0; i < X.size(); i++)
xp[i] = X.get(i).getNumericalValues().dot(v)/vNrmSqrd;
//we need this in sorted order later, so lets just sort them now
Arrays.sort(xp, 0, X.size());
DenseVector Xp = new DenseVector(xp, 0, X.size());
Xp.mutableSubtract(Xp.mean());
Xp.mutableDivide(Math.max(Xp.standardDeviation(), 1e-6));
//5.
for(int i = 0; i < Xp.length(); i++)
Xp.set(i, Normal.cdf(Xp.get(i), 0, 1));
double A = 0;
for(int i = 1; i <= Xp.length(); i++)
{
double phi = Xp.get(i-1);
A += (2*i-1)*log(phi) + (2*(n-i)+1)*log(1-phi);
}
A/=-n;
A += -n;
//eq(2)
A *= 1 + 4.0/n - 25.0/(n*n);
if(A <= thresh)
{
if(trustH0)//if we are going to trust that H0 is true forever, mark it
dontRedo.set(c, true);
continue;//passed the test, do not split
}
//else, accept the split
//first, update assignment array. Cluster '0' stays as is, re-set cluster '1'
for(int i = 0; i < X.size(); i++)
if(subC[i] == 1)
designations[subS[i]] = means.size();
//replace current mean and add new one
means.set(c, c1.clone());//cur index in dontRedo stays false
means.add(c2.clone());//add a 'false' for new center
dontRedo.add(false);
}
//"Between each round of splitting, we run k-means on the entire dataset and all the centers to refine the current solution"
if(iterativeRefine && means.size() > 1)
kmeans.cluster(dataSet, accelCache, means.size(), means, designations, false, parallel, false, null);
}
while (origMeans < means.size());
if(!iterativeRefine && means.size() > 1)//if we havn't been refining we need to do so now!
kmeans.cluster(dataSet, accelCache, means.size(), means, designations, false, parallel, false, null);
return designations;
}
@Override
public int getIterationLimit()
{
return kmeans.getIterationLimit();
}
@Override
public void setIterationLimit(int iterLimit)
{
kmeans.setIterationLimit(iterLimit);
}
@Override
public void setSeedSelection(SeedSelectionMethods.SeedSelection seedSelection)
{
//XXX when called from constructor in superclass seed is ignored
if(kmeans != null)//needed when initing
kmeans.setSeedSelection(seedSelection);
}
@Override
public SeedSelectionMethods.SeedSelection getSeedSelection()
{
return kmeans.getSeedSelection();
}
@Override
protected double cluster(DataSet dataSet, List accelCache, int k, List means, int[] assignment, boolean exactTotal, boolean threadpool, boolean returnError, Vec dataPointWeights)
{
return kmeans.cluster(dataSet, accelCache, k, means, assignment, exactTotal, threadpool, returnError, null);
}
@Override
public GMeans clone()
{
return new GMeans(this);
}
}
Ads help maintain this website.