jsat.clustering.kmeans

Class KernelKMeans

java.lang.Object

jsat.clustering.ClustererBase

jsat.clustering.KClustererBase

jsat.clustering.kmeans.KernelKMeans

All Implemented Interfaces:

Serializable, Clusterer, KClusterer, Parameterized

Direct Known Subclasses:

ElkanKernelKMeans, LloydKernelKMeans

public abstract class KernelKMeans
extends KClustererBase
implements Parameterized

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 the closest cluster or finding the distance between means

Author:

Edward Raff

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected List<Double>	accel THe acceleration cache for the kernel
protected KernelTrick	kernel The kernel trick to use
protected int	maximumIterations
protected double[]	meanSqrdNorms The value of the un-normalized squared norm for each mean
protected int[]	newDesignations A temporary space for updating ownership designations for each datapoint.
protected double[]	normConsts The normalizing constant for each mean.
protected double[]	ownes The weighted number of dataums owned by each mean
protected double[]	selfK The value of k(x,x) for every point in X
protected Vec	W The weight of each data point
protected List<Vec>	X The list of data points that this was trained on

Constructor Summary

Constructors

Constructor and Description
KernelKMeans(KernelKMeans toCopy) Copy constructor
KernelKMeans(KernelTrick kernel)

Method Summary

Modifier and Type	Method and Description
protected void	applyMeanUpdates(double[] sqrdNorms, double[] ownerships)
abstract KernelKMeans	clone()
int[]	cluster(DataSet dataSet, ExecutorService threadpool, int[] designations) Performs clustering on the given data set.
int[]	cluster(DataSet dataSet, int[] designations) Performs clustering on the given data set.
int[]	cluster(DataSet dataSet, int lowK, int highK, ExecutorService threadpool, int[] designations)
int[]	cluster(DataSet dataSet, int lowK, int highK, int[] designations)
protected double	distance(int i, int k, int[] designations) Computes the distance between one data point and a specified mean
double	distance(Vec x, int k) Returns the distance between the given data point and the the specified cluster
double	distance(Vec x, List<Double> qi, int k) Returns the distance between the given data point and the the specified cluster
protected double	evalSumK(int i, int clusterID, int[] d) Computes the kernel sum of data point i against all the points in cluster group clusterID.
protected double	evalSumK(Vec x, List<Double> qi, int clusterID, int[] d) Computes the kernel sum of the given data point against all the points in cluster group clusterID.
int	findClosestCluster(Vec x) Finds the cluster ID that is closest to the given data point
int	findClosestCluster(Vec x, List<Double> qi) Finds the cluster ID that is closest to the given data point
int	getMaximumIterations() Returns the maximum number of iterations of the KMeans algorithm that will be performed.
Parameter	getParameter(String paramName) Returns the parameter with the given name.
List<Parameter>	getParameters() Returns the list of parameters that can be altered for this learner.
double	meanToMeanDistance(int k0, int k1) Computes the distance between two of the means in the clustering
protected double	meanToMeanDistance(int k0, int k1, int[] assignments)
protected double	meanToMeanDistance(int k0, int k1, int[] assignments, ExecutorService ex)
protected double	meanToMeanDistance(int k0, int k1, int[] assignments0, int[] assignments1, double k1SqrdNorm)
protected double	meanToMeanDistance(int k0, int k1, int[] assignments0, int[] assignments1, double k1SqrdNorm, ExecutorService ex)
void	setMaximumIterations(int iterLimit) Sets the maximum number of iterations allowed
protected void	setup(int K, int[] designations, Vec W) Sets up the internal structure for KenrelKMeans.
boolean	supportsWeightedData() Indicates whether the model knows how to cluster using weighted data points.
protected int	updateMeansFromChange(int i, int[] designations) Updates the means based off the change of a specific data point
protected int	updateMeansFromChange(int i, int[] designations, double[] sqrdNorms, double[] ownership) Accumulates the updates to the means and ownership into the provided arrays.
protected void	updateNormConsts() Updates the normalizing constants for each mean.

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.KClusterer

cluster, cluster

Methods inherited from interface jsat.clustering.Clusterer

cluster, cluster

Field Detail

kernel

protected KernelTrick kernel

The kernel trick to use

X

protected List<Vec> X

