協(xié)同過(guò)濾

在 用戶(hù) ―― 物品（user - item）的數(shù)據(jù)關(guān)系下很容易收集到一些偏好信息（preference），比如評(píng)分。利用這些分散的偏好信息，基于其背后可能存在的關(guān)聯(lián)性，來(lái)為用戶(hù)推薦物品的方法，便是協(xié)同過(guò)濾，或稱(chēng)協(xié)作型過(guò)濾（collaborative filtering）。

這種過(guò)濾算法的有效性基礎(chǔ)在于：

??? 用戶(hù)的偏好具有相似性，即用戶(hù)是可分類(lèi)的。這種分類(lèi)的特征越明顯，推薦的準(zhǔn)確率就越高
??? 物品之間是存在關(guān)系的，即偏好某一物品的任何人，都很可能也同時(shí)偏好另一件物品

不同環(huán)境下這兩種理論的有效性也不同，應(yīng)用時(shí)需做相應(yīng)調(diào)整。如豆瓣上的文藝作品，用戶(hù)對(duì)其的偏好程度與用戶(hù)自身的品位關(guān)聯(lián)性較強(qiáng)；而對(duì)于電子商務(wù)網(wǎng)站來(lái)說(shuō)，商品之間的內(nèi)在聯(lián)系對(duì)用戶(hù)的購(gòu)買(mǎi)行為影響更為顯著。當(dāng)用在推薦上，這兩種方向也被稱(chēng)為基于用戶(hù)的和基于物品的。本文內(nèi)容為基于用戶(hù)的。
影評(píng)推薦實(shí)例

本文主要內(nèi)容為基于用戶(hù)偏好的相似性進(jìn)行物品推薦，使用的數(shù)據(jù)集為 GroupLens Research 采集的一組從 20 世紀(jì) 90 年代末到 21 世紀(jì)初由 MovieLens 用戶(hù)提供的電影評(píng)分?jǐn)?shù)據(jù)。數(shù)據(jù)中包含了約 6000 名用戶(hù)對(duì)約 4000 部電影的 100萬(wàn)條評(píng)分，五分制。數(shù)據(jù)包可以從網(wǎng)上下載到，里面包含了三個(gè)數(shù)據(jù)表――users、movies、ratings。因?yàn)楸疚牡闹黝}是基于用戶(hù)偏好的，所以只使用 ratings 這一個(gè)文件。另兩個(gè)文件里分別包含用戶(hù)和電影的元信息。

本文使用的數(shù)據(jù)分析包為 pandas，環(huán)境為 IPython，因此其實(shí)還默認(rèn)攜帶了 Numpy 和 matplotlib。下面代碼中的提示符看起來(lái)不是 IPython 環(huán)境是因?yàn)?Idle 的格式發(fā)在博客上更好看一些。
數(shù)據(jù)規(guī)整

首先將評(píng)分?jǐn)?shù)據(jù)從 ratings.dat 中讀出到一個(gè) DataFrame 里：

            
>>> import pandas as pd
>>> from pandas import Series,DataFrame
>>> rnames = ['user_id','movie_id','rating','timestamp']
>>> ratings = pd.read_table(r'ratings.dat',sep='::',header=None,names=rnames)
>>> ratings[:3]
 user_id movie_id rating timestamp
0  1  1193  5 978300760
1  1  661  3 978302109
2  1  914  3 978301968
 
[3 rows x 4 columns]


          

ratings 表中對(duì)我們有用的僅是 user_id、movie_id 和 rating 這三列，因此我們將這三列取出，放到一個(gè)以 user 為行，movie 為列，rating 為值的表 data 里面。（其實(shí)將 user 與 movie 的行列關(guān)系對(duì)調(diào)是更加科學(xué)的方法，但因?yàn)橹嘏芤槐樘闊┝?，這里就沒(méi)改。）
?

            
>>> data = ratings.pivot(index='user_id',columns='movie_id',values='rating')
>>> data[:5]
movie_id 1 2 3 4 5 6 
user_id                  
1   5 NaN NaN NaN NaN NaN ...
2  NaN NaN NaN NaN NaN NaN ...
3  NaN NaN NaN NaN NaN NaN ...
4  NaN NaN NaN NaN NaN NaN ...
5  NaN NaN NaN NaN NaN 2 ...

          

