본문 바로가기
Sensor/Algorithm

[K - means Clustering] K-평균 군집화

by Gnaseel 2020. 10. 11.
728x90
반응형

K-means Clustering은 무엇인가

K-means Clustering(이하 KC)은 대표적인 분리형 군집화 알고리즘중 하나이다.

이 알고리즘은 point cloud를 Clustering할 때 사용되는데, Expectation과 Maximization을 반복하며 최적을 찾아가는 알고리즘이다.

아래 설명을 보다보면 매우 RANSAC과 유사한 논리를 전개하는 것을 볼 수 있을 것이다.

 

 

이제부터 실제 예시를 통해 clustering이 어떻게 진행되는지 알아보자.

 

알고리즘 구조

dataset

위와 같은 point cloud에 KC를 적용해보자.

 

우선 KC를 적용하려면 군집의 수를 정해야 한다. 

군집의 수가 정해지면 모든 point들 중 랜덤으로 군집의 중앙이 선정된다.

군집의 수를 2라고 설정하고 진행해보겠다.

포인트들 사이에서 랜덤으로 2개의 군집 중앙(centeroid)이 선정되었다.

 

이제 모든 포인트들을 가장 가까운 군집으로 할당한다. 이 할당과정을 Expectation이라고 한다.

하지만 보다시피 군집이라고 하기에는 너무 볼품없는 output이다.

그래서 이제부터 이 군집을 Maximization 할것이다.

 

Maximization작업은 매우 간단하다.

군집의 중앙을 현재 clustering된 군집의 중앙(centroid)로 설정하는 것이 전부이다.

(여기서 유의해야할 점은 최초 과정에서는 랜덤으로 특정 point의 위치를 군집의 중앙으로 설정해서

centeroid에 해당하는 point가 있었지만, 이제부터는 centeroid는 특정 point의 위치를 가르키는것이 아닌

군집의 중앙이라는 의미로만 사용된다.)

 

이제부터는 다시 Expectation 작업을 진행한다.

물론 다시 Maximization한다.

이 작업을 계속계속 반복하면 k개로 나눠진 군집 데이터를 얻을 수 있다.

 

결과

클러스터링 이전                                            클러스터링 이후

 

Expectation과 Maximization작업을 2번 반복하여 위와 같은 결과를 얻을 수 있었다.

clustering 하고자하는 dataset의 크기나 양에 따라서 반복횟수, 군집개수를 정한 후 알고리즘을 실행하면 된다.

 

즉, KC 알고리즘의 input Data는

1. Points

2. 반복 횟수 N

3. 군집 개수 k

 

로 이루어져있다.

KC알고리즘의 실제 구현에서는 많은 반복을 거친 뒤, clustering된 군집 데이터를 집계해서, 가장 많이 발생한 군집을 기반으로 알고리즘 결과를 출력한다.

 

 

끝내며

 

KC알고리즘은 Expectation과 Maximization 두 작업을 반복하며 진행하며 최적을 얻는데, 엄밀하게 말하자면 최적이라고 할 수 없다.

정답이 존재하고, 이 정답대로 point cloud를 나누는 classification과 다르게, Clustering은 정답이 없기 때문이다.

 

애초에 clustering이라는 것이 비슷한 객체끼리 적당히 묶어 사용한다는 개념인 만큼

몇 개의 군집을 만들것인가, 어느정도 유격되어있어야 다른 군집인가, 군집의 크기는 어느정도인가

같은 이슈들은 사용자의 파라미터로 입력받는 또다른 알고리즘이다.

 

그래서 그렇다면 어떻게 clustering 결과를 평가하는데? 라는 질문에 답하기 위해서 군집타당성지표 (Clustering Validity Index)라는 개념이 있다.

이 내용은 본 포스트의 범위를 넘어가므로 다른 포스트에서 자세히 설명하도록 하겠다.

반응형