군집분석

계층적 군집화

 

계층적 방법

개체간 거리를 계산한 후 비슷한 개체를 군집화함

병합: n개의 군집들을 가지고 시작해서 최종적으로 하나의 군집이 남을 때까지 순차적으로 유사한 군집들을 병합한다.

 

계층적 방법은 적은 수의 데이터를 다루기에 설명력이 좋아 유리하고, 또 군집 개수를 먼저 지정해줄 필요가 없지만 계산량이 너무나 많기 때문에 현업에서는  k-means 방법을 많이 사용한다고 한다. 계층적 군집분석은 단일연결법, 완전연결법, 평균연결법 등이 있지만 단일연결법(최단거리)에 대해서만 간단하게만 보고 넘어가고, 비계층적 군집분석의 k-means 방법에 대해 알아본다. 유투브 이상철 교수님의 영상에 있는 예시를 토대로 하였다.

 

 

아래의 표는 일단 개체 간의 거리를 미리 구해놓은 행렬이라고 보면 된다. 우선 계층적 방법은 개체 처음부터 한땀한땀 거리를 계산해 나가면서 군집을 형성하게 하는거라 우선 단일연결법 특성상 최단거리를 활용하기 때문에 먼저 Arizona부터 들어가면 거리가 0.76인 Commonweath와 가장 가깝다고 판단하여 우선 군집을 형성시킨다.

 

 

아래의 표에서 색깔이 들어간 것은 위에서 Arizona랑 Commonwealth가 가장 가까워서 이미 군집을 형성했기 때문에 나머지 Boston, Central, NY는 전부 Arizona와 Commonwealth와의 거리를 모두 구해야하고, 이들 중에서 거리가 짧은 것을 선택해야 한다.

 

아래의표는 이제 Arizona와 Commonwealth가 군집으로 형성이 된 단계이고, 이들에 대해서 나머지 Boston, Central, NY와 Arizona, Commonwealth 사이의 거리를 측정해서 색깔있는 곳에 나타낸 것이다. 거리는 각각 2개씩 나오게 되고, 이중에 최솟값을 뽑고, 세 개중에서 또 가장 작은 값을 가지고 군집을 꾸리게 된다.

 

이제 아래 그림은 위의 세개의 색깔 칸중에서 각각 최솟값을 나타낸 것이고 이들중에서 가장 작은 값인 0.77을 가진 Central이 Arizona와Commonwealth가 꾸린 군집에 선정이 되게 되었다.

이제 남은 것은 Central과 NY이다. 계속해서 군집을 만들어가고 있는데, 이미 한번 위에서처럼Arizona와Commonwealth군집에 대한 최단거리로 거리를 하나 구해놨으니 Central과의 거리를 각각 보면 1.47, 2.43이라는 것을 볼 수 있다.

 

아래처럼 이제 다시 또 최솟값을 구하는 과정을 거치게 된다. 

아래의 표처럼 만약 최솟값을 구한 1.47이랑 2.43보다 더 짧은 거리인 1.01이라고해서 Boston이랑 NY가 서로 더 가까운 경우에 또다른 군집을 만들게 된다.

마침내 아래의 표와 덴드로그램과 같은 결과를 얻게 된다.

 

 

비계층적 군집분석

 

k-means는 비계층적 군집분석에 해당한다. 비계층적 군집화는 사전에 군집 수를 결정해주어야 한다. 계층적으로 형성시키지 않고, 개체들을 몇 개의 군집으로 구분시킨다. 

 군집의 수를 사전에 정의하고, 군집 간의 분산을 최소화하도록 각각의 케이스를 k개의 군집들 중 하나에 할당한다.

 초기에 부적절한 병합(분리)이 일어났을 때 회복이 가능하다.

 개체의 수가 많을 때 유용하다.

 

- k-평균 알고리즘

"주어진 데이터를 k개의 군집으로 묶는 알고리즘. 각 클러스터 간의 거리의 분산을 최소화함. "

"EM알고리즘을 기반으로 작동. EM알고리즘은 Expectation 스텝과 Maximization 스텝으로 나뉘고 수렴할 때까지 반복하는 방식이다. 1-각 군집 중심의 위치, 2-각 개체가 어떤 군집에 속해야 하는지 멤버십. 이 두가지를 동시에 찾아야 하기 때문에 EM 알고리즘을 적용한다."

 

 

우선 중심연결법으로 시작을 해보도록 한다. Centroid Method.  아까 위의 예제를 토대로 설명한다.

1.초기세팅 : 임의로 하는 것이다. 어차피 돌리면서 계속 바꿔가기 때문에 거리 뭐 이런게 상관이없다.

군집A : {Arizona, Boston}

군집B : {Central, Commonwealth, NY}

 

군집A의 대푯값은 그 둘의 평균으로 구한다. 아래의 표가 원래 데이터라고 할 때, 3,4번째 열은 1,2 번째 열에 대한 표준화 값((값-평균)/표준편차)이다.

즉 아래의 그림은 위에서 부터 각각 군집A, 군집B를 의미한다. 변수별로 평균값을 준 것이다.

 

저 위에 구한 두개의 대푯값을 각각 군집A,B의 중심점이라하고, 이 중심점에 대해서 모든 개체들과의 거리를 구하게 된다. 그리고 거리가 가까운 쪽으로 군집을 이동하게 된다. 처음에 설정한 군집과는 상관없이 평균을 구해서 계속 다시 계산하면, 평균이 바뀌기 때문에 군집이 또 바뀌게 된다.

 즉, 지금 나뉜 3개 2개 의 군집을 기준으로 또 평균을 구하고, 그 군집들의 대푯값(평균)을 통해 모든 개체에 대해 거리를 또 구하고, 가까운 쪽으로 또 변경을 시켜주게 되는데, 더이상 군집의 이동이 없게 되면 멈추게 된다.

아래의 군집의 평균을 끝으로 클러스터링이 종료되게 된다.

 

 

 

 

 

출처: wikipedia, ratsgo, KC.prof LEE