[ML] Clustering(군집화) model

※해당 게시물에 사용된 일부 자료는 순천향대학교 빅데이터공학과 정영섭 교수님의 머신러닝 전공수업 자료에 기반하였음을 알려드립니다.

 

이번 포스팅에서는 Unsupervised learning의 종류로서 Clustering에 대해 소개하고 Clustering model의 종류에 대해서 알아보자. 목차는 다음과 같다.

 

1. Clustering model 이란?

2. K-means Clustering

3. KNN(K-Nearest Neighbors)

4. Hierarchical Clustering

1. Clustering model 이란?

기본적으로 클러스터링은 비지도 학습방법이므로 label(정답)이 존재하지 않는 상태에서 학습을 한다. 하지만 클러스터링 모델들도 최후의 단계에서는 이 클러스터링 모델이 정답을 잘 맞추느냐 안 맞추느냐에 대한 평가 척도가 있어야 하고 결국엔 일부의 데이터에라도 label(정답)이 존재해야 한다. 

 

Clustering model이란?

 

여기서 label에 대한 정의가 필요하다. label을 정의해주기 위해서는 모델을 사용하는 사용자 마다 다르다. 왜냐하면 각자 해결하려는 문제가 다르기 때문이다. 따라서 label은 어떤 문제인지에 따라 정의되야 한다. 예를 들어, 하마와 기린 데이터가 존재할 때 우리가 해결하려는 문제가 '수컷' 인지 '암컷'인지 분류하는 문제라면 label을 '수컷', '암컷'으로 labeling해주어야 한다는 것이다.

 

2. K-means Clustering

클러스터링 모델의 대표적인 종류로서 K-means에 대해서 알아보자. 간단하게 정의한다면 "K개의 평균값을 중심으로 해서 데이터를 클러스터링(군집화) 시키자!" 로 직관적으로 이해하면 되겠다. 그렇다면 가장 적절한 K값은 어떻게 결정해주어야 할까? 이 때 우리가 할 일이 나타나게 된다. 바로 이 최적의 'K' 값을 찾아주는 것!

 

우리는 최적의 K값을 찾아주어야 한다.

 

2-1. K-means 알고리즘

최적의 K값을 찾아주기 위해서 사용되는 알고리즘이 존재한다. 알고리즘은 다음 4가지의 단계로 iterative(반복적으로)하게 진행되며 최적의 K값을 찾아준다.

 

1. 임의의 K값을 초기값으로 설정하고 K개의 군집 중심을 선택한다.

2. 각 데이터와 각 K개의 중심과 거리가 얼마인지 계산하고 가장 가까운 중심을 선택한다.

3. 군집 중심을 다시 Update한다.

4. 할당된 데이터의 군집이 군집 중심을 업데이트 하기 전, 후로 변경되지 않을 때까지 2,3번째 단계를 반복한다.

하지만 이 때 주의해야 할 것이 하나 있다. 1번의 단계에서 임의의 K값을 자칫 잘못주게 된다면 매우 잘못된 결과로 이어질 수 있는 가능성이 농후하다. 따라서 K값을 초기값으로 어떻게 설정할지에 대한 문제에 직면하게 된다.

 

2-2. 최적의 초기 Cluster 개수(K값) 설정

초기값을 설정하기 위해서는 '관점'에 따라 방법이 달라지는데, 다음과 같은 방법들이 존재한다.

 

• Hierarchical Clustering : 완전 밑바닥부터 끝까지 bottom-up 방식으로 모두 계층화시킨다.

• Elbow-method : 여러 후보 k값들 중 적절함을 평가하고 적절한 초기값을 선정한다. 이때 적절함을 평가하는 척도는 예를들어 군집 중심으로부터 거리를 계산하는 등 다양한 방법 중 선택한다. 이 방법은 Grid-search 처럼 일일이 시행하면서 최적의 k의 초기값을 설정한다.

• Information Criterion Approach : 클러스터링 모델에 대해 likelihood(조건부확률)을 점수로 계산한다. K-means의 경우에는 Gaussian Mixture model을 활용해 likelihood를 계산한다.

• Rule of thumb : 간단한 공식을 따른다. 공식은 바로 하단의 그림이다. 이 때 n은 데이터의 개수이다.

Rule of thumb 공식

 

#참고로 만약 특정한 데이터가 두 개의 군집 중심간의 거리가 각각 동일하다면 알고리즘 자체에서 기준을 하나 설정해서 하나의 군집으로 선택한다. 기준이란 예를 들어 '앞의 순서를 먼저 선택한다거나 랜덤샘플링을 통해 선택한다거나 등등..' 이런 기준이 되겠다.

 

2-3. K-means의 한계

K-means 알고리즘은 다음과 같은 한계점들이 존재한다.

 

• 위에서도 언급했지만 k값의 초기값에 의해 잘못된 결과가 도출될 가능성이 있다.

• 이상치에 취약하다.

이상치에 취약하다는 한계를 극복하기 위해 이상치를 제거하고 클러스터링을 한다거나 K-medoids 알고리즘을 사용한다. K-medoids 알고리즘이란, 클러스터 중심을 평균값이 아닌 '데이터' 하나를 선택해 그 '데이터'를 중심으로 가정하는 것이다.

 

3. KNN(K-Nearest Neighbors)

#KNN은 우선 클러스터링으로서 사용될 순 있지만 클러스터링을 '위한' 알고리즘은 아님을 참고하자.

 

KNN은 쉽게 말하면 '유유상종' 이라는 사자성어를 비유로 들 수 있겠다. 즉, 새로운 데이터를 맞닥뜨렸을 때 "어 이 데이터 내가 본 것중에 어떤 거랑 제일 비슷하네!" 라는 식으로 이미 경험했던 데이터로 분류하는 것이다.

 

