package jsat.clustering.kmeans;

import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.clustering.KClustererBase;
import jsat.clustering.SeedSelectionMethods;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.*;
import jsat.utils.*;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * Implements the mini-batch algorithms for k-means. This is a stochastic algorithm, 
 * so it does not find the global solution. This implementation is parallel, but 
 * only the methods that specify the exact number of clusters are supported. 
*
* See: Sculley, D. (2010). Web-scale k-means clustering. Proceedings of the * 19th international conference on World wide web (pp. 1177–1178). * New York, New York, USA: ACM Press. doi:10.1145/1772690.1772862 * * @author Edward Raff */ public class MiniBatchKMeans extends KClustererBase { private static final long serialVersionUID = 412553399508594014L; private int batchSize; private int iterations; private DistanceMetric dm; private SeedSelectionMethods.SeedSelection seedSelection; private boolean storeMeans = true; private List means; /** * Creates a new Mini-Batch k-Means object that uses * {@link SeedSelection#KPP k-means++} for seed selection * and uses the {@link EuclideanDistance}. * * @param batchSize the mini-batch size * @param iterations the number of mini batches to perform */ public MiniBatchKMeans(int batchSize, int iterations) { this(new EuclideanDistance(), batchSize, iterations); } /** * Creates a new Mini-Batch k-Means object that uses * {@link SeedSelection#KPP k-means++} for seed selection. * * @param dm the distance metric to use * @param batchSize the mini-batch size * @param iterations the number of mini batches to perform */ public MiniBatchKMeans(DistanceMetric dm, int batchSize, int iterations) { this(dm, batchSize, iterations, SeedSelectionMethods.SeedSelection.KPP); } /** * Creates a new Mini-Batch k-Means object * @param dm the distance metric to use * @param batchSize the mini-batch size * @param iterations the number of mini batches to perform * @param seedSelection the seed selection algorithm to initiate clustering */ public MiniBatchKMeans(DistanceMetric dm, int batchSize, int iterations, SeedSelection seedSelection) { setBatchSize(batchSize); setIterations(iterations); setDistanceMetric(dm); setSeedSelection(seedSelection); } /** * Copy constructor * @param toCopy the object to copy */ public MiniBatchKMeans(MiniBatchKMeans toCopy) { this.batchSize = toCopy.batchSize; this.iterations = toCopy.iterations; this.dm = toCopy.dm.clone(); this.seedSelection = toCopy.seedSelection; this.storeMeans = toCopy.storeMeans; if(toCopy.means != null) { this.means = new ArrayList<>(); for(Vec v : toCopy.means) this.means.add(v.clone()); } } /** * If set to {@code true} the computed means will be stored after clustering * is completed, and can then be retrieved using {@link #getMeans() }. * @param storeMeans {@code true} if the means should be stored for later, * {@code false} to discard them once clustering is complete. */ public void setStoreMeans(boolean storeMeans) { this.storeMeans = storeMeans; } /** * Returns the raw list of means that were used for each class. * @return the list of means for each class */ public List getMeans() { return means; } /** * Sets the distance metric used for determining the nearest cluster center * @param dm the distance metric to use */ public void setDistanceMetric(DistanceMetric dm) { this.dm = dm; } /** * Returns the distance metric used for determining the nearest cluster center * @return the distance metric in use */ public DistanceMetric getDistanceMetric() { return dm; } /** * Sets the batch size to use at each iteration. Increasing the * batch size can improve the resulting clustering, but increases * computational cost at each iteration.
* If the batch size is set equal to or larger than data set size, * it reduces to the {@link NaiveKMeans naive k-means} algorithm. * @param batchSize the number of points to use at each iteration */ public void setBatchSize(int batchSize) { if(batchSize < 1) throw new ArithmeticException("Batch size must be a positive value, not " + batchSize); this.batchSize = batchSize; } /** * Returns the batch size used at each iteration * @return the batch size in use */ public int getBatchSize() { return batchSize; } /** * Sets the number of mini-batch iterations to perform * @param iterations the number of algorithm iterations to perform */ public void setIterations(int iterations) { if(iterations < 1) throw new ArithmeticException("Iterations must be a positive value, not " + iterations); this.iterations = iterations; } /** * Returns the number of mini-batch iterations used * @return the number of algorithm iterations that will be used */ public int getIterations() { return iterations; } /** * Sets the method of selecting the initial data points to * seed the clustering algorithm. * @param seedSelection the seed selection algorithm to use */ public void setSeedSelection(SeedSelection seedSelection) { this.seedSelection = seedSelection; } /** * Returns the method of seed selection to use * @return the method of seed selection to use */ public SeedSelection getSeedSelection() { return seedSelection; } @Override public int[] cluster(DataSet dataSet, int[] designations) { throw new UnsupportedOperationException("Not supported yet."); } @Override public int[] cluster(DataSet dataSet, boolean parallel, int[] designations) { throw new UnsupportedOperationException("Not supported yet."); } @Override public int[] cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations) { if(designations == null) designations = new int[dataSet.getSampleSize()]; TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel); final List source = dataSet.getDataVectors(); final List distCache; distCache = dm.getAccelerationCache(source, parallel); means = SeedSelectionMethods.selectIntialPoints(dataSet, clusters, dm, distCache, RandomUtil.getRandom(), seedSelection, parallel); final List> meanQIs = new ArrayList<>(means.size()); for (int i = 0; i < means.size(); i++) if (dm.supportsAcceleration()) meanQIs.add(dm.getQueryInfo(means.get(i))); else meanQIs.add(Collections.EMPTY_LIST); final int[] v = new int[means.size()]; final int usedBatchSize = Math.min(batchSize, dataSet.getSampleSize()); /** * Store the indices of the sampled points instead of sampling, that * way we can use the distance acceleration cache. */ final List M = new IntList(usedBatchSize); final List allIndx = new IntList(source.size()); ListUtils.addRange(allIndx, 0, source.size(), 1); final int[] nearestCenter = new int[usedBatchSize]; for(int iter = 0; iter < iterations; iter++) { M.clear(); ListUtils.randomSample(allIndx, M, usedBatchSize); //compute centers ParallelUtils.run(parallel, usedBatchSize, (start, end) -> { double tmp; for (int i = start; i < end; i++) { double minDist = Double.POSITIVE_INFINITY; int min = -1; for (int j = 0; j < means.size(); j++) { tmp = dm.dist(M.get(i), means.get(j), meanQIs.get(j), source, distCache); if (tmp < minDist) { minDist = tmp; min = j; } } nearestCenter[i] = min; } }); //Update centers for(int j = 0; j < M.size(); j++) { int c_i = nearestCenter[j]; double eta = 1.0/(++v[c_i]); Vec c = means.get(c_i); c.mutableMultiply(1-eta); c.mutableAdd(eta, source.get(M.get(j))); } //update mean caches if(dm.supportsAcceleration()) for(int i = 0; i < means.size(); i++) meanQIs.set(i, dm.getQueryInfo(means.get(i))); } //Stochastic travel complete, calculate all final int[] des = designations; double sumErr = ParallelUtils.run(parallel, dataSet.getSampleSize(), (start, end) -> { double dists = 0; double tmp; for (int i = start; i < end; i++) { double minDist = Double.POSITIVE_INFINITY; int min = -1; for (int j = 0; j < means.size(); j++) { tmp = dm.dist(i, means.get(j), meanQIs.get(j), source, distCache); if (tmp < minDist) { minDist = tmp; min = j; } } des[i] = min; dists += minDist*minDist; } return dists; }, (t, u) -> t+u); if(!storeMeans) means = null; return des; } @Override public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations) { throw new UnsupportedOperationException("Not supported yet."); } @Override public MiniBatchKMeans clone() { return new MiniBatchKMeans(this); } }

Ads help maintain this website.