CURE Algorithm (Clustering Using REpresentatives)

CURE (Clustering Using REpresentatives)

CURE 알고리즘은 k-means와 BFR이 cluster가 정규분포를 따르며, outlier에 취약하다는 단점을 보완하기 위해 만들어진 하이브리드 클러스팅 기법이다. centroid-based aprroach와 all-point approach를 접목하였으며, 타원형이 아닌 모양의 클러스터를 허용한다.

CURE 알고리즘의 과정은 다음과 같다

1) 메인메모리의 용량만큼 샘플 instance를 랜덤하게 뽑는다
2) 초기 클러스터를 형성하기 위해 hierarchical clustering을 이용하여 가까운 점들끼리 그룹핑한다
3) 각 클러스터에서 최대한 멀리 떨어져 있는 representative instances(대표점)를 정해진 수만큼 뽑는다
4) α [0~1]만큼 뽑은 representative instances를 centroid 방향으로 수축시킨다
: α 가 0이라면 all-point approach이며, α 가 1이면 centroid-based approach
5) 모든 instance마다 가장 가까운 representative instances를 포함하는 cluster로 할당한다


CURE알고리즘의 경우 centroid방향으로 대표점들을 수축시켰기 때문에 outlier와의 거리는 더 멀게 측정되므로  k-means와 BFR 기법의 취약점을 보완가능하다!

K-means Clustering (K-평균 군집화)

BFR  Algorithm