KNN은 Instance-based learning이라는 방식을 사용한다. Instance-based learning이란, 데이터 자체만 본다는 것이다. 즉, 학습데이터로 Parameter를 학습하는 게 아니라 학습, 테스트 데이터를 서로 직접 비교한다. 따라서 KNN은 Non-parametric 모델이다. 또한 데이터끼리 비교해야 하므로 학습 데이터의 label(정답)을 참고해 테스트 데이터의 label을 맞추기 때문에 학습데이터의 label을 알고 있어야 한다. 그러므로 KNN은 Supervised learning이기도 하다. 하지만 전체 데이터 셋 중 일부의 데이터(학습 데이터)의 label만 알고 있는 상태므로 Semi-supervised learning이라고 할 수 있겠다.

 

간단하게 KNN에서 K=3일때의 예시를 그림으로 알아보자.

 

K=3일때의 KNN 모델

 

위 그림처럼 K=3일때를 보자. 해당 동그라미 경계선(클러스팅이라고 할 수 있겠다.)안에 Test data인 검은색 별표가 들어가 있고 또 CLASS 'A'인 파란색 동그라미는 1개, CLASS 'B'인 주황색 동그라미는 2개가 존재한다. 이 때 동그라미 경계선 안에 주황색 동그라미가 파란색 동그라미보다 갯수가 1개 더 많고 이는 결국 모델이 "아! 동그라미 경계선 안에 별표 데이터가 들어왔는데 동시에 주황색 동그라미가 2개나 있네? 그러면 주황색 동그라미랑 같은 CLASS 'B' 이겠구나!" 라고 판단하고 분류한다는 것이다.

 

그렇다면 이 때 K값은 또 어떻게 찾아줄까? 이 k값 또한 Grid-search 방식으로 일일이 이거저거 해보면서 최적의 k값을 찾아야 한다.

 

4. Hierarchical Clustering

'계층적 군집화' 라고 불리우는 Hierarchical Clustering은 우리가 앞서 배웠던 K-means 알고리즘에서 최적의 K값을 찾아주기 위한 방법 중 하나로 언급됬었다. 이 계층적 군집화의 단계적인 알고리즘부터 알아보자.

 

계층적 군집화는 어떻게 진행되는 걸까?

#위 그림의 초록색 동그라미는 하나의 데이터를 의미한다.

 

<Hierarchical Clustering의 알고리즘>

1. 각 데이터 한 개를 하나의 클러스터로 가정하고 시작을 한다. 
2. 데이터 2개씩 짝지어 Pair들을 만들고 그 사이의 distance를 계산한다. 여기서 distance를 계산할 때 어떤 distance function을 사용할지 선택해야 한다.
3. 가장 distance가 작은 Pair를 하나의 클러스터로 묶는다. 여기서 가장 distance가 작다고 하는 것은 가장 Similar 하다는 뜻이다.
4. 모든 데이터가 하나의 클러스터로 묶이지 않았으면 2, 3번 단계를 계속적으로 반복한다.(iterative)

위의 그림을 보면서 알고리즘 과정이 잘 이해가 가지 않는다면 밑의 Distance Matrix를 살펴보면서 차근차근 이해해보자. Distance Matrix에서 예를 들어 (2,1)의 값이 1이라고 하면 '2번데이터'와 '1번데이터' 사이의 거리는 '1'이라는 의미이다.

 

Distance Matrix를 통해 알고리즘 이해하기

 

위 그림의 노란색으로 칠해진 부분은 각 데이터들 간의 거리 조합 중 가장 거리가 가까운 값을 의미하고 노란색으로 칠해진 부분에 해당하는 행과 열의 데이터를 클러스터링 하면서 점진적으로 응집된 클러스터링을 만들어가게 된다.

 

#참고로 그림 밑의 Decision Tree 구조같이 되어 있는 그림은 'Dendrogram'이라는 그래프인데 사전적인 정의로는 '나무를 나타내는 diagram'으로 Hierarchical clustering 알고리즘 프로세스를 나타내는 것이다.

 

4-1. Hierarchical Clustering Variants

계층적 군집화의 변형이 존재한다. 그렇다면 이게 대체 왜 필요할까? 다음 그림을 보자.

 

계층적 군집화의 변형이 필요한 이유는 뭘까?

 

위와 같이 데이터들이 존재한다고 가정해보자. 이제 클러스터링을 해야 하는데 각 클러스터링 내부에 존재하는 여러가지 데이터들 중 어떤 데이터를 기준으로 해서 거리를 계산할까? 가장 가까운 데이터? 가장 먼 데이터? 이제 이러한 '기준'을 정하기 위해서 몇 가지 변형들이 존재한다.

 

4-1.1 Single-link : 두 클러스터 내의 데이터 중 각각 가장 가까운 거리로 계산하여 클러스터링 하는 방법이다.

 

Single-link

 

4-1.2 Complete-link : 두 클러스터 내의 데이터 중 각각 가장 먼 거리로 계산하여 클러스터링 하는 방법이다.

 

Complete-link

 

4-1.3 Average-link : 나올 수 있는 모든 데이터들 간의 거리를 평균내어 그 평균값으로 계산해 클러스터링하는 방법이다.

 

Average-link

 

이렇게 해서 Clustering에 대한 여러가지 내용을 살펴보았다. 하지만 빠진 내용이 하나 있는데 바로 'Distance function'에 대한 내용이다. 이 Distance function에 대해 종류가 뭐가 있고 장단점이 무엇이 있는지에 대해서는 다음 포스팅에서 다루려고 한다.