군집 분석(Cluster Analysis)은 대표적인 비지도 학습법으로 관측값 \(\mathbf{X} = \{x_{1},x_{2},...,x_{N}\}\) 을 적절한 기준에 따라 비슷한 것들끼리 모으는 과정이다. 즉 데이터의 Segmentation 과정인 것이다. 좀 더 쉽게 표현하자면, 비슷한 데이터 포인트끼리 한 그룹으로 묶고 서로 다른 데이터 포인트끼리는 다른 그룹으로 묶어버리는 과정이다.

유사한 속성을 지닌 데이터를 모아 하나의 집단으로 인지하는 과정인 셈이다. 군집 분석에 활용되는 데이터는 타깃 변수(\(\mathbf{y}\)) 없이 모든 변수가 독립 변수로만 이루어져있다는 특징을 갖는다. 이러한 점에서 군집분석은 판별분석(Classification Analysis)와 차이가 있다.

판별분석은 소속 집단(예를 들자면, \(y=0\), \(y=1\)로 구분되는)을 아는 데이터를 가지고 모형을 만들어 나중에 추가되는 (소속집단을 모르는) 데이터의 소속 집단을 맞추려고 활용하는 방식이다. 그래서 판별 분석은 모델을 생성하는 과정에서 독립변수 \(\mathbf{X}\)에 대한 타깃 변수 \(\mathbf{y}\) 를 활용하여 모델을 만들고 새로운 독립변수 \(X_{new}\) 가 입력되었을 때, 기존 모델을 활용하여 \(\mathbf{y}\) 집단을 결정짓고 이를 바탕으로 정답률을 확인할 수 있다. 판별 분석은 데이터 포인트의 범주(label)에 대한 사전 정보가 있는 경우, 분류를 더 잘 할 수 있는 모델을 만들어내는데 목적이 있다.

군집 분석은 앞서 언급한 것처럼 타깃 변수 \(\mathbf{y}\) 가 존재하지 않는 경우로, 사전 정보가 없는 자료에 대한 탐색적 방법이며 이에 따라 분석자의 주관에 따라 결과나 해석이 달라질 수 있다는 특징이 있다. 즉, 군집 분석은 유사한 데이터 포인트끼리 묶어내어 군집별 특성을 파악하여 전체 자료 구조에 대한 이해를 돕기 위해 시행하는 과정이라 할 수 있다.

이번 포스팅에서는 대표적인 군집 분석 방식인 K-평균 군집화(K-means Clustering) 알고리즘과 DBSCAN 알고리즘을 알아보고자 한다. 두개의 알고리즘은 각각 중심 기반(center-based) 군집화, 밀도 기반(density-based) 군집화라는 차이를 갖는다.

중심 기반 군집화는 동일한 클래스에 속하는 데이터는 어떤 중심점을 기준으로 분포할 것이라는 가정에 기반하는 방식이다. 군집의 중심을 기준으로 가까운 데이터를 1개의 집단으로 묶는 것으로 원 형태의 집단 모양이 형성된다.

밀도 기반 군집화는 동일한 클래스에 속하는 데이터는 밀집해 있을 것이라는 가정에 기반한다. 이 방식은 데이터가 불특정 분포를 따르는 경우 활용하는 것이 적절하다.

K-평균 군집화

K-평균 군집화(이하 K-means Clustering) 알고리즘은 가장 기본적이면서 동시에 가장 많이 활용되는 알고리즘이다. 이 알고리즘은 분석 이전에 분석자가 K값을 설정해야 한다는 특징을 갖는다. 앞서 군집 분석은 분석자의 주관에 따라 결과가 달라질 수 있다고 말하였는데 K값이 분석자의 주관에 따라 결정된다는 점이 이를 뒷받침한다. 아무튼 K값이 주어졌다고 가정하고 논의를 시작하자.

한 집단에 속한 데이터들 간의 거리가 서로 다른 집단에 속한 데이터들 간의 거리보다 더 가까울 수 있도록 집단을 나누는 것은 굉장히 상식적이다. 각 집단의 중심점을 \(\mu_{K} = \{\mu_{1},...,\mu_{k}\}\) 라 하자. 여기서 \(\mu_{k}\) 는 k번째 군집의 중심점을 의미한다.

그렇다면, 우리는 각각의 데이터 포인트로부터 가장 가까운 \(\mu_{k}\) 를 선택하여 각각의 데이터를 해당 집단에 할당해야 한다. 각각의 데이터 포인트를 군집에 할당시키는 과정은 다음과 같이 표현될 수 있다.

