Package elki.clustering.kmedoids.initialization

Class LAB<O>

java.lang.Object

elki.clustering.kmedoids.initialization.LAB<O>

Type Parameters:

O - Object type for KMedoids initialization

All Implemented Interfaces:

KMeansInitialization, KMedoidsInitialization<O>

@Reference(authors="Erich Schubert, Peter J. Rousseeuw",
           title="Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms",
           booktitle="Proc. 12th Int. Conf. Similarity Search and Applications (SISAP\'2019)",
           url="https://doi.org/10.1007/978-3-030-32047-8_16",
           bibkey="DBLP:conf/sisap/SchubertR19")
public class LAB<O>
extends java.lang.Object
implements KMeansInitialization, KMedoidsInitialization<O>

Linear approximative BUILD (LAB) initialization for FastPAM (and k-means).

This is a O(nk) aproximation of the original PAM BUILD. For performance, it uses an O(sqrt(n)) sample to achieve linear run time. The results will be worse than those of BUILD, but provide a good starting point for FastPAM optimization.

Reference:

Erich Schubert, Peter J. Rousseeuw
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
Proc. 12th Int. Conf. Similarity Search and Applications (SISAP'2019)

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LAB.Par<V>	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
private static Logging	LOG	Class logger.
private RandomFactory	rnd	Random generator

Constructor Summary

Constructors

Constructor	Description
LAB(RandomFactory rnd)	Constructor.

Method Summary

Modifier and Type	Method	Description
double[][]	chooseInitialMeans(Relation<? extends NumberVector> relation, int k, NumberVectorDistance<?> distance)	Choose initial means
DBIDs	chooseInitialMedoids(int k, DBIDs ids, DistanceQuery<? super O> distQ)	Choose initial means
protected static double	getMinDist(DBIDArrayIter j, DistanceQuery<?> distQ, DBIDArrayIter mi, WritableDoubleDataStore mindist)	Get the minimum distance to previous medoids.
private static void	shuffle(ArrayModifiableDBIDs ids, int ssize, int end, java.util.Random random)	Partial Fisher-Yates shuffle.

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final Logging LOG

Class logger.

rnd

private RandomFactory rnd

Random generator

Constructor Detail

LAB

public LAB(RandomFactory rnd)

Constructor.

Parameters:

rnd - Random generator

Method Detail

chooseInitialMeans

public double[][] chooseInitialMeans(Relation<? extends NumberVector> relation,
                                     int k,
                                     NumberVectorDistance<?> distance)

Description copied from interface: KMeansInitialization

Choose initial means

Specified by:

chooseInitialMeans in interface KMeansInitialization

Parameters:

relation - Relation

k - Parameter k

distance - Distance function

Returns:

List of chosen means for k-means

chooseInitialMedoids

public DBIDs chooseInitialMedoids(int k,
                                  DBIDs ids,
                                  DistanceQuery<? super O> distQ)

Description copied from interface: KMedoidsInitialization

Choose initial means

Specified by:

chooseInitialMedoids in interface KMedoidsInitialization<O>

Parameters:

k - Parameter k

ids - Candidate IDs.

distQ - Distance function

Returns:

List of chosen means for k-means

getMinDist

protected static double getMinDist(DBIDArrayIter j,
                                   DistanceQuery<?> distQ,
                                   DBIDArrayIter mi,
                                   WritableDoubleDataStore mindist)

Get the minimum distance to previous medoids.

Parameters:

j - current object

distQ - distance query

mi - medoid iterator

mindist - distance storage

Returns:

minimum distance

shuffle

private static void shuffle(ArrayModifiableDBIDs ids,
                            int ssize,
                            int end,
                            java.util.Random random)

Partial Fisher-Yates shuffle.

Parameters:

ids - IDs to shuffle

ssize - sample size to generate

end - Valid range

random - Random generator