k-means 클러스터링의 선형대수학적 해석

k-means 클러스터링을 선형대수학적으로 해석해본다.
우선 k-means 클러스터링에 대해 간단히 짚고 넘어가자.

기존

k-means 클러스터링은 은 각 클러스터에 대해 centroid와 sample 간 거리들의 합을 최소화하는 방식으로 학습하며 k-means 클러스터링의 목적함수는 일반적으로 다음과 같이 정의된다.

$$ \sum^k_{i=1}{\sum_{x \in S_i}{||x – \mu_i||^2}} $$

이 때, 각 클러스터의 centroid는 다음과 같이 정의된다.

$$ \mu_i = \frac{1}{|S_i|}{\sum_{x \in S_i}{x}} $$

위의 로직을 바탕으로 k-means 클러스터링은 다음의 순서로 진행된다.
1. 초기 데이터를 k개의 클러스터로 무작위 배정
2. 클러스터 별 centroid 계산
3. 각 데이터별로 가장 가까운 centroid의 클러스터를 배정
4. 클러스터 변화가 없을 때까지 2-3 반복

선형대수학적 해석

기존 알고리즘을 토대로 k-means 클러스터링은 centroid와 membership을 잘 정의하는 과정이라 요약할 수 있다.
이 때 데이터를 f x n 행렬 X로, centroid와 membership을 각각 f x k과 k x n인 행렬 C와 M으로 정의하자.
행렬 C의 k개 열벡터는 각각 f개의 feature를 가지며, 행렬 M의 n개 열벡터는 하나의 원소만 1이고 나머지는 0인 벡터이다.
그 결과 k-means 클러스터링의 목적함수는 다음과 같이 정의할 수 있다.

$$ ||X – CM||^2_F$$

정의에 의해 행렬 CM은 각 데이터가 속한 클러스터의 centroid로 구성된 f x n 행렬이 되며 이는 곧 기존 k-means 클러스터링 목적함수와 동일한 값이 된다.
이 때, 데이터(X)와 추정(CM) 간 제곱합 오차를 계산하기 위해 frobenius norm을 사용한다.

이제 기존 알고리즘을 다시 한 번 생각해보자.
데이터들의 클러스터가 정해졌을 때 centroid가 결정된다.
즉, membership이 고정되었을 때 centroid가 최적해로 결정된다.
이는 목적함수의 최적화가 주어진 M에 대해 목적함수를 최소로 하는 C를 계산하는 것임을 말한다.

이 때, 목적함수는 C에 대한 2차식이므로 convex인 것을 알 수 있다.
즉, 목적함수의 최적화를 위해 MLE(Maximum Likelihood Estimation)를 사용하면 최적해 C가 결정된다는 것이다.

MLE를 계산하기 전에 먼저 목적함수를 미분하기 편한 형태로 고쳐 쓸 것이다.
하지만 그 전에 다음의 선형대수학적 성질들을 살펴보자.

$$
\begin{align*}
\frac{\partial{(X^T A)}}{\partial{X}} &= \frac{\partial{(A^T X)}}{\partial{X}} = A \\
\frac{\partial{(AX)}}{\partial{X}} &= A \\
\frac{\partial{(X^T AX)}}{\partial{X}} &= (A+A^T)X \\
\frac{\partial{(X^T X)}}{\partial{X}} &= 2X \\
\end{align*}
$$

$$
\begin{align*}
tr(X) &= tr(X^T) \\
tr(ABC) &= tr(BCA) = tr(CAB) \neq tr(CBA) \\
tr(A^T B) &= tr(A B^T) = tr(B^T A) = tr(B A^T) \\
\frac{\partial{(tr(XA))}}{\partial{X}} &= A^T \\
\frac{\partial{(tr(XA))}}{\partial{X^T}} &= A \\
\frac{\partial{(tr(AX^T))}}{\partial{X}} &= A \\
\frac{\partial{(tr(X^T AX))}}{\partial{X}} &= X(A+A^T)
\end{align*}
$$

이제 이 성질들을 이용해 목적함수를 풀어보자.

$$
\begin{align*}
||X – CM||^2_F &= tr(X^T X) – tr(X^T CM) – tr(M^T C^T X) + tr(MC^T CM^T) \\
&= tr(X^T X) – 2tr(X^T CM) + tr(MC^T CM^T)
\end{align*}
$$

이제 주어진 M을 바탕으로 C에 대해 편미분하면

$$
\begin{align*}
\frac{\partial}{\partial{C}}||X – CM||^2_F &= \frac{\partial}{\partial{C}} (tr(X^T X) – 2tr(X^T CM) + tr(M^T C^T CM)) \\
&= -2 \frac{\partial}{\partial{C}} tr(X^T CM) + \frac{\partial}{\partial{C}} tr(M^T C^T CM) \\
&= -2 \frac{\partial}{\partial{C}} tr(CMX^T) + \frac{\partial}{\partial{C}} tr(C^T CMM^T) \\
&= -2 (MX^T)^T + 2CMM^T \\
&= -2XM^T + 2CMM^T
\end{align*}
$$

이고, 미분값이 0이 되는 점을 찾으면

$$
\begin{align*}
-2XM^T + 2CMM^T &= 0 \\
XM^T &= CMM^T \\
C &= XM^T (MM^T)^{-1}
\end{align*}
$$

이므로 목적함수는 다음과 같이 정리된다.

$$ ||X – CM||^2_F = ||X – XM^T (MM^T)^{-1}M||^2_F $$

이제 k-means 클러스터링은 위의 목적함수를 최소화하는 M을 찾는 문제가 된다.

간소화

위에서 구한 목적함수를 전개하여 식을 간소화시켜본다.

