군집화(Clustering)
`군집화(Clustering)`이란 예측 모델과 같이 예측을 목적으로 하는 것이 아닌, 데이터가 주어졌을 때 데이터 간에 유사한 속성들을 갖는 관측치들을 묶어 전체 데이터를 몇 개의 군집(그룹)으로 나누는 것을 말한다.
군집화의 기준은 동일한 군집에 소속된 관측치들은 서로 유사할수록 좋으며, 상이한 군집에 소속된 관측치들은 서로 다를수록 좋다.
`분류(Classification)`와 `군집화(Clustering)`의 차이는 다음과 같다.
- 분류 : 사전 정의된 범주가 있는(labeled) 데이터로부터 예측 모델을 학습하는 문제 → `지도학습(Supervised Learning)`
- 군집화 : 사전 정의된 범주가 없는(unlabeled) 데이터에서 최적의 그룹을 찾는 문제 → `비지도학습(Unsupervised Learning)`
군집화를 수행함에 있어 주요한 고려사항은 다음과 같다.
- 어떤 거리 척도를 사용하여 유사도를 측정할 것인가?
- 어떤 군집화 알고리즘을 사용할 것인가?
- 어떻게 최적의 군집 수를 결정할 것인가?
- 어떻게 군집화 결과를 측정/평가할 것인가?
군집화 : 유사도 측정
`유클리디안 거리(Euclidean Distance)`는 일반적으로 사용하는 거리로, 대응되는 관측치 X, Y 값 간 차이 제곱합의 제곱근으로써, 두 관측치 사이의 직선 거리를 의미한다. `맨하탄 거리(Manhattan Distance)`는 X에서 Y로 이동 시 각 좌표축 방향으로만 이동할 경우에 계산되는 거리를 말한다. `마할라노비스 거리(Mahalanobis Distance)`는 변수 내 분산, 변수 간 공분산을 모두 반영하여 X, Y 간 거리를 계산하는 방식이다. 데이터의 `covariance matrix`가 `identity matrix`인 경우에는 유클리디안 거리와 동일하다. `상관계수 거리(Correlation Distance)`는 데이터 각 `Pearson correlation`을 거리 척도로 사용하는 방식으로, 데이터 패턴의 유사도/비유사도를 반영할 수 있다.
군집화 : 알고리즘
계층적 군집화(Hierarchical Clustering)
`계층적 군집화(Hierarchical Clustering`는 계층적 트리모형을 이용하여 개별 개체들을 순차적/계층적으로 유사한 개체/군집과 통합하는 방법이다. 이는 개체들을 가까운 집단부터 차근차근 묶어나가며, 군집화 결과 뿐만 아니라 유사한 개체들이 결합하는 `덴드로그램(dendrogram)`을 통해 시각화가 가능하다. 덴드로그램은 개체들이 결합하는 순서를 나타내는 트리 형태의 구조이다. 계층적 군집화는 덴드로그램 생성 후 적절한 수준에서 자르면 그에 해당하는 군집화 결과를 생성할 수 있다.
계층적 군집화는 먼저 모든 개체들 사이의 거리에 대한 유사도 행렬을 계산하고, 거리가 인접한 관측치끼리 군집을 형성한다. 이후 유사도 행렬을 업데이트하는 과정을 반복하여 군집화를 수행한다. 여기서 두 군집사이의 유사성/거리 측정 방법은 다양하게 있는데, 대표적인 예시로는 `Min(단일연결)`, `Max(완전연결)`, `Group Average(평균연결)`, `between centroid` 등이 있다.
추가적으로 군집 사이의 거리 측정에 많이 쓰이는 방법으로는 `Ward Distance`가 있다. 이는 계층적 군집화에서 비교적 정확한 거리 측정이 가능한 방법이다. 이는 A와 B 두 군집이 있을 때, A와 B 군집을 모두 포함해 중심을 계산하고 중심을 기준으로 각 데이터의 거리의 제곱합을 계산하고, 이후 각 군집별 중심에서의 제곱합을 계산해 빼는 것으로 계산한다.
K-평균 군집화(K-Means Clustering)
`K-평균 군집화(K-Means Clustering)`이란 대표적인 분리형 군집화 알고리즘이다. 여기서 각 군집은 하나의 `중심(centroid)`을 가지며, 각 개체는 가장 가까운 중심에 할당되고 같은 중심에 할당된 개체들이 모여 하나의 군집을 형성한다. 또한 사전에 군집의 수 K가 정해여쟈 알고리즘을 실행할 수 있다.
K-평균 군집화의 수행 절차는 다음과 같다.
- 초기 중심을 K개 임의로 생성
- 개별 관측치로부터 각 중심까지의 거리를 계산한 후, 가장 가까운 중심이 이루는 군집에 관측치 할당
- 각 군집의 중심을 다시 계산
- 중심이 변하지 않을 때까지 2,3의 과정을 반복
여기서 초기 중심은 종종 무작위로 설정되며, 이로 인해 군집화 결과가 초기 중심 설정에 따라 다르게 나타나는 경우가 발생할 수 있다. 초기 중심을 무작위로 설정했을 때 바람직한 결과와 바람직하지 않은 결과를 비교하면 다음과 같다.
이러한 무작위 초기 중심 설정의 위험을 피하고자 다양한 연구들이 진행되었다. 하지만 많은 경우 초기 중심 설정이 최종 결과에 큰 영향을 미치지는 않는다.
- 반복적으로 수행하여 가장 여러 번 나타나는 군집을 사용
- 전체 데이터 중 일부만 샘플링하여 계층적 군집화를 수행한 뒤 초기 군집 중심 설정
- 데이터 분포의 정보를 사용하여 초기 중심 설정
K-평균 군집화는 여러가지 문제점이 있다.
- 서로 다른 크기의 군집을 잘 찾아내지 못함
- 서로 다른 밀도의 군집을 잘 찾아내지 못함
- 지역적 패턴이 존재하는 군집을 판별하기 어려움
군집화 : 최적의 군집 수 결정
앞서 본 K-평균 군집화처럼 군집의 개수를 사전에 알아야 하는 등의 경우에는 최적의 군집 수를 결정할 수 있어야 한다. 만약 해결하고자 하는 문제의 도메인 지식을 가지고 있어 군집의 개수를 지정할 수 있다면 좋겠지만, 그러지 못한 경우 여러 방법론을 통해 결정한다. 먼저, 다양한 군집 수에 대해 성능 평가 지표를 도시하여 최적의 군집 수를 선택한다. 이 경우 `Elbow point`에서 최적 군집 수가 결정되는 경우가 일반적이다.
여기서 대표적인 성능 평가 지표로는 `Sum of Squared Error(SSE)`, `Silhouette`이 있다. 먼저 SSE는 어떠한 군집이 있을 때, 이 군집의 중심으로부터 데이터 간의 거리(차이)의 제곱을 합해 계산된다. 그러나 SSE는 간단하지만 군집 분석의 두가지 목표 중 군집 내의 거리는 최소화하지만, 군집 간의 거리를 최대화하는 부분에 대해서는 고려하지 않는다. 따라서 이를 보완한 것이 Silhouette 계수이며, 다음과 같다. Silhouette 계수는 각 관측치마다 계산되며, 이 평균 값이 0.5보다 크면 일반적으로 군집 결과가 타당하다고 볼 수 있다. 반대로 평균 값이 -1에 가까우면 군집이 전혀 되지 않았음을 의미한다.
이 포스팅은 고려대학교 산업경영공학부 김성범 교수님 유튜브의 핵심 머신러닝 강의를 듣고 작성한 글입니다.
