weka.clusterers
Class EM

java.lang.Object
  weka.clusterers.Clusterer
      weka.clusterers.DensityBasedClusterer
          weka.clusterers.EM

All Implemented Interfaces:

java.lang.Cloneable, OptionHandler, java.io.Serializable, WeightedInstancesHandler

public class EM

extends DensityBasedClusterer

implements OptionHandler, WeightedInstancesHandler

Simple EM (expectation maximisation) class.

EM assigns a probability distribution to each instance which indicates the probability of it belonging to each of the clusters. EM can decide how many clusters to create by cross validation, or you may specify apriori how many clusters to generate.

The cross validation performed to determine the number of clusters is done in the following steps:
1. the number of clusters is set to 1
2. the training set is split randomly into 10 folds.
3. EM is performed 10 times using the 10 folds the usual CV way.
4. the loglikelihood is averaged over all 10 results.
5. if loglikelihood has increased the number of clusters is increased by 1 and the program continues at step 2.

The number of folds is fixed to 10, as long as the number of instances in the training set is not smaller 10. If this is the case the number of folds is set equal to the number of instances.

Valid options are:

-V
Verbose.

-N
Specify the number of clusters to generate. If omitted, EM will use cross validation to select the number of clusters automatically.

-I
Terminate after this many iterations if EM has not converged.

-S
Specify random number seed.

-M
Set the minimum allowable standard deviation for normal density calculation.

Version:

$Revision: 1.25 $

Author:

Mark Hall (mhall@cs.waikato.ac.nz), Eibe Frank (eibe@cs.waikato.ac.nz)

See Also:

Serialized Form

Field Summary

private int	m_initialNumClusters the initial number of clusters requested by the user--- -1 if xval is to be used to find the number of clusters
private double	m_loglikely the loglikelihood of the data
private int	m_max_iterations maximum iterations to perform
private double[]	m_maxValues attribute max values
private double	m_minStdDev default minimum standard deviation
private double[]	m_minValues attribute min values
private Estimator[][]	m_model hold the discrete estimators for each cluster
private double[][][]	m_modelNormal hold the normal estimators for each cluster
private static double	m_normConst Constant for normal distribution.
private int	m_num_attribs number of attributes
private int	m_num_clusters number of clusters selected by the user or cross validation
private int	m_num_instances number of training instances
private double[]	m_priors the prior probabilities for clusters
private java.util.Random	m_rr random numbers and seed
private int	m_rseed
private Instances	m_theInstances training instances
private boolean	m_verbose Verbose?
private double[][]	m_weights hold the weights of each instance for each cluster

Constructor Summary

EM()
Constructor.

Method Summary

void	buildClusterer(Instances data) Generates a clusterer.
double[]	clusterPriors() Returns the cluster priors.
private void	CVClusters() estimate the number of clusters by cross validation on the training data.
private void	doEM() Perform the EM algorithm
private double	E(Instances inst, boolean change_weights) The E step of the EM algorithm.
private void	EM_Init(Instances inst) Initialise estimators and storage.
private void	EM_Report(Instances inst) verbose output for debugging
private void	estimate_priors(Instances inst) calculate prior probabilites for the clusters
double[][][]	getClusterModelsNumericAtts() Return the normal distributions for the cluster models
double[]	getClusterPriors() Return the priors for the clusters
boolean	getDebug() Get debug mode
int	getMaxIterations() Get the maximum number of iterations
double	getMinStdDev() Get the minimum allowable standard deviation.
int	getNumClusters() Get the number of clusters
java.lang.String[]	getOptions() Gets the current settings of EM.
int	getSeed() Get the random number seed
java.lang.String	globalInfo() Returns a string describing this clusterer
private double	iterate(Instances inst, boolean report) iterates the E and M steps until the log likelihood of the data converges.
java.util.Enumeration	listOptions() Returns an enumeration describing the available options..
double[]	logDensityPerClusterForInstance(Instance inst) Computes the log of the conditional density (per cluster) for a given instance.
private double	logNormalDens(double x, double mean, double stdDev) Density function of normal distribution.
private void	M(Instances inst) The M step of the EM algorithm.
static void	main(java.lang.String[] argv) Main method for testing this class.
java.lang.String	maxIterationsTipText() Returns the tip text for this property
java.lang.String	minStdDevTipText() Returns the tip text for this property
private void	new_estimators() New probability estimators for an iteration
int	numberOfClusters() Returns the number of clusters.
java.lang.String	numClustersTipText() Returns the tip text for this property
protected void	resetOptions() Reset to default options
java.lang.String	seedTipText() Returns the tip text for this property
void	setDebug(boolean v) Set debug mode - verbose output
void	setMaxIterations(int i) Set the maximum number of iterations to perform
void	setMinStdDev(double m) Set the minimum value for standard deviation when calculating normal density.
void	setNumClusters(int n) Set the number of clusters (-1 to select by CV).
void	setOptions(java.lang.String[] options) Parses a given list of options.
void	setSeed(int s) Set the random number seed
java.lang.String	toString() Outputs the generated clusters into a string.
private void	updateMinMax(Instance instance) Updates the minimum and maximum values for all the attributes based on a new instance.

