NMFでMovieLensのレコメンドを実装する

前回の投稿( SVDでMovieLensのレコメンドを実装する - け日記 )に引き続き、今回はNMFで映画のレコメンドを実装します。

NMF

非負値行列因子分解(Non-negative Matrix Factorization: NMF)は、ある行列XをW・Hに近似的に分解する方法の一つです。その名の通り、各行列の要素は全て0以上となります。

SVDなどの行列分解では、負の値が現れることがあります。
しかし、実世界で使われる値(画素、頻度、評価値など)の多くは非負値で、分解した結果に解釈を与えるなど非負の性質を保ちたいケースもあります(負の画素値などは存在しませんし)。そうした場合にNMFが使われるようです。

NMFでは、M×Nの行列Xを、N×kの行列Wとk×Mの行列Hに分解します。kはM,Nよりも小さな値が使われます。

$X \approx W \cdot H$

未知のWとHを求めるために、Xとの距離を定義します。
ここでは一番直感的なフロベニウスノルムを使います。

$D= || X-WH ||^2=\sum^{M}_{i=1}\sum^{N}_{j=1}(X_{ij}-(WH)_{ij})^2$

学習では、この距離(つまり誤差)が小さくなるように、HとWを更新します。

$H_{n+1} \leftarrow H_n \frac{W^T_n V_n}{W^T_n W_n H_n}, W_{n+1} \leftarrow W_n \frac{V_n H^T_{n+1}}{W_n H_{n+1} H^T_{n+1}}$

上述以外にもいくつか距離の定義と更新式が提案されていますが、割愛します。こちらの方の投稿がよくまとまっています。

非負値行列因子分解（NMF : Non-negative Matrix Factorization）を改めてやり直してみた - Qiita

NMFを推薦システムに適用する

以下のように、5本の映画に対して、4人のユーザが5段階(1〜5)で評価した、というケースを想定します。
恣意的に選択しているのでそうなっているのですが、これら5本の映画にはロマンス要素とアニメーション要素の2つがあり、ユーザもこの2つのグループに分けられそうです(AとBはロマンス要素が強い映画、CとDはアニメーション要素が強い映画をそれぞれ好んでいる)。

f:id:ohke:20171223190013p:plain

この表は5×4の行列(ここではX)で表現できます。なお、未評価となっている要素は0で埋めています。

$X=\left( \begin{matrix} 5 & 5 & 0 & 3 \\ 4 & 4 & 0 & 0 \\ 0 & 3 & 4 & 0 \\ 0 & 1 & 4 & 5 \\ 1 & 0 & 5 & 4 \end{matrix} \right)$

XをNMFでWとHに分解します。ここではk=2としています。

$X \approx W \cdot H=\left( \begin{matrix} 2.7 & 0.3 \\ 2.1 & 0.0 \\ 0.6 & 0.8 \\ 0.2 & 1.6 \\ 0.1 & 1.6 \end{matrix} \right) \left( \begin{matrix} 1.8 & 1.9 & 0.0 & 0.4 \\ 0.0 & 0.4 & 3.1 & 2.5 \end{matrix} \right) =\left( \begin{matrix} 4.9 & 5.3 & 0.9 & 1.9 \\ 3.8 & 4.0 & 0.0 & 0.9 \\ 1.1 & 1.5 & 2.4 & 2.2 \\ 0.3 & 0.9 & 4.8 & 4.1 \\ 0.2 & 0.8 & 4.9 & 4.1 \end{matrix} \right)$

分解されたWとHを見ると、映画の持つ要素やユーザの嗜好が反映された行列になっていることがわかります。

Wは映画数×kの行列
- 上2行(ローマの休日、タイタニック)は1列目、下2行(サマーウォーズ、AKIRA)は2列目の値がそれぞれ大きくなっており、映画の持つ要素が各列に反映されているように見えます
Hはk×ユーザ数の行列
- 左2列は1行目、右2列は2行目の値がそれぞれ大きくなっており、ユーザごとの嗜好がグループ分けされているように見えます
kによって集約された特徴と捉えることができます

レコメンドの実装

それではNMFを使ったレコメンドを実装します。データセットの準備とランキングの作成については前回の投稿( SVDでMovieLensのレコメンドを実装する - け日記 )とほぼ同じです。

データセットの準備

今回もMovieLens 100K Datasetを使います。

以下からダウンロードして、今回作成するPythonファイルと同じディレクトリに解凍しておきます。以前の投稿( word2vecでitem2vecを実装して映画を推薦する - け日記 )も参考にしてみてください。

MovieLens | GroupLens

評価値をnumpy行列にして持ちます。欠測値は0で補完しています。あわせてアイテムIDとタイトルの一覧もDataFrameにロードしておきます。

import numpy as np
import pandas as pd
import codecs


# 評価値を持つファイルはu.data。楽に行列化するために、まずはDataFrameでロードする
ratings = pd.read_csv('ml-100k/u.data', delimiter='\t', header=None).iloc[:, :3]
ratings.rename(columns={0: 'user_id', 1: 'item_id', 2: 'rating'}, inplace=True)
print('ratings.shape: {}'.format(ratings.shape)) # ratings.shape: (100000, 3)

