jsat.clustering.kmeans

Class XMeans

java.lang.Object

jsat.clustering.ClustererBase

jsat.clustering.KClustererBase

jsat.clustering.kmeans.KMeans

jsat.clustering.kmeans.XMeans

All Implemented Interfaces:

java.io.Serializable, Clusterer, KClusterer, Parameterized

public class XMeans
extends KMeans

This class provides a method of performing KMeans clustering when the value of K is not known. It works by recursively splitting means up to some specified maximum. value.

When the value of K is specified, the implementation will simply call the regular KMeans object it was constructed with.

Note, that specifying a minimum value of K=1 has a tendency to not be split by the algorithm, returning the naive result of 1 cluster. It is better to use at least K=2 as the default minimum, which is what the implementation will start from when no range of K is given.

See: Pelleg, D.,&Moore, A. (2000). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In ICML (pp. 727–734). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. Retrieved from here

See Also:

Serialized Form

Field Summary

Fields inherited from class jsat.clustering.kmeans.KMeans

DEFAULT_SEED_SELECTION

Constructor Summary

Constructors

Constructor and Description
XMeans()
XMeans(KMeans kmeans)
XMeans(XMeans toCopy) Copy constructor

Method Summary

Modifier and Type	Method and Description
XMeans	clone()
int[]	cluster(DataSet dataSet, boolean parallel, int[] designations) Performs clustering on the given data set.
int[]	cluster(DataSet dataSet, int[] designations) Performs clustering on the given data set.
int[]	cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
int	getIterationLimit() Returns the maximum number of iterations of the ElkanKMeans algorithm that will be performed.
boolean	getIterativeRefine()
int	getMinClusterSize()
SeedSelectionMethods.SeedSelection	getSeedSelection()
boolean	isStopAfterFail()
void	setIterationLimit(int iterLimit) Sets the maximum number of iterations allowed
void	setIterativeRefine(boolean refineCenters) Sets whether or not the set of all cluster centers should be refined at every iteration.
void	setMinClusterSize(int minClusterSize) Sets the minimum size for splitting a cluster.
void	setSeedSelection(SeedSelectionMethods.SeedSelection seedSelection) Sets the method of seed selection to use for this algorithm.
void	setStopAfterFail(boolean stopAfterFail) Each new cluster will be tested for improvement according to the BIC metric.

Methods inherited from class jsat.clustering.kmeans.KMeans

cluster, getDistanceMetric, getMeans, setStoreMeans, supportsWeightedData

Methods inherited from class jsat.clustering.ClustererBase

createClusterListFromAssignmentArray, getDatapointsFromCluster

Methods inherited from class java.lang.Object

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

Methods inherited from interface jsat.parameters.Parameterized

getParameter, getParameters

Methods inherited from interface jsat.clustering.KClusterer

cluster, cluster, cluster, cluster, cluster, cluster

Methods inherited from interface jsat.clustering.Clusterer

cluster, cluster

Constructor Detail

XMeans

public XMeans()

XMeans

public XMeans(KMeans kmeans)

XMeans

public XMeans(XMeans toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

setStopAfterFail

public void setStopAfterFail(boolean stopAfterFail)

Each new cluster will be tested for improvement according to the BIC metric. If this is set to true then an optimization is done that once a center fails be improved by splitting, it will never be tested again. This is a safe assumption when setIterativeRefine(boolean) is set to false, but otherwise may not quite be true.

When trustH0 is true , X-Means will make at most O(k) runs of k-means for the final value of k chosen. When false (the default option), at most O(k²) runs of k-means will occur.

Parameters:

stopAfterFail - true if a centroid shouldn't be re-tested once it fails to split.

isStopAfterFail

public boolean isStopAfterFail()

Returns:

true if clusters that fail to split wont be re-tested. false if they will.

setMinClusterSize

public void setMinClusterSize(int minClusterSize)

Sets the minimum size for splitting a cluster.

Parameters:

minClusterSize - the minimum number of data points that must be present in a cluster to consider splitting it

getMinClusterSize

public int getMinClusterSize()

Returns:

the minimum number of data points that must be present in a cluster to consider splitting it

setIterativeRefine

public void setIterativeRefine(boolean refineCenters)

Sets whether or not the set of all cluster centers should be refined at every iteration. By default this is true and part of how the X-Means algorithm is described. Setting this to false can result in large speedups at the potential cost of quality.

Parameters:

refineCenters - true to refine the cluster centers at every step, false to skip this step of the algorithm.

getIterativeRefine

public boolean getIterativeRefine()

Returns:

true if the cluster centers are refined at every step, false if skipping this step of the algorithm.

cluster

public int[] cluster(DataSet dataSet,
                     int[] designations)

Description copied from interface: Clusterer

Performs clustering on the given data set. Parameters may be estimated by the method, or other heuristics performed.

Specified by:

cluster in interface Clusterer

Overrides:

cluster in class KMeans

Parameters:

dataSet - the data set to perform clustering on

designations - the array which will contain the designated values. The array will be altered and returned by the function. If null is given, a new array will be created and returned.

Returns:

an array indicating for each value indicating the cluster designation. This is the same array as designations, or a new one if the input array was null

cluster

public int[] cluster(DataSet dataSet,
                     boolean parallel,
                     int[] designations)

Description copied from interface: Clusterer

Performs clustering on the given data set. Parameters may be estimated by the method, or other heuristics performed.

Specified by:

cluster in interface Clusterer

Overrides:

cluster in class KMeans

Parameters:

dataSet - the data set to perform clustering on

parallel - true if multiple threads should be used to perform clustering. false if it should be done in a single threaded manner.

designations - the array which will contain the designated values. The array will be altered and returned by the function. If null is given, a new array will be created and returned.

Returns:

the int[]

cluster

public int[] cluster(DataSet dataSet,
                     int lowK,
                     int highK,
                     boolean parallel,
                     int[] designations)

Specified by:

cluster in interface KClusterer

Overrides:

cluster in class KMeans

getIterationLimit

public int getIterationLimit()

Description copied from class: KMeans

Returns the maximum number of iterations of the ElkanKMeans algorithm that will be performed.

Overrides:

getIterationLimit in class KMeans

Returns:

the maximum number of iterations of the ElkanKMeans algorithm that will be performed.

setIterationLimit

public void setIterationLimit(int iterLimit)

Description copied from class: KMeans

Sets the maximum number of iterations allowed

Overrides:

setIterationLimit in class KMeans

Parameters:

iterLimit - the maximum number of iterations of the ElkanKMeans algorithm

setSeedSelection

public void setSeedSelection(SeedSelectionMethods.SeedSelection seedSelection)

Description copied from class: KMeans

Sets the method of seed selection to use for this algorithm. SeedSelectionMethods.SeedSelection.KPP is recommended for this algorithm in particular.

Overrides:

setSeedSelection in class KMeans

Parameters:

seedSelection - the method of seed selection to use

getSeedSelection

public SeedSelectionMethods.SeedSelection getSeedSelection()

Overrides:

getSeedSelection in class KMeans

Returns:

the method of seed selection used

clone

public XMeans clone()

Specified by:

clone in interface Clusterer

Specified by:

clone in interface KClusterer

Specified by:

clone in class KMeans