[Data Mining] 13. Clustering - Non-Hierarchical clustering

Non-Hierarchical clustering

계층적이지 않은 방법으로 군집화를 이룰 수 있는 방법이 몇 가지 있는데 본 챕터에서는 아래 4가지 기법을 소개하고자 한다.

K-means / K-medoids / Model-based / DBSCAN(Density-based)

1. K-means clustering

군집의 수 k를 하이퍼파라미터로 가지는 방법이며, 가장 많이 쓰이는 군집 기법이다.

• Step 0. (Initialize) k=3로 주어졌을 때, 어떤 방법으로든 샘플 3개를 선택해 군집의 중심으로 인식하자.
  ※ 임의의 3개를 선택 할 수도 있고(random), 가장 멀리 떨어진 sample을 선택하는 방법도 있다. (sklearn의 K-means 라이브러리에는 init 파라미터에 k-means++를 지원한다.)
  ※ 초기에 어떤 샘플을 선택했느냐에 따라 하이퍼파라미터 k를 동일하게 셋팅해도 군집의 결과가 달라질 수 있다.

• Step 1. (Assignment) 선택되지 않은 다른 변수들과 3개의 군집 중심간 거리를 구해서 가장 가까운 군집으로 assign 한다.
  ※ 유클리디언 거리를 주로 사용한다

• Step 2. (New Centroids) 군집이 완료되면 각 군집의 중심점이 변경됐을 것이다. 

• Step 3. (Convergence) 새로운 군집의 중심과 샘플간의 거리를 기반으로 Step 1~2를 수렴할 때 까지반복한다.
  ※ 더 이상의 assign이 발생하지 않을 때까지 혹은, Centroids의 변화가 없을 때까지

2. K-medoids clustering

K-means는 모든 점들 좌표의 중심, 즉 평균값을 Centroid로 삼는 알고리즘이다. 위 그림은 K-means의 아쉬운 점을 보여준다. K-means는 outlier에 민감하기 때문에 기대하는 것과 다르게 군집을 이룰 수 있다. (평균값은 Outlier에 취약하기 때문)

vs. 

위 문제를 해결하기 위해 나온 알고리즘이 K-medoids이다.
※ median의 고차원 ver. = medoids

K-means의 군집 중심이 허공에 위치하고 있었다면, K-medoids는 가장 중심에 있는 객체를 중심으로 삼는 것이다. 즉, 평균값을 Centroids로 사용하는 것이 아니라 중앙값을 사용하는 개념이다. 

※ 보다시피 아이디어는 굉장히 좋은데 알고리즘이 너무 복잡해서 아쉽게도 잘 사용되진 않는다.

(부록)K-means-like Algorithm

2009년에 전치혁 교수님 연구실에서 발표한 군집 알고리즘이다. K-means의 동작 원리를 따르지만 Centroid를 갱신하는 것이 아니라 Medoids를 갱신하는 방법이다. 
Chi-Hyunk Jun, Hae-Sang Park, Jong-Seok Lee, "A K-means-like Algorithm for K-medoids Clustering", Expert Systems with Applications(March 2006)

• Step. 1 k=2라면 가장 중앙에 있는 2개를 medoids로 선택한다.

• Step. 2 (Update medoids) 각 medoids와 가까운 샘플들을 찾아 군집한다.

• Step. 3 (Assign object to medoids) 새로운 군집의 중앙값을 새로운 medoids로 설정한다

----------------------------여기까지 정리 완료-----------------------------------

---------------------------11/4 이론3 동영상 시작-------------------------------

3. Model-based Clustering

각 객체가 Gaussian 분포를 가진다고 가정하고 군집하는 것이다.
※ 여러 변수가 있기 때문에 다변량 정규분포를 가진다.

P(x) = Σk=1~K πk F(x | Θk)

F(x | Θk) : 군집 k에 x가 있을 확률 → likelihood

πk : x가 k군집일 확률 → prior

Θ(k) = {μ, Σ} : 군집 k는 평균과 분산을 갖는다.  

P(x) : 

즉 위 문제를 풀기 위해서는 최우추정법(Maximum Likelihood estimation)으로 문제를 풀어야 하는데, missing data에 대해서는 인공적으로 데이터를 만들고 maximize하는 기법을 사용한다.

EM 알고리즘은 missing value때문에 ML알고리즘을 쓸 수 없어서 missing data를 인위적으로 만들어서 maximize 하는 알고리즘이다.

이 EM 모델 기반으로 Gaussian Mixtures를 수행하면

1. expectation : wik를 구한다. (군집에 속할 확률)

2. maximize : wik를 이용해서 k의 평균, k의 비율, k의 공분산을 구한다.

