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

Class EM<V extends NumberVector,M extends MeanModel>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<Clustering<M>>

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

Type Parameters:

V - vector type to analyze

M - model type to produce

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<M>>

@Title(value="EM-Clustering: Clustering by Expectation Maximization")
 @Description(value="Cluster data via Gaussian mixture modeling and the EM algorithm")
 @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)",url="http://www.jstor.org/stable/2984875",bibkey="journals/jroyastatsocise2/DempsterLR77") @Reference(title="Bayesian Regularization for Normal Mixture Estimation and Model-Based Clustering",authors="C. Fraley, A. E. Raftery",booktitle="J. Classification 24(2)",url="https://doi.org/10.1007/s00357-007-0004-5",bibkey="DBLP:journals/classification/FraleyR07")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.clustering.EM")
 @Priority(value=200)
public class EM<V extends NumberVector,M extends MeanModel>
extends AbstractAlgorithm<Clustering<M>>
implements ClusteringAlgorithm<Clustering<M>>

Clustering by expectation maximization (EM-Algorithm), also known as Gaussian Mixture Modeling (GMM), with optional MAP regularization.

Reference:

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

The MAP estimation is derived from

C. Fraley and A. E. Raftery
Bayesian Regularization for Normal Mixture Estimation and Model-Based Clustering
J. Classification 24(2)

Since:

0.1

Author:

Arthur Zimek, Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
private double	delta Delta parameter
private int	k Number of clusters
private static java.lang.String	KEY Key for statistics logging.
private static Logging	LOG The logger for this class.
private int	maxiter Maximum number of iterations to allow
private EMClusterModelFactory<V,M>	mfactory Factory for producing the initial cluster model.
private static double	MIN_LOGLIKELIHOOD Minimum loglikelihood to avoid -infinity.
private double	prior Prior to enable MAP estimation (use 0 for MLE)
private boolean	soft Retain soft assignments.
static SimpleTypeInformation<double[]>	SOFT_TYPE Soft assignment result type.

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

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
EM(int k, double delta, EMClusterModelFactory<V,M> mfactory) Constructor.
EM(int k, double delta, EMClusterModelFactory<V,M> mfactory, int maxiter, boolean soft) Constructor.
EM(int k, double delta, EMClusterModelFactory<V,M> mfactory, int maxiter, double prior, boolean soft) Constructor.

Method Summary

Modifier and Type	Method and Description
static double	assignProbabilitiesToInstances(Relation<? extends NumberVector> relation, java.util.List<? extends EMClusterModel<?>> models, 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.
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()
private static double	logSumExp(double[] x) Compute log(sum(exp(x_i)), with attention to numerical issues.
static void	recomputeCovarianceMatrices(Relation<? extends NumberVector> relation, WritableDataStore<double[]> probClusterIGivenX, java.util.List<? extends EMClusterModel<?>> models, double prior) Recompute the covariance matrixes.
Clustering<M>	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

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.

KEY

private static final java.lang.String KEY

Key for statistics logging.

k

private int k

Number of clusters

delta

private double delta

Delta parameter

mfactory

private EMClusterModelFactory<V extends NumberVector,M extends MeanModel> mfactory

Factory for producing the initial cluster model.

maxiter

private int maxiter

Maximum number of iterations to allow

prior

private double prior

Prior to enable MAP estimation (use 0 for MLE)

soft

private boolean soft

Retain soft assignments.

MIN_LOGLIKELIHOOD

private static final double MIN_LOGLIKELIHOOD

Minimum loglikelihood to avoid -infinity.

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,
          EMClusterModelFactory<V,M> mfactory)

Constructor.

Parameters:

k - k parameter

delta - delta parameter

mfactory - EM cluster model factory

EM

public EM(int k,
          double delta,
          EMClusterModelFactory<V,M> mfactory,
          int maxiter,
          boolean soft)

Constructor.

Parameters:

k - k parameter

delta - delta parameter

mfactory - EM cluster model factory

maxiter - Maximum number of iterations

soft - Include soft assignments

EM

public EM(int k,
          double delta,
          EMClusterModelFactory<V,M> mfactory,
          int maxiter,
          double prior,
          boolean soft)

Constructor.

Parameters:

k - k parameter

delta - delta parameter

mfactory - EM cluster model factory

maxiter - Maximum number of iterations

prior - MAP prior

soft - Include soft assignments

Method Detail

run

public Clustering<M> 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

recomputeCovarianceMatrices

public static void recomputeCovarianceMatrices(Relation<? extends NumberVector> relation,
                                               WritableDataStore<double[]> probClusterIGivenX,
                                               java.util.List<? extends EMClusterModel<?>> models,
                                               double prior)

Recompute the covariance matrixes.

Parameters:

relation - Vector data

probClusterIGivenX - Object probabilities

models - Cluster models to update

prior - MAP prior (use 0 for MLE)

assignProbabilitiesToInstances

public static double assignProbabilitiesToInstances(Relation<? extends NumberVector> relation,
                                                    java.util.List<? extends EMClusterModel<?>> models,
                                                    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

models - Cluster models

probClusterIGivenX - Output storage for cluster probabilities

Returns:

the expectation value of the current mixture of distributions

logSumExp

private static double logSumExp(double[] x)

Compute log(sum(exp(x_i)), with attention to numerical issues.

Parameters:

x - Input

Returns:

Result

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<M extends MeanModel>>

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<M extends MeanModel>>

Returns:

the static logger

isSoft

public boolean isSoft()

Returns:

the soft

setSoft

public void setSoft(boolean soft)

Parameters:

soft - the soft to set