package jsat.clustering.kmeans;
import java.util.*;
import jsat.DataSet;
import jsat.linear.Vec;
/**
* This class provides a method of performing {@link KMeans} clustering when the
* value of {@code K} is not known. It works by incrementing the value
* of {@code k} up to some specified maximum, and running a full KMeans for each
* value.
*
* Note, by default this implementation uses a heuristic for the max value of
* {@code K} that is capped at 100 when using the
* {@link #cluster(jsat.DataSet) } type methods.
*
* When the value of {@code K} is specified, the implementation will simply call
* the regular KMeans object it was constructed with.
*
* See: Pham, D. T., Dimov, S. S.,&Nguyen, C. D. (2005). Selection of K in
* K-means clustering. Proceedings of the Institution of Mechanical
* Engineers, Part C: Journal of Mechanical Engineering Science, 219(1),
* 103–119. doi:10.1243/095440605X8298
*
* @author Edward Raff
*/
public class KMeansPDN extends KMeans
{
private static final long serialVersionUID = -2358377567814606959L;
private KMeans kmeans;
private double[] fKs;
/**
* Creates a new clusterer.
*/
public KMeansPDN()
{
this(new HamerlyKMeans());
}
/**
* Creates a new clustered that uses the specified object to perform clustering for all {@code k}.
* @param kmeans the k-means object to use for clustering
*/
public KMeansPDN(KMeans kmeans)
{
super(kmeans.dm, kmeans.seedSelection, kmeans.rand);
this.kmeans = kmeans;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public KMeansPDN(KMeansPDN toCopy)
{
super(toCopy);
this.kmeans = toCopy.kmeans.clone();
if(toCopy.fKs != null)
this.fKs = Arrays.copyOf(toCopy.fKs, toCopy.fKs.length);
}
/**
* Returns the array of {@code f(K)} values generated for the last data set.
* The value at index {@code i} is the score for cluster {@code i+1}.
* Smaller values indicate better clusterings.
*
* @return the array of {@code f(K)} values, or {@code null} if no data set
* has been clustered
*/
public double[] getfKs()
{
return fKs;
}
@Override
public int[] cluster(DataSet dataSet, boolean parallel, int[] designations)
{
return cluster(dataSet, 1, (int) Math.min(Math.max(Math.sqrt(dataSet.getSampleSize()), 10), 100), parallel, designations);
}
@Override
public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations)
{
if(highK == lowK)
return cluster(dataSet, lowK, parallel, designations);
else if(highK < lowK)
throw new IllegalArgumentException("low value of k (" + lowK + ") must be higher than the high value of k(" + highK + ")");
final int N = dataSet.getSampleSize();
final int D = dataSet.getNumNumericalVars();
fKs = new double[highK-1];//we HAVE to start from k=2
fKs[0] = 1.0;//see eq(2)
int[] bestCluster = new int[N];
double minFk = lowK == 1 ? 1.0 : Double.POSITIVE_INFINITY;//If our low k is > 1, force the check later to kick in at the first candidate k by making fK appear Inf
if(designations == null || designations.length < N)
designations = new int[N];
double alphaKprev = 0, S_k_prev = 0;
//re used every iteration
List curMeans = new ArrayList<>(highK);
means = new ArrayList<>();//the best set of means
//pre-compute cache instead of re-computing every time
List accelCache = dm.getAccelerationCache(dataSet.getDataVectors(), parallel);
for(int k = 2; k < highK; k++)
{
curMeans.clear();
//kmeans objective function result is the same as S_k
double S_k = cluster(dataSet, accelCache, k, curMeans, designations, true, parallel, true, null);//TODO could add a flag to make approximate S_k an option. Though it dosn't seem to work great on toy problems, might be fine on more realistic data
double alpha_k;
if(k == 2)
alpha_k = 1 - 3.0/(4*D); //eq(3a)
else
alpha_k = alphaKprev + (1-alphaKprev)/6;//eq(3b)
double fK;//eq(2)
if(S_k_prev == 0)
fKs[k-1] = fK = 1;
else
fKs[k-1] = fK = S_k/(alpha_k*S_k_prev);
alphaKprev = alpha_k;
S_k_prev = S_k;
if(k >= lowK && minFk > fK)
{
System.arraycopy(designations, 0, bestCluster, 0, N);
minFk = fK;
means.clear();
for(Vec mean : curMeans)
means.add(mean.clone());
}
}
//contract is we return designations with the data in it if we can, so copy the values back
System.arraycopy(bestCluster, 0, designations, 0, N);
return designations;
}
@Override
protected double cluster(DataSet dataSet, List accelCache, int k, List means, int[] assignment, boolean exactTotal, boolean threadpool, boolean returnError, Vec dataPointWeights)
{
return kmeans.cluster(dataSet, accelCache, k, means, assignment, exactTotal, threadpool, returnError, null);
}
@Override
public KMeansPDN clone()
{
return new KMeansPDN(this);
}
}
Ads help maintain this website.