이 과정에서 우리는 이진 변수 \(r_{nk} \in \{0,1\}\) 를 도입한다. 여기서 \(k = 1,2,...,K\)이며 이 변수는 변수 \(\mathbf{X}=\{x_{1},....x_{N}\}\) 중 \(x_{n}\) 이 K개의 군집 중에서 어느 곳에 속하는지를 나타내는 값이다. 만약 k번째 집단에 속하게 된다면 \(r_{nk} = 1\) 이고 \(j \neq k\)인 나머지에 대해서는 \(r_{nj} = 0\) 이다. 이 이진변수를 도입하면 각각의 데이터 포인트의 최소 거리를 갖게 만드는 집단을 찾는 과정은 다음과 같은 수식으로 표현할 수 있다.

\[J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk}\mid\mid x_{n}-\mu_{k} \mid\mid^{2}\]

이를 뒤틀림 척도(distortion measure)라고 표현하기도 한다. 우리의 목표는 함수 \(J\) 를 최소화하는 \(r_{nk}\) 값과 \(\mu_{k}\) 값을 발견해내는 것이다.

\[\text{argmin}_{r,\mu} \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk}\mid\mid x_{n}-\mu_{k} \mid\mid^{2}\]

이는 \(r_{nk}\)에 대한 최적화와 \(\mu_{k}\) 에 대한 최적화 두가지 과정을 반복함으로써 성취해낼 수 있다. 일종의 EM 알고리즘과 유사한 과정을 거치는 것이다.

  1. 가장 먼저 \(\mu_{k}\) 에 대한 초기값을 설정해야 한다.

  2. \(\mu_{k}\) 값을 고정한 상태로 \(J\)를 최소화시키는 \(r_{nk}\) 값을 찾는다.

  3. \(r_{nk}\) 값을 고정한 채로 \(J\)를 최소화하는 \(\mu_{k}\)를 찾는다.

  4. 값이 수렴할 때까지 (혹은 지정한 반복 횟수까지) 2,3단계 과정을 반복한다.

\(r_{nk}\)는 다음과 같이 구할 수 있다.

함수 \(J\) 는 \(r_{nk}\)의 선형 함수이며 서로 다른 \(n\)에 해당하는 항은 각각에 대하여 독립적이다. 그래서 각각의 \(n\)에 대하여 개별적인 최적화를 시행할 수 있다. 그래서 각 \(n\)에 대하여 \(\mid\mid x_{n}-\mu_{k}\mid\mid^{2}\) 를 최소화시키는 \(k\) 값에 대하여 \(r_{nk} = 1\) 로 결정지으면 된다. 말로 길게 표현한걸 수식으로 간단히 줄이면 다음과 같다.

\[r_{nk} = \begin{cases} 1 \quad \text{if} \quad k= \text{argmin}_{j} \mid\mid x_{n}-\mu_{j}\mid\mid^{2} \\ 0 \quad \text{else} \end{cases}\]

\(r_{nk}\) 값을 고정한 상태로 \(\mu_{k}\)값을 찾는 과정은 다음과 같다.

함수 \(J\)는 \(\mu_{k}\)에 대하여 제곱 형태를 갖는다. 제곱 형태일 때 함수의 최소값을 갖는 경우는 \(\mu_{k}\) 에 대한 미분값을 0으로 하는 지점에서 발견할 수 있다.

\[2\sum_{n=1}^{N}r_{nk}(x_{n}-\mu_{k}) = 0\] \[\mu_{k} = \frac{\sum_{n}r_{nk}x_{n}}{\sum_{n}r_{nk}}\]

두번째 수식의 분모는 군집 k에 할당된 데이터 포인트의 개수를 의미하게 되며, 따라서 \(\mu_{k}\) 는 군집 k에 할당된 데이터 포인트의 평균이라 해석할 수 있다. 그래서 이 알고리즘을 K-평균 알고리즘이라 부르는 것이다. 이러한 2가지 최적화 과정을 반복해서 진행하여 각 군집에 할당되는 데이터 포인트에 변화가 없을 때 알고리즘이 작동이 종료된다.

DBSCAN 알고리즘

DBSCAN 알고리즘은 K-평균 군집화와 달리 데이터의 밀집도를 활용해 군집을 분류해낸다. 글의 도입 부분에서 언급했듯이 DBSCAN의 아이디어는 데이터가 밀집된 지역이 한 군집을 형성하고 비교적 밀집도가 낮은 영역을 경계로 다른 군집과 구분된다는 것에서 시작한다. 따라서 DBSCAN 과정에서 군집은 저밀도 영역으로 둘러쌓인 고밀도 영역으로 인식 된다.

어느 1개의 데이터 포인트를 기준으로 반경 \(\epsilon\) 내에 데이터 포인트가 최소 \(n\)개 이상 존재하면 하나의 군집으로 인식하는 것이 DBSCAN 알고리즘의 기본 방식이다. 그렇다면 우리가 DBSCAN 함수를 활용하는 과정에서는 \(\epsilon\), \(n\) 값을 설정할 필요가 있다.

