[AI/ML] Clustering과 K-means 알고리즘(+Elbow Method, Silhouette Analysis) 정리!

0. 개요

  본 포스팅에서는 Clustering에 대해 알아보고, 대표적 알고리즘인 K-means 알고리즘에 대해 설명한다. 시간이 없다면 증명이나 수식은 넘어가도 무방하나, 개념을 상세하게 풀어 설명했으니 길지만 찬찬히 따라가다 보면 Clustering에 대한 깊은 개념과 중요한 본질을 파악할 수 있을 것이다. 

---

1. Clustering 개념

 

 A. 거리 함수

  Clustering(군집화)란, 주어진 데이터를 특성에 따라 일정 군집(Cluster)으로 나누는, 정답값(label)이 주어지지 않는 대표적인 비지도학습 방식이다. 이때, 비슷하거나 가까운 데이터는 같은 군집에 속하게 하기 위해서, Clustering 간에는 "비슷하거나", "가까운" 것에 대한 정량적 정의가 '거리 함수(Distance Function)'에 의해 정의된다. 쉽게 말해서, 데이터 간에 어떻게 가까운 것을 가깝다고 할 지에 대해 정의해 주어야 한다는 것이다. 이를 위해, 주어진 데이터를 Data Point로써 취급, 일반적인 두 점 사이의 거리를 나타내는 유클리드 거리 (Euclidean Distance)를 거리 함수로 사용해 두 데이터 간 거리를 구하여, 가까울수록 유사하다고 판단하는 것이다. 거리 표현에 있어서, 두 점 사이의 수평/수직 이동거리의 합을 나타내는 맨해튼 거리(Manhattan Distance)도 존재한다.

 

유클리드 거리와 맨해튼 거리 [출처1]

 B. Soft vs Hard Clustering

  또한 Clustering을 진행할 때, 해당 데이터가 오직 하나의 Cluster에만 속하게 할지, 다중 Cluster에 중복하여 속하는 것을 허용할지에 대해서도 결정해야 한다. 전자를 Hard Clustering, 후자를 Soft Clustering이라고 칭한다. 

 

C. Flat vs Hierarchical Clustering

  Clustering을 구별 짓는 또 다른 중요한 특성으로는 Flat Clustering과 Hierarchical Clustering이 있다.

 

  Flat Clustering은 사전에 사용자가 Cardinality(몇 개의 Cluster를 사용할지)를 지정해 주는 방식으로, Unstructured Cluster Set을 반환한다. 이 방식은 직관적이고 효과적이지만, Cardinality를 몇으로 할지 결정하는 것이 아주 어렵고 중요하다. 또한, 최고의 Clustering을 찾기 위해서 Brute Force로 모든 분할 조합을 나열해서 Best Cluster를 선택하는 것이 가장 좋겠지만, 이렇게 찾는 것은 조합의 경우의 수가 너무 많기 때문에, 이것도 합리적인 방식은 아니다.

 이러한 한계 때문에, Flat Clustering에서는 초반 분할을 반복적으로 하여 최적 시작점을 찾은 뒤 분할을 시작한다. 불리한 시작점에서 분할을 시작하면 Global Optimum을 놓칠 수도 있기 때문이다. 

 

  반면 Hierarchical Clustering은 사전에 Cardinality를 지정해 줄 필요가 없으며, Cluster 내부에서 Recursive 하게 Clustering이 수행되기에 계층이 생길 수 있는 Clustering 방식이다. 또한 Structured Cluster Set을 반환하기에 Flat Clustering보다 조금 더 많은 정보를 제공해 준다. 이러한 장점은 Hierarchical Clustering의 복잡도와 비효율성에서 비롯되는데, Flat Clustering에 해당하는 K-means나 EM(Expectation-Maximization) 선형 복잡도를 가지는 데 비해 Hierarchical Clustering은 최소 Quadratic(이차) 이상의 복잡도를 가지게 된다. 

 

D.  Outlier (Noise)

  간혹 데이터가 어느 Cluster에도 속하지 않을 수도 있다. 이는 결측치(Outlier)로 처리되며, 이러한 데이터는 일반적으로 Clustering 알고리즘의 성능을 저하시킬 수 있다.

