jsat.clustering.kmeans

Class ElkanKMeans

java.lang.Object

jsat.clustering.ClustererBase

jsat.clustering.KClustererBase

jsat.clustering.kmeans.KMeans

jsat.clustering.kmeans.ElkanKMeans

All Implemented Interfaces:

Serializable, Clusterer, KClusterer, Parameterized

public class ElkanKMeans
extends KMeans

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 DistanceMetric used support DistanceMetric.isSubadditive().
Implementation based on the paper: Using the Triangle Inequality to Accelerate k-Means, by Charles Elkan

Author:

Edward Raff

See Also:

Serialized Form

Field Summary

Fields inherited from class jsat.clustering.kmeans.KMeans

DEFAULT_SEED_SELECTION, dm, MaxIterLimit, means, nearestCentroidDist, rand, saveCentroidDistance, seedSelection, storeMeans

Constructor Summary

Constructors

Constructor and Description
ElkanKMeans() Creates a new KMeans instance.
ElkanKMeans(DistanceMetric dm) Creates a new KMeans instance
ElkanKMeans(DistanceMetric dm, Random rand) Creates a new KMeans instance
ElkanKMeans(DistanceMetric dm, Random rand, SeedSelectionMethods.SeedSelection seedSelection) Creates a new KMeans instance.
ElkanKMeans(ElkanKMeans toCopy)

Method Summary

Modifier and Type	Method and Description
ElkanKMeans	clone()
protected double	cluster(DataSet dataSet, List<Double> accelCache, int k, List<Vec> means, int[] assignment, boolean exactTotal, ExecutorService threadpool, boolean returnError, Vec dataPointWeights) This is a helper method where the actual cluster is performed.
boolean	isUseDenseSparse() Returns if Dense Sparse acceleration will be used if available
void	setUseDenseSparse(boolean useDenseSparse) Sets whether or not to use DenseSparseMetric when computing.

Methods inherited from class jsat.clustering.kmeans.KMeans

cluster, cluster, cluster, cluster, cluster, cluster, getDistanceMetric, getIterationLimit, getListOfLists, getMeans, getParameter, getParameters, getSeedSelection, setIterationLimit, setSeedSelection, setStoreMeans, supportsWeightedData

Methods inherited from class jsat.clustering.KClustererBase

cluster, cluster, cluster, cluster

Methods inherited from class jsat.clustering.ClustererBase

cluster, cluster, createClusterListFromAssignmentArray, getDatapointsFromCluster

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jsat.clustering.Clusterer

cluster, cluster

Constructor Detail

ElkanKMeans

public ElkanKMeans(DistanceMetric dm,
                   Random rand,
                   SeedSelectionMethods.SeedSelection seedSelection)

Creates a new KMeans instance.

Parameters:

dm - the distance metric to use, must support DistanceMetric.isSubadditive().

rand - the random number generator to use during seed selection

seedSelection - the method of seed selection to use

ElkanKMeans

public ElkanKMeans(DistanceMetric dm,
                   Random rand)

Creates a new KMeans instance

Parameters:

dm - the distance metric to use, must support DistanceMetric.isSubadditive().

rand - the random number generator to use during seed selection

ElkanKMeans

public ElkanKMeans(DistanceMetric dm)

Creates a new KMeans instance

Parameters:

dm - the distance metric to use, must support DistanceMetric.isSubadditive().

ElkanKMeans

public ElkanKMeans()

Creates a new KMeans instance. The EuclideanDistance will be used by default.

ElkanKMeans

public ElkanKMeans(ElkanKMeans toCopy)

Method Detail

setUseDenseSparse

public void setUseDenseSparse(boolean useDenseSparse)

Sets whether or not to use DenseSparseMetric when computing. This may or may not provide a speed increase.

Parameters:

useDenseSparse - whether or not to compute the distance from dense mean vectors to sparse ones using acceleration

isUseDenseSparse

public boolean isUseDenseSparse()

Returns if Dense Sparse acceleration will be used if available

Returns:

if Dense Sparse acceleration will be used if available

cluster

protected double cluster(DataSet dataSet,
                         List<Double> accelCache,
                         int k,
                         List<Vec> means,
                         int[] assignment,
                         boolean exactTotal,
                         ExecutorService threadpool,
                         boolean returnError,
                         Vec dataPointWeights)

Description copied from class: KMeans

This is a helper method where the actual cluster is performed. This is because there are multiple strategies for modifying kmeans, but all of them require this step.
The distance metric used is trained if needed

Specified by:

cluster in class KMeans

Parameters:

dataSet - The set of data points to perform clustering on

accelCache - acceleration cache to use, or null. If null, the kmeans code will attempt to create one

k - the number of clusters

means - the initial points to use as the means. Its length is the number of means that will be searched for. These means will be altered, and should contain deep copies of the points they were drawn from. May be empty, in which case the list will be filled with some selected means

assignment - an empty temp space to store the clustering classifications. Should be the same length as the number of data points

exactTotal - determines how the objective function (return value) will be computed. If true, extra work will be done to compute the exact distance from each data point to its cluster. If false, an upper bound approximation will be used. This also impacts the value stored in KMeans.nearestCentroidDist

threadpool - the source of threads for parallel computation. If null, single threaded execution will occur

returnError - true is the sum of squared distances should be returned. false means any value can be returned. KMeans.saveCentroidDistance only applies if this is true

dataPointWeights - the weight value to use for each data point. If null, assume each point has equal weight.

Returns:

the double

clone

public ElkanKMeans clone()

Specified by:

clone in interface Clusterer

Specified by:

clone in interface KClusterer

Specified by:

clone in class KMeans