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

public abstract class AbstractKMeansQualityMeasure<O extends NumberVector>
extends java.lang.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.

References:

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
Proc. 17th Int. Conf. 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

Since:

0.7.0

Author:

Tibor Goldschwendt, Erich Schubert

Constructor Summary

Constructors

Constructor and Description
AbstractKMeansQualityMeasure()

Method Summary

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

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",
           title="X-means: Extending K-means with Efficient Estimation on the Number of Clusters",
           booktitle="Proc. 17th Int. Conf. on Machine Learning (ICML 2000)",
           url="http://www.pelleg.org/shared/hp/download/xmeans.ps",
           bibkey="DBLP:conf/icml/PellegM00")
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.

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