비지도학습과 클러스터링

Programming & Machine Learning/풀어쓰는 머신러닝

비지도학습과 클러스터링

Yamarae 2017. 9. 1. 11:55

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

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

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

지도학습은 이미 결과를 알고 있는, 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++ 는 초기의 센트로이드를 서로 가능한 멀리 두는 것이 그 메인 아이디어인데, 자세한 것은 위키피디아의 설명을 참고하자.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 실루엣 분석(silhouette analysis)

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

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

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

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