jsat.clustering.kmeans

Class ElkanKernelKMeans

java.lang.Object

jsat.clustering.ClustererBase

jsat.clustering.KClustererBase

jsat.clustering.kmeans.KernelKMeans

jsat.clustering.kmeans.ElkanKernelKMeans

All Implemented Interfaces:

Serializable, Clusterer, KClusterer, Parameterized

public class ElkanKernelKMeans
extends KernelKMeans

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 DistanceMetric used support 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

See Also:

Serialized Form

Field Summary

Fields inherited from class jsat.clustering.kmeans.KernelKMeans

accel, kernel, maximumIterations, meanSqrdNorms, newDesignations, normConsts, ownes, selfK, W, X

Constructor Summary

Constructors

Constructor and Description
ElkanKernelKMeans(ElkanKernelKMeans toCopy)
ElkanKernelKMeans(KernelTrick kernel) Creates a new Kernel K Means object

Method Summary

Modifier and Type	Method and Description
ElkanKernelKMeans	clone()
int[]	cluster(DataSet dataSet, int clusters, ExecutorService threadpool, int[] designations)
int[]	cluster(DataSet dataSet, int clusters, int[] designations)
protected double	cluster(DataSet dataSet, int k, int[] assignment, boolean exactTotal, ExecutorService threadpool) This is a helper method where the actual cluster is performed.
int	findClosestCluster(Vec x, List<Double> qi) Finds the cluster ID that is closest to the given data point

Methods inherited from class jsat.clustering.kmeans.KernelKMeans

applyMeanUpdates, cluster, cluster, cluster, cluster, distance, distance, distance, evalSumK, evalSumK, findClosestCluster, getMaximumIterations, getParameter, getParameters, meanToMeanDistance, meanToMeanDistance, meanToMeanDistance, meanToMeanDistance, meanToMeanDistance, setMaximumIterations, setup, supportsWeightedData, updateMeansFromChange, updateMeansFromChange, updateNormConsts

Methods inherited from class jsat.clustering.KClustererBase

cluster, cluster, cluster, cluster

Methods inherited from class jsat.clustering.ClustererBase

cluster, cluster, createClusterListFromAssignmentArray, getDatapointsFromCluster

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jsat.clustering.Clusterer

cluster, cluster

Constructor Detail

ElkanKernelKMeans

public ElkanKernelKMeans(KernelTrick kernel)

Creates a new Kernel K Means object

Parameters:

kernel - the kernel to use

ElkanKernelKMeans

public ElkanKernelKMeans(ElkanKernelKMeans toCopy)

Method Detail

findClosestCluster

public int findClosestCluster(Vec x,
                              List<Double> qi)

Description copied from class: KernelKMeans

Finds the cluster ID that is closest to the given data point

Overrides:

findClosestCluster in class KernelKMeans

Parameters:

x - the data point to get the closest cluster for

qi - the query information for the given data point generated for the kernel in use. See KernelTrick.getQueryInfo(jsat.linear.Vec)

Returns:

the index of the closest cluster

cluster

protected double cluster(DataSet dataSet,
                         int k,
                         int[] assignment,
                         boolean exactTotal,
                         ExecutorService threadpool)

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

Parameters:

dataSet - The set of data points to perform clustering on

k - the number of clusters

assignment - an empty temp space to store the clustering classifications. Should be the same length as the number of data points

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.

threadpool - the source of threads for parallel computation. If null, single threaded execution will occur

Returns:

the sum of squares distances from each data point to its closest cluster

cluster

public int[] cluster(DataSet dataSet,
                     int clusters,
                     ExecutorService threadpool,
                     int[] designations)

cluster

public int[] cluster(DataSet dataSet,
                     int clusters,
                     int[] designations)

clone

public ElkanKernelKMeans clone()

Specified by:

clone in interface Clusterer

Specified by:

clone in interface KClusterer

Specified by:

clone in class KernelKMeans