4. Clustering (1)

한성대학교 지준교수님 강의자료를 통해 기초적인 개념들을 다지고자 한다.

클러스터링은 크게 비모수적(non-parametric) 방법과 모수적(parametric) 방법으로 나뉜다. 두 방법의 대표적인 알고리즘들을 살펴보고자 한다.

 

0. Parametric, Non-parametric Methods

Parametric modeling은 통계모델링의 한 종류로 유한한 개수의 parameter를 지닌 확률 분포를 가정하여 데이터에 대한 분포를 모델링하는 방법이다(e.g. Gaussian Mixture Model). Nonp-parametrinc modeling은 데이터에 대한 parametric 확률 분포를 가정하지 않거나 모델 또한 고정되어있지 않다는 것을 가정한 추정 방식이다(e.g. K-Means clustering).

 

1. Non-parametric clustering

1) K-Means clustering

K-Means 클러스터링 알고리즘은 가장 단순한 알고리즘이다. $K$개의 중심점(centroid)들을 설정하고 각 데이터 점들에 대해 가장 근접한 중심점으로 클러스터링하며 다음 목적함수 값이 최소화 될 때 까지 클러스터의 centroid의 위치를 정하고 데이터를 각 클러스터에 클러스터링하는 과정을 반복한다.

$$J = \sum_{k=1}^{K}\sum_{i \in C_{k}}^{}d(x_{i}, u_{k})$$

• $K$: 클러스터 갯수(hyper-parameter)
• $C_{k}$: $k$번 째 클러스터에 속하는 데이터의 집합
• $u_{k}$: $k$번 째 클러스터의 중심위치(centroid)
• $d$: $x_{i}, u_{k}$ 두 데이터 사이의 distance 또는 dissimilarity(e.g. 유클리드 거리로 하면 $d(x_{i}, u_{k}) = \left\| x_{i} - u_{k} \right\|^{2}$)

세부적인 과정은 다음과 같다.

1. 임의로 centroid $u_{k}$를 고른다. 보통은 데이터에서 임의로 $K$개를 선택하지만 공간상에서 임의의 위치을 랜덤으로 선택하기도 한다.
2. 각 centroid $u_{k}$에서 모든 데이터에 대해서 거리를 계산한다.
3. 각 데이터에 대해서 가장 가까운 centroid에 해당하는 클러스터를 할당한다.
4. 다시 만들어진 클러스터에 대해 centroid를 다시 계산하고(e.g. 각 클러스터 데이터들의 평균값) 1~4를 반복한다.

K-means 알고리즘 과정(출처: 강의자료)

 

2) K-Means++

K-Means 클러스터링은 적절한 클러스터 개수 $K$가 얼마인지를 판단하기가 어려우며, 초기값을 어떻게 선택하는지에 따라 성능이 많이 달라지는 단점이 있다. K-Means++는 이를 보완하기 위해 초기 centriod 값을 적절히 설정하기 위한 알고리즘이다. 

1. 임의로 데이터 중 하나의 centroid $u_{k_{1}}$를 선택한다.(K-Means에서는 $k$개를 먼저 선택함)
2. 모든 데이터들에 대해서 선택된 centroid $u_{k_{1}}$와의 거리 $D(x,u_{k_{1}})$를 계산한다.
3. 이후 초기 centroid로 할당할 $u_{k_{t}}$들은 데이터 포인트들 중 이전에 선택한 $u_{k_{t-1}}$과의 거리 $D(x,u_{k_{t-1}})$가 가장 큰 점이 높은 확률로 선택하도록 확률 분포를 $\frac{D(x, u_{k_{t-1}})}{\sum_{}^{}D(x_{i}, u_{k_{t-1}})}$와 같이 조절하여 샘플링하여 선택한다.
4. 3번 과정으로 반복하여 $k$개의 centroid가 선택되면 K-Means 클러스터링을 수행한다.

K-Means ++ 클러스터링 과정(출처: 이미지 링크)

위와 같이 초기 centroid를 지정하는 이유는 K-Means 알고리즘의 초기 centroid가 비슷한 점들이 여러개 선택되면 학습이 불안정하게 되는데 이러한 단점들을 보완하기 위해서이다. 설명에 따르면 초기값 할당 과정 이후 K-Means 알고리즘이 $O(log \ k)$시간 동안 최적의 K-Means해를 찾는 것을 보장한다고 한다.

 

 

3) DBSCAN 클러스터링

K-Means 클러스터링은 단순하고 성능이 좋지만 거리함수 $D(x,u_{k_{t}})$를 Euclidean으로 사용할 경우 클러스터 모양이 원형이 아닌 경우에는 잘 동작하지 않고 클러스터 개수 $k$가 hyper-parameter이기 때문에 최적의 $k$개를 경험적으로 판단해야하는 단점이 있다. 

DBSCAN(Density-Based Spatial Clustering of Application with Noise) 클러스터링 방법은 데이터의 밀도만 사용하여 이를 보완한다. 때문에 클러스터 형태와 무관하게 작동하며 클러스터 갯수를 사용자가 지정할 필요도 없다. DBSCAN은 초기 centroid에서 근접한 데이터를 찾아나가는 방식으로 클러스터를 형성해나간다. 이때 필요한 parameter는 다음과 같다.

• $\epsilon$: 이웃 데이터를 정의하기 위한 거리값
• minimum point: 밀집지역을 정의하기 위해 필요한 이웃의 개수

DBSCAN은 먼저 거리 $\epsilon$내에 minimum point 만큼의 데이터가 있는 core point를 찾는다. 이후 core point에서 $\epsilon$내에 있는 다른 이웃 데이터들에 대해서 $\epsilon$내에 있는 데이터들을 찾고 이를 연결해나간다. 만약 더 이상 이웃이 없으면 해당 이웃 데이터는 border point가 되고 클러스터를 형성한다. 이후 클러스터 외에서 core point를 찾아 위 과정을 반복하여 클러스터링을 하며 최종적으로 생성된 클러스터 외의 데이터를 outlier로 정의한다.

DBSCAN 클러스터링 과정 (출처: 이미지 링크)

 

 

4) 이외 클러스터링

앞서 설명한 3가지 방법 외에도 Mean-Shift Clustering, Hierarchical Clustering등이 있다.