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

Class AbstractKMeans.Instance

java.lang.Object

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

Direct Known Subclasses:

KMeansCompare.Instance, KMeansHamerly.Instance, KMeansLloyd.Instance, KMeansMacQueen.Instance, KMeansMinusMinus.Instance, KMeansSimplifiedElkan.Instance, KMediansLloyd.Instance, SingleAssignmentKMeans.Instance

Enclosing class:

AbstractKMeans<V extends NumberVector,M extends Model>

protected abstract static class AbstractKMeans.Instance
extends java.lang.Object

Inner instance for a run, for better encapsulation, that encapsulates the standard flow of most (but not all) k-means variations.

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
protected WritableIntegerDataStore	assignment A mapping of elements to cluster ids.
protected java.util.List<ModifiableDBIDs>	clusters Store the elements per cluster.
private NumberVectorDistanceFunction<?>	df Distance function.
private long	diststat Number of distance computations
protected boolean	isSquared Indicates whether the distance function is squared.
protected int	k Number of clusters.
protected java.lang.String	key Key for statistics logging.
(package private) double[][]	means Cluster means.
protected Relation<? extends NumberVector>	relation Data relation.
protected double[]	varsum Sum of squared deviations in each cluster.

Constructor Summary

Constructors

Constructor and Description
Instance(Relation<? extends NumberVector> relation, NumberVectorDistanceFunction<?> df, double[][] means) Constructor.

Method Summary

Modifier and Type	Method and Description
protected int	assignToNearestCluster() Assign each object to the nearest cluster.
protected Clustering<KMeansModel>	buildResult() Build a standard k-means result, with known cluster variance sums.
protected Clustering<KMeansModel>	buildResult(boolean varstat, Relation<? extends NumberVector> relation) Build the result, recomputing the cluster variance if varstat is set to true.
protected void	copyMeans(double[][] src, double[][] dst) Copy means
protected double	distance(NumberVector x, NumberVector y) Compute a distance (and count the distance computations).
(package private) abstract Logging	getLogger() Get the class logger.
protected boolean	isSquared() Get if the distance function is squared.
protected abstract int	iterate(int iteration) Main loop function.
protected void	meansFromSums(double[][] dst, double[][] sums) Compute means from cluster sums by averaging.
protected double	movedDistance(double[][] means, double[][] newmeans, double[] dists) Maximum distance moved.
protected void	recomputeSeperation(double[] sep, double[][] cdist) Recompute the separation of cluster means.
protected void	run(int maxiter) Run the clustering.

Methods inherited from class java.lang.Object

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

Field Detail

means

double[][] means

Cluster means.

clusters

protected java.util.List<ModifiableDBIDs> clusters

Store the elements per cluster.

assignment

protected WritableIntegerDataStore assignment

A mapping of elements to cluster ids.

varsum

protected double[] varsum

Sum of squared deviations in each cluster.

relation

protected Relation<? extends NumberVector> relation

Data relation.

diststat

private long diststat

Number of distance computations

df

private final NumberVectorDistanceFunction<?> df

Distance function.

k

protected final int k

Number of clusters.

isSquared

protected final boolean isSquared

Indicates whether the distance function is squared.

key

protected java.lang.String key

Key for statistics logging.

Constructor Detail

Instance

public Instance(Relation<? extends NumberVector> relation,
                NumberVectorDistanceFunction<?> df,
                double[][] means)

Constructor.

Parameters:

relation - Relation to process

means - Initial mean

Method Detail

distance

protected double distance(NumberVector x,
                          NumberVector y)

Compute a distance (and count the distance computations).

Parameters:

x - First object

y - Second object

Returns:

Distance

run

protected void run(int maxiter)

Run the clustering.

Parameters:

maxiter - Maximum number of iterations

iterate

protected abstract int iterate(int iteration)

Main loop function.

Parameters:

iteration - Iteration number (beginning at 1)

Returns:

Number of reassigned points

meansFromSums

protected void meansFromSums(double[][] dst,
                             double[][] sums)

Compute means from cluster sums by averaging.

Parameters:

dst - Output means

sums - Input sums

copyMeans

protected void copyMeans(double[][] src,
                         double[][] dst)

Copy means

Parameters:

src - Source values

dst - Destination values

assignToNearestCluster

protected int assignToNearestCluster()

Assign each object to the nearest cluster.

Returns:

number of objects reassigned

recomputeSeperation

protected void recomputeSeperation(double[] sep,
                                   double[][] cdist)

Recompute the separation of cluster means.

Used by Elkan's variant and Exponion.

Parameters:

sep - Output array of separation

cdist - Center-to-Center distances (half-sqrt scaled)

movedDistance

protected double movedDistance(double[][] means,
                               double[][] newmeans,
                               double[] dists)

Maximum distance moved.

Used by Hamerly, Elkan (not using the maximum).

Parameters:

means - Old means

newmeans - New means

dists - Distances moved (output)

Returns:

Maximum distance moved

buildResult

protected Clustering<KMeansModel> buildResult()

Build a standard k-means result, with known cluster variance sums.

Returns:

Clustering result

buildResult

protected Clustering<KMeansModel> buildResult(boolean varstat,
                                              Relation<? extends NumberVector> relation)

Build the result, recomputing the cluster variance if varstat is set to true.

Parameters:

varstat - Recompute cluster variance

relation - Data relation (only needed if varstat is set)

Returns:

Clustering result

isSquared

protected boolean isSquared()

Get if the distance function is squared.

Returns:

true when squared

getLogger

abstract Logging getLogger()

Get the class logger.

Returns:

Logger