Package elki.clustering.kmeans

Class AbstractKMeans<V extends NumberVector,M extends Model>

java.lang.Object

elki.clustering.kmeans.AbstractKMeans<V,M>

Type Parameters:

V - Vector type

M - Cluster model type

All Implemented Interfaces:

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

Direct Known Subclasses:

BetulaLloydKMeans, CompareMeans, HamerlyKMeans, HartiganWongKMeans, KDTreePruningKMeans, KMeansMinusMinus, KMediansLloyd, LloydKMeans, MacQueenKMeans, ParallelLloydKMeans, SameSizeKMeans, SimplifiedElkanKMeans, SingleAssignmentKMeans, SphericalKMeans, XMeans, YinYangKMeans

public abstract class AbstractKMeans<V extends NumberVector,M extends Model>
extends java.lang.Object
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	Description
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.Par<V extends NumberVector>	Parameterization class.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
protected NumberVectorDistance<? super V>	distance	Distance function used.
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 interface elki.clustering.kmeans.KMeans

DISTANCE_FUNCTION_ID, INIT_ID, K_ID, MAXITER_ID, SEED_ID, VARSTAT_ID

Constructor Summary

Constructors

Constructor	Description
AbstractKMeans(int k, int maxiter, KMeansInitialization initializer)	Constructor.
AbstractKMeans(NumberVectorDistance<? super V> distance, int k, int maxiter, KMeansInitialization initializer)	Constructor.

Method Summary

Modifier and Type	Method	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.
private static void	densePlusEquals(double[] sum, NumberVector vec)	Similar to VMath.plusEquals, but accepts a number vector.
private static void	densePlusMinusEquals(double[] add, double[] sub, NumberVector vec)	Add to one, remove from another.
NumberVectorDistance<? super V>	getDistance()	Returns the distance.
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
protected abstract Logging	getLogger()	Get the (STATIC) logger for this class.
protected static void	incrementalUpdateMean(double[] mean, NumberVector vec, int newsize, double op)	Compute an incremental update for the mean.
protected double[][]	initialMeans(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	setDistance(NumberVectorDistance<? super V> distance)	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.
private static void	sparsePlusEquals(double[] sum, SparseNumberVector vec)	Similar to VMath.plusEquals, but for sparse number vectors.
private static void	sparsePlusMinusEquals(double[] add, double[] sub, SparseNumberVector vec)	Add to one, remove from another.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.clustering.ClusteringAlgorithm

autorun

Methods inherited from interface elki.clustering.kmeans.KMeans

run

Field Detail

distance

protected NumberVectorDistance<? super V extends NumberVector> distance

Distance function used.

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(int k,
                      int maxiter,
                      KMeansInitialization initializer)

Constructor.

Parameters:

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

AbstractKMeans

public AbstractKMeans(NumberVectorDistance<? super V> distance,
                      int k,
                      int maxiter,
                      KMeansInitialization initializer)

Constructor.

Parameters:

distance - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

Method Detail

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction

initialMeans

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

Choose the initial means.

Parameters:

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

densePlusEquals

private static void densePlusEquals(double[] sum,
                                    NumberVector vec)

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

Parameters:

sum - Aggregation array

vec - Vector to add

sparsePlusEquals

private static void sparsePlusEquals(double[] sum,
                                     SparseNumberVector vec)

Similar to VMath.plusEquals, but for sparse number vectors.

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

densePlusMinusEquals

private static void densePlusMinusEquals(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

sparsePlusMinusEquals

private static void sparsePlusMinusEquals(double[] add,
                                          double[] sub,
                                          SparseNumberVector 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

getDistance

public NumberVectorDistance<? super V> getDistance()

Description copied from interface: KMeans

Returns the distance.

Specified by:

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

Returns:

the distance

setDistance

public void setDistance(NumberVectorDistance<? super V> distance)

Description copied from interface: KMeans

Set the distance function to use.

Specified by:

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

Parameters:

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

getLogger

protected abstract Logging getLogger()

Get the (STATIC) logger for this class.

Returns:

the static logger