zhuzigege

本文引自http://blog.csdn.net/dustinsea/article/details/17394615

在設計實現推薦系統，選擇推薦算法時， 肯定會考慮協同過濾（CF）的使用，而CF中經常使用的兩種方法包括： neighbour-based方法和因式分解。 作為一個搜索推薦系統，百度關鍵詞系統中也使用了CF(包括neighbour-based和因式分解方法)為用戶推薦流量，考慮到可解釋性和工程上在hadoop上實現的便利性，最終主要使用了neighbour-based中的item-based方法。但學術上，因式分解會從全局考慮用戶投票的影響，所以理論和實踐上效果都會更好。本文主要結合之前對因式分解的調研理解及調研demo代碼， 介紹因式分解實現協同過濾的方法， 同時感興趣的同學可以下載源碼及MovieLens數據進行實驗。

注:

為了方便理解， 以下介紹均使用MovieLens 100K數據進行介紹（公司數據太大， 且包含過多預處理過程， 同時涉及泄密，你懂的：）

文中的代碼可從文章最后的參考內容鏈接中下載。

推薦算法對比基線的建立

要評估一個策略的好壞，就需要建立一個對比基線，以便后續觀察算法效果的提升。此處我們可以簡單地對推薦算法進行建模作為基線。假設我們的訓練數據為：  <user, item, rating>三元組， 其中user為用戶id， item為物品id(item可以是MovieLens上的電影，Amazon上的書， 或是百度關鍵詞工具上的關鍵詞), rating為user對item的投票分數， 其中用戶u對物品i的真實投票分數我們記為rui，基線(baseline)模型預估分數為bui，則可建模如下：

其中mu（希臘字母mu）為所有已知投票數據中投票的均值，bu為用戶的打分相對于平均值的偏差（如果某用戶比較苛刻，打分都相對偏低， 則bu會為負值；相反，如果某用戶經常對很多片都打正分， 則bu為正值）， bi為該item被打分時，相對于平均值得偏差。 bui則為基線模型對用戶u給物品i打分的預估值。該模型雖然簡單， 但其中其實已經包含了用戶個性化和item的個性化信息， 而且特別簡單（很多時候， 簡單就是一個非常大的特點， 特別是面對大規模數據時）

基線模型中， mu可以直接統計得到，我們的優化函數可以寫為：

其中參數lambda1及之后的式子是為了防止過擬合產生。 其中rui為已知的投票， mu可直接統計， 對每個用戶的參數bu, 對每個item的bi可求（相當于AX=B，求X，此處X即為bu, bi，可使用最小二乘法， 例如可使用Numerical Recipes: The Art of Scientific Computing中提供的優化函數） ，當然， 最簡單的方法就是直接根據當前的觀測值， 直接統計出bu 和bi， 統計方式如下：

其中lambda2, lambda3為手動設定參數（在MovieLens上為20左右效果比較好， 才參數相當于降低投票較少的用戶， 以及被投票較少的item對整體預估效果的影響）， R(u)為用戶u投了的item的rating集合，R(i)，為投票給item i的rating集合。

基線實驗結果

還有一種更簡便的方法， 就是直接使用user，item的rating的平均值直接預估bi，bu，例如直接計算bu = sum(Ru)/len(Ru)，其中Ru為用戶u投票的集合， sum(Ru)為這些rating值得和， len(Ru)為該集合大小。bi = sum(Ri)/len(Ri)， 其中Ri為用戶i被投票的集合， sum(Ri)為這些rating的分值之和， len(Ri)為這個集合的大小。我們將此方法記為baseline1，上文描述的方法記為baseline2。 以下為兩種方法在不同lambdau，lambdai值下的具體表現（其中兩個lambda值在實際應用中可以根據代價進行全空間搜索最優解）， 具體分值代表RMSE。

圖： 兩種基線的RMSE效果表現

可以看到，隨著lambdai和lambdau的增長， 兩種方法的RMSE均在下降， 且效果上， baseline2 優于baseline1。

基線源代碼

源碼文件對應為RecBaseLine.h，其中RecBaseLine封裝了baseline1的實現， RecBaseLineAdv封裝了baseline2策略的實現， 而每個推薦算法均繼承自RecTask， 所有每個推薦算法除了接受該算法特有的參數外，還必須提供以下接口。

其中代碼在上傳時添加了部分注釋。

因式分解實現協同過濾

