package jsat.clustering.kmeans;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicBoolean;
import jsat.DataSet;
import jsat.clustering.ClusterFailureException;
import jsat.distributions.kernels.KernelTrick;
import jsat.exceptions.FailedToFitException;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.*;
import jsat.utils.*;
import jsat.utils.concurrent.ParallelUtils;
/**
* An efficient implementation of the K-Means algorithm. This implementation uses
* the triangle inequality to accelerate computation while maintaining the exact
* same solution. This requires that the {@link DistanceMetric} used support
* {@link DistanceMetric#isSubadditive() }.
*
* See: Elkan, C. (2003). Using the Triangle Inequality to Accelerate
* k-Means. In Proceedings of the Twentieth International Conference on
* Machine Learning (ICML-2003) (pp. 147–153). AAAI Press.
*
* @author Edward Raff
*/
public class ElkanKernelKMeans extends KernelKMeans
{
private static final long serialVersionUID = 4998832201379993827L;
/**
* Distances between centroid i and all other centroids
*/
private double[][] centroidSelfDistances;
/**
* un-normalized dot product between centroid i and all other centroids.
*/
private double[][] centroidPairDots;
/**
* Creates a new Kernel K Means object
* @param kernel the kernel to use
*/
public ElkanKernelKMeans(KernelTrick kernel)
{
super(kernel);
}
public ElkanKernelKMeans(ElkanKernelKMeans toCopy)
{
super(toCopy);
}
@Override
public int findClosestCluster(Vec x, List qi)
{
double min = Double.MAX_VALUE;
int min_indx = -1;
//Use triangle inequality to prune out clusters!
boolean[] pruned = new boolean[meanSqrdNorms.length];
Arrays.fill(pruned, false);
for(int i = 0; i < meanSqrdNorms.length; i++)
{
if(ownes[i] <= 1e-15 || pruned[i])
continue;
double dist = distance(x, qi, i);
if(dist < min)
{
min = dist;
min_indx = i;
}
//we now know d(x, c_i), see who we can prune based off this
for(int j = i+1; j < meanSqrdNorms.length; j++)
{
if(centroidSelfDistances[i][j] >= 2*dist)
pruned[j] = true;
}
}
return min_indx;
}
/**
* Updates the un-normalized dot product between cluster centers, which is
* stored in {@link #centroidPairDots}. Using this method avoids redundant
* calculation, only adjusting for the values that have changed.
*
* @param prev_assignments what the previous assignment of data points to
* cluster center looked like
* @param new_assignments the new assignment of data points to cluster
* centers
* @param parallel source of threads for parallel computation. May be null.
*/
private void update_centroid_pair_dots(final int[] prev_assignments, final int[] new_assignments, boolean parallel)
{
final int N = X.size();
//TODO might need an update for alocation
ParallelUtils.run(parallel, N, (start, end) ->
{
double[][] localChanges = new double[centroidPairDots.length][centroidPairDots.length];
for(int i = start; i < end; i++)
{
final double w_i = W.get(i);
int old_c_i = prev_assignments[i];
int new_c_i = new_assignments[i];
for(int j = i; j < N; j++)
{
int old_c_j = prev_assignments[j];
int new_c_j = new_assignments[j];
if(old_c_i == new_c_i && old_c_j == new_c_j)//no class changes
continue;//so we can skip it
final double w_j = W.get(j);
double K_ij = w_i * w_j * kernel.eval(i, j, X, accel);
if(old_c_i >= 0 && old_c_j >= 0)
{
localChanges[old_c_i][old_c_j] -= K_ij;
localChanges[old_c_j][old_c_i] -= K_ij;
}
localChanges[new_c_i][new_c_j] += K_ij;
localChanges[new_c_j][new_c_i] += K_ij;
}
}
for(int i = 0; i < localChanges.length; i++)
{
double[] centroidPairDots_i = centroidPairDots[i];
synchronized(centroidPairDots_i)
{
for(int j = 0; j < localChanges[i].length; j++)
centroidPairDots_i[j] += localChanges[i][j];
}
}
});
}
/**
* This is a helper method where the actual cluster is performed. This is because there
* are multiple strategies for modifying kmeans, but all of them require this step.
*
* The distance metric used is trained if needed
*
* @param dataSet The set of data points to perform clustering on
* @param k the number of clusters
* @param assignment an empty temp space to store the clustering
* classifications. Should be the same length as the number of data points
* @param exactTotal determines how the objective function (return value)
* will be computed. If true, extra work will be done to compute the exact
* distance from each data point to its cluster. If false, an upper bound
* approximation will be used.
* @param parallel the source of threads for parallel computation. If null, single threaded execution will occur
* @return the sum of squares distances from each data point to its closest cluster
*/
protected double cluster(final DataSet dataSet, final int k, final int[] assignment, boolean exactTotal, boolean parallel)
{
try
{
/**
* N data points
*/
final int N = dataSet.getSampleSize();
if(N < k)//Not enough points
throw new ClusterFailureException("Fewer data points then desired clusters, decrease cluster size");
X = dataSet.getDataVectors();
setup(k, assignment, dataSet.getDataWeights());
final double[][] lowerBound = new double[N][k];
final double[] upperBound = new double[N];
/**
* Distances between centroid i and all other centroids
*/
centroidSelfDistances = new double[k][k];
centroidPairDots = new double[k][k];
final double[] sC = new double[k];
calculateCentroidDistances(k, centroidSelfDistances, sC, assignment, null, parallel);
final int[] prev_assignment = new int[N];
int atLeast = 2;//Used to performan an extra round (first round does not assign)
final AtomicBoolean changeOccurred = new AtomicBoolean(true);
final boolean[] r = new boolean[N];//Default value of a boolean is false, which is what we want
initialClusterSetUp(k, N, lowerBound, upperBound, centroidSelfDistances, assignment, parallel);
int iterLimit = maximumIterations;
while ((changeOccurred.get() || atLeast > 0) && iterLimit-- >= 0)
{
atLeast--;
changeOccurred.set(false);
//Step 1
if(iterLimit < maximumIterations-1)//we already did this on before iteration
calculateCentroidDistances(k, centroidSelfDistances, sC, assignment, prev_assignment, parallel);
//Save current assignent for update next iteration
System.arraycopy(assignment, 0, prev_assignment, 0, assignment.length);
final CountDownLatch latch = new CountDownLatch(SystemInfo.LogicalCores);
//Step 2 / 3
ParallelUtils.run(parallel, N, (q) ->
{
//Step 2, skip those that u(v) < s(c(v))
if (upperBound[q] <= sC[assignment[q]])
return;
for (int c = 0; c < k; c++)
if (c != assignment[q] && upperBound[q] > lowerBound[q][c] && upperBound[q] > centroidSelfDistances[assignment[q]][c] * 0.5)
{
step3aBoundsUpdate(r, q, assignment, upperBound, lowerBound);
step3bUpdate(upperBound, q, lowerBound, c, centroidSelfDistances, assignment, changeOccurred);
}
});
int moved = step4_5_6_distanceMovedBoundsUpdate(k, N, lowerBound, upperBound, assignment, r, parallel);
}
double totalDistance = 0.0;
//TODO do I realy want to keep this around for the kernel version?
if (exactTotal == true)
for (int i = 0; i < N; i++)
totalDistance += Math.pow(upperBound[i], 2);//TODO this isn't exact any more
else
for (int i = 0; i < N; i++)
totalDistance += Math.pow(upperBound[i], 2);
return totalDistance;
}
catch (Exception ex)
{
ex.printStackTrace();
throw new FailedToFitException(ex);
}
}
private void initialClusterSetUp(final int k, final int N, final double[][] lowerBound,
final double[] upperBound, final double[][] centroidSelfDistances, final int[] assignment, boolean parallel)
{
ParallelUtils.run(parallel, N, (start, end) ->
{
//Skip markers
final boolean[] skip = new boolean[k];
for (int q = start; q < end; q++)
{
double minDistance = Double.MAX_VALUE;
int index = -1;
//Default value is false, we cant skip anything yet
Arrays.fill(skip, false);
for (int i = 0; i < k; i++)
{
if (skip[i])
continue;
double d = distance(q, i, assignment);
lowerBound[q][i] = d;
if (d < minDistance)
{
minDistance = upperBound[q] = d;
index = i;
//We now have some information, use lemma 1 to see if we can skip anything
for (int z = i + 1; z < k; z++)
if (centroidSelfDistances[i][z] >= 2 * d)
skip[z] = true;
}
}
newDesignations[q] = index;
}
});
}
private int step4_5_6_distanceMovedBoundsUpdate(final int k, final int N,
final double[][] lowerBound, final double[] upperBound,
final int[] assignment, final boolean[] r, boolean parallel)
{
final double[] distancesMoved = new double[k];
//copy the originonal sqrd norms b/c we need them to compute the distance means moved
final double[] oldSqrdNorms = new double[meanSqrdNorms.length];
for(int i = 0; i < meanSqrdNorms.length; i++)
oldSqrdNorms[i] = meanSqrdNorms[i]*normConsts[i];
//first we need to do assignment movement updated, otherwise the sqrdNorms will be wrong and we will get incorrect values for cluster movemnt
int moved = ParallelUtils.run(parallel, N, (start, end)->
{
double[] sqrdChange = new double[k];
double[] ownerChange = new double[k];
int localChange = 0;
for(int q = start; q < end; q++)
localChange += updateMeansFromChange(q, assignment, sqrdChange, ownerChange);
synchronized(assignment)
{
applyMeanUpdates(sqrdChange, ownerChange);
}
return localChange;
},
(t, u) -> t+u);
updateNormConsts();
//now do cluster movement
//Step 5
ParallelUtils.run(parallel, k, (i)->
{
distancesMoved[i] = meanToMeanDistance(i, i, newDesignations, assignment, oldSqrdNorms[i], parallel);
});
ParallelUtils.run(parallel, k, (c) ->
{
for (int q = 0; q < N; q++)
lowerBound[q][c] = Math.max(lowerBound[q][c] - distancesMoved[c], 0);
});
//now we can move the assignments over
System.arraycopy(newDesignations, 0, assignment, 0, N);
//Step 6
ParallelUtils.run(parallel, N, (start, end) ->
{
for(int q = start; q < end; q++)
{
upperBound[q] += distancesMoved[assignment[q]];
r[q] = true;
}
});
return moved;
}
private void step3aBoundsUpdate(boolean[] r, int q, final int[] assignment, double[] upperBound, double[][] lowerBound)
{
//3(a)
if (r[q])
{
r[q] = false;
int meanIndx = assignment[q];
double d = distance(q, meanIndx, assignment);
lowerBound[q][meanIndx] = d;///Not sure if this is supposed to be here
upperBound[q] = d;
}
}
private void step3bUpdate(double[] upperBound, final int q, double[][] lowerBound,
final int c, double[][] centroidSelfDistances, final int[] assignment,
final AtomicBoolean changeOccurred)
{
//3(b)
if (upperBound[q] > lowerBound[q][c] || upperBound[q] > centroidSelfDistances[assignment[q]][c] / 2)
{
double d = distance(q, c, assignment);
lowerBound[q][c] = d;
if (d < upperBound[q])
{
newDesignations[q] = c;
upperBound[q] = d;
changeOccurred.lazySet(true);
}
}
}
private void calculateCentroidDistances(final int k, final double[][] centroidSelfDistances, final double[] sC, final int[] curAssignments, int[] prev_assignments, final boolean parallel)
{
if(prev_assignments == null)
{
prev_assignments = new int[curAssignments.length];
Arrays.fill(prev_assignments, -1);
}
final int[] prev_assing = prev_assignments;
//compute self dot-products
update_centroid_pair_dots(prev_assing, curAssignments, parallel);
double[] weight_per_cluster = new double[k];
for (int i = 0; i < curAssignments.length; i++)
weight_per_cluster[curAssignments[i]] += W.get(i);
//normalize dot products and make distances
for (int i = 0; i < k; i++)
for (int z = i + 1; z < k; z++)
{
double dot = centroidPairDots[i][z];
dot /= (weight_per_cluster[i] * weight_per_cluster[z]);
double d = meanSqrdNorms[i] * normConsts[i] + meanSqrdNorms[z] * normConsts[z] - 2 * dot;
centroidSelfDistances[z][i] = centroidSelfDistances[i][z] = Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger
}
//update sC
for (int i = 0; i < k; i++)
{
double sCmin = Double.MAX_VALUE;
for (int z = 0; z < k; z++)
if(i != z)
sCmin = Math.min(sCmin, centroidSelfDistances[i][z]);
sC[i] = sCmin / 2.0;
}
}
@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");
cluster(dataSet, clusters, designations, false, parallel);
return designations;
}
@Override
public ElkanKernelKMeans clone()
{
return new ElkanKernelKMeans(this);
}
}
Ads help maintain this website.