이 문서 및 군집분석 앱을 작성하는 데에 참조한 문헌들은 다음과 같다.

1. R in action(2nd edition)
2. Practical Data Science with R
3. An introduction to statistical learning
4. clValid, an R package for cluster validation

이 문서에 사용된 R 패키지들은 다음과 같다.

requiredPackages=c("flexclust","NbClust","rattle","cluster","fMultivar","ggplot2")
for(p in requiredPackages){
        if(!require(p,character.only=TRUE)) install.packages(p)
}

웹R에서 만든 cluster analysis 샤이니 앱을 실행하기 위해서는 다음 패키지들이 필요하다.

requiredPackages=c("shiny","d3heatmap","RColorBrewer","DT","fpc","clValid","RankAggreg")
for(p in requiredPackages){
        if(!require(p,character.only=TRUE)) install.packages(p)
}

군집분석

군집분석은 주어진 데이타셋 내에 존재하는 몇 개의 군집을 찾아내는 비지도(unsupervised) 기법이다. 군집(cluster)는 다른 그룹에 속한 다른 관찰치들에 비해 서로 보다 유사한 관찰치들의 그룹이라고 할 수 있는데 그 정의가 정밀하지 않기 때문에 수 많은 군집 방법이 존재하게 된다.

군집분석의 예 : http://shiny.rstudio.com/gallery/kmeans-example.html

군집분석이 유용한 경우

군집분석은 생물학, 행동과학, 마케팅 및 의학분야에서 다양하게 사용된다. 예를 들어 정신과 영역에서는 우울증의 subtype 을 발견하기 위해 우울증 환자의 중상과 인구학적인 특징에 관한 데이타로 군집분석을 할 수 있다. 이를 통해 subtype이 발견된다면 질병에 대한 이해를 넓힐수 있고 보다 효과적인 치료도 가능할 것이다. 마케팅 담당자라면 고객의 인구학적인 특징 및 소비 성향의 유사성에 근거해 몇개의 군집으로 나눔으로써 맞춤형 마케팅을 하는데 활용할 수 있을 것이다. 의학연구자들은 유전체데이타를 이용하여 유사한 표현형 및 공통되는 생물학적 경로를 가지는 유전자와 단백질들을 grouping하는데 군집분석을 사용할 수 있다.

군집분석 방법

  1. Hierarchical agglomerative clustering
  • 모든 관찰치는 자신만의 군집에서 시작하여 유사한 데이타 두 개를 하나의 군집으로 묶는데 이를 모든 데이타가 하나의 군집으로 묶일때까지 반복한다.
  • 사용되는 알고리즘 : single linkage, complete linkage, average linkage, controid, Ward의 방법 등이 있다.
  1. Partitioning clustering
  • 먼저 군집의 갯수 K 를 정한 후 데이타를 무작위로 K개의 군으로 배정한 후 다시 계산하여 군집으로 나눈다.

  • 사용되는 알고리즘 : k-means 및 PAM(partitioning around medoids) 등이 있다.

군집분석 단계

  1. 알맞은 속성 선택(Choose appropriate attributes)

첫번째(이자 아마도 가장 중요한) 단계는 데이타를 군집화하는데 중요하다고 판단되는 속성들을 선택하는 것이다. 예를 들어 우울증에 대한 연구라고 하면 다음과 같은 속성들을 평가할 수 있다. 정신과적 증상, 이학적증상, 발병나이, 우울증의 횟수, 지속기간, 빈도, 입원 횟수, 기능적 상태, 사회력 및 직업력, 현재 나이, 성별, 인종, 사회경제적 상태, 결혼상태, 가족력, 과거 치료에 대한 반응 등. 아무리 복잡하고 철저하게 군집분석을 하더라도 잘못 선택한 속성을 극복할 수 없다.(A sophisticated cluster analysis can’t compaensate for a poor choice of variables.)

  1. 데이타 표준화(Scale the data)

분석에 사용되는 변수들의 범위에 차이가 있는 경우 가장 큰 범위를 갖는 변수가 결과에 가장 큰 영향을 미치게 된다. 이런 결과가 바람직하지 않은 경우 데이타를 표준화 할 수 있다. 가장 많이 사용되는 방법은 각 변수를 평균 0, 표준편차 1로 표준화하는 것이다.

df1 <- apply(mydata, 2, function (x) {(x-mean(x))/sd(x)})

R의 scale() 함수를 사용하면 같은 결과를 얻을 수 있다. 웹R에서도 이 방법을 사용한다. 그 외에 각 변수를 최대값으로 나누는 방법도 있고(df2) 각 값에서 평균을 빼고 median absolute deviation으로 나눌 수도 있다(df3).

