k-means 알고리즘

- 개요

k-means 알고리즘은 데이터를 군집하는 간단하고 자주 사용되는 기법이다. k-means를 사용하면 데이터를 지정한 k개의 군집으로 나눌 수 있다.

이러한 k-means 알고리즘은 복잡한 통계 없이 간단한 원리를 사용하며, 휴리스틱 과정을 사용하여 효율적으로 데이터를 유용한 군집으로 나눌 수 있다.

- k-means 알고리즘

간단히 작동 순서를 살펴보면, 최초에는 무작위로 k개의 중심 데이터를 선정하고, 해당 데이터로부터 각 데이터의 거리(유클리디언, 맨하탄 등)을 계산한다. 그 거리의 평균이 작은 곳으로 중심점을 변경하고 다시 거리를 계산하는 것을 반복하여 최적의 군집을 찾을 수 있다.

정리하자면,

입력값

1. k: 클러스터 수
2. D: n 개의 데이터 오브젝트를 포함하는 집합

출력값: k 개의 클러스터

알고리즘

1. 데이터 오브젝트 집합 D에서 k 개의 데이터 오브젝트를 임의로 추출하고, 이 데이터 오브젝트들을 각 클러스터의 중심 (centroid) 으로 설정한다. (초기값 설정)
2. 집합 D의 각 데이터 오브젝트들에 대해 k 개의 클러스터 중심 오브젝트와의 거리를 각각 구하고, 각 데이터 오브젝트가 어느 중심점 (centroid) 와 가장 유사도가 높은지 알아낸다. 그리고 그렇게 찾아낸 중심점으로 각 데이터 오브젝트들을 할당한다.
3. 클러스터의 중심점을 다시 계산한다. 즉, 2에서 재할당된 클러스터들을 기준으로 중심점을 다시 계산한다.
4. 각 데이터 오브젝트의 소속 클러스터가 바뀌지 않을 때 까지 2, 3 과정을 반복한다.

k-means 알고리즘 결과 예시

k-means 알고리즘에서 중요한 점은 k의 설정이다. k가 매우 큰 값으로 설정하면 군집의 동실성이 향상되는 동시에 데이터에 대한 과적합화가 될 위험이 있다.
k를 선택하는 방법은 데이터의 수의 n/2 제곱근으로 설정하는 경험 법칙, 엘보우 기법 등이 있으나, 무엇보다 도메인 지식을 쌓아서 k를 선택하는 것이 중요하다고 생각한다.
k의 선택에 관련된 내용은 추후에 다루도록 할 것이다.

- k-means 알고리즘의 평가

k-means 알고리즘을 사용하고 클러스터링이 얼마나 잘 되었는가를 측정하는 방법으로는 크게 내부평가와 외부평가를 이용할 수 있다.
내부 평가
내부 평가 (internal evaluation) 은 데이터 집합을 클러스터링한 결과 그 자체를 놓고 평가하는 방식이다. 이러한 방식에서는 클러스터 내 높은 유사도 (high intra-cluster similarity) 를 가지고, 클러스터 간 낮은 유사도 (low inter-cluster similarity) 를 가진 결과물에 높은 점수를 준다. 이와 같은 평가 방법은 오로지 데이터를 클러스터링한 결과물만을 보고 판단하기 때문에, 평가 점수가 높다고 해서 실제 참값 (ground truth) 에 가깝다는 것을 반드시 보장하지는 않는다는 단점이 있다.
유사도를 계산하는 방법으로는 Daives-Bouldin index, Dunn index, 실루엣 기법 등이 있다.

외부 평가
외부 평가 방식 (external evaluation)에서 클러스터링의 결과물은 클러스터링에 사용되지 않은 데이터로 평가된다. 다시 말해, 클러스터링의 결과물을 전문가들이 미리 정해높은 모범답안 혹은 외부 벤치마크 평가 기준 등을 이용해서 클러스터링 알고리즘의 정확도를 평가하는 것이다. 이러한 평가 방식은 클러스터링 결과가 미리 정해진 결과물과 얼마나 비슷한지를 측정한다.
외부 평가 방법으로는 Rand measure, F-measure, Jaccard index 등의 기법이 있다.

- k-means 알고리즘 활용분야

k-평균 알고리즘은 시장 분할, 컴퓨터 비전, 지질통계학, 천문학 및 농업 등 광범위한 분야에 적용될 수 있다. 이 기법은 주로 어떤 알고리즘을 수행하기 전 데이터를 전처리 (pre-processing) 하는 용도로 많이 쓰인다. 구체적으로, 이미지 분할, 벡터 양자화, 클러스터 분석 등에 활용될 수 있다.

- k-means 알고리즘 코드

#iris 데이타 이용
data(iris)

#종 정보를 제외하고, 꽃잎과 꽃받침의 길이와 두께 정보만을 이용하여 군집화를
#수행해 보도록 한다. scale() 함수를 이용하여 변수의 값을 표준화하였다.
iris.data <- scale(iris[-5])

kmeans.ch5 <- function(x, k, maxiter=100, nstart=1, epsilon=0.001)
{
# 데이터를 매트릭스 형태로 변환
x <- as.matrix(x)
centers <- k
xrows <- nrow(x)
xcols <- ncol(x)

# 데이터(point들) 중에서 k개의 임의의 데이터(point) 선택
ids = sample(1:xrows, k)
centroids = x[ids, ]

# 클러스터 초기 매트릭스 공간 설정
initial.cluster=matrix(0, 1, xrows)

# iteration 초기 설정
iter=0

## for 혹은 while 필요
# maxiter가 될 때까지 while문 반복
while(iter < maxiter)
{

# k개의 임의의 데이터(point)와의 유클리디언 거리 계산
dists <- apply(x, 1, function(point)
                  sapply(1:nrow(centroids), function(dim)
                                 dist(rbind(point, centroids[dim,]))
                        )
               )
cDists <- t(dists)

# Centers와 가까운 거리들을 계산하여 클러스터 할당
# 결과: 군집 번호, 1~k
cluster.dist = sapply(1:xrows, function(x) which.min(cDists[x,]))

# for every cluster, calculate its new centroid
newCentroids = t(sapply(1:centers, function(c) colMeans(x[which(cluster.dist == c), ])))

## check if change in centroids is significant
delta = sum((newCentroids - centroids) ^ 2)

# 종료조건..
# 1. iteration
# 2. delta
iter=iter+1

if (delta > epsilon) {
    ## use new centroids for next iteration
    centroids = newCentroids
    } else {
    break
    }
}

cluster.size <- c(table(cluster.dist)[1:centers])

# 출력 함수 설정
# 1. cluster size
# 2. cluster means
# 3. cluster vector

structure(list("Cluster size"=cluster.size , "Cluster means"=newCentroids, 
               "Cluster vector"=cluster.dist, "Iteration"=iter))

}


kmeans.result <- kmeans.ch5(iris.data, 3)
plot(iris[-5], pch = kmeans.result$'Cluster vector', col = kmeans.result$'Cluster vector')

위 결과는 생성함수(kmeans.ch5(iris.data, 3)). 아래 결과는 R 내장함수(kmeans(iris.data, 3))

Plot 비교

두 Plot이 거의 흡사함을 보아 잘 코딩되었음을 확인할 수 있었다.
이로써 기본적인 k-means의 설계를 익히고, 응용할 수 있는 능력 습득!

출처:
1. github
2. R을 활용한 기계학습
3. http://blog.daum.net/sys4ppl/7