K-means clustering

K-means 클러스터링은 가장 가까운 중심을 가진 군집에 할당됩니다. 이 때, 중심은 군집의 평균(mean)을 의미합니다. 사용자가 사전에 클러스터 수 K를 지정해야 하며 이를 하이퍼파라미터(hyperparameter)라고 합니다. 군집의 중심은 랜덤 초기화됩니다.

학습과정에서는 EM 알고리즘을 기반으로 작동합니다. EM 알고리즘은 Expectation 단계와 Maximization 단계로 나뉘어 수렴할 때까지 반복됩니다. Expectation 단계에서는 모든 점들을 가장 가까운 중심의 군집에 할당합니다. Maximization 단계에서는 군집의 중심을 군집의 경계에 맞게 업데이트합니다. 이 과정을 사용자가 지정한 반복수가 되거나 수렴할 때까지 반복합니다.

초기에 군집의 중심이 랜덤으로 정해지기 때문에 이에 따라 결과가 좋지 않게 나올수도 있습니다. 군집별 크기나 밀도가 매우 다르거나 데이터 분포가 원형이 아닌 특이한 경우에도 클러스터링이 잘 이뤄지지 않을 수 있습니다.

K-medoids clustering

위와 같은 K-means clustering의 단점을 보완하기 위해 평균 대신 중앙점(medoid)을 이용하는 방법입니다.

사용자가 사전에 클러스터 수 K를 결정하고 K개 군집의 초기 중앙점을 선정합니다. 각 점들을 군집의 중앙점과 가장 가까운 군집에 할당하고 점과 중앙점과의 거리를 계산합니다. 군집의 중앙점이 바뀌지 않을 때까지 군집에 할당하고 거리를 계산하는 과정을 반복합니다.

중앙값은 평균에 비해 이상치에 영향을 덜 받기 때문에 k-medoid가 k-means보다 안정적입니다. 그러나 k-medoid 알고리즘의 경우 kmeans에 비해 계산복잡도가 훨씬 높기 때문에 훨씬 느리며 계산 비용이 많이 소모됩니다. 즉 작은 데이터에서는 잘 작동하나 대규모 데이터에는 적절하지 않습니다.

Self-Organizing Map

자기조직화지도(Self-Organizing Map, SOM)는 차원축소와 군집화를 동시에 수행하는 기법입니다. 사람이 눈으로 볼 수 있는 저차원 격자에 고차원 데이터가 대응하도록 군집을 도출해냅니다. 저차원 격자에서의 유사도는 고차원 입력 공간에서의 유사도를 최대한 보존하도록 학습됩니다.

학습과정은 다음과 같습니다. 임의의 고차원 입력벡터가 들어왔을 때 가장 가까운 격자벡터를 찾고 이에 대응되는 저차원 격자에 입력벡터를 할당합니다. 같은 격자에 할당된 입력벡터라 하더라도 격자벡터와의 거리가 모두 다를 수 있습니다.

초기에 고차원 데이터 공간에 대응되는 격자벡터의 위치를 랜덤으로 초기화합니다. 그리고 학습데이터를 하나씩 추가하면서 격자벡터의 위치를 학습데이터의 위치와 비슷해지도록 업데이트합니다. 이 때, 주어진 학습데이터와 가장 가까운 격자벡터가 가장 많이 업데이트되고 멀리 떨어진 격자벡터들은 거의 업데이트되지 않게 합니다.

Fuzzy C-means clustering

퍼지 군집(Fuzzy C-means clustering)은 분할적 군집화(partional clustering) 중 프로토타입 기반 군집화 기법입니다. 각 관측치가 여러 군집에 속할 수 있으며 각 군집에 속할 확률을 제시합니다. 군집 내 유사도를 최대화하고 군집 간 유사도를 최소화합니다.

사전에 클러스터 수 K를 결정하고 각 관측치가 특정 군집에 속할 가중치를 랜덤으로 할당합니다. 그리고 각 군집의 중심을 계산하여 특정 군집에 속할 확률을 다시 계산합니다. 이 과정을 가중치 값의 변화가 주어진 민감도 기준 미만이 될 때까지 반복합니다.

DBSCAN

밀도 기반 클러스터링(Density-based Spatial Clustering of Application with Noise, DBSCAN)은 점들이 몰려 있어 밀도가 높은 부분을 클러스터링하는 방식입니다. 즉, 어느 점을 기준으로 반경 x 이내 점이 n개 이상 있으면 하나의 군집으로 인식합니다.

DBSCAN에서 군집은 밀도 기반 도달가능한 최대치의 밀도기반 연결된 점들의 집합으로 정의됩니다. 점을 중심으로 epsilon 반경 이내에 있는 이웃점에 속하고 minPts 이상의 점이 있으면 밀도 기반 도달가능하다고 합니다. 그 점을 중심으로 군집이 되고 이를 core point라고 하며, 군집의 경계에 있는 점은 border point라고 합니다.

초기에 공간 데이터셋에서 core point의 조건을 만족하는 임의의 점을 선택합니다. 초기값으로부터 밀도기반 도달가능한 점들을 뽑아 core point와 border point를 구분하고 이에 속하지 않는 점들은 noise로 구분합니다. 반경 epsilon인 원 주위에 있는 core point들을 서로 연결하고 이를 하나의 군집으로 정의합니다. 이 때, 모든 border point들은 어느 하나의 군집에 할당됩니다.

• 본 게시글은 ratsgo’s blog와 rfriend를 참고하여 작성되었습니다.