군집분석: 비지도 학습 효율적 군집분석 급내 (intra-class) 유사성이 높고 급간 (inter-class) 유사성이 낮다
군집분석의 연구 분야 Scalability. 작은 자료 (수 백개 까지는 잘 적용된다. 예: 200 개 이하) 다양한 종류의 자료. (이진, 범주형, 이산형 등에도 적용 가능) 구형 자료 (spherical data)외의 다양한 형태 (말발굼 자료 등)의 자료에도 적용 가능 잡음 자료나 이상 값 등의 영향 고차원 자료에도 효율적인 방법 결과의 유용성과 해석
자료 Data matrix n: 자료수 p: 변수의 수 Dissimilarity matrix n x n
자료의 형태 구간형 변수 이진 변수 명목형, 순서형 변수 혼합형 변수
구간형변수 표준화 mean absolute deviation 이 표준편차보다 robust 여기서 펴준화 점수 (z-score) mean absolute deviation 이 표준편차보다 robust
거리: Similarity 와 Dissimilarity 두 개체간의 거리: 유사성과 비유사성 Minkowski distance: xi = (xi1, xi2, …, xip), xj = (xj1, xj2, …, xjp) : p-차원인 2 개의 개체 q: 양정수 q = 1, Manhattan 거리
거리 q = 2, Euclidean 거리 기타: 가중 거리 (341쪽). Pearson 상관게수, 기타 특성 d(i,j) 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) d(i,k) + d(k,j) 기타: 가중 거리 (341쪽). Pearson 상관게수, 기타
이진변수 이진자료의 분할표 Simple matching coefficient (symmetric - 중요성이 동일) Jaccard coefficient (asymmetric, 중요성이 다름): Object j Object i
이진변수 (asymmetric) 예 gender: symmetric 기타변수: asymmetric Y, P =>1, N => 0
명목 변수 방법 1: Simple matching 방법 2: 명목형 변수=>이진 변수 m: # of matches, p: total # of variables 방법 2: 명목형 변수=>이진 변수 각 범주에 대해 이진 변수화
순서 변수 xif 를 순위 rif 로 변환 각 변수는 다음과 같은 형식에 의해 [0, 1] 사이의 값으로 표준화 구간형 변수와 같은 방법으로 거리계산
혼합형 DB 에 모든 형식의 자료가 다 있는 경우 가중값을 사용. f :이진 또는 명목 xif = xjf => dij(f) = 0, 기타 =>dij(f) = 1 f : 구간, 표준화 거리 (교재 346 참조) f : 순서형, 순위 표준화
군집방법 Partitioning algorithms: K-means, K-medoids Hierarchy algorithms: dendrogram
K-Means 방법 K 가 주어질 때 다음의 4 단계로 작동 샘플을 k 개의 부분 집합으로 분리 현재의 분할이 군집이 되고 이 분할의 중심 (centroid) 을 계산 각 개체를 가장 가까운 중심에 할당 2 단계 부터 다시 시작. 만약 더 이상 개체의 움직임이 없으면 여기서 마침.
K-Means 방법: 그림
K-Means 장단점 장점 단점 비교적 효율적. O(tkn), 대개 지역적 최적점에 도달. n=개체수, k = 군집수, t = # 반복수. k, t << n. 대개 지역적 최적점에 도달. 단점 중심(mean)이 정의될 때에만 성립. 범주형에는 불가 K 를 먼저 정의해야함 이상값에 매우 민감 non-convex 형의 군집을 발견할 수 없음
K-Means 방법의 변형 초기 k 평균의 선택: 범주형 자료의 처리: k-modes (Huang’98) 계층적 응집모형 (hierachical agglomeration)으로부터 k 와 평균을 초기화 범주형 자료의 처리: k-modes (Huang’98) 평균을 최빈값(modes) 로 대체 범주형 비유사성 측도를 사용 군집의 새로운 중심(modes) 추정을 위해 거리보다 빈도를 사용 구간변수와 범주형 변수의 혼합=> k-means 와 k-modes의 혼합을 사용: k-prototype 방법
K-Medoids 방법 K-means 방법은 몇 개의 이상값에 너무 민감 => PAM (Partitioning Around Medoids, 1987) 평균 대신 대표주자 (medoid)를 선택하고 더 좋은 군집을 만드는 대표주자가 있으면 대체한다. PAM 은 자료수가 작을 때 잘 되지만 큰 자료에는 불안 (non-scalable)
R program for PAM library(cluster) data(votes.repub) votes.diss <- daisy(votes.repub) #euclidean distance votes.clus <- pam(votes.diss, 2, diss = TRUE)$clustering if(interactive()) clusplot(votes.diss, votes.clus, diss = TRUE, shade = TRUE, labels = 1)
K-medoid: iris data: ##irir 자료: k-medoid (PAM): k=3 par(mfrow=c(1,2)) data(iris) iris.x <- iris[, 1:4] clusplot(iris.x, pam(iris.x, 3)$clustering, diss = FALSE, plotchar = TRUE, color = TRUE, shade = TRUE,span=FALSE, line=1)
게층적 군집분석 거리행렬을 사용하여 군집. agglomerative (AGNES) a a b b a b c d e c K 를 먼저 선택할 필요가 없다. 끝나는 지점을 지정해야한다. Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e agglomerative (AGNES) divisive (DIANA)