package jsat.clustering.kmeans;

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.clustering.ClusterFailureException;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import static jsat.clustering.SeedSelectionMethods.selectIntialPoints;
import jsat.linear.ConstantVector;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.*;
import jsat.utils.*;
import jsat.utils.concurrent.AtomicDoubleArray;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * An efficient implementation of the K-Means algorithm. This implementation uses
 * the triangle inequality to accelerate computation while maintaining the exact
 * same solution. This requires that the {@link DistanceMetric} used support 
 * {@link DistanceMetric#isSubadditive() }. 
 * 
* Implementation based on the paper: Using the Triangle Inequality to Accelerate k-Means, by Charles Elkan * * @author Edward Raff */ public class ElkanKMeans extends KMeans { private static final long serialVersionUID = -1629432283103273051L; private DenseSparseMetric dmds; private boolean useDenseSparse = false; /** * Creates a new KMeans instance. * @param dm the distance metric to use, must support {@link DistanceMetric#isSubadditive() }. * @param rand the random number generator to use during seed selection * @param seedSelection the method of seed selection to use */ public ElkanKMeans(DistanceMetric dm, Random rand, SeedSelection seedSelection) { super(dm, seedSelection, rand); if(!dm.isSubadditive()) throw new ClusterFailureException("KMeans implementation requires the triangle inequality"); } /** * Creates a new KMeans instance * @param dm the distance metric to use, must support {@link DistanceMetric#isSubadditive() }. * @param rand the random number generator to use during seed selection */ public ElkanKMeans(DistanceMetric dm, Random rand) { this(dm, rand, DEFAULT_SEED_SELECTION); } /** * Creates a new KMeans instance * @param dm the distance metric to use, must support {@link DistanceMetric#isSubadditive() }. */ public ElkanKMeans(DistanceMetric dm) { this(dm, RandomUtil.getRandom()); } /** * Creates a new KMeans instance. The {@link EuclideanDistance} will be used by default. */ public ElkanKMeans() { this(new EuclideanDistance()); } public ElkanKMeans(ElkanKMeans toCopy) { super(toCopy); if(toCopy.dmds != null) this.dmds = (DenseSparseMetric) toCopy.dmds.clone(); this.useDenseSparse = toCopy.useDenseSparse; } /** * Sets whether or not to use {@link DenseSparseMetric } when computing. * This may or may not provide a speed increase. * @param useDenseSparse whether or not to compute the distance from dense * mean vectors to sparse ones using acceleration */ public void setUseDenseSparse(boolean useDenseSparse) { this.useDenseSparse = useDenseSparse; } /** * Returns if Dense Sparse acceleration will be used if available * @return if Dense Sparse acceleration will be used if available */ public boolean isUseDenseSparse() { return useDenseSparse; } /* * IMPLEMENTATION NOTE: Means are updates as a set of sums via deltas. Deltas are * computed locally withing a thread local object. Then to avoid dropping updates, * every thread that was working must apply its deltas itself, as other threads * can not access another's thread locals. */ @Override protected double cluster(final DataSet dataSet, List accelCache, final int k, final List means, final int[] assignment, boolean exactTotal, boolean parallel, boolean returnError, Vec dataPointWeights) { try { /** * N data points */ final int N = dataSet.getSampleSize(); final int D = dataSet.getNumNumericalVars(); if(N < k)//Not enough points throw new ClusterFailureException("Fewer data points then desired clusters, decrease cluster size"); /** * Weights for each data point */ final Vec W; if(dataPointWeights == null) W = dataSet.getDataWeights(); else W = dataPointWeights; TrainableDistanceMetric.trainIfNeeded(dm, dataSet); final List X = dataSet.getDataVectors(); //Distance computation acceleration final List distAccelCache; final List> meanQIs = new ArrayList<>(k); //done a wonky way b/c we want this as a final object for convinence, otherwise we may be stuck with null accel when we dont need to be if(accelCache == null) distAccelCache = dm.getAccelerationCache(X, parallel); else distAccelCache = accelCache; if(means.size() != k) { means.clear(); means.addAll(selectIntialPoints(dataSet, k, dm, distAccelCache, rand, seedSelection, parallel)); } //Make our means dense for(int i = 0; i < means.size(); i++) if(means.get(i).isSparse()) means.set(i, new DenseVector(means.get(i))); final double[][] lowerBound = new double[N][k]; final double[] upperBound = new double[N]; /** * Distances between centroid i and all other centroids */ final double[][] centroidSelfDistances = new double[k][k]; final double[] sC = new double[k]; calculateCentroidDistances(k, centroidSelfDistances, means, sC, null, parallel); final AtomicDoubleArray meanCount = new AtomicDoubleArray(k); Vec[] oldMeans = new Vec[k];//The means fromt he current step are needed when computing the new means final Vec[] meanSums = new Vec[k]; for (int i = 0; i < k; i++) { oldMeans[i] = means.get(i).clone();//This way the new vectors are of the same implementation if(dm.supportsAcceleration()) meanQIs.add(dm.getQueryInfo(means.get(i))); else meanQIs.add(Collections.EMPTY_LIST);//Avoid null pointers meanSums[i] = new DenseVector(D); } if(dm instanceof DenseSparseMetric && useDenseSparse) dmds = (DenseSparseMetric) dm; final double[] meanSummaryConsts = dmds != null ? new double[means.size()] : null; int atLeast = 2;//Used to performan an extra round (first round does not assign) final AtomicBoolean changeOccurred = new AtomicBoolean(true); final boolean[] r = new boolean[N];//Default value of a boolean is false, which is what we want final ThreadLocal localDeltas = new ThreadLocal() { @Override protected Vec[] initialValue() { Vec[] toRet = new Vec[k]; for(int i = 0; i < toRet.length; i++) toRet[i] = new DenseVector(D); return toRet; } }; initialClusterSetUp(k, N, X, means, lowerBound, upperBound, centroidSelfDistances, assignment, meanCount, meanSums, distAccelCache, meanQIs, localDeltas, parallel, W); int iterLimit = MaxIterLimit; while ((changeOccurred.get() || atLeast > 0) && iterLimit-- >= 0) { atLeast--; changeOccurred.set(false); //Step 1 if(iterLimit < MaxIterLimit-1)//we already did this on before iteration calculateCentroidDistances(k, centroidSelfDistances, means, sC, meanSummaryConsts, parallel); final CountDownLatch latch = new CountDownLatch(SystemInfo.LogicalCores); //Step 2 / 3 ParallelUtils.run(parallel, N, (q)-> { //Step 2, skip those that u(v) < s(c(v)) if (upperBound[q] <= sC[assignment[q]]) return; final Vec v = X.get(q); for (int c = 0; c < k; c++) if (c != assignment[q] && upperBound[q] > lowerBound[q][c] && upperBound[q] > centroidSelfDistances[assignment[q]][c] * 0.5) { step3aBoundsUpdate(X, r, q, v, means, assignment, upperBound, lowerBound, meanSummaryConsts, distAccelCache, meanQIs); step3bUpdate(X, upperBound, q, lowerBound, c, centroidSelfDistances, assignment, v, means, localDeltas, meanCount, changeOccurred, meanSummaryConsts, distAccelCache, meanQIs, W); } step4UpdateCentroids(meanSums, localDeltas); }); step5_6_distanceMovedBoundsUpdate(k, oldMeans, means, meanSums, meanCount, N, lowerBound, upperBound, assignment, r, meanQIs, parallel); } double totalDistance = 0.0; if(returnError) { if(saveCentroidDistance) nearestCentroidDist = new double[N]; else nearestCentroidDist = null; if (exactTotal == true) for (int i = 0; i < N; i++) { double dist = dm.dist(i, means.get(assignment[i]), meanQIs.get(assignment[i]), X, distAccelCache); totalDistance += Math.pow(dist, 2); if(saveCentroidDistance) nearestCentroidDist[i] = dist; } else for (int i = 0; i < N; i++) { totalDistance += Math.pow(upperBound[i], 2); if(saveCentroidDistance) nearestCentroidDist[i] = upperBound[i]; } } return totalDistance; } catch (Exception ex) { Logger.getLogger(ElkanKMeans.class.getName()).log(Level.SEVERE, null, ex); } return Double.MAX_VALUE; } private void initialClusterSetUp(final int k, final int N, final List dataSet, final List means, final double[][] lowerBound, final double[] upperBound, final double[][] centroidSelfDistances, final int[] assignment, final AtomicDoubleArray meanCount, final Vec[] meanSums, final List distAccelCache, final List> meanQIs, final ThreadLocal localDeltas, boolean parallel, final Vec W) { ParallelUtils.run(parallel, N, (from, to)-> { Vec[] deltas = localDeltas.get(); final boolean[] skip = new boolean[k]; for (int q = from; q < to; q++) { Vec v = dataSet.get(q); double minDistance = Double.MAX_VALUE; int index = -1; //Default value is false, we cant skip anything yet Arrays.fill(skip, false); for (int i = 0; i < k; i++) { if (skip[i]) continue; double d = dm.dist(q, means.get(i), meanQIs.get(i), dataSet, distAccelCache); lowerBound[q][i] = d; if (d < minDistance) { minDistance = upperBound[q] = d; index = i; //We now have some information, use lemma 1 to see if we can skip anything for (int z = i + 1; z < k; z++) if (centroidSelfDistances[i][z] >= 2 * d) skip[z] = true; } } assignment[q] = index; final double weight = W.get(q); meanCount.addAndGet(index, weight); deltas[index].mutableAdd(weight, v); } for (int i = 0; i < deltas.length; i++) { synchronized (meanSums[i]) { meanSums[i].mutableAdd(deltas[i]); } deltas[i].zeroOut(); } }); } private void step4UpdateCentroids(Vec[] meanSums, ThreadLocal localDeltas) { Vec[] deltas = localDeltas.get(); for(int i = 0; i < deltas.length; i++) { if(deltas[i].nnz() == 0) continue; synchronized(meanSums[i]) { meanSums[i].mutableAdd(deltas[i]); } deltas[i].zeroOut(); } } private void step5_6_distanceMovedBoundsUpdate(final int k, final Vec[] oldMeans, final List means, final Vec[] meanSums, final AtomicDoubleArray meanCount, final int N, final double[][] lowerBound, final double[] upperBound, final int[] assignment, final boolean[] r, final List> meanQIs, boolean parallel) { final double[] distancesMoved = new double[k]; ParallelUtils.run(parallel, k, (i)-> { //Re compute centroids means.get(i).copyTo(oldMeans[i]); //normalize meanSums[i].copyTo(means.get(i)); double count = meanCount.get(i); if (count <= 1e-14) means.get(i).zeroOut(); else means.get(i).mutableDivide(meanCount.get(i)); distancesMoved[i] = dm.dist(oldMeans[i], means.get(i)); if(dm.supportsAcceleration()) meanQIs.set(i, dm.getQueryInfo(means.get(i))); //Step 5 for (int q = 0; q < N; q++) lowerBound[q][i] = Math.max(lowerBound[q][i] - distancesMoved[i], 0); }); //Step 6 ParallelUtils.run(parallel, N, (start, end) -> { for(int q = start; q < end; q++) { upperBound[q] += distancesMoved[assignment[q]]; r[q] = true; } }); } private void step3aBoundsUpdate(List X, boolean[] r, int q, Vec v, final List means, final int[] assignment, double[] upperBound, double[][] lowerBound, double[] meanSummaryConsts, List distAccelCache, List> meanQIs) { //3(a) if (r[q]) { r[q] = false; double d; int meanIndx = assignment[q]; if(dmds == null) d = dm.dist(q, means.get(meanIndx), meanQIs.get(meanIndx), X, distAccelCache); else d = dmds.dist(meanSummaryConsts[meanIndx], means.get(meanIndx), v); lowerBound[q][meanIndx] = d;///Not sure if this is supposed to be here upperBound[q] = d; } } private void step3bUpdate(List X, double[] upperBound, final int q, double[][] lowerBound, final int c, double[][] centroidSelfDistances, final int[] assignment, Vec v, final List means, final ThreadLocal localDeltas, AtomicDoubleArray meanCount, final AtomicBoolean changeOccurred, double[] meanSummaryConsts, List distAccelCache, List> meanQIs, final Vec W) { //3(b) if (upperBound[q] > lowerBound[q][c] || upperBound[q] > centroidSelfDistances[assignment[q]][c] / 2) { double d; if(dmds == null) d = dm.dist(q, means.get(c), meanQIs.get(c), X, distAccelCache); else d = dmds.dist(meanSummaryConsts[c], means.get(c), v); lowerBound[q][c] = d; if (d < upperBound[q]) { Vec[] deltas = localDeltas.get(); final double weight = W.get(q); deltas[assignment[q]].mutableSubtract(weight, v); meanCount.addAndGet(assignment[q], -weight); deltas[c].mutableAdd(weight, v); meanCount.addAndGet(c, weight); assignment[q] = c; upperBound[q] = d; changeOccurred.set(true); } } } private void calculateCentroidDistances(final int k, final double[][] centroidSelfDistances, final List means, final double[] sC, final double[] meanSummaryConsts, boolean parallel) { final List meanAccelCache = dm.supportsAcceleration() ? dm.getAccelerationCache(means) : null; //TODO can improve parallel performance for when k ~<= # cores ParallelUtils.run(parallel, k, (i)-> { for (int z = i + 1; z < k; z++) centroidSelfDistances[z][i] = centroidSelfDistances[i][z] = dm.dist(i, z, means, meanAccelCache);; if (meanSummaryConsts != null) meanSummaryConsts[i] = dmds.getVectorConstant(means.get(i)); }); //final step quickly figure out sCmin for (int i = 0; i < k; i++) { double sCmin = Double.MAX_VALUE; for (int z = 0; z < k; z++) if (z != i) sCmin = Math.min(sCmin, centroidSelfDistances[i][z]); sC[i] = sCmin / 2.0; } } @Override public ElkanKMeans clone() { return new ElkanKMeans(this); } }

Ads help maintain this website.