개요 : 계층적 클러스터링
- hiercial clustering, 줄여서 hclustering 이라고 함.
- 고차원의 데이터를 시각화할 때 사용하는 방법
- 요점은 가까이에 있는 대상들을 묶어서 그룹으로 만드는 것.
- 다음과 같은 질문을 던질 수 있다
- 가까운 것을 어떻게 정의할 것인가?
- 어떻게 묶을 것인가?
- 그룹을 어떻게 시각화할 것인가?
- 어떻게 그룹을 해석할 것인가?
supervised vs unsupervised
- supervised : 클래스 레이블이 존재, 이를 통해 어떠한 그룹들이 있는지 확인할 수 있다.
- unsupervised : 클래스 레이블이 없다. 따라서 얼마나 많은 그룹들이 있는지는 모른다.
클러스터링 순서
- 패턴 인식
- Pattern Proximity measure
- 그룹핑
- 데이터 추상화
- Cluster Assessment
거리와 가까움
표준화가 항상 좋지는 않다.
격차가 줄수 있음
점 간의 거리 (distance)
거리를 정의하는 방법으로, 크게 2가지가 있다.
- 유클리드 거리
\sqrt{\textstyle\sum_{i=1}^{n}~
(X_{ik}-X_{ik})^2 }
- 맨해튼 거리 (절댓값 거리. 택시기하학에서 확인 가능)
- 민코프스키 거리 : 거리의 일반화
\Big\{\textstyle\sum_{i=1}^{n}~
|X_{ik}-X_{ik}|^{\lambda} \Big\}^{1/\lambda}
- \lambda = 1 이면 맨해튼 거리 (R에서는 parameter로 p값을 조정)
- \lambda = 2 이면 유클리드 거리 (R에서는 parameter로 p값을 조정)
그룹 간의 거리 (linkage)
- 총 5가지 : single, complete, average, centroid, ward’s method
- single linkage
- 모든 거리 중 가장 짧은 거라, nearest neghibor
- 데이터 A에 점 3개, 데이터 B에 점 3개. 거리는 총 9개
- 모든 거리 중 최솟값 = single linkage
- 문제점 : chaining (다른 군집끼리 걸리는 현상)
- complete linkage
- 모든 거리 중 가장 긴 거리, furthest neighbor
- 데이터 A에 점 3개, 데이터 B에 점 3개. 거리는 총 9개
- 모든 거리 중 최댓값 = complete linkage
- Average linkage
- 모든 거리 중 평균, average neighbor
- 데이터 A에 점 3개, 데이터 B에 점 3개. 거리는 총 9개
- 모든 거리 중 최댓값 = complete linkage
- centroid linkage
- 그룹의 중심끼리 평균 내기
- 데이터 A에 점 3개, 데이터 B에 점 3개. 거리는 총 9개
- A의 평균점과 B의 평균점 간의 거리 = centroid linkage
- 단점 : reversal
- 단계가 올라 갈수록 오히려 거리가 멀어질 수 있다.
- ward’s method
d_c(r,x) = {n_rn_s{d_{rs}^2} \over (n_r + n_s)}
- {d_{rs}}^2 : r-th와 s-th의 거리 제곱합
- sum of squares로 인해, outlier에 민감할 수 밖에 없다.
Dendrogram (계층 구조도)
계층 구조도라고 할 수 있다. (트리 구조)
- 아래 : distance가 작음. 위 : distance가 큼
- 어디에서 잘랐냐에 따라 그룹의 갯수가 달라짐.
- linkage에 따라 다른 그림이 나올 수 있다.
덴드로그룹 : 어디서 자를까?
해결책 1 : 표를 그린다.
| K | G | n | mean | sd | min | max |
| 2 | 1 | 4 | ||||
| … | 2 | 8 | ||||
| … |
해결책 2 : heatmap 그리기
- 색을 통해 정도의 차이를 표현
- 그룹 간의 유사성, 변수 간의 유사성 동시에 표기
덴드로그램, 그림만 보고 자르는 것은 위험하다.
차원이 많아졌을 때 그림으로 알 수 없고, 위험하다.
R언어에서 덴드로그램 다루기
- 자른다.
예시문제 1
문제 1 : 시뮬레이션 데이터
데이터를 만들어주고, 분포를 본다.
- 시드값 1234
- x 데이터, y 데이터 만들기
- 그래프 그려보기
해답
r
set.seed(1234)
x = rnorm(12, rep(1:3, each=4), 0.2)
y = rnorm(12, rep(c(1, 2, 1), each=4), 0.2)
plot(x, y, col="blue", pch=19, cex=2)
text(x + 0.05, y + 0.05, labels=as.character(1:12))
문제 2 : 거리행렬
거리행렬을 구해본다.
- 데이터프레임를 행렬로 바꾸고, rdistxy에 할당.
- 대각원소들을 최대화한다.
해답
r
# 거리행렬 만들기
rdist.xy = dist(data.frame(x, y))
rdist.xy = as.matrix(rdist.xy)
# 대각원소의 값 늘리기
diag(rdist.xy) = diag(rdist.xy) + 1000
몇 번째 점이 가장 가까운지 구하기
해답
r
# 가장 가까운 점
ind1 = which(rdist.xy == min(rdist.xy), arr.ind=TRUE)
ind1
그래프로 가장 가까운 점 표기하기
해답
r
plot(x, y, col="blue", cex=2, pch=19)
text(x + 0.05, y + 0.05, as.character(1:12))
points(x[ind1[1, ]], y[ind1[1, ]], col="orange", cex=2, pch=19)
문제 3 : 덴드로그램과 1st tree
덴드로그램 만들고, 자르기
- 덴드로그램을 만든다.
hclust(),dist(): 정보 as.dendrogram()을 사용해 잘리는 구간을 확인한다.cut()을 이용해 자른다.
해답
r
# 덴드로그램 만들기
hclustering = hclust(dist(data.frame(x, y)))
plot(hclustering)
hcluster = as.dendrogram(hcluster)
# 덴드로그램의 잘리는 구간 확인하기
hclustering$height
# 덴드로그램 자르기
cutDendro = cut(hclustering, h = hclustering$height[1] + 0.0001)
덴드로그램 그려보기
- 자른 덴드로그램의 내림차순 중 마지막. 구조는 리스트
- y축을 없애준다. 힌트)
yaxt = "n"
해답
r
# 덴드로그램만 그려보기
plot(cutDendro$lower[[11]], yaxt="n")
플롯과 같이 시각화하기
해답
r
# 플롯과 같이 그리기
par(mfrow=c(1, 2))
plot(x, y, col="blue", cex=2, pch=19)
text(x + 0.05, y + 0.05, as.character(1:12))
points(x[ind1[1, ]], y[ind1[1, ]], col="orange", cex=2, pch=19)
text(x + 0.05, y + 0.05, as.character(1:12))
points(x[ind1[1, ]], y[ind1[1, ]], col="orange", cex=2, pch=19)
plot(cutDendro$lower[[11]], yaxt="n", main="Begin building tree")
문제 4 : 덴드로그램과 2nd tree
2번째로 가까운 점 찾기
order(rdist.xy) : 순서를 지정
해답
r
# 플롯 준비 : 2번째로 가까운 point 찾기
nextmin = rdist.xy[order(rdist.xy)][3]
ind2 = which(rdist.xy == nextmin, arr.ind=TRUE)
ind2
덴드로그램 : 두 번째 파트 자르기
해답
r
# 덴드로그램 : 두 번째 파트 자르기
cutDendro2 = cut(dendro, h=(hcluster$height[2] + 0.00001))
hcluster$height
cutDendro2$lower
플롯 1개 + 줄기 2개 그리기
해답
r
# 플롯
par(mfrow=c(1,3))
plot(x, y, col="blue", pch=19, cex=2)
text(x+0.05, y+0.05, labels=as.character(1:12))
points(x[ind1[1, ]], y[ind1[1, ]], col="orange", pch=19, cex=2)
points(x[ind2[1, ]], y[ind2[1, ]], col="red", pch=19, cex=2)
# 줄기 1
plot(cutDendro2$lower[[10]], yaxt="n")
# 줄기 2
plot(cutDendro2$lower[[5]], yaxt="n")
문제 5 : 히트맵 그리기
-
gplots라이브러리 부착 -
데이터프레임 > 행렬 >
heatmap.2()사용하기 -
옵션 : trace (발자취, 자국), notecol (cellnote의 색), cellnote (값 표기),
density.info (부가설명 추가), dendrogram, key (color key 표기 여부)
해답
r
library(gplots)
datamat = as.matrix(data.frame(x=x, y=y))
heatmap.2(datamat, trace='none', notecol = 'black',
cellnote=round(datamat, 3), density.info = 'none')
row의 덴드로그램만 보기
해답
r
heatmap.2(datamat, trace='none', notecol='black',
cellnote=round(datamat, 3), density.info='none',
dendrogram="row")
col의 덴드로그램만 보기
해답
r
heatmap.2(datamat, trace='none', notecol='black',
cellnote=round(datamat, 3), density.info='none',
dendrogram="col")
예시문제 2
문제 1 : 유클리드, complete
덴드로그램을 그려보자.
해답
r
# 데이터프레임 만들기
dataFrame = data.frame(x=x, y=y)
# 거리: 유클리드, linkage: complete
hc1 = hclust(dist(dataFrame))
plot(hc1, main="Euclidean distance/complete")
이 녀석 역시 잘라보자.
해답
r
# 거리: 유클리드, linkage: complete
hc1 = hclust(dist(as.data.frame(x=x, y=y)))
plot(hc1, main="Euclidean distance/complete")
문제 2 : absoulte / centroid
해답: 2번
r
# 거리: absolute, linkage: centroid
hc2 <- hclust(dist(dataFrame, method="minkowski", p=1), method="single")
plot(hc2, main="Absolute/Centroid")
문제 3 : 변수 x만 클러스터링
해답: 3번
r
# x만 클러스터링
hClustering2 <- hclust(dist(x))
plot(hClustering2)
문제 4 : 변수 y만 클러스터링
해답: 4번
r
# y만 클러스터링
hClustering3 <- hclust(dist(y))
plot(hClustering3)
문제 5 : 정규화하기
보통 단위가 다를때 정규화를 해준다.
해답: 5번
r
# 정규화
dataFrame2<-scale(dataFrame)
hClustering4 <- hclust(dist(dataFrame2))
plot(hClustering4)