[Data Mining] Hierarchical agglomerative Clustering

지난번 포스팅하고 지지난번 포스팅이 조금 힘들어서 포스팅하기가 살짝 귀찮아지나.. 그래도 한다. 세 개만 더 하고 쉬어야지. Hierarchical agglomerative Clustering를 공부해보자. 이제 드디어 Clustering으로 왔다. Clustering은 간단하다. Decision Tree 같은 것처럼 수학이 그렇게 많이 들어가지 않는다. Cluster는 그룹으로 묶는다는 것을 의미한다. 즉, 데이터를 그룹으로 묶어보겠다는 것이다.

그래. 아주 명확하게 C1과 C2로 나뉠 수 있다. 앞으로 한.. 2개 혹은 3개 정도의 Clustering 관련 포스팅을 할 것인데, 이번 포스팅에서는 Hierarchical agglomerative Clustering을 공부해보도록 하겠다. 간단하게 설명을 해보자. 아래의 data set을 보자.

왼쪽 그림은 그냥 오른쪽 그림의 data set을 그냥 일직선상에 뿌려놓은 것이다. 우선 처음에는 모든 data들이 각각 cluster이다. 즉 10개의 Cluster가 있다. 위의 cluster 중에서 가장 가까운 애들을 먼저 잇는다. 그리고 왼쪽 그림도 또 다시 잇는다.(왼쪽 그림은 오른쪽 그림에서 만들어지는 cluster를 tree로 표현하기 위함이다.)

이제 이어진 저 두 data가 하나의 cluster가 된다. 자 이제 cluster는 9개이다. 이 9개의 distance를 다시 구한다. 대부분 이전에 구한 것과 같겠지만, 묶여진 저 두개와의 거리는 새로 구해야 되겠지. 그렇게 해서 또 다시 가장 가까운 것을 찾는다.

이런 식으로 모든 data가 하나로 묶일 때까지 계속 한다.

여기서 보면, 우리는 아래와 같이 라인으로 나누어서 cluster 개수를 우리가 원하는 것으로 정할 수가 있다. 아래의 그림은 4개로 나누었을 때와 2개로 나누었을 때의 그림이다.

자 그런데 여기서 하나 집고 넘어가자. 젤 처음에 하나의 data가 모두 cluster였을 때는 거리 계산하는데 전혀 문제가 없다. 그런데 그런데 두 개 일 때는 어떻게 계산할까? 말 그대로 위의 두번째 스탭에서의 C1과 C2의 거리는 어찌 계산할까? 계산하는 방법이 여러가지 있다.

최소거리를 이용하여 거리를 계산하는 것을 우리는 Single link라고 한다. 이것과 최대 거리를 이용하여 거리를 구하는 방법인 Complete link를 비교해보자.

출처 : https://www.youtube.com/watch?v=OcoE7JlbXvY

결과가 다르다. 당연히 결과가 다르다. 위의 예제에서 보면 길게 늘어져있는 데이터는 single link가 더 잘 맞지만, 뭉태기로 모여있는 data는 complete link가 더 잘 맞는다. 따라서 사용하고자 하는 data set의 분포도에 따라서 distance 구하는 법을 달리하여 분석하면 된다.

짧은 포스팅이다. Decision Tree 하고 SVM 설명하느라 힘들었으니 이번 포스팅 짧게 마무리 하려한다. 그래도 쓸 내용은 다 썼다!! 다음 포스팅은 k-mean 알고리즘에 대해서 알아보자.