[태그:] Clustering

K-means 클러스터링의 전역탐색은 NP-hard 문제이다.그러므로 EM(Expectation Maximization)과 Hill Climbing 기법을 사용하여 K-means 클러스터링의 지역최소값을 구해내는 것이 일반적이다. Hill Climbing기법의 최대 약점은 Non-convex 공간에서 탐색 시작위치에 매우 민감하다는 점이다.이를 해결하기 위한 방법으로는 크게 두 가지가 있는 것 같다. 첫째는 Climbing의 이동 폭이나 방향을 조정하는 것이다.일부러 눈앞에 보이는 가장 좋은 길을 포기하고 다른 길을 찾아 모험을 떠나는…