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

Class KMedoidsEM<V>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<V,Clustering<MedoidModel>>

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsEM<V>

Type Parameters:

V - vector datatype

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MedoidModel>>, DistanceBasedAlgorithm<V>

public class KMedoidsEM<V>
extends AbstractDistanceBasedAlgorithm<V,Clustering<MedoidModel>>
implements ClusteringAlgorithm<Clustering<MedoidModel>>

A k-medoids clustering algorithm, implemented as EM-style bulk algorithm. In contrast to PAM, which will in each iteration update one medoid with one (arbitrary) non-medoid, this implementation follows the EM pattern. In the expectation step, the best medoid from the cluster members is chosen; in the M-step, the objects are reassigned to their nearest medoid. We do not have a reference for this algorithm. It borrows ideas from EM and PAM. If needed, you are welcome cite it using the latest ELKI publication (this variation is likely not worth publishing on its own).

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KMedoidsEM.Parameterizer<V> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected KMedoidsInitialization<V>	initializer Method to choose initial means.
protected int	k Holds the value of KMeans.K_ID.
private static String	KEY Key for statistics logging.
private static Logging	LOG The logger for this class.
protected int	maxiter Holds the value of KMeans.MAXITER_ID.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
KMedoidsEM(DistanceFunction<? super V> distanceFunction, int k, int maxiter, KMedoidsInitialization<V> initializer) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	assignToNearestCluster(ArrayDBIDs means, Mean[] mdist, List<? extends ModifiableDBIDs> clusters, DistanceQuery<V> distQ) Returns a list of clusters.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
Clustering<MedoidModel>	run(Database database, Relation<V> relation) Run k-medoids

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

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

Field Detail

LOG

private static final Logging LOG

The logger for this class.

KEY

private static final String KEY

Key for statistics logging.

k

protected int k

Holds the value of KMeans.K_ID.

maxiter

protected int maxiter

Holds the value of KMeans.MAXITER_ID.

initializer

protected KMedoidsInitialization<V> initializer

Method to choose initial means.

Constructor Detail

KMedoidsEM

public KMedoidsEM(DistanceFunction<? super V> distanceFunction,
          int k,
          int maxiter,
          KMedoidsInitialization<V> initializer)

Constructor.

Parameters:

distanceFunction - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

Method Detail

run

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

Run k-medoids

Parameters:

database - Database

relation - relation to use

Returns:

result

assignToNearestCluster

protected boolean assignToNearestCluster(ArrayDBIDs means,
                             Mean[] mdist,
                             List<? extends ModifiableDBIDs> clusters,
                             DistanceQuery<V> distQ)

Returns a list of clusters. The k^th cluster contains the ids of those FeatureVectors, that are nearest to the k^th mean.

Parameters:

means - a list of k means

mdist - Mean distances

clusters - cluster assignment

distQ - distance query

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

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<MedoidModel>>

Returns:

the static logger