可以看到這個(gè)表相當(dāng)?shù)孟∈?，填充率大約只有 5%，接下來(lái)要實(shí)現(xiàn)推薦的第一步是計(jì)算 user 之間的相關(guān)系數(shù)，DataFrame 對(duì)象有一個(gè)很親切的 .corr(method='pearson', min_periods=1) 方法，可以對(duì)所有列互相計(jì)算相關(guān)系數(shù)。method 默認(rèn)為皮爾遜相關(guān)系數(shù)，這個(gè) ok，我們就用這個(gè)。問(wèn)題僅在于那個(gè) min_periods 參數(shù)，這個(gè)參數(shù)的作用是設(shè)定計(jì)算相關(guān)系數(shù)時(shí)的最小樣本量，低于此值的一對(duì)列將不進(jìn)行運(yùn)算。這個(gè)值的取舍關(guān)系到相關(guān)系數(shù)計(jì)算的準(zhǔn)確性，因此有必要先來(lái)確定一下這個(gè)參數(shù)。

??? 相關(guān)系數(shù)是用于評(píng)價(jià)兩個(gè)變量間線(xiàn)性關(guān)系的一個(gè)值，取值范圍為 [-1, 1]，-1代表負(fù)相關(guān)，0 代表不相關(guān)，1 代表正相關(guān)。其中 0~0.1 一般被認(rèn)為是弱相關(guān)，0.1~0.4 為相關(guān)，0.4~1 為強(qiáng)相關(guān)。

min_periods 參數(shù)測(cè)定

測(cè)定這樣一個(gè)參數(shù)的基本方法為統(tǒng)計(jì)在 min_periods 取不同值時(shí)，相關(guān)系數(shù)的標(biāo)準(zhǔn)差大小，越小越好；但同時(shí)又要考慮到，我們的樣本空間十分稀疏，min_periods 定得太高會(huì)導(dǎo)致出來(lái)的結(jié)果集太小，所以只能選定一個(gè)折中的值。

這里我們測(cè)定評(píng)分系統(tǒng)標(biāo)準(zhǔn)差的方法為：在 data 中挑選一對(duì)重疊評(píng)分最多的用戶(hù)，用他們之間的相關(guān)系數(shù)的標(biāo)準(zhǔn)差去對(duì)整體標(biāo)準(zhǔn)差做點(diǎn)估計(jì)。在此前提下對(duì)這一對(duì)用戶(hù)在不同樣本量下的相關(guān)系數(shù)進(jìn)行統(tǒng)計(jì)，觀察其標(biāo)準(zhǔn)差變化。

首先，要找出重疊評(píng)分最多的一對(duì)用戶(hù)。我們新建一個(gè)以 user 為行列的方陣 foo，然后挨個(gè)填充不同用戶(hù)間重疊評(píng)分的個(gè)數(shù)：
?

            
>>> foo = DataFrame(np.empty((len(data.index),len(data.index)),dtype=int),index=data.index,columns=data.index)
>>> for i in foo.index:
  for j in foo.columns:
   foo.ix[i,j] = data.ix[i][data.ix[j].notnull()].dropna().count()

          

這段代碼特別費(fèi)時(shí)間，因?yàn)樽詈笠恍姓Z(yǔ)句要執(zhí)行 4000*4000 = 1600萬(wàn)遍；（其中有一半是重復(fù)運(yùn)算，因?yàn)?foo 這個(gè)方陣是對(duì)稱(chēng)的）還有一個(gè)原因是 Python 的 GIL，使得其只能使用一個(gè) CPU 線(xiàn)程。我在它執(zhí)行了一個(gè)小時(shí)后，忍不住去測(cè)試了一下總時(shí)間，發(fā)現(xiàn)要三個(gè)多小時(shí)后就果斷 Ctrl + C 了，在算了一小半的 foo 中，我找到的最大值所對(duì)應(yīng)的行列分別為 424 和 4169，這兩位用戶(hù)之間的重疊評(píng)分?jǐn)?shù)為 998：

?

            
>>> for i in foo.index:
  foo.ix[i,i]=0#先把對(duì)角線(xiàn)的值設(shè)為 0
 
>>> ser = Series(np.zeros(len(foo.index)))
>>> for i in foo.index:
  ser[i]=foo[i].max()#計(jì)算每行中的最大值
 
