K-means Clustering

댄·2022년 7월 24일

이번 포스트에서는 Unsupervised Learning의 Clustering 기법 중 하나인 K-means Clustering에 대해서 다룹니다.

Background

Cluster(군집)란 비슷한 특성을 가진 데이터의 묶음이다. 어떠한 데이터들이 주어졌을 때 같은 특성의 그룹으로 나눌 수 있게 된다면 데이터 처리 관점에서 매우 유용하게 사용 할 수 있을 것이다. 예를 들어 다음과 같은 사진들이 주어졌다고 가정해보자.

사진에선 강아지, 고양이, 책상, 의자가 있다. 이들은 특성적으로만 본다면 강아지와 고양이는 같은 데이터의 특성으로 분류 가능할 것이고(동물..으로) 책상과 의자도 같은 특성으로 분류 할 수 있을 것이다(가구 등으로). 이처럼 데이터가 주어졌을 때 같은 특성을 가진 그룹으로 나누는 작업을 Clustering이라고 부른다.

K-means Clustering

Clustering을 진행할 때에는 몇 개의 cluster로 묶을지 사용자가 정해야 할 경우가 생긴다. 그때 사용하는 방법이 K-means Clustering이다. K-means에서 K는 cluster의 개수이며 정리하여 말하자면 데이터를 K개의 cluster으로 나누는 알고리즘을 K-means Clsutering이라 한다. 알고리즘의 순서는 다음과 같다.

1. Cluster의 개수를 정함(parameter k)

데이터를 몇 개의 cluster로 분류할지 결정하는 과정이다. K-mean에서는 k개의 cluster로 미리 지정을 해주어야 한다. 이는 K-means Clustering 알고리즘의 장점이자 단점으로 꼽히는데, 적용할 데이터가 정확히 몇 개의 cluster로 분류될지 알고 있다면 유용하게 사용할 수 있지만 실제 데이터 분포를 나누고자 할 때는 그렇지 않은 경우가 많다. 다른 접근법에서는 k를 데이터 분포에 따라 최적화하는 방법도 존재한다.

2. Centroid Initalize

centroid란 각 cluster를 대표하는 중앙 값이라고 생각하면 된다. 그림을 예를 들어 설명하자면, 다음의 그림에서는 3개의 cluster가 분포되어 있고, 각 cluster의 중앙에는 centroid가 있다. 그림에서 ○은 데이터, ★은 centroid를 의미한다.

Centroid는 처음부터 각 cluster를 대표하는 위치에 assign되진 않고 어디에서부터 assign할지 크게 3가지 방법을 통해 결정된다.

Random
Manually
kmean++ (mostly used)

K-mean Clustering은 Centroid Initalize에 따라서 최적의 centroid에 수렴하는 속도의 차이가 매우 심하다. 그러므로 Centroid Init method를 잘 결정 해주어야 한다.

3. Data Cluster Update

각 데이터는 k개의 centroid에서 어느 centroid에 가깝게 위치하는지 계산하여 가까운 centroid에 assign된다. 특정 centroid에 assigned 데이터는 cluster가 된다. 정리하자면 k개의 centroid가 주어지면 각 데이터들은 자신이 어느 centroid에 assign될지 결정한다. 여기서 가까운 정도를 측정하는 방법은 유클리드 거리를 사용한다. 아래의 그림으로 예시를 든다.