Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.algorithm.clustering
Class EM<V extends RealVector<V,?>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<V,Clustering<EMModel<V>>>
              extended by de.lmu.ifi.dbs.elki.algorithm.clustering.EM<V>
Type Parameters:
V - a type of RealVector as a suitable datatype for this algorithm
All Implemented Interfaces:
Algorithm<V,Clustering<EMModel<V>>>, ClusteringAlgorithm<Clustering<EMModel<V>>,V>, Parameterizable

public class EM<V extends RealVector<V,?>>
extends AbstractAlgorithm<V,Clustering<EMModel<V>>>
implements ClusteringAlgorithm<Clustering<EMModel<V>>,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

Author:
Arthur Zimek

Field Summary
private  double delta
          Holds the value of DELTA_PARAM.
static OptionID DELTA_ID
          OptionID for DELTA_PARAM
private  DoubleParameter DELTA_PARAM
          Parameter to specify the termination criterion for maximization of E(M): E(M) - E(M') < em.delta, must be a double equal to or greater than 0.
private  int k
          Holds the value of K_PARAM.
static OptionID K_ID
          OptionID for K_PARAM
private  IntParameter K_PARAM
          Parameter to specify the number of clusters to find, must be an integer greater than 0.
private static double MIN_LOGLIKELIHOOD
           
private  Clustering<EMModel<V>> result
          Keeps the result.
private static double SINGULARITY_CHEAT
          Small value to increment diagonally of a matrix in order to avoid singularity before building the inverse.
 
Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
optionHandler
 
Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debug, logger
 
Constructor Summary
EM()
          Provides the EM algorithm (clustering by expectation maximization), adding parameters K_PARAM and DELTA_PARAM to the option handler additionally to parameters of super class.
 
Method Summary
protected  void assignProbabilitiesToInstances(Database<V> database, List<Double> normDistrFactor, List<V> means, List<Matrix> invCovMatr, List<Double> clusterWeights)
          Assigns the current probability values to the instances in the database.
protected  double expectationOfMixture(Database<V> database)
          The expectation value of the current mixture of distributions.
 Description getDescription()
          Returns a description of the algorithm.
 Clustering<EMModel<V>> getResult()
          Retrieve the result.
protected  List<V> initialMeans(Database<V> database)
          Creates k random points distributed uniformly within the attribute ranges of the given database.
protected  Clustering<EMModel<V>> runInTime(Database<V> database)
          Performs the EM clustering algorithm on the given database.
 List<String> setParameters(List<String> args)
          Calls the super method and sets additionally the values of the parameters K_PARAM and DELTA_PARAM.
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm
isTime, isVerbose, run, setTime, setVerbose
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, verbose, warning
 
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
 
Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.Algorithm
setTime, setVerbose
 
Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription
 

Field Detail

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_ID

public static final OptionID K_ID
OptionID for K_PARAM


K_PARAM

private final IntParameter K_PARAM
Parameter to specify the number of clusters to find, must be an integer greater than 0.

Key: -em.k


k

private int k
Holds the value of K_PARAM.


DELTA_ID

public static final OptionID DELTA_ID
OptionID for DELTA_PARAM


MIN_LOGLIKELIHOOD

private static final double MIN_LOGLIKELIHOOD
See Also:
Constant Field Values

DELTA_PARAM

private final DoubleParameter DELTA_PARAM
Parameter to specify the termination criterion for maximization of E(M): E(M) - E(M') < em.delta, must be a double equal to or greater than 0.

Default value: 0.0

Key: -em.delta


delta

private double delta
Holds the value of DELTA_PARAM.


result

private Clustering<EMModel<V extends RealVector<V,?>>> result
Keeps the result.

Constructor Detail

EM

public EM()
Provides the EM algorithm (clustering by expectation maximization), adding parameters K_PARAM and DELTA_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected Clustering<EMModel<V>> runInTime(Database<V> database)
                                                            throws IllegalStateException
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.

Specified by:
runInTime in class AbstractAlgorithm<V extends RealVector<V,?>,Clustering<EMModel<V extends RealVector<V,?>>>>
Parameters:
database - the database to run the algorithm on
Returns:
the Result computed by this algorithm
Throws:
IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

assignProbabilitiesToInstances

protected void assignProbabilitiesToInstances(Database<V> database,
                                              List<Double> normDistrFactor,
                                              List<V> means,
                                              List<Matrix> invCovMatr,
                                              List<Double> clusterWeights)
Assigns the current probability values to the instances in the database.

Parameters:
database - 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

expectationOfMixture

protected double expectationOfMixture(Database<V> database)
The expectation value of the current mixture of distributions.

Computed as the sum of the logarithms of the prior probability of each instance.

Parameters:
database - the database where the prior probability of each instance is associated
Returns:
the expectation value of the current mixture of distributions

initialMeans

protected List<V> initialMeans(Database<V> database)
Creates k random points distributed uniformly within the attribute ranges of the given database.

Parameters:
database - the database must contain enough points in order to ascertain the range of attribute values. Less than two points would make no sense. The content of the database is not touched otherwise.
Returns:
a list of k random points distributed uniformly within the attribute ranges of the given database

getDescription

public Description getDescription()
Description copied from interface: Algorithm
Returns a description of the algorithm.

Specified by:
getDescription in interface Algorithm<V extends RealVector<V,?>,Clustering<EMModel<V extends RealVector<V,?>>>>
Returns:
a description of the algorithm

getResult

public Clustering<EMModel<V>> getResult()
Description copied from interface: ClusteringAlgorithm
Retrieve the result.

Specified by:
getResult in interface Algorithm<V extends RealVector<V,?>,Clustering<EMModel<V extends RealVector<V,?>>>>
Specified by:
getResult in interface ClusteringAlgorithm<Clustering<EMModel<V extends RealVector<V,?>>>,V extends RealVector<V,?>>
Returns:
the result of the algorithm

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException
Calls the super method and sets additionally the values of the parameters K_PARAM and DELTA_PARAM.

Specified by:
setParameters in interface Parameterizable
Overrides:
setParameters in class AbstractAlgorithm<V extends RealVector<V,?>,Clustering<EMModel<V extends RealVector<V,?>>>>
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

Release 0.2.1 (2009-07-13_1605)