jsat.clustering.dissimilarity

Class LanceWilliamsDissimilarity

java.lang.Object

jsat.clustering.dissimilarity.AbstractClusterDissimilarity

jsat.clustering.dissimilarity.DistanceMetricDissimilarity

jsat.clustering.dissimilarity.LanceWilliamsDissimilarity

All Implemented Interfaces:

ClusterDissimilarity, UpdatableClusterDissimilarity

Direct Known Subclasses:

AverageLinkDissimilarity, CentroidDissimilarity, CompleteLinkDissimilarity, MedianDissimilarity, SingleLinkDissimilarity, WardsDissimilarity

public abstract class LanceWilliamsDissimilarity
extends DistanceMetricDissimilarity
implements UpdatableClusterDissimilarity

This class provides a base implementation of a Lance Williams (LW) Dissimilarity measure, which is updatable. All LW measures can be written in the form
α_i d_ik + α_j d_jk + β d_ij + γ |d_ik - d_jk|
The d's represent the distances between points, and the variables:

• α
• β
• γ

are computed from other functions, and depend on prior values.

NOTE: LW is meant for algorithms that perform updates to a distance matrix. While the dissimilarity(java.util.List, java.util.List) and dissimilarity(java.util.Set, java.util.Set, double[][]) methods will work and produce the correct results, their performance will likely be less than desired had they be computed directly.

Author:

Edward Raff

Field Summary

Fields inherited from class jsat.clustering.dissimilarity.DistanceMetricDissimilarity

dm

Constructor Summary

Constructors

Constructor and Description
LanceWilliamsDissimilarity(DistanceMetric dm) Creates a new LW dissimilarity measure using the given metric as the base distance between individual points.
LanceWilliamsDissimilarity(LanceWilliamsDissimilarity toCopy) Copy constructor

Method Summary

Modifier and Type	Method and Description
protected abstract double	aConst(boolean iFlag, int ni, int nj, int nk) This method computes the value of the α variable.
protected abstract double	bConst(int ni, int nj, int nk) This method computes the value of the β variable.
protected abstract double	cConst(int ni, int nj, int nk) This method computes the value of the γ variable.
abstract LanceWilliamsDissimilarity	clone()
double	dissimilarity(int ni, int nj, int nk, double d_ij, double d_ik, double d_jk) Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.
double	dissimilarity(int i, int ni, int j, int nj, double[][] distanceMatrix) Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.
double	dissimilarity(int i, int ni, int j, int nj, int k, int nk, double[][] distanceMatrix) Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.
double	dissimilarity(List<DataPoint> a, List<DataPoint> b) Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.
double	dissimilarity(Set<Integer> a, Set<Integer> b, double[][] distanceMatrix) Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.

Methods inherited from class jsat.clustering.dissimilarity.DistanceMetricDissimilarity

distance

Methods inherited from class jsat.clustering.dissimilarity.AbstractClusterDissimilarity

createDistanceMatrix, getDistance, setDistance

Methods inherited from class java.lang.Object

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

Methods inherited from interface jsat.clustering.dissimilarity.ClusterDissimilarity

distance

Constructor Detail

LanceWilliamsDissimilarity

public LanceWilliamsDissimilarity(DistanceMetric dm)

Creates a new LW dissimilarity measure using the given metric as the base distance between individual points.

Parameters:

dm - the base metric to measure dissimilarity from.

LanceWilliamsDissimilarity