df2 <- apply(mydata, 2, function (x) {x/max(x)})
df3 <- apply(mydata, 2, function (x) {(x-mean(x))/mad(x)})
  1. 이상치 선별(Screen for outliers)

많은 군집분석 방법은 이상치에 민감하기 때문에 이상치가 있는 경우 군집분석 결과가 왜곡된다. 단변량 이상치의 경우 outlier 패키지의 함수를 사용할 수 있고 다변량 이상치의 경우 mvoutlier 패키지에 있는 함수들을 사용하여 이상치를 선별하고 제거할 수 있다. 또 다른 방법은 이상치에 대하여 강건한(robust) 군집분석 방법을 쓸 수 있는데 PAM(partitioning around medoids)이 대표적인 방법이다.

  1. 거리의 계산 (Calcuate distance)

두 관찰치 간의 거리를 측정하는 방법은 여러가지가 있는데 “euclidean”, “maximum”, “manhattan”, “canberra”, “binary” 또는 “minkowski” 방법을 사용할 수가 있다. R의 dist()함수를 쓰면 위의 방법들을 이용하여 거리를 계산할 수 있으며 웹R 에서도 이 함수를 사용하여 거리를 계산한다. 디폴트 값은 유클리드 거리(“euclidean”)이다. 유클리드 거리는 다음 절에서 다룬다.

  1. 군집 알고리즘 선택

다음 단계로 군집 방법을 선택하여야 한다. 계층적군집(Hierarchical agglomerative clustering)은 150 관찰치 이하의 적은 데이타에 적합하다. 분할군집은 보다 많은 데이타를 다룰 수 있으나 군집의 갯수를 정해주어야 한다. 계층적 군집/분할 군집을 선택한 후 구체적인 방법을 선택하여야 한다. 각각의 방법은 장단점이 있기 때문에 하나 이상의 방법을 사용해보고 어느 방법이 강건한지 평가해 볼 수 있다.

  1. 하나 이상의 군집분석 결과 얻음

  2. 군집의 갯수 결정

군집분석 최종 결과를 얻기 위해 몇 개의 군집이 있는지 결정해야 한다. NbClust패키지의 NbClust()힘수를 사용할 수 있다. 웹R에서는 clValid패키지를 사용하여 군집 갯수 결정에 도움을 주고자 하였다.

  1. 최종결과 획득

  2. 분석 결과의 시각화

최종 결과를 시각화할 때 계층적 분석은 dendrogram으로 나타내고 분할군집은 이변량 cluster plot으로 시각화한다.

  1. 군집분석 결과의 해석

최종 결과를 얻은 후 그 결과를 해석하고 가능하면 이름도 지어야 한다. 한 군집의 관측치가 갖고 있는 공통점은 무엇인가? 다른 군집과 어떤 점이 다른가? 이 단계는 각 군집의 통계량을 요약함으로써 얻어진다. 연속형 변수의 경우 평균 또는 중앙값을 계산하고 범주형 변수가 있는 경우 범주별로 각 군집의 분포를 보아야 한다.

  1. 결과의 확인(validate the result)

다음과 같은 질문을 가져본다. “이 군집 결과가 실제 존재하는가? 이 데이타셋에서만 또는 이 방법에서만 나타나는 것은 아닌가?” 다른 군집 방법 또는 다른 데이타셋이 사용될 경우 같은 군빕이 얻어질 것인가? 결과의 validation을 위해 fpc, clv 또는 clValid 패키지 등을 사용할 수 있다. 웹R에서는 clValid 패키지를 사용한다.

거리의 계산

유클리드 거리는 다음과 같은 공식으로 계산된다.

\(d_{ij}=\sqrt{\sum^{p}_{p=1}(x_{ip}-x_{jp})^2}\)

여기서 i,j는 관측치이며 P는 변수 번호이다. 에를 들어 nutrient데이타를 살펴보자.

data(nutrient,package="flexclust")
head(nutrient,4)
             energy protein fat calcium iron
BEEF BRAISED    340      20  28       9  2.6
HAMBURGER       245      21  17       9  2.7
BEEF ROAST      420      15  39       7  2.0
BEEF STEAK      375      19  32       9  2.6

첫 두 데이타(beef braised와 hamburger)사이의 유클리드 거리는 다음과 같이 구할 수 있다.

\(d=\sqrt{(340-245)^2+(20-21)^2+(28-17)^2+(9-9)^2+(2.6-2.7)^2}=95.64\)

R의 dist()함수는 데이타프레임 또는 행렬의 모든 행 사이의 거리를 계산하여 행렬 형식으로 결과를 반환헤 준다. 다음과 같이 할 수 있다.