# item_idを行、user_idを列とする1682×943の行列(欠測値は0埋め)
rating_matrix = ratings.pivot(index='item_id', columns='user_id', values='rating').fillna(0).as_matrix()
print('rating_matrix.shape: {}'.format(rating_matrix.shape)) # rating_matrix.shape: (1682, 943)

# pd.read_csvで読み込もうとすると文字コードエラーになるため、
# codecs.openでエラーを無視してファイルを読み込んだ後にDataFrameにする
with codecs.open('ml-100k/u.item', 'r', 'utf-8', errors='ignore') as f:
    item_df = pd.read_table(f, delimiter='|', header=None).ix[:, 0:1]
    item_df.rename(columns={0: 'item_id', 1: 'item_title'}, inplace=True)
    item_df.set_index('item_id', inplace=True)

items = pd.Series(item_df['item_title'])
print('items.shape: {}'.format(items.shape)) # items.shape: (1682, 1)

評価ランキングの予測と表示

指定したユーザに対して、未評価のアイテムの評価値を予測し、ランキングを返す関数を作ります。

未評価の映画については0で補完しており、また映画やユーザごとの評価値の平均なども考慮していないため、絶対値の予測精度は高くないと予想されます。そのため、ランキングにしています。

def predict_ranking(user_index, reducted_matrix, original_matrix, n):
    # 対象ユーザのSVD評価値
    reducted_vector = reducted_matrix[:, user_index]
    
    # 評価済みのアイテムの値は0にする
    filter_vector = original_matrix[:, user_index] == 0
    predicted_vector = reducted_vector * filter_vector

    # 上位n個のアイテムのインデックスと予測した評価値を返す
    return [(i, predicted_vector[i]) for i in np.argsort(predicted_vector)[::-1][:n]]


def print_ranking(user_ids, items, reducted_matrix):
    for user_id in user_ids:
        predicted_ranking = predict_ranking(user_id - 1, reducted_matrix, rating_matrix, 10)
        print('User: {}:'.format(user_id))
        for item_id, rating in predicted_ranking:
            # アイテムID, 映画タイトル, 予測した評価値を表示
            print('{}: {} [{}]'.format(item_id, items[item_id + 1], rating))

NMFによる行列分解

NMFによる行列分解ですが、sklearn.decomposition.NMFでお手軽にできますので、これを使います。

n_componentsにk=30を指定しています(前回のSVDと同じ)
initで初期値の設定方法を指定できます(今回はランダム)
MAE(絶対平均誤差)は約0.26
- XとWHの各要素は平均0.26の差がある、ということです

from sklearn.decomposition import NMF


def reduct_matrix_nmf(matrix, k):
    # NMFで分解
    model = NMF(n_components=k, init='random', random_state=1)
    w = model.fit_transform(matrix)
    h = model.components_
    
    return np.dot(w, h)


reducted_matrix_nmf = reduct_matrix_nmf(rating_matrix, k=30)

print('MAE: {}'.format(np.average(np.absolute(rating_matrix - reducted_matrix_nmf))))
# MAE: 0.25617962729902044

評価

それでは実際に推薦をさせてみます。

前回のSVDの結果と比較するために、前回と同じ2人のユーザ(ユーザID 267と868)を対象にランキングを生成しました。
概ねSVDの時と同じようなタイトルが得られましたが、負値を含まない分、予測評価値は全体的にNMFの方が高いことがわかります。

この2人は"Akira(1988)"と"Ghost in the Shell(Kokaku kidotai)(1995)"を5で評価しています(つまりSF+アニメーション好きです)

User: 267:
95: Terminator 2: Judgment Day (1991) [4.355731842820824]
10: Seven (Se7en) (1995) [3.5465670297733514]
231: Young Guns (1988) [3.3581447476132875]
78: Fugitive, The (1993) [3.3281046778126173]
153: Monty Python's Life of Brian (1979) [3.3028868626155874]
41: Clerks (1994) [3.1889273065852977]
172: Princess Bride, The (1987) [3.158916000181793]
356: One Flew Over the Cuckoo's Nest (1975) [3.1348566836324423]
0: Toy Story (1995) [3.128039827666597]
3: Get Shorty (1995) [2.8694586381163]

User: 868:
174: Brazil (1985) [4.270610564574103]
257: Contact (1997) [2.965456387373195]
356: One Flew Over the Cuckoo's Nest (1975) [2.914023120253882]
143: Die Hard (1988) [2.5656501189688483]
430: Highlander (1986) [2.5194608160565846]
195: Dead Poets Society (1989) [2.319622366933584]
21: Braveheart (1995) [2.2844329680205355]
41: Clerks (1994) [2.212755642335326]
379: Star Trek: Generations (1994) [2.212123031118453]
27: Apollo 13 (1995) [2.1517770562746565]