package jsat.clustering.kmeans;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.LongAdder;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.clustering.SeedSelectionMethods;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import static jsat.clustering.SeedSelectionMethods.selectIntialPoints;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.utils.FakeExecutor;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDoubleArray;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* An implementation of Lloyd's K-Means clustering algorithm using the
* naive algorithm. This implementation exists mostly for comparison as
* a base line and educational reasons. For efficient exact k-Means,
* use {@link ElkanKMeans}
*
* This implementation is parallel, but does not support any of the
* clustering methods that do not specify the number of clusters.
*
* @author Edward Raff
*/
public class NaiveKMeans extends KMeans
{
private static final long serialVersionUID = 6164910874898843069L;
/**
* Creates a new naive k-Means cluster using
* {@link SeedSelection#KPP k-means++} for the seed selection and the
* {@link EuclideanDistance}
*/
public NaiveKMeans()
{
this(new EuclideanDistance());
}
/**
* Creates a new naive k-Means cluster using
* {@link SeedSelection#KPP k-means++} for the seed selection.
* @param dm the distance function to use
*/
public NaiveKMeans(DistanceMetric dm)
{
this(dm, SeedSelectionMethods.SeedSelection.KPP);
}
/**
* Creates a new naive k-Means cluster
* @param dm the distance function to use
* @param seedSelection the method of selecting the initial seeds
*/
public NaiveKMeans(DistanceMetric dm, SeedSelection seedSelection)
{
this(dm, seedSelection, RandomUtil.getRandom());
}
/**
* Creates a new naive k-Means cluster
* @param dm the distance function to use
* @param seedSelection the method of selecting the initial seeds
* @param rand the source of randomness to use
*/
public NaiveKMeans(DistanceMetric dm, SeedSelection seedSelection, Random rand)
{
super(dm, seedSelection, rand);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public NaiveKMeans(NaiveKMeans toCopy)
{
super(toCopy);
}
@Override
protected double cluster(final DataSet dataSet, List accelCacheInit, final int k, final List means, final int[] assignment, final boolean exactTotal, boolean parallel, boolean returnError, Vec dataPointWeights)
{
TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel);
/**
* Weights for each data point
*/
final Vec W;
if (dataPointWeights == null)
W = dataSet.getDataWeights();
else
W = dataPointWeights;
final int blockSize = dataSet.getSampleSize() / SystemInfo.LogicalCores;
final List X = dataSet.getDataVectors();
//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
final List accelCache;
if (accelCacheInit == null)
accelCache = dm.getAccelerationCache(X, parallel);
else
accelCache = accelCacheInit;
if (means.size() != k)
{
means.clear();
means.addAll(selectIntialPoints(dataSet, k, dm, accelCache, rand, seedSelection, parallel));
}
final List> meanQIs = new ArrayList<>(k);
//Use dense mean objects
for(int i = 0; i < means.size(); i++)
{
if(dm.supportsAcceleration())
meanQIs.add(dm.getQueryInfo(means.get(i)));
else
meanQIs.add(Collections.EMPTY_LIST);
if(means.get(i).isSparse())
means.set(i, new DenseVector(means.get(i)));
}
final List meanSum = new ArrayList<>(means.size());
final AtomicDoubleArray meanCounts = new AtomicDoubleArray(means.size());
for(int i = 0; i < k; i++)
meanSum.add(new DenseVector(means.get(0).length()));
final LongAdder changes = new LongAdder();
//used to store local changes to the means and accumulated at the end
final ThreadLocal localMeanDeltas = new ThreadLocal()
{
@Override
protected Vec[] initialValue()
{
Vec[] deltas = new Vec[k];
for(int i = 0; i < k; i++)
deltas[i] = new DenseVector(means.get(0).length());
return deltas;
}
};
final int N = dataSet.getSampleSize();
Arrays.fill(assignment, -1);
do
{
changes.reset();
ParallelUtils.run(parallel, N, (start, end) ->
{
Vec[] deltas = localMeanDeltas.get();
double tmp;
for (int i = start; i < end; i++)
{
final Vec x = X.get(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), X, accelCache);
if (tmp < minDist)
{
minDist = tmp;
min = j;
}
}
if(assignment[i] == min)
continue;
final double w = W.get(i);
//add change
deltas[min].mutableAdd(w, x);
meanCounts.addAndGet(min, w);
//remove from prev owner
if(assignment[i] >= 0)
{
deltas[assignment[i]].mutableSubtract(w, x);
meanCounts.getAndAdd(assignment[i], -w);
}
assignment[i] = min;
changes.increment();
}
//accumulate deltas into globals
for(int i = 0; i < deltas.length; i++)
synchronized(meanSum.get(i))
{
meanSum.get(i).mutableAdd(deltas[i]);
deltas[i].zeroOut();
}
});
if(changes.longValue() == 0)
break;
for(int i = 0; i < k; i++)
{
meanSum.get(i).copyTo(means.get(i));
means.get(i).mutableDivide(meanCounts.get(i));
if(dm.supportsAcceleration())
meanQIs.set(i, dm.getQueryInfo(means.get(i)));
}
}
while(changes.longValue() > 0);
if (returnError)
{
if (saveCentroidDistance)
nearestCentroidDist = new double[X.size()];
else
nearestCentroidDist = null;
double totalDistance = ParallelUtils.run(parallel, N, (start, end) ->
{
double totalDistLocal = 0;
for(int i = start; i < end; i++)
{
double dist = dm.dist(i, means.get(assignment[i]), meanQIs.get(assignment[i]), X, accelCache);
totalDistLocal += Math.pow(dist, 2);
if(saveCentroidDistance)
nearestCentroidDist[i] = dist;
}
return totalDistLocal;
}, (t, u) -> t+u);
return totalDistance;
}
else
return 0;//who cares
}
@Override
public NaiveKMeans clone()
{
return new NaiveKMeans(this);
}
}
Ads help maintain this website.