推薦システム・協調フィルタリング「Slope One」を作ってみた


注意事項

初投稿です.



動機・やりたいこと

「情報型推薦システム入門」を読んで, 自分なりに実装を試みる.

協調フィルタリングには様々な手法があるが, その中の「Slope One予測」をまとめる.



協調フィルタリングとは何か?

過去のデータから、ユーザーの好みや興味をもつアイテムを予測すること

某ECサイトでおなじみの

「この商品を買った人はこんな商品を買っています」

「あなたへのおすすめ商品は…」

に使われているツールである.



基本的な協調フィルタリング

1.ユーザーベースの最近傍推薦

①対象ユーザーの過去の嗜好から, 似ている他のユーザー(ピアユーザー)を特定する.

②対象ユーザーがまだ見ていない製品に対する評価値をピアユーザーの評価値を用いて予測する.


2.アイテムベース推薦

①アイテム間の類似度を用いて予測値を計算する.

の大きく2種類ある.

今回は, アイテムベースの派生である「Slope One予測」を実装する.



Slope One予測

個々のユーザーのアイテム評価値間差分を算出

全ユーザーについて算出されたアイテム評価値間差分を算出

算出結果を元に予測値を算出

といった手順で行う.

$i$,$j$はアイテム,$u$はユーザー,$u_{i}$はユーザー$u$のアイテム$i$に対する評価値,$R$は評価値データベース全体を表し,$S_{i,j}(R)$は$i$,$j$に対する評価値

関数$Relevant(u,j)$は関連するアイテム集合である.関連するアイテムとは,ユーザー$u$によってアイテム$j$と共に少なくとも一回は評価されたアイテムである.

計算方法として,以下の公式を用いてアイテム間の平均偏差を計算する.

$$ dev_{j,i} = \sum_{(u_{j},u_{i})\in S_{j,i}(R)} \frac{u_{j}-u_{i}}{|S_{j,i}(R)|}$$

次に下の式で予測を行う.

$$ pred(u,j) = \frac{\sum_{i \in Relevant(u,j)}(dev_{j,i}+u_{i})}{|Relevant(u,j)|} $$

拡張方法として,個々の偏差の重みを考慮した「Weighted Slop One」では,以下の予測式を用いる.

$$ pred(u,j) = \frac{\sum_{i \in Relevant(u,j)}(dev_{j,i}+u_{i}*|S_{j,i}(R)|)}{|Relevant(u,j)|} $$

簡単な例で「Weighted Slope One」の結果を示す.

(ex1)

0は未だ評価されていない事を示す.

     i1  i2  i3

u1 2  5  0
u2 3  2  5
u3 4  0  3

u1のi3を予測したいとき、ユーザー(target_user以外)ごとで

①i3とi1を比較する

$u_{2}$について,$5-3=2$

$u_{3}$について,$3-4=-1$

平均距離は, $\frac{2+(-1)}{2}=0.5$

②i3とi2を比較する

$u_{2}$について,5-2=3

平均距離は, $\frac{3}{1}=3.0$

よって,アイテム1と対象ユーザのアイテム1の評価値2に基づく予測値は$2+0.5=2.5$

アイテム2と対象ユーザのアイテム2の評価値5に基づく予測値は$5+3=8.0$

評価回数を考慮して予測を行うので,以下の結果になる.

$$pred(u1,i3) = \frac{2*2.5 + 1*8}{2+1}=4.33$$



まとめ

今回,Slope One予測のアルゴリズムを実装してみた(下にコードを示す).

結果としては, 完成したが, loopが多く適用したため計算量が多く, 実際に適用されるようなビッグデータに対してはあまり機能しなかった.

数値計算で,for構文を使っている箇所は, 変更できるので, 変更していき計算時間を短縮していきたいと思う.



コード

コードは以下に示す.


データセットは, DataFrame型で列をアイテム, 行をユーザの形式である.


コメントで,コード中身の詳細を記載している.

%matplotlib inline

import pylab as plt
import seaborn
import numpy as np
import pandas as pd
import statistics
import math
def div_make(dataset,target_user,target_item):
#予測値格納 , float型変換
dataset_predict = dataset.copy().astype(np.float64)
Count =[]
Count_re =[]
item_count =[]
Div =[]
"""
①U_(j,i)の作成
j(target_item)とi(比較アイテム)を両方評価するユーザーの集合の定義
(ex)
i1 i2 i3
u1 2 5 0
u2 3 2 5
u3 4 0 3
u1のi3を予測したいとき、ユーザー(target_user以外)ごとで
①i3とi1を比較する
②i3とi2を比較する

① を満たすとき user1以外でi1とi3の両方を評価しているのはu2,u3なので、
   i1 i2 i3
u2 3 2 5
u3 4 0 3
② を満たすとき user1以外でi1とi3の両方を評価しているのはu2,u3なので、
   i1 i2 i3
u2 3 2 5
"""
user_range = range(1,len(dataset.index)+1)
item_range = range(1,len(dataset.columns)+1)