---

1. K-means Clustering

  이제 대표적인 (Flat) Clustering 알고리즘인 K-means 알고리즘에 대해 알아보자. K-means 알고리즘은 오직 Numeric Data에서만 작동하며, K-means의 최종 목표는 'Cluster Center(Cluster 내 데이터의 평균값)와 각 데이터 간의 Average Squared Euclidean distance(데이터의 위치를 벡터라고 했을 때 종점 간 거리)를 최소화'하는 것이다. (이를 minimizing Inertia라고도 한다.)

Average Squared Euclidean distance. 두 벡터의 종점 간 거리

 

 

  K-means는 다음과 같은 Step을 통해 Clustering를 진행한다. 이를 통해 랜덤한 위치에 Cluster Center를 잡더라도, 샘플링 이후에 해당 샘플들과 평균 계산을 통해 최적의 Cluster Center를 찾아갈 수 있게 된다.

1. 사전 정의된 K개의 Point를 랜덤하게 선택, Cluster Center(=Centroid)로 지정한다.
2. 각각의 데이터와 Cluster Center 간의 거리를 계산하여, 각 Cluster Center와 가장 가까운(유클리드 거리가 가장 짧은) 데이터를 해당 Cluster의 샘플로 업데이트한다.
3. 클러스터에 속하도록 업데이트된 샘플까지 포함하여 Cluster Center를 다시 계산하여 변경한다.
4. Cluster Center의 변화가 없을 때까지(자기 Cluster의 평균이 되었을 때까지) 2~3을 반복한다.

 

여기까지가 K-means 알고리즘의 기본적인 작동원리였다. 그렇다면 위에서도 언급했던, 최적의 K(Cardinality,cluster의 개수)를 찾는 방법은 무엇이 있을까? 대표적으로 Elbow Method과 Silhouette Analysis가 있다. 

 

  A. Elbow Method

  Elbow Method는 K-means의 K값을 (2, n) 개로 점차 증가시키면서 Clustering을 수행하고, 각각의 WCSS(Within Cluster Sum of Squares)를 계산한 그래프를 그려 최적의 K를 찾는 방식이다. WCSS란 영문 그대로 각 데이터와 Cluster Center 간의 거리의 제곱합을 의미한다. 정의를 생각해 보면, K를 늘릴수록 WCSS 값은 서서히 감소할 것이다. Cluster Center가 많아지므로, 중심과 각 데이터 간의 거리는 전체적으로 계속해서 줄어들 것이 때문이다. 이때, WCSS 값의 감소량이 급격하게 작아지는 지점을 최적의 K값이라고 판단하는 것이 Elbow Method이다. (감소량이 줄어들기 시작하는 부분이 팔꿈치 같다고 하여 Elbow Method라고 불린다.)

 

  그러나, Elbow Method에도 나름의 한계점이 존재하는데, 다음의 분포와 그래프를 보자. 직관적으로 우리는 K=5 임을 알 수 있지만, 보다 고차원의 데이터는 이렇게 직관적으로 표현할 수 없기에, Elbow Method를 사용하고자 그래프를 그리면 K=4가 되는 것을 알 수 있다. 왜 이런 것일까? 오른쪽 아래의 두 Cluster는 상대적으로 매우 가깝기 때문에, K가 3에서 4로 갈 때 인접한 두 클러스터의 가운데에 Cluster Center를 설정하여 하나의 Cluster처럼 보면 WCSS가 확 줄어든다. 그러나 4에서 5로 갈 때는 Cluster가 거의 하나에 가깝기 때문에 크게 줄지 않고, Elbow Point가 생기는 것이다. 이처럼 Elbow Method는 이 둘을 하나의 Cluster로 보도록 우리를 착각시키는 경우가 있다.

  또, 다음과 같이 명확한 Elbow Point가 존재하지 않는 경우도 있다. 실제로, Real-world Dataset의 대부분은 이렇게 명확한 Elbow Point가 없는 경우가 많다. 

  B. Silhouette Analysis

  Silhouette Analysis는, Silhouette Score(Silhouette Coefficient의 평균)을 산출하여, 생성된 클러스터 간의 분리 정도를 확인할 수 있는 방법이다. Silhouette Coefficient는, 각 데이터가 자신의 이웃 Cluster(자신이 포함되지 않은 Cluster)와 얼마나 가까운지를 나타내는데, 수식은 다음과 같으며, [-1,+1] 범위의 값을 가지게 된다.

