Basic concepts of Partitioning methods
partitioning method는 초기 분할(initial partitioning)을 하고 반복적으로 재분배 테크닉(iterative relocation technique)을 사용해 분할을 개선한다.
-k-means, k-medoids, PAM
K-means clustering
1. 전체 데이터 포인트 중 임의로 k 개를 클러스터의 시작 중심점으로 선택
2. 모든 데이터 포인트를 가장 유사한 클러스터로 할당(distance similarity (Euclidean distance))
3. 각 클러스터에 할당된 포인터들을 기반으로 클러스터의 중심 점을 업데이트
4. criterion function이 통합될때 까지 2-3번 과정을 반복
Evaluation criterion
$SSE=\sum_{i=1}^k \sum_{p\in C_i} dist^2(m_i, p) $
$p$ : a point in a cluster $C_i$
$m_i$ : the mean of a cluster $C_i$
Remarks
강점 : efficient
O(tkn) : n = 데이터 포인트 수, k = 클러스터의 수, t = iteration 횟수
Comment
가끔 local optimal 에서 중단
Limitation
continuous space에서만 적용.
k를 미리 선언해야 함.
다양한 사이즈나 밀도, 형태의 클러스터에 적용하기 어렵다.
outlier에 민감하다.
-> k-Medoids (클러스터에서 가장 중심에 위치한 포인트를 충심으로)
A medoid can be defined as the object of a cluster whose average dissimilarity to all the objects in the cluster is minimal. i.e. it is a most centrally located point in the cluster. -k-medoids, Wikipedia
PAM(Partitioning Around Medoids) : 처음 medoids에서 시작해 클러스터의 total distance가 개선되면 modoids를 수정하는 작업을 반복
데이터 셋이 클수록 계산 복잡도에서 비효율적이다.
by "Data mining and knowledge discovery", kse525, Prof. Jae-gil, Lee