gov.sandia.cognition.learning.algorithm.clustering

Class MiniBatchKMeansClusterer<DataType extends Vector>

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<java.util.Collection<? extends DataType>,java.util.Collection<ClusterType>>

gov.sandia.cognition.learning.algorithm.clustering.KMeansClusterer<Vector,MiniBatchCentroidCluster>

gov.sandia.cognition.learning.algorithm.clustering.MiniBatchKMeansClusterer<DataType>

Type Parameters:

DataType - The type of the data to cluster. This is typically defined by the divergence function used.

All Implemented Interfaces:

AnytimeAlgorithm<java.util.Collection<MiniBatchCentroidCluster>>, IterativeAlgorithm, MeasurablePerformanceAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<java.util.Collection<? extends Vector>,java.util.Collection<MiniBatchCentroidCluster>>, BatchLearner<java.util.Collection<? extends Vector>,java.util.Collection<MiniBatchCentroidCluster>>, BatchClusterer<Vector,MiniBatchCentroidCluster>, DivergenceFunctionContainer<MiniBatchCentroidCluster,Vector>, CloneableSerializable, Randomized, java.io.Serializable, java.lang.Cloneable

@PublicationReference(author="Jeff Piersol",
                      title="Parallel Mini-Batch k-means Clustering",
                      type=Conference,
                      year=2016,
                      publication="to appear",
                      url="to appear")
public class MiniBatchKMeansClusterer<DataType extends Vector>
extends KMeansClusterer<Vector,MiniBatchCentroidCluster>
implements Randomized

Approximates k-means clustering by working on random subsets of the data. This method is particularly useful for large data sets. For spherical k-means, use a Cosine distance semimetric for the divergence function, normalize all input data, and normalize each centroid after the algorithm converges.

Since:

4.0.0

Author:

Jeff Piersol

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MiniBatchKMeansClusterer.Builder<DataType extends Vector> Can be used to create custom MiniBatchKMeansClusterers without using the big constructor.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.List<java.lang.Integer>	dataIndices Indices of the data.
static int	DEFAULT_MAX_ITERATIONS The default maximum number of iterations is 100000.
protected java.util.Random	random The random number generator to use for initialization and subset selection.

Fields inherited from class gov.sandia.cognition.learning.algorithm.clustering.KMeansClusterer

assignments, clusterCounts, clusters, DEFAULT_NUM_REQUESTED_CLUSTERS, divergenceFunction, initializer, numRequestedClusters

Fields inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

data, keepGoing

Fields inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

maxIterations

Fields inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

DEFAULT_ITERATION, iteration

Constructor Summary

Constructors

Constructor and Description
MiniBatchKMeansClusterer(int numClusters) Create a clusterer with the default parameters.
MiniBatchKMeansClusterer(int numClusters, int maxIterations, FixedClusterInitializer<MiniBatchCentroidCluster,Vector> initializer, Semimetric<? super Vector> metric, ClusterCreator<MiniBatchCentroidCluster,Vector> creator, java.util.Random random) Creates a new MiniBatchKMeansClusterer.

Method Summary

Modifier and Type	Method and Description
protected int[]	assignDataToClusters(java.util.Collection<? extends Vector> data) Creates the cluster assignments given the current locations of clusters
protected void	cleanupAlgorithm() Called to clean up the learning algorithm's state after learning has finished.
MiniBatchKMeansClusterer<DataType>	clone() This makes public the clone method on the Object class and removes the exception that it throws.
java.util.List<? extends DataType>	getData() Gets the data to use for learning.
int	getMinibatchSize() Get the size of the mini-batches used.
java.util.Random	getRandom() Gets the random number generator used by this object.
double	getStoppingCriterion() Get the stopping criterion for this clusterer.
protected boolean	initializeAlgorithm() Called to initialize the learning algorithm's state based on the data that is stored in the data field.
protected void	saveFinalClustering() Saves the final clustering for each data point.
void	setData(java.util.Collection<? extends Vector> data) Set the data to be clustered.
void	setMinibatchSize(int minibatchSize) Set the size of the mini-batches.
void	setRandom(java.util.Random random) Sets the random number generator used by this object.
void	setStoppingCriterion(double stoppingCriterion) Set the stopping criterion for this clusterer.
protected boolean	step() Do a step of the clustering algorithm.

Methods inherited from class gov.sandia.cognition.learning.algorithm.clustering.KMeansClusterer

assignDataFromIndices, createClustersFromAssignments, getAssignments, getClosestClusterIndex, getCluster, getClusterCounts, getClusters, getCreator, getDivergenceFunction, getInitializer, getNumChanged, getNumClusters, getNumElements, getNumRequestedClusters, getPerformance, getResult, setAssignment, setClusters, setCreator, setDivergenceFunction, setInitializer, setNumChanged, setNumRequestedClusters

Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

getKeepGoing, learn, setKeepGoing, stop

Methods inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

getMaxIterations, isResultValid, setMaxIterations

Methods inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

