package jsat.clustering;
import static java.lang.Math.log;
import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.DataPoint;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import jsat.distributions.multivariate.MultivariateDistribution;
import jsat.distributions.multivariate.NormalM;
import jsat.linear.*;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* An implementation of Gaussian Mixture models that learns the specified number of Gaussians using Expectation Maximization algorithm.
*
* @author Edward Raff
*/
public class EMGaussianMixture implements KClusterer, MultivariateDistribution
{
private SeedSelection seedSelection;
private static final long serialVersionUID = 2606159815670221662L;
private List gaussians;
/**
* The coefficients for the gaussians
*/
private double[] a_k;
private double tolerance = 1e-3;
/**
* Control the maximum number of iterations to perform.
*/
protected int MaxIterLimit = Integer.MAX_VALUE;
public EMGaussianMixture(SeedSelection seedSelection)
{
setSeedSelection(seedSelection);
}
public EMGaussianMixture()
{
this(SeedSelection.KPP);
}
/**
* Sets the method of seed selection to use for this algorithm.
* {@link SeedSelection#KPP} is recommended for this algorithm in
* particular.
*
* @param seedSelection the method of seed selection to use
*/
public void setSeedSelection(SeedSelectionMethods.SeedSelection seedSelection)
{
this.seedSelection = seedSelection;
}
/**
*
* @return the method of seed selection used
*/
public SeedSelectionMethods.SeedSelection getSeedSelection()
{
return seedSelection;
}
/**
* Sets the maximum number of iterations allowed
* @param iterLimit the maximum number of iterations of the ElkanKMeans algorithm
*/
public void setIterationLimit(int iterLimit)
{
if(iterLimit < 1)
throw new IllegalArgumentException("Iterations must be a positive value, not " + iterLimit);
this.MaxIterLimit = iterLimit;
}
/**
* Returns the maximum number of iterations of the ElkanKMeans algorithm that will be performed.
* @return the maximum number of iterations of the ElkanKMeans algorithm that will be performed.
*/
public int getIterationLimit()
{
return MaxIterLimit;
}
/**
* Copy constructor. The new Gaussian Mixture can be altered without effecting gm
* @param gm the Guassian Mixture to duplicate
*/
public EMGaussianMixture(EMGaussianMixture gm)
{
if(gm.gaussians != null && !gm.gaussians.isEmpty())
{
this.gaussians = new ArrayList<>(gm.gaussians.size());
for(NormalM gaussian : gm.gaussians)
this.gaussians.add(gaussian.clone());
}
if(gm.a_k != null)
this.a_k = Arrays.copyOf(gm.a_k, gm.a_k.length);
this.MaxIterLimit = gm.MaxIterLimit;
this.tolerance = gm.tolerance;
}
/**
* Copy constructor
* @param gaussians value to copy
* @param a_k value to copy
* @param tolerance value to copy
*/
@SuppressWarnings("unused")
private EMGaussianMixture(List gaussians, double[] a_k, double tolerance)
{
this.gaussians = new ArrayList(a_k.length);
this.a_k = new double[a_k.length];
for (int i = 0; i < a_k.length; i++)
{
this.gaussians.add(gaussians.get(i).clone());
this.a_k[i] = a_k[i];
}
}
protected double cluster(final DataSet dataSet, final List accelCache, final int K, final List means, final int[] assignment, boolean exactTotal, boolean parallel, boolean returnError)
{
EuclideanDistance dm = new EuclideanDistance();
List> means_qi = new ArrayList<>();
//Pick some initial centers
if(means.size() < K)
{
means.clear();
means.addAll(SeedSelectionMethods.selectIntialPoints(dataSet, K, dm, accelCache, RandomUtil.getRandom(), seedSelection, parallel));
for(Vec v : means)
means_qi.add(dm.getQueryInfo(v));
}
//Use the initial result to initalize GuassianMixture
List covariances = new ArrayList<>(K);
int dimension = dataSet.getNumNumericalVars();
for(int k = 0; k < means.size(); k++)
covariances.add(new DenseMatrix(dimension, dimension));
a_k = new double[K];
double sum = dataSet.getSampleSize();
//Compute inital Covariances
Vec scratch = new DenseVector(dimension);
List X = dataSet.getDataVectors();
for(int i = 0; i < dataSet.getSampleSize(); i++)
{
Vec x = dataSet.getDataPoint(i).getNumericalValues();
//find out which this belongs to
double closest = dm.dist(i, means.get(0), means_qi.get(0), X, accelCache);
int k = 0;
for(int j = 1; j < K; j++)//TODO move out and make parallel
{
double d_ij = dm.dist(i, means.get(j), means_qi.get(j), X, accelCache);
if(d_ij < closest)
{
closest = d_ij;
k = j;
}
}
assignment[i] = k;
a_k[k]++;
x.copyTo(scratch);
scratch.mutableSubtract(means.get(k));
Matrix.OuterProductUpdate(covariances.get(k), scratch, scratch, 1.0);
}
for(int k = 0; k < means.size(); k++)
{
covariances.get(k).mutableMultiply(1.0 / a_k[k]);
a_k[k] /= sum;
}
return clusterCompute(K, dataSet, assignment, means, covariances, parallel);
}
protected double clusterCompute(int K, DataSet dataSet, int[] assignment, List means, List covs, boolean parallel)
{
List dataPoints = dataSet.getDataPoints();
int N = dataPoints.size();
double currentLogLike = -Double.MAX_VALUE;
gaussians = new ArrayList<>(K);
//Set up initial covariance matrices
for(int k = 0; k < means.size(); k++)
gaussians.add(new NormalM(means.get(k), covs.get(k)));
double[][] p_ik = new double[dataPoints.size()][K];
while(true)
{
try
{
//E-Step:
double logLike = eStep(N, dataPoints, K, p_ik, parallel);
//Convergence check!
double logDifference = Math.abs(currentLogLike - logLike);
if(logDifference < tolerance)
break;//We accept this as converged. Probablities could be refined, but no one should be changing class anymore
else
currentLogLike = logLike;
mStep(means, N, dataPoints, K, p_ik, covs, parallel);
}
catch (ExecutionException | InterruptedException ex)
{
Logger.getLogger(EMGaussianMixture.class.getName()).log(Level.SEVERE, null, ex);
}
}
//Hard asignments based on most probable outcome
for(int i = 0; i < p_ik.length; i++)
for(int k = 0; k < K; k++)
if(p_ik[i][k] > p_ik[i][assignment[i]])
assignment[i] = k;
return -currentLogLike;
}
private void mStep(final List means,final int N,final List dataPoints, final int K, final double[][] p_ik, final List covs, final boolean parallel) throws InterruptedException
{
/**
* Dimensions
*/
final int D = means.get(0).length();
//M-Step
/**
* n
* =====
* \
* > p
* / i k
* =====
* p + 1 i = 1
* a = ----------
* k n
*/
//Recompute a_k and update means in the same loop
for(Vec mean : means)
mean.zeroOut();
Arrays.fill(a_k, 0.0);
ThreadLocal localMean = ThreadLocal.withInitial(()->new DenseVector(dataPoints.get(0).numNumericalValues()));
ParallelUtils.run(parallel, N, (start, end)->
{
//doing k loop first so that I only need one local tmp vector for each thread
for(int k = 0; k < K; k++)
{
//local copies
Vec mean_k_l = localMean.get();
mean_k_l.zeroOut();
double a_k_l = 0;
for(int i = start; i < end; i++)
{
Vec x_i = dataPoints.get(i).getNumericalValues();
a_k_l += p_ik[i][k];
mean_k_l.mutableAdd(p_ik[i][k], x_i);
}
//store updates in globals
synchronized(means.get(k))
{
means.get(k).mutableAdd(mean_k_l);
a_k[k] += a_k_l;
}
}
});
//We can now dived all the means by their sums, which are stored in a_k, and then normalized a_k after
for(int k = 0; k < a_k.length; k++)
means.get(k).mutableDivide(a_k[k]);
//We hold off on nomralized a_k, becase we will use its values to update the covariances
for(Matrix cov : covs)
cov.zeroOut();
ParallelUtils.run(parallel, N, (start, end)->
{
Vec scratch = new DenseVector(means.get(0).length());
Matrix cov_local = covs.get(0).clone();
for(int k = 0; k < K; k++)
{
final Vec mean = means.get(k);
scratch.zeroOut();
cov_local.zeroOut();
for(int i = start; i < end; i++)
{
DataPoint dp = dataPoints.get(i);
Vec x = dp.getNumericalValues();
x.copyTo(scratch);
scratch.mutableSubtract(mean);
Matrix.OuterProductUpdate(cov_local, scratch, scratch, p_ik[i][k]);
}
synchronized(covs.get(k))
{
covs.get(k).mutableAdd(cov_local);
}
}
});
//clean up covs
for(int k = 0; k < K; k++)
covs.get(k).mutableMultiply(1.0 / (a_k[k]));
//Finaly, normalize the coefficents
for(int k = 0; k < K; k++)
a_k[k] /= N;
//And update the Normals
for(int k = 0; k < means.size(); k++)
gaussians.get(k).setMeanCovariance(means.get(k), covs.get(k));
}
private double eStep(final int N, final List dataPoints, final int K, final double[][] p_ik, final boolean parallel) throws InterruptedException, ExecutionException
{
double logLike = 0;
/*
* p / | p p\
* a P|x | mean , Sigma |
* k \ i | k k/
* p = ------------------------------
* i k K
* =====
* \ p / | p p\
* > a P|x | mean , Sigma |
* / k \ i | k k/
* =====
* k = 1
*/
/*
* We will piggy back off the E step to compute the log likelyhood
*
* N / K \
* ===== |===== |
* \ |\ |
* L(x, Theat) = > log| > a P/x | mean , Sigma \|
* / |/ k \ i | k k/|
* ===== |===== |
* i = 1 \k = 1 /
*/
logLike = ParallelUtils.run(parallel, N, (start, end)->
{
double logLikeLocal = 0;
for(int i = start; i < end; i++)
{
Vec x_i = dataPoints.get(i).getNumericalValues();
double p_ikNormalizer = 0.0;
for(int k = 0; k < K; k++)
{
double tmp = a_k[k] * gaussians.get(k).pdf(x_i);
p_ik[i][k] = tmp;
p_ikNormalizer += tmp;
}
//Normalize previous values
for(int k = 0; k < K; k++)
p_ik[i][k] /= p_ikNormalizer;
//Add to part of the log likelyhood
logLikeLocal += Math.log(p_ikNormalizer);
}
return logLikeLocal;
}, (t,u)->t+u);
return logLike;
}
@Override
public double logPdf(Vec x)
{
double pdf = pdf(x);
if(pdf == 0)
return -Double.MAX_VALUE;
return log(pdf);
}
@Override
public double pdf(Vec x)
{
double PDF = 0.0;
for(int i = 0; i < a_k.length; i++)
PDF += a_k[i] * gaussians.get(i).pdf(x);
return PDF;
}
@Override
public boolean setUsingData(List dataSet, boolean parallel)
{
List dataPoints = new ArrayList<>(dataSet.size());
for(Vec x : dataSet)
dataPoints.add(new DataPoint(x, new int[0], new CategoricalData[0]));
return setUsingData(new SimpleDataSet(dataPoints), parallel);
}
@Override
public boolean setUsingData(DataSet dataSet, boolean parallel)
{
try
{
cluster(dataSet, parallel);
return true;
}
catch (ArithmeticException ex)
{
return false;
}
}
@Override
public EMGaussianMixture clone()
{
return new EMGaussianMixture(this);
}
@Override
public List sample(int count, Random rand)
{
List samples = new ArrayList<>(count);
//First we need the figure out which of the mixtures to sample from
//So generate [0,1] uniform values to determine
double[] priorTargets = new double[count];
for(int i = 0; i < count; i++)
priorTargets[i] = rand.nextDouble();
Arrays.sort(priorTargets);
int subSampleSize = 0;
int currentGaussian = 0;
int pos = 0;
double a_kSum = 0.0;
while(currentGaussian < a_k.length)
{
a_kSum += a_k[currentGaussian];
while(pos < count && priorTargets[pos++] < a_kSum)
subSampleSize++;
samples.addAll(gaussians.get(currentGaussian++).sample(subSampleSize, rand));
}
return samples;
}
@Override
public int[] cluster(DataSet dataSet, int[] designations)
{
return cluster(dataSet, 2, (int)Math.sqrt(dataSet.getSampleSize()/2), designations);
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 2, (int)Math.sqrt(dataSet.getSampleSize()/2), parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int clusters, boolean parallel, int[] designations)
{
if(designations == null)
designations = new int[dataSet.getSampleSize()];
if(dataSet.getSampleSize() < clusters)
throw new ClusterFailureException("Fewer data points then desired clusters, decrease cluster size");
List means = new ArrayList<>(clusters);
cluster(dataSet, null, clusters, means, designations, false, parallel, false);
return designations;
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
throw new UnsupportedOperationException("EMGaussianMixture does not supported determining the number of clusters");
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, int[] designations)
{
throw new UnsupportedOperationException("EMGaussianMixture does not supported determining the number of clusters");
}
}
Ads help maintain this website.