d=dist(nutrient)
as.matrix(d)[1:4,1:4]
             BEEF BRAISED HAMBURGER BEEF ROAST BEEF STEAK
BEEF BRAISED      0.00000   95.6400   80.93429   35.24202
HAMBURGER        95.64000    0.0000  176.49218  130.87784
BEEF ROAST       80.93429  176.4922    0.00000   45.76418
BEEF STEAK       35.24202  130.8778   45.76418    0.00000

관측치 사이의 거리가 크다는 것은 관측치가 유사하지 않다는 것이다. 어떤 관측치와 자신과의 거리는 0이다. beef braised와 hamburger 사이의 거리는 손으로 계산한 값과 같다.

계층적군집 방법

모든 관찰치는 자신만의 군집에서 시작하여 유사한 데이타 두 개를 하나의 군집으로 묶는데 이를 모든 데이타가 하나의 군집으로 묶일때까지 반복한다. 알고리즘은 다음과 같다.

1. 모든 관찰치를 군집으로 정의한다.
2. 모든 군집에 대하여 다른 모든 군집과의 거리를 계산한다.
3. 가장 작은 거리를 갖는 두 군집을 합해 하나의 군집으로 만든다. 따라서 군집의 갯수가 하나 감소한다.
4. 2와3을 반복하여 모든 관찰치가 하나의  군집으로 합쳐질 때까지 반복한다.

2단계에서 군집 사이의 거리를 정의하는 것에 따라 계층적 군집 알고리즘이 달라진다. 가장 많이 쓰이는 다섯가지 방법의 정의는 다음과 같다.

군집방법 두 군집 사이의 거리 정의
single linkage 한 군집의 점과 다른 군집의 점 사이의 가장 짧은 거리(shortest distance)
complete linkage 한 군집의 점과 다른 군집의 점 사이의 가장 긴 거리(longest distance)
average linkage 한 군집의 점과 다른 군집의 점 사이의 평균 거리. UPGMA(unweighted pair group mean averaging)이라고도 한다.
centroid 두 군집의 centroids(변수 평균의 벡터) 사이의 거리.관측치가 하나인 경우 centroid는 변수의 값이 된다
Ward 모든 변수들에 대하여 두 군집의 ANOVA sum of square를 더한 값

single linkage clustering은 긴 시가모양의 군집이 만들어지는 경향이 있으며 이러한 현상을 chaining이라고 한다. chaining은 유사하지 않은 관측치들의 중간 관측치들이 유사하기 때문에 하나의 군집으로 합쳐지는 것를 말한다. complete linkage clustering은 거의 비슷한 직경을 갖는 compact cluster를 만드는 경향이 있으며 이상치에 민감한 것으로 알려져 있다. average linkage clustering은 두 가지 방법의 타협점이다. chaining결향이 덜하고 이상치에도 덜 민감하다. 또한 분산이 적은 군집을 만드는 경향이 있다. Ward의 방법은 적은 관찰치를 갖는 군집을 만드는 경향이 있으며 관찰치의 수와 거의 같은 군집을 만드는 경향이 있다. centroid방법은 단순하고 이해하기 쉬운 거리의 정의를 갖는 매력적인 방법으로 다른 방법들에 비해 이상치에 덜 민감하지만 average linkage나 Ward방법에 비해 수행능력이 떨어진다.

R을 이용해 계층적 분석을 하려면 다음과 같이 한다.

hclust(d, method=)

d는 dist()함수에 의해 만들어지는 거리행렬이고 method로는 “ward.D”, “ward.D2”, “single”, “complete”, “average” (= UPGMA), “mcquitty” (= WPGMA), “median” (= WPGMC) 또는 “centroid” (= UPGMC)를 사용할 수 있다.

R을 이용한 계층적 군집분석

data(nutrient,package="flexclust")
rownames(nutrient)=tolower(rownames(nutrient))
nutrient.scaled=scale(nutrient)

d=dist(nutrient.scaled)
fit.average=hclust(d, method="average")
plot(fit.average,hang=-1,cex=.8,main="Average Linkage Clustering")

몇 개의 군집으로 나누어야 하는가?

library(NbClust)
devAskNewPage(ask=TRUE)
nc=NbClust(nutrient.scaled,distance="euclidean",min.nc=2,max.nc=15,
           method="average")

*** : The Hubert index is a graphical method of determining the number of clusters.
                In the plot of Hubert index, we seek a significant knee that corresponds to a 
                significant increase of the value of the measure i.e the significant peak in Hubert
                index second differences plot.