군집 분석

통계학 Statistics
{{{#!wiki style="margin:0 -10px -5px; min-height:calc(1.5em + 5px); word-break: keep-all" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-5px -1px -11px"	<colbgcolor=#4d4d4d><colcolor=#fff> 수리통계학	기반	실해석학 ( 측도론) · 선형대수학 · 이산수학
확률론		사건 · 가능성 · 확률 변수 · 확률 분포 ( 표본 분포 · 정규 분포 · 이항 분포 · 푸아송 분포 · 카이제곱분포 · t분포 · Z분포 · F-분포 · 결합확률분포) · 확률밀도함수 · 확률질량함수 · 조건부확률 · 조건부기댓값 · 조건부분산 · 전체 확률의 법칙 · 베이즈 정리 · 도박사의 오류 · 도박꾼의 파산 · 몬티 홀 문제 · 뷔퐁의 바늘 · 마르코프 부등식 · 체비쇼프 부등식 · 큰 수의 법칙 ( 무한 원숭이 정리) · 중심극한정리 · 벤포드의 법칙
통계량		평균 ( 산술 평균 · 기하 평균 · 조화 평균 · 멱평균 · 대수 평균) · 기댓값 · 편차 ( 절대 편차 · 표준 편차) · 분산 ( 공분산) · 결정계수 · 변동계수 · 상관계수 · 대푯값 · 자유도
추론통계학	가설 · 변인 · 추정량 · 점추정 · 신뢰 구간 · 상관관계와 인과관계 · 실험통계학 · p-해킹 · 통계의 함정 · 그레인저 인과관계 · 신뢰도와 타당도
추론통계학	통계적 방법	회귀 분석 · 최소제곱법 · 분산 분석 · 주성분 분석 ( 요인 분석) · 시계열 분석 · 패널 분석 · 2SLS · 생존 분석 · GARCH · 비모수통계학 · 준모수통계학 · 기계학습 ( 군집 분석 · 분류 분석) · 위상 데이터분석 · 외삽법 · 메타 분석 · 모델링 ( 구조방정식)
기술통계학 · 자료 시각화		도표 ( 그림그래프 · 막대그래프 · 선 그래프 · 원 그래프 · 상자 수염 그림 · 줄기와 잎 그림 · 산포도 · 산점도 · 히스토그램 · 도수분포표) · 그래프 왜곡 · 이상점	}}}}}}}}}

1. 소개2. 상세3. 종류

3.1. 계층적 군집화3.2. 분할적 군집화

3.2.1. 중심점 기반: K-평균 군집화3.2.2. 밀도 기반: DBSCAN3.2.3. 확률 기반: 퍼지군집화3.2.4. 분포 기반: 기댓값 최대화 알고리즘3.2.5. 그래프 기반: 자기조직화지도

4. 같이 보기

1. 소개

群集分析
cluster analysis

기계학습 분야에서 활용되는 통계분석방법 중 하나로, 통계학의 관점에서는 다변량분석(multi-variate analysis)의 한 종류이다. 군집 분석은 각 데이터의 유사성을 측정하여 다수의 군집으로 나누고 군집 간의 상이성을 확인하는 분석이며, 주어진 자료에 대한 요약정리 혹은 이해를 목적으로 실시한다는 점에서는 기술통계학적인 면모도 갖고 있다. 아이디어 자체는 이미 80년대 논문에서도 등장할 정도로 오래되었으나, 인공지능 및 기계학습의 발전과 함께 급격히 체계화되었다.

2. 상세

군집 분석은 비지도학습(unsupervised learning)의 대표주자이다. 다시 말해, 분석가는 데이터 속에 다수의 군집이 존재한다고 믿고자 하나, 구체적으로 그 군집의 개수나 구조가 어떻게 될지는 아무것도 알지 못하는 상태에서 분석을 시도한다. 비지도학습이 다 그렇듯, 군집의 수는 분석을 시행하는 기계가 맨땅에 헤딩 하듯이 정하게 되며, 이 과정에서 인간의 지도(supervision)가 일체 개입하지 않는다. 단지 군집의 수를 정하는 기준만을 정할 수 있을 뿐이다. 이러한 특성은 기계학습 분야에서 비지도학습에 대응되는 개념인 지도학습(supervised learning)과는 극명하게 대조된다.

물론 막상 뚜껑을 열어 봤더니 군집이 단 하나밖에 나오지 않는 완전한 무작위적 패턴으로 나올 수도 있다. 반면 경우에 따라서는 위에 첨부된 그림처럼 거의 완벽하게 구분되는 몇 개의 군집이 튀어나오기도 한다. 이 경우를 잘 분리된 군집화(well-separated clustering)라고 하며, 이때 군집 내의 어떠한 데이터 쌍이라도 서로간의 거리는 군집 간의 어떠한 데이터 쌍의 거리보다 더 가깝다. 하지만 현실은 대개 이렇게까지 깔끔하지는 못하며, 많은 데이터들은 잘 분리되지 못한 군집화를 보이게 마련이다.