Methods inherited from class weka.clusterers.DensityBasedClusterer

distributionForInstance, logDensityForInstance, logJointDensitiesForInstance

Methods inherited from class weka.clusterers.Clusterer

clusterInstance, forName, makeCopies

Methods inherited from class java.lang.Object

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

Field Detail

m_model

private Estimator[][] m_model

hold the discrete estimators for each cluster

m_modelNormal

private double[][][] m_modelNormal

hold the normal estimators for each cluster

m_minStdDev

private double m_minStdDev

default minimum standard deviation

m_weights

private double[][] m_weights

hold the weights of each instance for each cluster

m_priors

private double[] m_priors

the prior probabilities for clusters

m_loglikely

private double m_loglikely

the loglikelihood of the data

m_theInstances

private Instances m_theInstances

training instances

m_num_clusters

private int m_num_clusters

number of clusters selected by the user or cross validation

m_initialNumClusters

private int m_initialNumClusters

the initial number of clusters requested by the user--- -1 if xval is to be used to find the number of clusters

m_num_attribs

private int m_num_attribs

number of attributes

m_num_instances

private int m_num_instances

number of training instances

m_max_iterations

private int m_max_iterations

maximum iterations to perform

m_minValues

private double[] m_minValues

attribute min values

m_maxValues

private double[] m_maxValues

attribute max values

m_rr

private java.util.Random m_rr

random numbers and seed

m_rseed

private int m_rseed

m_verbose

private boolean m_verbose

Verbose?

m_normConst

private static double m_normConst

Constant for normal distribution.

Constructor Detail

EM

public EM()

Constructor.

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing this clusterer

Returns:

a description of the evaluator suitable for displaying in the explorer/experimenter gui

listOptions

public java.util.Enumeration listOptions()

Returns an enumeration describing the available options..

Valid options are:

-V
Verbose.

-N
Specify the number of clusters to generate. If omitted, EM will use cross validation to select the number of clusters automatically.

-I
Terminate after this many iterations if EM has not converged.

-S
Specify random number seed.

-M
Set the minimum allowable standard deviation for normal density calculation.

Specified by:

listOptions in interface OptionHandler

Returns:

an enumeration of all the available options.

setOptions

public void setOptions(java.lang.String[] options)
                throws java.lang.Exception

Parses a given list of options.

Specified by:

setOptions in interface OptionHandler

Parameters:

options - the list of options as an array of strings

Throws:

java.lang.Exception - if an option is not supported

minStdDevTipText

public java.lang.String minStdDevTipText()

Returns the tip text for this property

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setMinStdDev

public void setMinStdDev(double m)

Set the minimum value for standard deviation when calculating normal density. Reducing this value can help prevent arithmetic overflow resulting from multiplying large densities (arising from small standard deviations) when there are many singleton or near singleton values.

Parameters:

m - minimum value for standard deviation

getMinStdDev

public double getMinStdDev()

Get the minimum allowable standard deviation.

Returns:

the minumum allowable standard deviation

seedTipText

public java.lang.String seedTipText()

Returns the tip text for this property

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setSeed

public void setSeed(int s)

Set the random number seed

Parameters:

s - the seed

getSeed

public int getSeed()

Get the random number seed

Returns:

the seed

numClustersTipText

public java.lang.String numClustersTipText()

Returns the tip text for this property

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setNumClusters

public void setNumClusters(int n)
                    throws java.lang.Exception

Set the number of clusters (-1 to select by CV).

Parameters:

n - the number of clusters

Throws:

java.lang.Exception - if n is 0

getNumClusters

public int getNumClusters()

Get the number of clusters

Returns:

the number of clusters.

maxIterationsTipText

public java.lang.String maxIterationsTipText()

Returns the tip text for this property

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

