8. 클러스터링 : k-means

개요 : K-Means

그루핑을 할 때마다 재계산. 따라서 hierarchical와 속도에서 차이가 난다.
먼저 클러스터의 갯수 k를 정하고, 거리를 계산한다.
- hierarchical과의 가장 큰 차이점.
자료가 있다면, 계산을 할 때마다 공간을 나눈다.

알고리즘과 결과

k를 정한다. 최소한 2보다는 커야 한다.
각 클러스터의 centroid를 랜덤으로 찍고, 거리 계산.
centroid에서 가장 가까운 점을 고른다. 이를 기준으로 클러스터링.
묶인 파트를 기준으로 또 centroid 찍기.
반복 → 안 묶일때까지!

묶이지 않는 기준 = 점들이 움직이지 않을 경우.

결과 1 : 최적의 centriod.

결과 2 : 각 점별 할당된 그룹을 알려줌 (파티셔닝 결과)

근접성 파악

클러스터링, 다변량 scaling, 비선형 차원축소 기법에서 중요
- 각각의 변수를 하나씩 표준화하는 것 ⇒ marginally

min=0, max=1 ⇒ 각 변수들의 차이 고려

{x_i}^{*} = {{x_{ij}} - min(\underline{x}) \over max(\underline{x})- min(\underline{x})}

mean = 0, std = 1 ⇒ z 표준화

{x_{ij}}^{*} = {x_{ij} - \overline{x_j}\over s_{x_j}}

이산형 데이터를 클러스터링? 좋은 데이터라고 보기는 어렵다.

임의로 숫자를 할당
단, 0과 1로 코딩되는 경우(성별) 클러스터링 가능

유사도 측정 기법

코사인 유사도 (연속형 변수)
상관관계 유사도 (연속형 변수)
jaccard 계수 (이산형 변수)

1 0

1 a b a+b

0 c d c+d

a+c b+d a+b+c+d

a와 d가 높을수록 두 변수의 상관성이 비슷하다.

적어도 1이라고 응답할 가능성을 따진다. (일종의 조건부 확률)

범주형 자료분석 등에서 쓰임.
Ochiai 측도
Simple matching 계수

비유사도 측정 기법

유클리드 거리
마할라노비스(mahalanobis) 거리
$(\bold{x_i} - \bold{x_j})^T ~\Sigma^{-1}~ (\bold{x_i} - \bold{x_j})$
다변량 분포의 exp 부분을 가져 온 것.

유사하면 유사할수록, 더 값이 작아진다. 스케일 역시 반영한다.
민코프스키 거리

유사도 ↔ 비유사도 변환

$\delta = 1 - s$
$\delta = c - s$
$\delta = \sqrt{2(1-s)}$
$\delta = \sqrt{2(1-s)}$
$s = {(1 + \delta)}^{-1}$

예시문제: K-Means

준비하기

데이터를 준비한다. 시드값은 1234. 정규분포에서 뽑기.

x ⇒ 12개. 평균은 1,2,3을 각각 4번씩. 표준편차는 0.2

y ⇒ 12개. 평균은 1,2,1을 각각 4번씩. 표준편차는 0.2

해답

# 데이터 준비하기
rm(list=ls())
set.seed(1234)
x = rnorm(12, mean=rep(1:3, each=4), sd=0.2)
y = rnorm(12, mean = rep(c(1, 2, 1), each=4), sd=0.2)

파트 1 : kmeans() 쓰기

kmeans()는 유클리드 거리를 기준으로 한다.

라이브러리 stats 사용
데이터프레임 생성
kmeans() 를 이용해 클러스터링을 한다. centers = 3

힌트 : 반복 횟수(iter.max)를 100회로 지정.

(안 하면 클러스터링이 1번으로 끝)
변수 kmeans_Obj 에 값을 할당한다.

해답

library(stats)
dataFrame = data.frame(x, y)
kmeans_obj = kmeans(dataFrame, centers=3, iter.max=100)

변수 kmeans_obj를 보고, 클러스터 이름을 보자.

해답

names(kmeans_obj)
kmeans_obj$cluster

> names(kmeans_obj)
[1] "cluster"      "centers"     
[3] "totss"        "withinss"    
[5] "tot.withinss" "betweenss"   
[7] "size"         "iter"        
[9] "ifault"      
> kmeans_obj$cluster
 [1] 3 3 3 3 1 1 1 1 2 2 2 2

해답

cluster : 몇 번째 데이터가 어디 그룹인지 나타낸다.
centers : 중심점을 보여준다.
totss : 그룹 내 거리 제곱의 합 (sum of squares)
withinss : Vector of within-cluster sum of squares, one component per cluster.
tot.withinss : withiness의 합
betweenss : between-cluster sum of squares
size : The number of points in each cluster.
iter : 반복횟수
ifault : indicator of a possible algorithm problem

파트 2 : 그림 그려보기