>>> ser.idxmax()#返回 ser 的最大值所在的行號(hào)
4169
 
>>> ser[4169]#取得最大值
998
 
>>> foo[foo==998][4169].dropna()#取得另一個(gè) user_id
424  4169
Name: user_id, dtype: float64

          

我們把 424 和 4169 的評(píng)分?jǐn)?shù)據(jù)單獨(dú)拿出來(lái)，放到一個(gè)名為 test 的表里，另外計(jì)算了一下這兩個(gè)用戶(hù)之間的相關(guān)系數(shù)為 0.456，還算不錯(cuò)，另外通過(guò)柱狀圖了解一下他倆的評(píng)分分布情況：

            
>>> data.ix[4169].corr(data.ix[424])
0.45663851303413217
>>> test = data.reindex([424,4169],columns=data.ix[4169][data.ix[424].notnull()].dropna().index)
>>> test
movie_id 2  6  10 11 12 17 ...
424    4  4  4  4  1  5 ...
4169    3  4  4  4  2  5 ...
 
>>> test.ix[424].value_counts(sort=False).plot(kind='bar')
>>> test.ix[4169].value_counts(sort=False).plot(kind='bar')


          

對(duì)這倆用戶(hù)的相關(guān)系數(shù)統(tǒng)計(jì)，我們分別隨機(jī)抽取 20、50、100、200、500 和 998 個(gè)樣本值，各抽 20 次。并統(tǒng)計(jì)結(jié)果：

            
 >>> periods_test = DataFrame(np.zeros((20,7)),columns=[10,20,50,100,200,500,998])
>>> for i in periods_test.index:
  for j in periods_test.columns:
   sample = test.reindex(columns=np.random.permutation(test.columns)[:j])
   periods_test.ix[i,j] = sample.iloc[0].corr(sample.iloc[1])
 
 
>>> periods_test[:5]
  10  20  50  100  200  500  998
0 -0.306719 0.709073 0.504374 0.376921 0.477140 0.426938 0.456639
1 0.386658 0.607569 0.434761 0.471930 0.437222 0.430765 0.456639
2 0.507415 0.585808 0.440619 0.634782 0.490574 0.436799 0.456639
3 0.628112 0.628281 0.452331 0.380073 0.472045 0.444222 0.456639
4 0.792533 0.641503 0.444989 0.499253 0.426420 0.441292 0.456639
 
[5 rows x 7 columns]
>>> periods_test.describe()
    10   20   50   100  200  500 #998略
count 20.000000 20.000000 20.000000 20.000000 20.000000 20.000000 
mean 0.346810 0.464726 0.458866 0.450155 0.467559 0.452448 
std  0.398553 0.181743 0.103820 0.093663 0.036439 0.029758 
min -0.444302 0.087370 0.192391 0.242112 0.412291 0.399875 
25%  0.174531 0.320941 0.434744 0.375643 0.439228 0.435290 
50%  0.487157 0.525217 0.476653 0.468850 0.472562 0.443772 
75%  0.638685 0.616643 0.519827 0.500825 0.487389 0.465787 
max  0.850963 0.709073 0.592040 0.634782 0.546001 0.513486 
 
[8 rows x 7 columns]


          

從 std 這一行來(lái)看，理想的 min_periods 參數(shù)值應(yīng)當(dāng)為 200 左右?？赡苡腥藭?huì)覺(jué)得 200 太大了，這個(gè)推薦算法對(duì)新用戶(hù)簡(jiǎn)直沒(méi)意義。但是得說(shuō)，隨便算出個(gè)有超大誤差的相關(guān)系數(shù)，然后拿去做不靠譜的推薦，又有什么意義呢。
算法檢驗(yàn)

