Package elki.clustering.kmedoids

Class PAM<O>

java.lang.Object

elki.clustering.kmedoids.PAM<O>

Type Parameters:

O - object datatype

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MedoidModel>>, KMedoidsClustering<O>

Direct Known Subclasses:

CLARA, EagerPAM, FastPAM1, PAMSIL, ReynoldsPAM, SingleAssignmentKMedoids

@Title("Partioning Around Medoids")
@Priority(100)
@Reference(authors="L. Kaufman, P. J. Rousseeuw",title="Clustering by means of Medoids",booktitle="Statistical Data Analysis Based on the L1-Norm and Related Methods",bibkey="books/misc/KauRou87") @Reference(authors="L. Kaufman, P. J. Rousseeuw",title="Partitioning Around Medoids (Program PAM)",booktitle="Finding Groups in Data: An Introduction to Cluster Analysis",url="https://doi.org/10.1002/9780470316801.ch2",bibkey="doi:10.1002/9780470316801.ch2") @Reference(authors="R. A. Whitaker",title="A Fast Algorithm For The Greedy Interchange For Large-Scale Clustering And Median Location Problems",booktitle="INFOR: Information Systems and Operational Research 21(2)",url="https://doi.org/10.1080/03155986.1983.11731889",bibkey="doi:10.1080/03155986.1983.11731889")
public class PAM<O>
extends java.lang.Object
implements KMedoidsClustering<O>

The original Partitioning Around Medoids (PAM) algorithm or k-medoids clustering, as proposed by Kaufman and Rousseeuw; a largely equivalent method was also proposed by Whitaker in the operations research domain, and is well known by the name "fast interchange" there.

Reference:

L. Kaufman, P. J. Rousseeuw
Clustering by means of Medoids
Statistical Data Analysis Based on the L1-Norm and Related Methods

R. A. Whitaker
A Fast Algorithm For The Greedy Interchange For Large-Scale Clustering And Median Location Problems
INFOR: Information Systems and Operational Research 21(2)

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	PAM.Instance	Instance for a single dataset.
static class	PAM.Par<O>	Parameterization class.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
protected Distance<? super O>	distance	Distance function used.
protected KMedoidsInitialization<O>	initializer	Method to choose initial means.
protected int	k	The number of clusters to produce.
private static Logging	LOG	The logger for this class.
protected int	maxiter	The maximum number of iterations.

Constructor Summary

Constructors

Constructor	Description
PAM(Distance<? super O> distance, int k, int maxiter, KMedoidsInitialization<O> initializer)	Constructor.

Method Summary

Modifier and Type	Method	Description
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
protected Logging	getLogger()	Get the static class logger.
protected ArrayModifiableDBIDs	initialMedoids(DistanceQuery<? super O> distQ, DBIDs ids, int k)	Choose the initial medoids.
Clustering<MedoidModel>	run(Relation<O> relation)	Run k-medoids clustering.
Clustering<MedoidModel>	run(Relation<O> relation, int k, DistanceQuery<? super O> distQ)	Run k-medoids clustering with a given distance query. Not a very elegant API, but needed for some types of nested k-medoids.
protected static Clustering<MedoidModel>	wrapResult(DBIDs ids, WritableIntegerDataStore assignment, ArrayModifiableDBIDs medoids, java.lang.String name)	Wrap the clustering result.

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

Field Detail

LOG

private static final Logging LOG

The logger for this class.

distance

protected Distance<? super O> distance

Distance function used.

k

protected int k

The number of clusters to produce.

maxiter

protected int maxiter

The maximum number of iterations.

initializer

protected KMedoidsInitialization<O> initializer

Method to choose initial means.

Constructor Detail

PAM

public PAM(Distance<? super O> distance,
           int k,
           int maxiter,
           KMedoidsInitialization<O> initializer)

Constructor.

Parameters:

distance - distance function

k - k parameter

maxiter - Maxiter parameter

initializer - Function to generate the initial means

Method Detail

run

public Clustering<MedoidModel> run(Relation<O> relation)

Description copied from interface: KMedoidsClustering

Run k-medoids clustering.

Specified by:

run in interface KMedoidsClustering<O>

Parameters:

relation - relation to use

Returns:

result

run

public Clustering<MedoidModel> run(Relation<O> relation,
                                   int k,
                                   DistanceQuery<? super O> distQ)

Description copied from interface: KMedoidsClustering

Run k-medoids clustering with a given distance query.
Not a very elegant API, but needed for some types of nested k-medoids.

Specified by:

run in interface KMedoidsClustering<O>

Parameters:

relation - relation to use

k - Number of clusters

distQ - Distance query to use

Returns:

result

initialMedoids

protected ArrayModifiableDBIDs initialMedoids(DistanceQuery<? super O> distQ,
                                              DBIDs ids,
                                              int k)

Choose the initial medoids.

Parameters:

distQ - Distance query

ids - IDs to choose from

k - Number of medoids to choose from

Returns:

Initial medoids

wrapResult

protected static Clustering<MedoidModel> wrapResult(DBIDs ids,
                                                    WritableIntegerDataStore assignment,
                                                    ArrayModifiableDBIDs medoids,
                                                    java.lang.String name)

Wrap the clustering result.

Parameters:

ids - Object ids

assignment - Cluster assignment

medoids - Medoids

name - Clustering name

Returns:

Wrapped result

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

getLogger

protected Logging getLogger()

Get the static class logger.