package jsat.clustering.kmeans;

import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.clustering.ClusterFailureException;
import jsat.clustering.KClustererBase;
import jsat.clustering.PAM;
import jsat.clustering.SeedSelectionMethods;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.parameters.*;
import jsat.utils.SystemInfo;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.random.RandomUtil;

/**
 * Base class for the numerous implementations of k-means that exist. This base
 * class provides an slow heuristic approach to the selection of k. 
 * 
 * @author Edward Raff
 */
public abstract class KMeans extends KClustererBase implements Parameterized
{

    private static final long serialVersionUID = 8730927112084289722L;

    /**
     * This is the default seed selection method used in ElkanKMeans. When used
     * with the {@link EuclideanDistance}, it selects seeds that are log optimal
     * with a high probability.
     */
    public static final SeedSelectionMethods.SeedSelection DEFAULT_SEED_SELECTION = SeedSelectionMethods.SeedSelection.KPP;
    
    @ParameterHolder
    protected DistanceMetric dm;
    protected SeedSelectionMethods.SeedSelection seedSelection;
    protected Random rand;
    
    /**
     * Indicates whether or not the means from the clustering should be saved
     */
    protected boolean storeMeans = true;
    /**
     * Indicates whether or not the distance between a datapoint and its nearest
     * centroid should be saved after clustering. This only applies when the 
     * error of the model is requested 
     */
    protected boolean saveCentroidDistance = true;
    
    /**
     * Distance from a datapoint to its nearest centroid. May be an approximate 
     * distance 
     */
    protected double[] nearestCentroidDist;
    
    /**
     * The list of means
     */
    protected List means;
    
    /**
     * Control the maximum number of iterations to perform. 
     */
    protected int MaxIterLimit = Integer.MAX_VALUE;

    public KMeans(DistanceMetric dm, SeedSelectionMethods.SeedSelection seedSelection, Random rand)
    {
        this.dm = dm;
        setSeedSelection(seedSelection);
        this.rand = rand;
    }

    /**
     * Copy constructor
     * @param toCopy 
     */
    public KMeans(KMeans toCopy)
    {
        this.dm = toCopy.dm.clone();
        this.seedSelection = toCopy.seedSelection;
        this.rand = RandomUtil.getRandom();
        if (toCopy.nearestCentroidDist != null)
            this.nearestCentroidDist = Arrays.copyOf(toCopy.nearestCentroidDist, toCopy.nearestCentroidDist.length);
        if (toCopy.means != null)
        {
            this.means = new ArrayList<>(toCopy.means.size());
            for (Vec v : toCopy.means)
                this.means.add(v.clone());
        }
    }
    
    /**
     * 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;
    }
    
    /**
     * If set to {@code true} the computed means will be stored after clustering
     * is completed, and can then be retrieved using {@link #getMeans() }. 
     * @param storeMeans {@code true} if the means should be stored for later, 
     * {@code false} to discard them once clustering is complete. 
     */
    public void setStoreMeans(boolean storeMeans)
    {
        this.storeMeans = storeMeans;
    }

    /**
     * Returns the raw list of means that were used for each class. 
     * @return the list of means for each class
     */
    public List getMeans()
    {
        return means;
    }
    
    /**
     * 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;
    }

    /**
     * Returns the distance metric in use
     * @return the distance metric in use
     */
    public DistanceMetric getDistanceMetric()
    {
        return dm;
    }
    
    /**
     * 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 accelCache acceleration cache to use, or {@code null}. If * {@code null}, the kmeans code will attempt to create one * @param k the number of clusters * @param means the initial points to use as the means. Its length is the * number of means that will be searched for. These means will be altered, * and should contain deep copies of the points they were drawn from. May be * empty, in which case the list will be filled with some selected means * @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. This also impacts the value stored in * {@link #nearestCentroidDist} * @param parallel the source of threads for parallel computation. If * null, single threaded execution will occur * @param returnError {@code true} is the sum of squared distances should be * returned. {@code false} means any value can be returned. * {@link #saveCentroidDistance} only applies if this is {@code true} * @param dataPointWeights the weight value to use for each data point. If * null, assume each point has equal weight. * @return the double */ abstract protected double cluster(final DataSet dataSet, List accelCache, final int k, final List means, final int[] assignment, boolean exactTotal, boolean parallel, boolean returnError, Vec dataPointWeights); static protected List> getListOfLists(int k) { List> ks = new ArrayList<>(k); for(int i = 0; i < k; i++) ks.add(new ArrayList<>()); return ks; } @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"); means = new ArrayList<>(clusters); cluster(dataSet, null, clusters, means, designations, false, parallel, false, null); if(!storeMeans) means = null; return designations; } @Override public int[] cluster(DataSet dataSet, int lowK, int highK, boolean parallel, int[] designations) { if(dataSet.getSampleSize() < highK) throw new ClusterFailureException("Fewer data points then desired clusters, decrease cluster size"); if(designations == null) designations = new int[dataSet.getSampleSize()]; double[] totDistances = new double[highK-lowK+1]; List cache = dm.getAccelerationCache(dataSet.getDataVectors(), parallel); for(int k = lowK; k <= highK; k++) { totDistances[k-lowK] = cluster(dataSet, cache, k, new ArrayList<>(), designations, true, parallel, true, null); } return findK(lowK, highK, totDistances, dataSet, designations); } private int[] findK(int lowK, int highK, double[] totDistances, DataSet dataSet, int[] designations) { //Now we process the distance changes /** * Keep track of the changes */ OnLineStatistics stats = new OnLineStatistics(); double maxChange = Double.MIN_VALUE; int maxChangeK = lowK; for(int i = lowK; i <= highK; i++) { double totDist = totDistances[i-lowK]; if(i > lowK) { double change = Math.abs(totDist-totDistances[i-lowK-1]); stats.add(change); if(change > maxChange) { maxChange = change; maxChangeK = i; } } } double changeMean = stats.getMean(); double changeDev = stats.getStandardDeviation(); //If we havent had any huge drops in total distance, assume that there are onlu to clusts if(maxChange < changeDev*2+changeMean) maxChangeK = lowK; else { double tmp; for(int i = 1; i < totDistances.length; i++) { if( (tmp = Math.abs(totDistances[i]-totDistances[i-1])) < maxChange ) { maxChange = tmp; maxChangeK = i+lowK; break; } } } return cluster(dataSet, maxChangeK, designations); } @Override abstract public KMeans clone(); @Override public boolean supportsWeightedData() { return true; } }

Ads help maintain this website.