[OpenCV] 08-3-1. Understanding K-Means Clustering

< Understanding K-Means Clustering >

K-Means Clustering의 개념에 대해서 이해해보고, 어떻게 작동하는지 알아보자!

Theory

자주 사용되는 사례를 가지고 이해해 볼 것이다.

T-shirt size problem

시장에 새로운 티셔츠를 출시하고자 하는 회사를 생각해보자. 모든 사람들의 사이즈를 충족시키기 위해서 다른 사이즈의 모델들을 제조할 것이다. 그래서 아래의 그래프 처럼 사람들의 키와 몸무게를 시각화했다.

회사는 모든 사이즈의 티셔츠를 맞춤으로 만들어 줄 수 없다. 대신에, S,M,L사이즈로 나눈 3가지 모델을 통해 사람들의 사이즈를 맞춰 줄 수는 있다. 이렇게 사람들을 세 그룹으로 나누는 것은 k-means clustering이라고 하고, 알고리즘은 3개가 사람들을 만족시키기에 최적이라고 알려준다. 만약 만족이 안된다면, 그룹을 더 다양화 시켜서 충족시킬 수 있다.

How does it work?

이 알고리즘은 반복성 과정을 갖는다. 그림을 참고하여 한단계씩 설명해보겠다.

아래의 데이터셋 분포를 보자. 우리는 이 데이터를 2개의 그룹으로 클러스터링 해야한다.

단계 1 : 알고리즘이 무작위로 두 개의 중심(Centroid)인 C1,C2를 선택한다.

단계 2 : 각 포인트로 부터 두 개의 중심간의 거리를 계산한다. 만약 테스트 데이터가 C1에 더 가깝다면, ‘0’으로 레이블링해준다. 만약에 C2에 더 가깝다면, ‘1’로 레이블링해준다.

이 데이터의 경우에는, ‘0’을 붉은색으로, ‘1’을 파란색을로 칠한다. 위의 과정을 거치면 아래의 사진과 같은 결과를 얻게 된다.

단계 3 : 이제 모든 파란점과 붉은 점의 평균을 각각 계산하고 이를 새로운 중심점으로 설정한다. 새로 계산된 중심점으로 C1,C2가 이동하게 되는 것이다.

그리고 다시 단계 2를 수행하면 다음과 같은 결과를 얻을 수 있다.

이제 단계 2와 단계 3은 두 개의 중심점이 고정점으로 수렴할 때 까지 반복된다.(정해진 기준이나, 반복 횟수나, 특정 정확도에 다다르길 바랄경우에 의존하여 멈춘다.) 이 점들은 테스트 데이터와 이에 대응하는 중심점과의 거리의 합이 최소가 되도록 하는 점들이다. 또는 간단하게, C1↔Red_Points 사이 거리와 C2↔Blue_Points 사이 거리의 합을 최소화하는 것이라 말할 수 있다.

minimize[J=∑All Red Pointsdistance(C1,Red_Points)+∑All Blue Pointsdistance(C2,Blue_Points)]

최종 결과는 다음과 같다 :

K-means clustering에 대한 직관적인 이해를 해보았다. 더 자세한 수학적 설명을 원한다면 도서나, 추가 자료들을 찾아보길 바란다! 이는 그저 top layer K-means clustering일 뿐이다. 다양하게 개조된 알고리즘들이 존재한다! 중심점을 고르는 법이나, 어떻게 반복 과정의 속도를 높이는지에 대한 것 들이다.