Agglomerative Hierarchical Clustering "complete linkage" as opposed to "single linkage" dendrogram

Question

Will any dataset clustered via each of the following methods:

Agglomerative Hierarchical Clustering using "complete linkage" method
Agglomerative Hierarchical Clustering using "single linkage" method

have the same dendrogram structure?

If yes, please help prove it or show a contradicting example (if not).

Spelling is dendrogram and it's worth remembering that the root (good word here) is the same as in dendritic or rhododendron. As the dendron root means tree, the word "tree" is redundant. — Nick Cox, Apr 20 '14 at 15:34
@PeterFlom, same hierarchy with only possible difference at heights — YevgenyM, Apr 20 '14 at 15:37

score 3 · Answer 1 · answered Apr 20 '14 at 18:42

Consider the data set

run linkage clustering with any distance metric or linkage. The result will be the same dendrogram (which consists of a single node, at height infinity).

Alternatively, any data set with two instances will also work.

 0
 1

Will have a dendrogram merging the two nodes at height 1.

On these data sets, any linkage will yield the same results.

score 1 · Answer 2 · answered Apr 20 '14 at 15:42

1

Dendrograms are used to visualize clustering results. Single-linkage and complete-linkage clustering may give different results. Hence, the dendrograms can be different too. However, it is quite likely that there are some special cases where the two methods give the same result. Then, also the dendrograms would be the same.

answered Apr 20 '14 at 15:42

Guest

11

Can you please help build an example that shows a simple dataset clustered using each of the these methods will give different dendogram? – YevgenyM Apr 20 '14 at 15:44

score 1 · Accepted Answer · edited Apr 20 '14 at 15:58

1

They will give different dendrograms in most cases. e.g.

hc1 <- hclust(dist(USArrests), "single")
plot(hc1)
plot(hc1, hang = -1)

hc2 <- hclust(dist(USArrests), "complete")
plot(hc2)
plot(hc2, hang = -1)

edited Apr 20 '14 at 15:58

Nick Cox

56,404
8
127
185

answered Apr 20 '14 at 15:56

Peter Flom

119,535
36
175
383

I also got a relevant example via swiss {datasets} – YevgenyM Apr 20 '14 at 15:59

Agglomerative Hierarchical Clustering "complete linkage" as opposed to "single linkage" dendrogram

3 Answers3