package jsat.clustering.kmeans;

import java.util.*;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.DataPoint;
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.
*
* Note, that specifying a minimum value of {@code K=1} has a tendency to not be * split by the algorithm, returning the naive result of 1 cluster. It is better * to use at least {@code K=2} as the default minimum, which is what the * implementation will start from when no range of {@code K} is given.
*
* See: Pelleg, D.,&Moore, A. (2000). X-means: Extending K-means with * Efficient Estimation of the Number of Clusters. In ICML (pp. 727–734). * San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. Retrieved from * * here * * @author Edward Raff */ public class XMeans extends KMeans { private static final long serialVersionUID = -2577160317892141870L; private boolean stopAfterFail = false; private boolean iterativeRefine = true; private int minClusterSize = 25; private KMeans kmeans; public XMeans() { this(new HamerlyKMeans()); } public XMeans(KMeans kmeans) { super(kmeans.dm, kmeans.seedSelection, kmeans.rand); this.kmeans = kmeans; this.kmeans.saveCentroidDistance = true; this.kmeans.setStoreMeans(true); } /** * Copy constructor * @param toCopy the object to copy */ public XMeans(XMeans toCopy) { super(toCopy); this.kmeans = toCopy.kmeans.clone(); this.stopAfterFail = toCopy.stopAfterFail; this.iterativeRefine = toCopy.iterativeRefine; this.minClusterSize = toCopy.minClusterSize; } /** * Each new cluster will be tested for improvement according to the BIC * metric. If this is set to {@code true} then an optimization is done that * once a center fails be improved by splitting, 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} , X-Means will * make at most O(k) runs of k-means for the final value of k chosen. When * {@code false} (the default option), at most O(k2) runs of * k-means will occur. * * @param stopAfterFail {@code true} if a centroid shouldn't be re-tested once it * fails to split. */ public void setStopAfterFail(boolean stopAfterFail) { this.stopAfterFail = stopAfterFail; } /** * * @return {@code true} if clusters that fail to split wont be re-tested. * {@code false} if they will. */ public boolean isStopAfterFail() { return stopAfterFail; } /** * 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 * X-Means 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, 2, Math.max(dataSet.getSampleSize()/20, 10), designations); } @Override public int[] cluster(DataSet dataSet, boolean parallel, int[] designations) { return cluster(dataSet, 2, Math.max(dataSet.getSampleSize()/20, 10), parallel, designations); } /** * "p_j is simply the sum of K- 1 class probabilities, M * K centroid * coordinates, and one variance estimate." * * @param K the number of clusters * @param D the number of dimensions * @return the number of free parameters */ private static int freeParameters(int K, int D) { return (K - 1) + (D * K) + 1; } @Override public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations) { final int N = dataSet.getSampleSize(); final int D = dataSet.getNumNumericalVars();//"M" in orig paper if(designations == null || designations.length < dataSet.getSampleSize()) designations = new int[N]; List data = dataSet.getDataVectors(); final List accelCache = dm.getAccelerationCache(data, parallel); /** * The sum of ||x - \mu_i||^2 for each cluster currently kept */ double[] localVar = new double[highK]; int[] localOwned = new int[highK]; //initiate if(lowK >= 2) { means = new ArrayList(); kmeans.cluster(dataSet, accelCache, lowK, means, designations, true, parallel, true, null); for(int i = 0; i < data.size(); i++) { localVar[designations[i]] += Math.pow(kmeans.nearestCentroidDist[i], 2); localOwned[designations[i]]++; } } 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))); localOwned[0] = N; List qi = dm.getQueryInfo(means.get(0)); for(int i = 0; i < data.size(); i++) localVar[0] += Math.pow(dm.dist(i, means.get(0), qi, data, accelCache), 2); } int[] subS = new int[designations.length]; int[] subC = new int[designations.length]; //tract if we should stop testing a mean or not List dontRedo = new ArrayList<>(Collections.nCopies(means.size(), false)); int origMeans; do { origMeans = means.size(); for(int c = 0; c < origMeans; c++) { if(dontRedo.get(c)) continue; /* * Next, in each parent region we run a local K-means (with * K = 2) for each pair of children. It is local in that the * children are fighting each other for the points in the * parent's region: no others */ List X = getDatapointsFromCluster(c, designations, dataSet, subS); final int n = X.size();//NOTE, not the same as N. PAY ATENTION //TODO add the optimization in the paper where we check for movment, and dont test means that haven't mvoed much if(X.size() < minClusterSize || means.size() == highK) continue;//this loop with force it to exit when we hit max K subC = kmeans.cluster(new SimpleDataSet(X), 2, parallel, subC); //call explicitly to force that distance to nearest center is saved List subMean = new ArrayList<>(2); kmeans.cluster(new SimpleDataSet(X), null, 2, subMean, subC, true, parallel, true, null); double[] nearDist = kmeans.nearestCentroidDist; Vec c1 = subMean.get(0); Vec c2 = subMean.get(1); /* * "it determines which one to explore by improving the BIC * locally in each region." * so we only compute BIC from local information */ double newSigma = 0; int size_c1 = 0; for(int i = 0; i < X.size(); i++) { newSigma += Math.pow(nearDist[i], 2); if(subC[i] == 0) size_c1++; } newSigma /= D*(n-2); int size_c2 = n-size_c1; //have needed values, now compute BIC for LOCAL models double localNewBic = size_c1*log(size_c1) + size_c2*log(size_c2) - n*log(n) - n*D/2.0*log(2*PI*newSigma) - D/2.0*(n-2)//that gets us the log like, last line to penalize for bic -freeParameters(2, D)/2.0*log(n); double localOldBic = - n*D/2.0*log(2*PI*localVar[c]/(D*(n-1))) - D/2.0*(n-1)//that gets us the log like, last line to penalize for bic -freeParameters(1, D)/2.0*log(n); if(localOldBic > localNewBic) { if(stopAfterFail)//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, true, parallel, true, null); Arrays.fill(localVar, 0.0); Arrays.fill(localOwned, 0); for(int i = 0; i < data.size(); i++) { localVar[designations[i]] += Math.pow(kmeans.nearestCentroidDist[i], 2); localOwned[designations[i]]++; } } } while (origMeans < means.size()); if(!iterativeRefine)//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) { 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 XMeans clone() { return new XMeans(this); } }

Ads help maintain this website.