初投稿です。
勉強したことのアウトプットの場として活用していきたいと考えています。
最近は推薦システムに関して勉強していました。

今回紹介する内容については神嶌先生の記事¹を参考にしています。とても丁寧に推薦システムについて説明がされていますので、詳しくはそちらを参考にしてください。

#利用者間型メモリベース法
利用者間型メモリベース法とは、推薦システムにおける嗜好の予測手法である協調フィルタリングの一種です。今回紹介する手法は1990年代にGroupLensにより提案されたシンプルな利用者間メモリベース法です。
利用者間型メモリベース法では、以下のステップで予測を行います。

1.利用者間の類似度を計算
2.類似度から評価値を予測

以下、順を追って説明していきますが、まず用いる記号について説明します。

##記号について

$a$ :活動利用者
- 評価値を予測する対象の利用者
$x$ :標本利用者
- 活動利用者ではないシステム利用者
$X$ :$n$人の標本利用者集合
$Y$ :$m$種類のアイテム集合
$Y_x$ :$x$による評価済みのアイテム集合
$Y_{ax}$ : $a$と$x$による評価済みのアイテム集合
$X_y$ : アイテム$y$を評価した利用者の集合
$r_{xy}$ ($r_{ay}$) :利用者$x$($a$)のアイテム$y$に対する評価値
$\overline r'_x$ ($\overline r'_a$) :$a$と$x$が共通して評価したアイテムに対する$x$($a$)の平均評価値

\overline r'_x = \sum_{y\in Y_{ax}} r_{xy}/|Y_{ax}|

##利用者間の類似度を計算
次に、活動利用者と標本利用者の評価値を用いて、利用者間の類似度を計算します。数式の形はピアソンの相関係数と全く同じです。

\rho_{ax} = \frac{\sum_{y\in Y_{ax}} (r_{ay}-\overline r'_a)(r_{xy}-\overline r'_x)}{\sqrt{\sum_{y\in Y_{ax}}(r_{ay}-\overline r'_a)^2}\sqrt{\sum_{y\in Y_{ax}}(r_{xy}-\overline r'_x)^2}}

※計算の都合上、分母が$0$となるとき $\rho_{ax}=0$ とします。

##類似度から評価値を予測
そして、活動利用者が未評価のアイテムの評価値を予測していきます。以下で予測値を計算します。


\hat{r}_{ay} = \overline{r}_a+\frac{\sum_{x\in x_{y}} \rho_{ax}(r_{xy}-\overline r'_x)}{\sum_{x\in x_{y}} |\rho_{ax}|}

ここで、右辺第二項の分子は $(r_{xy}-\overline r'_x)$の加重平均です。分母は$|X_y|$が大きいと加重平均が大きくなりやすい問題に対する正規化項です。

#実装
これまでに紹介した手法をpythonで実装していきたいと思います。
とりあえず実装したという感じのコードなので無駄だったりパフォーマンスがよくないだったりとご意見あると思います。ぜひコメントいただけるとありがたいです。

import numpy as np
from tqdm import tqdm_notebook as tqdm

def userMemoryBased(array :np.ndarray) -> dict:
    predict = {}

    for a_num in tqdm(range(array.shape[0])):

        a_user = array[a_num]
        other_users = np.delete(array, a_num, axis=0)
        a_mean = np.mean(a_user[np.nonzero(a_user)]) #mean of evaluations by an active user to items
        ra_equal_0 = np.where(a_user==0)[0]
        rho = {}
        common_mean_dic = {}

        #calculate degree of similarity
        for index, one_user in enumerate(other_users):
            if index >= a_num:
                index += 1
            rx_c, ra_c = [], []
            for rx,ra in zip(one_user, a_user):
                if rx != 0 and ra != 0:
                    rx_c.append(rx)
                    ra_c.append(ra) 

            rx_c_ = np.array(rx_c)
            ra_c_ = np.array(ra_c)
            mean_x = np.mean(np.array(rx_c))
            mean_a = np.mean(np.array(ra_c)) 
            common_mean_dic[index] = mean_x

            upper_s = np.dot((rx_c_ - mean_x), (ra_c_-mean_a))
            lower_s = np.dot((((rx_c_-mean_x)**2)**0.5), (((ra_c_-mean_x)**2)**0.5))
            if lower_s == 0:
                rho[index] = 0
            else:
                rho[index] = upper_s/lower_s

        #predict evaluations
        a_predict = {}
        for k in range(len(ra_equal_0)):
            upper = 0
            lower = 0
            for i, r_xi in enumerate(other_users[:,ra_equal_0[k]]):
                if i >= a_num:
                    i += 1
                upper += rho[i]*(r_xi - common_mean_dic[i])
                lower += abs(rho[i])
            a_predict[ra_equal_0[k]] = a_mean + (upper/lower)
        predict[a_num] = a_predict

    return predict

未評価アイテムについて、評価値は0であると想定して実装しています。
関数にnumpy配列を渡してあげると、以下のように未評価アイテムの予測評価値を返してくれます。

#100ユーザの1000アイテムに対する評価値を(0,1,2,3,4)の一様乱数で生成
test = np.random.randint(0, 5, (100, 1000)) 
a = userMemoryBased(test)

print(a)

{0: {2: 2.468040770193209,
  11: 2.6568178540334513,
  15: 2.5840213055330685,
  16: 2.6791009339457705,
  25: 2.3998161470909904,
  33: 2.5034719588965726,
  36: 2.6105254456721436,
  47: 2.721250774393618,
  48: 2.6377660735294057,
  61: 2.734947112709698,
  65: 2.418918576187929,
  67: 2.5312179005869497,
  71: 2.828277671246278,
  74: 2.6330321567914496,
  75: 2.9791210026642583,
  94: 2.489187514809523,
  98: 2.5073410705066315},
 1: {0: 2.8350857619311847,
  2: 2.734994278585904,
  4: 2.9105141986233938,
  13: 2.737412251357452,
    #(以下略)

どういうユースケースが想定されるかわからなかったので、与えられた評価値行列に対して、ユーザごとの未評価アイテムの評価値を辞書型で返すようにしています。
(あまり関数自体に機能をもたせるのはよくないなと思いつつも、評価値行列が大きい場合には計算時間がかかるゆえ進捗状況を見たいなと思ったので、プログレスバーを表示してくれるtqdmモジュールを使いました。)
#まとめ
今回は、利用者間メモリベース法の一番シンプルな手法を紹介・実装しました。
実はこのモデルはユーザの評価値が全部同じときは類似度の計算ができないなどの問題点がありまして、モデルの改善が必要となってきます。
今後は協調フィルタリングに関する他のモデルの勉強を行い、また紹介できたらいいなと思います。

神嶌敏弘, 推薦システムのアルゴリズム, 2016 ,http://www.kamishima.net/archive/recsysdoc.pdf ↩