NMF(Non-negative Matrix Factorization)とK-meansが等価であるという話を聞いたので参考論文を基にメモ書き程度に残しておきます。
なお、本稿では簡単な対称NMFについてしか記述しないので、それ以上を求める方は参考論文を辿って下さい。
NMF(Non-negative Matrix Factorization)
各成分が非負であるデータ行列$X=[\boldsymbol{x}_1 , ..., \boldsymbol{x}_n] \in \mathbb{R}^{p \times n}$であるとする(画像の各ピクセル値がデータ数分の行列となっている状態)。NMFではSVDやPCA等と異なり、この行列を非負行列で近似する。要するに下のようになる。
\begin{equation*}
X \simeq F G^{\rm T}
\end{equation*}
- $F$ : $[ \boldsymbol{f}_1 , \ldots, \boldsymbol{f}_n] \in \mathbb{R}^{p \times k}$, 非負行列
- $G$ : $[ \boldsymbol{g}_1 , \ldots, \boldsymbol{g}_n] \in \mathbb{R}^{n \times k}$, 非負行列
- $k$ : 事前に定められたパラメータ
K-means
K-meansではK個のクラスタを作ることを目的とするが、各クラスを$C_k$とすれば、その平均$\boldsymbol{m}_k$は次のようになる。
\begin{equation*}
\boldsymbol{m}_k = \sum_{i \in C_k} \boldsymbol{x}_i
\end{equation*}
K-meansで最小化したいものは各点からクラスの平均までの距離の和であるので以下のようなコスト関数$J_K$になる。
\begin{align*}
J_K &= \sum_{k=1}^K \sum_{i \in C_k} || \boldsymbol{x}_i - \boldsymbol{m}_k ||^2 \\
&= \sum_{i=1}^N || \boldsymbol{x}_i ||^2 - \sum_{k=1}^K \frac{1}{n_k} \sum_{i,j=1}^N \boldsymbol{x}_i^{\rm T} \boldsymbol{x}_j \tag{1}
\end{align*}
である。ここで次のような行列$H$を導入する。
\begin{align*}
H &= [\boldsymbol{h}_1, \ldots, \boldsymbol{h}_K] \in \mathbb{R}^{N \times K} \\
h_k &= \frac{1}{n_k^{1/2}} [0, \ldots, 0, 1, \ldots, 1, 0, \ldots, 0]^{\rm T} \\
n_k &= |C_k|
\end{align*}
なお、$\boldsymbol{h}_k $の要素の$1$の個数は$n_k$個である。この$H$は$H^{\rm T} H = I$を満たす。これを用いれば式(1)は次のように変換できる。
\begin{align*}
J_K &= {\rm Tr} (X^{\rm T} X) - {\rm Tr} (H^{\rm T} X^{\rm T} X H) \\
&= {\rm Tr} (W) - {\rm Tr} (H^{\rm T} W H) \\
&= - {\rm Tr} (H^{\rm T} W H) + C \\
W &= X^{\rm T} X
\end{align*}
$C$は$H$に依存しない項である。また、$W$は類似度行列である。
以上の式より$J_K$の最小化は次のように変形される。
\begin{equation*}
\max_{H^{\rm T} H = I, H \geq 0} {\rm Tr} (H^{\rm T} W H) \tag{2}
\end{equation*}
さらにこれは次のように変換できる。
\begin{align*}
H^{\ast} &= \text{argmax}_{H^{\rm T} H = I, H \geq 0} {\rm Tr} (H^{\rm T} W H) \\
&= \text{argmin}_{H^{\rm T} H = I, H \geq 0} -2 {\rm Tr} (H^{\rm T} W H) \\
&= \text{argmin}_{H^{\rm T} H = I, H \geq 0} \{ ||W||^2 -2 {\rm Tr} (H^{\rm T} W H) + ||H^{\rm T} H||^2 \} \\
&= \text{argmin}_{H^{\rm T} H = I, H \geq 0} ||W- H H^{\rm T}||^2 \tag{3}
\end{align*}
ノルムはフロベニウスノルムである。また、$||W||$が定数であること及び$||H^{\rm T} H||=K$であることを用いている。
類似度行列を
\begin{equation*}
W_{i,j} = \boldsymbol{\phi}^{\rm T} (\boldsymbol{x}_i) \boldsymbol{\phi} (\boldsymbol{x}_j)
\end{equation*}
のようにして、$x$を特徴空間に飛ばして分類するkernel K-meansの場合も同様である。
式(2)に示されるようにK-meansでは$H$に直交性と非負性の2つの制約がある。後者を無視すれば$H$は$W$の固有値の上位いくつかで表現する問題に帰着し、前者を無視すればNMFとなる。
対称NMF
対称NMFでは行列$W$を$H H^{\rm T}$のように分解して近似することを考える。ただし$H$は非負行列である。この問題は以下のように定式化され、コスト関数$J$を最小化する問題になる。
\min_{H \geq 0} J = \min_{H \geq 0} ||W - H H^{\rm T}||^2
これはまさに上のK-means(式(3))から直交性の条件を除いたものである。対称NMFでは直交性はないが、依然として直交性を保ったまま近似しようとする。これは上の式に$\min_{H \geq 0} ||H^{\rm T} H||^2$という項がついているためである。この項は次のように分解される。
\begin{align*}
||H^{\rm T} H||^2 &= ||H^{\rm T} H - I||^2 + 2 ||H||^2 - {\rm Tr} (I) \\
&= ||H^{\rm T} H - I||^2 + 2 {\rm Tr}(H H^{\rm T}) - {\rm Tr} (I) \tag{4}
\end{align*}
$W \simeq H H^{\rm T}$であるから、式(4)2項目も定数と扱え$\min_{H \geq 0}||H^{\rm T} H - I||^2$のようになり、直交性の条件がなくとも直交に近づけようという項が現れていることがわかる。
純粋なK-meansでは直交性のため、$H$の各行でゼロでない成分は1つしか存在しない、つまり各データ点は1つのクラスタしか属さない(帰属度1、ハードクラスタリング)。一方上述のようにNMFで直交性を近似した場合そのようなことは起こらず、複数のクラスタに属しうる(帰属度1以下、ソフトクラスタリング)。
実際にクラスタリングを行う例に関しては参考論文の図を参考にしてください。実際にソフトクラスタリングされていることがわかります。
おわりに
K-meansとNMFが関連しているとは意外でした。
参考論文
Ding, Chris, Xiaofeng He, and Horst D. Simon. "On the equivalence of nonnegative matrix factorization and spectral clustering." Proceedings of the 2005 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2005.