劉佳

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

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

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

1 協(xié)同過濾推薦

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

2 實(shí)驗(yàn)數(shù)據(jù)集和評測標(biāo)準(zhǔn)

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

[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.