[Data Analysis 개념] Clustering(1) - K-means/K-medoids

1. Clustering - 군집분석

 군집분석은 비지도학습(unsupervised learning)의 일종으로 유사한 데이터끼리 그룹화를 시키는 학습모델을 말한다. 각 데이터의 유사성을 측정하여, 유사성이 높은 집단끼리 분류하고 군집간에 상이성을 규명하는 방법이다. 군

 위의 그림을 보면 raw data에는 여러가지 종류가 섞여있다. 섞여있는 raw data를 군집분석을 통해 서로 다른 특성을 가진 군집으로 분류한다. 이때, 분류문제와는 다르게 target Y가 존재하지 않는다. 그렇기에 학습과정에 있어서 정답을 맞출 기준표가 없는 것이다. 

 위의 그림은 기사에 대한 군집분석을 보여준다. 각 군집은 이슈별로 정리된 결과를 도출했다. 이처럼 군집분석은 raw data에서 segmentation을 통해 insight를 도출하고, 이를 특정 활용하여 마케팅/특정 프로모션등으로 활용할 수 있다. 물론 군집 별 추가 분석을 수행하여 새로운 더 심화적인 insight를 도출할 수도 있다. 

 이러한Clustering의 종류로는 대표적으로

K-means clustering : 데이터를 사용자가 지정한 k개의 군집으로 나눈다.

Hierarchical clustering : 나무 모양의 계층적 구조를 형성하여 군집분석을 수행한다.  

DBSCAN : k개를 설정할 필요없이 인근에 있는 데이터를 따라가며 군집화 할 수 있다. 

와 같은 종류들이 있다. 

 

2. K-means

 

 K-means clustering은 각 군집에 할당된 포인트들의 평균 좌표를 이용해서 중심점을 반복적으로 업데이트하며 군집을 형성하는 알고리즘이다. 학습과정은 다음과 같다. 

1. 각 데이터 포인트에 대해서 가장 가까운 중심점을 찾고, 그 중심점에 해당하는 군집을 할당한다.

2. 할당된 군집을 기반으로 새로운 중심을 계산한다. 중심점은 군집 내부 점들의 좌표 평균으로 한다.

3. 각 클러스터의 할당된 중심점이 바뀌지 않을 때까지 반복한다.

아래 그림을 봐보자. 

 먼저 raw data상태인 (a)에서는 아무런 포인트와 군집이 형성되지 않는다. (b)에서처럼 포인트를 할당한다. 이때 포인트의 개수는 사용자가 직접 K를 지정해주어야 한다. 위의 그림에서는 K=2이다. 이 포인트를 기반으로 (c)에서처럼 가까운 점들을 분류한다. (d)에서 분류된 점들의 중심점을 찾기위해 평균을 사용하여 군집의 중심점 방향으로 포인트를 업데이트 시킨다. (e)에서는 업데이트된 포인트에 맞게 다시 군집을 재형성한다. (f) 다시 포인트를 찾으며 더이상 이 할당된 점이 바뀌지 않으면 학습을 종료한다. 

 이떄, 포인트와 해당 군집에 대해서 거리를 기반으로 평균을 내고 학습을 진행한다. 이때 사용되는 거리는 대표적으로 Manhattan distance와 Euclidean distance가 존재한다. Manhattan distance는 쉽게말해서 지도에서 사용하는 거리방식이고 Euclidean distance는 점과 점 사이의 가장 짧은 거리를 계산하는 방식이다. 수식은 아래와 같다.

 

 여태까지 K-means의 학습방법에 대해서 알아보았다. 그리고 군집을 형성할 개수(중심점 개수) K는 사용자가 직접 지정해야하는 parameter라고 하였다. 그렇다면 최적의 K를 어떻게 정해야하나? 이 K를 설정하는 대표적인 방법은 Elbow method와 Silhouette method가 있다. 

Elbow method

 Elbow method는 군집간 분산(BSS; Between cluster Sum of Squares)과 전체분산(TSS = BSS + WSS)의 비율을 고려하는 것이다. 

WSS(Within cluster Sum of Squares)의 수식은 아래와 같다.

TSS(Total Sum of Squares)의 수식은 아래와 같다. 

 이를 활용하여, 군집간 분산과 전체 분산의 비율은 아래와 같이 표현할 수 있다. 

 이때, 비율의 한계비용(marginal cost)이 완곡하게 줄어드는 지점이 최적의 클러스터 개수이다. 

또한, WWS를 통해 비율의 한계비용(marginal cost)이 줄어드는 지점이 최적의 클러스터 개수로 볼 수도 있다.

 

 

Silhouette method

 Silhouette method는 객체와 그 객체가 속한 군집의 데이터들과의 비유사성(dissimilarity)을 계산하는 방법이다. 그리고 Silhouette method는 elbow method에 비해 상대적으로 간단하다. 

 

 a(i)는 객체i와 그 객체가 속한 군집의 데이터들과의 비유사성을 뜻한다. 여기서 g(x_i)는 x_i가 속한 군집을 말한다.

 b(i)는 그 객체가 속하지 않은 다른 군집의 모든 데이터들과의 비유사성의 최소값을 말한다(즉, 가장 가까운 군집을 말한다). 여기서 g_k는 x_i가 속하지 않은 다른 군집 k를 말한다. 

 

 이렇게 a(i)와 b(i)가 정의되었다면, 실루엣 s(i)는 아래와 같이 계산된다.

 여기서 s(i)의 값이 1에 가까울수록 객체 i는 올바른 클러스터에 분류된 것이다. 그리고 k를 증가시키면서 평균 실루엣 값(silhouette coefficient)이 최대가 되는 k를 선택한다.

 이 위의 예시를 본다면 1에 가장 가까운 k=3를 선택해야 하는 것이다. 

 

3. K-medoids

 

 앞에서 K-means clustering에 대해서 알아보았다. K-means clustering은 초기 중심 값에 민감한 반응을 보이고, 노이즈와 아웃라이어에 모델이 민감하다는 단점이 있다. K-medoids는 K-means를 변형한 것으로, 군집의 무게 중심을 구하기 위해서 데이터의 평균대신 중간점(medoids)를 사용하는 것이다. 그로 인해, K-medoids는 데이터의 이상값에 대해서 더 건강한(?) 성능을 보인다.  

 아래 그림의 결과는 K-means와 K-medoids를 비교한 것이다. 이 그림을 보면 K-medoid가 중심값을 더 명확히 설정하였으며, 이는 더 좋은 군집을 형성할 가능성이 높아지는 것이다. 

 

 K-medoids는 대신 데이터 간의 모든 거리 비용을 반복하여 계산해야하기에 K-means보다는 상대적으로 많은 시간이 소요된다. 그리고 K-medoids는 K-means와 동일한 Elbow method와 Silhouette method를 이용하여 최적의 K를 구한다. 

 그리고 K-means와 K-medoids 모두 원형의 군집이 아닌 경우에 군집화를 이루기가 어렵다는 단점이 존재한다.

 

K-means에 대한 python 실습과정은 아래 링크를 통해서 남겨놓겠다.

https://todayisbetterthanyesterday.tistory.com/60

[Python] K-means clustering