@yuichirominato 2019.02.02更新 209views

【リコメンド】量子リコメンドシステムを自作してみる(その1)


はじめに

もちろん最後は量子コンピュータをつかってリコメンドシステムを作りますが、自作することでその仕組みを理解することができます。全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

Matrix Factorization(MF)はNetflixなどで採用されている大きな評価のmatrixの次元を削減する方法です。評価システムの特徴は評価してないという0と評価が低いという0が同じところです。この特徴を維持しながら行列因子分解のMFを行うことで、次元削減をしてより精度が高くて大きなリコメンドシステムが作れます。

参考:
Matrix Factorizationとは
https://qiita.com/ysekky/items/c81ff24da0390a74fc6c

量子コンピュータでのMF

こちらは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

つづく

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方