잘 분리되지 못한 군집화에서의 군집의 선정 기준은 매우 다양하며, 딱히 우월한 정답이 없다. 각 군집의 중심(center)을 기준으로 군집화를 할 수도 있고 이게 가장 기초적이면서도 보편적이지만, 근접성(contiguity), 밀도(density), 공유된 특성(shared-property)을 바탕으로 군집을 만들 수도 있다. 현대에는 공유된 최근접이웃(S-NN; shared nearest-neighbor)처럼 새로운 접근을 찾으려는 시도도 이루어지는 중이다. 이 중에서 분석가는 자신의 문제의식과 데이터에 가장 잘 맞는다고 생각되는 군집 분석을 수행하게 된다.

다른 접근법으로는 데이터를 하나의 군집에 꼭 대응시키지 않을 수도 있다. 종래의 가장 흔한 접근법은 하나의 데이터를 무조건 하나의 군집에만 소속시키는 배타적 군집화(exclusive clustering)였는데, 경우에 따라서는 하나의 데이터를 여러 군집들에 복수로 소속시키는 중첩적 군집화(overlapping clustering)도 가능하겠다는 관점도 있다. 심지어는 하술되겠지만 아예 어떤 데이터가 어떤 군집에 소속되는 여부를 확률로 표현하는 확률기반 군집화, 일명 퍼지군집화(fuzzy clustering)라는 것도 나와 있다.

또한 데이터 세트에 따라서는 모든 데이터를 무조건 군집에 대응시킬 필요가 없을 수도 있다. 즉 모든 데이터가 어떤 군집에 소속되어 있는 완전한 군집화가 일반적이기는 해도, 필요하다면 부분적 군집화만 완료하고 나머지는 배경(background)으로 남겨두는 것도 가능하다. 배경에 남겨진 데이터들은 어떠한 군집에도 소속될 수 없다고 보자는 것이다. 특히 이상점(outlier)을 이런 식으로 처리할 수도 있는데, 군집 분석은 대개 이상점의 영향을 심하게 받기 때문에 이런 튀는 데이터들을 군집에서 열외시켜 군집화를 보정하는 것이다.

이와 같이 군집화라는 것도 뜻밖의 애매한 결과들을 도출하는 경우가 많아, 분석가는 처음부터 과연 이 데이터 세트가 애초부터 군집화를 필요로 하는가를 고민할 필요가 있다. 그래서 엄격하게 수행되는 군집 분석은 반드시 사전에 분석의 필요성을 평가하는 단계를 거치는데, 이때 쓰이는 기준이 바로 홉킨스 통계량(Hopkins statistic)이다. 홉킨스 통계량은 0에서 1 사이의 숫자로 나타나며, 0일 경우에는 완전한 무패턴의 산포를 의미하지만, 1일 경우에는 이상적인 수준으로 잘 분리된 군집화가 가능함을 의미한다.

군집 분석의 사전에 사용되는 평가지표가 홉킨스 통계량이라면, 군집 분석을 수행한 사후에 사용되는 평가지표도 생각할 수 있을 것이다. 이때 활용되는 것이 바로 실루엣분석(silhouette analysis)이다. 실루엣분석은 군집 분석을 한 결과의 성능을 평가하는 대표적인 지표라고 할 수 있다. 모든 각각의 데이터에는 실루엣계수(silhouette coefficient)가 도출될 수 있으며, 이는 －1에서 1 사이의 값으로 나타난다. 그리고 데이터의 수만큼 얻어진 실루엣계수들을 모두 평균한 후, 그 숫자가 얼마나 1에 가깝게 큰지를 살펴보게 된다. 단, 군집별로 실루엣계수 평균값의 편차가 작아야 한다는 점은 주의.

실루엣계수 값은 많은 경우 0에서 1 사이로 나타난다. 1에 가까울수록 그 데이터는 제대로 된 군집에 할당되었다는 의미이고, 0에 가까울수록 그 데이터의 위치가 애매함을 암시한다. 반대로 음수 값이 나왔다면 이는 정말로 엉뚱한 군집에 오할당됐다는 의미다. 실루엣계수는 그 논리 상 응집도(cohesion)와 분리도(separation)를 활용하여 계산되며, 여기서 응집도는 같은 군집에 속한 다른 데이터들과의 평균거리로서 군집 내 데이터들의 연결에 대한 가중치의 합을 의미하고, 분리도는 다른 군집에 속한 다른 데이터들과의 평균거리로서 군집 간 데이터들의 연결에 대한 가중치의 합을 의미한다.

