k-means Clustering - 군집화 알고리즘

 

Machine Learning 알고리즘 중에서도 매우 기본 중에 기본인 k-means clustering에 대해서 알아볼께요.

 

k-means 군집 알고리즘은, 

어떤 데이터들이 있을 때, 유사한 데이터들끼리 자동으로 그룹핑을 해주는 알고리즘 입니다. 

 

 

 

기본 로직은 아래와 같습니다. 

 

모든 ML 알고리즘은 반복적인 과정을 통해 최적화를 해나가는 특징이 있습니다.

마찬가지로 k-means 알고리즘도 n번의 iteration 과정을 거쳐 최종 군집 결과를 보여주게 됩니다. 

 

기본 로직을 단계별로 한번 살펴볼께요 ! 

 

 

 

 

(1) Choose random k points and set as cluster centers.

 

A. raw data

 말 그대로, 날 것의 data 그 자체예요.

 데이터가 이렇게 있다고 했을 때,

 몇 개의 군집으로 그룹핑을 하고 싶은지를 정해줍니다.

 

 즉, 우리가 말하는 k-means 에서 k는 Cluster(군집)의 수를 나타내요.

 본 예제에서는 k =2 로 두겠습니다. 

 

 

 

 

B. initial points (cluster centers)

 

첫 시작으로, 임의로 k개의 점을 찍습니다.

이때 랜덤 좌표를 정하는 방법은 크게,

(1) 좌표 평면 상에 정말 랜덤하게 찍는 방법도 있고, 

(2) 가지고 있는 데이터 중에서 하나를 선택하는 방법도 있어요.

 

둘 중 뭘 해도 크게 상관은 없으나, (1)일 경우, 만약 정말 엉뚱한 자리를 찍게 되면 그만큼 최적화 하는 시간이 오래 걸리게 될 거예요.

그러나, (2)으로 할 경우에는 그래도 데이터가 있는 부근을 선택하기 때문에

(1)보다는 최적화 시간이 더 짧을 확률이 높겠죠? 

 

 

(2) Assign each object to the closest centroid's cluster.

 

그 다음, 지정된 점을 기준으로 데이터와 거리를 계산해요 

2개의 지정된 점 (A,B)가 있다고 했을 때, 모든 데이터와 A/B 거리를 계산해서

A랑 더 가까우면 A(빨간색), B랑 더 가까우면 B(파랑색)으로 군집을 assign 합니다. 

 

 

 

 

 

 

 

(3) Recalculate the positions of the centriods.

 

 

2번 과정을 통해 모든 데이터가 A(빨강) or B(파랑) 군집으로 Assign 된 상태에서

다시 Centriod(중심값)을 계산해줍니다.

각 각의 중심값을 구하는 방법은 A 군집 데이터들 간에 평균값,

B 군집 데이터들 간의 평균을 구하는 방식으로 구할 수 있겠죠?

 

 

 

 

 

 

(4) Go back to Step 2 unless the centroids are not changing.

 

 

 

 

 

 

 

 

 

 

 

 

새롭게 Centriod 값을 구했으면, 다시 2~4번 Step을 반복해줍니다. (반복적인 과정을 통해 최적화해나갑니다.)

다시 모든 데이터와 각 Centroid 값과의 거리를 계산하여,

A와 B 중 더 가까운 쪽으로 군집을 다시 Assign 해줍니다.

 

계속 Step 2~4번을 반복하게 되면, 어느 순간 Data 각각의 군집이 더이상 바뀌지 않고 정착하게 됩니다.

그럼 Centriod 값에도 변화가 없을 경우, 군집화 과정은 끝이 납니다.

 

 

기본적인 k-means Clustering 방법은 위에 설명드린 것과 같고,

- initialization points를 어떻게 정하는가? (randomly, select k points, etc.)

- 각 Data 간에 거리를 어떻게 측정할 것인가? (유클리디안, cosine similarity, etc.)

 

위 방법에 따라서 조금씩 결과가 달라질 수 있습니다 :) 

 

다음번에 시간이 되면, 오픈 라이브러리를 이용해서 간단하게 구현하는 것도 적어둬야겠네요..