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

Class EM<V extends NumberVector<?>>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<EMModel<V>>>

de.lmu.ifi.dbs.elki.algorithm.clustering.EM<V>

Type Parameters:

V - a type of NumberVector as a suitable datatype for this algorithm

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<EMModel<V>>>, Parameterizable

@Title(value="EM-Clustering: Clustering by Expectation Maximization")
@Description(value="Provides k Gaussian mixtures maximizing the probability of the given data")
@Reference(authors="A. P. Dempster, N. M. Laird, D. B. Rubin",
           title="Maximum Likelihood from Incomplete Data via the EM algorithm",
           booktitle="Journal of the Royal Statistical Society, Series B, 39(1), 1977, pp. 1-31",
           url="http://www.jstor.org/stable/2984875")
public class EM<V extends NumberVector<?>>
extends AbstractAlgorithm<Clustering<EMModel<V>>>
implements ClusteringAlgorithm<Clustering<EMModel<V>>>

Provides the EM algorithm (clustering by expectation maximization).

Initialization is implemented as random initialization of means (uniformly distributed within the attribute ranges of the given database) and initial zero-covariance and variance=1 in covariance matrices.

Reference: A. P. Dempster, N. M. Laird, D. B. Rubin:
Maximum Likelihood from Incomplete Data via the EM algorithm.
In Journal of the Royal Statistical Society, Series B, 39(1), 1977, pp. 1-31

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	EM.Parameterizer<V extends NumberVector<?>> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private double	delta Delta parameter
private KMeansInitialization<V>	initializer Class to choose the initial means
private int	k Number of clusters
private static Logging	LOG The logger for this class.
private int	maxiter Maximum number of iterations to allow
private static double	MIN_LOGLIKELIHOOD
private static double	SINGULARITY_CHEAT Small value to increment diagonally of a matrix in order to avoid singularity before building the inverse.
private boolean	soft Retain soft assignments.
static SimpleTypeInformation<double[]>	SOFT_TYPE Soft assignment result type.

Constructor Summary

Constructors

Constructor and Description
EM(int k, double delta, KMeansInitialization<V> initializer, int maxiter, boolean soft) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
static double	assignProbabilitiesToInstances(Relation<? extends NumberVector<?>> relation, double[] normDistrFactor, Vector[] means, Matrix[] invCovMatr, double[] clusterWeights, WritableDataStore<double[]> probClusterIGivenX) Assigns the current probability values to the instances in the database and compute the expectation value of the current mixture of distributions.
static void	computeInverseMatrixes(Matrix[] covarianceMatrices, Matrix[] invCovMatr, double[] normDistrFactor, double norm) Compute the inverse cluster matrices.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
boolean	isSoft()
static void	recomputeCovarianceMatrices(Relation<? extends NumberVector<?>> relation, WritableDataStore<double[]> probClusterIGivenX, Vector[] means, Matrix[] covarianceMatrices, int dimensionality) Recompute the covariance matrixes.
Clustering<EMModel<V>>	run(Database database, Relation<V> relation) Performs the EM clustering algorithm on the given database.
void	setSoft(boolean soft)

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

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

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

SINGULARITY_CHEAT

private static final double SINGULARITY_CHEAT

Small value to increment diagonally of a matrix in order to avoid singularity before building the inverse.

See Also:

Constant Field Values

k

private int k

Number of clusters

delta

private double delta

Delta parameter

initializer

private KMeansInitialization<V extends NumberVector<?>> initializer

Class to choose the initial means

maxiter

private int maxiter

Maximum number of iterations to allow

soft

private boolean soft

Retain soft assignments.

MIN_LOGLIKELIHOOD

private static final double MIN_LOGLIKELIHOOD

See Also:

Constant Field Values

SOFT_TYPE

public static final SimpleTypeInformation<double[]> SOFT_TYPE

Soft assignment result type.

Constructor Detail

EM

public EM(int k,
  double delta,
  KMeansInitialization<V> initializer,
  int maxiter,
  boolean soft)

Constructor.

Parameters:

k - k parameter

delta - delta parameter

initializer - Class to choose the initial means

maxiter - Maximum number of iterations

soft - Include soft assignments

Method Detail

run

public Clustering<EMModel<V>> run(Database database,
                         Relation<V> relation)

Performs the EM clustering algorithm on the given database.

Finally a hard clustering is provided where each clusters gets assigned the points exhibiting the highest probability to belong to this cluster. But still, the database objects hold associated the complete probability-vector for all models.

Parameters:

database - Database

relation - Relation

Returns:

Result

computeInverseMatrixes

public static void computeInverseMatrixes(Matrix[] covarianceMatrices,
                          Matrix[] invCovMatr,
                          double[] normDistrFactor,
                          double norm)

Compute the inverse cluster matrices.

Parameters:

covarianceMatrices - Input covariance matrices

invCovMatr - Output array for inverse matrices

normDistrFactor - Output array for norm distribution factors.

norm - Normalization factor, usually (2pi)^d

recomputeCovarianceMatrices

public static void recomputeCovarianceMatrices(Relation<? extends NumberVector<?>> relation,
                               WritableDataStore<double[]> probClusterIGivenX,
                               Vector[] means,
                               Matrix[] covarianceMatrices,
                               int dimensionality)

Recompute the covariance matrixes.

Parameters:

relation - Vector data

probClusterIGivenX - Object probabilities

means - Cluster means output

covarianceMatrices - Output covariance matrixes

dimensionality - Data set dimensionality

assignProbabilitiesToInstances

public static double assignProbabilitiesToInstances(Relation<? extends NumberVector<?>> relation,
                                    double[] normDistrFactor,
                                    Vector[] means,
                                    Matrix[] invCovMatr,
                                    double[] clusterWeights,
                                    WritableDataStore<double[]> probClusterIGivenX)

Assigns the current probability values to the instances in the database and compute the expectation value of the current mixture of distributions. Computed as the sum of the logarithms of the prior probability of each instance.

Parameters:

relation - the database used for assignment to instances

normDistrFactor - normalization factor for density function, based on current covariance matrix

means - the current means

invCovMatr - the inverse covariance matrices

clusterWeights - the weights of the current clusters

Returns:

the expectation value of the current mixture of distributions

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Clustering<EMModel<V extends NumberVector<?>>>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Clustering<EMModel<V extends NumberVector<?>>>>

Returns:

the static logger

isSoft

public boolean isSoft()

Returns:

the soft

setSoft

public void setSoft(boolean soft)

Parameters:

soft - the soft to set