[R]2. 데이터 클러스터링 k-means 알고리즘

[R]2. 데이터 클러스터링 k-mean 알고리즘 #tdm #tweet 분석 #clustering #k-means #Elbow Method #Elbow Point

[연구 질문]

각 문서들 속에 들어 있는 데이터 분석을 통해 유사하거나 관계가 높은 항목끼리의 집합(클러스터)을 만들고 싶다

[개념]

k-means 클러스터링

   : 분할법, 주어진 데이터를 여러 그룹으로 나눔

     같은 그룹내의 단어들 끼리의 유사도는 증가하고, 다른 그룹에 있는 단서들과는 유사도가 가장 적은 형태로 나눔

     알고리즘은 각 그룹의 중심점과 그 그룹 내의 단어들과의 거리 제곱합이 가장 최소화 되는 방향으로 그룹을 나눈다

    n개의 단어  (x₁, x₂, …, x_n)에서  개의 집합 S = {S₁, S₂, …, S_k}로 분할, μ_i가 집합 S_i의 중심점일때 각 중심점으로

    부터 각 집합의 단어까지의 거리의 제곱합을 최소로하는 집합 S를 찾는 것이 목표

    근사 최적해를 찾는 것이므로 각 중심점을 랜덤으로 찍는 만큼 계속해서 각 그룹이 달라질 수 있다

적절한 k는?

Rule of thumb

 데이터 수가 N개일때 필요한 클러스터의 수는 

Elbow Method

 클러스트의 수를 순차적으로 늘려가면서 결과 모니터링 

 Within group 그래프에서 기울기가 완만해지는 곳을 Elbow Point라 하며 이때의 K가 적정값이라 판단

 

k-means 한계점

• k 값을 입력 파라미터로 지정해줘야 함

• 지역 최소값에 수렴할 가능성이 있음 - 이를 방지하기 위해 담금질 기법 (Simulated Annealing) 을 수행하여 의도적으로 에러가 줄어드는 방향을 피하는 방식을 이용

• 이상값(outlier)에 민감함

• 구형(spherical)이 아닌 클러스터를 찾는 데 적절하지 않음

[필요 패키지]

[코드] *파란색은 스크립트, 검정색은 결과값입니다

#대표적인 테스트데이터인 iris을 읽어옴

data("iris")

#iris데이터와 나중에 비교하기위해 새로운 변수 niris에 복사

niris<-iris

#제대로 clustering하는지 확인하기 위해 종 분류는 우선 삭제하자

niris$Species<-NULL

#k는 3개의 종을 구별해내길 기대하며 3으로 설정. 아래에 적정 k를 찾는 부분 추가

kc<-kmeans(niris,3)

kc

K-means clustering with 3 clusters of sizes 62, 38, 50

Cluster means:

  Sepal.Length Sepal.Width Petal.Length Petal.Width

1     5.901613     2.748387     4.393548    1.433871

2     6.850000    3.073684     5.742105    2.071053

3     5.006000    3.428000     1.462000    0.246000

Clustering vector:

  [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

 [27] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1

 [53] 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

 [79] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2

[105] 2 2 1 2 2 2 2 2 2 1 1 2 2 2 2 1 2 1 2 1 2 2 1 1 2 2

[131] 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 1

Within cluster sum of squares by cluster:

[1] 39.82097 23.87947 15.15100

 (between_SS / total_SS =  88.4 %)

Available components:

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

[4] "withinss"     "tot.withinss" "betweenss"   

[7] "size"         "iter"         "ifault"

# iris데이터의 종과 구별해낸 cluster를 비교해 얼마나 맞았는지 파악

table(iris$Species,kc$cluster)

                  1  2  3

  setosa      0  0 50

  versicolor 48  2  0

  virginica   14 36  0

#클러스터별 색깔로 Sepal.Length와 Sepal.Width만 표시

plot(niris[c("Sepal.Length","Sepal.Width")], col=kc$cluster)

#각 클러스터의 중심점 그리기

points(kc$centers[,c("Sepal.Length","Sepal.Width")],col=1:3,pch=8,cex=2)

#Elbow Method

wss <- 0

#k를 1~15까지 변화시키면서 각 withinss 값을 wss에 저장

for(i in 1:15) wss[i]<-sum(kmeans(niris,centers = i)$withinss)

#withinss값을 그래프로 그리기, 기울기가 완만해지는 3~4가 Elbow point라는 것을 알수 있다

plot(1:15, wss, type="b",xlab = "Number of Clusters", ylab = "Within group sum of squares")

안되는 부분이나 궁금한 점이 있으면 댓글 달아주세요 :)

 

출처: https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

추가: Spark에서의 KMeans