25. Clustering

25.1. Introduction

클러스터링은 비슷한 오브젝트를 한데 묶는 과정이다. 이 때 사용할 입력에는 크게 두 종류가 있다. 유사도 기반 클러스터링에서는 입력은 N \times N 비유사도 행렬 또는 거리 행렬 \mathbf{D}로 주어진다. 특성 기반 클러스터링에서는 입력은 N \times D 특성 행렬 또는 디자인 행렬 \mathbf{X}로 주어진다. 유사도 기반 클러스터링은 도메인 의존적 유사도나 커널 함수를 포함하기 쉽다는 장점이 있다. 특성 기반 클러스터링에서는 노이즈 있을 수 있는 전처리되지 않은 데이터에 적용하기 쉽다는 장점이 있다.

출력에도 크게 두 가지 종류가 있다. 평평한 클러스터링 (또는 분할 클러스터링)에서는 오브젝트가 서로소인 집합으로 분할된다. 분할 클러스터링에서는 분할이 심층 트리로 구성된다. 전자는 O(ND)의 시간, 후자는 O(N^{2} \log N)의 시간이 든다. 하지만 분할 클러스터링이 일반적으로 더 유용하고, 결정론적이며 클러스터의 수를 특정해줘야 할 필요가 없다. 반면 평평한 클러스터링 알고리즘들은 초기 조건과 클러스터 수 K에 의존적이다.

또한 확률적이지 않은 클러스터링법도 있다. 이들은 자주 쓰이기도 하고 확률적 모델을 가속시킬 수 있는 좋은 아이디어를 담고 있기도 하다.

25.1.1. Measuring (dis)similarity

