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

Class LABInitialMeans<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.LABInitialMeans<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="preprint, to appear",
           url="https://arxiv.org/abs/1810.05691",
           bibkey="DBLP:journals/corr/abs-1810-05691")
public class LABInitialMeans<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
preprint, to appear

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
LABInitialMeans(RandomFactory rnd) Constructor.

Method Summary

Modifier and Type	Method and Description
double[][]	chooseInitialMeans(Database database, Relation<? extends NumberVector> relation, int k, NumberVectorDistanceFunction<?> distanceFunction) 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

LABInitialMeans

public LABInitialMeans(RandomFactory rnd)

Constructor.

Parameters:

rnd - Random generator

Method Detail

chooseInitialMeans

public double[][] chooseInitialMeans(Database database,
                                     Relation<? extends NumberVector> relation,
                                     int k,
                                     NumberVectorDistanceFunction<?> distanceFunction)

Description copied from interface: KMeansInitialization

Choose initial means

Specified by:

chooseInitialMeans in interface KMeansInitialization

Parameters:

database - Database context

relation - Relation

k - Parameter k

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