[R] k-means 알고리즘

k means 알고리즘은 k 개의 평균(means) 벡터를 이용한 클러스터링(군집화) 알고리즘이다. 데이터들의 분산을 최소화하는 k개의 평균 벡터를 구한다. 

k means 알고리즘은 다음과 같다

1. (처음 중심 값 선택) 랜덤하게 초기 중심 값(centroid)을 선택한다.

2. (클러스터 할당) k 개의 중심 값과 각 개별 데이터간의 거리(distance)를 측정한다. 가장 가까운 클러스터에 해당 데이터를 할당(assign)한다.

3. (새 중심 값 선택) 클러스터마다 새로운 중심 값을 계산한다.

4. (범위 확인-convergence) 선택된 중심 값이 변화가 어느 정도 없다면 멈춘다. 만약 계속 변화가 있다면 1 번부터 반복한다.

그림으로 이해할 수 있는 알고리즘으로서,

 http://ai-times.tistory.com/158에 올려놓은 PPT를 참조하면 다음과 같다. (이해가 가장 쉬운 그림이었다.)

* 랜덤하게 중심 값(centroid) 잡기

* 만약 특이한 데이터(noise)가 끼면, k means 알고리즘(k=2)은 아래와 같이 진행한다.

http://stanford.edu/~cpiech/cs221/handouts/kmeans.html 에 보면 고급 알고리즘이다.

R은 kmeans() 함수를 제공한다. 다음은 이해할 수 있는 쉬운 예제이다. 

> c <- c(3, 4, 1, 5, 7, 9, 5, 4, 6, 8)

> row <- c("A", "B", "C", "D", "E")

> col <- c("X", "Y")

> data <- matrix(c, nrow=5, ncol=2, byrow=TRUE, dimnames=list(row, col))

> data

  X Y

A 3 4

B 1 5

C 7 9

D 5 4

E 6 8

> plot(data)

> 

> 

> km <- kmeans(data, 2, 15)

> km

K-means clustering with 2 clusters of sizes 3, 2

Cluster means:

    X        Y

1 3.0 4.333333

2 6.5 8.500000

Clustering vector:

A B C D E 

1 1 2 1 2 

Within cluster sum of squares by cluster:

[1] 8.666667 1.000000

 (between_SS / total_SS =  78.6 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"    

[5] "tot.withinss" "betweenss"    "size"         "iter"        

[9] "ifault"      

> km$cluster

A B C D E 

1 1 2 1 2 

> km$centers

    X        Y

1 3.0 4.333333

2 6.5 8.500000

> 

> 

> plot(data, col = km$cluster)

 

> points(km$centers, col = 1:2, pch = 9)

데이터가 많으면, kmeans 함수는 데이터가 많아서 잘 안맞는 경우가 있다고 한다. ykmeans 함수를 추천한다고 한다.

https://cran.r-project.org/web/packages/ykmeans/index.html