Clustering 2

Hierarchical Clustering

실제 세상에서는, 데이터들 간의 보이지 않는 계층이 존재합니다.
hierarchical clustering을 이용하면 cluster들 안에 보이지 않는 sub-cluster를 구현할 수도 있습니다.

Top-down 방식으로 (Divisive Hierarchical Clustering) clustering을 할 수 있습니다.
전체 instance를 쪼개고, 쪼개고, 쪼개는 방식입니다.

Bisective k-means clustering이 여기에 속하겠네요.

Bottom-up 방식으로 clustering을 할 수도 있습니다.
(Agglomerative Hierarchical clustering)

이 6개의 점으로 agglomerative하게 clustering을 수행하면 다음과 같습니다.
기본적으로 이렇게 bottom-up하게 clustering을 수행하면, 계통도가 자연스럽게 생깁니다.

기본적으로 각각의 데이터를 원소가 1개뿐인 cluster로 잡고,
특정 조건에 맞게 clustering을 하는 것입니다.

이 높이가 매우 중요한데,
거리가 작을수록 cluster간의 유사도가 높습니다.

또, 특정 시점에서 {13}과 {43}이 합쳐졌다는 것은, {13, 43}이 하나의 클러스터가 되었다
는 뜻입니다.

그리고 둘이 합쳐진 그 결과물의 높이가 낮다면, {13}과 {43}은 Similar하다고 해석됩니다.

또, bottom-up 방식으로 만들면, 원하는 높이에서 dendrogram을 잘라서 cluster의 개수를 정할 수 있습니다.
먼저 clustering을 수행한 후 그 후 원하는 만큼 cluster를 얻어낼 수 있습니다.

이 경우는 k=2겠네요.

이렇게 자르면 k=6을 얻을 수 있는거구요.
극단적으로 d=0에서 자르면, 모든 data point에 대해 cluster를 만들 수 있겠네요.

pseudo code는 다음과 같습니다.

1. 각 individual data point를 cluster로 취급합니다.
   cluster list $L = \{c_1, c_2, ... , c_n\}$에 넣습니다.

2. $L$ 내에서 closest pair $c_i, c_j$를 찾습니다.

3. $L$에서 $c_i, c_j$를 제거한 후, $(c_i, c_j)$를 넣습니다.

4. 2, 3을 $L$에 하나의 cluster만 남을 때까지 진행합니다.

그러면, 어떻게 $L$ 내에서 closest pair를 얻어낼까요?

만약 둘 다 size = 1인 cluster라면 거리를 측정하면 되지만,

$c_2$와 $(c_3, c_5, c_6, c_8)$간의 유사도는 어떻게 측정할까요?
이 때 유사도를 측정할 기준인 Linkage Criteria가 중요합니다.

가장 단순한 방법은, 서로 cluster의 무게중심간의 거리를 재면 되겠죠.

이렇게 많습니다.
방금 말한 단순한 방법은 Centroid-linkage clustering이구요.

두 cluster간의 거리 중 최대치를 가지고 거리를 측정하는 Maximum linkage clustering이 있구요.
최소치만 가지고 측정하는 Minimum linkage clustering도 있고,
전체 거리를 싹 다 더해서 평균을 내는 Average linkage clustering도 있고,
아무튼 많습니다.

대표적으로 쓰이는 것들이
Maximum Linkage, Average Linkage, Single (Minimum) Linkage,
그리고 Ward Linkage (cluster간의 중점을 잡고, cluster 내부의 점과 그 중점 사이의 분산이 제일 덜 늘어나는 cluster를 찾는 것)
가 있습니다.

이 Linkage Criteria를 바꿔갈 수록 Cluster되는 모양이 정말 많이 변합니다!
그만큼 중요해요.

Summary : Agglomerative Hierarchical Clustering

장점은, Cluster의 개수를 clustering 시작 전에 정할 필요가 없습니다.
또, k-means와 다르게 random성이 없습니다.

입력이 같으면 출력도 같아요. 천번 만번 돌려도요.
또, 계층이 자연적으로 만들어져서 좀 더 해석하기 좋습니다.

단점은, Linkage Criteria를 미리 정해야 하며,
일반적으로 빠르지 않고 좀 무겁습니다.

DBSCAN

Density Based Spatial Clustering of Applications with Noise의 약어입니다.

데이터가 뭉쳐있는 정도가 threshold를 넘어가면 그 때 cluster를 만드는,
그런 'connectivity based' 알고리즘입니다.

그러면, 뭉쳐있는 정도는 어떻게 정의하나요?

이 값이 DBSCAN 알고리즘의 parameter입니다.
$MinPts$와 $\epsilon$이라는 2개의 파라미터가 존재합니다.

$MinPts$는 개수고, $\epsilon$은 반경입니다. 이 2개를 사용자가 입력으로 넣습니다.

우선 $\epsilon$-Neighborhood를 정의합니다. K-NN과 비슷합니다.
$N_\epsilon(p)$는 점 $p$와 반경 $\epsilon$ 안에 있는 모든 이웃의 집합입니다.

