基于矩陣分解協同過濾算法的評分預測

劉佳

摘 ?要：文章以GroupLens項目組提供的MovieLens數據集作為測試數據集，通過實驗實現了協同過濾算法中傳統的非負矩陣分解（NMF）算法及奇異值分解（SVD）模型算法，結合兩個算法的優點，提出了基于非負矩陣分解與奇異值分解的混合推薦算法。最后采用均方根誤差RMSE驗證了算法的有效性，證明了文章所提的算法是解決矩陣的稀疏性問題的有效手段，在評分預測問題上較前兩種算法有明顯的提高。

關鍵詞：協同過濾;非負矩陣分解;奇異值分解

近些年，隨著計算機技術和互聯網技術的大規模發展，人們逐漸從信息匱乏的時代走進了信息爆炸的時代。網站運營商如何采用更有效的手段使得有價值的信息展現在用戶面前，已經成為計算機行業的一個重要課題，同時也是個性化推薦系統開發的重要目標之一。推薦算法是推薦系統的核心，它的好壞決定了推薦系統效率的高低，協同過濾算法已經成為當今最流行和最成熟的推薦算法。

1 協同過濾推薦

協同過濾這一概念于1992年由Goldberg、Nicols、Oki及Terry首次提出[1]。推薦系統發展至今，協同過濾已經成為最流行和最成熟的技術。它的基本思想是：利用已有用戶群過去的行為或意見預測當前用戶最可能喜歡哪些東西或對哪些東西感興趣[2]。

2 實驗數據集和評測標準

文章所采用的是MovieLens網站所提供的1M數據集，簡稱為ML 1M。MovieLens是一個歷史悠久的推薦系統，由美國Minnesota大學計算機科學與工程學院的GroupLens項目組創辦，是一個非商業性質的、以研究為目的的實驗性站點。MovieLens主要使用Collaborative Filtering和Association Rules相結合的技術，向用戶推薦他們感興趣的電影。文章采用評測方法中的均方根誤差（RMSE）作為評測標準，用于評價算法的預測性能。

3 基于NMF協同過濾推薦算法分析

文章通過實驗實現了基于非負矩陣分解的協同過濾推薦算法，在該算法中需要將原始用戶評分矩陣分解為用戶集合的矩陣和電影集合的矩陣，通過計算它們特征向量的點積預測評分。分解原始用戶評分矩陣采用的是梯度下降法通過迭代逐漸減小預測評分和真實矩陣的誤差直至收斂而得到。在本實驗中梯度下降常數設為0.0002。采用均方根誤差RMSE計算誤差，即循環地計算每一條目的誤差，最后將其結果相加。

為了選取合適的非負矩陣分解算法的參數n的值，需要通過實驗觀察不同的迭代次數對RMSE的影響。最后通過實驗得出n>=100時，RMSE的值趨于平緩，達到最小為1.131，也就是n的值對于RMSE值的變化不再敏感，所以選擇n=100。通過實驗可以看出雖然NMF使矩陣的維度得到了有效的降低，但是在算法執行過程中收斂速度很慢，需要200次的迭代才能得出比較滿意的結果，時間代價太大，在MovieLens 1M數據集上需要2730.2S才能實現最后評分預測。

4 基于SVD協同過濾推薦算法分析

文章所采用的是2006年Simon Funk提出了一個新的SVD分解算法，稱為Funk-SVD，在該算法中有幾個非常重要的參數，如學習速率、特征矩陣維度k及user特征矩陣和item特征矩陣的初值。本實驗中選取k為100。User特征矩陣和item特征矩陣是通過原矩陣分解得到的，而此分解是一個NP問題，也就是得不到全局最優解，只能從兩個矩陣的初值開始，沿著梯度方向向下走，得到局部最優解，所以user特征矩陣和item特征矩陣初值的確定關系到局部最優解的效果，在本實驗中定義其初值為0.1?rand（0，1）/sqrt（k）。隨著迭代次數的增加，RMSE的值也在不斷變化，當迭代次數為100時，RMSE達到最小值0.871069。雖然定義迭代次數為100，實際上只進行了48次。

基于奇異值分解的協同過濾推薦算法，在每次迭代后RMSE的值都減小了，說明模型的性能也得到了很大提高，在第一次迭代后，RMSE的值從0.947080下降到0.935648，性能提高了1%;經過十次迭代后，RMSE的值下降到0.914292，性能提高了3%;經過四十八次迭代后，RMSE的值下降到0.871069，性能提高了7%。但是在實驗過程中，RMSE值的下降速度越來越緩慢，需要很多的迭代次數和執行時間。

5 基于非負矩陣分解與奇異值分解混合推薦算法分析

通過對兩種算法原理的論述，兩種算法各有其優點，為了更好地提高預測的準確度，解決矩陣的稀疏性問題，文章提出了基于非負矩陣分解與奇異值分解混合推薦算法。非負矩陣分解算法通過迭代可以得到用戶矩陣和物品矩陣，通過它們特征向量的乘積可以得到初步的用戶與測評分矩陣，使得原始的稀疏矩陣變得更加稠密，但是其預測準確度并不高。所以將非負矩陣分解得到的用戶特征矩陣作為K-均值聚類算法的輸入，將用戶集分成不同的簇，每個簇內的用戶都具有較高的相似性，由于SVD算法具有較高的預測準確度，所以對每個簇內的用戶數據進行SVD分解，最后得到新的用戶評分矩陣。本算法實際上是對上述兩種算法的結合，所以在實驗過程中需要考慮非負矩陣分解算法中的迭代次數n，設定迭代次數n為100，梯度下降常數為0.002。奇異值分解時學習速率=學習速率*0.9、特征矩陣維度k=100及user特征矩陣和item特征矩陣的初值為0.1?rand（0，1）/sqrt（k）。在算法中需要通過K-均值聚類算法對用戶集進行分類，通過實驗得出聚類的個數等于60時RMSE的值最小，也就是可以達到最好的準確度，所以在此改進算法中設定K值為60。

如圖1所示，從以上三個算法的對比試驗可以得出，基于SVD協同過濾算法在時間性能上較基于NMF協同過濾算法具有較大的優勢，但是準確性一般;基于NMF協同過濾算法預測準確度最差，而且時間消耗很大。而基于非負矩陣分解與奇異值分解混合過濾算法相對上述兩種方法有了很大的提升，在時間上優于NMF算法與SVD算法，準確性要高于前兩種算法。

參考文獻

[1]David Goldberg， David Nichols， Brian M. Oki and Douglas Terry. Using collaborative filtering to weave an information tapestry. Communications of the ACM[J].1992，35（12）：61-70.

[2]Dietmar Jannach， Markus Zanker，Alexander Felfernig， Gerhard Friedrich. 推薦系統[M].人民郵電出版社，2013，11：2-83.