Clustering 전반부 - 3단계

• What is cluster analysis
• Categories & Basic Concepts of Clustering
• Partitioning Methods
• Hierarchical Methods

⬆️ 여기까지

• Integration of Hierarchical & Distance-based Clustering
• Density Based Methods
• Summary

---

What is cluster analysis

• Cluster: 같은 cluster 안의 데이터는 유사하다
• Cluster Analysis: data 사이의 유사함을 찾아내는 것
• Unsupervised learning
• 유사도는 distance function으로 알아냄
• Good clustering ➡️ cluster 안의 유사도가 높음

Categories & Basic Concepts of Clustering

• Major clustering Approaches
  • Partitioning approach : partition으로 나눠놓고 특정 기준에 따라 평가한다
    • ex) k-means, k-medoids, PAM, CLARA
  • Hierarchical approach : data set을 계층 분해를 한다
    • ex) Agnes, Diana , BIRCH, Chameleon
  • Density based approach : density function을 기반으로 함
    • ex) DBSCAN, OPTICS
• Centroid: cluster의 가운데 (가상의 점)
• Radius: 어떤 점으로부터 centroid까지의 거리
• Diameter: cluster 내의 가능한 모든 점들의 평균 거리
• Distance between Clusters
  • Single Link: cluster의 원소 간의 최소거리
  • Complete Link: cluster의 원소 간의 최대 거리
  • Average: 서로 다른 cluster의 원소 간의 평균 거리
    • Centroid: 두 cluster의 centroid 간의 거리
    • Medoid: 두 cluster의 medoid 간의 거리

Partitioning Methods

Data set을 기준점(centroid 또는 medoid 같은 거)으로부터

cluster 내 모든 거리가 제일 작게 되는 k개의 cluster로 partition 하는 것
[기준점-representative]

 

💭방법론

• 모든 partition 다해보기 - 불가능
• 휴리스틱 방법
• k-means: 기준점 centroid(가상점)
• K-medoids: 기준점 medoid(실제점)

K-Means Clustering

1. 랜덤으로 k개의 seed point를 정함, 나머지 점들을 각 seed에 배정 (initialize)
2. 생성된 cluster의 centroid를 다시 seed point로 정함
3. 그 seed point와 가까운 점들을 할당해 새로운 cluster 생성
4. 2로 돌아가 반복 - 더 이상 새로운 할당이 없을 때까지

장점:효율적임 시간복잡도 $O(n•k•t) $ n이 data 수, k 가 cluster 수, t가 반복 수 | 보통 k,t << n
PAM $O(k(n-k)^2$), CLARA $O(ks^2+k(n-k))$보다 효율적

Comment : local optimum에 종료될 수도 있음

한계:

• 몇 개의 cluster을 만들지 개발자가 정해줘야 함
• Noise와 outlier에 취약함
• Non-convex 모양일 때 cluster 찾기 어려움 (Non-convex는 여러 개의 극소값을 갖는 그래프)
• 원 형태를 찾는 것에 최적화

Variations of the k-means

K-means는 numerical는 잘하는데 다른 건 기준 잡기가 어려움

K-modes

• categorical data만 다룸
• Distance를 mismatch 된 feature의 수로 판단함
• 가장 많이 나타나는 feature를 기준으로!

K-Medoids

K-means는 가상의 점을 사용해서 outliers에 취약했음
그래서 k-medoids는 실제 하는 점인 medoid를 사용하자

PAM

1. 랜덤하게 k개의 seed object를 정하기
2. Cluster 내 non-seen object를 seed로 바꿨을 때 총 distance가 적어진다면 바꾼다. (더 좋은 seed 찾기)
   • d(non-seed-j, seed-after)-d(non-seed-j, seed-before)
3. 다시 새로운 seed를 기준으로 cluster를 만든다.
4. 변화가 없을 때까지 반복한다

📌non-seed에게 발생할 수 있는 상황

• 가까운 seed가 새로운 seed로 바뀌면서 같은 cluster에 배정
• 가까운 seed가 다른 cluster seed로 바뀌면서 다른 cluster에 배정
• 변화 없음

장점: k-means보다 noise나 outlier에 강함
단점: 큰 data set에는 느려짐
➡️sampling으로 해결하자 이게 CLARA

CLARA(Clustering Large Applications)

1. 전체 dataset에서 여러 개의 sample data set을 뽑음
2. 각 data set에 대하여 PAM 적용해 medoids 찾음
3. 찾은 medoid를 전체 데이터에 대하여 평가함
4. 제일 좋은 medoid 선택

✅여러 sample 중의 여러 medoid 중에 best 찾기

장점: PAM 보다 빠름
단점: sample size에 따라 효율성 결정됨, 진짜 좋은지는 알 수가 없음 sampling의 한계

Hierarchical Methods

마찬가지로 거리로 clustering 함
몇 개의 cluster를 만들어야 하는지 정해줄 필요 없음!
대신 언제 끝낼지 정해줘야 함

---

작은 것부터 모아 모아 크게 만드는 게 AGNES

아그네스가 그루의 사랑을 먹어먹어 자라

큰 것부터 잘라 잘라 작게 만드는 게 DIANA

평타로 잘라 잘라

---

Agnes (AGglomerative NESting)

먹어먹어 자라였음

1. Single link(가 뭐였냐면 최소거리)를 이용해 cluster와 cluster 사이 거리 측정
2. 최소한의 dissimilarity를 가지면 node들을 합침(유사하면 합친다는 소리임)

복잡도: 모든 node를 다 비교해야 함 $n(n-1)/2$
Dendrogram으로 어디까지 병합할 건지 정함

DIANA(DIvisive ANAlysis)

평타로 잘라 잘라였음

Agnes 반대
결과적으로 각 node가 cluster 한 개일 때까지 나눔
한 개의 커다란 cluster에서부터 시작해 가능한 가장 큰 2개의 cluster로 나눔
복잡도: 가능한 모든 cluster를 비교해 봐야 함 $2^{n-1}-1$

출처: Exploreing K-Means with Internal Validity Indexes for Data Clustering in Traffic Management System