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

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

java.lang.Object

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

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

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

Type Parameters:

V - Vector type

D - Distance type

All Implemented Interfaces:

Algorithm, KMeans, InspectionUtilFrequentlyScanned, Parameterizable

Direct Known Subclasses:

KMeansLloyd, KMeansMacQueen, KMediansLloyd

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

Abstract base class for k-means implementations.

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractPrimitiveDistanceBasedAlgorithm

AbstractPrimitiveDistanceBasedAlgorithm.Parameterizer<O,D extends Distance<D>>

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 interface de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeans

INIT_ID, K_ID, MAXITER_ID, SEED_ID

Constructor Summary

Constructors

Constructor and Description
AbstractKMeans(PrimitiveDistanceFunction<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) 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) 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.

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

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<V,?>> initializer

Method to choose initial means.

Constructor Detail

AbstractKMeans

public AbstractKMeans(PrimitiveDistanceFunction<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)

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

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<MeanModel<V extends NumberVector<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)

Perform a MacQueen style iteration.

Parameters:

relation - Relation

means - Means

clusters - Clusters

Returns:

true when the means have changed