主成分分析とK-meansクラスタリングを使った協調フィルタリング

# レコメンドエンジンのAPI利用を考える
レコメンドエンジンはWEB APIなどで利用する機会が多く、精度を保ったまま素早く結果を返すことを要求されます。
そのため本記事では映画の視聴履歴に基づくレコメンド機能を実装する際に、主成分分析とK-meansクラスタリングを利用して、レコメンド精度をなるべく保ちつつ、APIの利用に耐えるように計算速度とのバランスを取ります。

今回利用するレコメンドのロジックは、選択した映画に対する各ユーザーの評価が似た映画を抽出してレコメンドするという単純なアイテムベース協調フィルタリングです。

#主成分分析とK-meansクラスタリング

主成分分析(PCA)は高次元や超次元のベクトルの主成分のみを抽出して、ベクトルの次元を下げてデータ量を削減する手法です。
主成分分析後の次元数を予め決められるので、主成分の次元を決めるとデータ量も決まるので、分析する元ベクトルの次元が膨大になっても計算量を一定に保つことができます。

さらに、Kmeansクラスタリングである程度クラスタリングをしておくことで評価する対象の映画を限定し、比較回数を減少させて、レスポンスのスピードを向上を狙います。

今回はMovieLensというフリーの映画評価のデータセットを利用します。
https://grouplens.org/datasets/movielens/100k/

# ざっくりと言うと。。。。
自分が好きな映画に各ユーザーから似たような評価をされている映画はそれも好きなはず！！
でも全員といちいち比較していたら時間がかかっちゃって大変なので、先にざっくりと似てる人たちでグループ作っておいて(クラスタリング)、その中でもさらに重要そうな映画の評価だけ抜き出して(主成分分析)比較しよう！

### 主成分分析についてもう少し
例えば1万本の映画の評価データがあった際に、全員が見ている映画やほとんど誰も見ていないデータがあった場合に、あまりいい情報にならないから比較対象から外しちゃっても良いよね。特徴が出やすい100本くらいに絞っておこう。（厳密に言うと違うのですがだいたいこんな感じです。）

# データの取得
https://grouplens.org/datasets/movielens/100k/
からml-100k.zipをダウンロードして展開します。
中にはいくつかのファイルがありますがREADMEに説明があります。
今回主に利用するのは、u1.baseです。

# プログラム
プログラム内にコメントを記載して一通り下記します。

```python:recommend.py
import numpy as np
import pandas as pd
from sklearn.decomposition import PCA
from sklearn.cluster import KMeans

# TSV形式のデータの読み込み
datum = np.loadtxt("u1.base", delimiter="\t", usecols=(0, 1, 2), skiprows=1)

# ユーザーIDと映画IDの一覧を用意
user_ids = []
movie_ids = []
for row in datum:
    user_ids.append( row[0] )
    movie_ids.append( row[1] )
user_ids = list(set(user_ids))
movie_ids = list(set(movie_ids))

# 映画IDごとの評価データを整理
vectors = {}
for movie_id in sorted(movie_ids):
    vectors[movie_id] = {}
    for user_id in user_ids:
        # 見ていない映画はデフォルト-1評価とする
        vectors[movie_id][user_id] = -1

# ベクトルにユーザーの各評価を格納
for row in datum:
    vectors[row[1]][row[0]] = row[2]

dataset = []

# データを整形
for movie_id in vectors:
    temp_data = []
    for user_id in sorted(vectors[movie_id]):
        temp_data.append(vectors[movie_id][user_id])
    dataset.append(temp_data)

# Kmeansで3つのクラスタに分類
predict = KMeans(n_clusters=3).fit_predict(dataset)

# 主成分分析後の次元数
DIMENTION_NUM = 128
# 主成分分析
pca = PCA(n_components=DIMENTION_NUM)
dataset = pca.fit_transform(dataset)
print('累積寄与率: {0}'.format(sum(pca.explained_variance_ratio_)))

# 映画ID1に似た映画を探す
MOVIE_ID = 1
# 映画ID1のクラスターIDを取得
CLUSTER_ID = predict[movie_ids.index(MOVIE_ID)]

distance_data = {}
for index in range(len(predict)):
    # 同じクラスター内にある場合ベクトルの距離を比較
    if predict[index] == CLUSTER_ID:
        distance = np.linalg.norm( np.array(dataset[index], dtype=float) - np.array(dataset[movie_ids.index(MOVIE_ID)], dtype=float) )
        distance_data[movie_ids[index]] = distance

# ベクトルの距離順に表示
print(sorted(distance_data.items(), key=lambda x: x[1]))
```

# 結果
```
累積寄与率: 0.7248119795849713
[(1.0, 0.0), (121.0, 67.0315681132561), (117.0, 69.90161652852805), (405.0, 71.07049485275981), (151.0, 71.39559068741323), (118.0, 72.04600188124728), (222.0, 72.78595965661094), (181.0, 74.18442192660996), (742.0, 76.10520742268852), (28.0, 76.27732956739469), (237.0, 76.31850794116573), (25.0, 76.82773190547944), (7.0, 76.96541606511116), (125.0, 77.07961442692692), (95.0, 77.42577990621398), (257.0, 77.87452368514414), (50.0, 78.80566867021435), (111.0, 78.9631520879044), (15.0, 78.97825600046046), (69.0, 79.22663656944697), (588.0, 79.64989759225082), (82.0, 80.23718315576053), (71.0, 80.26936193506091), (79.0, 81.02025503780014).....
```

ID=1の映画がトイ・ストーリーで、一番近いとされた映画ID=121がインデペンデンス・デイでした。
寄与率は0.72ということは、主成分だけで元データの72%程度復元できているということです。
なんとなくわかる気もしますね！！！

# その後の実装
今回は一つのスクリプトでデータ整形からクラスタリングと主成分分析、比較まで通して行ってしまいましたが、
本来は主成分分析までを行ったデータをデータベースに格納しておいて、比較のみ都度行うように実装します。

また、映画データや評価データは日々増えていくので適切な期間を決めてクラスタリングや主成分分析をバッチなどでやり直していくようにします。

API化する際には主成分の次元数やクラスタ数、APIキャッシュなどを駆使してレコメンド精度とレスポンススピードを調整していきます。
この*レコメンド精度*ですが、最初はなんとなく感覚で合っているかどうかで見てもよいですが、CTRやCVRなどと兼ねわせて実際のデータを加味したディープラーニングを駆使していくとさらに今風の機械学習といったふうになります。

次回はPythonのflaskなどを用いいてAPIにするところを書こうと思います。