Silhouette Coefficient

  a는 '같은 Cluster 내에서 각 데이터 간의 거리의 평균'을 나타내고, b는 '한 클러스터 내의 데이터와 자신이 포함되지 않은 타 Cluster들 간의 거리의 평균'을 나타낸다. 즉, a가 작으면 같은 Cluster간 응집력이 높고, b가 크면 타 cluster과의 구별이 정확하다. 따라서,

• Silhouette Coefficient이 +1에 가깝다 ==  b>>a == 타 Cluster과는 매우 잘 떨어져 있으며 같은 Cluster 내에서는 응집력이 좋다 ==  데이터들이 올바르게 자신의 Cluster의 중심 쪽에 잘 모여있다 == 잘 분류되어 있다
• 반대로 -1에 가깝다 == b<<a == 타 Cluster과 오히려 가까우며 같은 Cluster 내에서의 거리가 타 Cluster보다 더 멀 정도이다 == 잘못 분류되었다
• 0이다 == b=a == 데이터가 두 Cluster 간의 decision boundary에 걸쳐있다.

와 같이 판단할 수 있게 된다. 이를 바탕으로 다음 plot을 통해, K=5일 때 가장 Silhouette Score가 높은 것을 확인할 수 있고, 최적의 K는 5인 것을 알 수 있다. 또한 Silhouette Score가 Elbow Method보다 조금 더 많은 정보를 제공하는 것을 알 수 있는데, Elbow Method의 WCSS 값은 기울기로써의 의미가 있고 , 값 자체는 큰 의미를 가지지 못하는 반면, Silhouette Score Plot은 K=4도 나쁜 판단은 아니지만, K=5가 최적이다와 같은 유연한 정보를 추가적으로 제공해 주고 있다.

---

2. 정리

  이렇게 Clustering의 종류를 구별하는 중요한 개념들을 학습하였고, K-means 알고리즘과 최적의 K값을 찾는 방법까지 알아보았다. 다음 포스팅에서는 실제 코드로 K-means 알고리즘을 구현해보고, Elbow Method와 Silhouette Analysis plot을 그려보며 K값을 찾아보는 실습을 해 보도록 하겠다!

 

🌼N줄 요약🌼
1. Clustering이란, 라벨링 되지 않은 데이터셋을 통해, 비슷한 특징의 데이터끼리 군집화하는 비지도학습의 대표적 예시
2. 거리 함수를 통해 수치 데이터간 유사도를 파악 
3. Soft Clustering은 한 데이터는 한 군집에만, Hard Clustering은 한 데이터가 여러 군집에 포함가능
4. Flat Clustering:Cardinality(군집 개수)를 미리 정하는 Unstructured Cluster Set, Cardinality 결정이 중요
    Hierarchical Clustering: Cardinality를 미리 정하지 않는 Structured Cluster Set, 높은 복잡도와 비효율성을 지님
5. K-means Clustering: Inertia를 최소화하여 Cluster의 평균값을 Cluster Center로 최적화하는 방법
6.  K-means에서 최적의 K 값을 찾기 위하여, WCSS 감소량의 급감지점을 찾는 Elbow Method와 Cluster간 분리 정도를 바탕으로 잘 분리되었을 때의 K값을 찾는 Silhouette Analysis를 사용한다

---

😊소중한 의견, 피드백 환영합니다!!😊

---

 

 

 

 

 

 

 

[출처 1] https://modulabs.co.kr/blog/cluster-analysis-clustering-grouping

[출처 2] https://medium.com/geekculture/stop-using-the-elbow-method-96bcfbbbe9fd