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

Class OstrovskyInitialMeans<O>

java.lang.Object

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

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

Type Parameters:

O - Vector type

All Implemented Interfaces:

KMeansInitialization

@Reference(authors="R. Ostrovsky, Y. Rabani, L. J. Schulman, C. Swamy",title="The effectiveness of Lloyd-type methods for the k-means problem",booktitle="Symposium on Foundations of Computer Science (FOCS)",url="https://doi.org/10.1109/FOCS.2006.75",bibkey="DBLP:conf/focs/OstrovskyRSS062") @Reference(authors="R. Ostrovsky, Y. Rabani, L. J. Schulman, C. Swamy",title="The effectiveness of lloyd-type methods for the k-means problem",booktitle="Journal of the ACM 59(6)",url="https://doi.org/10.1145/2395116.2395117",bibkey="DBLP:journals/jacm/OstrovskyRSS12")
public class OstrovskyInitialMeans<O>
extends AbstractKMeansInitialization

Ostrovsky initial means, a variant of k-means++ that is expected to give slightly better results on average, but only works for k-means and not for, e.g., PAM (k-medoids).

Reference:

R. Ostrovsky, Y. Rabani, L. J. Schulman, C. Swamy
The effectiveness of Lloyd-type methods for the k-means problem.
Symposium on Foundations of Computer Science (FOCS)

R. Ostrovsky, Y. Rabani, L. J. Schulman, C. Swamy
The effectiveness of Lloyd-type methods for the k-means problem.
Journal of the ACM 59(6)

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	OstrovskyInitialMeans.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
OstrovskyInitialMeans(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
protected static <T> double	initialWeights(WritableDoubleDataStore weights, Relation<? extends T> relation, DBIDs ids, T first, T second, DistanceQuery<? super T> distQ) Initialize 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

OstrovskyInitialMeans

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

Parameters:

database - Database context

relation - Relation

k - Parameter k

distanceFunction - Distance function

Returns:

List of chosen means for k-means

initialWeights

protected static <T> double initialWeights(WritableDoubleDataStore weights,
                                           Relation<? extends T> relation,
                                           DBIDs ids,
                                           T first,
                                           T second,
                                           DistanceQuery<? super T> distQ)

Initialize the weight list.

Type Parameters:

T - Object type

Parameters:

weights - Weight list

ids - IDs

relation - Data relation

first - First ID

second - Second ID

distQ - Distance query

Returns:

Weight sum