dm.cs.tu-dortmund.de/en/mlbits/cluster-hac-intro/
Hierarchical Agglomerative Clustering – Lecture Notes
\(\beta\)
\(\gamma\)
input
Single-linkage
\(1/2\)
\(1/2\)
\(0\)
\(-1/2\)
any
Complete-linkage
\(1/2\)
\(1/2\)
\(0\)
\(+1/2\)
any
Average-group-linkage (UPGMA)
\(\tfrac {|A|}{|A|+|B|}\)
\(\tfrac {|B|}{|A|+|B|}\) [...] {-|A||B|\phantom{-^2}}{(|A|+|B|)^2}\)
\(0\)
squared
McQuitty (WPGMA)
\(1/2\)
\(1/2\)
\(0\)
\(0\)
any
Median-linkage (WPGMC)
\(1/2\)
\(1/2\)
\(-1/4\)
\(0\)
squared
Ward
\(\tfrac {|A|+|C|}{|A|+|B|+|C|}\)
\(\tfrac [...] stored, known distances \(d(A, C)\) , \(d(B, C)\) , \(d(A, B)\) . 1
repeat from (2.) until only one entry remains
return dendrogram tree
1
avoid to compute \(d(A\cup B, C)\) directly, as this is expensive: …
