jsat.clustering.dissimilarity

Class SingleLinkDissimilarity

java.lang.Object

jsat.clustering.dissimilarity.AbstractClusterDissimilarity

jsat.clustering.dissimilarity.DistanceMetricDissimilarity

jsat.clustering.dissimilarity.LanceWilliamsDissimilarity

jsat.clustering.dissimilarity.SingleLinkDissimilarity

All Implemented Interfaces:

ClusterDissimilarity, UpdatableClusterDissimilarity

public class SingleLinkDissimilarity
extends LanceWilliamsDissimilarity
implements UpdatableClusterDissimilarity

Measures the dissimilarity of two clusters by returning the minimum dissimilarity between the two closest data points from the clusters, ie: the minimum distance needed to link the two clusters.

Author:

Edward Raff

Field Summary

Fields inherited from class jsat.clustering.dissimilarity.DistanceMetricDissimilarity

dm

Constructor Summary

Constructors

Constructor and Description
SingleLinkDissimilarity() Creates a new SingleLinkDissimilarity using the EuclideanDistance
SingleLinkDissimilarity(DistanceMetric dm) Creates a new SingleLinkDissimilarity
SingleLinkDissimilarity(SingleLinkDissimilarity toCopy) Copy constructor

Method Summary

Modifier and Type	Method and Description
protected double	aConst(boolean iFlag, int ni, int nj, int nk) This method computes the value of the α variable.
protected double	bConst(int ni, int nj, int nk) This method computes the value of the β variable.
protected double	cConst(int ni, int nj, int nk) This method computes the value of the γ variable.
SingleLinkDissimilarity	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

SingleLinkDissimilarity

public SingleLinkDissimilarity()

Creates a new SingleLinkDissimilarity using the EuclideanDistance

SingleLinkDissimilarity

public SingleLinkDissimilarity(DistanceMetric dm)

Creates a new SingleLinkDissimilarity

Parameters:

dm - the distance metric to use between individual points

SingleLinkDissimilarity

public SingleLinkDissimilarity(SingleLinkDissimilarity toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

clone

public SingleLinkDissimilarity clone()

Specified by:

clone in interface ClusterDissimilarity

Specified by:

clone in interface UpdatableClusterDissimilarity

Specified by:

clone in class LanceWilliamsDissimilarity

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

Overrides:

dissimilarity in class LanceWilliamsDissimilarity

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

Overrides:

dissimilarity in class LanceWilliamsDissimilarity

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

Overrides:

dissimilarity in class LanceWilliamsDissimilarity

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

Overrides:

dissimilarity in class LanceWilliamsDissimilarity

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)

Description copied from class: LanceWilliamsDissimilarity

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.

Overrides:

dissimilarity in class LanceWilliamsDissimilarity

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

aConst

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

Description copied from class: LanceWilliamsDissimilarity

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.

Specified by:

aConst in class LanceWilliamsDissimilarity

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 double bConst(int ni,
                        int nj,
                        int nk)

Description copied from class: LanceWilliamsDissimilarity

This method computes the value of the β variable.

Specified by:

bConst in class LanceWilliamsDissimilarity

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 double cConst(int ni,
                        int nj,
                        int nk)

Description copied from class: LanceWilliamsDissimilarity

This method computes the value of the γ variable.

Specified by:

cConst in class LanceWilliamsDissimilarity

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 γ