Image Processing Reference
In-Depth Information
7.3 Hierarchical Clustering
Hierarchical clustering is a method of cluster analysis that builds a hierarchy
of clusters. There are two types of hierarchical clustering: agglomerative and
divisive. The result of hierarchical clustering can be presented in a dendro-
gram as shown in Figure 7.2.
It shows how samples are grouped together. Agglomerative clustering
merges clusters iteratively and follows a bottom-up approach. The proce-
dure starts with each object as one cluster and forms a nested sequence by
subsequently merging all the clusters. Grouping can be done on the basis of
the nearest distance measure. It can be (1) a single linkage in which the mini-
mum distance is computed between the clusters (one can set a threshold, and
the clustering is stopped once the distance between the clusters is above the
threshold); (2) a complete linkage where the maximum distance between the
clusters is computed, that is, the farthest distance, and the algorithm stops
when the maximum distance between the nearest clusters exceeds an arbi-
trary threshold and (3) an average that computes the average distance.
The main advantage of agglomerative clustering is that the cluster num-
bers are not fixed and no initialization and optimization criteria are required.
Suppose
X =
{
x
1
,
x
2
, …,
x
n
} are samples for clustering. In level 1, samples are
partitioned randomly into a finite set of
p
0
partitions and all the samples
are considered as single clusters. Then the least distance pair of clusters, say
C
i
and
C
j
, is computed as
d
[
C
i
,
C
j
] = min[
d
(
x
),
d
(
y
)], where the minimum is
computed between all the pairs of clusters. The two clusters
C
i
and
C
j
are
merged to a single cluster. In the next level, the distance matrix is updated by
Level 6
Level 5
Level 4
Level 3
Level 2
Level 1
x
5
x
1
x
2
x
3
x
4
x
6
FIGURE 7.2
Dendrogram.
Search WWH ::
Custom Search