setMaxIterations

public void setMaxIterations(int i)
                      throws java.lang.Exception

Set the maximum number of iterations to perform

Parameters:

i - the number of iterations

Throws:

java.lang.Exception - if i is less than 1

getMaxIterations

public int getMaxIterations()

Get the maximum number of iterations

Returns:

the number of iterations

setDebug

public void setDebug(boolean v)

Set debug mode - verbose output

Parameters:

v - true for verbose output

getDebug

public boolean getDebug()

Get debug mode

Returns:

true if debug mode is set

getOptions

public java.lang.String[] getOptions()

Gets the current settings of EM.

Specified by:

getOptions in interface OptionHandler

Returns:

an array of strings suitable for passing to setOptions()

EM_Init

private void EM_Init(Instances inst)
              throws java.lang.Exception

Initialise estimators and storage.

Parameters:

inst - the instances

Throws:

java.lang.Exception

estimate_priors

private void estimate_priors(Instances inst)
                      throws java.lang.Exception

calculate prior probabilites for the clusters

Parameters:

inst - the instances

Throws:

java.lang.Exception - if priors can't be calculated

logNormalDens

private double logNormalDens(double x,
                             double mean,
                             double stdDev)

Density function of normal distribution.

Parameters:

x - input value

mean - mean of distribution

stdDev - standard deviation of distribution

new_estimators

private void new_estimators()

New probability estimators for an iteration

M

private void M(Instances inst)
        throws java.lang.Exception

The M step of the EM algorithm.

Parameters:

inst - the training instances

Throws:

java.lang.Exception

E

private double E(Instances inst,
                 boolean change_weights)
          throws java.lang.Exception

The E step of the EM algorithm. Estimate cluster membership probabilities.

Parameters:

inst - the training instances

Returns:

the average log likelihood

Throws:

java.lang.Exception

resetOptions

protected void resetOptions()

Reset to default options

getClusterModelsNumericAtts

public double[][][] getClusterModelsNumericAtts()

Return the normal distributions for the cluster models

Returns:

a double[][][] value

getClusterPriors

public double[] getClusterPriors()

Return the priors for the clusters

Returns:

a double[] value

toString

public java.lang.String toString()

Outputs the generated clusters into a string.

EM_Report

private void EM_Report(Instances inst)

verbose output for debugging

Parameters:

inst - the training instances

CVClusters

private void CVClusters()
                 throws java.lang.Exception

estimate the number of clusters by cross validation on the training data.

Throws:

java.lang.Exception

numberOfClusters

public int numberOfClusters()
                     throws java.lang.Exception

Returns the number of clusters.

Specified by:

numberOfClusters in class Clusterer

Returns:

the number of clusters generated for a training dataset.

Throws:

java.lang.Exception - if number of clusters could not be returned successfully

updateMinMax

private void updateMinMax(Instance instance)

Updates the minimum and maximum values for all the attributes based on a new instance.

Parameters:

instance - the new instance

buildClusterer

public void buildClusterer(Instances data)
                    throws java.lang.Exception

Generates a clusterer. Has to initialize all fields of the clusterer that are not being set via options.

Specified by:

buildClusterer in class Clusterer

Parameters:

data - set of instances serving as training data

Throws:

java.lang.Exception - if the clusterer has not been generated successfully

clusterPriors

public double[] clusterPriors()

Returns the cluster priors.

Specified by:

clusterPriors in class DensityBasedClusterer

Returns:

the prior probability for each cluster

logDensityPerClusterForInstance

public double[] logDensityPerClusterForInstance(Instance inst)
                                         throws java.lang.Exception

Computes the log of the conditional density (per cluster) for a given instance.

Specified by:

logDensityPerClusterForInstance in class DensityBasedClusterer

Parameters:

inst - the instance to compute the density for

Returns:

the density.

Throws:

java.lang.Exception - if the density could not be computed successfully

doEM

private void doEM()
           throws java.lang.Exception

Perform the EM algorithm

Throws:

java.lang.Exception

iterate

private double iterate(Instances inst,
                       boolean report)
                throws java.lang.Exception

iterates the E and M steps until the log likelihood of the data converges.

Parameters:

inst - the training instances.

report - be verbose.

Returns:

the log likelihood of the data

Throws:

java.lang.Exception

main

public static void main(java.lang.String[] argv)

Main method for testing this class.

Parameters:

argv - should contain the following arguments:

-t training file [-T test file] [-N number of clusters] [-S random seed]