원문 기사: https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68
The 5 Clustering Algorithms Data Scientists Need to Know
이 글에 나오는 모든 사진은 원글에서 가져온 것임
기계학습에서 사용하는 클러스터링(clustering)이라는 기술은 data point set을 기준으로 비지도적으로 분류하기 위한 것이다.
이론에 따르면 같은 그룹 안에 속한 data points는 특징과 비슷한 속성을 갖고 있어야 하지만 다른 그룹에 속하는 data points는 특징과 비슷하지 않은 속성을 가져야 한다.
데이터 사이언스에서 우리는 클러스터링 알고리즘에 적용했을 때 해당 데이터가 갖고 있는 몇 가지 관점을 얻기 위해 클러스터링 분석을 할 수 있다. 이제부터 가장 대중적인 5가지 알고리즘을 소개.
K-Means Clustering
K-Means는 아마도 가장 잘 알려진 클러스터링 알고리즘일 것이다. 이해하기 쉽고 구현하기 쉽기 때문이다.
1. 클래스 혹은 그룹의 수(K)를 정해야 한다. 그러면 그 숫자에 따라 랜덤하게 center point를 잡는다.
2. 각 data point는 각 center point끼리의 거리를 측정해서 분류된다.
3. 분류된 data points에 기반해서 우리는 모든 그룹의 벡터의 평균(mean)을 구하는 것으로 그룹의 center를 recompute한다.
4. 이 과정을 그룹 center가 그렇게까지 많이 바뀌지 않는 선에서 반복한다. 물론 그룹 center를 랜덤하게 여러번 초기화 시킬 수 있고 가장 좋은 결과가 나오도록 고를 수도 있다.
장점:
아주 빠름.
계산량은 O(n)
단점:
클래스/그룹 수(K)를 내가 정해야 한다.
처음에 point를 랜덤하게 고르기 때문에 돌릴 때마다 다른 결과가 나온다.
=> 같은 결과가 별로 반복되지 않으며 지속성이 떨어진다(다른 알고리즘은 이보단 낫다).
K-Median이라는 클러스터링 알고리즘은 K-Means와 관련되어 있긴 하지만 mean을 구할 때 그룹의 median1 vector를 사용해 mean을 구한다는 점에서 약간 다른 알고리즘이다.
Mean-Shift Clustering
Mean-Shift 클러스터링은 sliding-window에 기반한 알고리즘으로 data points의 가장 밀도 높은 지역을 찾으려고 한다.
이는 즉 centroid-based 알고리즘이라고도 하는데 목표(goal)이 그룹 혹은 클래스의 center points를 찾아가는 것이기 때문이다. 이 과정은 sliding-window 내에 있는 points의 평균이 되고자 하는 center points의 후보를 업데이트 하는 것으로 이루어진다.
후보 windows는 비슷한 것(near-duplicates)을 제거(eliminate)하는 post-processing 단계에서 center points의 final 집합과 그에 해당하는 그룹을 형성하면서 걸러진다.
1. 위 일러스트에서 볼 수 있는 것 처럼 point set을 2D 공간에 놔둬야 한다. 그리고 원 형태의 sliding window(kernel = 반지름(radius) r)를 랜덤하게 선택한 point C에 맞춘다. 때문에 이 알고리즘은 언덕을 오르는(hill climbing) 알고리즘이라고도 하며 높은 밀도를 보이는 지역을 각 단계에서 찾기 위해 kernel을 반복적으로 옮긴다.
2. 반복할 때마다 sliding window는 더 높은 밀도를 갖는 지역으로 center point를 points(window 범위 내에 있는)의 평균값으로 옮겨간다.
3. 우리는 평균값에 따라 sliding window를 계속해서 옮기고 이 작업은 kernel 안에 더 많은 points를 수납할 수 있는 방향을 찾지 못할 때까지 계속된다.
4. 여러 개의 sliding window안에 모든 points가 수납될 때까지 1-3을 반복한다.
다 끝나면 아래 일러스트와 같아진다.
장점:
K-Means와 대조적으로 이 알고리즘은 클래스 혹은 그룹의 개수를 정할 필요가 없다. Mean-Shift가 자동적으로 발견한다.
단점:
kernel = 반지름 r 사이즈를 선택해야 한다.
Density-Based Spatial Clustering of Applications with Noise (DBSCAN)
DBSCAN은 밀도에 따라 클러스터링 하는 알고리즘이기 때문에 Mean-Shift와 비슷하다고 할 수도 있겠지만 더 많은 장점이 있다.
1. DBSCAN은 임의로 고른(가 본 적 없는) starting data point에서 시작한다. 이 point의 이웃은 거리 입실론 ε을 사용해 추출된다.
2. 만약 '이웃' 안에 충분한 수의 points(minPoints에 따라)가 들어있다면 클러스터링을 시작한다. 새로운 클러스터에 있는(현재 시작점인) 첫 번째 point와 다르게 나머지 points는 noise로 라벨링된다. 나중에 noise도 클러스터의 부분이 된다. 그리고 두 경우 다 방문했다는 것을 기억한다.
3. 새로운 클러스터의 first point를 위해 입실론 거리에 있는 이웃에 속한 points도 같은 클러스터의 일부가 된다. 이러한 절차는 클러스터 그룹에 추가된 적이 있는 모든 새로운 points를 위해 반복된다.
4. 2, 3번은 모든 points가 정의될 때까지 계속된다. 즉, 모든 입실론 이웃인 points이 라벨링 될 때 까지 계속된다.
5. 현재 클러스터링이 끝나면 새로운 방문하지 않은 point가 나오고 다시 위 과정이 반복된다. 이는 더 먼 거리에 있는 cluster와 noise를 발견하기 위함이다. 이 과정도 모든 points를 방문할 때까지 계속된다.
장점:
미리 클래스 혹은 그룹 수를 지정할 필요가 없다.
Mean-Shift가 data point가 아주 다르면 그냥 다른 클러스터에 던졌던 것과 다르게 outlier(본체 이외의 것)를 noise로 정의하고 임의의 사이즈와 임의의 모양을 갖는 클러스터를 찾을 수 있다.
단점:
별로 잘 작동하지 않는다.
이웃 points를 위한 거리 임계점(distance threshold) ε과 minPints는 클러스터에서 클러스터에 넘어갈수록 그 밀도가 달라짐에 따라 똑같이 달라진다.
Expectation-Maximization (EM) Clustering using Gaussian Mixture Models (GMM)
K-Means의 주요 단점 중 하나는 cluster center를 알기 위해 평균 값을 naive하게 사용한다는 점이다.
아래 이미지(K-Means의 두 가지 실패한 예)를 보면 이것이 왜 단점인지 알 수 있을 것이다.
왼쪽은 딱 봐도 사람 눈 같이 생겼는데 즉 같은 평균값을 갖는 반지름만 다른 두 개의 클러스터로 나뉘었다.
K-Means는 이러한 문제를 다룰 수 없다. 왜냐 하면, 클러스터의 평균값은 서로 아주 비슷하기 때문이다.
오른쪽과 같이 원형이 아니어도 실패한 예가 있는데 이것도 평균 때문에 실패했다.
Gaussian Mixture Models (GMM)은 우리에게 K-Means보다 더 나은 flexibility를 보여준다.
우리는 data points가 가우시안 분포라고 가정하고 이는 즉 평균을 이용해 원이 되어야 한다는 것 보다 덜 제한적인 가정을 사용할 수 있게 된다. 따라서 우리는 클러스터의 모양을 묘사하기 위한 두 개의 파라메터를 갖는데: 평균과 분산이다!
2D로 예를 들면, 클러스터는 어떠한 종류의 타원형(x, y축 안에서 표준 분산을 갖기 때문에)도 가질 수 있다는 얘기이다. 따라서 각 가우시안 분포는 하나의 클러스터로 할당된다.
각 클러스터를 위한 가우시안의 파라메터(e.g. 평균, 분산)들을 찾기 위해 우리는 Expectation Maximization (EM)이라는 최적화 알고리즘을 사용한다. 그리고 우리는 GMM을 사용해서 EM을 돌릴 수 있다.
1. 우리는 클러스터의 개수를 K-Means와 같이 정하고 랜덤하게 각 클러스터의 가우시안 분포 파라메터를 정해준다.
2. 각 클러스터를 위해 주어진 이러한 가우시안 분포들의 각 data point가 특정 클러스터에 속할 확률을 계산한다. 가우시안의 중심부에 가까운 point는 해당 클러스터에 속할 가능성이 더 높다. 이는 대부분의 데이터가 클러스터의 중심부와 가깝게 나뉘어질 거라고 가정할 수 있게 한다.
3. 이러한 확률에 기초해 우리는 data points가 클러스터 안에 속할 확률을 최대화 하는 가우시안 분포들의 새로운 파라메터 집합을 계산한다. 계산은 data point 위치의 가중치를 적용한 합계를 이용해 이루어지며 가중치는 data point가 특정 클러스터에 속할 확률이다. 위 일러스트에서 노란색 클러스터를 예로 들면, 첫 번째 반복시에 해당 분산은 랜덤하게 정해지지만 대부분의 yellow points가 오른쪽으로 향해 가는 것을 볼 수 있다. 우리가 확률로 합 가중치를 적용한 합을 계산했을 때, 중심부에 가까운 몇 개의 points가 있다 하더라도 대부분은 오른쪽에 있는 것을 알 수 있다. 따라서 자연적으로 분산의 평균은 points 집합에 가까워지도록 옮겨진다. 이에 따라 분산은 확률로 가중치가 적용된 sum이 최대값이 되도록 이러한 points에 알맞는 타원형을 만들어간다.
4. 2, 3은 분산이 반복 시마다 많이 달라지지 않는 선에서 집합이 만들어질 때 까지 반복된다.
장점:
K-Means보다 클러스터 집합이 flexible(분산 덕분에 덜 제한적이라서).
GMMs는 확률을 사용하기 때문에 각 data point마다 여러 클러스터를 가질 수 있고 만약 data point가 겹쳐진 두 개의 클러스터 사이에 있다 하더라도 우리는 간단하게 확률로 나눠서 판단할 수 있다. 즉, GMMs는 mixed membership2을 지원한다.
Agglomerative Hierarchical Clustering
계층적인 클러스터링 알고리즘은 사실 2 가지로 나뉘어진다: top-down, bottom-up.
Bottom-up 알고리즘은 시작 부분(outset)에서 각 data point를 하나의 클러스터로 다루며 연속적으로 한 쌍의 클러스터를 모든 클러스터가 하나로 합쳐질 때까지 병합(merge 혹은 agglomerate; 뭉치다)한다.
Bottom-up 계층 클러스터링은 그러므로 계층으로 뭉쳐진(hierarchical agglomerative) 클러스터링 혹은 HAC라 불린다.
클러스터의 계층은 나무(혹은 dendrogram; 계통수)로 표현된다. 나무의 뿌리는 모든 샘플을 모아 놓은 unique한 클러스터이고 잎은 하나의 샘플을 갖는 클러스터가 된다.
1. 우리는 각 data point를 하나의 클러스터로 다루면서 시작한다. 즉, 만약 X개의 data points가 우리의 데이터셋에 있다면 우리는 X개의 클러스터를 갖는 것이다.
2. 각 반복시에 우리는 두 클러스터를 하나로 합친다. 무엇과 무엇을 합칠지는 두 클러스터의 가장 작은 평균 연결(average linkage; data points 사이의 평균 거리)3을 이용해 정한다. 즉, 선택된 거리에 따라 두 클러스터는 서로를 잇는 가장 짧은 거리를 가지며 이는 가장 비슷하다는 뜻이고 합쳐져야 한다는 말이 된다.
3. 2는 나무의 뿌리에 도달할 때 까지 계속된다. 즉, 우리는 모든 data points를 갖는 하나의 클러스터가 생길 때까지 계속하는 것이다. 여기서 우리는 우리가 원하는 클래스 개수가 될 때 멈추는 것으로 클래스 개수를 마음대로 고를 수 있다.
장점:
우리에게 클래스 혹은 그룹의 개수를 정하게 하지 않는다.
오히려 우리가 원하는 개수의 클러스터를 언제든지 얻을 수 있다.
거리에 민감하지 않다.
특히 좋은 점은 갖고 있는 데이터가 계층적인 구조를 갖고 있을 때이다. 다른 알고리즘은 이런 상황에서는 별 소용이 없다.
단점:
K-Means나 GMM과 다르게 높은 계산량을 갖는다. O(n^3)
'Medium 노트' 카테고리의 다른 글
| 파이썬이 느리지만 대중적인 이유 (1) | 2019.01.07 |
|---|---|
| GloVe란 무엇인가? (0) | 2018.10.06 |