のんびり読書日記

日々の記録をつらつらと

NMF(Non-negative Matrix Factorization)を試してみた

先週は言語処理学会の全国大会に参加してきたのですが、チュートリアル「推薦システム -機械学習の視点から-」で紹介されていた行列分解に興味が湧いたので実装しようと奮闘中です。とりあえず行列いじりの練習に、手元の本に説明があるNMF(Non-negative matrix factorization)を実装してみました。参考にした書籍は「Rで学ぶクラスタ解析」と「集合知プログラミング」です。

NMFはn×mの行列をn×k, k×mの2行列の積に分解する手法で、分解後の行列はクラスタリング結果としても利用できます。例えば文書の特徴をbag-of-wordsで表した文書-単語行列を分解すると、文書の各クラスタへの重要度を表す行列と、特徴語の各クラスタへの重要度を表す行列が出力されます。より詳しくは前述の書籍をご参照下さい。

作成したコードは以下の場所に置いてあります(汎用性のないコードだなぁ…)。行列演算部分はEigenを使ってみました。

ちなみに入力データはSparseMatrixに入れているのですが、分解後の行列やtemporaryの行列をDenseのMatrixにしているせいか、大きめのデータ(5万文書くらい)を入れると落ちてしまいます。メモリ不足が原因かな…?

実際に実行する時は以下のように(Eigenを事前にインストールしておく必要があります)。入力データは1行に1文書の特徴を持つタブ区切りテキストです。入力データは6x9の文書-特徴語行列なのですが、NMFでは1文書のデータを列ベクトルで表現するのが普通らしいので、入力を読み込んだ後に転置して9x6の特徴語-文書行列として処理しています。

% g++ -Wall -O3 nmf.cc -o nmf

% cat input.tsv         # 6x9の行列(6文書, 9種類の特徴)
阿佐田   J-POP       10   J-R&B       6   ロック  4
小島     ジャズ       8   レゲエ      9
古川     クラシック   4   ワールド    4
田村     ジャズ       9   メタル      2   レゲエ  6
青柳     J-POP        4   ロック      3   HIPHOP  3
三輪     クラシック   8   ロック      1

% ./nmf input.tsv 3 50  # 9x3, 3x6 の行列に分解
Reading input data
Factorizing input matrix
 loop: 10
 loop: 20
 loop: 30
 loop: 40
 loop: 50
Input matrix was factorized. ( V = W * H )
=== W matrix ===
J-POP   0.0004  0.4423  0.0000
J-R&B   0.0000  0.2320  0.0000
ロック  0.0521  0.1962  0.0000
ジャズ  0.0000  0.0001  0.5020
レゲエ  0.0000  0.0000  0.4493
クラシック      0.5053  0.0000  0.0000
ワールド        0.0051  0.0017  0.0010
メタル  0.0036  0.0047  0.0013
HIPHOP  0.0059  0.0076  0.0001

=== H matrix (transposed) ===
阿佐田  0.0000  0.5881  0.0000
小島    0.0000  0.0000  0.4753
古川    0.2006  0.0000  0.0002
田村    0.0006  0.0008  0.4256
青柳    0.0088  0.2118  0.0000
三輪    0.4024  0.0000  0.0000

ここではクラス多数を3にして行列の分解を行いました。分解後の1つ目の行列は特徴語の各クラスタでの重要度を表し、2つ目の行列は文書の各クラスタでの重要度を表します。一番重要度の高いクラスタがその文書が属しているクラスタと考えられるので、各クラスタは「阿佐田、青柳」「小島、田村」「古川、三輪」のように分かれていることが分かります。

ちなみにbayonでクラスタリングするとこんな感じで、クラスタの構成は同じになりますね。

% bayon -n 3 input.tsv
1       田村    小島
2       阿佐田  青柳
3       三輪    古川

まだEigenの使い方がよく分かってないとか、そもそも線形代数が苦手でどうしようという感じなのですが、とりあえずウォーミングアップは済んだので、次はもうちょい突っ込んだもの作りたいですね。