Linkages between Objects

By Kardi Teknomo, PhD.

< Previous | Next | Content>

The rule of hierarchical clustering lie on how objects should be grouped into clusters. Given a distance matrix, linkages between objects can be computed through a criterion to compute distance between groups. Most common & basic criteria are

•  Single Linkage: minimum distance criterion

•  Complete Linkage: maximum distance criterion

•  Average Group: average distance criterion

•  Centroid distance criterion

•  Ward: minimize variance of the merge cluster

Jain and Dubes (1988) showed general formula that first proposed by Lance & William (1967) to include most of the most commonly referenced hierarchical clustering called SAHN (sequential, agglomerative, hierarchical and nonoverlapping) clustering method. Distance between existing cluster k with objects and newly formed cluster (r, s) is given as

The values of the parameters are given in the table below.

(After Jain & Dubes, 1988)

In the next section, I will show how to compute hierarchical clustering using Single Linkage Hierarchical Clustering. Other methods of linkages have similar computation with only different in the computational formula.

< Previous | Next | Content>

This tutorial is copyrighted.

Preferable reference for this tutorial is

Teknomo, Kardi. (2009) Hierarchical Clustering Tutorial.
http://people.revoledu.com/kardi/tutorial/clustering/