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

Class AbstractKMeansQualityMeasure<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.AbstractKMeansQualityMeasure<O>

All Implemented Interfaces:

KMeansQualityMeasure<O>

Direct Known Subclasses:

AkaikeInformationCriterion, BayesianInformationCriterion, BayesianInformationCriterionZhao, WithinClusterVarianceQualityMeasure

@Reference(authors="D. Pelleg, A. Moore",
           booktitle="X-means: Extending K-means with Efficient Estimation on the Number of Clusters",
           title="Proceedings of the 17th International Conference on Machine Learning (ICML 2000)",
           url="http://www.pelleg.org/shared/hp/download/xmeans.ps")
public abstract class AbstractKMeansQualityMeasure<O extends NumberVector>
extends Object
implements KMeansQualityMeasure<O>

Base class for evaluating clusterings by information criteria (such as AIC or BIC). Provides helper functions (e.g. max likelihood calculation) to its subclasses. The use of information-theoretic criteria for evaluating k-means was popularized by X-means:

D. Pelleg, A. Moore:
X-means: Extending K-means with Efficient Estimation on the Number of Clusters
In: Proceedings of the 17th International Conference on Machine Learning (ICML 2000)

A different version of logLikelihood is derived in:

Q. Zhao, M. Xu, P. Fränti:
Knee Point Detection on Bayesian Information Criterion
20th IEEE International Conference on Tools with Artificial Intelligence

Author:

Tibor Goldschwendt, Erich Schubert

Constructor Summary

Constructors

Constructor and Description
AbstractKMeansQualityMeasure()

Method Summary

Methods

Modifier and Type	Method and Description
static <V extends NumberVector> double	logLikelihood(Relation<V> relation, Clustering<? extends MeanModel> clustering, NumberVectorDistanceFunction<? super V> distanceFunction) Computes log likelihood of an entire clustering.
static <V extends NumberVector> double	logLikelihoodAlternate(Relation<V> relation, Clustering<? extends MeanModel> clustering, NumberVectorDistanceFunction<? super V> distanceFunction) Computes log likelihood of an entire clustering.
static int	numberOfFreeParameters(Relation<? extends NumberVector> relation, Clustering<? extends MeanModel> clustering) Compute the number of free parameters.
static int	numPoints(Clustering<? extends MeanModel> clustering) Compute the number of points in a given set of clusters (which may be less than the complete data set for X-means!)
static <V extends NumberVector> double	varianceOfCluster(Cluster<? extends MeanModel> cluster, NumberVectorDistanceFunction<? super V> distanceFunction, Relation<V> relation) Variance contribution of a single cluster.

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.KMeansQualityMeasure

ascending, isBetter, quality

Constructor Detail

AbstractKMeansQualityMeasure

public AbstractKMeansQualityMeasure()

Method Detail

numPoints

public static int numPoints(Clustering<? extends MeanModel> clustering)

Compute the number of points in a given set of clusters (which may be less than the complete data set for X-means!)

Parameters:

clustering - Clustering to analyze

Returns:

Number of points

varianceOfCluster

public static <V extends NumberVector> double varianceOfCluster(Cluster<? extends MeanModel> cluster,
                                                NumberVectorDistanceFunction<? super V> distanceFunction,
                                                Relation<V> relation)

Variance contribution of a single cluster. If possible, this information is reused from the clustering process (when a KMeansModel is returned).

Type Parameters:

V - Vector type

Parameters:

cluster - Cluster to access

distanceFunction - Distance function

relation - Data relation

Returns:

Cluster variance

logLikelihood

@Reference(authors="D. Pelleg, A. Moore",
           booktitle="X-means: Extending K-means with Efficient Estimation on the Number of Clusters",
           title="Proceedings of the 17th International Conference on Machine Learning (ICML 2000)",
           url="http://www.pelleg.org/shared/hp/download/xmeans.ps")
public static <V extends NumberVector> double logLikelihood(Relation<V> relation,
                                                                              Clustering<? extends MeanModel> clustering,
                                                                              NumberVectorDistanceFunction<? super V> distanceFunction)

Computes log likelihood of an entire clustering. Version as used in the X-means publication.

Type Parameters:

V - Vector type

Parameters:

relation - Data relation

clustering - Clustering

distanceFunction - Distance function

Returns:

Log Likelihood.

logLikelihoodAlternate

@Reference(authors="Q. Zhao, M. Xu, P. Fra\u0308nti",
           title="Knee Point Detection on Bayesian Information Criterion",
           booktitle="20th IEEE International Conference on Tools with Artificial Intelligence",
           url="http://dx.doi.org/10.1109/ICTAI.2008.154")
public static <V extends NumberVector> double logLikelihoodAlternate(Relation<V> relation,
                                                                                       Clustering<? extends MeanModel> clustering,
                                                                                       NumberVectorDistanceFunction<? super V> distanceFunction)

Computes log likelihood of an entire clustering. Version as used by Zhao et al.

Type Parameters:

V - Vector type

Parameters:

relation - Data relation

clustering - Clustering

distanceFunction - Distance function

Returns:

Log Likelihood.

numberOfFreeParameters

public static int numberOfFreeParameters(Relation<? extends NumberVector> relation,
                         Clustering<? extends MeanModel> clustering)

Compute the number of free parameters.

Parameters:

relation - Data relation (for dimensionality)

clustering - Set of clusters

Returns:

Number of free parameters