for item in item_range:
#target_itemとitem毎の評価を行うので、item毎に毎回作成する
dataset_U = dataset.copy()
#target_itemとtarget_itemの比較をする必要がないのでスルーする
if( item == target_item):
continue
#userを一人づつ比較→target_itemと比較するitemのどちらかで,未評価(0)を出すuserがいた場合
# Uから削除する
for user in user_range:
#どちらかで未評価の場合
if(dataset ["i%d" %target_item]["u%d" %user] ==0 or dataset ["i%d" %item]["u%d" %user] == 0):
# userを削除
dataset_U = dataset_U.drop("u%d" %user ,axis=0) #特定の行の削除 
#dataset_U をdataframe型から変換
Dataset_U = dataset_U.values
#div に格納するため定義
div = np.zeros((len(dataset_U.columns)))

"""
② 作成したUを用いて計算を行う
U①
  i1 i2 i3
u2 3 2 5
u3 4 0 3
から、
u2:i3-i1 = 5-3 = 2
u3:i3-i1 = 3-4 = -1
→2+(-1) = +1.0
今回、2回計算したので,1/2.0 = 0.5
U②
  i1 i2 i3
u2 3 2 5
から、
u2:i3-i2 = 5-2 = 3
→3.0
今回、1回計算したので,3.0/1.0 = 3.0
"""

#範囲定義
U_item_range = range(len(dataset_U.columns))
U_user_range = range(len(dataset_U.index))

#target_item と比較アイテムの差を計算
ad_dev_deno =0
#Uに存在するuser毎で計算
for user2 in U_user_range:
#print("user %d" % (user2+1),"人目の比較" , "item%d" %item)
#print("%d" %Dataset_U [user2][target_item-1] , " - %d"%Dataset_U [user2][item-1])
ad_dev_deno += float(Dataset_U [user2][target_item-1] - Dataset_U [user2][item-1])

#print("何人で比較したのか→%d" %len(U_user_range))
if(len(U_user_range)==0):
ad_div =0
else:
ad_div = ad_dev_deno / len(U_user_range)

Count.append(len(U_user_range))
Count_re.append(len(U_user_range))

div[item-1] = div[item-1] + ad_div
Div.append(div[item-1])
item_count.append(item)
# Div:差を格納 Count,Count_re:何回、他のユーザーとの比較計算を行ったのか item_count:何番目のitemなのか

############################################################################################################################
## 以下、predictを行う
for item2 in range(len(item_count)):

# k:PのΣの中身を計算
k = Count[item2] * ( Div[item2] + dataset["i%d" % (item_count[item2])]["u%d" %(target_user)] )
if( dataset["i%d" % (item_count[item2])]["u%d" %(target_user)]==0):
k=0
Count_re[item2] = 0

# PのΣを計算
dataset_predict["i%d" % (target_item)]["u%d" %(target_user)] +=k

#Pの最後に割る部分を計算: target_userが元々評価していないitemからはtarget_itemを評価できないので,
# target_userが評価していないitemはカウントしてはいけない→Count_reで削除している Count[item2] =0 の部分
if(sum(Count_re)==0):
dataset_predict["i%d" % (target_item)]["u%d" %(target_user)] = 0
else:
dataset_predict["i%d" % (target_item)]["u%d" %(target_user)] = dataset_predict["i%d" % (target_item)]["u%d" %(target_user)] /sum(Count_re)
#print("**predict**\n")
print(dataset_predict["i%d"%target_item]["u%d"%target_user])
return dataset_predict["i%d"%target_item]["u%d"%target_user]

```php
#dataset:dataframe型:index:ユーザーid column:アイテムid
def slope_one(dataset):

start = time.time()

dataset_predict = dataset.copy().astype(np.float64)
user_range = range(1,len(dataset.index)+1)
item_range = range(1,len(dataset.columns)+1)

for user in user_range:
for item in item_range:
#print("(%d"%item,"%d)"%user)
if (dataset["i%d"%item]["u%d" %user] == 0 ):
target_user = user
target_item = item
print( "target_user%d" %target_user , "target_item%d" %target_item)
#print("**function_div_make **")
if(dataset_predict["i%d"%item]["u%d" %user] != 0):
continue
dataset_predict["i%d"%item]["u%d" %user] = div_make(dataset,target_user,target_item)

print("******************")
print(dataset)
print("******************")
print(dataset_predict)
return dataset_predict