[핸즈온 머신러닝] 챕터 9 비지도 학습 (clustering, k-means, DBSCAN, GMM)

비지도 학습(unsupervised learning)에 대한 파트입니다.

 

챕터 8에서 살펴본 차원 축소(dimension reduction)도 가장 널리 사용되는 unsupervised learning에 해당됩니다. 이번 장에서는 몇 가지 학습과 알고리즘을 살펴봅니다.

 

저는 책의 내용이 너무 방대하고 이 이론을 뒷받침하기엔 설명이 부족하다고 판단하여 주요 개념만 다루려고 합니다.

 

저는 Clustering, K-means, DBSCAN, GMM을 간단히 요약 정리하였습니다.

 

 

1. Overview

 

Unsupervised learing의 문제

• 클러스터링(clustering)
• 차원 압축(dimensionality reduction)
• 이상 감지(anomaly detection)

 

Unsupervised learing의 과제

• 알고리즘이 뭔가 유용한 것을 학습했는지 평가하는 것
• 보통 레이블이 없는 데이터에 적용하기 때문에 무엇이 올바른 출력인지 모름
• 모델이 어떤 일을 잘하고 있는지 이야기하기가 어려움
• 따라서 비지도 학습은 데이터를 더 잘 이해하고 싶을 때 탐석잭 분석 단계에서 많이 사용
• 지도 학습의 전처리 단계에서 사용
• 새롭게 표현된 데이터를 사용해 학습하면 지도 학습의 정확도가 좋아짐

 

그중 챕터 9에서 다루는 내용은 아래와 같습니다.

1. Clustering(군집)
   • 비슷한 샘플끼리 cluster로 묶는다.
2. Outlier detection(이상치 탐지)
   • 정상 데이터가 어떻게 보이는지 학습하고, 비정상 데이터를을 감지하는데 사용한다.
3. Density estimation(밀도 추정)
   • random precess에서 probability density function(PDF)를 추정한다.

 

이 주제에 맞게 K-means, DBSCAN, GMM의 알고리즘을 살펴보도록 하겠습니다. K-means와 DBSCAN이 clustering에 속하고, GMM이 outlier detection과 density estimation에 해당됩니다.

 

 

2. Clustering

 

| Cluster
데이터 분포의 모양

| Clustering
비슷한 샘플을 구별해 하나의 cluser 또는 비슷한 sample의 group으로 할당하는 작업을 말합니다. 즉, dataset을 cluster라는 그룹으로 나누는 작업을 의미합니다.

 

clustering 예시

 

그래서 cluster와 class의 의미는 살짝 다릅니다. 클래스는 단순한 label을 의미하지만, cluster는 분포의 특징을 나타냅니다.

 

위는 유명한 iris dataset의 example입니다.

 

왼쪽의 그림은 labeled data로 classification algorithm이 사용 가능하지만, 오른쪽은 unlabeled data로 clustering으로 classify 할 수 있습니다.

 

실제로 clustering 해본 결과를 살펴보면

 

 

150개의 sample 중에서 5개 sample만 실제 label과 다르다는 결과가 나왔습니다.

 

이제 clustering algorithms 중 하나인 K-means를 살펴보겠습니다.

 

 

3. K-means

K-means algoritnm

k개의 centroids를 설정하고, data point에서 가장 가까운 data point의 거리만큼 clustering합니다.

 

각 cluster의 mean(or centroid)을 계산한 다음 각 data point까지의 distance를 계산합니다. 그런 다음 후자는 가장 가까운 centroid로 식별되는 cluster의 일부로 label이 지정됩니다. 이 프로세스는 일부 수렴 기준이 충족될 때까지 반복됩니다

 

정리하면,

 

1. 데이터 포인트를 가장 가까운 클러스터 중심에 할당
2. 클러스터에 할당된 데이터 포인트의 평균으로 클러스터 중심을 다시 지정
3. 클러스터에 할당되는 데이터 포인트에 변화가 없을 때 알고리즘 종료

예시로 살펴보겠습니다.

 

 

 

sample cluster가 5개로 이루어진 unlabeled dataset로 학습시켜 보겠습니다.

 

먼저 알고리즘이 찾을 클러스터 개수 k를 지정해야 합니다. 각 sampme은 5개의 cluster 중 하나에 할당됩니다.

 

