4.1 Motivation
4.2 Proximity Matrix
- Similarity 또는 dissimilarity 를 나타내는 matrix
- 예를 들면, correlation, mutual information 또는 3장에서 배웠던 다양한 distance metrics가 있음
- 반드시 metric일 필요는 없음
- Undirected graph일 수 있음
- Normalize 중요
4.3 Types of Clustering
Cluster 종류
- Connectivity
- distance에 기반
- ex. hierachical clustering
- Centroids
- ex. K-means
- Distribution
- ex. Gaussian Mixture
- Density
- connected dense regions
- ex. DBSCAN or OPTICS
- Subspace
- 2차원에 clustering 하는 방법 (Features and observations)
- Connectivity
종류에 따라 input data가 similarity 또는 dissimilarity 로 달라짐/ 알맞은 input 넣는것이 중요
차원의 저주에 대한 해결 필요
- 예를 들어 PCA 로 차원을 줄인 새 데이터를 사용
- CH2 방법론 사용
4.4 Number of Clusters
4.4.1 Observations Matrix
N variables that follow a multivariate Normal distribution characterized by a correlation matrix ρ
Strong common component가 있는 경우 2장에서 다뤘던 detoning 방법 사용할 것
Correlation clustering 접근 방식
- (a) di,j=√12(1−ρi,j): distnace metrics 적용
- (b) Correlation matrix를 X matrix 그대로 사용
- (c) Derive X matrix Xi,j=√12(1−ρi,j): distance of distances approach
이 섹션에서는 observation matrix Xi,j=√12(1−ρi,j) 로 정의
- Distance matrix 처럼 보이지만 observation matrix 임. distances를 다시 구할 수 있음.
4.4.2 Base clustering
Clustering 할 때 몇개의 cluster가 가장 optimal 한지 구하는 것이 목적: "Opitmal K"
silhouette score introduced by Rousseeuw(1987) 이용하여 K 구하기
- Si=bi−aimax{ai,bi};i=1,...,N
- ai: i와 같은 클러스터 안의 다른 요소들 사이의 average distance
- bi: i와 가장 가까운 클러스터 요소들 사이의 average distance
- ai 는 작을수록, bi 는 클수록 좋음
- Si=1 이면 잘 된 클러스터, -1 이면 poor
q=E[{Si}]√V[{Si}]
- Cluster quality
- 높을수록 좋음
K=2,... max 까지 Loop 돌리면서 q 값이 가장 클 때의 K값을 선택
Double loop
- First loop: Given initialization, 높은 q 값 찾기
- Second loop: 첫번째 루프를 init를 바꾸면서 반복
- 최종적으로 가장 높은 q 값 찾기
4.4.3 Higher-level Clustering
Clustering 개선
- 4.4.2에서 클러스터링을 했을 때 q의 평균보다 작은 클러스터들을 모아서 평균보다 작은 클러스터가 없을 때까지 계속 클러스터링 함.
방법
- K1={qk|ˉq,k=1,...K}K1<K
- If K1≥2, then rerun the clustering of the items
- 클러스터를 반복할 때마다 평균 cluster quality q 보다 작은 클러스터는 다시 클러스터링을 진행함. 결국 한개의 클러스터가 남을 때까지 클러스터링을 다시해서 quality를 높임