上文中實現的兩種基線算法，僅僅孤立地去考慮user， item的投票偏差， 并沒有將二者建立內在聯系。此時我們可以對這種內在聯系通過隱主題進行建模。 最經常使用的方式莫過于SVD。

以MovieLens電影推薦為例，SVD(Singular Value Decomposition)的想法是根據已有的評分情況，分析出評分者對各個因子的喜好程度以及電影包含各個因子的程度，最后再反過來根據分析結果。

使用SVD對問題進行建模

SVD的想法抽象點來看就是將一個N行M列的評分矩陣R（R[u][i]代表第u個用戶對第i個物品的評分），分解成一個N行F列的用戶因子矩陣P（P[u][k]表示用戶u對因子k的喜好程度）和一個M行F列的物品因子矩陣Q（Q[i][k]表示第i個物品的因子k的程度）。用公式來表示就是
R = P * T(Q) ，其中T(Q)表示Q矩陣的轉置

下面是將評分矩陣R分解成用戶因子矩陣P與物品因子矩陣Q的一個例子。R的元素數值越大，表示用戶越喜歡這部電影。P的元素數值越大，表示用戶越喜歡對應的因子。Q的元素數值越大，表示物品對應的因子程度越高。分解完后，就能利用P，Q來預測Zero君對《七夜》的評分了。按照這個例子來看，Zero君應該會給《七夜》較低的分數。因為他不喜歡恐怖片。

圖： 推薦問題的因式分解建模

實際上，我們給一部電影評分時，除了考慮電影是否合自己口味外，還會受到自己是否是一個嚴格的評分者和這部電影已有的評分狀況影響。例如：一個嚴格評分者給的分大多數情況下都比一個寬松評分者的低。你看到這部電影的評分大部分較高時，可能也傾向于給較高的分。在SVD中，口味問題已經有因子來表示了，但是剩下兩個還沒有相關的式子表示。因此有必要加上相關的部分，提高模型的精準度。改進后的SVD的公式如下：

其中mu表示所有電影的平均分，bu表示用戶評分偏離mu的程度，bi表示電影評分偏離mu的程度，P，Q意思不變。特別注意，這里除了mu之后，其它幾個都是向量。其中qi， pu的維度， 就是隱主題的維度。

分解完后，即（1）式中的五個參數都有了正確的數值后，就可以用來預測分數了。假設我們要預測用戶u對電影i的評分：

加入了防止過擬合的lambda參數后， 我們的優化函數為：

有了這個優化目標函數后， 就可以使用較多的手段來進行優化了。

以下主要使用梯度下降法解優化目標函數。具體的公式推導可參見論文。同時還可以使用ALS算法進行求解（該方法已經融合進mahout，后續會有專門文章對該算法進行介紹并給出實驗結果）

最終推導出的求解公式為：

在實現時， 設定最大的迭代次數， 以及收斂的誤差， 即可經過迭代球接觸bu, bi, qi, pu

因式分解同過濾代碼實現

因式分解的實現使用了RecTask， 故封裝使用了一致的接口。具體感興趣的同學可直接review source code

圖：使用梯度下降求解因式分解CF推薦。

因式分解CF效果對比

此處就僅給出兩組程序直接運行出來的結果及對應參數， 可以看到， 在latent factor的維度為30， 設定gama和lambda后， RMSE就降低至0.903105,效果比較明顯。

以下為具體配置參數：

task:SGD30,mae:0.687782,rmse:0.903105
mu:3.528350,lambda:0.200000,gama:0.020000,min_res_err:0.010000,max_iter_num:10000,fea_dim:30

上文描述算法的hadoop版本未上傳網盤， 如感興趣可以郵件溝通。

參考文獻：

Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008: 426-434.

Zhou Y, Wilkinson D, Schreiber R, et al. Large-scale parallel collaborative filtering for the netflix prize[M]//Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg, 2008: 337-348.

Bell R, Koren Y, Volinsky C. Modeling relationships at multiple scales to improve accuracy of large recommender systems[C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2007: 95-104.

Shapira B. Recommender systems handbook[M]. Springer, 2011.

MovieLens數據集： http://grouplens.org/datasets/movielens/

文中描述算法代碼實現及評測框架參見：http://pan.baidu.com/share/link?shareid=2198676312&uk=1493671608

百度關鍵詞工具介紹參見：http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596

也可關注我的微博：  weibo.com/dustinsea

或是直接訪問： http://semocean.com