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, InspectionUtilFrequentlyScanned, Parameterizable

Direct Known Subclasses:

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

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<? 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) 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

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

run

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)

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<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)

Perform a MacQueen style iteration.

Parameters:

relation - Relation

means - Means

clusters - Clusters

Returns:

true when the means have changed