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

Class KMedoidsPark<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.KMedoidsPark<V>

Type Parameters:

V - vector datatype

All Implemented Interfaces:

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

@Reference(authors="H.-S. Park, C.-H. Jun",title="A simple and fast algorithm for K-medoids clustering",booktitle="Expert Systems with Applications 36(2)",url="https://doi.org/10.1016/j.eswa.2008.01.039",bibkey="DBLP:journals/eswa/ParkJ09") @Reference(authors="A. P. Reynolds, G. Richards, B. de la Iglesia, V. J. Rayward-Smith",title="Clustering Rules: A Comparison of Partitioning and Hierarchical Clustering Algorithms",booktitle="J. Math. Model. Algorithms 5(4)",url="https://doi.org/10.1007/s10852-005-9022-1",bibkey="DBLP:journals/jmma/ReynoldsRIR06")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsEM")
public class KMedoidsPark<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.

This implementation evolved naturally from EM and k-means algorithms, but apparently a similar approach was published by Park and Jun, and also Reynolds et al. discussed this kind of approach before as a side note.

In our experiments, it tends to be much faster than PAM, but also find less good solutions, as the medoids are only chosen from the cluster members. This aligns with findings of Reynolds et al. and can be explained with the requirement of the new medoid to cover the entire cluster.

Reference:

H.-S. Park, C.-H. Jun
A simple and fast algorithm for K-medoids clustering
Expert Systems with Applications 36(2)

A. P. Reynolds, G. Richards, B. de la Iglesia, V. J. Rayward-Smith
Clustering Rules: A Comparison of Partitioning and Hierarchical Clustering Algorithms
J. Math. Model. Algorithms 5(4)

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KMedoidsPark.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 java.lang.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 class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
protected double	assignToNearestCluster(DBIDArrayIter miter, double[] dsum, java.util.List<? extends ModifiableDBIDs> clusters, DistanceQuery<V> distQ) Returns a list of clusters.
protected int	currentCluster(java.util.List<? extends ModifiableDBIDs> clusters, DBIDRef id) Find the current cluster assignment.
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

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 java.lang.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

KMedoidsPark

public KMedoidsPark(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 double assignToNearestCluster(DBIDArrayIter miter,
                                        double[] dsum,
                                        java.util.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:

miter - Iterator over the medoids

dsum - Distance sums

clusters - cluster assignment

distQ - distance query

Returns:

cost

currentCluster

protected int currentCluster(java.util.List<? extends ModifiableDBIDs> clusters,
                             DBIDRef id)

Find the current cluster assignment.

Parameters:

clusters - Clusters

id - Current object

Returns:

Current cluster assignment.

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