package jsat.clustering;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.distributions.empirical.kernelfunc.GaussKF;
import jsat.distributions.empirical.kernelfunc.KernelFunction;
import jsat.distributions.multivariate.MetricKDE;
import jsat.distributions.multivariate.MultivariateKDE;
import jsat.distributions.multivariate.ProductKDE;
import jsat.exceptions.FailedToFitException;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import static jsat.utils.SystemInfo.LogicalCores;
import jsat.utils.concurrent.ParallelUtils;


/**
 * The MeanShift algorithms performs clustering on a data set by letting the 
 * data speak for itself and performing a mode search amongst the data set, 
 * returning a cluster for each discovered mode. 
*
* While not normally discussed in the context of Mean Shift, this * implementation has rudimentary outlier-removal, outliers will not be included * in the clustering.
*
* The mean shift requires a {@link MultivariateKDE} to run. Contrary to use in * density estimation, where the {@link KernelFunction} used has only a minor * impact on the results, it is highly recommended you use the {@link GaussKF} * for the MeanShift method. This is because of the large support and better * behaved derivative, which adds in the avoidance of oscillating convergence. *

* Implementation Note: This implementation does not snap the values to a grid. * This causes the prior noted oscillation in convergence. * * @author Edward Raff */ public class MeanShift implements Clusterer { private static final long serialVersionUID = 4061491342362690455L; /** * The default number of {@link #getMaxIterations() } is * {@value #DefaultMaxIterations} */ public static final int DefaultMaxIterations = 1000; /** * The default value of {@link #getScaleBandwidthFactor() } is {@value #DefaultScaleBandwidthFactor} */ public static final double DefaultScaleBandwidthFactor = 1.0; private MultivariateKDE mkde; private int maxIterations = DefaultMaxIterations; private double scaleBandwidthFactor = DefaultScaleBandwidthFactor; /** * Creates a new MeanShift clustering object using a {@link MetricKDE}, * the {@link GaussKF}, and the {@link EuclideanDistance}. */ public MeanShift() { this(new EuclideanDistance()); } /** * Creates a new MeanShift clustering object using a {@link MetricKDE} and * the {@link GaussKF}. * @param dm the distance metric to use */ public MeanShift(DistanceMetric dm) { this(new MetricKDE(GaussKF.getInstance(), dm)); } /** * Creates a new MeanShift clustering object. *
* NOTE: {@link ProductKDE} does not currently support the functions needed to work with MeanShift. * @param mkde the KDE to use in the clustering process. */ public MeanShift(MultivariateKDE mkde) { this.mkde = mkde; } /** * Copy constructor * @param toCopy the object to copy */ public MeanShift(MeanShift toCopy) { this.mkde = toCopy.mkde.clone(); this.maxIterations = toCopy.maxIterations; this.scaleBandwidthFactor = toCopy.scaleBandwidthFactor; } /** * Sets the maximum number of iterations the algorithm will go through, * terminating early if convergence has not occurred. * @param maxIterations the maximum number of iterations * @throws ArithmeticException if a value less than 1 is given */ public void setMaxIterations(int maxIterations) { if(maxIterations <= 0) throw new ArithmeticException("Invalid iteration count, " + maxIterations); this.maxIterations = maxIterations; } /** * Returns the maximum number of iterations the algorithm will go through, * terminating early if convergence has not occurred. * @return the maximum number of iterations */ public int getMaxIterations() { return maxIterations; } /** * Sets the value by which the bandwidth of the {@link MultivariateKDE} will * be scaled by. * @param scaleBandwidthFactor the value to scale bandwidth by * @throws ArithmeticException if the value given is {@link Double#NaN NaN } * or {@link Double#POSITIVE_INFINITY infinity} */ public void setScaleBandwidthFactor(double scaleBandwidthFactor) { if(Double.isNaN(scaleBandwidthFactor) || Double.isInfinite(scaleBandwidthFactor)) throw new ArithmeticException("Invalid scale factor, " + scaleBandwidthFactor); this.scaleBandwidthFactor = scaleBandwidthFactor; } /** * Returns the value by which the bandwidth of the {@link MultivariateKDE} will * be scaled by. * @return the value to scale bandwidth by */ public double getScaleBandwidthFactor() { return scaleBandwidthFactor; } @Override public int[] cluster(DataSet dataSet, boolean parallel, int[] designations) { try { if(designations == null || designations.length < dataSet.getSampleSize()) designations = new int[dataSet.getSampleSize()]; boolean[] converged = new boolean[dataSet.getSampleSize()]; Arrays.fill(converged, false); final KernelFunction k = mkde.getKernelFunction(); mkde.setUsingData(dataSet, parallel); mkde.scaleBandwidth(scaleBandwidthFactor); Vec[] xit = new Vec[converged.length]; for(int i = 0; i < xit.length; i++) xit[i] = dataSet.getDataPoint(i).getNumericalValues().clone(); mainLoop(converged, xit, designations, k, parallel); assignmentStep(converged, xit, designations); return designations; } catch (InterruptedException ex) { Logger.getLogger(MeanShift.class.getName()).log(Level.SEVERE, null, ex); throw new FailedToFitException(ex); } catch (BrokenBarrierException ex) { Logger.getLogger(MeanShift.class.getName()).log(Level.SEVERE, null, ex); throw new FailedToFitException(ex); } } private void assignmentStep(boolean[] converged, Vec[] xit, int[] designations) { //We now repurpose the 'converged' array to indicate if the point has not yet been asigned to a cluster //Loop through and asign clusters int curClusterID = 0; boolean progress = true; while(progress) { progress = false; int basePos = 0;//This will be the mode of our cluster while(basePos < converged.length && !converged[basePos]) basePos++; for(int i = basePos; i < converged.length; i++) { if(!converged[i] || designations[i] == -1) continue;//Already assigned progress = true; if(Math.abs(xit[basePos].pNormDist(2, xit[i])) < 1e-3) { converged[i] = false; designations[i] = curClusterID; } } curClusterID++; } } private void mainLoop(final boolean[] converged, final Vec[] xit, final int[] designations, final KernelFunction k, boolean parallel) throws InterruptedException, BrokenBarrierException { AtomicBoolean progress = new AtomicBoolean(true); int count = 0; /* * +1 b/c we have to wait for the worker threads, but we also want this * calling thread to wait with them. Hence, +1 */ CyclicBarrier barrier = new CyclicBarrier(LogicalCores+1); final ThreadLocal localScratch = ThreadLocal.withInitial(()->new DenseVector(xit[0].length())); while(progress.get() && count++ < maxIterations) { progress.set(false); ParallelUtils.run(parallel, converged.length, (i)-> { if(converged[i]) return; progress.lazySet(true); convergenceStep(xit, i, converged, designations, localScratch.get(), k); }); } //Fill b/c we may have bailed out due to maxIterations Arrays.fill(converged, true); } /** * Computes the meanShift of the point at the given index, and then updates the vector array to indicate the movement towards the mode for the data point. * @param xit the array of the current data point's positions * @param i the index of the data point being considered * @param converged the array used to indicate the convergence to a mode * @param designations the array to store value designations in * @param scratch the vector to compute work with * @param k the kernel function to use */ private void convergenceStep(final Vec[] xit, int i, final boolean[] converged, final int[] designations, final Vec scratch, final KernelFunction k) { double denom = 0.0; Vec xCur = xit[i]; List, Double>> contrib = mkde.getNearbyRaw(xCur); if(contrib.size() == 1) { //If a point has no neighbors, it can not shift, and is its own mdoe - so we mark it noise converged[i] = true; designations[i] = -1; } else { scratch.zeroOut(); for(VecPaired, Double> v : contrib) { double g = - k.kPrime(v.getPair()); denom += g; scratch.mutableAdd(g, v); } scratch.mutableDivide(denom); if( Math.abs(scratch.pNormDist(2, xCur)) < 1e-5) converged[i] = true; scratch.copyTo(xCur); } } @Override public MeanShift clone() { return new MeanShift(this); } }

Ads help maintain this website.