$$
\begin{align*}
||X – CM||^2_F &= ||X – XM^T (MM^T)^{-1}M||^2_F \\
&= tr(X^T X) – 2tr(X^T XM^T (MM^T)^{-1}M) + tr(M^T (MM^T)^{-1}M X^T XM^T (MM^T)^{-1}M) \\
&= tr(X^T X) – 2tr(X^T XM^T (MM^T)^{-1}M) + tr((MM^T)^{-1}M X^T XM^T) \\
&= tr(X^T X) – 2tr(X^T XM^T (MM^T)^{-1}M) + tr(X^T XM^T (MM^T)^{-1}M) \\
&= tr(X^T X) – tr(X^T XM^T (MM^T)^{-1}M)
\end{align*}
$$

그런데 위의 두 번째 term에서 tr(M^T (MM^T)^{-1}M) 부분을 살펴보자.
M은 원소가 0 또는 1인 k x n의 멤버십 행렬이며 모든 열벡터의 원소합이 1이 되는 행렬이다.
그러므로 M은 역행렬이 존재하지 않는 비정방행렬(non-square matrix)이며 직교행렬(orthogonal matrix)조차 아니다.
하지만 M은 멤버십 행렬이기에 MM^T는 k x k의 정방행렬(square matrix)이자 대각행렬이며 각 대각성분은 각 그룹에 속한 원소(행렬 X의 열벡터)의 개수가 된다.
MM^T는 각 그룹에 대한 크기 정보를 의미하며 이에 대한 역행렬은 각 그룹별 크기에 대한 정규화 스케일러가 된다.

$$ (MM^T)^{-1} = \begin{Bmatrix} s_1^{-1} & & \\ & \ddots & \\ & & s_k^{-1} \end{Bmatrix} $$

이 때, s_k는 군집 k의 원소 개수이다.

(MM^T)^{-1} 이 스케일링 역할을 하기에 이를 토대로 식을 재구성할 수 있다.
k x n 행렬 S를 다음과 같이 정의하자.

$$ S = (MM^T)^{-\frac{1}{2}} M $$

그러므로

$$ S^T = M^T (MM^T)^{-\frac{1}{2}} $$

이며 자연스레 다음이 성립한다.

$$
\begin{align*}
||X – CM||^2_F &= tr(X^T X) – tr(X^T XM^T (MM^T)^{-1}M) \\
&= tr(X^T X) – tr(X^T XS^T S) \\
&= tr(X^T X) – tr(SX^T XS^T)
\end{align*}
$$

참고로 tr(M^T (MM^T)^{-1}M) 에서 (MM^T)^{-1} 전후의 M^T M 는 무엇을 의미할까?
이 gram 행렬은 주어진 데이터들(행렬 X의 열벡터) 간 소속 정보를 알려주는 n x n 행렬이다.
행렬 인덱스 i, j에 대해 동일한 군집에 속한 데이터 x_i, x_j들은 모두 1로, 나머지는 0으로 표시된다.
그 결과 특정 데이터를 기준으로 같은 군집에 속한 다른 데이터들을 인덱싱할 수 있다.

정리

이제 k-means 클러스터링은 주어진 X에 대해 아래의 목적함수를 최소화하는 멤버십 행렬 S를 찾는 문제가 되었다.

$$ ||X – CM||^2_F = tr(X^T X) – tr(SX^T XS^T)$$

위 식을 최소화하는 것은 곧 tr(SX^T XS^T)을 최대화하는 것을 의미하며 이 trace값은 Ky Fan 정리[3][4][5]에 의해 X^T X의 고윳값을 k번째까지 더한 것이 된다.

$$ \max{tr(Q^T X Q)} = \sum_{i=1}^{k} \lambda_i $$

Ky Fan Maximum Principle

즉, k-means 클러스터링의 목적함수 최솟값(WCSS: Within Cluster Sum of Squares)은 주어진 데이터에 대해 자명하게 결정된다.
하지만 k-means 클러스터링의 최종목적은 목적함수가 최소화되었을 때 각 데이터들이 어떤 그룹에 속하는지를 찾는 것이다.
Ky Fan 정리는 이에 대한 해답을 알려주지 않기 때문에 tr(SX^T XS^T)에서 S^T S = I가 되는 적절한 S를 찾는 것 말고는 방법이 없음을 알 수 있다.
그러므로 k-means 클러스터링의 최적해를 찾는 것은 이미 알려진 것처럼 NP-hard임을 다시 한 번 알 수 있다.

그리고 최적 WCSS는 데이터에 대한 공분산 행렬의 k개 고윳값을 더한 값으로 자명하게 결정되는데 이 과정에서 eigen decomposition이 필요하며 이에 따라 최적 WCSS를 구하는 것은 O(n^2)임을 자연스럽게 알 수 있다.

k-means clustering의 최적해가 아니라 최적 WCSS가 필요한 경우에는 기분 좋게 eigen-solver를 가져다 쓰면 될 것이다.
다만 시간복잡도를 주의해야 할 것이다.

참고자료

  1. Christian Bauckhage, “k-Means Clustering Is Matrix Factorization”, arXiv:1512.07548v1 [stat.ML], Dec. 2015. [arXiv]
  2. Hongyuan Zha et al., “Spectral relaxation for K-means clustering”, Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, MIT Press, Jan. 2001. [DL.ACM]
  3. Ky Fan, “On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations. 1”. Mathmatics, PNAS, Nov. 1949. [PNAS]
  4. Ky Fan, “Maximum Properties and Inequalities for the Eigenvalues of Completely Continuous Operators”, Mathmatics, PNAS, Nov. 1951. [PNAS]
  5. Achiya Dax, “Maximum Principles for Normal Matrices”, Advances in Linear Algebra & Matrix Theory, Scientific Research Publishing, 9, 73-81, Sep. 2019. [SRP]

댓글 남기기