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

Class AbstractKMeans<V extends NumberVector<?>,D extends Distance<D>,M extends MeanModel<V>>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractPrimitiveDistanceBasedAlgorithm<NumberVector<?>,D,Clustering<M>>

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

Type Parameters:

V - Vector type

D - Distance type

M - Cluster model type

All Implemented Interfaces:

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

Direct Known Subclasses:

KMeansBatchedLloyd, KMeansHybridLloydMacQueen, KMeansLloyd, KMeansMacQueen, KMediansLloyd, SameSizeKMeansAlgorithm

public abstract class AbstractKMeans<V extends NumberVector<?>,D extends Distance<D>,M extends MeanModel<V>>
extends AbstractPrimitiveDistanceBasedAlgorithm<NumberVector<?>,D,Clustering<M>>
implements KMeans<V,D,M>, ClusteringAlgorithm<Clustering<M>>

Abstract base class for k-means implementations.

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
protected KMeansInitialization<V>	initializer Method to choose initial means.
protected int	k Holds the value of KMeans.K_ID.
protected int	maxiter Holds the value of KMeans.MAXITER_ID.

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

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

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	assignToNearestCluster(Relation<V> relation, List<? extends NumberVector<?>> means, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment) 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 boolean	macQueenIterate(Relation<V> relation, List<Vector> means, List<ModifiableDBIDs> clusters, WritableIntegerDataStore assignment) Perform a MacQueen style iteration.
protected List<Vector>	means(List<? extends ModifiableDBIDs> clusters, List<? extends NumberVector<?>> means, Relation<V> database) Returns the mean vectors of the given clusters in the given database.
protected List<NumberVector<?>>	medians(List<? extends ModifiableDBIDs> clusters, List<? extends NumberVector<?>> medians, Relation<V> database) Returns the median vectors of the given clusters in the given database.
void	setDistanceFunction(PrimitiveDistanceFunction<? super NumberVector<?>,D> distanceFunction) Set the distance function to use.
void	setK(int k) Set the value of k.
protected boolean	updateAssignment(DBIDIter iditer, List<? extends ModifiableDBIDs> clusters, WritableIntegerDataStore assignment, int newA)
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.AbstractPrimitiveDistanceBasedAlgorithm

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

Holds the value of KMeans.K_ID.

maxiter

protected int maxiter

Holds the value of KMeans.MAXITER_ID.

initializer

protected KMeansInitialization<V extends NumberVector<?>> initializer

Method to choose initial means.

Constructor Detail

AbstractKMeans

public AbstractKMeans(PrimitiveDistanceFunction<? super NumberVector<?>,D> distanceFunction,
              int k,
              int maxiter,
              KMeansInitialization<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<V> relation,
                             List<? extends NumberVector<?>> means,
                             List<? extends ModifiableDBIDs> clusters,
                             WritableIntegerDataStore assignment)

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

Returns:

true when the object was reassigned

updateAssignment

protected boolean updateAssignment(DBIDIter iditer,
                       List<? extends ModifiableDBIDs> clusters,
                       WritableIntegerDataStore assignment,
                       int newA)

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 MeanModel<V>>>

Returns:

Type restriction

means

protected List<Vector> means(List<? extends ModifiableDBIDs> 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<NumberVector<?>> medians(List<? extends ModifiableDBIDs> clusters,
                            List<? extends NumberVector<?>> 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)

Perform a MacQueen style iteration.

Parameters:

relation - Relation

means - Means

clusters - Clusters

assignment - Current cluster assignment

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<?>,D extends Distance<D>,M extends MeanModel<V>>

Parameters:

k - K parameter

setDistanceFunction

public void setDistanceFunction(PrimitiveDistanceFunction<? super NumberVector<?>,D> distanceFunction)

Description copied from interface: KMeans

Set the distance function to use.

Specified by:

setDistanceFunction in interface KMeans<V extends NumberVector<?>,D extends Distance<D>,M extends MeanModel<V>>

Parameters:

distanceFunction - Distance function.