.

그림, 실습코드 등 학습자료 출처 : https://datascienceschool.net

# 계층적 클러스터링

• 클러스터를 물방울 합쳐지듯이 작은 물방울들을 합쳐서 하나의 큰 물방울(클러스터)을 만드는 것과 같다.

• 처음 단계로 하나의 데이터를 하나의 클러스터로 본다. 그러면 데이터가 N개 있으면 클러스터의 갯수도 N개가 되는 것이다. 데이터 하나마다 클러스터가 하나가 있는 것이다. 그 다음 스탭으로 데이터 하나하나 일일히 거리를 측정한 다음에 가장가까운 데이터를 고른다. 이 가장 가까운 데이터들끼리 붙어서 클러스터가 합쳐지게 된다. 그 다음스탭 역시 방금과 같은 방법으로 클러스터를 또 합친다.

• 가장처음에 데이터간의 거리를 계산해야 할때는 이 데이터간의 거리를 계산하는 방법은 여러가지가 있다. 유클리드거리, 코싸인거리 등이 있다.

• 그 다음에 문제가 데이터가 여러개가 묶여있는 클러스터 간의 거리를 계산을 해야하는데 어떻게 해야하는가이다.

• 가장 간단한 방법은 비귀납적인 방법이 있다. 이 방법은 계층적 클러스터링을 쓰던지 안쓰던지 적용할 수 있는 방법이다. 클러스터 두개가 있으면 이 두개사이에 대해서 클러스터링을 정의하는 방법이다. 크게 4가지 방법으로 정의한다.

1) centroid 방법

특정 클러스터 내의 데이터의 평균을 구하면 센트로이드가 나오는데 이 센트로이드와 센트로이드 간의 거리를 측정하는게 클러스터간의 거리를 측정하는 것이다라고 하는 방법이다.

2) single 방법

클러스터 A의 모든 데이터 i와 클러스터 B의 모든 데이터 j의 모든 조합에 대해 거리를 측정해서 최소값을 측정한다.

\[\ d(A,B) = \min(dist(A[i],B[j]))\]

3) complete 방법

싱글방법과 정반대 방법으로 가장 멀리떨어져 있는 거리를 측정한다.

4) average 방법

클러스터 A의 모든 데이터 i와 클러스터 B의 모든 데이터 j의 모든 조합에 대해 거리를 측정한 후 평균을 내보자 라는 방법이다.

• 위의 방법들중 어떤 방법을 쓰던지간에 클러스터 두개가 주어지면 거리를 잴 수 있다. 그래서 저런 방식으로 거리를 측정해서 가장 가까이 붙어있는 클러스터를 하나로 묶는다. 이 방법을 계속하게 되면 한번 할때마다 클러스터가 하나씩 없어지게 된다. 최종적으로는 한개의 클러스터링이 된다.

• 이런과정을 SciPy 패키지는 클러스터링 결과를 tree 형태로 시각화할 수 있는 dendrogram 명령을 이용하면 된다.

• 우리가 계층적 클러스터링을 위해 클러스터간의 거리를 구한다고 하면 비귀잡적 방법을 쓰지 않아도 된다. 비귀납적 방법은 단점이 계산양이 너무 많은게 문제다. 사실상 현실적으로 잘 쓸 수가 없다.

• 비귀납적 방법 말고도 귀납적방법이라는 것을 쓸 수도 있다. 귀납적방법은 클러스터와 클러스터간에 안에 있는 데이터를 보지 않는다.

• 데이터가 몇개가 되었든지 그것은 중요한 요소가 아니다. 내가 만약에 특정 클러스터간의 거리를 측정할때 그 이전에도 클러스터간에 병합과정이 있었을 것이다. 그전단계의 정보를 다음단계 병합시 그대로 쓰겠다는 것이 귀납적방법이다.

• 귀납적 방법에는 크게 세가지가 존재한다.

1) median 방법

센트로이드를 이용하는 방법이다. 각각의 클러스터내에 센트로이드를 만들어진 센트로이드 간에 또 평균을 내서 새로운 센트로이드를 만든다. 그러면 이 센트로이드간에 거리를 측정하는 것이다. 새로운 센트로이드를 만들때 아까 센트로이드 정보를 이용한다는 점이 비귀납적방법과는 다른 방법이다.

2) weighted 방법

만약 클러스터 A가 클러스터가 B와 클러스터와 C가 결합하여 생겼다면(결합한 클러스를 S라고 치자) 다음과 같이 원래 클러스터까지의 두 거리의 평균을 사용한다.

\[\ d(A,S) = (dist(B,S) + dist(C,S))/2\]

3) ward 방법

만약 클러스터 u 가 클러스터 s 와 클러스터 t 가 결합하여 생겼다면 두 클러스터의 거리의 가중평균에서 원래의 두 클래스터 사이의 거리를 보정한 값을 사용한다. 통상 계층적 클러스터링 방법에서 디폴트 방법이 와드방법이다.