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

Class AbstractKMeans<V extends NumberVector,M extends Model>

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,M>

Type Parameters:

V - Vector type

M - Cluster model type

All Implemented Interfaces:

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

Direct Known Subclasses:

KMeansBatchedLloyd, KMeansElkan, KMeansHamerly, KMeansHybridLloydMacQueen, KMeansLloyd, KMeansMacQueen, KMediansLloyd, ParallelLloydKMeans, SingleAssignmentKMeans, XMeans

public abstract class AbstractKMeans<V extends NumberVector,M extends Model>
extends AbstractNumberVectorDistanceBasedAlgorithm<V,Clustering<M>>
implements KMeans<V,M>, ClusteringAlgorithm<Clustering<M>>

Abstract base class for k-means implementations.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
protected KMeansInitialization<? super V>	initializer Method to choose initial means.
protected int	k Number of cluster centers to initialize.
protected int	maxiter Maximum number of iterations

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
AbstractKMeans(NumberVectorDistanceFunction<? super V> distanceFunction, int k, int maxiter, KMeansInitialization<? super V> initializer) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	assignToNearestCluster(Relation<? extends V> relation, List<? extends NumberVector> means, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, double[] varsum) Returns a list of clusters.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected void	incrementalUpdateMean(Vector mean, V vec, int newsize, double op) Compute an incremental update for the mean.
protected void	logVarstat(DoubleStatistic varstat, double[] varsum) Log statistics on the variance sum.
protected boolean	macQueenIterate(Relation<V> relation, List<Vector> means, List<ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, double[] varsum) Perform a MacQueen style iteration.
protected List<Vector>	means(List<? extends DBIDs> clusters, List<? extends NumberVector> means, Relation<V> database) Returns the mean vectors of the given clusters in the given database.
protected List<Vector>	medians(List<? extends DBIDs> clusters, List<Vector> medians, Relation<V> database) Returns the median vectors of the given clusters in the given database.
void	setDistanceFunction(NumberVectorDistanceFunction<? super V> distanceFunction) Set the distance function to use.
void	setK(int k) Set the value of k.
private boolean	updateMeanAndAssignment(List<ModifiableDBIDs> clusters, List<Vector> means, int minIndex, V fv, DBIDIter iditer, WritableIntegerDataStore assignment) Try to update the cluster assignment.

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

getDistanceFunction

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

getLogger, 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.kmeans.KMeans

run

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

k

protected int k

Number of cluster centers to initialize.

maxiter

protected int maxiter

Maximum number of iterations

initializer

protected KMeansInitialization<? super V extends NumberVector> initializer

Method to choose initial means.

Constructor Detail

AbstractKMeans

public AbstractKMeans(NumberVectorDistanceFunction<? super V> distanceFunction,
              int k,
              int maxiter,
              KMeansInitialization<? super V> initializer)

Constructor.

Parameters:

distanceFunction - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

Method Detail

assignToNearestCluster

protected boolean assignToNearestCluster(Relation<? extends V> relation,
                             List<? extends NumberVector> means,
                             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

means - a list of k means

clusters - cluster assignment

assignment - Current cluster assignment

varsum - Variance sum output

Returns:

true when the object was reassigned

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Clustering<M extends Model>>

Returns:

Type restriction

means

protected List<Vector> means(List<? extends DBIDs> clusters,
                 List<? extends NumberVector> means,
                 Relation<V> database)

Returns the mean vectors of the given clusters in the given database.

Parameters:

clusters - the clusters to compute the means

means - the recent means

database - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

medians

protected List<Vector> medians(List<? extends DBIDs> clusters,
                   List<Vector> medians,
                   Relation<V> database)

Returns the median vectors of the given clusters in the given database.

Parameters:

clusters - the clusters to compute the means

medians - the recent medians

database - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

incrementalUpdateMean

protected void incrementalUpdateMean(Vector mean,
                         V vec,
                         int newsize,
                         double op)

Compute an incremental update for the mean.

Parameters:

mean - Mean to update

vec - Object vector

newsize - (New) size of cluster

op - Cluster size change / Weight change

macQueenIterate

protected boolean macQueenIterate(Relation<V> relation,
                      List<Vector> means,
                      List<ModifiableDBIDs> clusters,
                      WritableIntegerDataStore assignment,
                      double[] varsum)

Perform a MacQueen style iteration.

Parameters:

relation - Relation

means - Means

clusters - Clusters

assignment - Current cluster assignment

varsum - Variance sum output

Returns:

true when the means have changed

updateMeanAndAssignment

private boolean updateMeanAndAssignment(List<ModifiableDBIDs> clusters,
                              List<Vector> means,
                              int minIndex,
                              V fv,
                              DBIDIter iditer,
                              WritableIntegerDataStore assignment)

Try to update the cluster assignment.

Parameters:

clusters - Current clusters

means - Means to update

minIndex - Cluster to assign to

fv - Vector

iditer - Object ID

assignment - Current cluster assignment

Returns:

true when assignment changed

setK

public void setK(int k)

Description copied from interface: KMeans

Set the value of k. Needed for some types of nested k-means.

Specified by:

setK in interface KMeans<V extends NumberVector,M extends Model>

Parameters:

k - K parameter

setDistanceFunction

public void setDistanceFunction(NumberVectorDistanceFunction<? super V> distanceFunction)

Description copied from interface: KMeans

Set the distance function to use.

Specified by:

setDistanceFunction in interface KMeans<V extends NumberVector,M extends Model>

Parameters:

distanceFunction - Distance function.

logVarstat

protected void logVarstat(DoubleStatistic varstat,
              double[] varsum)

Log statistics on the variance sum.

Parameters:

varstat - Statistics log instance

varsum - Variance sum per cluster