2005 Ding@SIAM
abst:
現在の非負値行列因子分解（NMF）は、$ X = FG^T型を扱っています。
本稿では、対称型$ W = HH^Tおよび重み付き$ W = HSH^TへのNMFの体系的な解析と拡張を示します。
(1) 対称型$ W = HH^Tは、カーネル K-meansクラスタリングおよびラプラシアンに基づいたスペクトルクラスタリングと同等である
(2) 非対称型分解$ X = FG^Tは、２部グラフの行と列の同時クラスタリングと同等である を示します。これらの対称型NMFを計算するためのアルゴリズムを示します。
1. Intro
データ行列の標準的な因子分解では、主成分分析（PCA）で広く用いられている特異値分解（SVD）が用いられます。
しかし、画像やテキストなど多くのデータセットでは、元のデータ行列は非負値です。
SVDのような因子分解は負の値を含むため、解釈が困難になります。
非負値行列因子分解（NMF）7, 8は、標準的なPCA/SVDベースの因子分解に比べて多くの利点があります。 SVDベースの因子分解では行列因子の負の値によって相殺が発生しますが、NMFの非負性により、因子には元のデータ（画像）の一貫性のある部分が含まれることが保証されます。
NMFはXを2つの非負行列に分解する。
$ X \approx FG^\top
因数分解は最小二乗法によって得られる。NMF計算手法のさらなる発展に関する多くの研究12, 11, 10やテキストマイニングの応用に関する研究が行われている。本稿では、NMFをデータクラスタリングの観点から考察する。NMFとベクトル量子化の関係、特にその差異は、LeeとSeung 7によってNMFの動機付けとして議論されている。NMFのクラスタリング的側面は、14, 10でも研究されている。本稿では、 NMFの体系的な分析と拡張を提供する
NMFがカーネルK平均法クラスタリングやラプラシアンベースのスペクトルクラスタリングと同等であることを示す。
(1) 対称型NMF
$ W \approx HH^\top
ここで、Wはペアワイズ類似度、すなわちカーネルを含みます。これはK平均法型クラスタリングおよびラプラシアンベースのスペクトルクラスタリングと同等であることを示します。
(2）これを２部グラフのクラスタリング問題に一般化する。つまり、長方形データ行列の行と列を同時にクラスタリングする。その結果、標準的なNMFが得られる。
(3) 重み付きNMFに拡張する:
$ W \approx HSH^\top
(4) これらの因数分解を計算するアルゴリズムを導出する。
全体として、私たちの研究は、非負行列の分割とスペクトルのクラスタリングに関する包括的な考察を提供します。
2. Kernel K-means clustering and Symmetric NMF
K平均法クラスタリングは、最も広く用いられているクラスタリング手法の一つです。
ここではまず、スペクトル緩和法(spectoral relaxation) 15, 3 を用いたK平均法について簡単に紹介します。これにより、必要な背景情報と表記法が示され、§2.1で述べる非負値行列因子分解法への道が開かれます。 K平均法は、クラスターの重心であるK個のプロトタイプを用いてデータを特徴づけます。目的関数は、二乗誤差の和を最小化することです。
eq. 4
$ J_K = \sum \sum || x_i - m_k ||^2 = ...
...
クラスタリングの解は、K 個の非負指標ベクトルによって表されます。
...
ペアワイズ類似度行列$ W = X^\top Xは、標準的な内積線形カーネル行列です。これは他の任意のカーネルに拡張できます。これは、高次元空間への非線形変換（写像）を用いて行われます。
3. Bipartite graph K -means clustering and NMF
多くのデータセットは、テキストマイニングにおける単語-文書連想行列やDNA遺伝子発現プロファイルなど、矩形非負行列の形式をとっています。これらの種類のデータセットは、２部グラフで簡便に表現できます。 隣接行列$ Bは、行オブジェクトと列オブジェクト間の連想を格納し、これが入力データ行列B = Xとなります。
上記のカーネルK平均法は、２部グラフにも簡単に拡張できる。k行目のクラスターの指標を$ f_ k とします。
$ f_k は式(6)の$ h_k と同じ形を持ちます。
これらをまとめると、指標行列$ F = (f_1 , ··· , f_k )が得られます。
同様に、列クラスターの指標行列$ G = (g_1 , ··· , g_k )を定義します。