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:

KMeansCompare, KMeansHamerly, KMeansLloyd, KMeansMacQueen, KMeansMinusMinus, KMeansSimplifiedElkan, KMediansLloyd, ParallelLloydKMeans, SameSizeKMeansAlgorithm, SingleAssignmentKMeans, XMeans

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

Abstract base class for k-means implementations.

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	AbstractKMeans.Instance Inner instance for a run, for better encapsulation, that encapsulates the standard flow of most (but not all) k-means variations.
static class	AbstractKMeans.Parameterizer<V extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected KMeansInitialization	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 class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

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

INIT_ID, K_ID, MAXITER_ID, SEED_ID, VARSTAT_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 initializer) Constructor.

Method Summary

Modifier and Type	Method and Description
private static double[][]	denseMeans(java.util.List<? extends DBIDs> clusters, double[][] means, Relation<? extends NumberVector> relation) Returns the mean vectors of the given clusters in the given database.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected static void	incrementalUpdateMean(double[] mean, NumberVector vec, int newsize, double op) Compute an incremental update for the mean.
protected double[][]	initialMeans(Database database, Relation<V> relation) Choose the initial means.
protected static double[][]	means(java.util.List<? extends DBIDs> clusters, double[][] means, Relation<? extends NumberVector> relation) Returns the mean vectors of the given clusters in the given database.
static void	minusEquals(double[] sum, NumberVector vec) Similar to VMath.minusEquals, but accepts a number vector.
protected static void	nearestMeans(double[][] cdist, int[][] cnum) Recompute the separation of cluster means.
static void	plusEquals(double[] sum, NumberVector vec) Similar to VMath.plusEquals, but accepts a number vector.
static void	plusMinusEquals(double[] add, double[] sub, NumberVector vec) Add to one, remove from another.
void	setDistanceFunction(NumberVectorDistanceFunction<? super V> distanceFunction) Set the distance function to use.
void	setInitializer(KMeansInitialization init) Set the initialization method.
void	setK(int k) Set the value of k.
private static double[][]	sparseMeans(java.util.List<? extends DBIDs> clusters, double[][] means, Relation<? extends SparseNumberVector> relation) Returns the mean vectors of the given clusters in the given database.

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

getDistanceFunction

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

getLogger, 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 initializer

Method to choose initial means.

Constructor Detail

AbstractKMeans

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

Constructor.

Parameters:

distanceFunction - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

Method Detail

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

initialMeans

protected double[][] initialMeans(Database database,
                                  Relation<V> relation)

Choose the initial means.

Parameters:

database - Database

relation - Relation

Returns:

Means

means

protected static double[][] means(java.util.List<? extends DBIDs> clusters,
                                  double[][] means,
                                  Relation<? extends NumberVector> relation)

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

Parameters:

clusters - the clusters to compute the means

means - the recent means

relation - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

denseMeans

private static double[][] denseMeans(java.util.List<? extends DBIDs> clusters,
                                     double[][] means,
                                     Relation<? extends NumberVector> relation)

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

Parameters:

clusters - the clusters to compute the means

means - the recent means

relation - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

plusEquals

public static void plusEquals(double[] sum,
                              NumberVector vec)

Similar to VMath.plusEquals, but accepts a number vector.

Parameters:

sum - Aggregation array

vec - Vector to add

minusEquals

public static void minusEquals(double[] sum,
                               NumberVector vec)

Similar to VMath.minusEquals, but accepts a number vector.

Parameters:

sum - Aggregation array

vec - Vector to subtract

plusMinusEquals

public static void plusMinusEquals(double[] add,
                                   double[] sub,
                                   NumberVector vec)

Add to one, remove from another.

Parameters:

add - Array to add to

sub - Array to remove from

vec - Vector to subtract

sparseMeans

private static double[][] sparseMeans(java.util.List<? extends DBIDs> clusters,
                                      double[][] means,
                                      Relation<? extends SparseNumberVector> relation)

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

Parameters:

clusters - the clusters to compute the means

means - the recent means

relation - the database containing the vectors

Returns:

the mean vectors of the given clusters in the given database

nearestMeans

protected static void nearestMeans(double[][] cdist,
                                   int[][] cnum)

Recompute the separation of cluster means.

Used by sort, and our exponion implementation.

Parameters:

cdist - Center-to-Center distances

cnum - Center numbers

incrementalUpdateMean

protected static void incrementalUpdateMean(double[] mean,
                                            NumberVector 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

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.

setInitializer

public void setInitializer(KMeansInitialization init)

Description copied from interface: KMeans

Set the initialization method.

Specified by:

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

Parameters:

init - Initialization method