tutorial.clustering

Class SameSizeKMeansAlgorithm<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractPrimitiveDistanceBasedAlgorithm<NumberVector,Clustering<M>>

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

tutorial.clustering.SameSizeKMeansAlgorithm<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MeanModel>>, KMeans<V,MeanModel>, DistanceBasedAlgorithm<V>

public class SameSizeKMeansAlgorithm<V extends NumberVector>
extends AbstractKMeans<V,MeanModel>

K-means variation that produces equally sized clusters. Note that this is a rather obvious variation, and one cannot expect very good results from this algorithm. K-means already is quite primitive, and putting in the size constraint will likely not make the results much better (in particular, it will even less be able to make sense of outliers!) There is no reference for this algorithm. If you want to cite it, please cite the latest ELKI release as given on the ELKI web page: http://elki.dbs.ifi.lmu.de/wiki/Releases

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	SameSizeKMeansAlgorithm.Meta Object metadata.
static class	SameSizeKMeansAlgorithm.Parameterizer<V extends NumberVector> Parameterization class.
class	SameSizeKMeansAlgorithm.PreferenceComparator Sort a list of integers (= cluster numbers) by the distances.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class logger

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans

initializer, k, maxiter

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractPrimitiveDistanceBasedAlgorithm

distanceFunction

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

INIT_ID, K_ID, MAXITER_ID, SEED_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
SameSizeKMeansAlgorithm(PrimitiveDistanceFunction<? super NumberVector> distanceFunction, int k, int maxiter, KMeansInitialization<? super V> initializer) Constructor.

Method Summary

Modifier and Type	Method and Description
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected ArrayModifiableDBIDs	initialAssignment(List<ModifiableDBIDs> clusters, WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas, DBIDs ids)
protected WritableDataStore<SameSizeKMeansAlgorithm.Meta>	initializeMeta(Relation<V> relation, List<? extends NumberVector> means) Initialize the metadata storage.
protected List<Vector>	refineResult(Relation<V> relation, List<Vector> means, List<ModifiableDBIDs> clusters, WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas, ArrayModifiableDBIDs tids) Perform k-means style iterations to improve the clustering result.
Clustering<MeanModel>	run(Database database, Relation<V> relation) Run k-means with cluster size constraints.
protected void	transfer(WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas, SameSizeKMeansAlgorithm.Meta meta, ModifiableDBIDs src, ModifiableDBIDs dst, DBIDRef id, Integer dstnum) Transfer a single element from one cluster to another.
protected void	updateDistances(Relation<V> relation, List<Vector> means, WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas, PrimitiveDistanceFunction<? super NumberVector> df) Compute the distances of each object to all means.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.AbstractKMeans

assignToNearestCluster, getInputTypeRestriction, incrementalUpdateMean, logVarstat, macQueenIterate, means, medians, setDistanceFunction, setK, updateAssignment

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

getDistanceFunction

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

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

getDistanceFunction

Field Detail

LOG

private static final Logging LOG

Class logger

Constructor Detail

SameSizeKMeansAlgorithm

public SameSizeKMeansAlgorithm(PrimitiveDistanceFunction<? super NumberVector> distanceFunction,
                               int k,
                               int maxiter,
                               KMeansInitialization<? super V> initializer)

Constructor.

Parameters:

distanceFunction - Distance function

k - K parameter

maxiter - Maximum number of iterations

initializer -

Method Detail

run

public Clustering<MeanModel> run(Database database,
                                 Relation<V> relation)

Run k-means with cluster size constraints.

Parameters:

database - Database

relation - relation to use

Returns:

result

initializeMeta

protected WritableDataStore<SameSizeKMeansAlgorithm.Meta> initializeMeta(Relation<V> relation,
                                                                         List<? extends NumberVector> means)

Initialize the metadata storage.

Parameters:

relation - Relation to process

means - Mean vectors

Returns:

Initialized storage

initialAssignment

protected ArrayModifiableDBIDs initialAssignment(List<ModifiableDBIDs> clusters,
                                                 WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas,
                                                 DBIDs ids)

updateDistances

protected void updateDistances(Relation<V> relation,
                               List<Vector> means,
                               WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas,
                               PrimitiveDistanceFunction<? super NumberVector> df)

Compute the distances of each object to all means. Update SameSizeKMeansAlgorithm.Meta.secondary to point to the best cluster number except the current cluster assignment

Parameters:

relation - Data relation

means - Means

metas - Metadata storage

df - Distance function

refineResult

protected List<Vector> refineResult(Relation<V> relation,
                                    List<Vector> means,
                                    List<ModifiableDBIDs> clusters,
                                    WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas,
                                    ArrayModifiableDBIDs tids)

Perform k-means style iterations to improve the clustering result.

Parameters:

relation - Data relation

means - Means list

clusters - Cluster list

metas - Metadata storage

tids - DBIDs array

Returns:

final means

transfer

protected void transfer(WritableDataStore<SameSizeKMeansAlgorithm.Meta> metas,
                        SameSizeKMeansAlgorithm.Meta meta,
                        ModifiableDBIDs src,
                        ModifiableDBIDs dst,
                        DBIDRef id,
                        Integer dstnum)

Transfer a single element from one cluster to another.

Parameters:

metas - Meta storage

meta - Meta of current object

src - Source cluster

dst - Destination cluster

id - Object ID

dstnum - Destination cluster number

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<MeanModel>>

Returns:

the static logger