基于矩陣分解協(xié)同過濾算法的評分預(yù)測

劉佳

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

關(guān)鍵詞：協(xié)同過濾;非負矩陣分解;奇異值分解

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

1 協(xié)同過濾推薦

協(xié)同過濾這一概念于1992年由Goldberg、Nicols、Oki及Terry首次提出[1]。推薦系統(tǒng)發(fā)展至今，協(xié)同過濾已經(jīng)成為最流行和最成熟的技術(shù)。它的基本思想是：利用已有用戶群過去的行為或意見預(yù)測當前用戶最可能喜歡哪些東西或?qū)δ男〇|西感興趣[2]。

2 實驗數(shù)據(jù)集和評測標準

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

3 基于NMF協(xié)同過濾推薦算法分析

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

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

4 基于SVD協(xié)同過濾推薦算法分析

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

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

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

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

如圖1所示，從以上三個算法的對比試驗可以得出，基于SVD協(xié)同過濾算法在時間性能上較基于NMF協(xié)同過濾算法具有較大的優(yōu)勢，但是準確性一般;基于NMF協(xié)同過濾算法預(yù)測準確度最差，而且時間消耗很大。而基于非負矩陣分解與奇異值分解混合過濾算法相對上述兩種方法有了很大的提升，在時間上優(yōu)于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. 推薦系統(tǒng)[M].人民郵電出版社，2013，11：2-83.