addIterativeAlgorithmListener, fireAlgorithmEnded, fireAlgorithmStarted, fireStepEnded, fireStepStarted, getIteration, getListeners, removeIterativeAlgorithmListener, setIteration, setListeners

Methods inherited from class java.lang.Object

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

Methods inherited from interface gov.sandia.cognition.learning.algorithm.BatchLearner

learn

Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm

getMaxIterations, setMaxIterations

Methods inherited from interface gov.sandia.cognition.algorithm.IterativeAlgorithm

addIterativeAlgorithmListener, getIteration, removeIterativeAlgorithmListener

Methods inherited from interface gov.sandia.cognition.algorithm.StoppableAlgorithm

isResultValid

Field Detail

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS

The default maximum number of iterations is 100000.

See Also:

Constant Field Values

random

protected java.util.Random random

The random number generator to use for initialization and subset selection.

dataIndices

protected java.util.List<java.lang.Integer> dataIndices

Indices of the data. This should be a range of ints= [0, data.size)

Constructor Detail

MiniBatchKMeansClusterer

public MiniBatchKMeansClusterer(int numClusters)

Create a clusterer with the default parameters. This is a 'vanilla' mini-batch k-means, using Euclidean distance for the semimetric.

Parameters:

numClusters - the number of clusters to output

MiniBatchKMeansClusterer

public MiniBatchKMeansClusterer(int numClusters,
                                int maxIterations,
                                FixedClusterInitializer<MiniBatchCentroidCluster,Vector> initializer,
                                Semimetric<? super Vector> metric,
                                ClusterCreator<MiniBatchCentroidCluster,Vector> creator,
                                java.util.Random random)

Creates a new MiniBatchKMeansClusterer.

Parameters:

numClusters - the number of clusters to create

maxIterations - the number of iterations before stopping

initializer - sets the initial centroids

metric - the metric to use

creator - the cluster creator to use

random - the random number generator to use

Method Detail

clone

public MiniBatchKMeansClusterer<DataType> clone()

Description copied from class: AbstractCloneableSerializable

This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:

clone in interface CloneableSerializable

Overrides:

clone in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

Returns:

A clone of this object.

initializeAlgorithm

protected boolean initializeAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to initialize the learning algorithm's state based on the data that is stored in the data field. The return value indicates if the algorithm can be run or not based on the initialization.

Overrides:

initializeAlgorithm in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

Returns:

True if the learning algorithm can be run and false if it cannot.

step

protected boolean step()

Do a step of the clustering algorithm.

Overrides:

step in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

Returns:

true means keep going, false means stop clustering.

saveFinalClustering

protected void saveFinalClustering()

Saves the final clustering for each data point.

cleanupAlgorithm

protected void cleanupAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to clean up the learning algorithm's state after learning has finished.

Overrides:

cleanupAlgorithm in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

getRandom

public java.util.Random getRandom()

Description copied from interface: Randomized

Gets the random number generator used by this object.

Specified by:

getRandom in interface Randomized

Returns:

The random number generator used by this object.

setRandom

public final void setRandom(java.util.Random random)

Description copied from interface: Randomized

Sets the random number generator used by this object.

Specified by:

setRandom in interface Randomized

Parameters:

random - The random number generator for this object to use.

getData

public java.util.List<? extends DataType> getData()

Description copied from interface: AnytimeBatchLearner

Gets the data to use for learning. This is set when learning starts and then cleared out once learning is finished.

Specified by:

getData in interface AnytimeBatchLearner<java.util.Collection<? extends Vector>,java.util.Collection<MiniBatchCentroidCluster>>

Overrides:

getData in class AbstractAnytimeBatchLearner<java.util.Collection<? extends Vector>,java.util.Collection<MiniBatchCentroidCluster>>

Returns:

The data to use for learning.

setData

public void setData(java.util.Collection<? extends Vector> data)

Set the data to be clustered. If the data is not a RandomAccess List, it will be copied into one.

Overrides:

setData in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

Parameters:

data -

getStoppingCriterion

public double getStoppingCriterion()

Get the stopping criterion for this clusterer. See setStoppingCriterion(double) for details on the criterion.

Returns:

setStoppingCriterion

public void setStoppingCriterion(double stoppingCriterion)

Set the stopping criterion for this clusterer.

Parameters:

stoppingCriterion - if the fraction of samples that changed assignment is lower than this number, iteration stops. Set this to a negative value to disable early stopping

getMinibatchSize

public int getMinibatchSize()

Get the size of the mini-batches used.

Returns:

setMinibatchSize

public void setMinibatchSize(int minibatchSize)

Set the size of the mini-batches. If the size is ≤0, a heuristic will be used to compute the size before clustering.

Parameters:

minibatchSize -

assignDataToClusters

protected int[] assignDataToClusters(java.util.Collection<? extends Vector> data)

Description copied from class: KMeansClusterer

Creates the cluster assignments given the current locations of clusters

Overrides:

assignDataToClusters in class KMeansClusterer<Vector,MiniBatchCentroidCluster>

Parameters:

data - Data to assign

Returns:

Assignments of the data to each of the k-clusters