비지도학습과 클러스터링

비지도 학습에서의 군집분석

---

머신 러닝은 크게는 두 가지,

지도학습과 비지도학습으로 나뉜다.

지도학습은 이미 결과를 알고 있는, label이 있는 데이터를 예측하거나 분류하는 것이다.

반면 비지도학습은 label이 없는 데이터에서 패턴을 발견하고, 숨겨진 구조를 찾아내는 것이다.

가장 대표적인 비지도학습으로 군집분석이 있다.

아래의 그림을 보자.

왼쪽의 점들은 A, B라는 label, 즉 그들의 정체가 밝혀져 있다.

오른쪽 점들은 그것들의 정체를 가려 놓은 것이다.

왼쪽 데이터의 경우, 직선 하나를 그어 놓고 점들을 분류한다고 생각해보자. 

우리는 그들의 정체를 알고 있기 때문에, 분류에 대한 평가까지 할 수 있다.

만약 직선 위의 데이터라면 A. 직선 아래의 데이터라면 B이다. 

A,B 라는 기준에 따라 이리저리 선을 긋다 보면 위와 같이 적당한 분류를 하는 선을 그을 수 있다.

또한, 총 14개의 데이터중 2개가 다른 위치에 있기 때문에 2/14 라는 오답율까지 구할 수 있으며, 

새로운 데이터가 들어왔을 때 A 혹은 B 라고 정해줄 수도 있다.

이제 오른쪽의 상황을 생각해보자. 우리는 저 까만 점들의 정체를 알 수 없다.

그렇기 때문에 직선을 그어 그들을 평가할만한 기준이 없는 것이다.

하지만 데이터들의 패턴을 발견할 수는 있다. 위 데이터는 두 개의 지점을 기준으로 군집을 형성하고 있다는 것이다.

따라서, 그림과 같이 두 개의 군집으로 우리는 저 데이터를 나눌 수 있다.

이것이 군집분석과 비지도학습의 매우 간단한 개요이다.

---

K-means 알고리즘

군집분석의 가장 유명한 알고리즘은 k-means 알고리즘이다.

물론 원형 그대로의 알고리즘을 사용하는 경우는 거의 없지만, 케이민즈 알고리즘은 구현이 매우 쉽고 효율적인 계산 때문에 여전히 인기가 많은 알고리즘 중에 하나이다. k-means ++ 등의 발전된 알고리즘을 주로 사용한다.

알고리즘은 다음과 같이 동작한다.

1. 사용자는 하이퍼 파라미터 K를 선택한다. 이에 따라 K개의 클러스터가 생성된다.
2. 모든 데이터들을 1번에서 정해진 K개의 클러스터 중, 가장 가까운 클러스터에 할당한다.
3. 모든 데이터들이 클러스터에 편입되면, 클러스터의 중심을 재설정한다. 클러스터 내 데이터들의 평균점이 클러스터의 중심이 된다.
4. 2~3 번의 과정을 허용 오차 내에 들어올 때 까지 반복한다. 최대 반복 횟수는 사용자가 설정하게 된다.

개체 간의 유사도(거리) 측정 방법

가장 일반적인 것은 연속형 피처들간의 m차원 공간 상의 유클리디안 거리를 통한 측정방법이다.

p = (p₁, p₂,..., p_n)와 q = (q₁, q₂,..., q_n)가 있을때, 두 데이터간의 유클리디안 거리를 이용하여 두 점 p, q의 거리를 계산하는 방법이 기준이 된다. 이 때, 데이터의 피처는 동일한 스케일로 표준화를 적용해야 한다.

K-means ++

기본적인 K-means에서는 초기의 클러스터 센트로이드가 랜덤이다.

하지만 이는 좋지 않은 결과로 수렴하거나, 성능의 저하가 발생하기 때문에 보정이 필요하다.

k-means++ 는 초기의 센트로이드를 서로 가능한 멀리 두는 것이 그 메인 아이디어인데, 자세한 것은 위키피디아의 설명을 참고하자.

1. 데이터 집합으로부터 임의의 데이터를 하나 선택하여 첫 번째 중심으로 설정한다.
2. k개의 중심이 선택될 때 까지 다음의 단계를 반복한다.
   1. 데이터 집합의 각 데이터에 대해서, 해당 데이터와 선택된 중심점들 중 가장 가까운 중심과의 거리 D(x)를 계산한다.
   2. 확률이 D(x)^2에 비례하는 편중 확률 분포를 사용하여 임의의 데이터를 선택한 후, n번째 중심으로 설정한다.