위에서도 설명했지만 여기서 말하는 cluseter는 알고리즘이 sample에 할당한 cluster의 index임을 잊지 말아야 합니다.

 

k-means 알고리즘이 5개의 centroid(중심)를 찾았습니다. sample은 대부분 적절하게 cluster에 할당되었지만, 왼쪽 위에 있는 클러스터와 가운데 클러스터의 경계 부근에서 몇 개가 잘못 구분되었습니다.

 

이는 cluster의 크기가 많이 다를 경우 잘못 구분되고는 하는데요. sample을 cluster에 할당 할 때 centroid까지의 거리를 고려하는 것이 전부이기 때문입니다.

 

이렇듯 k-means algorithm을 hard clustering이라고 설명하기도 합니다. 이는 k-means의 중요한 특징 중 하나입니다.

 

| Hard clustering

Hard assignment of data points to clusters (하나의 data point를 각 cluster에 할당하는 것)

 

k-means algorithm의 작동 방식을 더 살펴보겠습니다.

 

centroid를 random하게 선정 → sample에 label 할당 → update the centroids → sample에 label 할당 ...

 

그리고 알고리즘은 제한된 횟수 안에 수렴되는 것을 보장 받습니다.

 

K-means algorithm은 EM algorithm으로 설명이 되는데 해당 책에선 Expectation과 Maximization 하는 과정은 설명되지 않습니다.

 

 

EM algorithm은 iteration에 따라 distance의 변화가 어느 정도에서 수렴됨을 알 수 있습니다. k-means는 distance metric을 이용하기 때문에 distance의 sum으로써 평가를 할 수 있습니다.

 

Random initialization

 

k-means 기법의 경우 data point가 속한 cluster의 centroid까지의 제곱 거리를 전체 데이터로 합한 것이 목적 함수에 해당합니다.

 

이를 왜곡 척도(distortion measure)이라고도 하며, 이는 초깃값에 의존하는 경향이 있습니다.

 

처음에 어떤 centroid에 data point가 할당되느냐에 따라 결과가 달라집니다. 실제로는 다양한 centroid에서 시작하여 얻은 결과 중 가장 distortion measure이 적은 결과를 사용합니다.

 

위 그래프는 다른 random initial value에 따라 달라진 result를 비교해 볼 수 있습니다.

 

Properites K-means algoritnm

• cluster의 개수는 불명확함
• centroid의 초기 위치에 따라 다른 결과가 나옴
• distance metrics에 대한 한계
  • Euclidean distance는 data에서 information을 얻기에 제한되어 있음
• Hard clustering
  • 각 data point를 각 cluster에 모두 할당함

 

 

4. DBSCAN

DBSCAN은 density-based spatial clustering of applications with noise의 줄임말입니다.

 

Density-Based models

 

Density-Based model(밀도 기반 모델)은 data point의 다양한 density regions에 대해 data space를 탐색하려는 모델 유형입니다.

 

동일한 cluster에서 이러한 영역 내의 data point들을 할당하여 다른 density region을 분리합니다.

 

k-means는 거리를 기반으로 cluster가 할당되었다면, data space의 밀도를 계산하여 관찰되는 나머지 dataset보다 밀도가 더 높다면 cluster를 생성하는 방식입니다.

 

그중 가장 대표적인 것이 이제 설명할 DBSCAN에 해당합니다.

 

이처럼 DBSCAN은 cluster의 개수를 미리 지정할 필요가 없습니다. 복잡한 형상도 잘 찾으며, 어떤 클래스에도 속하지 않는 point도 구분 가능합니다.

 

따라서 DBSCAN은 모든 cluster가 충분히 밀집되어 있고, 밀집되지 않은 지역과 잘 구분될 때 좋은 성능을 냅니다. 

 

작동 방식은 아래와 같습니다.

 

DBSCAN algorithm

 