밀도가 높은 곳에서는 $\epsilon$-Neighborhood가 엄청 높게 나올거고, 밀도가 낮으면 작게 나오겠죠.

다음, Core Points를 정의합니다.
Core Points는 본인의 $\epsilon$-Neighborhood에 $MinPts$ 이상의 점이 존재하는 점을 의미합니다.

$MinPts = 4$라면,

여기선 q가 Core Point가 되겠죠. (자기 자신도 포함합니다.)
이 경우 q의 Density가 높다고 봅니다.

이걸 바탕으로 전체 데이터셋에서 각 점이 Core Point인지 아닌지 판별이 가능합니다.

Core Point가 된다는 것은, 그 Core Point가 곧 Cluster가 됨을 의미합니다.

이 예시에서 A라는 점은 Core Point입니다.
A를 기준으로 하나의 cluster를 만듭니다.

그리고, A의 $\epsilon$-Neighborhood에 속하는 점을 전부 A Cluster로 포함시킵니다.

그 때 포함된 점들 중 또 Core Point가 존재한다면,
그 Core Point를 중심으로 한 $\epsilon$-Neighborhood의 점들 역시 같은 Cluster로 편입시킵니다.

이렇게 계속 확장을 해나갑니다.

확장의 결과는,
Core Point (빨간색 점들)과,
Border Point (노란색 점. Core Point는 아닌데 Core Point의 $\epsilon$-Neighborhood에 속함),
Noise Point (파란색 점. Core도 아니며 Core의 이웃도 아님)

으로 나뉩니다.

이 original dataset을 나누면,
core point들과 border point, noise point로 분류가 됩니다.

DBSCAN은 밀도, 즉 connectivity 기반이기 때문에,
밀도만 충분하다면 비선형 cluster도 확장해서 묶을 수 있습니다.

$MinPts$와 $\epsilon$의 초기 설정은,
$MinPts$는 $2\times num\_dims$가 나름 괜찮은 수치라고 불리고,

$\epsilon$의 경우는,
$num\_dims$가 10이라고 가정하면, $MinPts$는 20이 되고,
이 때 특정 점과 '19번째' 가까운 점을 찾아 거리를 잽니다.

누구는 dense해서 19번째 점하고 거리가 가까울거고,
누구는 sparse해서 19번째 점하고 거리가 멀겠죠?
모든 점에 대해 그 거리로 그래프를 만들었을 때,

급격스럽게 변화하는 지점, 즉 Elbow Point를 찾습니다.
그 지점을 $\epsilon$으로 삼습니다!

Heuristic한 방법이죠.

그리고, 만약 MinPts = 2라면,
DBSCAN의 결과는 Single Linkage를 적용한 Hierarchical clustering에서,
높이 $\epsilon$에서 잘린 dendrogram과 아예 같아집니다.

Summary - DBSCAN

DBSCAN은 cluster의 개수를 입력으로 받지 않습니다.
Core Point의 개수와 밀집도에 따라 자동으로 정해져요.

그리고, noise에 대한 통찰이 생깁니다.
정확히는, 어떤 점이 noise인지 아닌지까지 파악이 돼요.

그리고 $N_\epsilon(p)$가 핵심 계산인데, 이걸 빠르게 구하는 알고리즘들은 이미 널렸습니다.

대신 단점은 $MinPts$와 $\epsilon$이 전역이기 때문에,
cluster간의 density가 상대적으로 다를 경우에,
공통적인 hyperparameter가 존재하기 때문에 clustering이 불가해집니다.

Comparing all Clustering Algorithms

K-means

쉽습니다.
병렬화도 아주 잘 돼요.
하지만, k를 사전에 정해야 합니다. outlier에 민감하구요.
$O(tknd)$입니다.

Bisecting K-means

K-means보다 빠릅니다.
계층도 자동으로 만들어줍니다.

하지만, 역시 k가 사전에 정해져야 합니다.
얘도 outlier에 민감하구요.
$O(tnd)$입니다.

GMM

Soft Assignment를 하기 때문에, 조금 더 유연한 해석이 가능하며,
Outlier에 덜 민감합니다.

대신 얘도 k를 사전에 정해야 하구요.
Gaussian 분포 자체가 데이터를 잘 묘사한다는 보장이 없습니다.
$O(tknd)$입니다.

HC (Hierarchical Clustering)

k가 알고리즘을 수행한 후 정해집니다.
outlier에 대한 명시가 어느정도 가능하고, 시각화하기도 쉽습니다.

단점은, 느리고, linkage method를 사전에 정해야 합니다.
$O(n^3d)$인데, $O(n^2lognd)$까지 줄일 수는 있습니다.

DBSCAN

k가 필요 없습니다.
noise를 구분까지 해 주며,
어떤 shape을 가지든 clustering이 가능합니다.

단점은 $MinPts$와 $\epsilon$을 신중히 골라야 하며,
여러 density를 handle할 수 없습니다.

$O(n^2d)$이며, $O(nlognd)$까지 줄일 수 있습니다.