군집 분석과 관련하여 잘 알려진 R 함수들로는 대개 agnes(　), kmeans(　), hclust(　) 등이 있다.

3. 종류

3.1. 계층적 군집화

hierarchical clustering

계층적 군집화는 하나의 군집이 다른 하위 군집들을 갖도록 군집을 만드는 방법으로, 내포형(nested) 군집화, 연속적 분할 군집화라고도 한다. 이 경우 군집은 데이터들을 합쳐가는 방법 혹은 나눠가는 방법으로 만들게 되며, 합칠지 말지 혹은 나눌지 말지를 결정하는 것은 군집 간의 연결(linkage)을 기준으로 판단하게 된다. 이 때문에 계층적 군집화는 분석하는 데 들어가는 컴퓨팅 비용이 높다고 알려져 있다. 계층적 군집화에는 데이터들을 합쳐가며 군집화하는 합병형 군집화(agglomerative clustering), 데이터들을 나누어가며 군집화하는 분리형 군집화(divisive clustering)가 대표적이며, 흔히 다이애나(DIANA)라고 불리는 하향식 군집화(top-down clustering)도 자주 꼽힌다.

그 중에서 기초 수준에서 소개할 만한 것이 있다면 합병형 군집화라고 할 수 있다. 이것은 데이터 세트에서 단일원소 군집(singleton cluster)들을 먼저 생성하고, 인접행렬을 통해서 데이터 간의 거리를 측정하여, 가장 가까이 있는 군집들을 서로 합병해 나가는 과정을 반복하는 방법이다. 이를 끝없이 반복하다 보면 마침내 모든 데이터를 포함하는 단 하나의 군집만 남게 되는데, 그 이전에 적절한 시점에서 합병을 종료하고 몇 개의 군집들로 정리하게 된다. 시점을 좀 더 이르게 한다면 군집의 수는 많아질 것이고, 시점을 좀 더 늦춘다면 군집의 수는 감소할 것이다. 따라서 합병형 군집화는 근접성 기반 군집화라고도 볼 수 있다.

전체 과정의 진행상황은 내포 다이어그램(nested diagram)을 활용하거나, 계통수(系統樹) 혹은 그대로 음역한 덴드로그램(dendrogram)이라는 특수한 그림을 통해서 파악하게 된다. 덴드로그램은 인접행렬을 기준으로 군집들이 묶이는 과정을 아래에서 위 방향으로 도해하는 그림인데, 아래쪽의 작은 '나뭇가지' 들은 각각의 데이터에 대응되고, 이것들이 위로 올라갈수록 서로 묶이고 합쳐지면서 마침내는 맨 위 꼭대기에서 단 하나의 큰 가지로 서로 만나게 된다. 분석가는 위쪽의 적당한 높이에서 덴드로그램을 자르게 되는데, 이때 잘리는 '나뭇가지' 의 갯수가 바로 군집의 수가 되는 것.

덴드로그램을 그리는 기준이 되는 정보인 인접행렬은 각 데이터들 사이의 거리를 측정함으로써 도출된다. 여기서 문제는 어떤 식으로 측정할 것인가이다. 우리가 일반적으로 생각하는 '거리' 개념을 그대로 가져온다면, 이는 공간 위를 최단거리로 질러가는 거리라고 할 수 있다. 이를 유클리디안 거리(L2)라고 한다. 반면 바둑판처럼 모든 데이터가 격자 위에 놓여있을 때, 거리는 격자 위를 가로세로로 따라가면서 찾아질 수도 있다. 마치 자동차 내비게이션을 연상케 하는 이 거리는 맨하탄 거리(L1)라고 불린다. L1과 L2를 동시에 표현하는 민코스키(Minkowski) 거리도 있고, 격자 위에서 대각선 이동을 허용하는 체비셰프(Chevyshev) 거리, 데이터의 산포 정도를 고려하여 거리를 통계적으로 표준화한 마할라노비스(Mahalanobis) 거리,[1] 그리고 이 모든 것을 골고루 반영한 브레그만(Bregman) 발산도 존재한다.

이상의 거리 측정법들은 데이터가 연속형(continuous) 또는 이산형(discrete)인 성질일 때 사용 가능하며, 만일 데이터가 범주형(categorical)인 성질이라면 다른 방식으로 거리를 측정해야 한다. 그 중에서도 가장 유명한 자카드 지수(Jaccard index) 계산법은 고전적 논리연산을 빌려온 것으로, 두 범주 사이의 합집합이 아닌 원소는 무시하고 합집합과 교집합에 해당하는 원소만 활용해서 0~1 사이의 계수값을 도출한다. 숫자가 클수록 두 범주는 서로 유사한 집합이라고 볼 수 있다. 또한 코사인 유사도(cosine similarity)는 단위벡터의 내각의 크기를 측정하여 계산하지만, R 함수에서 지원되지 않다 보니 상대적으로 잘 쓰이지는 않는다. 요지는 측정 문서에서도 나오듯이 무언가를 측정하는 전략은 매우 다양하다는 것이고, 자신의 분석 데이터에 가장 적합한 측정방법을 찾아야 한다는 것이다.

