Clustering 전반부 - 2단계

• 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 안의 데이터는 유사하다
• Unsupervised learning
• Good clustering ➡️ cluster 안의 유사도가 높음

Categories & Basic Concepts of Clustering

• Major clustering Approaches
  • Partitioning approach : partition으로 나눠놓고 특정 기준에 따라 평가한다
  • Hierarchical approach : data set을 계층 분해를 한다
  • Density based approach : density function을 기반으로 함
• 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로 돌아가 반복 - 더 이상 새로운 할당이 없을 때까지

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. 변화가 없을 때까지 반복한다

CLARA(Clustering Large Applications)

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

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$