もちろん最後は量子コンピュータをつかってリコメンドシステムを作りますが、自作することでその仕組みを理解することができます。全2回でみていきたいと思います。
通常のリコメンドシステムはECサイトやブログなどではよりたくさんの商品を買ってもらったり、より多くのブログを読んでもらうためにリコメンドシステムというオススメシステムがあります。それはアルゴリズムによって成り立っており、その成り立ちを学びたいと思います。
リコメンドシステムには様々な種類があります。
・購買・閲覧履歴ベース
・アイテムベース
・ルールベース
・個人ベース
それぞれアルゴリズムが違いますが、アイテムベースはテキストや画像認識から検索、ルールベースは開発者の決めたルール、個人ベースは過去の購買や個人の属性から学習を通じて行います。
今回は購買・閲覧履歴ベースで考えます。また、実際にはNetflixやAmazonのように商品や動画を評価することでリコメンドを作ることが多いですが、その評価値の特性を考えてシステムを構築する必要があります。
リコメンドシステムは新しい技術ではないので、様々な企業から技術やサービスが提供されています。ASP型やオープンソース型など色々ありますのでいいのを選びましょう。本気でビジネスをしたい場合には、自作しましょう。なかなかぴったりのリコメンドエンジンは手に入りません。
・ASP型
・オープンソース型
・自作
ここに多くのオープンソースのまとめがあります。
https://github.com/grahamjenson/list_of_recommender_systems
外部のASP提供で月額数万から15万円くらいでしょうか。それを超える場合にはカスタマイズでお金がかかりそうです。大きなエンジンは作るの大変ですが利益も大きそうです。
作り方を参考にしたり、データ圧縮を学びます。言語はpythonを使います。
Comprehensive Guide to build a Recommendation Engine from scratch (in Python)
https://www.analyticsvidhya.com/blog/2018/06/comprehensive-guide-recommendation-engine-python/
今回は協調フィルタリングという似たものを探してそれをお勧めするという方式をやってみます。まず行うことは2つのユーザーやデータが類似しているかということをやります。
類似度の算定には多々ありますが、今回はジャッカード係数というものを使ってみます。(ジャッカード係数)=(積集合)/(和集合)という集合で計算できます。早速コードは、
import numpy as np
def jac(ss1,ss2):
return len(set(ss1) & set(ss2))/len(set(ss1) | set(ss2))
このようにしてみました。集合計算をpythonを使って値を返します。
jac([1,2],[1,2,3])
#=>0.6666666666666666
このように使います。計算自体は、積集合が1と2が共通してて、2。和集合が全部足して3です。2/3で0.66666…となります。
アイテムを縦横の行列にして、それぞれのアイデムの類似度を行列にしてみます。
def sim(mat):
n_mat = len(mat)
data_matrix = np.zeros((n_mat,n_mat))
for i in range(n_mat-1):
for j in range(i+1,n_mat):
data_matrix[i][j] = jac(mat[i],mat[j])
return data_matrix
ここでは、比較したい2つのアイテムの類似度をどんどん行列の非対角成分に入れていきます。最初に入れるのは連想配列の形でどんどん比較したいものを入れてしまいます。
sim(np.array([[1,2,3,4],[5,6,7,8],[1,2,5,6],[1,3,2,4,8,6]]))
array([[0. , 0. , 0.33333333, 0.66666667],
[0. , 0. , 0.33333333, 0.25 ],
[0. , 0. , 0. , 0.42857143],
[0. , 0. , 0. , 0. ]])
行列の非対角成分に入力した連想配列の通し番号順に計算した類似度が入ります。文字列でも大丈夫です。
sim(np.array([["りんご","みかん","牛乳"],["みかん"],["牛乳","りんご","牛肉","パイナップル"],["自動車","みかん"]]))
array([[0. , 0.33333333, 0.4 , 0.25 ],
[0. , 0. , 0. , 0.5 ],
[0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. ]])
早速アイテムを選んで上記の類似度matrixから一番近いもの順に並べ替えてみます。
def rec(mat2):
mat3 = sim(mat2)
mat3 = mat3 + mat3.T
arr_total = []
for i in range(len(mat3)):
mat_temp = mat3[i]
sort = np.sort(mat_temp)
sort_index = np.argsort(mat_temp)
arr_temp = []
for j in range(len(sort)):
arr_temp.append([sort_index[::-1][j],sort[::-1][j]])
arr_total.append(arr_temp)
return arr_total
rec(np.array([[“りんご”,”みかん”,”牛乳”],[“みかん”],[“牛乳”,”りんご”,”牛肉”,”パイナップル”],[“自動車”,”みかん”]]))
[[[2, 0.4], [1, 0.3333333333333333], [3, 0.25], [0, 0.0]], [[3, 0.5], [0, 0.3333333333333333], [2, 0.0], [1, 0.0]], [[0, 0.4], [3, 0.0], [2, 0.0], [1, 0.0]], [[1, 0.5], [0, 0.25], [3, 0.0], [2, 0.0]]]
連想配列を入れると、それぞれに対して類似度を計算してソートした番号と類似度スコアが出ます。 上記だと、一番目の[“りんご”,”みかん”,”牛乳”]にたいして、[“牛乳”,”りんご”,”牛肉”,”パイナップル”]が類似度0.4、[“みかん”]が類似度0.33です。使用する場合には、このまま対応するidを順番に提案してあげればいいかと思います。
簡単な実装コードを下記に書いておきます。類似度の判定にはジャッカード係数をつかっています。
import numpy as np
#類似度計算
def jac(ss1,ss2):
return len(set(ss1) & set(ss2))/len(set(ss1) | set(ss2))
#類似度計算を格納するデータ行列
def sim(mat):
n_mat = len(mat)
data_matrix = np.zeros((n_mat,n_mat))
for i in range(n_mat-1):
for j in range(i+1,n_mat):
data_matrix[i][j] = jac(mat[i],mat[j])
return data_matrix
#類似度順にソートして表示
def rec(mat2):
mat3 = sim(mat2)
mat3 = mat3 + mat3.T
arr_total = []
for i in range(len(mat3)):
mat_temp = mat3[i]
sort = np.sort(mat_temp)
sort_index = np.argsort(mat_temp)
arr_temp = []
for j in range(len(sort)):
arr_temp.append([sort_index[::-1][j],sort[::-1][j]])
arr_total.append(arr_temp)
return arr_total
このmatrixはアイテム数やユーザー数が増えると急激に大きくなります。そんなmatrixを効率的に裁くために今後必要なのが行列因子分解などのデータの次元削減方法です。
Matrix Factorization(MF)はNetflixなどで採用されている大きな評価のmatrixの次元を削減する方法です。評価システムの特徴は評価してないという0と評価が低いという0が同じところです。この特徴を維持しながら行列因子分解のMFを行うことで、次元削減をしてより精度が高くて大きなリコメンドシステムが作れます。
参考:
Matrix Factorizationとは
https://qiita.com/ysekky/items/c81ff24da0390a74fc6c
こちらはLANL(米国ロスアラモス国立研究所)で提案がされています。次回はこちらをみて、実際にイジングでのMFを実装して、上記のリコメンドシステムを改善してみます。
Nonnegative/binary matrix factorization with a D-Wave quantum annealer
https://arxiv.org/abs/1704.01605
参考:
https://www.rco.recruit.co.jp/career/engineer/blog/dwave03/
https://qard.is.tohoku.ac.jp/T-Wave/?p=397
つづく
Tweetinfo@mdrft.com