1개의 데이터 포인트를 중심으로 반경 \(\epsilon\) 내에 최소 \(n\) 개 이상의 데이터 포인트가 존재한다면, 해당 데이터 포인트를 중심으로 군집이 형성되고 이를 Core Point 라고 부른다. 하나의 Core Point가 서로 다른 Core Point의 군집의 일부로 판단된다면, 해당 군집들은 서로 연결되어 하나의 군집을 형성한다.

어느 군집에는 속하지만, 스스로 Core Point가 되지 못하는 데이터 포인트를 Border Point라 부르며 이는 주로 군집의 외곽을 이루는 데이터 포인트로 구성된다. 만약 거리 \(\epsilon\) 반경 내에 데이터 포인트 수가 \(n\) 보다 적다면 그 데이터 포인트는 어느 클래스에도 속하지 않은 noise로 처리한다.

clustering

위의 그림을 바탕으로 Core Point와 Border Point, Noise를 구분해보자. 여기서 반경 \(\epsilon\) 내의 최소 데이터 포인트개수를 4로 지정했다고 가정하자.

점 A를 비롯한 빨간색 점은 Core Point이다. 각 빨간점을 중심으로 형성되는 반경 내에는 자기 자신을 포함하여 최소 4개 이상의 점이 존재한다. 각 빨간점은 서로의 반경 \(\epsilon\) 내에 존재하기 때문에 하나의 단일 군집으로 형성된다.

점 B와 C는 Core Point는 아니지만, 다른 빨간 점을 통해서 A와 하나의 군집으로 묶일 수 있다. 색깔을 다르게 표시했지만, Core Point가 아닌 것일 뿐, A와 같은 군집으로 판단된다. 반면, N은 그 어느 점과도 연결되지 못해 Noise로 구분된다.

DBSCAN은 군집수를 의미하는 값인 K를 분석 이전에 지정해야 하는 K-평균 군집화 방법과 달리 군집의 개수를 미리 지정하지 않아도 된다.

군집화 결과 평가

군집화는 정답이 없는 비지도 학습이다. 따라서 분류 정확도(Accuracy)와 같은 지표로 군집화 모델을 평가하는 것은 적절하지 않다. 그런데 어쨌든 군집화 모델에 대한 평가는 내려야 한다. 이럴 때 활용할 수 있는 것이 군집 타당성 지표(Cluster Validity Index)이다.

군집화는 비슷한 데이터 포인트끼리 하나의 그룹으로 묶고 다른 데이터 포인트와는 다른 그룹으로 묶어버리는 과정이다. 따라서 군집 간의 거리(분산)은 최대화 되고 군집 내 거리(분산)은 최소화되는 것이 바람직하다.

군집간 분산, 군집 내 분산을 바탕으로 구성되는 대표적인 군집 타당성 지표는 Dunn-Index 이다. Dunn-Index는 다음과 같은 수식으로 표현 가능하다.

\[I(C) = \frac{\text{min}_{i \neq j} \{d_{c}(C_{i},C_{j})\}}{\text{max}_{1 \leq l \leq k} \{\Delta C_{l}\}}\]

분자 부분은 군집 \(i\)와 군집 \(j\)의 거리 최소값으로 이는 군집 간 분산의 최소값이며, 분모 부분은 전체 \(K\)개의 군집 중 군집 내 분산이 최대인 \(l\) 번째 군집의 군집 내 분산값을 의미한다. 군집 간 분산은 클수록 군집 내 분산은 작을수록 좋은 군집 결과이므로 Dunn-Index는 값이 클수록 군집의 결과가 좋다고 판단된다.

최적의 군집 개수를 결정하는 과정에서 사용되는 또 다른 방법은 실루엣(silhouette) 점수를 활용하는 것이다. 실루엣 점수 역시도 Dunn-Index와 마찬가지로 군집 내 분산 최소화, 군집 간 분산 최대화를 목표로 한다. 실루엣 점수는 다음과 같은 공식을 통해 구할 수 있다.

\[s(i) = \frac{b(x_i)-a(x_i)}{\text{max}\{a(x_i),b(x_i)\}}\]

먼저 \(a(x_i)\) 는 \(i\)번째 개체와 같은 군집에 속한 요소들 간에 거리의 평균값을 의미한다. 반면 \(b(x_i)\)는 \(i\)번째 개체와 다른 군집에 속한 요소들 간의 거리 평균을 구하고 그 중에 최소값을 선택한다. 즉, \(b(x_i)\) 는 \(i\)번째 개체가 속한 군집과 가장 가까운 이웃 군집을 택하여 거리의 평균값을 계산하는 것이다.

이 값은 -1부터 1 사이의 값을 가질 수 있다. 군집 내 거리 최소, 군집 간 거리 최대를 추구하기 때문에 \(b(x_{i}) \geq a(x_{i})\) 인 케이스가 바람직한 결과이다. 따라서 실루엣 점수가 1에 가까울수록 좋다고 볼 수 있다.

이 포스팅과 관련된 간단한 코드는 다음의 주소에서 확인할 수 있습니다.