package jsat.clustering.kmeans;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.clustering.KClustererBase;
import jsat.distributions.kernels.KernelTrick;
import jsat.linear.ConstantVector;
import jsat.linear.Vec;
import jsat.parameters.Parameter;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.Parameterized;
import jsat.utils.DoubleList;
import jsat.utils.ListUtils;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* Base class for various Kernel K Means implementations. Because the Kernelized
* version is more computationally expensive, only the clustering methods where
* the number of clusters is specified apriori are supported.
*
* KernelKMeans keeps a reference to the data passed in for clustering so that
* queries can be conveniently answered, such as getting
* {@link #findClosestCluster(jsat.linear.Vec) the closest cluster} or finding
* the {@link #meanToMeanDistance(int, int) distance between means}
*
* @author Edward Raff
*/
public abstract class KernelKMeans extends KClustererBase implements Parameterized
{
private static final long serialVersionUID = -5294680202634779440L;
/**
* The kernel trick to use
*/
@ParameterHolder
protected KernelTrick kernel;
/**
* The list of data points that this was trained on
*/
protected List X;
/**
* The weight of each data point
*/
protected Vec W;
/**
* THe acceleration cache for the kernel
*/
protected List accel;
/**
* The value of k(x,x) for every point in {@link #X}
*/
protected double[] selfK;
/**
* The value of the un-normalized squared norm for each mean
*/
protected double[] meanSqrdNorms;
/**
* The normalizing constant for each mean. General this would be
* 1/owned[k]2
*/
protected double[] normConsts;
/**
* The weighted number of dataums owned by each mean
*/
protected double[] ownes;
/**
* A temporary space for updating ownership designations for each datapoint.
* When done, this will store the final designations for each point
*/
protected int[] newDesignations;
protected int maximumIterations = Integer.MAX_VALUE;
/**
*
* @param kernel the kernel to use
*/
public KernelKMeans(KernelTrick kernel)
{
this.kernel = kernel;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public KernelKMeans(KernelKMeans toCopy)
{
this.kernel = toCopy.kernel.clone();
this.maximumIterations = toCopy.maximumIterations;
if(toCopy.X != null)
{
this.X = new ArrayList<>(toCopy.X.size());
for( Vec v : toCopy.X)
this.X.add(v.clone());
}
if(toCopy.accel != null)
this.accel = new DoubleList(toCopy.accel);
if(toCopy.selfK != null)
this.selfK = Arrays.copyOf(toCopy.selfK, toCopy.selfK.length);
if(toCopy.meanSqrdNorms != null)
this.meanSqrdNorms = Arrays.copyOf(toCopy.meanSqrdNorms, toCopy.meanSqrdNorms.length);
if(toCopy.normConsts != null)
this.normConsts = Arrays.copyOf(toCopy.normConsts, toCopy.normConsts.length);
if(toCopy.ownes != null)
this.ownes = Arrays.copyOf(toCopy.ownes, toCopy.ownes.length);
if(toCopy.newDesignations != null)
this.newDesignations = Arrays.copyOf(toCopy.newDesignations, toCopy.newDesignations.length);
if(toCopy.W != null)
this.W = toCopy.W.clone();
}
/**
* Sets the maximum number of iterations allowed
* @param iterLimit the maximum number of iterations of the KMeans algorithm
*/
public void setMaximumIterations(int iterLimit)
{
if(iterLimit <= 0)
throw new IllegalArgumentException("iterations must be a positive value, not " + iterLimit);
this.maximumIterations = iterLimit;
}
/**
* Returns the maximum number of iterations of the KMeans algorithm that will be performed.
* @return the maximum number of iterations of the KMeans algorithm that will be performed.
*/
public int getMaximumIterations()
{
return maximumIterations;
}
@Override
public int[] cluster(DataSet dataSet, int[] designations)
{
throw new UnsupportedOperationException("Not supported.");
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
throw new UnsupportedOperationException("Not supported.");
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
throw new UnsupportedOperationException("Not supported.");
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, int[] designations)
{
throw new UnsupportedOperationException("Not supported.");
}
/**
* Computes the kernel sum of data point {@code i} against all the points in
* cluster group {@code clusterID}.
* @param i the index of the data point to query for
* @param clusterID the cluster index to get the sum of kernel products
* @param d
* @return the sum Σk(xi, xj), ∀ j, d[j] == clusterID
*/
protected double evalSumK(int i, int clusterID, int[] d)
{
double sum = 0;
for(int j = 0; j < X.size(); j++)
if(d[j] == clusterID)
sum += W.get(j) * kernel.eval(i, j, X, accel);
return sum;
}
/**
* Computes the kernel sum of the given data point against all the points in
* cluster group {@code clusterID}.
* @param x the data point to get the kernel sum of
* @param qi the query information for the given data point generated from the kernel in use. See {@link KernelTrick#getQueryInfo(jsat.linear.Vec) }
* @param clusterID the cluster index to get the sum of kernel products
* @param d the array of cluster assignments
* @return the sum Σk(xi, xj), ∀ j, d[j] == clusterID
*/
protected double evalSumK(Vec x, List qi, int clusterID, int[] d)
{
double sum = 0;
for(int j = 0; j < X.size(); j++)
if(d[j] == clusterID)
sum += W.get(j) * kernel.eval(j, x, qi, X, accel);
return sum;
}
/**
* Sets up the internal structure for KenrelKMeans. Should be called first before any work is done
* @param K the number of clusters to find
* @param designations the initial designations array to fill with values
* @param W the weight for each individual data point
*/
protected void setup(int K, int[] designations, Vec W)
{
accel = kernel.getAccelerationCache(X);
final int N = X.size();
selfK = new double[N];
for(int i = 0; i < selfK.length; i++)
selfK[i] = kernel.eval(i, i, X, accel);
ownes = new double[K];
meanSqrdNorms = new double[K];
newDesignations = new int[N];
if(W == null)
this.W = new ConstantVector(1.0, N);
else
this.W = W;
Random rand = RandomUtil.getRandom();
for (int i = 0; i < N; i++)
{
int to = rand.nextInt(K);
ownes[to] += this.W.get(i);
newDesignations[i] = designations[i] = to;
}
normConsts = new double[K];
updateNormConsts();
for (int i = 0; i < N; i++)
{
int i_k = designations[i];
final double w_i = this.W.get(i);
meanSqrdNorms[i_k] += w_i * selfK[i];
for (int j = i + 1; j < N; j++)
if (i_k == designations[j])
meanSqrdNorms[i_k] += 2 * w_i * this.W.get(j) * kernel.eval(i, j, X, accel);
}
}
/**
* Updates the normalizing constants for each mean. Should be called after
* every change in ownership
*/
protected void updateNormConsts()
{
for(int i = 0; i < normConsts.length; i++)
normConsts[i] = 1.0/(ownes[i]*ownes[i]);
}
/**
* Computes the distance between one data point and a specified mean
* @param i the data point to get the distance for
* @param k the mean index to get the distance to
* @param designations the array if ownership designations for each cluster to use
* @return the distance between data point {@link #X x}i and mean {@code k}
*/
protected double distance(int i, int k, int[] designations)
{
return Math.sqrt(Math.max(selfK[i] - 2.0/ownes[k] * evalSumK(i, k, designations) + meanSqrdNorms[k]*normConsts[k], 0));
}
/**
* Returns the distance between the given data point and the the specified cluster
* @param x the data point to get the distance for
* @param k the cluster id to get the distance to
* @return the distance between the given data point and the specified cluster
*/
public double distance(Vec x, int k)
{
return distance(x, kernel.getQueryInfo(x), k);
}
/**
* Returns the distance between the given data point and the the specified cluster
* @param x the data point to get the distance for
* @param qi the query information for the given data point generated for the kernel in use. See {@link KernelTrick#getQueryInfo(jsat.linear.Vec) }
* @param k the cluster id to get the distance to
* @return the distance between the given data point and the specified cluster
*/
public double distance(Vec x, List qi, int k)
{
if(k >= meanSqrdNorms.length || k < 0)
throw new IndexOutOfBoundsException("Only " + meanSqrdNorms.length + " clusters. " + k + " is not a valid index");
return Math.sqrt(Math.max(kernel.eval(0, 0, Arrays.asList(x), qi) - 2.0/ownes[k] * evalSumK(x, qi, k, newDesignations) + meanSqrdNorms[k]*normConsts[k], 0));
}
/**
* Finds the cluster ID that is closest to the given data point
* @param x the data point to get the closest cluster for
* @return the index of the closest cluster
*/
public int findClosestCluster(Vec x)
{
return findClosestCluster(x, kernel.getQueryInfo(x));
}
/**
* Finds the cluster ID that is closest to the given data point
* @param x the data point to get the closest cluster for
* @param qi the query information for the given data point generated for the kernel in use. See {@link KernelTrick#getQueryInfo(jsat.linear.Vec) }
* @return the index of the closest cluster
*/
public int findClosestCluster(Vec x, List qi)
{
double min = Double.MAX_VALUE;
int min_indx = -1;
for(int i = 0; i < meanSqrdNorms.length; i++)
{
double dist = distance(x, qi, i);
if(dist < min)
{
min = dist;
min_indx = i;
}
}
return min_indx;
}
/**
* Updates the means based off the change of a specific data point
* @param i the index of the data point to try and update the means based on its movement
* @param designations the old assignments for ownership of each data point to one of the means
* @return {@code 1} if the index changed ownership, {@code 0} if the index did not change ownership
*/
protected int updateMeansFromChange(int i, int[] designations)
{
return updateMeansFromChange(i, designations, meanSqrdNorms, ownes);
}
/**
* Accumulates the updates to the means and ownership into the provided
* arrays. This does not update {@link #meanSqrdNorms}, and is meant to
* accumulate the change. To apply the changes pass the same arrays to {@link #applyMeanUpdates(double[], int[]) }
* @param i the index of the data point to try and update the means based on its movement
* @param designations the old assignments for ownership of each data point to one of the means
* @param sqrdNorms the array to place the changes to the squared norms in
* @param ownership the array to place the changes to the ownership counts in
* @return {@code 1} if the index changed ownership, {@code 0} if the index did not change ownership
*/
protected int updateMeansFromChange(final int i, final int[] designations, final double[] sqrdNorms, final double[] ownership)
{
final int old_d = designations[i];
final int new_d = newDesignations[i];
if (old_d == new_d)//this one has not changed!
return 0;
final int N = X.size();
final double w_i = W.get(i);
ownership[old_d] -= w_i;
ownership[new_d] += w_i;
for (int j = 0; j < N; j++)
{
final double w_j = W.get(j);
final int oldD_j = designations[j];
final int newD_j = newDesignations[j];
if (i == j)//diagonal is an easy case
{
sqrdNorms[old_d] -= w_i*selfK[i];
sqrdNorms[new_d] += w_i*selfK[i];
}
else
{
//handle removing contribution from old mean
if (old_d == oldD_j)
{
//only do this for items that were apart of the OLD center
if (i > j && oldD_j != newD_j)
{
/*
* j,j is also being removed from this center.
* To avoid removing the value k_ij twice, the
* person with the later index gets to do the update
*/
}
else//safe to remove the k_ij contribution
sqrdNorms[old_d] -= 2 * w_i * w_j * kernel.eval(i, j, X, accel);
}
//handle adding contributiont to new mean
if (new_d == newD_j)
{
//only do this for items that are apart of the NEW center
if (i > j && oldD_j != newD_j)
{
/*
* j,j is also being added to this center.
* To avoid adding the value k_ij twice, the
* person with the later index gets to do the update
*/
}
else
sqrdNorms[new_d] += 2 * w_i * w_j * kernel.eval(i, j, X, accel);
}
}
}
return 1;
}
protected void applyMeanUpdates(double[] sqrdNorms, double[] ownerships)
{
for(int i = 0; i < sqrdNorms.length; i++)
{
meanSqrdNorms[i] += sqrdNorms[i];
ownes[i] += ownerships[i];
}
}
/**
* Computes the distance between two of the means in the clustering
* @param k0 the index of the first mean
* @param k1 the index of the second mean
* @return the distance between the two
*/
public double meanToMeanDistance(int k0, int k1)
{
if(k0 >= meanSqrdNorms.length || k0 < 0)
throw new IndexOutOfBoundsException("Only " + meanSqrdNorms.length + " clusters. " + k0 + " is not a valid index");
if(k1 >= meanSqrdNorms.length || k1 < 0)
throw new IndexOutOfBoundsException("Only " + meanSqrdNorms.length + " clusters. " + k1 + " is not a valid index");
return meanToMeanDistance(k0, k1, newDesignations);
}
protected double meanToMeanDistance(int k0, int k1, int[] assignments)
{
double d = meanSqrdNorms[k0]*normConsts[k0]+meanSqrdNorms[k1]*normConsts[k1]-2*dot(k0, k1, assignments);
return Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger
}
protected double meanToMeanDistance(int k0, int k1, int[] assignments, boolean parallel)
{
double d = meanSqrdNorms[k0]*normConsts[k0]+meanSqrdNorms[k1]*normConsts[k1]-2*dot(k0, k1, assignments, parallel);
return Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger
}
/**
*
* @param k0 the index of the first cluster
* @param k1 the index of the second cluster
* @param assignments0 the array of assignments to use for index k0
* @param assignments1 the array of assignments to use for index k1
* @param k1SqrdNorm the normalized squared norm for the mean
* indicated by {@code k1}. (ie: {@link #meanSqrdNorms} multiplied by {@link #normConsts}
* @return
*/
protected double meanToMeanDistance(int k0, int k1, int[] assignments0, int[] assignments1, double k1SqrdNorm)
{
double d = meanSqrdNorms[k0]*normConsts[k0]+k1SqrdNorm-2*dot(k0, k1, assignments0, assignments1);
return Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger
}
/**
*
* @param k0 the index of the first cluster
* @param k1 the index of the second cluster
* @param assignments0 the array of assignments to use for index k0
* @param assignments1 the array of assignments to use for index k1
* @param k1SqrdNorm the normalized squared norm for the mean
* indicated by {@code k1}. (ie: {@link #meanSqrdNorms} multiplied by {@link #normConsts}
* @param parallel source of threads for parallel execution
* @return
*/
protected double meanToMeanDistance(int k0, int k1, int[] assignments0, int[] assignments1, double k1SqrdNorm, boolean parallel)
{
double d = meanSqrdNorms[k0]*normConsts[k0]+k1SqrdNorm-2*dot(k0, k1, assignments0, assignments1, parallel);
return Math.sqrt(Math.max(0, d));//Avoid rare cases wehre 2*dot might be slightly larger
}
/**
* dot product between two different clusters from one set of cluster assignments
* @param k0 the index of the first cluster
* @param k1 the index of the second cluster
* @param assignment the array of assignments for cluster ownership
* @return the dot product between the two clusters.
*/
private double dot(final int k0, final int k1, final int[] assignment)
{
return dot(k0, k1, assignment, assignment);
}
/**
* dot product between two different clusters from one set of cluster assignments
* @param k0 the index of the first cluster
* @param k1 the index of the second cluster
* @param assignment the array of assignments for cluster ownership
* @param parallel source of threads for parallel execution
* @return the dot product between the two clusters.
*/
private double dot(final int k0, final int k1, final int[] assignment, boolean parallel)
{
return dot(k0, k1, assignment, assignment, parallel);
}
/**
* dot product between two different clusters from different sets of cluster
* assignments. Two different assignment arrays are used to allow
* overlapping assignment of points to the clusters.
*
* @param k0 the first cluster to take the dot product with
* @param k1 the second cluster to take the dot product with.
* @param assignment0 vector containing assignment values, will be used to
* determine which points belong to k0
* @param assignment1 vector containing assignment values, will be used to
* determine which points belong to k1
* @return the dot product between the two clusters.
*/
private double dot(final int k0, final int k1, final int[] assignment0, final int[] assignment1)
{
double dot = 0;
final int N = X.size();
double a = 0, b = 0;
/*
* Below, unless i&j are somehow in the same cluster - nothing bad will happen
*/
for(int i = 0; i < N; i++)
{
final double w_i = W.get(i);
if(assignment0[i] != k0)
continue;
a += w_i;
for(int j = 0; j < N; j++)
{
if(assignment1[j] != k1)
continue;
final double w_j = W.get(j);
dot += w_i * w_j * kernel.eval(i, j, X, accel);
}
}
for(int j = 0; j < N; j++)
if(assignment1[j] == k1)
b += W.get(j);
return dot/(a*b);
}
/**
* dot product between two different clusters from different sets of cluster
* assignments. Two different assignment arrays are used to allow
* overlapping assignment of points to the clusters.
*
* @param k0 the first cluster to take the dot product with
* @param k1 the second cluster to take the dot product with.
* @param assignment0 vector containing assignment values, will be used to
* determine which points belong to k0
* @param assignment1 vector containing assignment values, will be used to
* determine which points belong to k1
* @param ex source of threads for parallel execution
* @return the dot product between the two clusters.
*/
private double dot(final int k0, final int k1, final int[] assignment0, final int[] assignment1, boolean parallel)
{
double dot = 0;
final int N = X.size();
double a = 0, b = 0;
/*
* Below, unless i&j are somehow in the same cluster - nothing bad will happen
*/
ParallelUtils.run(parallel, N, (i) ->
{
final double w_i = W.get(i);
if(assignment0[i] != k0)
return 0.0;
double localDot = 0;
for(int j = 0; j < N; j++)
{
if(assignment1[j] != k1)
continue;
final double w_j = W.get(j);
localDot += w_i * w_j * kernel.eval(i, j, X, accel);
}
return localDot;
}, (t, u)->t+u);
a = W.sum();
for(int j = 0; j < N; j++)
if(assignment1[j] == k1)
b += W.get(j);
return dot/(a*b);
}
@Override
abstract public KernelKMeans clone();
@Override
public boolean supportsWeightedData()
{
return true;
}
}
Ads help maintain this website.