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

####注意事項  
初投稿です.
****  

#### 動機・やりたいこと  
「情報型推薦システム入門」を読んで, 自分なりに実装を試みる.
協調フィルタリングには様々な手法があるが, その中の「Slope One予測」をまとめる.
****  

####協調フィルタリングとは何か？
過去のデータから、ユーザーの好みや興味をもつアイテムを予測すること
某ECサイトでおなじみの
「この商品を買った人はこんな商品を買っています」
「あなたへのおすすめ商品は…」
に使われているツールである.
****  
####基本的な協調フィルタリング
1.ユーザーベースの最近傍推薦
①対象ユーザーの過去の嗜好から, 似ている他のユーザー（ピアユーザー）を特定する.
②対象ユーザーがまだ見ていない製品に対する評価値をピアユーザーの評価値を用いて予測する.  
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型で列をアイテム, 行をユーザの形式である.  
コメントで,コード中身の詳細を記載している.

```php
%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
```