[머신러닝] 군집분석 (Cluster Analysis)

군집분석

- 군집분석(cluster analysis)은 각 개체에 대해 관측된 여러 개의 변수 값들로부터 n개의 개체를 유사한 성격을 가지는 몇 개의 군집으로 집단화하고, 형성된 군집들의 특성을 파악하여 군집들 사이의 관계를 분석하는 다변량분석 기법이다. 

- 군집화의 방법에는 계층적군집, 분리(partitioning)군집, 밀도-기반군집, 모형-기반군집, 격자-기반군집, 커널-기반군집, 코호넨군집, 고차원데이터를 위한 방법 등이 있다.

 

1 계층적군집

- 계층적군집(hierarchical clustering)은 가장 유사한 개체를 묶어 나가는 과정을 반복하여 원하는 갯수의 군집을 형성하는 방법이다. 보통 계통도 또는 덴드로그램(dendrogram)의 형 태로 결과가 주어지며 각 개체는 하나의 군집에만 속하게 된다. 개체간의 유사성(또는 거 리)에 대한 다양한 정의가 가능하며, 군집간의 연결법(최단연결법, 최장연결법, 평균연결법, 중심연결법, 와드연결법)에 따라 군집의 결과가 달라질 수 있다.

 

- 계층적 군집의 결과는 다음과 같이 덴드로그램(dendrogram)의 형태로 표현된다. 이 그림 을 통해 군집들 간의 구조적 관계를 쉽게 살펴볼 수 있다. 이 구조를 통해서 항목간의 거 리, 군집간의 거리를 알 수 있고 군집 내의 항목 간 유사정도를 파악함으로써 군집의 견고 성을 해석할 수 있다.

- 계층적군집을 수행할 때 두 군집간의 거리를 측정하는 방법에 따라 병합방법이 달라진다. 거리측정(또는 병합) 방법에는 최단연결법, 최장연결법, 중심연결법, 평균연결법, 와드연결법 이 있다.

- 최단연결법 또는 단일연결법(single linkage method)은 두 군집 사이의 거리를 각 군집 에서 하나씩 관측 값을 뽑았을 때 나타날 수 있는 거리의 최솟값으로 측정한다. 최단거리를 사용할 때 사슬 모양으로 생길 수 있으며, 고립된 군집을 찾는데 중점을 둔 방법이다.

- 최장연결법 또는 완전연결법(complete linkage method)은 두 군집 사이의 거리를 각 군집에서 하나씩 관측 값을 뽑았을 때 나타날 수 있는 거리의 최댓값으로 측정한다. 같은 군집에 속하는 관측치는 알려진 최대 거리보다 짧으며, 군집들의 내부 응집성에 중점을 둔 방법이다. 
- 중심연결법(centroid linkage)은 두 군집의 중심 간의 거리를 측정한다. 두 군집이 결합될 때 새로운 군집의 평균은 가중평균을 통해 구해진다.
- 평균연결법(average linkage)은 모든 항목에 대한 거리 평균을 구하면서 군집화를 하기 때문에 계산양이 불필요하게 많아질 수 있다. 
- 마지막으로 와드연결법(Ward linkage)은 군집간의 거리에 기반하는 다른 연결법과는 달리 군집내의 오차제곱합(error sum of square)에 기초하여 군집을 수행한다. 보통 두 군집이 합해지면 병합된 군집의 오차제곱합은 병합 이전 각 군집의 오차제곱합의 합 보다 커지게 되는데, 그 증가량이 가장 작아지는 방향으로 군집을 형성해 나가는 방법이다. 와드연결
법은 크기가 비슷한 군집끼리 병합하는 경향이 있다

 

 

2 k-평균군집
- k-평균군집(k-means clustering)은 원하는 군집 수만큼(k개) 초기값을 지정하고, 각 개체(데이터)를 가까운 초기값에 할당하여 군집을 형성한 뒤, 각 군집의 평균을 재계산하여 초기값을 갱신한다. 갱신된 값에 대해 위의 할당과정을 반복하여 k개의 최종군집을 형성한다. 

 

k-평균군집의 절차(알고리즘)는 다음과 같다.
단계1. 초기 (군집의) 중심으로 k개의 객체를 임의로 선택한다. 

단계2. 각 자료를 가장 가까운 군집 중심에 할당한다. 

단계3. 각 군집 내의 자료들의 평균을 계산하여 군집의 중심을 갱신(update)한다. 

단계4. 군집 중심의 변화가 거의 없을 때(또는 최대 반복수)까지 단계2와 단계3를 반복한다.

 

k-평균군집의 절차

 

- k-평균군집에서 군집의 수(k)는 미리 정해 주어야 하며, k-개의 초기 중심값은 임의로 선택될 수 있으나, 자료값 중에서 무작위로 선택하는 것이 보다 편리할 것이다. 다만 초기 중심점들은 서로 멀리 떨어져 있는 것이 바람직하며, 초기값에 따라 군집 결과가 크게 달라질 수 있다. 또한 k-평균군집은 군집의 매 단계마다 군집 중심으로부터의 오차제곱합을 최소화하는 방향으로 군집을 형성해나가는(부분 최적화를 수행하는) 탐욕적(greedy) 알고리즘으로 간주될 수 있으며, 안정된 군집은 보장하나 전체적으로 최적이라는 것은 보장하지 못한다. 
 - k-평균군집은 알고리즘이 단순하며, 빠르게 수행되며 계층적 군집보다 많은 양의 자료를 다룰 수 있으며, 평균 등 거리 계산에 기반하므로 모든 변수가 연속적이어야 한다. 단점으로는 잡음이나 이상점에 영향을 많이 받으며(군집의 중심을 계산하는 과정에서), 볼록한 형태가 아닌(non-convex) 군집(예를 들어, U-형태의 군집)이 존재할 경우에는 성능이 떨어진다.

 

- k-평균군집을 수행하는 R 함수에는 kmeans{stats}, kcca{flexclust}, cclust{flexclust}, cclust{cclust}, Kmeans{amap} 등이 있다. Kmeans{amap}은 kmeans{stats}와 그 사용법 이 유사하다. k-평균군집과 유사한 k-중앙값군집(k-medoids clusting)은 pam() 함수를 통 해 수행할 수 있다. pam은 partitioning around medoids를 의미한다