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

Class KMeansPlusPlusInitialMeans<O>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.KMeansPlusPlusInitialMeans<O>

Type Parameters:

O - Vector type

All Implemented Interfaces:

KMeansInitialization, KMedoidsInitialization<O>

@Reference(authors="D. Arthur, S. Vassilvitskii",
           title="k-means++: the advantages of careful seeding",
           booktitle="Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)",
           url="http://dl.acm.org/citation.cfm?id=1283383.1283494",
           bibkey="DBLP:conf/soda/ArthurV07")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansPlusPlusInitialMeans")
public class KMeansPlusPlusInitialMeans<O>
extends AbstractKMeansInitialization
implements KMedoidsInitialization<O>

K-Means++ initialization for k-means.

Reference:

D. Arthur, S. Vassilvitskii
k-means++: the advantages of careful seeding
Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)

Since:

0.5.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.AbstractKMeansInitialization

rnd

Constructor Summary

Constructors

Constructor and Description
KMeansPlusPlusInitialMeans(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
(package private) static void	chooseRemaining(DBIDs ids, DistanceQuery<?> distQ, int k, ArrayModifiableDBIDs means, WritableDoubleDataStore weights, double weightsum, java.util.Random random) Choose remaining means, weighted by distance.
(package private) static void	chooseRemaining(Relation<? extends NumberVector> relation, DBIDs ids, DistanceQuery<NumberVector> distQ, int k, java.util.List<NumberVector> means, WritableDoubleDataStore weights, double weightsum, java.util.Random random) Choose remaining means, weighted by distance.
(package private) static double	initialWeights(WritableDoubleDataStore weights, DBIDs ids, DBIDRef latest, DistanceQuery<?> distQ) Initialize the weight list.
(package private) static double	initialWeights(WritableDoubleDataStore weights, DBIDs ids, NumberVector first, DistanceQuery<? super NumberVector> distQ) Initialize the weight list.
private static double	updateWeights(WritableDoubleDataStore weights, DBIDs ids, DBIDRef latest, DistanceQuery<?> distQ) Update the weight list.
private static double	updateWeights(WritableDoubleDataStore weights, DBIDs ids, NumberVector latest, DistanceQuery<? super NumberVector> distQ) Update the weight list.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.AbstractKMeansInitialization

unboxVectors

Methods inherited from class java.lang.Object

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

Constructor Detail

KMeansPlusPlusInitialMeans

public KMeansPlusPlusInitialMeans(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

initialWeights

static double initialWeights(WritableDoubleDataStore weights,
                             DBIDs ids,
                             NumberVector first,
                             DistanceQuery<? super NumberVector> distQ)

Initialize the weight list.

Parameters:

weights - Weight list

ids - IDs

first - Added ID

distQ - Distance query

Returns:

Weight sum

initialWeights

static double initialWeights(WritableDoubleDataStore weights,
                             DBIDs ids,
                             DBIDRef latest,
                             DistanceQuery<?> distQ)

Initialize the weight list.

Parameters:

weights - Weight list

ids - IDs

latest - Added ID

distQ - Distance query

Returns:

Weight sum

chooseRemaining

static void chooseRemaining(Relation<? extends NumberVector> relation,
                            DBIDs ids,
                            DistanceQuery<NumberVector> distQ,
                            int k,
                            java.util.List<NumberVector> means,
                            WritableDoubleDataStore weights,
                            double weightsum,
                            java.util.Random random)

Choose remaining means, weighted by distance.

Parameters:

relation - Data relation

ids - IDs

distQ - Distance function

k - Number of means to choose

means - Means storage

weights - Weights (initialized!)

weightsum - Sum of weights

random - Random generator

chooseRemaining

static void chooseRemaining(DBIDs ids,
                            DistanceQuery<?> distQ,
                            int k,
                            ArrayModifiableDBIDs means,
                            WritableDoubleDataStore weights,
                            double weightsum,
                            java.util.Random random)

Choose remaining means, weighted by distance.

Parameters:

ids - IDs

distQ - Distance function

k - Number of means to choose

means - Means storage

weights - Weights (initialized!)

weightsum - Sum of weights

random - Random generator

updateWeights

private static double updateWeights(WritableDoubleDataStore weights,
                                    DBIDs ids,
                                    DBIDRef latest,
                                    DistanceQuery<?> distQ)

Update the weight list.

Parameters:

weights - Weight list

ids - IDs

latest - Added ID

distQ - Distance query

Returns:

Weight sum

updateWeights

private static double updateWeights(WritableDoubleDataStore weights,
                                    DBIDs ids,
                                    NumberVector latest,
                                    DistanceQuery<? super NumberVector> distQ)

Update the weight list.

Parameters:

weights - Weight list

ids - IDs

latest - Added ID

distQ - Distance query

Returns:

Weight sum