為了確認(rèn)在 min_periods=200 下本推薦算法的靠譜程度，最好還是先做個(gè)檢驗(yàn)。具體方法為：在評(píng)價(jià)數(shù)大于 200 的用戶(hù)中隨機(jī)抽取 1000 位用戶(hù)，每人隨機(jī)提取一個(gè)評(píng)價(jià)另存到一個(gè)數(shù)組里，并在數(shù)據(jù)表中刪除這個(gè)評(píng)價(jià)。然后基于閹割過(guò)的數(shù)據(jù)表計(jì)算被提取出的 1000 個(gè)評(píng)分的期望值，最后與真實(shí)評(píng)價(jià)數(shù)組進(jìn)行相關(guān)性比較，看結(jié)果如何。
?

            
>>> check_size = 1000
>>> check = {}
>>> check_data = data.copy()#復(fù)制一份 data 用于檢驗(yàn)，以免篡改原數(shù)據(jù)
>>> check_data = check_data.ix[check_data.count(axis=1)>200]#濾除評(píng)價(jià)數(shù)小于200的用戶(hù)
>>> for user in np.random.permutation(check_data.index):
  movie = np.random.permutation(check_data.ix[user].dropna().index)[0]
  check[(user,movie)] = check_data.ix[user,movie]
  check_data.ix[user,movie] = np.nan
  check_size -= 1
  if not check_size:
   break
 
 
>>> corr = check_data.T.corr(min_periods=200)
>>> corr_clean = corr.dropna(how='all')
>>> corr_clean = corr_clean.dropna(axis=1,how='all')#刪除全空的行和列
>>> check_ser = Series(check)#這里是被提取出來(lái)的 1000 個(gè)真實(shí)評(píng)分
>>> check_ser[:5]
(15, 593)  4
(23, 555)  3
(33, 3363) 4
(36, 2355) 5
(53, 3605) 4
dtype: float64

          

接下來(lái)要基于 corr_clean 給 check_ser 中的 1000 個(gè) 用戶(hù)-影片 對(duì)計(jì)算評(píng)分期望。計(jì)算方法為：對(duì)與用戶(hù)相關(guān)系數(shù)大于 0.1 的其他用戶(hù)評(píng)分進(jìn)行加權(quán)平均，權(quán)值為相關(guān)系數(shù)：
?

            
>>> result = Series(np.nan,index=check_ser.index)
>>> for user,movie in result.index:#這個(gè)循環(huán)看著很亂，實(shí)際內(nèi)容就是加權(quán)平均而已
  prediction = []
  if user in corr_clean.index:
   corr_set = corr_clean[user][corr_clean[user]>0.1].dropna()#僅限大于 0.1 的用戶(hù)
  else:continue
  for other in corr_set.index:
   if not np.isnan(data.ix[other,movie]) and other != user:#注意bool(np.nan)==True
    prediction.append((data.ix[other,movie],corr_set[other]))
  if prediction:
   result[(user,movie)] = sum([value*weight for value,weight in prediction])/sum([pair[1] for pair in prediction])
 
 
>>> result.dropna(inplace=True)
>>> len(result)#隨機(jī)抽取的 1000 個(gè)用戶(hù)中也有被 min_periods=200 刷掉的
862
>>> result[:5]
(23, 555)  3.967617
(33, 3363) 4.073205
(36, 2355) 3.903497
(53, 3605) 2.948003
(62, 1488) 2.606582
dtype: float64
>>> result.corr(check_ser.reindex(result.index))
0.436227437429696
>>> (result-check_ser.reindex(result.index)).abs().describe()#推薦期望與實(shí)際評(píng)價(jià)之差的絕對(duì)值
count 862.000000
mean  0.785337
std  0.605865
min  0.000000
25%  0.290384
50%  0.686033
75%  1.132256
max  3.629720
dtype: float64

          

862 的樣本量能達(dá)到 0.436 的相關(guān)系數(shù)，應(yīng)該說(shuō)結(jié)果還不錯(cuò)。如果一開(kāi)始沒(méi)有濾掉評(píng)價(jià)數(shù)小于 200 的用戶(hù)的話(huà)，那么首先在計(jì)算 corr 時(shí)會(huì)明顯感覺(jué)時(shí)間變長(zhǎng)，其次 result 中的樣本量會(huì)很小，大約 200+ 個(gè)。但因?yàn)闃颖玖孔冃〉木壒剩嚓P(guān)系數(shù)可以提升到 0.5~0.6 。

另外從期望與實(shí)際評(píng)價(jià)的差的絕對(duì)值的統(tǒng)計(jì)量上看，數(shù)據(jù)也比較理想。
實(shí)現(xiàn)推薦

在上面的檢驗(yàn)，尤其是平均加權(quán)的部分做完后，推薦的實(shí)現(xiàn)就沒(méi)有什么新東西了。

