▶EDA :: 계층적 클러스터링[Hierarchical clustering]

▶EDA :: 계층적 클러스터링[Hierarchical clustering]

이번 글에서는 계층적 클러스터링[Hierarchical clustering]에 대하여 살펴보고자한다.

계층적 군집방법 [Hierarchical Clustering]

고차원 또는 다차원 데이터를 시각화하는 데 있어 기본적인 방법 중 하나이며, 사용하기에 매우 간단하다. 아이디어가 대부분의 사람들에게 매우 직관적이며, 고차원의 데이터 셋에서 어떤 일이 일어나고 있는 지에 대해 빠르게 확인할 수 있는 방법이다.

군집분석[Cluster Analysis]의 사전적 정의

균일한 하부 그룹에서 여러 개체들을 그들의 상호 유사성이나 계층 관계 등에 기초하여 배열하는 절차를 말한다.

출처 :  [네이버지식백과] 군집분석, 지구과학사전, 2009.8.30, 북스힐 

복잡하게 생각할 것도 없이 'cluster analysis'라는 검색어를 구글에 입력하면 수백만 건의 문서가 검색된다. 군집분석방법은 현대과학의 다양한 분야에서 적용되는 기법 중 하나이다. 따라서, 계층적 군집방법의 원리를 이해하는 것은 단순히 데이터 시각화 뿐만 아니라 여러면에서 도움이 될 것이라고 생각한다.

계층적 군집화[Hierarchical Clustering]는 이름에서 보여지듯, 이 작업은 쉽게말해 우리의 데이터를 '계층화'하는 작업을 말한다.

계층적 군집방법의 종류

1) 집괴(cluster)적 접근방식

집괴적 접근법은 기본적으로 상향식 접근법이며, 각 개별 데이터부터 시작하여 군집형태의 데이터로 묶어나가기 시작한다. 이러한 수행의 결과로 전체 데이터 셋트가 하나의 큰 군집형태를 이루게 된다.

집과분석이란?

대상 변량들의 변화 양상의 유사도를 표현하는 특정 지수에 근거하여, 그 지수가 증가하는 순서 혹은 감소하는 순서에 따라 변량들을 무리지어 구분하는 통계적 분석 방법.

자료 : 네이버 지식백과, "집괴분석", 해양광학용어사전, 200.5.10.7, 아카데미서적)

흩어져있는 수 많은 작은 조각들이 모이기 시작하다가, 이것들이 조금씩 모이기 시작하면서 작은 공형태로 '무리'가 형성된다. 형성된 무리는 또 다른 무리와 합쳐지게 되면서 결과적으로 대형 군집을 이룬다.

= 데이터 셋에서 서로 가장 가까운 두 개의 점을 찾는 것이다. 그런다음 그 점을 합쳐서 하나로 만들어준다. 이 결과로 나오게될 하나의 상위 점. 데이터셋에는 실제 존지하지 않지만 "새로운 점"으로 여겨지는 "상위점"을 만든다. 이 상위점이 만들어 졌다면, 원래 있던 두 점을 지우고, 합쳐서 만든 점으로 대체한다. 이를 계속 반복하여 그 다음으로 가장 가가운 것들을 찾고, 그것들을 합쳐나간다.

이 접근법에는 두 가지가 중요하다.

1) 거리측정기준으로서 두 점사이의 거리를 어떻게 계산할 것인가?

2) 점들을 합치는 것에 대한 접근방식(두 점이 가장 가깝다고 했을때 어떤 방식으로 그 두 점을 합칠것인가?) 계층적군집이 만들어내는 멋진 형태 중 하나가 바로 '덴드로그램'이라고 부르기도하는 트리이다.

이치에 맞는 측정기준을 가지고 있다면, 좋은 결과를 얻을 수 있겠지만, 

그렇지 않다면(이치에 맞지 않는 측정기준을 가지고 있다면)의미없는 결과를 얻게 될 것이다.

 '거리'를 어떻게 규정할 것인가?

k-means와 같은 대부분의 군집 기법과 마찬가지로, 여기에서도 "어떤 것들이 가깝고, 어떤 것들은 멀리떨어져 있는가"에 대한 정의를 해야할 필요가 있다. 우리가 이 "계층적 군집 방법"을 활용하는 목적이 '언제 어떤 하나가 다른 하나와 다른 것들보다 가까워 지는가"를 보여주는 것이기 때문이다.

k-means알고리즘 : k-means 알고리즘은 각 점에 대해 가장 가까운 클러스터를 찾아 배당하고, 만약 클러스터가 변하지 않으면 정지되는 형태이다. 간단한 알고리즘을 갖으면서도 많은 환경에서 빠르게 수렴된다는 점때문에 다양한 분야에서 활용하고 있다. 위키백과에 따르면, k-means는 대개 처음 주어진 데이터의 개수보다 훨씬 적은 반복만 필요하다고 한다. 

예 : 같은 군집안에 있는 것들은 다른 군집에 있는 것들보다 가깝다.

거리를 정의하고 -> 그룹(군집)화 하여 -> 군집이 의미하는 바를 도출

거리측정에 관한 몇 가지 예시 - 유클리디안/상관관계/이진 거리측정법

1) 유클리디안 거리 측정방식 : 가장 친숙한 방법 중 하나. 두 점간의 직선 상의 거리이다.

2) 상관관계에 따른 측정방식

3) 이진 거리 또는 맨하탄 거리 측정방식

따라서 우리는 문제해결에 합당한 측정방식을 선택야해야한다.

1) 유클리디안 거리 측정방식

---

 가장 친숙한 방법 중 하나.두 점간의 직선 상의 거리이다. 위키백과는 유클리드거리(Eucliean distance)에 대해 "두 점 사이의거리를 계산할 때 흔히 쓰는 방법"이라고 정의하고 있고, 지식백과전에서 '유클리드 알고리즘'의 정의를 찾아보면, "두 개의자연수 x와 y의 최대 공약수(GCD)를 계산하는 알고리즘"^[각주:1]이라고 되어있다.

유클리드의 평생선의 공리와 피타고라스 정리가 섭립하는 n차원 공간으로 직선은 1차원 유클리드 공간을, 평면은 2차원 유클리드공간으로 인식하고. 공간에 대해서는 3차원 유클리드 공간으로 인식한다.

자료 : [두산백과, "유클리드공간"

2) 이진 거리 또는 맨하탄 거리 측정 방식[Manhattan distance, 혹은 택시거리 등]

---

맨해튼 거리[Manhattan distance, 혹은 택시거리 등]에 대한 사전적 정의를 살펴보면, "19세기의 수학자 헤르만 민코프스키가 고안한 용어로, 보통 유클리드 기하학의 거리 공간을 좌표에 표시된 두 점 사이의 거리(절댓값)의 차이에 따른 새로운 거리 공간으로 대신하기도한다."로 되어있다. 

1. [네이버 지식백과] 유클리드 알고리즘 [Euclideans algorithm] (컴퓨터인터넷IT용어대사전, 2011.1.20, 일진사) [본문으로]