de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans

Class KMeansBatchedLloyd<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractNumberVectorDistanceBasedAlgorithm<V,Clustering<M>>

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans<V,KMeansModel>

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansBatchedLloyd<V>

Type Parameters:

V - vector datatype

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<KMeansModel>>, KMeans<V,KMeansModel>, DistanceBasedAlgorithm<V>

public class KMeansBatchedLloyd<V extends NumberVector>
extends AbstractKMeans<V,KMeansModel>

An algorithm for k-means, using Lloyd-style bulk iterations. However, in contrast to Lloyd's k-means and similar to MacQueen, we do update the mean vectors multiple times, not only at the very end of the iteration. This should yield faster convergence at little extra cost. To avoid issues with ordered data, we use random sampling to obtain the data blocks.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KMeansBatchedLloyd.Parameterizer<V extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int	blocks Number of blocks to use.
private static String	KEY Key for statistics logging.
private static Logging	LOG The logger for this class.
(package private) RandomFactory	random Random used for partitioning.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans

initializer, k, maxiter

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractNumberVectorDistanceBasedAlgorithm

distanceFunction

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeans

INIT_ID, K_ID, MAXITER_ID, SEED_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
KMeansBatchedLloyd(NumberVectorDistanceFunction<? super V> distanceFunction, int k, int maxiter, KMeansInitialization<? super V> initializer, int blocks, RandomFactory random) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	assignToNearestCluster(Relation<V> relation, DBIDs ids, List<? extends NumberVector> oldmeans, double[][] meanshift, int[] changesize, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, double[] varsum) Returns a list of clusters.
protected Logging	getLogger() Get the (STATIC) logger for this class.
Clustering<KMeansModel>	run(Database database, Relation<V> relation) Run the clustering algorithm.
protected boolean	updateAssignment(DBIDIter id, V fv, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, double[][] meanshift, int[] changesize, int minIndex) Update the assignment of a single object.
protected void	updateMeans(List<Vector> means, double[][] meanshift, List<ModifiableDBIDs> clusters, int[] changesize) Merge changes into mean vectors.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans

assignToNearestCluster, getInputTypeRestriction, incrementalUpdateMean, logVarstat, macQueenIterate, means, medians, setDistanceFunction, setK

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractNumberVectorDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.ClusteringAlgorithm

run

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

getDistanceFunction

Field Detail

LOG

private static final Logging LOG

The logger for this class.

KEY

private static final String KEY

Key for statistics logging.

blocks

int blocks

Number of blocks to use.

random

RandomFactory random

Random used for partitioning.

Constructor Detail

KMeansBatchedLloyd

public KMeansBatchedLloyd(NumberVectorDistanceFunction<? super V> distanceFunction,
                  int k,
                  int maxiter,
                  KMeansInitialization<? super V> initializer,
                  int blocks,
                  RandomFactory random)

Constructor.

Parameters:

distanceFunction - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Initialization method

blocks - Number of blocks

random - Random factory used for partitioning.

Method Detail

run

public Clustering<KMeansModel> run(Database database,
                          Relation<V> relation)

Description copied from interface: KMeans

Run the clustering algorithm.

Parameters:

database - Database to run on.

relation - Relation to process.

Returns:

Clustering result

assignToNearestCluster

protected boolean assignToNearestCluster(Relation<V> relation,
                             DBIDs ids,
                             List<? extends NumberVector> oldmeans,
                             double[][] meanshift,
                             int[] changesize,
                             List<? extends ModifiableDBIDs> clusters,
                             WritableIntegerDataStore assignment,
                             double[] varsum)

Returns a list of clusters. The k^th cluster contains the ids of those FeatureVectors, that are nearest to the k^th mean.

Parameters:

relation - the database to cluster

ids - IDs to process

oldmeans - a list of k means

meanshift - delta to apply to each mean

changesize - New cluster sizes

clusters - cluster assignment

assignment - Current cluster assignment

varsum - Sum of variances

Returns:

true when the object was reassigned

updateAssignment

protected boolean updateAssignment(DBIDIter id,
                       V fv,
                       List<? extends ModifiableDBIDs> clusters,
                       WritableIntegerDataStore assignment,
                       double[][] meanshift,
                       int[] changesize,
                       int minIndex)

Update the assignment of a single object.

Parameters:

id - Object to assign

fv - Vector

clusters - Clusters

assignment - Current cluster assignment

meanshift - Current shifting offset

changesize - Size change of the current cluster

minIndex - Index of best cluster.

Returns:

true when assignment changed.

updateMeans

protected void updateMeans(List<Vector> means,
               double[][] meanshift,
               List<ModifiableDBIDs> clusters,
               int[] changesize)

Merge changes into mean vectors.

Parameters:

means - Mean vectors

meanshift - Shift offset

clusters -

changesize - Size of change (for weighting!)

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<KMeansModel>>

Returns:

the static logger