• 알고리즘이 각 sample에서 작은 거리인 $\epsilon$ 내에 sample이 몇 개 놓여 있는지 셉니다. 이 지역을 샘플의 $\epsilon-neighborhood$이라고 부릅니다.
• $\epsilon-neighborhood$ 내에 적어도 min_samples개 sample이 있다면 이를 core instance로 간주합니다. 즉, core instance는 밀집된 지역에 있는 sample입니다.
• core instance의 이웃에 있는 모든 sample은 동일한 cluster에 속합니다. 이웃에는 다른 core instance가 포함될 수 있습니다. 따라서 core sample의 이웃의 이웃은 계속해서 하나의 cluster를 형성합니다.
• core instance가 아니고 neighborhood도 아닌 sample은 outlier로 판단합니다.

---

책의 설명이 부족한 것 같아 추가로 설명하겠습니다.

 

Parameters

 

DBSCAN에서 사용되는 paramter는 2가지로 eps(epsilon)과 min_pts(min_samples)입니다.

 

• eps: It represents the radius of the neighbourhoods around a data point x.
• min_pts: It is the minimum number of data points that we want in the neighbourhood of a particular point to define a cluster.

data point에서 얼마나 가까워야 하는지를 결정하는 eps가 있고, cluster를 정의하기 위해 특정 point에서 원하는 data point의 최소 갯수(min_pts)를 설정할 수 있습니다.

 

다시 알고리즘의 단계를 정리해 보면

 

1단계: 매개변수 eps 및 min_pts 의 값을 결정합니다.

2단계: dataset에 있는 각 data point(x)에 대해

• 다른 모든 data point로부터의 distance를 계산합니다. 거리가 엡실론(eps) 값보다 작거나 같으면 해당 점을 x의 이웃으로 간주합니다.
• 해당 data point(x)가 min_pts보다 크거나 같은 이웃 수를 얻으면 core point를 방문한 것으로 표시합니다.

3단계: 각 core point에 대해 클러스터에 아직 할당되지 않은 경우 새 cluster를 생성합니다. 또한 모든 인접 포인트를 재귀적으로 결정하여 core point와 동일한 cluster를 할당합니다.

 

사용되는 point의 종류는 총 3가지입니다.

 

• Core Point: A data point is considered to be a core point if it has a minimum number of neighbouring data points (min_pts) at an epsilon distance from it. These min_pts include the original data points also.
• Border Point: A data point that has less than the minimum number of data points needed but has at least one core point in the neighbourhood.
• Noise Point: A data point that is not a core point or a border point is considered noise or an outlier.

 

 

위 이미지에서 순서대로 x, y, z가 core point, border point, noise point에 해당됩니다.

 

• Core Point: The data point x is the core point since it has at least min_pts (n) within epsilon (eps) distance.
• Border Point: The data point y is the border point since it has at least one core point within epsilon (eps) distance and lower than min_pts (n) within epsilon (eps) distance from it.
• Noise Point: The data point z is the noise point since it has no core points within epsilon (eps) distance.

 

K-means algorithm vs. DBSCAN

K-means는 spherical-shaped clusters 또는 convex clusters를 찾기 위한 계층적 클러스터링 작업 즉, 작고 잘 분리된 클러스터에만 적합하며, 노이즈 및 이상값의 존재에도 크게 영향을 받습니다.

 

하지만 실제 데이터에는 다음과 같은 다양한 불규칙성이 포함되는 경우가 많습니다.

• 클러스터는 임의의 모양일 수 있습니다.
• 데이터에 noise point가 포함될 수 있습니다.

이러한 문제를 극복하기 위해 DBSCAN은 다양한 분포에서 k-평균보다 더 합리적인 결과를 생성하기 때문에 사용됩니다.

 

Properites DBSCAN algoritnm

1. 미리 정의된 수의 cluster가 필요하지 않음. 즉, cluster 수의 초기 지정이 필요하지 않음

2. 기본적으로 cluster는 구형이 아닌 clsuter를 포함하여 임의적인 모양과 크기일 수 있음

3. 일반적으로 outlier라고 알려진 noise data를 찾을 수 있음

4. DBSCAN은 모든 형태의 cluster를 찾을 수 있음

5. cluster가 원형이 아니어도 됨

6. DBSCAN은 cluster의 outlier를 포함하지 않음. outlier는 clustering하는 동안 noise로 분류되어 algorithm이 완료 후 cluster에서 제거 됨

7. parameter에 민감함

8. 고차원 데이터의 경우 효과적인 clsuter를 제공하지 않음

 

 

