[인공지능개론] Clustering

이때까지 대표적인 supervised learning에 대해 알아보았다. supervised learning은 labeled data로 학습하기 때문에 unsupervised learning에 비해 비교적 높은 정확도를 갖는다. 하지만 사람이 하나하나 labeling을 해야 한다. 반면 unsupervised learning은 labeled data가 필요없기 때문에 사람의 노력이 최소화된다는 장점이 있지만 그만큼 정확도도 낮다. 

학습과 데이터에 따라 task를 분류해보자.

supervised learning으로 해결하는 task는 classification(categorization), regression이 있지만 data가 continuous한지 discrete한지에 따라 분류된다. 하지만 discrete data를 무한히 쪼개면 결국 continuous data에 가까워지므로 classification과 regression의 경계는 모호하다.

이제 unsupervised learning의 일반적인 task에는 clustering, density estimation, dimensional transform이 있는데 이중에서 많이 사용되는 clustering에 대해 알아보자.

clustering이란 비슷한 data들을 묶어 여러 개의 cluster로 분할하는 것으로, cluster 내부의 data들 간의 유사도는 높게 조직한다. 다양한 clustering algorithm이 있는데 그중에서 가장 간단한 k-means algorithm을 공부해보자.

clustering에서 중요한 유사도는 거리에 의해 계산되는데, 거리 측정법에는 Euclidean distance와 Manhattan distance가 있다.

Euclidean distance는 우리가 흔히 일상생활에서 적용하는 거리 측정법으로, $d(x,y)=\sqrt{\Sigma_i (x_i-y_i)^2}$ 의 공식으로 계산할 수 있다. 반면, Manhattan distance는 $d(x,y)=\Sigma_i |x_i-y_i|$ 로, 택시가 건물을 통과하지 못하고 도로로만 지나가는 것처럼 절대거리로만 계산한다는 점에서 택시거리라고도 불린다. (sup distance 라는 것도 있는데, $d(x,y) = max_i |x_i-y_i|$로, 절대값 중 최댓값만 취하는 것이다.)

이제 k-means algorithm으로 돌아가보자. k-means algorithm은 clustering의 일종으로 같은 cluster에 속하는 데이터들의 내부 similarity를 증가시키는 방향으로 cluster를 형성한다. 여기서는 Euclidean distance를 이용하며 평균을 구할 수 있도록 실수의 좌표를 가져야 한다.

k-means algorithm의 과정은 단순하다. 처음에는 k개의 centroid을 random하게 선택한다. 그리고는 각각의 object를 가장 가까운 centroid에 할당하고 같은 centroid에 할당된 object들의 평균을 새로운 centroid 값으로 설정하는 것을 계속 반복하면 된다. 이는 각각의 centroid에 할당된 object들이 변하지 않을 때까지 반복된다.

이를 계속 반복하다보면 아무 데이터가 없는 cluster가 생길 수 있는데 일반적으로 그 cluster를 그냥 없애버린다. 만약 k개의 cluster가 꼭 필요한 경우에는 새로운 random centroid를 만들어서 해결한다.

k-means algorithm의 cost function은 아래와 같다. $$J(c^{(1)}, \cdots , c^{(m)}, \mu_1, \cdots , \mu_k)={{1}\over{m}}\Sigma^m_{i=1} ||x^{(i)}-\mu_{c^(i)}||^2$$ 

하지만 k-means algorithm은 local optima에 빠질 수 있다는 한계가 있다. cluster의 개수가 적을 수록 local optima에 빠질 확률이 크다. 이를 극복하기 위해서는 random initialization을 여러 번 해야 한다.

군집 개수 k는 몇 개로 나눌 것인지로, 주로 목적에 따라 사람이 직접 데이터 분포를 보고 결정한다. 이를 선택할 때 elbow method를 활용하기도 한다. elbow method란 k 개수에 따라 cost function 그래프를 그려보았을 때, 특정 k 이후 cost가 거의 변하지 않는 elbow point가 있다면 그 k를 선택하는 방법이다. 하지만 cost function 그래프가 대체로 부드러워서 elbow point라고 부를 만한 지점이 없다면 elbow method로 k를 정하는 데에는 무리가 있다.

 

[출처] 한양대학교 장준혁 교수님 인공지능개론 수업