The list of data points that this was trained on

W

protected Vec W

The weight of each data point

accel

protected List<Double> accel

THe acceleration cache for the kernel

selfK

protected double[] selfK

The value of k(x,x) for every point in X

meanSqrdNorms

protected double[] meanSqrdNorms

The value of the un-normalized squared norm for each mean

normConsts

protected double[] normConsts

The normalizing constant for each mean. General this would be 1/owned[k]²

ownes

protected double[] ownes

The weighted number of dataums owned by each mean

newDesignations

protected int[] newDesignations

A temporary space for updating ownership designations for each datapoint. When done, this will store the final designations for each point

maximumIterations

protected int maximumIterations

Constructor Detail

KernelKMeans

public KernelKMeans(KernelTrick kernel)

Parameters:

kernel - the kernel to use

KernelKMeans

public KernelKMeans(KernelKMeans toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

setMaximumIterations

public void setMaximumIterations(int iterLimit)

Sets the maximum number of iterations allowed

Parameters:

iterLimit - the maximum number of iterations of the KMeans algorithm

getMaximumIterations

public int getMaximumIterations()

Returns the maximum number of iterations of the KMeans algorithm that will be performed.

Returns:

the maximum number of iterations of the KMeans algorithm that will be performed.

cluster

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

Description copied from interface: Clusterer

Performs clustering on the given data set. Parameters may be estimated by the method, or other heuristics performed.

Specified by:

cluster in interface Clusterer

Parameters:

dataSet - the data set to perform clustering on

designations - the array which will contain the designated values. The array will be altered and returned by the function. If null is given, a new array will be created and returned.

Returns:

an array indicating for each value indicating the cluster designation. This is the same array as designations, or a new one if the input array was null

cluster

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

Description copied from interface: Clusterer

Performs clustering on the given data set. Parameters may be estimated by the method, or other heuristics performed.

Specified by:

cluster in interface Clusterer

Parameters:

dataSet - the data set to perform clustering on

threadpool - a source of threads to run tasks

designations - the array which will contain the designated values. The array will be altered and returned by the function. If null is given, a new array will be created and returned.

Returns:

an array indicating for each value indicating the cluster designation. This is the same array as designations, or a new one if the input array was null

cluster

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

Specified by:

cluster in interface KClusterer

cluster

public int[] cluster(DataSet dataSet,
                     int lowK,
                     int highK,
                     int[] designations)

Specified by:

cluster in interface KClusterer

evalSumK

protected double evalSumK(int i,
                          int clusterID,
                          int[] d)

Computes the kernel sum of data point i against all the points in cluster group clusterID.

Parameters:

i - the index of the data point to query for

clusterID - the cluster index to get the sum of kernel products

d -

Returns:

the sum Σk(x_i, x_j), ∀ j, d[j] == clusterID

evalSumK

protected double evalSumK(Vec x,
                          List<Double> qi,
                          int clusterID,
                          int[] d)

Computes the kernel sum of the given data point against all the points in cluster group clusterID.

Parameters:

x - the data point to get the kernel sum of

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

clusterID - the cluster index to get the sum of kernel products

d - the array of cluster assignments

Returns:

the sum Σk(x_i, x_j), ∀ j, d[j] == clusterID

setup

protected void setup(int K,
                     int[] designations,
                     Vec W)

Sets up the internal structure for KenrelKMeans. Should be called first before any work is done

Parameters:

K - the number of clusters to find

designations - the initial designations array to fill with values

W - the weight for each individual data point

updateNormConsts

protected void updateNormConsts()

Updates the normalizing constants for each mean. Should be called after every change in ownership

distance

protected double distance(int i,
                          int k,
                          int[] designations)

Computes the distance between one data point and a specified mean

Parameters:

i - the data point to get the distance for

k - the mean index to get the distance to

designations - the array if ownership designations for each cluster to use

Returns:

the distance between data point x_i and mean k

distance

public double distance(Vec x,
                       int k)

Returns the distance between the given data point and the the specified cluster

Parameters:

x - the data point to get the distance for

k - the cluster id to get the distance to

Returns:

the distance between the given data point and the specified cluster

distance

public double distance(Vec x,
                       List<Double> qi,
                       int k)

Returns the distance between the given data point and the the specified cluster

Parameters:

x - the data point to get the distance for

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

k - the cluster id to get the distance to

Returns:

the distance between the given data point and the specified cluster

findClosestCluster

public int findClosestCluster(Vec x)

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

Parameters:

x - the data point to get the closest cluster for

Returns:

the index of the closest cluster

findClosestCluster

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

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

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

updateMeansFromChange

protected int updateMeansFromChange(int i,
                                    int[] designations)

Updates the means based off the change of a specific data point

Parameters:

i - the index of the data point to try and update the means based on its movement

designations - the old assignments for ownership of each data point to one of the means

Returns:

1 if the index changed ownership, 0 if the index did not change ownership

updateMeansFromChange

protected int updateMeansFromChange(int i,
                                    int[] designations,
                                    double[] sqrdNorms,
                                    double[] ownership)

Accumulates the updates to the means and ownership into the provided arrays. This does not update meanSqrdNorms, and is meant to accumulate the change. To apply the changes pass the same arrays to #applyMeanUpdates(double[], int[])

Parameters:

i - the index of the data point to try and update the means based on its movement

designations - the old assignments for ownership of each data point to one of the means

sqrdNorms - the array to place the changes to the squared norms in

ownership - the array to place the changes to the ownership counts in

Returns:

1 if the index changed ownership, 0 if the index did not change ownership

applyMeanUpdates

protected void applyMeanUpdates(double[] sqrdNorms,
                                double[] ownerships)

meanToMeanDistance

public double meanToMeanDistance(int k0,
                                 int k1)

Computes the distance between two of the means in the clustering

Parameters:

k0 - the index of the first mean

k1 - the index of the second mean

Returns:

the distance between the two

meanToMeanDistance

protected double meanToMeanDistance(int k0,
                                    int k1,
                                    int[] assignments)

meanToMeanDistance

protected double meanToMeanDistance(int k0,
                                    int k1,
                                    int[] assignments,
                                    ExecutorService ex)

meanToMeanDistance

protected double meanToMeanDistance(int k0,
                                    int k1,
                                    int[] assignments0,
                                    int[] assignments1,
                                    double k1SqrdNorm)

Parameters:

k0 - the index of the first cluster

k1 - the index of the second cluster

assignments0 - the array of assignments to use for index k0

assignments1 - the array of assignments to use for index k1

k1SqrdNorm - the normalized squared norm for the mean indicated by k1. (ie: meanSqrdNorms multiplied by normConsts

Returns:

meanToMeanDistance

protected double meanToMeanDistance(int k0,
                                    int k1,
                                    int[] assignments0,
                                    int[] assignments1,
                                    double k1SqrdNorm,
                                    ExecutorService ex)

Parameters:

k0 - the index of the first cluster

k1 - the index of the second cluster

assignments0 - the array of assignments to use for index k0

assignments1 - the array of assignments to use for index k1

k1SqrdNorm - the normalized squared norm for the mean indicated by k1. (ie: meanSqrdNorms multiplied by normConsts

ex - source of threads for parallel execution

Returns:

clone

public abstract KernelKMeans clone()

Specified by:

clone in interface Clusterer

Specified by:

clone in interface KClusterer

Specified by:

clone in class KClustererBase

supportsWeightedData

public boolean supportsWeightedData()

Description copied from interface: Clusterer

Indicates whether the model knows how to cluster using weighted data points. If it does, the model will train assuming the weights. The values returned by this method may change depending on the parameters set for the model.

Specified by:

supportsWeightedData in interface Clusterer

Overrides:

supportsWeightedData in class ClustererBase

Returns:

true if the model supports weighted data, false otherwise

getParameters

public List<Parameter> getParameters()

Description copied from interface: Parameterized

Returns the list of parameters that can be altered for this learner.

Specified by:

getParameters in interface Parameterized

Returns:

the list of parameters that can be altered for this learner.

getParameter

public Parameter getParameter(String paramName)

Description copied from interface: Parameterized

Returns the parameter with the given name. Two different strings may map to a single Parameter object. An ASCII only string, and a Unicode style string.

Specified by:

getParameter in interface Parameterized

Parameters:

paramName - the name of the parameter to obtain

Returns:

the Parameter in question, or null if no such named Parameter exists.