org.ddogleg.clustering.kmeans

Class StandardKMeans_F64

java.lang.Object

org.ddogleg.clustering.kmeans.StandardKMeans_F64

All Implemented Interfaces:

ComputeClusters<double[]>

public class StandardKMeans_F64
extends java.lang.Object
implements ComputeClusters<double[]>

Standard implementation of k-means [1], summary is provided below:

1. The initial seeds for each cluster is selected by the provided InitializeKMeans_F64.
2. Each point is assigned to a cluster which minimizes the euclidean distance squared.
3. New cluster centers are computed from the average of all points assigned to it.

This will find a locally optimal solution which minimizes the sum of the distance-squared of each point to the cluster they are assigned to.

Converged if, , where D is the sum of point from cluster distance at iteration 'i', and tol is the convergence tolerance threshold.

[1] Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982)

Constructor Summary

Constructors

Constructor and Description
StandardKMeans_F64(int maxIterations, int maxConverge, double convergeTol, InitializeKMeans_F64 seedSelector) Configures k-means parameters

Method Summary

Modifier and Type	Method and Description
AssignCluster<double[]>	getAssignment() Returns a class which is used to assign a point to a cluster.
FastQueue<double[]>	getClusterMeans() Returns the mean of each cluster
double	getDistanceMeasure() Computes the potential function.
GrowQueue_I32	getPointLabels() Returns the labels assigned to each point
void	init(int pointDimension, long randomSeed) Must be called first to initializes internal data structures.
void	process(java.util.List<double[]> points, int numCluster) Computes a set of clusters which segment the points into numCluster sets.
void	setVerbose(boolean verbose) If set to true then information about status will be printed to standard out.

Methods inherited from class java.lang.Object

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

Constructor Detail

StandardKMeans_F64

public StandardKMeans_F64(int maxIterations,
                          int maxConverge,
                          double convergeTol,
                          InitializeKMeans_F64 seedSelector)

Configures k-means parameters

Parameters:

maxIterations - Maximum number of iterations

maxConverge - Maximum iterations before it converges. It is reseeded if it doesn't converge.

convergeTol - Clusters have converged if the change in score is <= to this amount.

seedSelector - Used to select initial seeds for the clusters

Method Detail

init

public void init(int pointDimension,
                 long randomSeed)

Description copied from interface: ComputeClusters

Must be called first to initializes internal data structures. Only needs to be called once.

Specified by:

init in interface ComputeClusters<double[]>

Parameters:

pointDimension - Number of degrees of freedom in each point.

randomSeed - Seed for any random number generators used internally.

process

public void process(java.util.List<double[]> points,
                    int numCluster)

Description copied from interface: ComputeClusters

Computes a set of clusters which segment the points into numCluster sets.

Specified by:

process in interface ComputeClusters<double[]>

Parameters:

points - Set of points which are to be clustered. Not modified.

numCluster - Number of clusters it will use to split the points.

getPointLabels

public GrowQueue_I32 getPointLabels()

Returns the labels assigned to each point

getClusterMeans

public FastQueue<double[]> getClusterMeans()

Returns the mean of each cluster

getAssignment

public AssignCluster<double[]> getAssignment()

Description copied from interface: ComputeClusters

Returns a class which is used to assign a point to a cluster. Only invoked after ComputeClusters.process(java.util.List<D>, int) has been called.

WARNING: The returned data structure is recycled each time compute clusters is called. Create a copy if you wish to avoid having it modified.

Specified by:

getAssignment in interface ComputeClusters<double[]>

Returns:

Instance of AssignCluster.

getDistanceMeasure

public double getDistanceMeasure()

Computes the potential function. The sum of distance for each point from their cluster centers.\

Specified by:

getDistanceMeasure in interface ComputeClusters<double[]>

Returns:

sum of distance between each point and their respective clusters.

setVerbose

public void setVerbose(boolean verbose)

Description copied from interface: ComputeClusters

If set to true then information about status will be printed to standard out. By default verbose is off

Specified by:

setVerbose in interface ComputeClusters<double[]>

Parameters:

verbose - true for versbose mode. False for quite mode.