package jsat.clustering;

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.linear.MatrixStatistics;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.*;
import static jsat.utils.SystemInfo.LogicalCores;
import jsat.utils.concurrent.ParallelUtils;

/**
 * This class provides methods for sampling a data set for a set of initial points to act as the seeds for a clustering algorithm. 
 * 
 * @author Edward Raff
 */
public class SeedSelectionMethods
{

    private SeedSelectionMethods()
    {
    }
    
    
    static public enum SeedSelection 
    {
        /**
         * The seed values will be randomly selected from the data set
         */
        RANDOM, 
        
        /**
         * The k-means++ seeding algo: 
* The seed values will be probabilistically selected from the * data set.
* The solution is O(log(k)) competitive with the * optimal k clustering when using {@link EuclideanDistance}. *

* See k-means++: The Advantages of Careful Seeding */ KPP, /** * The first seed is chosen randomly, and then all others are chosen * to be the farthest away from all other seeds */ FARTHEST_FIRST, /** * Selects the seeds in one pass by selecting points as evenly * distributed quantiles for the distance of each point from the mean * of the whole data set. This makes the seed selection deterministic *

* See: J. A. Hartigan and M. A. Wong, "A k-means clustering algorithm", * Applied Statistics, vol. 28, pp. 100–108, 1979. */ MEAN_QUANTILES }; /** * Selects seeds from a data set to use for a clustering algorithm. Copies of the vectors chosen will be returned. * * @param d the data set to perform select from * @param k the number of seeds to choose * @param dm the distance metric to used when selecting points * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @return a list of the copies of the chosen vectors. */ static public List selectIntialPoints(DataSet d, int k, DistanceMetric dm, Random rand, SeedSelection selectionMethod) { return selectIntialPoints(d, k, dm, null, rand, selectionMethod); } /** * * @param d the data set to perform select from * @param k the number of seeds to choose * @param dm the distance metric to used when selecting points * @param accelCache the cache of pre-generated acceleration information for the distance metric. May be null * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @return a list of the copies of the chosen vectors. */ static public List selectIntialPoints(DataSet d, int k, DistanceMetric dm, List accelCache, Random rand, SeedSelection selectionMethod) { int[] indicies = new int[k]; selectIntialPoints(d, indicies, dm, accelCache, rand, selectionMethod, false); List vecs = new ArrayList<>(k); for(Integer i : indicies) vecs.add(d.getDataPoint(i).getNumericalValues().clone()); return vecs; } /** * Selects seeds from a data set to use for a clustering algorithm. Copies of the vectors chosen will be returned. * * @param d the data set to perform select from * @param k the number of seeds to choose * @param dm the distance metric to used when selecting points * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @param parallel {@code true} if multiple threads should be used to * perform clustering. {@code false} if it should be done in a single * threaded manner. * @return a list of the copies of the chosen vectors. */ static public List selectIntialPoints(DataSet d, int k, DistanceMetric dm, Random rand, SeedSelection selectionMethod, boolean parallel) { return selectIntialPoints(d, k, dm, null, rand, selectionMethod, parallel); } /** * Selects seeds from a data set to use for a clustering algorithm. Copies of the vectors chosen will be returned. * * @param d the data set to perform select from * @param k the number of seeds to choose * @param dm the distance metric to used when selecting points * @param accelCache the cache of pre-generated acceleration information for the distance metric. May be null * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @param parallel {@code true} if multiple threads should be used to * perform clustering. {@code false} if it should be done in a single * threaded manner. * @return a list of the copies of the chosen vectors. */ static public List selectIntialPoints(DataSet d, int k, DistanceMetric dm, List accelCache, Random rand, SeedSelection selectionMethod, boolean parallel) { int[] indicies = new int[k]; selectIntialPoints(d, indicies, dm, accelCache, rand, selectionMethod, parallel); List vecs = new ArrayList(k); for(Integer i : indicies) vecs.add(d.getDataPoint(i).getNumericalValues().clone()); return vecs; } /** * Selects seeds from a data set to use for a clustering algorithm. The indices of the chosen points will be placed in the indices array. * * @param d the data set to perform select from * @param indices a storage place to note the indices that were chosen as seed. The length of the array indicates how many seeds to select. * @param dm the distance metric to used when selecting points * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. */ static public void selectIntialPoints(DataSet d, int[] indices, DistanceMetric dm, Random rand, SeedSelection selectionMethod) { selectIntialPoints(d, indices, dm, null, rand, selectionMethod); } /** * Selects seeds from a data set to use for a clustering algorithm. The indices of the chosen points will be placed in the indices array. * * @param d the data set to perform select from * @param indices a storage place to note the indices that were chosen as seed. The length of the array indicates how many seeds to select. * @param dm the distance metric to used when selecting points * @param accelCache the cache of pre-generated acceleration information for the distance metric. May be null * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. */ static public void selectIntialPoints(DataSet d, int[] indices, DistanceMetric dm, List accelCache, Random rand, SeedSelection selectionMethod) { selectIntialPoints(d, indices, dm, accelCache, rand, selectionMethod, false); } /** * Selects seeds from a data set to use for a clustering algorithm. The indices of the chosen points will be placed in the indices array. * * @param d the data set to perform select from * @param indices a storage place to note the indices that were chosen as seed. The length of the array indicates how many seeds to select. * @param dm the distance metric to used when selecting points * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @param parallel {@code true} if multiple threads should be used to * perform clustering. {@code false} if it should be done in a single * threaded manner. */ static public void selectIntialPoints(DataSet d, int[] indices, DistanceMetric dm, Random rand, SeedSelection selectionMethod, boolean parallel) { selectIntialPoints(d, indices, dm, null, rand, selectionMethod, parallel); } /** * Selects seeds from a data set to use for a clustering algorithm. The indices of the chosen points will be placed in the indices array. * * @param d the data set to perform select from * @param indices a storage place to note the indices that were chosen as seed. The length of the array indicates how many seeds to select. * @param dm the distance metric to used when selecting points * @param accelCache the cache of pre-generated acceleration information for the distance metric. May be null * @param rand a source of randomness * @param selectionMethod The method of seed selection to use. * @param parallel {@code true} if multiple threads should be used to * perform clustering. {@code false} if it should be done in a single * threaded manner. */ static public void selectIntialPoints(DataSet d, int[] indices, DistanceMetric dm, List accelCache, Random rand, SeedSelection selectionMethod, boolean parallel) { int k = indices.length; if (null != selectionMethod) switch (selectionMethod) { case RANDOM: Set indecies = new IntSet(k); while (indecies.size() != k)//Keep sampling, we cant use the same point twice. indecies.add(rand.nextInt(d.getSampleSize()));//TODO create method to do uniform sampleling for a select range int j = 0; for (Integer i : indecies) indices[j++] = i; break; case KPP: kppSelection(indices, rand, d, k, dm, accelCache, parallel); break; case FARTHEST_FIRST: ffSelection(indices, rand, d, k, dm, accelCache, parallel); break; case MEAN_QUANTILES: mqSelection(indices, d, k, dm, accelCache, parallel); break; default: break; } } private static void kppSelection(int[] indices, Random rand, DataSet d, int k, DistanceMetric dm, List accelCache) { kppSelection(indices, rand, d, k, dm, accelCache, false); } private static void kppSelection(final int[] indices, Random rand, final DataSet d, final int k, final DistanceMetric dm, final List accelCache, boolean parallel) { /* * http://www.stanford.edu/~darthur/kMeansPlusPlus.pdf : k-means++: The Advantages of Careful Seeding * */ //Initial random point indices[0] = rand.nextInt(d.getSampleSize()); final double[] closestDist = new double[d.getSampleSize()]; final List X = d.getDataVectors(); for (int j = 1; j < k; j++) { //Compute the distance from each data point to the closest mean final int newMeanIndx = indices[j - 1];//Only the most recently added mean needs to get distances computed. final boolean forceCompute = j == 1; double sqrdDistSum = ParallelUtils.run(parallel, X.size(), (start, end) -> { double sqrdDistChanges = 0.0; for (int i = start; i < end; i++) { double newDist = dm.dist(newMeanIndx, i, X, accelCache); newDist *= newDist; if (newDist < closestDist[i] || forceCompute) { sqrdDistChanges -= closestDist[i];//on inital, -= 0 changes nothing. on others, removed the old value sqrdDistChanges += newDist; closestDist[i] = newDist; } } return sqrdDistChanges; }, (t, u) -> t + u); if(sqrdDistSum <= 1e-6)//everyone is too close, randomly fill rest { Set ind = new IntSet(); for(int i = 0;i accelCache, boolean parallel) { //Initial random point indices[0] = rand.nextInt(d.getSampleSize()); final double[] closestDist = new double[d.getSampleSize()]; Arrays.fill(closestDist, Double.POSITIVE_INFINITY); final List X = d.getDataVectors(); for (int j = 1; j < k; j++) { //Compute the distance from each data point to the closest mean final int newMeanIndx = indices[j - 1];//Only the most recently added mean needs to get distances computed. //Atomic integer storres the index of the vector with the current maximum minimum distance to a selected centroid final AtomicInteger maxDistIndx = new AtomicInteger(0); ParallelUtils.run(parallel, d.getSampleSize(), (start, end)-> { double maxDist = Double.NEGATIVE_INFINITY; int max = indices[0];//set to some lazy value, it will be changed for (int i = start; i < end; i++) { double newDist = dm.dist(newMeanIndx, i, X, accelCache); closestDist[i] = Math.min(newDist, closestDist[i]); if (closestDist[i] > maxDist) { maxDist = closestDist[i]; max = i; } } synchronized(maxDistIndx) { if(closestDist[max] > closestDist[maxDistIndx.get()]) maxDistIndx.set(max); } }); indices[j] = maxDistIndx.get(); } } private static void mqSelection(final int[] indices, final DataSet d, final int k, final DistanceMetric dm, final List accelCache, boolean parallel) { final double[] meanDist = new double[d.getSampleSize()]; //Compute the distance from each data point to the closest mean final Vec newMean = MatrixStatistics.meanVector(d); final List meanQI = dm.getQueryInfo(newMean); final List X = d.getDataVectors(); ParallelUtils.run(parallel, d.getSampleSize(), (start, end)-> { for (int i = start; i < end; i++) meanDist[i] = dm.dist(i, newMean, meanQI, X, accelCache); }); IndexTable indxTbl = new IndexTable(meanDist); for(int l = 0; l < k; l++) indices[l] = indxTbl.index(l*d.getSampleSize()/k); } }

Ads help maintain this website.