public LanceWilliamsDissimilarity(LanceWilliamsDissimilarity toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

aConst

protected abstract double aConst(boolean iFlag,
                                 int ni,
                                 int nj,
                                 int nk)

This method computes the value of the α variable. A flag is used to control whether the value for the cluster i and k is being computed, or the value for the cluster j and k.

Parameters:

iFlag - true indicates that α_i is the value to compute, false indicated that α_j should be computed.

ni - the number of points that make up cluster i

nj - the number of points that make up cluster j

nk - the number of points that make up cluster k

Returns:

the value of the variable α

bConst

protected abstract double bConst(int ni,
                                 int nj,
                                 int nk)

This method computes the value of the β variable.

Parameters:

ni - the number of points that make up cluster i

nj - the number of points that make up cluster j

nk - the number of points that make up cluster k

Returns:

the value of the variable β

cConst

protected abstract double cConst(int ni,
                                 int nj,
                                 int nk)

This method computes the value of the γ variable.

Parameters:

ni - the number of points that make up cluster i

nj - the number of points that make up cluster j

nk - the number of points that make up cluster k

Returns:

the value of the variable γ

dissimilarity

public double dissimilarity(List<DataPoint> a,
                            List<DataPoint> b)

Description copied from interface: ClusterDissimilarity

Provides the notion of dissimilarity between two sets of points, that may not have the same number of points.

Specified by:

dissimilarity in interface ClusterDissimilarity

Parameters:

a - the first cluster of points

b - the second cluster of points

Returns:

a value >= 0 that describes the dissimilarity of the two clusters. The larger the value, the more different the two clusterings are.

dissimilarity

public double dissimilarity(Set<Integer> a,
                            Set<Integer> b,
                            double[][] distanceMatrix)

Description copied from interface: ClusterDissimilarity

Provides the notion of dissimilarity between two sets of points, that may not have the same number of points. This is done using a matrix containing all pairwise distance computations between all points.

Specified by:

dissimilarity in interface ClusterDissimilarity

Parameters:

a - the first set of indices of the original data set that are in a cluster, which map to distanceMatrix

b - the second set of indices of the original data set that are in a cluster, which map to distanceMatrix

distanceMatrix - the upper triangual distance matrix as created by AbstractClusterDissimilarity.createDistanceMatrix(jsat.DataSet, jsat.clustering.dissimilarity.ClusterDissimilarity)

Returns:

a value >= 0 that describes the dissimilarity of the two clusters. The larger the value, the more different the two clusterings are.

dissimilarity

public double dissimilarity(int i,
                            int ni,
                            int j,
                            int nj,
                            double[][] distanceMatrix)

Description copied from interface: UpdatableClusterDissimilarity

Provides the notion of dissimilarity between two sets of points, that may not have the same number of points. This is done using a matrix containing all pairwise distance computations between all points. This distance matrix will then be updated at each iteration and merging, leaving empty space in the matrix. The updates will be done by the clustering algorithm. Implementing this interface indicates that this dissimilarity measure can be accurately computed in an updatable manner that is compatible with a Lance–Williams update.

Specified by:

dissimilarity in interface UpdatableClusterDissimilarity

Parameters:

i - the index of cluster i's distance in the original data set

ni - the number of items in the cluster represented by i

j - the index of cluster j's distance in the original data set

nj - the number of items in the cluster represented by j

distanceMatrix - a distance matrix originally created by AbstractClusterDissimilarity.createDistanceMatrix(jsat.DataSet, jsat.clustering.dissimilarity.ClusterDissimilarity)

Returns:

a value >= 0 that describes the dissimilarity of the two clusters. The larger the value, the more different the two clusterings are.

dissimilarity

public double dissimilarity(int i,
                            int ni,
                            int j,
                            int nj,
                            int k,
                            int nk,
                            double[][] distanceMatrix)

Description copied from interface: UpdatableClusterDissimilarity

Provides the notion of dissimilarity between two sets of points, that may not have the same number of points. This is done using a matrix containing all pairwise distance computations between all points. This distance matrix will then be updated at each iteration and merging, leaving empty space in the matrix. The updates will be done by the clustering algorithm. Implementing this interface indicates that this dissimilarity measure can be accurately computed in an updatable manner that is compatible with a Lance–Williams update.
This computes the dissimilarity of the union of clusters i and j, (C_i ∪ C_j), with the cluster k. This method is used by other algorithms to perform an update of the distance matrix in an efficient manner.

Specified by:

dissimilarity in interface UpdatableClusterDissimilarity

Parameters:

i - the index of cluster i's distance in the original data set

ni - the number of items in the cluster represented by i

j - the index of cluster j's distance in the original data set

nj - the number of items in the cluster represented by j

k - the index of cluster k's distance in the original data set

nk - the number of items in the cluster represented by k a distance matrix originally created by AbstractClusterDissimilarity.createDistanceMatrix(jsat.DataSet, jsat.clustering.dissimilarity.ClusterDissimilarity)

Returns:

a value >= 0 that describes the dissimilarity of the union of two clusters with a third cluster. The larger the value, the more different the resulting clusterings are.

dissimilarity

public double dissimilarity(int ni,
                            int nj,
                            int nk,
                            double d_ij,
                            double d_ik,
                            double d_jk)

Provides the notion of dissimilarity between two sets of points, that may not have the same number of points. This is done using a matrix containing all pairwise distance computations between all points. This distance matrix will then be updated at each iteration and merging, leaving empty space in the matrix. The updates will be done by the clustering algorithm. Implementing this interface indicates that this dissimilarity measure can be accurately computed in an updatable manner that is compatible with a Lance–Williams update.
This computes the dissimilarity of the union of clusters i and j, (C_i ∪ C_j), with the cluster k. This method is used by other algorithms to perform an update of the distance matrix in an efficient manner.

Parameters:

ni - the number of items in the cluster represented by i

nj - the number of items in the cluster represented by j

nk - the number of items in the cluster represented by k

d_ij - the distance between clusters i and j

d_ik - the distance between clusters i and k

d_jk - the distance between clusters j and k

Returns:

the distance between the cluster formed from i and j, to the cluster k

clone

public abstract LanceWilliamsDissimilarity clone()

Specified by:

clone in interface ClusterDissimilarity

Specified by:

clone in interface UpdatableClusterDissimilarity

Specified by:

clone in class DistanceMetricDissimilarity