edu.ucla.sspace.clustering

Class FastStreamingKMeans

java.lang.Object

edu.ucla.sspace.clustering.FastStreamingKMeans

public class FastStreamingKMeans
extends Object

An implementation of Shindler's streaming K Means algorithm. It is based on a the following paper:

• Michael Shindler, Alex Wong, and Adam Meyerson. Fast and Accurate k-means for Large Datasets. In NIPS, 2011.. Available online here

A key feature of this algorithm is that only one pass is made through a data set and is intended for applications where the total number of data points is known, but the data set cannot be held in memory at any given time.

Author:

David Jurgens

Field Summary

Fields

Modifier and Type	Field and Description
static String	BETA_PROPERTY The property for specifying the beta value which determines increases to the facilities cost for creating a new facility, see page 6 in the paper for details.
static double	DEFAULT_BETA The default value of beta that appeared to work best according ot Michael Shindler
static SimilarityFunction	DEFAULT_SIMILARITY_FUNCTION The default similarity function is in the inverse of the square of the Euclidean distances, which preserves all the properties specified in the Shindler et al (2011) paper.
static String	KAPPA_PROPERTY The property for specifying kappa, the maximum number of facilities.
static String	SIMILARITY_FUNCTION_PROPERTY The property for specifying the similarity function with which to compare data points

Constructor Summary

Constructors

Constructor and Description
FastStreamingKMeans()

Method Summary

Methods

Modifier and Type	Method and Description
Assignments	cluster(Matrix matrix, int numClusters, int kappa, double beta, SimilarityFunction simFunc) Clusters the rows of the provided matrix into the specified number of clusters in a single pass using the parameters to guide how clusters are formed.
Assignments	cluster(Matrix matrix, int numClusters, Properties props) Clusters the set of rows in the given Matrix into the specified number of clusters and using the default values for beta, kappa, and the SimilarityFunction, unless otherwise specified in the properties.
Assignments	cluster(Matrix matrix, Properties props) Throws an UnsupportedOperationException if called.

Methods inherited from class java.lang.Object

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

Field Detail

BETA_PROPERTY

public static final String BETA_PROPERTY

The property for specifying the beta value which determines increases to the facilities cost for creating a new facility, see page 6 in the paper for details.

See Also:

Constant Field Values

KAPPA_PROPERTY

public static final String KAPPA_PROPERTY

The property for specifying kappa, the maximum number of facilities. By default kappa is selected as k * log(num data points).

See Also:

Constant Field Values

SIMILARITY_FUNCTION_PROPERTY

public static final String SIMILARITY_FUNCTION_PROPERTY

The property for specifying the similarity function with which to compare data points

See Also:

Constant Field Values

DEFAULT_BETA

public static final double DEFAULT_BETA

The default value of beta that appeared to work best according ot Michael Shindler

See Also:

Constant Field Values

DEFAULT_SIMILARITY_FUNCTION

public static final SimilarityFunction DEFAULT_SIMILARITY_FUNCTION

The default similarity function is in the inverse of the square of the Euclidean distances, which preserves all the properties specified in the Shindler et al (2011) paper.

Constructor Detail

FastStreamingKMeans

public FastStreamingKMeans()

Method Detail

cluster

public Assignments cluster(Matrix matrix,
                  Properties props)

Throws an UnsupportedOperationException if called.

cluster

public Assignments cluster(Matrix matrix,
                  int numClusters,
                  Properties props)

Clusters the set of rows in the given Matrix into the specified number of clusters and using the default values for beta, kappa, and the SimilarityFunction, unless otherwise specified in the properties.

Parameters:

matrix -

numClusters -

props -

Returns:

cluster

public Assignments cluster(Matrix matrix,
                  int numClusters,
                  int kappa,
                  double beta,
                  SimilarityFunction simFunc)

Clusters the rows of the provided matrix into the specified number of clusters in a single pass using the parameters to guide how clusters are formed. Note that due to the streaming nature of the algorithm, fewer than numClusters may be returned.

Parameters:

matrix - the matrix whose rows are to be clustered

numClusters - the number of clusters to be returned. Note that under some circumstances, the algorithm may return fewer clusters than this amount.

kappa - the maximum number of facilities (clusters) to keep in memory at any given point. At most this should be numClusters * Math.log(matrix.rows())

beta - the initial cost for creating a new facility. The default value of is recommended for this parameter, unless specific customization is required.

simFunc - the similarity function used to compare rows of the matrix. In the original paper, this is the inverse of square of the Euclidean distance.

Returns:

an assignment from each row of the matrix to a cluster identifier.