시작하며
우리가 Supervised Learning에서 다양한 알고리즘을 다루면서 항상 했던 연산들 중 하나가 바로 Cost 최소화 즉 Cost 함수 최적화(optimization)였습니다.
이번 포스팅에서는 K-means 알고리즘의 Cost 함수에 대해 알아보고 이를 어떻게 최적화하는지에 대해 공부해보겠습니다.
이번 포스팅은 아래 포스팅들을 읽고 공부하시면 더욱 효과적입니다.
https://box-world.tistory.com/29
비지도 학습(Unsupervised Learning)이란? : Clustering
시작하며 우리가 그동안 이전 포스팅에서 배웠던 Linear Regression, Logistic Regression, Neural Network, SVM은 모두 지도학습(Supervised Learning) 즉 레이블(Label)이 있는 데이터에 대한 학습이었습니다...
box-world.tistory.com
https://box-world.tistory.com/30
비지도 학습(Unsupervised Learning)이란? : K-means algorithm
시작하며 저번 포스팅에서는 비지도학습(Unsupervised Learning)의 기초 개념을 다뤄보았습니다. 이번 포스팅에서는 Unsupervised Learning의 원리를 알아보고 이것의 대표적인 알고리즘인 'K-means algorithm'에
box-world.tistory.com
K-means Algorithm : Cost 함수
우선 K-means 알고리즘의 Cost 함수를 구성하는 요소에 대해 알아보겠습니다.
우리는 $c^{(i)}$가 i 번째 데이터 $x^{(i)}$가 속한 Cluster 값을 의미하고, $μ_k$ 는 K번쨰 Cluster의 Cluster Centroid를 의미함을 저번 포스팅에서 배웠습니다. 그리고 새롭게 등장한 $μ_c^{(i)}$는 $x^{(i)}$가 속한 Cluster의 Cluster Centroid를 의미합니다.
K-means 알고리즘의 Cost 함수 J는 위와 같습니다. 이는 DIstortion Cost 함수라고도 불립니다. 이 함수의 Cost 값을 최소화(minimize)하기 위해서는 i 번째 데이터 $x^{(i)}$와 이 데이터가 속한 Cluster의 Centroid인 $μ_c^{(i)}$ 사이의 거리를 최소화 시켜야합니다.
이제 방금 배운 Cost 함수를 이용하여 알고리즘을 어떻게 동작시키는지 알아보겠습니다. 우선 Cluster가 k개라고 할때, K개의 Cluster Centroids를 랜덤으로 지정합니다.
여기서 첫번째 단계인 Cluster assignment step에 의하여, 데이터들을 자기와 가까운 Cluster Centroids의 Cluster로 구분시킵니다. 그리고 두번쨰 단계인 Move Centoirds에 의하여, 그렇게 할당된 각 Cluster의 데이터들의 평균값의 위치로 각 Cluster의 Centroid들을 이동시킵니다. 이 두 가지 단계를 반복적으로 실행하여 최적의 Clustering을 하게 됩니다.
Random Initialization
우리는 저번 시간에 알고리즘의 시작 부분에서 랜덤으로 설정되는 Cluster Centroids의 위치에 따라 결과값이 바뀔 수 있음을 배웠습니다. 구체적으로 이렇게 초기에 위치가 잘못 설정되어 정상적인 Clustering이 되지 못한 결과를 Local optima이라고 합니다.
이러한 문제를 해결하고자 나온 방법이 바로 Multiple Random Initialization입니다. 말 그대로 여러 번 알고리즘을 수행하여 이중 Cost가 가장 작은 값이 나온 Case를 채택하는 것입니다. 예를 들어 알고리즘으 100번 돌리게 되면, 각기 다른 랜덤한 Cluster Centroid에서 출발한 K-means 알고리즘의 100개의 Cost 값들은 각각 다를 것인데, 우리는 이중 가장 작은 Cost 값을 가지는 Case를 취하는 것입니다.
보통 이렇게 반복하는 횟수는 50 ~ 1000회가 적당하고, 이러한 방법은 Cluster의 갯수가 10개 이하일 때 잘 적용됩니다. 만약 그 이상의 Cluster를 가지는 dataset에 사용할 경우 Local optima가 발생할 가능성이 상대적으로 높아 좋지 않은 결과가 나올 수 있습니다.
Choosing the Number of Clusters
dataset를 구분하는 Cluster의 수는 어떻게 결정해야하는지 알아보겠습니다. 결론은 정답은 없고, 따라서 다 해봐야 한다는 것입니다. 그래서 가장 많이 사용되는 것이 Elbow Method입니다.
간단하게 Cluster 개수가 1개일 때부터 시작하여 계속 K를 늘려가며 각 K에 대한 Cost 값을 비교하는 것입니다. 이때 위와 같은 그래프를 보았을 때, 그 모양이 마치 우리가 팔을 구부린 것과 같으며, 저 중 그래프가 꺾이는 지점 즉 팔꿈치에 해당하는 K = 3를 가장 적절한 갯수로 결정하게 됩니다. 그러나 오른쪽처럼 모든 그래프에 이러한 Elbow가 나타나는 것은 아니므로 유의해야합니다.