首先在原始未閹割的 data 數(shù)據(jù)上重做一份 corr 表：
?

            
>>> corr = data.T.corr(min_periods=200)
>>> corr_clean = corr.dropna(how='all')
>>> corr_clean = corr_clean.dropna(axis=1,how='all')

          

我們?cè)?corr_clean 中隨機(jī)挑選一位用戶(hù)為他做一個(gè)推薦列表：
?

            
>>> lucky = np.random.permutation(corr_clean.index)[0]
>>> gift = data.ix[lucky]
>>> gift = gift[gift.isnull()]#現(xiàn)在 gift 是一個(gè)全空的序列

          

最后的任務(wù)就是填充這個(gè) gift：
?

            
>>> corr_lucky = corr_clean[lucky].drop(lucky)#lucky 與其他用戶(hù)的相關(guān)系數(shù) Series，不包含 lucky 自身
>>> corr_lucky = corr_lucky[corr_lucky>0.1].dropna()#篩選相關(guān)系數(shù)大于 0.1 的用戶(hù)
>>> for movie in gift.index:#遍歷所有 lucky 沒(méi)看過(guò)的電影
  prediction = []
  for other in corr_lucky.index:#遍歷所有與 lucky 相關(guān)系數(shù)大于 0.1 的用戶(hù)
   if not np.isnan(data.ix[other,movie]):
    prediction.append((data.ix[other,movie],corr_clean[lucky][other]))
  if prediction:
   gift[movie] = sum([value*weight for value,weight in prediction])/sum([pair[1] for pair in prediction])
 
 
>>> gift.dropna().order(ascending=False)#將 gift 的非空元素按降序排列
movie_id
3245  5.000000
2930  5.000000
2830  5.000000
2569  5.000000
1795  5.000000
981   5.000000
696   5.000000
682   5.000000
666   5.000000
572   5.000000
1420  5.000000
3338  4.845331
669   4.660464
214   4.655798
3410  4.624088
...
2833  1
2777  1
2039  1
1773  1
1720  1
1692  1
1538  1
1430  1
1311  1
1164  1
843   1
660   1
634   1
591   1
56   1
Name: 3945, Length: 2991, dtype: float64

          

?
補(bǔ)充

上面給出的示例都是些原型代碼，有很多可優(yōu)化的空間。比如 data 的行列轉(zhuǎn)換；比如測(cè)定 min_periods 時(shí)的方陣 foo 只需計(jì)算一半；比如有些 for 循環(huán)和相應(yīng)運(yùn)算可以用數(shù)組對(duì)象方法來(lái)實(shí)現(xiàn)（方法版比用戶(hù)自己編寫(xiě)的版本速度快很多）；甚至肯定還有一些 bug。另外這個(gè)數(shù)據(jù)集的體積還不算太大，如果再增長(zhǎng)一個(gè)數(shù)量級(jí)，那么就有必要針對(duì)計(jì)算密集的部分（如 corr）做進(jìn)一步優(yōu)化了，可以使用多進(jìn)程，或者 Cython/C 代碼。（或者換更好的硬件）

雖然協(xié)同過(guò)濾是一種比較省事的推薦方法，但在某些場(chǎng)合下并不如利用元信息推薦好用。協(xié)同過(guò)濾會(huì)遇到的兩個(gè)常見(jiàn)問(wèn)題是

1. ??? 稀疏性問(wèn)題――因用戶(hù)做出評(píng)價(jià)過(guò)少，導(dǎo)致算出的相關(guān)系數(shù)不準(zhǔn)確
2. ??? 冷啟動(dòng)問(wèn)題――因物品獲得評(píng)價(jià)過(guò)少，導(dǎo)致無(wú)“權(quán)”進(jìn)入推薦列表中

都是樣本量太少導(dǎo)致的。（上例中也使用了至少 200 的有效重疊評(píng)價(jià)數(shù)）因此在對(duì)于新用戶(hù)和新物品進(jìn)行推薦時(shí)，使用一些更一般性的方法效果可能會(huì)更好。比如給新用戶(hù)推薦更多平均得分超高的電影；把新電影推薦給喜歡類(lèi)似電影（如具有相同導(dǎo)演或演員）的人。后面這種做法需要維護(hù)一個(gè)物品分類(lèi)表，這個(gè)表既可以是基于物品元信息劃分的，也可是通過(guò)聚類(lèi)得到的。