3. 선택된 k개의 중심들을 초기 값으로 하여 K-평균 클러스터링을 수행한다.

---

하드 클러스터링과 소프트 클러스터링

군집분석은 또 다시 두개의 방법으로 설명이 가능하다.

하드 클러스터링 : 하나의 데이터가 정확히 하나의 군집에 할당하는 것

소프트 클러스터링 : 하나의 데이터가 다수의 군집에 할당하는 것

소프트 클러스터링의 대표적인 예로는 Fuzzy C-means 알고리즘이 있다.

일반적으로는 Fuzzy C-means 를 개선한 FCM 알고리즘이 널리 사용되는데

하드 클러스터의 할당을 개별 관측치가 각각의 군집에 속할 확률로 대체한다는 것이 메인 아이디어이다. (Softmax 분류와 유사한 아이디어이다.)

퍼지 씨민즈 역시 위키피디아의 매우 쉽고 직관적인 설명을 참고하자.

K-평균 알고리즘과는 다르게 각 점이 완전히 하나의 클러스터에 속하는 것이 아니라, 해당 클러스터에 속한 정도를 나타내는 수치를 갖는다. 그러므로 각 클러스터의 무게중심은 해당 클러스터에 속한 정도를 비중두어 모든 점들의 평균을 계산한 값이 된다.^[32]

각 데이터에 대해 편중 계수를 임의의 값으로 초기화 한다. 계산된 편중 계수의 변화가 주어진 ${\displaystyle \varepsilon }$보다 작을 때 까지 다음 단계를 반복한다. 계산된 편중 값을 적용하여 각 클러스터의 무게중심을 계산한다. 데이터가 각 클러스터에 속한 정도를 계산하여 새로운 편중 계수로 설정한다.

---

클러스터링의 성능의 최적화하는 방법은 여러가지가 있지만, 그 중 대표적인 것들만을 소개하려 한다.

1. 엘보우 메서드(Elbow Method)

최적의 군집 개수를 찾기 위해 관찰적 방법을 동원할 수 있다.

EDA(탐색적 데이터 분석)와 더불어, 데이터나 하이퍼 파라미터를 관찰하는 방법은 데이터 분석에서 매우 간단하지만 언제나 강력한 방법이다.

클러스터링에서는 그 방법으로, 성능을 최적화 파라미터를 관찰하는 엘보우 메서드를 사용할 수 있다. 아이디어는 다음과 같다.

K-means를 통해 구한 군집 내에서, k값의 변화에 따른 SSE를 관찰한다.

왜곡이 가장 빨리 증가하는 시점의 k를 식별함으로써 최적의 군집 개수 검출한다.

위와 같이 클러스터의 개수에 따른 SSE를 관찰함으로써, 엘보우 메서드를 실행할 수 있다.

2. 실루엣 분석(silhouette analysis)

실루엣 분석은 클러스터링의 성능 자체를 수량화하는 것이다.

군집 내의 샘플이 얼마나 결합력 있게 그룹핑 되었는지를 수량화하여 평가한다.

자세한 내용은 역시 위키피디아로.

1986년 Peter J. Rousseeuw에 의해 처음으로 서술된 실루엣은 간단한 방법으로 데이터들이 얼마나 잘 클러스터링 되었는지를 나타낸다.^[22] 하나의 데이터 i 에 대해, 해당 데이터가 속한 클러스터 내부의 데이터들과의 부동성을 ${\displaystyle a(i)}$라 하고, 해당 데이터가 속하지 않은 클러스터들의 내부의 데이터들과의 부동성을 ${\displaystyle b(i)}$라 할 때, 실루엣 ${\displaystyle s(i)}$은 다음과 같이 계산될 수 있다.

${\displaystyle s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}}$

이때 계산된 ${\displaystyle s(i)}$는 다음의 값을 가진다.

${\displaystyle -1\leq s(i)\leq 1}$

${\displaystyle s(i)}$가 1에 가까울 수록 데이터 데이터 i 는 올바른 클러스터에 분류된 것이며, -1에 가까울 수록 잘못된 클러스터에 분류되었음을 나타낸다.

그래프를 통해 실루엣 수치를 확인할 수 있다.