위 2가지를 반복한다.

예제로 좀더 자세히 알아보자.

7개의 데이터가 있고, k=2 군집을 이루고자 한다.

• step. 0 (initialize)
  각각의 wi1, wi2(클러스터 1, 2에 속할 확률)을 random하게 셋팅한다.

• step. 1 wi1, wi2 기반으로 N1, N2 (클러스터 1, 2의 예상 객체수)를 추정한다.
  그럼 π가 정해지고, x1, x2의 추정 평균과 분산을 구한다. 
  이 때 공분산은 0이라 가정한다. (두 변수는 독립이다 가정)

• step. 2 위에서 구한 것들로 wik를 update 해준다.

• step. 3 step 1~2를 수렴 할 때까지 반복한다.
  ※ 군집의 평균, 분산이 변하지 않을 때까지)

※ 위 예제에서 한번만 반복했는데도 O1, 2, 3이 군집2일 확률과 O4, 5, 6이 군집1일 확률이 확연하게 빨리 상승했다.

4. DBSCAN (Density-based Clustering & Outlier Detection)

DBSCAN은 "군집은 군집내 샘플간 밀도가 높을 것이다."가 핵심 아이디어다. 위 그림처럼 오밀조밀 잘 모여있는 그룹(밀도가 높은 샘플들)을 군집화 할 수 있는 것을 기대하는 군집방법이다. 이처럼 Density-based approach는 OPTICS, DENCLUE 등이 있지만 가장 처음 발표된 DBSCAN에 대해서 알아보자.

한 샘플에서 시작해서 특정 threshold보다 높은 밀도를 가진 샘플을 찾아 나가는 것이다.

즉, point P에서 ε만큼의 반지름을 갖는 원을 그렸을 때 그 안에 들어있는 point의 수 Nε(P)가 사용자가 설정한 MinPts보다 많으면 군집으로 설정하는 것이다. 여기서 사용자가 설정해 줘야할 파라미터는 반지름 ε와 MinPts이다. (하이퍼파라미터)

위와 같이 군집하다 보면 point는 3개 종류로 나뉘어 진다.

• Core point : 원의 중심 = high density를 가지고 있는 point

• Boarder point : 군집에 속해 있지만 core point는 될 수 없는 point (boarder point를 중심으로 원을 그려도 MinPts를 만족시키진 못할 수 있다.)

• Outlier(=noise) : 어느 군집에도 속하지 못한 point이며 noise로 판단한다.

DBSCAN의 군집 절차를 보다 일반화 하면 아래와 같다.

• 임의의 점 p를 선택한다.

• p주변의 밀도를 ε과 MinPts를 기준으로 확인한다.

• 만약 p가 core point라면 거리 ε 내에 있는 샘플과 군집을 이룬다.

• 만약 p가 boarder point라면 군집을 이루지 못한 다른 임의의 point로 이동한다.

• 더이상 군집을 이룰 수 없을 때까지 반복한다.

재밌는 사실은, 위와 같은 원리 덕분에 DBSCAN은 군집의 수 k를 미리 설정하지 않아도 알아서 군집을 만들어 주는 효과가 있다. 

물론 DBSCAN의 한계는 있다.

위 사례처럼 데이터가 homogeneous하지 않고 많은 density가 섞여 있으면 파라미터 Eps, MinPts를 설정하기가 어렵거나 불가능하기 때문이다. 

물론 두 파라미터를 어떻게 설정해야 하는 가이드라인은 몇 가지 있는데,
"clustering parameter with k-distance plot, Heuristic method"로 검색하면 찾을 수 있으니 참고하도록 하자.

[Outlier Detection]

DBSCAN과 같이 density를 활용하는 군집방법을 이용하면 Outlier를 탐지할 수 있는 효과를 얻을 수 있다.

LOF(Local Outlier Factor)라는 통계량을 구해서 outlier를 찾을 수 있다. 

수식은 위와 같은데 예제로 보는 것이 더욱 쉬울 듯 하다.

4개의 데이터가 있고, 2개로 군집하고자 하는 문제이다.

(k-distance) dist2(a)는 a에서 2번째 가까운 point까지의 거리를 의미한다. 

(k-distance neighborhood) N2(a)는 a와 가장 가까운 2개 샘플을 의미한다. 

구하고자 하는 값은 LOFk(o) = o의 local reachability density 비율/ neighborhood 계수

LOF2(a) : a를 local로 봤을 때 밀도를 확인하는 척도이며, 크면 density가 낮은 것이다.

이렇게 밀도가 낮은 점들을 찾으면 noise가 아닌 outlier를 찾을 수 있다.