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.