Clustering

Data를 여러 개의 그룹으로 나누거나, 혹은 Data의 분포를 추정하는 방법.

기본적으로 비지도 학습 방식으로 어떤 label 없이 데이터 내에서 거리가 가까운 것들끼리 각 cluster로 묶어내는 방법이다.

즉, 각 cluster에 속하는지에 대한 여부가 Latent Variable이 되며, label이 주어져 있지않으므로 Latent Variable를 Estimate해내는 비지도 학습 방식이다.

Error

각 Cluster가 묶인 것에 대한 Error, Clustering을 하는 데에 있어서 생긴 Error 두 가지로 분류된다.

이를 판단하는 기준은 Distance가 된다.
따라서, clusters간의 Distance를 판단하는 기준이 필요하다.

Distance between two clusters

d (a, b)

는 Distance를 재는 여러 함수들 중 적절한 함수를 사용한다.

Single-link distance

$d (g_{i}, g_{j}) = min_{a \in g_{i}, b \in g_{k}} d (a, b)$
:각 Cluster의 element 중 가장 서로 가까이 있는 element간의 거리.

Complete-link distance

$d (g_{i}, g_{j}) = max_{a \in g_{i}, b \in g_{k}} d (a, b)$
:각 Cluster의 element 중 가장 서로 멀리 있는 element간의 거리.

Average-link distance

$d (g_{i}, g_{j}) = \frac{1}{∣ g _{i} ∣∣ g _{j} ∣} a \in g_{i}, b \in g_{k} \sum d (a, b)$
:모든 거리의 합을, 각 클러스터의 개수로 나누어준다.

Centroid distance

$d (g_{i}, g_{j}) = d (μ_{i}, μ_{j})$
: 각 cluster내에 속한 element들의 평균 간의 거리.

Bhattacharyya distance

$d (g_{i}, g_{j}) = \frac{1}{8} (μ_{i} - μ_{j})^{⊤} (\frac{Σ _{i} + Σ _{j}}{2})^{- 1} (μ_{i} - μ_{j}) + \frac{1}{2} lo g \frac{∣ Σ _{i} + Σ _{k} ∣/2}{∣ Σ _{i} Σ _{j} ∣}$
:Gaussian Distribution의 Bhattacharyya distance.

두 Probability Distribution 간의 유사도(겹침)를 측정하는 지표.
거리가 작을수록 구분이 어렵고, 거리가 클수록 구분이 쉽다.

Cluster error

Clutser가 얼마나 흩어져 있는가를 나타낸다.

같은 Cluster내에 있는 데이터는 최대한 뭉쳐 있어야 하므로, Data point간의 distance가 클수록 Cluster error가 크다고 판단한다.

E (g_{k}) \equiv \frac{1}{∣ g _{k} ∣} x \in g_{k} \sum d (x, μ_{k})

Clustering error

전체 Cluster의 error. 즉, Clustering이 얼마나 잘 되었는지를 의미한다.

모든 cluster error의 합이 된다.

E ({g_{K}}_{k = 1}^{K}) \equiv k \sum \frac{∣ g _{k} ∣}{N} E (g_{k})

: 각 cluster error에 전체 데이터 중 각 cluster의 element 개수를 곱해 더한다.
즉, 일종의 cluster element 개수를 반영한 weighted sum이라 볼 수 있다.

같은 cluster 내에서는 Variance가 작고, cluster들 끼리는 variance가 큰 것이 좋으므로 이는 곧, LDA를 Error의 기준으로 활용할 수도 있다.

E ({g_{K}}_{k = 1}^{K}) = \frac{K k \sum x \in g _{k} \sum ( x - μ _{k} ) ^{⊤} ( x - μ _{k} )}{N k \sum ( μ _{k} - μ _{0} ) ^{⊤} ( μ _{k} - μ _{0} )}

:분자는 cluster내에서의 요소 간 거리, 분모는 cluste들 간의 거리라 볼 수 있다.

Algorithm

clustering을 하는 algorithm은 여러가지가 존재한다.

Agglomerative Clustering algorithm

모든 cluster에는 하나의 Datapoint만 포함시키고, 각 cluster를 하나의 그룹 $G$ 로 묶는다.
$d (g_{i}, g_{j})$ 가 최소인 $g_{i} \in G$ , $g_{j} \in G$ 를 찾는다.
$g_{i}, g_{j}$ 를 묶어 새로운 cluster $g_{k}$ 를 찾는다.
$G$ 에서 $g_{i}, g_{j}$ 를 제거하고 $g_{k}$ 를 추가한다.
원하는 클러스터의 개수 $K$ 에 도달할 때까지, 혹은 clustering error $>$ threshold일 때까지 반복한다.

Divisive Clustering Algorithm

모든 데이터를 묶어 하나의 cluster $g_{0}$ 으로 두고, 이를 그룹 $G$ 에 포함시킨다.
cluster error가 가장 큰 cluster $g_{k}$ 를 찾는다.
clustering error $<$ theshold 라면, 중단한다.
clustering error가 최소화되는 방법으로 $g_{k}$ 를 두 개의 cluster $g_{i}, g_{j}$ 로 분리한다.
그룹 $G$ 에서 $g_{i}, g_{j}$ 를 추가하고 $g_{k}$ 를 제거한다.
만일 원하는 cluster 개수 $K$ 에 도달했다면 중단.

K-means Clustering

기존의 위의 방법들과 달리, cluster가 계속 변하면서 clustering이 이루어진다.

How to find Optimal K?

어떻게 해야 최적의 cluster 개수

K

를 찾을 수 있는가?

방법은 다양하지만, Validation과정을 통해 가장 적은 error를 가져오는 $K$ 를 점진적으로 증가시켜 나가면서 찾는다.
PCA, Color quantization, Cross Validation등의 방법이 이용될 수 있다.