아무튼 이렇게 측정된 거리들을 바탕으로 인접행렬을 만들었다면, 이제 이를 바탕으로 데이터들을 군집으로 합병할 차례이다. 합병형 군집화에서 분석가는 가장 가까운 군집끼리 묶으면서 군집의 수를 줄이는 동안 각 단계의 인접행렬을 매번 새로 계산하게 되며, 이를 통해 만들어지는 덴드로그램의 도해를 보고 군집의 수를 최종 결정하게 된다. 유의해야 할 것은, 매 단계에서 거리계산법과 인접 데이터 연결법은 계속해서 동일하게 유지해야 한다는 것이다. 데이터를 연결하는 방법은 다음과 같은 것들이 있다.

단일연결법(single linkage): MIN이라고도 한다. 군집 간 거리를 계산할 때 최단거리를 기준으로 데이터가 최대의 유사성을 보이게 한다. 이 방법은 가장 직관적이지만 노이즈와 이상점에 취약하다는 문제가 있다.
완전연결법(complete linkage): MAX 또는 클리크(clique)라고도 한다. 단일연결법과는 정반대로, 최장거리를 기준으로 데이터가 최소의 유사성을 보이게 한다. 이런 식으로 연결할 경우 대형 군집이 형성되기 힘들다는 문제가 있다.
평균연결법(average linkage): 군집 간 거리를 계산할 때 평균을 활용해서 계산하며, 결과는 단일연결법과 완전연결법의 중간 정도에서 나타난다. 언뜻 절충적인 방법처럼 보이지만 평균을 쓰기 때문에 이상점에 가장 취약한 방법이다.
Ward의 연결법(Ward's linkage): 통계학적인 논리를 가져온 방법으로, 병합 이후 군집의 오차제곱합(SSE; sum of squared error)이 병합 이전 군집의 SSE에 비해서 더 작아질 경우에만 군집을 병합하는 방법이다. 그러나 이 방법으로도 이상점에는 대응하기 힘들다는 한계가 있다.

현대에는 합병형 군집화도 단순한 논리에 그치지 않고 점점 심화된 방식을 따르고 있다. 전공자들도 학부 수준에서는 간략하게 이름만 듣고 넘어가는 고급의 알고리즘들이 지금 이 순간에도 쏟아져나오고 있고, 여기에는 합병형 군집화도 예외는 아니다. 대표적으로 최소신장나무(MST; minimal spanning tree), 희소화(sparcification), 카멜레온 알고리즘, 라플라시안 행렬에 기반한 스펙트럼 군집화, S-NN 유사도 군집화, 자비스-패트릭(J-P) 알고리즘 등이 꼽히지만, 너무 깊은 내용들이므로 여기서는 다루지 않기로 한다.

3.2. 분할적 군집화

partitional clustering

분할적 군집화는 서로 계층적 관계가 없는 다수의 군집들을 만드는 방법으로, 비내포형 군집화(non-nested clustering)라고도 한다. 즉 데이터가 공간 위에 흩뿌려져 있을 때 여러 군집들이 공간을 땅따먹기로 나누어 갖게 만든다는 것으로, 위의 계층적 군집화처럼 매번 데이터들의 거리를 계산하면서 서로 합병하거나 나누는 식으로는 접근하지 않는다. 계층적 군집화에서 합병형 군집화가 대표적이라면, 분할적 군집화에서는 중심점 기반 군집화(center-based clustering), 밀도 기반 군집화(density-based clustering), 확률 기반 군집화(probability-based clustering), 분포 기반 군집화(distribution-based clustering), 그리고 그래프 기반 군집화(graph-based clustering)를 소개할 필요가 있다.

3.2.1. 중심점 기반: K-평균 군집화

중심점 기반 군집화는 가장 직관적인 형태의 분할적 군집화이며, 전형(prototype) 기반 군집화라고도 한다. 여기서의 논리는 모든 데이터는 타 군집의 중심점보다 자신이 속한 군집의 중심점에 더 가까이 위치해야 한다는 것이다. 군집화의 시각적 결과는 자연스럽게 원형에 가까워지며, 데이터가 실제로 원형일 때 가장 강력한 군집화 방법이다. 상단 그림에서도 각 군집마다 중앙부에 중심점이 위치해 있는 것을 볼 수 있으며, 군집이 원형을 이루고 있음을 볼 수 있다.

중심점 기반 군집화의 가장 대표적이고 빈번히 활용되는 사례는 바로 K-평균 군집화(K-means clustering)이다.[2] 여기서는 임의의 초기값의 개수와 위치를 분석가가 지정한 뒤, 군집을 나눌 수 있는 모든 가능한 방법을 점검한 이후 최적의 군집을 도출한다. 은근 중요한 것으로, 최초 초기값의 위치를 분석가가 어떻게 지정하는가에 따라서 최종적인 군집화의 결과가 달라질 가능성이 있다. 예컨대 중심점의 초기값을 3개로 하여 3개 군집을 만들었는데, 막상 분석해 보니 하필 2개 군집 사이의 중간에 1개의 중심점이 놓이고 1개 군집에 2개 중심점이 모여드는 사태가 벌어지기도 한다.

K-평균 군집화는 한번 군집이 형성되더라도 중심점의 위치가 재조정되면 이미 군집에 소속되었던 데이터들이 다른 군집으로 소속을 바꾸는 일이 벌어질 수 있다. 알고리즘이 계속해서 군집화를 반복하는 동안에 이런 일들이 빈번히 발생하곤 하는데, 이를 활용해서 알고리즘의 종료 조건을 지정하기도 한다. 예컨대 전체 중 1% 미만의 데이터가 소속 군집이 변경될 때 알고리즘을 종료하는 식. 그러나 보다 일반적인 절차는 다음과 같이 이루어진다.

1. 원하는 군집의 개수(k)와 중심점의 초기값(seed)을 입력하고, 군집을 잡아 줄 가장 가까운 초기값으로 모든 데이터를 연결시킨다.
2. 형성된 최초 군집 내에서 중심점의 위치를 재계산하고, 새로 갱신된 위치의 초기값에 대해서 다시 모든 데이터를 연결시킨다.
3. 이 과정을 반복하여 중심점이 사전에 합의된 기준 이하로 거의 바뀌지 않을 때 알고리즘을 정지한다.

K-평균 군집화는 데이터 마이닝의 세계에 처음으로 입문한 초보 분석가들도 이해하기 쉬울 만큼 직관적이고, 대중적으로도 무척 흔하게 접할 수 있는 분석방법에 속한다. 언론계에서는 천관율 전 기자가 대한민국의 젠더 분쟁에 말을 얹기 위해 K-평균 군집 분석을 동원해서 페미니즘의 편을 들었다가 방법론이 잘못됐다는 지적을 받은 적도 있다. 이는 그만큼 K-평균 군집화가 단순 신속하고 범용적인 알고리즘이며 데이터에 대한 사전정보가 불필요하고 대용량 데이터에도 적용이 쉬운, 쓰기 편한 논리라는 것을 보여준다.

그러나 K-평균 군집화에도 물론 한계점이 존재한다. 우선, 측정한 변인의 척도(scale)에 영향을 받기 때문에 분석을 수행하기 전에 미리 정규화(normalization)의 과정을 거쳐야 한다. MinMax 군집화는 이 경우 활용되는 대안적인 방법으로, 원천데이터의 분포형태가 보존될 수 있다. 또한 K-평균 군집화는 군집의 형태나 밀도에 유연하게 대응하기 어렵다. 모든 군집이 원형이라는 법은 없으며 많은 경우 'ㄴ' 형태나 'ㅡ' 형태로도 나타나곤 하는데 K-평균 군집화는 이걸 이해하기 힘들어하고, 크고 밀도 낮은 군집에는 여러 중심점들이 모이는 반면에 작고 밀도 높은 여러 군집들은 하나의 중심점이 독차지하는 경우가 많다. 심지어 텅 빈 군집이 튀어나와 분석가를 당황시키기도 한다.

또한 이상점이나 노이즈에 취약하다는 것도 K-평균 군집화의 한계로 꼽힌다. 이 경우에는 우회적으로 평균이 아니라 중앙값(median) 또는 중앙자(medoid)로 대체할 수 있으며, 이를 위해 중앙자 주변 분할(PAM; partitioning around medoids) 함수를 사용하기도 하지만, 이런 경우 컴퓨팅 비용이 크게 증가함이 알려져 있다. 그보다 더 최신의 기법으로는 K-평균++(K-means++) 기법도 있다. 아니면 아예 이상점 자체를 그냥 방치하고, 오히려 이상점의 탐지를 분석목적으로 쓰기도 한다. 군집 분석뿐만 아니라, 금융업계나 정보보안업계 등에서 막연히 빅데이터를 쓴다고 하면 대개 이런 목적일 때가 많다.

마지막으로 중요한 한계점이 있는데, K-평균 군집화는 지도학습 분야의 의사결정나무(decision tree)와 함께 데이터 마이닝 업계에서 탐욕적 알고리즘(greedy algorithm)으로 유명한 기법이다. 탐욕적(greedy)이라는 표현을 달리 비유하자면 나무만 보고 숲은 못 본다고도 할 수 있는데, 이것은 매 단계마다 알고리즘이 그때그때 눈앞의 최적의 선택만을 반복하기 때문에 근사적이고 실용적인 수준에서만 최적의 결과가 나온다는 의미다. 군집화의 형성기준이 당장의 SSE의 최소화에만 맞춰져 있다 보니, 안정적이기는 한데 최선은 아니라는 것. 달리 설명하면, 국지적(local)인 최적해만 반복적으로 산출한다고 해서 꼭 전역적(global)인 수준의 최적해가 산출된다는 보장이 없다는 얘기가 된다.

3.2.2. 밀도 기반: DBSCAN

밀도 기반 군집화는 군집을 '높은 밀도를 가진 데이터들의 공간' 으로 정의한다. 즉, 서로 근접하거나 연결되어 있는 패턴이라 할지라도 밀도가 낮다면 군집으로 인식하지 않고 무시한다. DBSCAN은 밀도 기반 군집화 중에서도 가장 대표적인 사례라고 할 수 있다. 여기서는 데이터를 중심으로 하는 원을 그리게 되는데, 엡스(Eps)로 불리는 임의로 정의된 반지름 내에 다른 데이터가 몇 개나 들어오는지 확인한다. 엡스의 길이는 분석가가 사전에 결정할 수 있으며, 엡스가 길거나 짧음에 따라서 군집의 수가 달라지게 된다.

DBSCAN에서 데이터는 세 종류 중 하나로 분류된다. 먼저 군집의 내부에 위치하는 핵심점(core point)이 있다. 그리고 이런 핵심점을 엡스 내부에 포함하지만 군집의 바깥쪽 경계에 위치하는 경계점(border point)이 있다. 마지막으로 엡스 내부에 아무런 핵심점이 없어 군집 밖에 위치하는 잡음점(noise point)이 있다. 여기서 분석가는 잡음점으로 분류된 데이터들을 먼저 제쳐놓고 핵심점들을 서로 이어준 후, 경계점들을 핵심점에 소속되게 함으로써 군집을 형성하게 된다.

DBSCAN을 통해 만들어진 군집을 보면 각종 기상천외한 모양의 군집이라도 정확하게 잡아내는 모습을 보여준다. 위에서 소개한 K-평균 군집화와는 달리, DBSCAN은 'ㄴ' 형태나 심지어는 'ㄹ' 형태의 군집이라 할지라도 그걸 고스란히 찾아내서 군집으로 묶어준다. 중심점이 아닌 공간 내 밀도의 관점에서 군집을 이해하기 때문에 발생하는 차이라고 할 수 있다. 그래서 DBSCAN은 군집들이 불규칙하거나, 얽혀 있거나, 원형이 아니거나, 노이즈가 심하거나, 이상점이 많은 경우에 대응하기 효과적인 방법이다. 반면 군집 간의 밀도 차이가 있을 때 사용하기 힘들다는 것은 문제.

K-평균 군집화와 DBSCAN을 비교하자면 다음과 같다.

DBSCAN	K-평균 군집화
밀도 기반 군집화	중심점 기반 군집화
일부 데이터는 노이즈로 판정하여 제거	모든 데이터의 완전한 군집화
군집의 밀도가 의미가 있을 때 효과적	군집의 중심점 위치가 의미가 있을 때 효과적
군집의 크기와 모양에 쉽게 대응	동일크기의 원형 군집들에만 적용 가능
저차원 데이터에만 적용 가능	고차원 데이터에도 적용 가능
데이터분포의 기본 가정 없음	모든 군집이 동일한 공분산행렬을 가진 정규분포를 따른다고 가정
겹치는 군집은 하나로 취급	겹치는 군집에 다수의 중심점 위치 가능
엡스의 길이를 분석가가 지정	군집의 개수를 분석가가 지정
SSE 최소화가 목적이 아님	SSE 최소화를 위한 통계적 최적해 문제의 성격

밀도 기반 군집화는 DBSCAN 이후로도 계속해서 발전해 왔으며, 현대적인 대안으로는 격자 셀(grid cell) 기반 군집화, CLIQUE 알고리즘, 커널 기반 DENCLUE 알고리즘, S-NN 밀도 기반 군집화 등이 있다. 물론 너무 전문적이고 어려운 내용이기 때문에 이들에 대해서도 자세한 내용은 여기서 소개하지는 않는다.

3.2.3. 확률 기반: 퍼지군집화

퍼지군집화로 대표되는 확률 기반 군집화는 군집을 전혀 다른 관점에서 이해한다. 여기서는 각 데이터가 특정 군집에 속할 확률을 각각 계산하면서 군집을 만들어나간다. 이런 방식은 수학적으로는 퍼지 이론에 기원하고 있으며, 잘 분리되지 못한 군집들이 다수 중첩되어 있는 골치 아픈 데이터 세트에 가장 적합하다고 여겨지고 있다. 여기서 각 군집들의 경계는 어렴풋하게(fuzzy) 존재하게 되는데, 경계면에 속한 데이터가 이 군집 혹은 저 군집에 속한다는 경성(hard)의 관점이 아니라 이 군집에 속할 확률 얼마, 저 군집에 속할 확률 얼마라는 연성(soft)의 관점으로 이해하기 때문이다. 그래서 퍼지군집화는 연성군집화(soft clustering)의 한 종류이기도 하다.

이와 같은 접근방식을 퍼지집합(fuzzy set)이라고 하는데, 어떤 원소가 어떤 집합에 속할 여부를 종래의 0 또는 1로 제한하지 않고 0에서 1 사이에 속하는 확률로 보여주자는 것이다. 퍼지집합을 설명할 때 흔히 드는 비유가 바로 날씨인데, 예컨대 현재의 하늘 상태가 '흐린 날' 집합 또는 '맑은 날' 집합 중 어느 쪽에 속하는지는 칼로 무 자르듯 명확하게 말할 수 없다. 이럴 경우에는 차라리 '흐린 날' 집합에 속할 확률이 얼마, '맑은 날' 집합에 속할 확률이 얼마 같은 식으로 설명하는 편이 더 낫다는 것이다. 퍼지군집화는 이와 같은 퍼지집합의 논리를 군집 분석에 가져온 것이다.

그 가장 대표적인 군집화 방법은 바로 퍼지 C-평균 군집화(FCM; fuzzy C-means clustering)이다. 여기서는 퍼지 유사분할(fuzzy pseudo-partition)이라는 기법을 활용하여 퍼지군집을 형성하는데, 알고리즘을 지속하면서 중심점이 계속해서 갱신되게 하는 확률적 방법이다. 이상의 절차는 SSE를 최소화한다는 점, 데이터와 중심점의 거리를 반복계산한다는 점, 군집의 수를 분석가가 사전 지정한다는 점 등등으로 K-평균 군집화와 매우 유사해 보일 수 있는데, 실제로 퍼지군집화의 관점에서는 오히려 K-평균 군집화는 퍼지군집화의 특수한 사례에 해당한다고 이해할 수 있다.

3.2.4. 분포 기반: 기댓값 최대화 알고리즘

분포 기반 군집화는 혼합분포군집화(mixture distribution clustering) 또는 가우시안 혼합 모형(GMM; Gaussian mixture model)이라고도 불린다. 여기서는 데이터 세트가 k개의 모집단 모형으로부터 얻어졌다고 간주, 그 모수(parameter)와 함께 가중치로서의 최대우도추정량(MLE; maximum likelihood estimator)을 자료로부터 추정한다. 그리고 군집의 분류기준은 각 데이터가 k개의 모집단 모형 중 어느 쪽으로부터 나왔을 확률이 높은지를 바탕으로 판단한다. 예컨대 데이터 세트가 3봉분포의 형태라면 이는 3개 군집의 정규분포가 결합되었다고 간주하는 식이다. 그래서 여기서도 상당히 연성적인 접근이라고 할 수 있다.

이때 쓰이는 알고리즘이 바로 기댓값 최대화(EM; expectation maximization)이다. 이것은 조건부 기댓값에 의거하여 MLE를 구하는 알고리즘이다. EM은 임의의 모수 기댓값을 계산하고 이 값으로 모수를 추정할 때 MLE가 최대화될 때까지 기댓값을 계속 재계산하며, 마침내 최종적인 모수의 기댓값을 도출한다. 따라서 EM은 각 데이터가 각 분포(군집)에 속할 확률을 계산하는 기대 단계(expectation step), 그리고 그 확률을 고려하여 MLE를 최대화할 수 있는 새로운 모수 기댓값으로 갱신하는 최대화 단계(maximization step)으로 나누어진다. 그리고 이 과정은 모수 기댓값의 변화량이 사전에 지정된 임계치의 미만으로 작게 변화할 때 종료된다.

이상의 접근방법은 통계학의 혼합모형(mixture model)의 논리를 군집화에 적용한 것처럼 보인다. 그러나 정규분포가 혼합되었다는 발상만 제외한다면 나머지는 K-평균 군집화와 유사한 절차를 따른다. 둘 모두 이상점에 민감하게 반응하고, 군집 간에 서로 다른 크기나 분포가 가능함을 상정하며, 실제로 EM의 관점에서 K-평균 군집화는 EM의 특수한 사례에 해당한다고 이해할 수 있다. 그러나 EM은 대용량 데이터를 빠르게 계산하기에는 K-평균 군집화에 비해 다소 취약한 모습을 보이며, 소용량 데이터의 경우 K-평균 군집화보다 군집이 잘 만들어지지 않는다는 지적이 있다. 마지막으로 군집의 개수, 즉 분포의 개수를 추정하는 데에도 베이지안의 보완이 필요하다.

3.2.5. 그래프 기반: 자기조직화지도

군집 분석과 함께 자주 엮이는 자기조직화지도(SOM; self-organizing map)는 군집 분석의 관점에서는 그래프 기반의 분할적 군집화라고 볼 수 있다. 이는 Kohonen의 군집화라고도 하며, 인공신경망(ANN; artificial neural network)에 대한 이해가 필요하다. 간략히 설명하자면 SOM은 비지도학습의 한 종류로, 신경망 기술을 활용하여 고차원의 데이터를 저차원의 뉴런으로 정렬, 지도의 형태로 형상화해서 군집화하는 방법이다. 원래 SOM은 이미지 분석에 활발히 사용되었지만 한편으로는 군집들의 중심점을 발견하는 데에도 탁월하기 때문.

SOM을 활용한 군집 분석의 목적은, 군집들의 형태를 암시적으로 정의하는 중심점들의 집합을 발견하는 데 있다. SOM은 3차 이상의 고차원적 데이터를 2차원 이하의 지도로 형상화하여 시각화하게 되는데, 입력변인들 간의 실제 공간적 거리가 가까울수록 지도상의 거리도 가깝게 도해된다. SOM은 먼저 중심점을 초기화하고, 데이터에서 가장 가까운 중심점을 결정한 후, 이 중심점 및 이와 가까이 위치한 다른 중심점을 갱신하여, 중심점의 변화가 사전에 합의된 기준 아래로 작게 발생할 경우에 종료한다. K-평균 군집화와 마찬가지로 초기값은 분석가가 직접 지정하게 되지만, K-평균 군집화와 달리 중심점들의 위상적 순서(topographic ordering)까지도 사전 지정되어야 한다.

SOM의 중요한 특징 중 하나는 그것이 완전히 연결(fully-connected)된 2층의 신경망 구조를 갖고 있다는 점이다. 먼저 언급할 신경망은 입력층(input layer)이다. 여기서는 입력신호를 받으며, 입력변인의 개수와 동일한 수의 뉴런이 존재한다. 다음으로 경쟁층(competitive layer)이 있다. 여기서는 입력층의 학습 결과가 정렬되고 군집화되는데, 연결 가중치(connection weight)를 반복적으로 재조정한다. 이때 중요한 것은 가중치에 있어 입력패턴과 가장 유사한 뉴런만이 승자독식으로 생존한다는 것이다. 즉, 데이터 입력벡터에 비교할 때 최소거리에 위치한 뉴런만이 최적부합단위(BMU; best-matching unit)로서 남겨진다.

기계학습 분야에서 SOM은 기존의 ANN에 비해 여러 장점들을 갖고 있으며, 군집 분석에도 다른 군집화에서 기대할 수 없는 장점이 존재한다. SOM은 신경망 간에 역전파(backpropagation)를 생략하고 순전파(feedforward)만 유지하므로 학습속도가 기존의 ANN보다 더 빠르고, 다른 군집 분석들보다 결과의 시각화에 더 강력하고 해석도 간편하다. 그러나 어디까지나 군집들의 중심점들을 찾기 위한 방편이므로 다른 군집 분석들보다 군집의 크기나 모양 및 밀도에 유연하게 대응하기가 더 어렵고, 결과물의 성능평가를 하기도 어려우며, 군집화의 결과가 항상 수렴한다는 보장도 없다는 한계가 존재한다.

4. 같이 보기

기계학습

데이터 마이닝

[1] 통계적 방법을 공부했다면, 마할라노비스 거리의 계산방식이 정규분포에 비추어 상당히 익숙하게 느껴질 것이다. 점 A와 점 B가 서로 3단위만큼 떨어져 있다고 하더라도 수많은 다른 점들이 A로부터 1단위 미만에만 오밀조밀 몰려 있다면 점 B는 상대적으로 매우 먼 곳에 있는 셈이 된다. 반면 점 A와 점 C가 서로 10단위만큼 떨어져 있다고 하더라도, 다른 점들이 15단위, 20단위까지 넓게 퍼져 있는 상황이라면 점 C는 점 B에 비해 점 A로부터 멀리 떨어져 있다고 말할 수 없다. [2] 수학적으로는 도함수와 경사하강법에 기초하고 있으나, 여기서는 방법론의 관점에서 소개하고 있으므로 엄밀한 수학적 증명을 원한다면 전공서를 참고할 것.