劉佳

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

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

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

1 協(xié)同過(guò)濾推薦

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

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

文章所采用的是MovieLens網(wǎng)站所提供的1M數(shù)據(jù)集，簡(jiǎn)稱為ML 1M。MovieLens是一個(gè)歷史悠久的推薦系統(tǒng)，由美國(guó)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ù)，向用戶推薦他們感興趣的電影。文章采用評(píng)測(cè)方法中的均方根誤差（RMSE）作為評(píng)測(cè)標(biāo)準(zhǔn)，用于評(píng)價(jià)算法的預(yù)測(cè)性能。

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

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

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

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

文章所采用的是2006年Simon Funk提出了一個(gè)新的SVD分解算法，稱為Funk-SVD，在該算法中有幾個(gè)非常重要的參數(shù)，如學(xué)習(xí)速率、特征矩陣維度k及user特征矩陣和item特征矩陣的初值。本實(shí)驗(yàn)中選取k為100。User特征矩陣和item特征矩陣是通過(guò)原矩陣分解得到的，而此分解是一個(gè)NP問(wèn)題，也就是得不到全局最優(yōu)解，只能從兩個(gè)矩陣的初值開(kāi)始，沿著梯度方向向下走，得到局部最優(yōu)解，所以u(píng)ser特征矩陣和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é)同過(guò)濾推薦算法，在每次迭代后RMSE的值都減小了，說(shuō)明模型的性能也得到了很大提高，在第一次迭代后，RMSE的值從0.947080下降到0.935648，性能提高了1%;經(jīng)過(guò)十次迭代后，RMSE的值下降到0.914292，性能提高了3%;經(jīng)過(guò)四十八次迭代后，RMSE的值下降到0.871069，性能提高了7%。但是在實(shí)驗(yàn)過(guò)程中，RMSE值的下降速度越來(lái)越緩慢，需要很多的迭代次數(shù)和執(zhí)行時(shí)間。

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

通過(guò)對(duì)兩種算法原理的論述，兩種算法各有其優(yōu)點(diǎn)，為了更好地提高預(yù)測(cè)的準(zhǔn)確度，解決矩陣的稀疏性問(wèn)題，文章提出了基于非負(fù)矩陣分解與奇異值分解混合推薦算法。非負(fù)矩陣分解算法通過(guò)迭代可以得到用戶矩陣和物品矩陣，通過(guò)它們特征向量的乘積可以得到初步的用戶與測(cè)評(píng)分矩陣，使得原始的稀疏矩陣變得更加稠密，但是其預(yù)測(cè)準(zhǔn)確度并不高。所以將非負(fù)矩陣分解得到的用戶特征矩陣作為K-均值聚類算法的輸入，將用戶集分成不同的簇，每個(gè)簇內(nèi)的用戶都具有較高的相似性，由于SVD算法具有較高的預(yù)測(cè)準(zhǔn)確度，所以對(duì)每個(gè)簇內(nèi)的用戶數(shù)據(jù)進(jìn)行SVD分解，最后得到新的用戶評(píng)分矩陣。本算法實(shí)際上是對(duì)上述兩種算法的結(jié)合，所以在實(shí)驗(yàn)過(guò)程中需要考慮非負(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）。在算法中需要通過(guò)K-均值聚類算法對(duì)用戶集進(jìn)行分類，通過(guò)實(shí)驗(yàn)得出聚類的個(gè)數(shù)等于60時(shí)RMSE的值最小，也就是可以達(dá)到最好的準(zhǔn)確度，所以在此改進(jìn)算法中設(shè)定K值為60。

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