상단 그래프는 3개의 집단의 자료들이 대부분 0.6~0.8 사이의 실루엣 계수로 나타나는 것을 볼 수 있다.

각 집단에서 아래쪽 부분(이상치로 판단 가능)의 비중이 크지 않은 괜찮은 클러스터링이라고 평가할 수 있겠다.

하단 그래프는 동일 자료를 2개의 집단으로 클러스터링한 경우로, 실루엣 계수가 낮아지고 아웃라이어 면적도 증가하는 것을 볼수 있다.

---

계층적 군집 분석

계층적 클러스터링 알고리즘은 계층도를 그릴 수 있는 군집 분석의 종류이다.

의사결정나무와 비슷한 알고리즘이며, 사용법과 장단점 또한 비슷하다.

계층적 클러스터링은 의미 있는 분류체계를 생성하며 결과 이해가 쉽고, 무엇보다 군집의 수를 설정할 필요가 없다.

계층적 클러스터링의 두 가지 방법으로 응집성 계층, 분열성 계층 클러스터링이 존재한다.

분열성 계층 클러스터링은 하나의 군집으로 시작하여, 각각의 군집이 하나의 샘플만을 가질 때 까지 분기를 반복적으로 분기하는 방법이다.

응집성 계층 클러스터링은 분열성 계층 클러스터링과 정 반대의 방식으로 하나의 샘플들이 뭉쳐들어 결국 하나의 군집을 형성하도록 반복적인 병합을 하는 방법이다.

클러스터링 응집의 방법 역시 많은 기준이 있지만, 가장 표준적인 것은 단일기준 결합방식과 완전기준 결합방식이라고 할 수 있다.

단일기준 결합방식(single linkage) : 군집 각각의 데이터를 쌍을 지은 뒤, 가장 유사한 개체간의 거리를 계산. 가장 짧은 거리의 두개 군집 병합

완전기준 결합방식(complete linkage) : 단일기준과 동일한 방식을 사용한 뒤, 가장 짧은 거리 대신 가장 긴 거리를 기준으로 병합.

응집성 클러스터링의 가지치기

의사결정 트리와 마찬가지로, 계층적 군집 트리 역시 leaf node가 단일 샘플일 경우에 문제가 발생한다. 

군집 트리의 가지치기를 시행함으로써 이를 해결할 수 있다.

의사결정트리에서는 depth와 전후 오차비교를 이용하여 가지치기를 시행하는 것과 비슷하게 계층적 군집트리에서는 cluster의 숫자를 지정함으로써 가지치기가 가능하다.

위의 그림은 ID0 ~ ID4로 나누어진 5개의 계층적 군집을 두개의 군집으로 가지치기한 결과를 나타낸 그래프이다.

이해를 돕기 위해 5개를 계층적 군집으로 표현한 원형을 보존한 채 1,0 이라는 레이블을 달아 2개의 군집이라는 것을 나타내었다.

---

클러스터링과 이상치(outlier)

클러스터링에서 이상치에 관한 문제는 가장 크리티컬한 문제중의 하나로 여겨진다.

특히 K-means 등을 활용한 클러스터링의 경우, 이상치에 굉장히 민감한 영향을 받는다.

이에대한 해법 역시 당연히 존재한다.

밀도 기반 희소 클러스터링(DBSCAN, Density-based Spatial Clustering of Applications with Noise)이라는 알고리즘이 대표적이다.

1. 사용자는 이웃 점의 개수를 미리 설정한다.

2. Core point를 iterate 하는 과정에서 설정한 반지름 내에 이웃 점의 개수가 만족되면 Core point로 간주한다. (반지름보다 멀지 않다면 Core point들은 결합된다)

3. 중심점, 경계점이 아닌 점들을 잡음점이라고 한다.

4. 결합된 중심점의 그룹에 대해 분리된 군집을 형성한다. (결합되지 않은 중심점들은 독립된 군집)

5. 각각의 경계점을 자신의 중심점이 포함되는 군집에 할당한다.

DBSCAN은 이상치가 있는 상황에서도 좋은 알고리즘이지만, 구형 클러스터링을 할 때 극적인 성능을 발휘한다.

이 내용 역시 위키피디아를 참고하자.

차원의 저주

클러스터링 역시 차원의 저주 문제를 피해갈 수 없다. 차원의 저주에 관한 내용은 지난 포스팅을 참고.