Class WardLinkage
java.lang.Object
ch.usi.inf.sape.hac.agglomeration.WardLinkage
- All Implemented Interfaces:
AgglomerationMethod
The "Ward", "inner squared distance", "sum of squares", "error sum of squares",
or "minimum variance" method.
This method fuses those two clusters that result in the smallest increase
in the total within-group error sum of squares.
This quantity is defined as the sum of squared deviation
of each object from the centroid of its own cluster.
In contrast to the other methods that use prior criteria,
this method is based on a posterior fusion criterion.
[The data analysis handbook. By Ildiko E. Frank, Roberto Todeschini]
Used only for Euclidean distance!
The general form of the Lance-Williams matrix-update formula:
d[(i,j),k] = ai*d[i,k] + aj*d[j,k] + b*d[i,j] + g*|d[i,k]-d[j,k]|
For the "Ward" method:
ai = (ci+ck)/(ci+cj+ck)
aj = (cj+ck)/(ci+cj+ck)
b = -ck/(ci+cj+ck)
g = 0
Thus:
d[(i,j),k] = (ci+ck)/(ci+cj+ck)*d[i,k] + (cj+ck)/(ci+cj+ck)*d[j,k] - ck/(ci+cj+ck)*d[i,j]
= ( (ci+ck)*d[i,k] + (cj+ck)*d[j,k] - ck*d[i,j] ) / (ci+cj+ck)
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptiondouble
computeDissimilarity
(double dik, double djk, double dij, int ci, int cj, int ck) Compute the dissimilarity between the newly formed cluster (i,j) and the existing cluster k.toString()
-
Constructor Details
-
WardLinkage
public WardLinkage()
-
-
Method Details
-
computeDissimilarity
public double computeDissimilarity(double dik, double djk, double dij, int ci, int cj, int ck) Description copied from interface:AgglomerationMethod
Compute the dissimilarity between the newly formed cluster (i,j) and the existing cluster k.- Specified by:
computeDissimilarity
in interfaceAgglomerationMethod
- Parameters:
dik
- dissimilarity between clusters i and kdjk
- dissimilarity between clusters j and kdij
- dissimilarity between clusters i and jci
- cardinality of cluster icj
- cardinality of cluster jck
- cardinality of cluster k- Returns:
- dissimilarity between cluster (i,j) and cluster k.
-
toString
-