package jsat.clustering.dissimilarity;
import static java.lang.Math.abs;
import java.util.List;
import java.util.Set;
import jsat.classifiers.DataPoint;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.utils.IntSet;
/**
* 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 dik + αj djk +
* β dij + γ |dik - djk|
*
* 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 {@link #dissimilarity(java.util.List, java.util.List) } and
* {@link #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
*/
public abstract class LanceWilliamsDissimilarity extends DistanceMetricDissimilarity implements UpdatableClusterDissimilarity
{
/**
* Creates a new LW dissimilarity measure using the given metric as the base distance between individual points.
* @param dm the base metric to measure dissimilarity from.
*/
public LanceWilliamsDissimilarity(DistanceMetric dm)
{
super(dm);
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public LanceWilliamsDissimilarity(LanceWilliamsDissimilarity toCopy)
{
this(toCopy.dm.clone());
}
/**
* 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.
*
* @param iFlag true indicates that αi is the
* value to compute, false indicated that αj
* should be computed.
* @param ni the number of points that make up cluster i
* @param nj the number of points that make up cluster j
* @param nk the number of points that make up cluster k
* @return the value of the variable α
*/
protected abstract double aConst(boolean iFlag, int ni, int nj, int nk);
/**
* This method computes the value of the β variable.
* @param ni the number of points that make up cluster i
* @param nj the number of points that make up cluster j
* @param nk the number of points that make up cluster k
* @return the value of the variable β
*/
protected abstract double bConst(int ni, int nj, int nk);
/**
* This method computes the value of the γ variable.
* @param ni the number of points that make up cluster i
* @param nj the number of points that make up cluster j
* @param nk the number of points that make up cluster k
* @return the value of the variable γ
*/
protected abstract double cConst(int ni, int nj, int nk);
@Override
public double dissimilarity(List a, List b)
{
if(a.size() == 1 && b.size() == 1)
return dm.dist(a.get(0).getNumericalValues(), b.get(0).getNumericalValues());
List CI;
List CJ;
List CK;
if(a.size() > 1)
{
CI = a.subList(0, 1);
CJ = a.subList(1, a.size());
CK = b;
}
else// a==1, b >1
{
CI = b.subList(0, 1);
CJ = b.subList(1, b.size());
CK = a;
}
double d_ik = dissimilarity(CI, CK);
double d_jk = dissimilarity(CJ, CK);
double d_ij = dissimilarity(CI, CJ);
return aConst(true, CI.size(), CJ.size(), CK.size()) * d_ik +
aConst(false, CI.size(), CJ.size(), CK.size()) * d_jk +
bConst(CI.size(), CJ.size(), CK.size()) * d_ij +
cConst(CI.size(), CJ.size(), CK.size()) * abs(d_ik-d_jk);
}
@Override
public double dissimilarity(Set a, Set b, double[][] distanceMatrix)
{
if(a.size() == 1 && b.size() == 1)
return getDistance(distanceMatrix, getVal(a), getVal(b));
Set CI;
Set CJ;
Set CK;
if(a.size() > 1)
{
CI = new IntSet();
CI.add(getVal(a));
CJ = new IntSet(a);
CJ.removeAll(CI);
CK = b;
}
else//a == 1, b > 1
{
CI = new IntSet();
CI.add(getVal(b));
CJ = new IntSet(b);
CJ.removeAll(CI);
CK = a;
}
double d_ik = dissimilarity(CI, CK, distanceMatrix);
double d_jk = dissimilarity(CJ, CK, distanceMatrix);
double d_ij = dissimilarity(CI, CJ, distanceMatrix);
return aConst(true, CI.size(), CJ.size(), CK.size()) * d_ik +
aConst(false, CI.size(), CJ.size(), CK.size()) * d_jk +
bConst(CI.size(), CJ.size(), CK.size()) * d_ij +
cConst(CI.size(), CJ.size(), CK.size()) * abs(d_ik-d_jk);
}
/**
* Returns a value from the set, assuming that all values are positive. If empty, -1 is returned.
* @param a the set to get a value of
* @return a value from the set, or -1 if empty
*/
private static int getVal(Set a)
{
for(int i : a)
return i;
return -1;
}
@Override
public double dissimilarity(int i, int ni, int j, int nj, double[][] distanceMatrix)
{
return getDistance(distanceMatrix, i, j);
}
@Override
public double dissimilarity(int i, int ni, int j, int nj, int k, int nk, double[][] distanceMatrix)
{
double d_ik = getDistance(distanceMatrix, i, k);
double d_jk = getDistance(distanceMatrix, j, k);
double d_ij = getDistance(distanceMatrix, i, j);
return dissimilarity(ni, nj, nk, d_ij, d_ik, 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,
* (Ci ∪ Cj), with the cluster k. This method is
* used by other algorithms to perform an update of the distance matrix in
* an efficient manner.
*
* @param ni the number of items in the cluster represented by i
* @param nj the number of items in the cluster represented by j
* @param nk the number of items in the cluster represented by k
* @param d_ij the distance between clusters i and j
* @param d_ik the distance between clusters i and k
* @param d_jk the distance between clusters j and k
* @return the distance between the cluster formed from i and j, to the cluster k
*/
public double dissimilarity(int ni, int nj, int nk, double d_ij, double d_ik, double d_jk)
{
return aConst(true, ni, nj, nk) * d_ik +
aConst(false, ni, nj, nk) * d_jk +
bConst(ni, nj, nk) * d_ij +
cConst(ni, nj, nk) * abs(d_ik-d_jk);
}
@Override
abstract public LanceWilliamsDissimilarity clone();
}
Ads help maintain this website.