4
$\begingroup$

Agglomerative clustering can use various measures to calculate distance between two clusters, which is then used to decide which two clusters to merge.

Two popular approaches are single-link and complete-link. There seems to be some discrepancy in whether single-link or complete-link is sensitive to outliers. I am stating a few examples below but I am sure that there are many more.

(1) Stanford NLP IR book states "[complete-link] causes sensitivity to outliers".

(2) Chapter 8 in the Data Mining book by Tan and Kumar says the following in the section 8.3.2:

"The single link technique is good at handling non-elliptical shapes, but is sensitive to noise and outliers."

"Complete link is less susceptible to noise and outliers, but it can break large clusters and it favors globular shapes."

(3) The Applied Multivariate Statistics book says (page 533):

"... single link method which is also very sensitive to errors of measurement, but somewhat robust to outliers. The complete link and Ward’s method tend to find compact clusters of nearly equal size with the clustering solution adversely affected by outliers."

To me it intuitive sense that complete-link is more sensitive to outliers a it uses max over the distances between the points in two given clusters which is a non local measure.

So the question is which one is the correct view? Or maybe both are correct and are saying different things that I do not understand?

Improve this question
$\endgroup$
2
  • $\begingroup$ Without defining or showing example of "outliers" or "noise" it is difficult to speak. Most linkage strategies in hierarchical CA don't assume any specific distribution, such as normal, so as far as "outlier" is defined relative a model distribution - nothing could be judged. There exist many definitions what is "outlier". You must be more concrete. Also, as Anony-Mousse said, you also have to define what is "robust" HCA. $\endgroup$
    – ttnphns
    Commented Sep 23, 2017 at 11:25
  • 2
    $\begingroup$ The topic of your question is an interesting one. I'd like to encourage you - after you arrive of what is outlier and what is robust - to do maybe a simulation study, to investigate, and then post your own answer. $\endgroup$
    – ttnphns
    Commented Sep 23, 2017 at 11:50

2 Answers 2

Reset to default
2
$\begingroup$

The complete link will merge outliers late. Because they increase maximum distances much. It will usually prefer inliers first, which is good. So I'd have assumed it to be more robust than single-link.

But without a good definition of "outlier" and "robust" it is not a well defined claim.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for your answer and @ttnphns thanks for your comments. This makes me wonder on what basis are those books making their claims! $\endgroup$
    – Krrr
    Commented Sep 23, 2017 at 18:02
  • $\begingroup$ You will be surprised how many books are written without having tried all the methods explained. So these claims may, unfortunately, be 'heresay' from some long forgotten source that had an example where the result was subjectively better if you removed the subjective outlier. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Sep 23, 2017 at 21:10
0
$\begingroup$

It depends on what you mean by noise or outliers. A noisy data has many jagged edges (data points) close together, which causes the single linkage to be sensitive to any of these points. An outlier however is a 'far-flung' point; which in this case won't affect the single linkage result. This far flung point in that case influences the complete linkage method.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.