솔루션을 그림으로 그려보자.

해답

힌트 : 색은 col=kmeans_obj$cluster 로, 플러스 표시는 points()로 조정.

plot(x, y, col=kmeans_obj$cluster, cex=2, pch=19)
points(kmeans_obj$centers, pch=3, cex=2)

그러나 이러한 그림은 변수가 2~3개 이상인 경우 그리기 힘들다.

그러한 경우에는 히트맵을 써야 한다.

파트 3 : 히트맵 그리기

heatmap.2() 대신 image()를 이용해서 덴드로그램 그리고, 센터 찾기

heatmap.2() 로 k-means 클러스터링을 그리면 너무 복잡하다.

데이터프레임 > 행렬
행렬을 전치한 후 순서를 지정.

그림을 그리고 난 뒤, 센터도 한번 확인해보자.

해답

# 데이터프레임을 행렬로
datamat = as.matrix(dataFrame)[sample(1:12),]

# 덴드로그램 그리기
par(mfrow=c(1,2))
image(t(datamat)[, nrow(datamat):1],
      yaxt = "n", 
      main="original data")

image(t(datamat)[,order(kmeans_obj$cluster)],
      yaxt = "n", 
      main="original data")

# 센터 찾기
kmeansObj$centers

클러스터 평가하기

몇 개의 클러스터가 적절한가?
클러스터링의 목적: 다른 그룹과 잘 분리, 같은 그룹과 잘 묶임.

실루엣 통계량

number of groups를 추정하는 방법

a(i)는 검정 사각형 표시된 데이터와 파란색 군집 내 포인트들 사이의 평균
b(i)는 검정 사각형 표시된 데이터와 오렌지색 군집 내 포인트들 사이의 평균

가장 이상적인 것은

한 군집의 객체들이 다 붙어있어 a(i)가 0값을 가지는 경우.
이 경우엔 분모, 분자에 b(i)만 남기 때문에 실루엣 값은 1.

반대로 최악의 경우엔

군집간의 거리가 0으로 수렴해 b(i)가 0값을 가지는 경우.
이 때는 분모엔 a(i)가 남고 분자엔 -a(i)가 남기 때문에 실루엣 값은 -1
이 경우 자료를 더 잘라야 한다. (k가 너무 작음)

결론적으로 다음과 같이 해석 가능.

1에 가까울 수록 군집화가 적절히 되었다.
1에 가까울 수록 군집 결과가 타당하지 못하다.

일반적으로 실루엣 > 0.5 데이터의 클러스터링이 잘 되었다고 판단한다.

예시문제 1

silhouette()를 이용해 계산하고, 클러스터를 그리기.

기본적으로 유클리드 거리를 쓴다는 것을 기억할 것.

해답

# 클러스터 라이브러리 불러오기
library(cluster)
# 거리 계산
data.dist = dist(datamat)
data.km2 = kmeans(datamat, centers=2)
data.km3 = kmeans(datamat, centers=3)
data.km4 = kmeans(datamat, centers=4)

# silhouette() 이용하기
data.km2.sil = silhouette(data.km2$cluster, data.dist)
data.km3.sil = silhouette(data.km3$cluster, data.dist)
data.km4.sil = silhouette(data.km4$cluster, data.dist)

# 그리기
par(mfrow=c(1, 3))
plot(data.km2.sil)
plot(data.km3.sil)
plot(data.km4.sil)

결과 해석하기

y축 : 데이터의 row number. 잘린 부분은 그룹을 나누는 경계선

x축 : 실루엣 값.

클러스터 2개인 경우
- 1: 4 | 0.74 ⇒ 4개가 묶였고, 평균 값이 0.74`
- 2: 8 | 0.48 ⇒ 8개가 묶였고, 평균 값이 0.48
클러스터 3개인 경우
- 평균 실루엣 점수가 제일 높다. 제일 좋은 케이스
클러스터 4개인 경우
- 4번째 클러스터 ⇒ 원소 1개, 거리가 0으로 나온다. (single term)
- k가 크면 클수록, 해석이 어려워진다.

예시문제 2 : 비교하기

hclust() 와의 비교

cutree()로 k개만큼 쪼개기.

해답

hcluster <- hclust(dist(dataMatrix))
plot(hcluster)

hclust.k2 <- cutree(hcluster, k=2)
str(hclust.k2)
table(hclust.k2)
hclust.k2

hclust.k3 <- cutree(hcluster, k =3)
table(hclust.k3)
hclust.k3

hclust.k4 <- cutree(hcluster, k =4)
table(hclust.k4)
hclust.k4

hclust()에 사각형 씌우기

해답

plot(hcluster)
rect.hclust(hcluster, k=2)

plot(hcluster)
rect.hclust(hcluster, k=4)

kmeans()와 비교해보자.

	1	0
1	a	b	a+b
0	c	d	c+d
	a+c	b+d	a+b+c+d