single link and complete link

single link : 클러스터 안에서 가장 가까운 문서의 유사도를 가지로 클러스터링을 한다.

complete link : 클러스터안에서 가장 먼 문서의 유사도를 가지로 클러스터링을 한다.

 

아래 그림을 보면 왼쪽 그램은 single link이고 오른쪽 그램은 complete link이다.

왼쪽 그램에서 d2를 기준으로 d3와 d6사이의 거리를 계산하는 방식은 single link이고

오른쪽 그램에서 d1을 기준으로 d4와 d6사이의 거리를 계산하는 방식은 complete link이다.

 

single effect로 clustering을 하다보면 결과적으로 d1, d2 d3, d4가 하나의 클러스터로 묶인다.

그런데 d1문서를 기준으로 볼때 d1과 d4사이의 거리가 d1과 d5사이의 거리보다 훨씬 멀다는 것을 알수 있다.

이런 결과로 인해서 기다란 체인 모양으로 클러스터가 생성된는데 이것을 가르켜 chaining effect라고 한다.

 

 

 

출처 : http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html#fig:clustersimilarities