군집분석: 비지도 학습 효율적 군집분석 급내 (intra-class) 유사성이 높고

Presentation on theme: "군집분석: 비지도 학습 효율적 군집분석 급내 (intra-class) 유사성이 높고"— Presentation transcript:

1 군집분석: 비지도 학습 효율적 군집분석 급내 (intra-class) 유사성이 높고
급간 (inter-class) 유사성이 낮다

2 군집분석의 연구 분야 Scalability. 작은 자료 (수 백개 까지는 잘 적용된다. 예: 200 개 이하)
다양한 종류의 자료. (이진, 범주형, 이산형 등에도 적용 가능) 구형 자료 (spherical data)외의 다양한 형태 (말발굼 자료 등)의 자료에도 적용 가능 잡음 자료나 이상 값 등의 영향 고차원 자료에도 효율적인 방법 결과의 유용성과 해석

3 자료 Data matrix n: 자료수 p: 변수의 수 Dissimilarity matrix n x n

4 자료의 형태 구간형 변수 이진 변수 명목형, 순서형 변수 혼합형 변수

5 구간형변수 표준화 mean absolute deviation 이 표준편차보다 robust
여기서 펴준화 점수 (z-score) mean absolute deviation 이 표준편차보다 robust

6 거리: Similarity 와 Dissimilarity
두 개체간의 거리: 유사성과 비유사성 Minkowski distance: xi = (xi1, xi2, …, xip), xj = (xj1, xj2, …, xjp) : p-차원인 2 개의 개체 q: 양정수 q = 1, Manhattan 거리

7 거리 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 상관게수, 기타

8 이진변수 이진자료의 분할표 Simple matching coefficient (symmetric - 중요성이 동일)
Jaccard coefficient (asymmetric, 중요성이 다름): Object j Object i

9 이진변수 (asymmetric) 예 gender: symmetric 기타변수: asymmetric
Y, P =>1, N => 0

10 명목 변수 방법 1: Simple matching 방법 2: 명목형 변수=>이진 변수
m: # of matches, p: total # of variables 방법 2: 명목형 변수=>이진 변수 각 범주에 대해 이진 변수화

11 순서 변수 xif 를 순위 rif 로 변환 각 변수는 다음과 같은 형식에 의해 [0, 1] 사이의 값으로 표준화
구간형 변수와 같은 방법으로 거리계산

12 혼합형 DB 에 모든 형식의 자료가 다 있는 경우 가중값을 사용. f :이진 또는 명목
xif = xjf => dij(f) = 0, 기타 =>dij(f) = 1 f : 구간, 표준화 거리 (교재 346 참조) f : 순서형, 순위 표준화

13 군집방법 Partitioning algorithms: K-means, K-medoids
Hierarchy algorithms: dendrogram

14 K-Means 방법 K 가 주어질 때 다음의 4 단계로 작동 샘플을 k 개의 부분 집합으로 분리
현재의 분할이 군집이 되고 이 분할의 중심 (centroid) 을 계산 각 개체를 가장 가까운 중심에 할당 2 단계 부터 다시 시작. 만약 더 이상 개체의 움직임이 없으면 여기서 마침.

15 K-Means 방법: 그림

16 K-Means 장단점 장점 단점 비교적 효율적. O(tkn), 대개 지역적 최적점에 도달.
n=개체수, k = 군집수, t = # 반복수. k, t << n. 대개 지역적 최적점에 도달. 단점 중심(mean)이 정의될 때에만 성립. 범주형에는 불가 K 를 먼저 정의해야함 이상값에 매우 민감 non-convex 형의 군집을 발견할 수 없음

17 K-Means 방법의 변형 초기 k 평균의 선택: 범주형 자료의 처리: k-modes (Huang’98)
계층적 응집모형 (hierachical agglomeration)으로부터 k 와 평균을 초기화 범주형 자료의 처리: k-modes (Huang’98) 평균을 최빈값(modes) 로 대체 범주형 비유사성 측도를 사용 군집의 새로운 중심(modes) 추정을 위해 거리보다 빈도를 사용 구간변수와 범주형 변수의 혼합=> k-means 와 k-modes의 혼합을 사용: k-prototype 방법

18 K-Medoids 방법 K-means 방법은 몇 개의 이상값에 너무 민감
=> PAM (Partitioning Around Medoids, 1987) 평균 대신 대표주자 (medoid)를 선택하고 더 좋은 군집을 만드는 대표주자가 있으면 대체한다. PAM 은 자료수가 작을 때 잘 되지만 큰 자료에는 불안 (non-scalable)

19 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)

20

21

22 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)

23

24

25 게층적 군집분석 거리행렬을 사용하여 군집. 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)

26