비유사도 행렬 \mathbf{D}d_{ii} = 0, d_{ij} \geq 0을 만족하는 행렬이다. 삼각 부등식이 성립하지 않을 때가 많으므로 엄밀한 의미에서의 거리를 만족시키지는 않는다. 유사도 행렬 \mathbf{S}이 있다면 이를 \mathbf{D} = \max(\mathbf{S}) - \mathbf{S}를 통해 비유사도 행렬로 변경할 수 있다. 오브젝트간 비유사도는 그 특성간 비유사도의 합 \delta(\mathbf{x}_{i}, \mathbf{x}_{i'}) = \sum_{j=1}^{D} \delta_{j}(x_{ij}, x_{i'j})로 정의된다. 특성간 비유사도를 정의하는 자주 쓰이는 함수들은 다음과 같다.

  • 유클리드 거리 \delta_{j}(x_{ij}, x_{i'j}) = (x_{ij} - x_{i'j})^{2}
  • l_{1} 거리 또는 도시 블록 거리 \delta_{j}(x_{ij}, x_{i'j}) = |x_{ij} - x_{i'j}|
  • 상관 계수.
  • 서수에 대해서는 이들에 1, 2, 3 등의 실수를 부여함으로써 전처리를 하고는 한다.
  • 범주 변수에 대해서는 해밍 거리 \delta(\mathbf{x}_{i}, \mathbf{x}_{i'}) = \sum_{j=1}^{D} \mathbf{1}_{x_{ij} \neq x_{i'j}}로 정의한다.

25.1.2. Evaluating the output of clustering methods

클러스터링을 검증하는 것은 가장 어려운 부분이다. 이는 클러스터링이 비지도학습이기 때문이다. 확률적 모델링을 쓸 수도 있지만 그 모델이 반드시 클러스터링을 표현한다는 법이 없고 비확률적 방법에 대해서는 사용할 수가 없다. 따라서 여기서는 가능도에 기반하지 않은 방법을 쓰기로 한다. 비슷한 점들은 같은 클러스터로 묶고, 비슷하지 않은 점들끼리는 다른 클러스터로 분리할 수 있다면 좋을 것이다.

25.1.2.1. Purity

N_{ij}를 클러스터 i 내 클래스 j 오브젝트의 수라고 하고 N_{i} = \sum_{j=1}^{C} N_{ij}를 클러스터 i 내 모든 오브젝트의 수라고 하자. p_{ij} = \frac{N_{ij}}{N_{i}}를 클러스터 i 내 라벨의 실측 분포라면 순수도 p_{i} = \max_{j} p_{ij}를 정의하면 전체 클러스터의 순수도를 \sum_{i} \frac{N_{i}}{N}p_{i}로 정의할 수 있다. 하지만 각 오브젝트마다 하나의 클러스터를 정의하면 순수도는 1이 되기 때문에 이는 단순히 클러스터의 수를 늘리는 것을 해결해 주지 못한다.

25.1.2.2. Rand index

U = \{u_{1}, \cdots, u_{R}\}, V = \{v_{1}, \cdots, v_{C}\}를 N개 데이터의 2개의 다른 분할이라 하자. 이제 2 x 2 행렬에서 TP를 U, V에서 같은 클러스터에 속한 쌍의 수, TN을 U, V에서 다른 클러스터에 속한 쌍의 수, FN을 U에서는 다른 클러스터에 속했지만 V에서는 같은 클러스터에 속한 쌍의 수, FP를 U에서는 같은 클러스터에 속했지만 V에서는 다른 클러스터에 속한 쌍의 수라고 하자. 그러면 랜드 지수 R = \frac{TP + TN}{TP + FP + FN + TN}을 클러스터링 정확도의 지표로 쓸 수 있다. 또는 조정 랜드 지수 AR = \frac{index - expected index}{max index - expected index}을 쓸 수도 있다.

랜드 지수는 거짓 음성과 거짓 양성을 똑같이 다룬다. F-점수 등의 다른 지표를 쓸 수도 있다.

25.1.2.3. Mutual information

U와 V 사이의 상호 정보량을 계산할 수도 있다. p_{UV}(i, j) = \frac{u_{i} \cap v_{j}}{N}, p_{U}(i) = \frac{\lvert u_{i} \rvert}{N}, p_{V}(j) = \frac{\lvert v_{j} \rvert}{N}로 정의하면 \mathbb{I}(U, V) = \sum_{i=1}^{R} \sum_{j=1}^{C} p_{UV}(i, j) \log \frac{p_{UV}(i, j)}{p_{U}(i)p_{V}(j)}로 상호 정보량을 계산할 수도 있다. 작은 클러스터가 여러 개 있으면 상호 정보량이 커지기 때문에 이를 보정하기 위해 표준화된 상호 정보량 NMI(U, V) = \frac{2 \mathbb{I}(U, V)}{\mathbb{H}(U) + \mathbb{H}(V)}를 쓰고는 한다. 또는 변량 정보량을 쓰기도 한다.

25.2. Dirichlet process mixture models

평탄 클러스터링에 쓸 수 있는 간단한 접근법은 유한 결합 모델을 쓰는 것이다. 이를 모델 기반 클러스터링이라고 부른다. 이는 성분의 수 K를 결정하기 힘들다는 단점이 있다.

여기서는 무한 결합 모델을 다룬다. 이를 위해서, 디리클레 과정에 기반한 비매개 사전분포를 쓴다. 이는 비매개 베이즈의 일종이다.

25.2.1. From finite to infinite mixture models

유한 결합 모델은 다음과 같이 나타내어진다.

p(\mathbf{x}_{i} | z_{i} = k, \mathbf{\theta}) = p(\mathbf{x}_{i} | \mathbf{\theta}_{k})

p(z_{i} = k | \mathbf{\pi}) = \pi_{k}

p(\mathbf{\pi} | \alpha) = \mathrm{Dir}(\mathbf{\pi} | \frac{\alpha}{K} \mathbb{1}_{K})

이 때 p(\mathbf{\theta}_{k} | \lambda)p(\mathbf{x}_{i} | \mathbf{\theta}_{k})와 켤레분포로 선택된다. 관측 분포를 F, 사전 분포를 H라 하면 \mathbf{x}_{i} \sim F(\mathbf{\theta}_{z_{i}}), \mathbf{\theta}_{k} \sim H(\lambda)로 표기할 수 있다. 또는 G(\mathbf{\theta}) = \sum_{k=1}^{K} \pi_{k} \delta_{\mathbf{\theta}_{k}}(\mathbf{\theta})일 때 분포 G로부터 샘플된다고 볼 수도 있다. (\mathbf{\pi} \sim \mathrm{Dir}(\frac{\alpha}{K} \mathbf{1}), \mathbf{\theta}_{k} \sim H) 이 모델로부터는 항상 K개의 클러스터를 얻는다.

G를 무작위 확률측도로 치환해 가변 개수의 클러스터를 얻고 데이터를 많이 생성할 수록 새 클러스터가 생성될 확률도 주게 할 수 있다. 심지어 이는 계산 가능하고, 서로 다른 K에 대해 유한 결합 모델을 피팅할 때에 비해 계산량도 더 적게 할 수 있다. 직관적 이유는 매개변수를 추정하기 전에 어떤 K의 값이 적절한 지 판단할 수 있기 때문이다. 이는 풀어야 할 모델 선택 문제가 여러 개일 때 더욱 그렇다.

디리클레 과정 혼합 분포를 통한 샘플링.

25.2.2. The Dirichlet process

가우시안 과정은 f : \mathcal{X} \to R의 형태를 가진 함수에서의 분포라는 것을 상기해 보자. 이는 p(f(\mathbf{x}_{1}), \cdots, f(\mathbf{x}_{N}))가 결합 가우시안이어야 한다는 조건으로부터 묵시적으로 유도될 수 있다. 이 가우시안은 평균 함수 \mu()와 공분산 (커널) 함수 K()로부터 f \sim \mathrm{GP}(\mu(), K())로 계산될 수 있다.

디리클레 과정은 확률측도 G : \Theta \to \mathbb{R}^{+} 위에서의 분포이며, G(\theta) \geq 0, \int_{\Theta} G(\theta) d \theta = 1 조건을 갖는다. 이는 \Theta의 임의의 유한 분할 (T_{1}, \cdots, T_{k})에 대해 (G(T_{1}), \cdots, G(T_{K}))이 결합 디리클레 분포 \mathrm{Dir}(\alpha H(T_{1}), \cdots, \alpha H(T_{K}))을 따른다는 조건으로부터 묵시적으로 유도될 수 있다. 이 경우 G \sim \mathrm{DP}(\alpha, H)로 쓰며 \alpha집중 매개변수, H기반 측도라 한다.

\mathbf{\pi} \sim \mathrm{Dir}(\mathbf{\alpha}), z | \mathbf{\pi} \sim \mathrm{Cat}(\mathbf{\pi})이면 \mathbf{\pi}를 적분해 디리클레-다항 베르누이 모델에 대한 예측 분포 z \sim \mathrm{Cat}(\frac{\alpha_{1}}{\alpha_{0}}, \cdots, \frac{\alpha_{K}}{\alpha_{0}})를 얻을 수 있다. (\alpha_{0} = \sum_{k} \alpha_{k}, 즉, p(z = k | \mathbf{\alpha}) = \frac{\alpha_{k}}{\alpha_{0}})

또한, 관찰 1개가 주어졌을 때 \mathbf{\pi}에 대한 업데이트된 사후분포는 \mathbf{\pi} | z \sim \mathrm{Dir}(\alpha_{1} + \mathbb{1}_{z = 1}, \cdots, \alpha_{K} + \mathbb{1}_{z = K})이 된다.

디리클레 과정은 임의의 분할에 대해 이를 확장한다. G \sim \mathrm{DP}(\alpha, H)일 때, p(\mathbf{\theta} \in T_{i}) = H(T_{i})이고 사후분포는 p(G(T_{1}), \cdots, G(T_{K}) | \mathbf{\theta}, \alpha, H) = \mathrm{Dir}(\alpha H(T_{1}) + \mathbf{1}_{\mathbf{\theta} \in T_{1}}, \cdots, \alpha H(T_{K}) + \mathbf{1}_{\mathbf{\theta} \in T_{K}})이 된다. 이는 임의의 분할에 대해 성립하므로, 표본 여러 개 \bar{\mathbf{\theta}}_{i} \sim G를 관찰한다면, 새 사후분포는 G | \bar{\mathbf{\theta}}_{1}, \cdots, \bar{\mathbf{\theta}}_{N}, \alpha, H \sim \mathrm{DP}(\alpha + N, \frac{1}{\alpha + N}(\alpha H + \sum_{i=1}^{N} \delta_{\mathbf{\theta}_{i}}))로 주어진다. 그러므로 디리클레 과정은 임의의 가측공간에 대한 켤레사전분포를 효과적으로 정의한다. 집중 매개변수 \alpha는 기반측도 H에 대한 유효표본수라고 볼 수 있다.

25.2.2.1. Stick breaking construction of the DP

막대 파괴 구성으로부터 디리클레 과정을 구성해 보자. \pi = \{\pi_{k}\}_{k=1}^{\infty}을 다음의 과정으로부터 유도되는 결합 가중치의 수열이라 하자:

\beta_{k} \sim \mathrm{Beta}(1, \alpha)

\pi_{k} = \beta_{k} \prod_{l=1}^{k - 1}(1 - \beta_{l}) = \beta_{k}(1 - \sum_{k=1}^{k-1} \pi_{l})

이는 \pi \sim \mathrm{GEM}(\alpha)로 나타내어지고는 하며, 확률 1로 종료됨이 보장된다. \alpha에 따라 생성하는 원소의 수가 커지고, \pi{k} 요소의 크기는 줄어든다. 이제 \pi \sim \mathrm{GEM}(\alpha), \mathbf{\theta}_{k} \sim H일 때 G(\mathbf{\theta}) = \sum_{k=1}^{\infty} \pi_{k} \delta_{\mathbf{\theta}_{k}}(\mathbf{\theta})를 정의하면 G \sim \mathrm{DP}(\alpha, H)임을 보일 수 있다. 그러므로 디리클레 과정으로부터의 표본은 확률 1에 대해 이산적이다. 즉, 계속해서 샘플링을 한다면, 이전에 생성된 값들을 계속해서 얻게 된다. 그러므로 \bar{\mathbf{\theta}}_{i} \sim G를 샘플링하면 이 값들이 서로 다른 값들 \mathbf{\theta}_{k}들 주위로 클러스터링된다. 이 방법으로 디리클레 과정을 클러스터링에 사용할 수 있다.

막대 파괴 구성의 예.

25.2.2.2. The Chinese restaurant process (CRP)

클러스터링 특성을 통해 디리클레 과정으로부터 표본을 추출해 보자. 핵심은 \hat{\mathbf{\theta}}_{i} \sim GG \sim \mathrm{DP}(\alpha, H)로부터의 N개의 관찰이면, K개의 서로 다른 \mathbf{\theta}_{k}들을 취하면 다음 관측에 대한 예측분포는 p(\bar{\mathbf{\theta}}_{N+1} = \mathbf{\theta} | \bar{\mathbf{\theta}}_{1 : N}, \alpha, H) = \frac{1}{\alpha + N}(\alpha H(\mathbf{\theta}) + \sum_{k=1}^{K} N_{k} \delta_{\bar{\mathbf{\theta}}_{k}}(\mathbf{\theta}))로 주어진다. (N_{k}\mathbf{\theta}_{k}가 이전에 관측된 횟수) 이를 폴야 항아리 또는 블랙웰-맥퀸 샘플링이라 한다. 이는 디리클레 과정으로부터 샘플링을 하는 구성적 방법을 제공한다.

어떤 \mathbf{\theta}_{k}을 쓸지 특정하는 이산변수 z_{i}를 이용하면 더 쉽다. 즉, \bar{\mathbf{\theta}}_{i} = \mathbf{\theta}_{z_{i}}로 정의하면 위의 식은 p(z_{N+1} = z | \mathbf{z}_{1 : N}, \alpha) = \frac{1}{\alpha + N}(\alpha \mathbf{1}_{z = k^{\ast}} + \sum_{k=1}^{K} N_{k} \mathbf{1}_{z = k})로 간소화된다. (k^{\ast}는 사용되지 않은 새 클러스터 인덱스). 이를 중식당 과정(CRP)이라 하며, 정수들의 분할 위에서의 분포이다. 이는 부익부 문제를 겪는다는 문제점이 있다. 실제로, 할당된 클러스터의 수 K는 N \to \infty에 따라 \alpha \log (N)로 수렴한다. 즉, 모델 복잡도는 데이터셋의 크기의 로그에 맞게 비례한다. 클러스터 크기에 대한 더 유연한 사전분포도 정의될 수 있는데, 이변수 핏먼-요르 과정 등이 있다.

25.2.3. Applying Dirichlet processes to mixture modeling

디리클레 과정은 데이터를 직접적으로 모델링하는 데는 그리 유용하지 않다. 데이터 벡터들 자체는 정확히 반복되는 일이 거의 없기 때문이다. 하지만, 혼합 모델과 같은 추계적 데이터 생성 메커니즘의 매개변수에 대한 사전분포로는 유용하다. 즉, 모델을 다음과 같이 쓸 수 있다.

\mathbf{\pi} \sim \mathrm{GEM}(\alpha)

z_{i} \sim \mathbf{\pi}

\mathbf{\theta}_{k} \sim H(\lambda)

\mathbf{x}_{i} \sim F(\mathbf{\theta}_{z_{i}})

G \sim \mathrm{DP}(\alpha, H)

이 때 G는 기반 분포 H로부터의 매개변수 \mathbf{\theta}_{k}를 각각 가중치 \pi_{k}로 제한 없이 무작위로 추출한 것이다. 각각의 데이터 \mathbf{x}_{i}는 G로부터 그 자신의 매개변수 \bar{\mathbf{\theta}}_{i}를 추출함으로써 생성된다. 데이터를 많이 얻을수록 \bar{\mathbf{\theta}}_{i}가 이전에 관측한 데이터 \mathbf{\theta}_{k}와 같아질 확률이 높아질 것이다. 그러므로 \mathbf{x}_{i}는 이미 존재하는 데이터와 가깝게 생성될 것이다.

25.2.4. Fitting a DP mixture model

디리클레 과정 혼합 분포를 피팅하는 가장 간단한 방법은 붕괴 깁스 샘플링을 이용하는 것이다. 다음이 성립한다.

p(z_{i} = k | \mathbf{z}_{-i}, \mathbf{x}, \alpha, \mathbf{\lambda}) \propto p(z_{i} = k | \mathbf{z}_{-i}, \alpha) p(\mathbf{x}_{i} | \mathbf{x}_{-i}, z_{i} = k, \mathbf{z}_{-i}, \mathbf{\lambda})

일반성을 잃지 않고, z_{i}를 마지막 샘플이라고 가정할 수 있다. 즉, 첫 번쨰 항은 p(z_{i} | \mathbf{z}_{-i}, \alpha) = \frac{1}{\alpha + N - 1}(\alpha \mathbf{1}_{z_{i} = k^{\ast}} + \sum_{k=1}^{K} N_{k, -i}\mathbf{1}_{z_{i} = k})로 주어진다. (K는 \mathbf{z}_{-i}에 쓰인 클러스터 수, k^{\ast}는 새 클러스터) 또는, p(z_{i} = k | \mathbf{z}_{-i}, \alpha)를 k가 이전에 본 적 있는 클러스터라면 \frac{N_{k, -i}}{\alpha + N - 1}, 새 클러스터라면 \frac{\alpha}{\alpha + N - 1}로 표현할 수도 있다.

두 번째 항 p(\mathbf{x}_{i} | \mathbf{x}_{-i}, z_{i} = k, \mathbf{z}_{-i}, \mathbf{\lambda})을 계산하기 위해서는 데이터 \mathbf{x}_{-i}\mathbf{z}_{-i} 기반한 클러스터로 분할한다. \mathbf{x}_{-i, c} = \{\mathbf{x}_{j} : z_{j} = c, j \neq i \}를 클러스터 c에 할당된 데이터의 집합이라 하자.

z_{i} = k\mathbf{x}_{i}는 클러스터 k에 할당된 데이터를 제외한 다른 모든 데이터에 대해 조건부독립이다. 그러므로 p(\mathbf{x}_{i} | \mathbf{x}_{-i}, \mathbf{z}_{-i}, z_{i} = k, \mathbf{\lambda}) = p(\mathbf{x}_{i} | \mathbf{x}_{-i, k}, \mathbf{\lambda}) = \frac{p(\mathbf{x}_{i}, \mathbf{x}_{-i, k} | \mathbf{\lambda})}{p(\mathbf{x}_{-i, k} | \mathbf{\lambda})}이 성립한다. 이 때 p(\mathbf{x}_{i}, \mathbf{x}_{-i, k} | \mathbf{\lambda}) = \int p(\mathbf{x}_{i} | \mathbf{\theta}_{k} [\prod_{j \neq i:z_{j} = k} p(\mathbf{x}_{j} | \mathbf{\theta}_{k})] H(\mathbf{\theta}_{k} | \mathbf{\lambda}) d \mathbf{\theta}_{k}은 클러스터 k에 할당된 데이터 전부에 대한 주변가능도이고, p(\mathbf{x}_{-i, k} | \mathbf{\lambda}) = \int \prod_{j \neq i:z_{j} = k} p(\mathbf{x}_{j} | \mathbf{\theta}_{k}) H(\mathbf{\theta}_{k} | \mathbf{\lambda}) d \mathbf{\theta}_{k}는 클러스터 k에 할당된 데이터에서 i를 제외한 데이터들에 대한 주변가능도이다. 그러므로 p(\mathbf{x}_{i} | \mathbf{x}_{-i}, \mathbf{z}_{-i}, z_{i} = k, \mathbf{\lambda})은 클러스터 k에 대한 사후예측분포를 \mathbf{x}_{i}에서 구한 값이다.

z_{i} = k^{\ast}p(\mathbf{x}_{i} | \mathbf{x}_{-i}, \mathbf{z}_{-i}, z_{i} = k^{\ast}, \mathbf{\lambda}) = p(\mathbf{x}_{i} | \mathbf{\lambda}) = p(\mathbf{x}_{i} | \mathbf{\lambda}) = \int p(\mathbf{x}_{i} | \mathbf{\theta}) H(\mathbf{\theta} | \mathbf{\lambda}) d \mathbf{\theta}이 되며 , 이는 새 클러스터에 대한 사전예측분포를 \mathbf{x}_{i}에서 구한 값이다. 이는 유한 결합에 대한 붕괴 깁스 샘플링과 대단히 비슷한데, 차이점은 새 클러스터가 생기는 경우 z_{i} = k^{\ast}를 고려해야 한다는 것뿐이지만, 추가 클러스터를 초기 과정에 만들 수 있기 때문에 깁스 샘플링이나 기대값 최대화 알고리즘에 비해서 국소적 최적해에 갇히는 일이 훨씬 적다. A^{\ast} 탐색과 빔 탐색을 이용하거나, 입자 필터링 등을 이용하는 여러 피팅 방법도 있다.

다른 중요한 이슈는 초매개변수를 어떻게 세팅하는지이다. 디리클레 과정에 대해서는 \alpha가 예측정확도에 크게 영향을 미치지는 않지만, 클러스터의 수에는 영향을 미친다. 한 접근법은 \mathrm{Ga}(a, b) 사전분포를 \alpha에 적용한 뒤 그 사후분포 p(\alpha | K, N, a, b)를 보조변수방법으로 구성하는 것이다. 또는 실측 베이즈를 이용할 수도 있다.

25.3. Affinity propagation

혼합 모델은 유한이든 무한이든 간에 N \times D 데이터 행렬에 대한 접근을 필요로 하며, 이 데이터에 대한 생성적 모델을 특정할 필요가 있다. 다른 방법은 N \times N 유사도 행렬을 입력으로 받는 것이다. K-중심 알고리즘도 하나의 방법이 될 수 있지만 국소적 최적해에 취약하다. 다른 방법으로 친화도 전파가 있다. 실제로 이것은 더 잘 동작한다.

발상은 각 데이터는 반드시 다른 데이터를 중심으로 삼아야 한다는 것이다. 구체적으로, c_{i} \in \{1, \cdots, N\}를 데이터 i의 무게중심이라 하면 목표는 S(\mathbf{c}) = \sum_{i=1}^{N} s(i, c_{i}) + \sum_{k=1}^{N} \delta_{k}(\mathbf{c})을 최대화시키는 것이다. 첫 번째 항은 각 점과 그 점의 무게중심간 유사성을 측정하고, 두 번째 항은 \delta_{k}(\mathbf{c}) = -\infty (c_{k} \neq k이지만 \exists i : c_{i} = k인 경우), \delta_{k}(\mathbf{c}) = 0 (이외)로서 c_{k} = k임을 강제하는 역할을 한다. 이 목적 함수는 노드 N개가 각각 N개의 값을 가질 수 있는 인자 그래프로 표현할 수 있다.

이 목적 함수는 최대-곱 순환 믿음 전파를 통해 국소적 최대값을 찾을 수 있다. 각각의 변수 노드 c_{i}는 각 인자 노드 \delta_{k}에 메시지(책임도) r_{i \to k}를 보낸다. 추가로, 각각의 인자 노드 \delta_{k}는 각 변수 노드 c_{i}에 메시지(가용성) a_{i \leftarrow k}를 보낸다. 이는 순환 믿음 전파법이므로 수렴이 보장되어 있지 않지만, 감쇠법을 쓰면 실제로는 상당히 잘 동작한다. 그래프의 밀도가 높다면 메시지 전파는 O(N^{2}) 시간이 걸리지만, 그래프가 희소하다면 간선의 수를 E라고 할 때 O(E) 시간이 걸린다. 클러스터의 수는 대각선 원소 S(i, i)를 스케일링함으로써 조절할 수 있다. 많은 상황에서 이는 K-메도이드 법보다 훨씬 잘 동작한다.

25.4. Spectral clustering

클러스터링을 보는 다른 관점은 그래프 컷으로 보는 것이다. 발상은유사도 행렬 \mathbf{S}로부터 각 점의 최근접 근방만을 사용해 희소 가중비방향그래프 \mathbf{W}를 구성한다. K개의 클러스터로 나누고 싶다면 \mathrm{cut}(A_{1}, \cdots, A_{k}) = \frac{1}{2} \sum_{k=1}^{K} \sum_{i \in A_{k}, j \in V - A_{k}} w_{ij}를 최대화하는 것으로 목표를 잡을 수 있다. 하지만 많은 경우 최적해는 단지 한 점을 나머지와 분리하게 되는데, 이를 방지하기 위해 표준화 컷 \mathrm{Ncut}(A_{1}, \cdots, A_{k}) = \frac{1}{2} \sum_{k=1}^{K} \frac{\mathrm{cut}(A_{k}, V - A_{k})}{\sum_{i \in A} \sum_{j=1}^{N} w_{ij}}을 정의할 수 있다. 이는 그래프를 K개의 클러스터로 분할하되 각 클러스터 내의 노드는 서로 비슷하도록 하지만 다른 클러스터의 노드와는 다르도록 한다.

이는 목적 함수를 최소화하는 이진 벡터 \mathbf{c}_{i} \in \{0, 1\}^{N} (c_{ik} = 1은 점 i가 클러스터 k에 속함을 나타내는 지시 변수)를 찾는 문제로 볼 수 있는데, 이는 NP-난해이다. 친화도 전파로 풀 수도 있고, \mathbf{c}_{i}를 실변수벡터로 전환한 뒤 고유벡터를 찾는 스펙트럼 클러스터링 문제로 바꿀 수도 있다. 이는 스펙트럼 그래프 이론의 일부이다.

25.4.1. Graph Laplacian

그래프에 대한 대칭 가중치 행렬 \mathbf{W}, w_{ij} = w_{ij} \geq 0이 있을 때, \mathbf{D} = \mathrm{diag}(d_{i})를 대각행렬이라 하면 그래프 라플라시안\mathbf{L} = \mathbf{D} - \mathbf{W}로 정의할 수 있다. 이는 \mathbf{1}을 고유값 0에 연관된 고유벡터로 갖고, 대칭이고 양의 반정칙이라는 특성을 갖는다. 또한 다음이 성립한다.

Theorem. \mathbf{L}의 고유값 0에 연관된 고유벡터의 집합은 지시 벡터 \mathbf{1}_{A_{1}}, \cdots, \mathbf{1}_{A_{K}}에 의해 생성된다. (A_{k}는 그래프의 K개의 연결요소)

이로부터 다음의 알고리즘을 생각할 수 있다. \mathbf{L}의 첫 K개의 고유벡터 \mathbf{u}_{k}를 열로 가지는 행렬 \mathbf{U}를 만든다. \mathbf{y}_{i} \in \mathbb{R}^{K}를 이의 i번째 행이라 하면 이는 구간별로 상수함수이므로 이에 K-평균 클러스터링을 적용해 연결요소들을 복원할 수 있다. 이제 \mathbf{Y}의 i번째 행이 클러스터 k에 할당된 경우에는 점 i를 클러스터 k에 할당하면 된다.

실제로는 그래프에 연관된 유사도 행렬이 분할연결요소를 가지는 일은 별로 없다. 하지만 분할연결요소를 가지는 행렬의 작은 변형이라고 가정하는 것은 바람직하다.

이 접근법은 커널 주성분 분석과 연관이 있는데, 커널 주성분 분석은 \mathbf{W}의 최대 고유벡터를 쓰고, \mathbf{I} - \mathbf{W}의 최소 고유벡터를 쓰는 것과 같다. 위의 알고리즘은 \mathbf{D} - \mathbf{W}의 최소 고유벡터를 쓰므로 비슷하다고 볼 수 있다. 실제로는 스펙트럼 클러스터링이 커널 주성분 분석보다 훨씬 잘 동작한다.

25.4.2. Normalized graph Laplacian

특정 노드는 연결성을 더 많이 가질 수 있기 때문에 그래프 라플라시안을 표준화하는 것은 중요하다. 두 가지 방법이 있는데, 첫 번째 방법은 무작위 걸음 행렬 \mathbf{L}_{rw} = \mathbf{D}^{-1} \mathbf{L}을 만든 뒤, 이의 K개의 최소 고유벡터를 열로 갖는 행렬을 만들고, 이의 행들을 K-평균 알고리즘으로 클러스터링하고 원래 점들의 분할을 추론하는 것이다. 두 번째 방법은 대칭 행렬 \mathbf{L}_{sym} = \mathbf{D}^{-\frac{1}{2}}\mathbf{L}\mathbf{D}^{-\frac{1}{2}}을 만든 뒤, 이의 K개의 최소 고유벡터를 열로 갖는 행렬을 만들고, 이의 행들을 각각 길이 1로 표준화한 뒤, 이 표준화한 행들을 K-평균 알고리즘으로 클러스터링하고 원래 점들의 분할을 추론하는 것이다.

그래프에서의 무작위 걸음과 표준화 컷에는 중요한 관계가 있다. 첫째로는 \mathbf{P} = \mathbf{I} - \mathbf{L}_{rw}는 추계적 행렬이 되며, p_{ij} = \frac{w_{ij}}{d_{i}}은 i로부터 j로 가는 확률이라 볼 수 있다. 그래프가 연결그래프이고 이분그래프가 아니라면, \pi_{i} = \frac{\sum_{j} w_{ij}}{\sum_{i \in V}\sum_{j} w_{ij}}이라 할 때 유일한 정지 분포 \mathbf{\pi} = (\mathbf{\pi}_{1}, \cdots, \mathbf{\pi}_{N})을 갖는다. 또한, \mathrm{Ncut}(A, V - A) = p(V - A | A) + p(A | V - A)임이 성립한다. 즉, 우리는 무작위 걸음이 A와 V – A 사이의 전환을 가급적 일으키지 않는 그래프 컷을 찾게 된다.

25.4.3. Example

다음 예제에서는 스펙트럼 클러스터링이 K-평균 클러스터링을 압도한다. 이는 O(N^{3}) 시간이 걸린다.

K-평균 클러스터링 vs 스펙트럼 클러스터링.

25.5. Hierarchical clustering

혼합 모델은 유한이든 무한이든 평탄한 클러스터링을 제공한다. 클러스터가 다른 클러스터에 포함되는 계층적 클러스터링을 하려면 두 가지 방법이 있는데, 상향식 (응집적 클러스터링)과 하향식 (분리적 클러스터링)이 있다. 둘 다 오브젝트간 비유사도 행렬을 입력으로 받지만, 상향식 접근법에서는 가장 비슷한 그룹들이 각 단계에서 뭉쳐지고, 하향식 접근법에서는 그룹들이 여러 다른 기준에 따라 분할된다.

이들은 모두 휴리스틱에 불과할 뿐, 잘 정의된 목적 함수를 최적화하지는 않는다는 점을 염두에 둘 필요가 있다. 그래서 이들이 낳는 클러스터링을 정확히 평가하기는 어렵다. 또한, 데이터에 구조가 없더라도 계층화된 클러스터링을 제공한다는 문제점이 있다.

25.5.1. Agglomerative clustering

응집적 클러스터링은 각각 하나의 오브젝트를 담고 있는 N개의 그룹으로부터 시작해서 각 단계마다 가장 유사한 2개의 그룹을 병합하여 단 하나의 그룹이 남을 때까지 이를 반복한다. 전체 시간복잡도는 O(N^{3})이지만, 우선 순위 큐를 쓰면 O(N^{2} \log N)으로 줄일 수 있다. N이 큰 경우에는 K-평균 알고리즘을 처음 사용해서 (O(KND) 시간이 든다) 클러스터 중심에 대해 계층적 클러스터링을 수행하는 휴리스틱이 있다. 병합 과정은 덴드로그램이라 불리는 이진 트리로 나타내어진다. 특정 높이에서 이 트리를 끊으면 특정 크기의 클러스터링을 얻는다. 응집적 클러스터링에는 오브젝트의 그룹간 비유사도를 어떻게 정의하냐에 따라 3가지 변형이 있다.

응집적 클러스터링의 예.

25.5.1.1. Single link

단일 연결 클러스터링(최근접 근방 클러스터링)에서는 두 그룹 G, H간의 거리는 두 그룹 내 가장 가까운 멤버의 거리로 나타내어진다. d_{SL}(G, H) = \min_{i \in G, j \in H} d_{ij} 이로부터 만들어지는 트리는 데이터의 최소 신장 트리이다. 이 때문에 이는 O(N^{2}) 시간에 구현할 수 있다.

25.5.1.2. Complete link

완전 연결 클러스터링(최원 근방 클러스터링)에서는 두 그룹 G, H간의 거리는 두 그룹 내 가장 먼 멤버의 거리로 나타내어진다. d_{CL}(G, H) = \max_{i \in G, j \in H} d_{ij} 단일 연결 클러스터링의 문제점은 두 그룹에서 단 한 쌍만 가까우면 되기 때문에 클러스터링이 컴팩트성을 위반한다는 것, 즉 그룹의 반경에 대해서 클러스터의 반경이 큰 클러스터링을 한다는 점이다. 완전 연결 클러스터링은 이 반대로서, 그룹 내 모든 원소 쌍들이 가까워야 한다. 이는 작은 반경의 컴팩트한 클러스터링을 낳는다.

25.5.1.3. Average link

실제로는 평균 연결 클러스터링이 많이 쓰인다. 이 때 두 그룹 G, H간의 거리는 모든 쌍 간의 거리의 평균 d_{avg}(G, H) = \frac{1}{n_{G}n_{H}} \sum_{i \in G}\sum_{j \in H} d_{ij}으로 정의된다. 이는 위의 두 방법의 장점을 결합하지만, 측정법이 달라지면 클러스터링 결과도 달라진다는 문제점이 있다.

3가지 응집적 클러스터링.

25.5.2. Divisive clustering

분리적 클러스터링은 모든 데이터를 단일 클러스터에 넣은 뒤 각 클러스터를 2개의 클러스터로 재귀적으로 분할한다. N개의 항목을 2개 그룹으로 분할하는 방법은 2^{N - 1} - 1 개가 있기 때문에 최적의 분할을 계산하기는 어렵다. 한 휴리스틱으로는 최고 반경을 갖는 클러스터를 고른 뒤 이를 K = 2일 때의 K-평균 알고리즘으로 분할하는 것이다. 이를 이분 K-평균 알고리즘이라 하며, 이를 목표하는 클러스터 수까지 반복한다. 이는 일반 K-평균의 대안으로 쓰일 수 있으나 계층적 클러스터링을 유도한다.

다른 방법은 비유사도 그래프의 최소 신장 트리를 만들고 비유사도가 가장 큰 연결을 깨는 방식으로 새 클러스터를 만드는 것이다.

또 다른 방법은 비유사도 분석으로 불리며, 단일 클러스터로부터 시작한 뒤 그룹의 각 원소에 대해 평균 비유사도 d_{i, G} = \frac{1}{n_{G}} \sum_{j \in G} d_{i, j}를 정의한 뒤, 이것이 가장 큰 오브젝트를 혼자만의 클러스터 H로 분리하는 것이다. 그 뒤 G에서 H로 특정 중지 조건을 만족시킬 때까지 오브젝트를 이동한다. 구체적으로, 이동시킬 오브젝트는 각 i \in G에 대한 평균 비유사도를 최대화시키면서 j \in H에 대한 평균 비유사도를 최소화시키는 오브젝트로 선택된다. 이 평균 비유사도의 차가 음수가 될 때까지 오브젝트를 이동시킨다. 이렇게 하면 G가 G, H 2개의 클러스터로 분할된다. 이는 재귀적으로 시행될 수 있다.

분리적 클러스터링은 응집적 클러스터링보다 덜 쓰이지만, O(N)의 시간이 걸리므로 더 빠르다. 또한, 분할 결정이 데이터 전부에 대한 관점으로 결정될 수 있다.

25.5.3. Choosing the number of clusters

최적 클러스터의 수를 결정하기는 어렵다. 베이지안식 접근법을 쓸 수 있다.

25.5.4. Bayesian hierarchical clustering

계층적 클러스터링과 비슷한 결과를 내는 확률적 모델을 만들 수 있는데 그 중 하나의 방법은 베이지안 계층적 클러스터링이다. 이는 상향식 응집적 클러스터링과 알고리즘적으로 대단히 비슷하지만 결합할 클러스터링을 결정하는 데 있어 베이지안적 가설 검증을 한다. 이는 디리클레 과정 혼합 분포에서 추론하는 데 쓰이는 계산 과정과 밀접한 연관이 있다. 또한, 입력은 비유사도 행렬이 아니라 데이터 행렬이 쓰인다.

25.5.4.1. The algorithm

\mathcal{D} = \{\mathbf{x}_{1}, \cdots, \mathbf{x}_{N}\}을 데이터라고 하고, \mathcal{D}_{i}를 부분 트리 T_{i}의 리프 노드에 존재하는 데이터들이라 하자. 각 단계마다, 트리 T_{i}, T_{j}를 비교해 새 트리로 결합시킬지를 결정한다. \mathcal{D}_{ij}를 병합된 데이터, M_{ij} = 1를 결합시킬지를 결정하는 지시변수라 할 때 결합 확률은 다음과 같다.

r_{ij} = \frac{p(\mathcal{D}_{ij} | M_{ij} = 1)p(M_{ij} = 1)}{p(\mathcal{D}_{ij} | T_{ij})}

p(\mathcal{D}_{ij} | T_{ij}) = p(\mathcal{D}_{ij} | M_{ij} = 1)p(M_{ij} = 1) + p(\mathcal{D}_{ij} | M_{ij} = 0)p(M_{ij} = 0)

이 때 p(M_{ij} = 1)은 결합시킬지 여부에 대한 사전확률이다. M_{ij} = 1이면 \mathcal{D}_{ij}는 같은 모델로부터 딸려나오므로 p(\mathcal{D}_{ij} | M_{ij} = 1) = \int [\prod_{\mathbf{x}_{n} \in \mathcal{D}_{ij}} p(\mathbf{x}_{n} | \mathbf{\theta})] p(\mathbf{\theta} | \lambda) d \mathbf{\theta}이 된다. M_{ij} = 0이면 \mathcal{D}_{ij}는 다른 모델로부터 딸려나오므로 p(\mathcal{D}_{ij} | M_{ij} = 0) = p(\mathcal{D}_{i} | T_{i}) p(\mathcal{D}_{j} | T_{j})이 된다. r_{ij} < 0.5라면 병합을 중지시킨다.

25.5.4.2. The connection between Dirichlet process mixture models

베이지안 계층적 클러스터링과 디리클레 과정 혼합 모델의 관계는 무엇일까? 디리클레 혼합 과정 모델에서의 주변가능도는 다음과 같다.

p(\mathcal{D}_{k}) = \sum_{v \in \mathcal{V}} p(v) p(\mathcal{D}_{v})

p(v) = \frac{\Gamma(\alpha) \alpha^{m_{v}} \prod_{l=1}^{m_{v}} \Gamma(n_{l, v}) }{\Gamma(n_{k} + \alpha)}

p(\mathcal{D}_{v}) = \prod_{l=1}^{m_{v}} p(\mathcal{D}_{l, v})

이 때 \mathcal{V}\mathcal{D}_{k}에서의 가능한 분할 전부의 집합, p(v)는 분할 v의 확률, m_{v}는 분할 v 내의 클러스터 수, n_{l, v}는 분할 v 내 클러스터 l의 크기, \mathcal{D}_{l, v}은 분할 v 내 클러스터 l, n_{k}\mathcal{D}_{k}의 크기이다. 이 때 p(\mathcal{D}_{k} | T_{k})은 베이지안 계층적 클러스터링 알고리즘으로 계산했을 때 위의 p(\mathcal{D}_{k})와 비슷하게 계산되지만, T_{k}와 일관적인 분할에 대해서만 합을 계산한다는 차이점이 있다. 이 방법으로, 베이지안 계층적 클러스터링 알고리즘을 통해 디리클레 과정 혼합 모델로부터의 데이터에 대한 주변가능도의 하한을 구할 수 있다. 또한, 전체 알고리즘을 각 단계마다 탐욕적 알고리즘을 적용하는 것으로 생각할 수도 있다.

이제 각 노드 k에 대해 \pi_{k} = p(M_{k} = 1)을 계산해야 하는데, 이는 \mathcal{D}_{k}내 하나의 클러스터가 디리클레 과정 혼합 모델로부터 올 사건의 \mathcal{D}_{k}의 다른 클러스터들이 현재 트리에 대해 일관적일 사건에 대한 상대적 확률로 계산할 수 있다. 풀어 쓰자면, 각 리프 i에 대해 d_{i} = \alpha, \pi_{i} = 1로 초기화하고, 트리의 내부 노드 k 각각에 대해 d_{k} = \alpha \Gamma(n_{k}) + d_{i}d_{j}, \pi_{k} = \frac{\alpha \Gamma(n_{k})}{d_{k}}을 계산하면 된다. (i, j는 k의 두 자식 노드)

25.5.4.3. Learning the hyper-parameters

모델의 자유 매개변수는 \alpha, \lambda 2개이다. (\lambda\mathbf{\theta}의 사전분포의 매개변수). 트리를 통해 \frac{\partial p(\mathcal{D}_{k} | T_{k})}{\partial \lambda} 꼴의 경사를 역전파함으로써 초매개변수에 대한 실측 베이즈 추정을 수행할 수 있음이 알려져 있다.

25.5.4.4. Experimental results

베이지안 계층적 클러스터링은 전통적인 응집적 클러스터링보다 훨씬 좋은 성능을 보인다.

25.6. Clustering datapoints and features

각 데이터가 복수의 특성으로 나타내어질 때는 어떻게 될까?

25.6.1. Biclustering

행과 열을 클러스터링하는 것은 바이클러스터링 또는 코클러스터링으로 알려져 있다. 이는 생물정보학에서 넓게 쓰인다. 또한, 협업 필터링에 쓰이기도 한다. 발상은 각 열과 행을 잠재 지시변수 r_{i}, c_{j}에 연관시킨 뒤 데이터 각각이 표본과 특성에 대해 동일하게 독립적으로 분포되어 있다는 가정을 하는 것이다. 즉 다음 가정을 한다.

p(\mathbf{x} | \mathbf{r}, \mathbf{c}, \mathbf{\theta}) = \prod_{i} \prod_{j} p(x_{ij} | r_{i}, c_{j}, \mathbf{\theta}) = p(x_{ij} | \mathbf{\theta}_{r_{i}, c_{j}})

열과 행에 대해 유한 개의 클러스터를 쓰는 대신 디리클레 과정을 쓸 수도 있다. 이는 붕괴 깁스 샘플링으로 피팅할 수 있다.

25.6.2. Multi-view clustering

바이클러스터링의 문제점은 각 오브젝트가 하나의 클러스터에만 속할 수 있다는 점이다. 직관적으로 하나의 오브젝트는 여러 역할을 가질 수 있으므로 어떤 특성을 조합하냐에 따라서 다른 클러스터에 속할 수도 있다. 이를 해결하는 방법으로 크로스캣, 또는 멀티-클러스트법이 있다. 이는 각 열들을 V개의 관점으로 나누는 것이다. 이 때 디리클레 과정 사전분포 p(c)을 사용한다. 이후 열들의 각 분할 v에 대해서 행들을 다시 디리클레 과정을 통해 분할한다. 행들과 열들을 분할했으면 이제 데이터를 생성한다. 이를 표현하자면 다음과 같다.

p(\mathbf{c}, \mathbf{r}, \mathcal{D}) = p(\mathbf{c}) p(\mathbf{r} | \mathbf{c}) p(\mathcal{D} | \mathbf{r}, \mathbf{c})

p(\mathbf{c}) = \mathrm{DP}(\mathbf{c} | \alpha)

p(\mathbf{r} | \mathbf{c}) = \prod_{v=1}^{V(\mathbf{c})} \mathrm{DP}(\mathbf{r}_{v} | \beta)

p(\mathcal{D} | \mathbf{r}, \mathbf{c}) = \prod_{v=1}^{V(\mathbf{c})} \prod_{j : c_{j} = v} [\prod_{k=1}^{K(\mathbf{r}_{v})} \int \prod_{i : r_{iv} = k} p(x_{ij} | \mathbf{\theta}_{jk}) p(\mathbf{\theta}_{jk}) d \mathbf{\theta}_{jk}   ]

데이터가 이진 데이터이면 \mathbf{\theta}_{jk}에 대해 \mathrm{Beta}(\gamma, \gamma) 사전분포를 써서 가능도를 다음과 같이 간소화시킬 수 있다.

p(\mathcal{D} | \mathbf{r}, \mathbf{c}, \gamma) = \prod_{v=1}^{V(\mathbf{c})} \prod_{j : c_{j} = v} \prod_{k=1}^{K(\mathbf{r}_{v})} \frac{\mathrm{Beta}(n_{j, k, v} + \gamma, \bar{n}_{j, k, v} + \gamma)}{\mathrm{Beta}(\gamma, \gamma)} (n_{j, k, v} = \sum_{i : r_{i, v} = k} \mathbf{1}_{x_{ij} = 1}, \bar{n}_{j, k, v} = \sum_{i : r_{i, v} = k} \mathbf{1}_{x_{ij} = 0})

이는 베타-베르누이, 가우시안-감마-가우시안 모델 등으로 잘 확장된다. 최대사후확률추정에 대한 근사는 추계적 탐색을 통해 이루어지고, 근사 추론은 변분 베이즈나 깁스 샘플링으로 이루어진다. 가능도에 대한 초매개변수 \gamma는 비정보적으로 세팅된다. 하지만 결과는 디리클레 과정 사전분포의 선택에 더 의존하고는 한다. 이에 대처하는 더 강건한 방법은 메트로폴리스 헤이스팅스법이다.

이 방법을 표준적인 무한 혼합 모델과 비교할 수 있다. 표준 모델은 N \to \infty일 때 고정 크기 벡터에 대한 임의의 밀도함수를 모델링할 수 있지만, D \to \infty에 대해서는 대처할 수 없다. 관계 없거나 노이즈에 속하거나 불필요한 특성을 제어할 수 없기 때문이다. 반면에 이 크로스캣 모델은 관계 없는 특성에 대해 더 강건하다. 분할해서 분리한 뒤 연관 특성들만 가지고 클러스터링을 하면 되기 때문이다. 또한, 이는 별도의 배경 모델을 필요로 하지 않는다.

요점 정리

  • 클러스터링 : 비슷한 오브젝트를 그룹화하는 과정.
  • 디리클레 과정 혼합 모델 : 무한 혼합 모델로서 클러스터 수 K에 대한 사전 지식 없이 클러스터링을 유동적으로 수행함.
  • 친화도 전파 : 유사도 행렬을 입력으로 받을 때 데이터 각각에 대해 순환 믿음 전파를 응용해 클러스터링을 수행함.
  • 스펙트럼 클러스터링 : 클러스터링 벡터를 실변수로 바꾼 뒤 고유값 문제로 변형해 K-평균 알고리즘을 적용해 클러스터링함.
  • 계층적 클러스터링 : 계층화된 클러스터링을 적용하며, 상향식과 하향식 방법이 있음.
  • 데이터에 복수의 특성을 연관지어 클러스터링할 수 있음.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중