5. GMM(Gaussian mixture models)

 

위에서 k-means의 주요한 특징 중 하나로 hard clustering을 설명했습니다. 이 접근 방식의 한계는 data point가 특정 cluster와 얼마나 연관되어 있는지 알려주는 uncertainty measure이나 probability가 없다는 점입니다.

 

그렇다면 hard clustering 대신에 soft clustering을 사용하는 것은 어떨까요?

 

이 접근 방식이 바로 Gaussian Mixture Model입니다.

 

 

 

이는 GMM의 graph입니다. $\mu$와 $\Sigma$, $\pi$가 paramter이며 $x$는 data point이며, $z$는 random variable에 해당됩니다. 화살표는 edge(=link)에 해당됩니다.

 

이는 조금 더 수식적인 설명이 바탕되었을 때 이해되는 그래프 같긴 하지만, 대충 이론만 살펴보아도 이해할 수 있을 거라 생각합니다. (교재의 p.330을 참고해도 좋습니다.)

 

GMM이란 무엇일까요?

 

Definitions

A Gaussian Mixture is a function that is comprised of several Gaussians, each identified by $k ∈ {1,…, K}$, where $K$ is the number of clusters of our dataset. Each Gaussian $k$ in the mixture is comprised of the following parameters:

 

• A mean $\mu$ that defines its centre.
• A covariance $\Sigma$ that defines its width. This would be equivalent to the dimensions of an ellipsoid in a multivariate scenario.
• A mixing probability $\pi$ that defines how big or small the Gaussian function will be.

 

정리하면, 평균 $\mu$가 중심을 정의하고, 그 너비를 계산하는 covariance $\Sigma$가 있고, gauss function의 크기를 결정하는 mixing probability $\pi$가 있습니다.

 

그래프로 나타내면 아래와 같습니다. $\mu$, $\Sigma$가 각 cluster에서 어떤 역할을 하는지 볼 수 있습니다.

 

 

 

3개의 gaussian function이 나왔으므로 $K=3$입니다. 각 gaussian은 사용 가능한 3개의 cluster에 각가 포함된 data를 설명합니다. 여기서 mixing coeifficient 자체가 probability이며, 각 $\pi$를 합하면 당연히 1이 나옵니다.

 

 

이제 3개의 paramter $\mu$와 $\Sigma$, $\pi$를 살펴보았는데요.

 

이러한 매개변수에 대한 최적의 값의 결정하기 위해 각 gaussian이 각 cluster에 속한 data point에 맞는지 확인해야 합니다. 이것이 바로 maximum likelihood가 하는 일입니다.

 

GMM에서도 EM algorithm을 사용합니다

 

모델의 최적의 parameter를 결정하기 위해 반복적인 방법을 사용합니다.

 

앞에서 짧게 언급하고 지나갔는데, 이는 Expectation — Maximization, 또는 간단하게 부르면 EM algorithm입니다.

 

 

 

3가지의 model parameter가 있습니다.

 

1. $\theta$를 초기화합니다. 예를 들어, K-means를 실행하고 얻은 결과를 algorithm의 초깃값으로 사용할 수도 있습니다.
2. Expectation step:
   • 알고리즘은 각 cluster에 속할 확률을 예측합니다.
3. Maximization step:
   • 각 clsuter가 dataset에 있는 모든 sample을 사용해서 update합니다.
   • cluster에 속할 추정 확률로 sample에 가중치가 적용됩니다.
   • 이 확률을 cluster의 responsibility라고 부릅니다.

 

K-means와 마찬가지로 초깃값에 의해 잘못된 결과를 얻을 가능성을 갖고 있으며, 이를 확인하기 위해 log-likelihood를 통해 검증합니다.

 

 

마찬가지로 일정 수준의 epoch에서 수렴하는 것을 볼 수 있습니다. EM algorithm은 주어진 수의 반복 후에는 local maximum에 도달하도록 보장합니다.

위 이미지를 통해 GMM이 어떻게 clustering을 하는지 확인할 수 있습니다.

 

 

 

Reference

 

[1] 핸즈온 머신러닝2, 한빛미디어, chapter 9

[2] KOOC, 인공지능 및 기계학습 개론 II, 문일철 교수, chapter 8

[3] DBSCAN

[4] GMM