基于FunkSVD矩陣分解和相似度矩陣的推薦算法

王 運(yùn) 倪 靜 馬 剛

(上海理工大學(xué)管理學(xué)院 上海 200093)

0 引 言

近年來，互聯(lián)網(wǎng)呈現(xiàn)出迅猛的發(fā)展趨勢(shì)，用戶接觸到的信息也變得越來越多，如何從海量數(shù)據(jù)中找到用戶感興趣的內(nèi)容變得至關(guān)重要。對(duì)于用戶來說，可以節(jié)省搜尋時(shí)間，提高效率；對(duì)于企業(yè)來說，可以提升用戶滿意度，也為企業(yè)吸引更多的用戶。因此，合適的推薦算法顯得尤為重要。針對(duì)這一目標(biāo)，廣大專家學(xué)者提出了大量的相關(guān)算法，其中最廣泛使用的有基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法和混合推薦算法等[1-2]。基于內(nèi)容的推薦算法可以根據(jù)用戶的已有數(shù)據(jù)找出興趣相似的物品進(jìn)行推薦，但是需要用戶有足夠多的數(shù)據(jù)；協(xié)同過濾推薦算法利用用戶對(duì)物品行為的相似性找出相似用戶進(jìn)行推薦，最為經(jīng)典；而混合推薦算法是上述算法的融合，推薦準(zhǔn)確性更好。

但是，需要處理的用戶數(shù)據(jù)往往面臨稀疏等缺點(diǎn)，針對(duì)這些問題，文獻(xiàn)[3]利用用戶-標(biāo)簽-資源三維關(guān)系刻畫用戶偏好，并以此來找出相似用戶從而進(jìn)行Top-N推薦；文獻(xiàn)[4]采用社交網(wǎng)絡(luò)中的信息及用戶標(biāo)簽數(shù)據(jù)來計(jì)算用戶之間的相似度并作推薦，有效克服了數(shù)據(jù)稀疏的缺點(diǎn)；文獻(xiàn)[5]提出將棧式降噪自編碼器運(yùn)用于基于內(nèi)容的推薦模型中，可以深層次挖掘用戶之間的潛在關(guān)系，同時(shí)與基于標(biāo)簽的協(xié)同過濾算法結(jié)合在一起進(jìn)行推薦。根據(jù)上述文獻(xiàn)中的方法可以在用戶數(shù)據(jù)稀疏時(shí)較好地求出用戶之間的相似度，然而，當(dāng)一個(gè)用戶沒有數(shù)據(jù)或者數(shù)據(jù)極少時(shí)難以準(zhǔn)確計(jì)算出用戶之間的相似度。本文采用了FunkSVD矩陣分解與相似度矩陣的推薦算法來計(jì)算用戶相似度。考慮到用戶的偏好因素，利用用戶評(píng)分?jǐn)?shù)據(jù)與物品標(biāo)簽數(shù)據(jù)計(jì)算用戶之間的相似度，同時(shí)，存在用戶之間評(píng)分?jǐn)?shù)據(jù)過少的情況，因此，將得到的用戶相似度矩陣進(jìn)行FunkSVD矩陣分解，加權(quán)矩陣分解前后的相似度值并做評(píng)分預(yù)測(cè)。經(jīng)過Movielens數(shù)據(jù)集的實(shí)驗(yàn)表明，該算法的評(píng)分預(yù)測(cè)準(zhǔn)確性得到了提升。

1 相關(guān)理論

1.1 傳統(tǒng)基于用戶的協(xié)同過濾推薦

在眾多推薦算法中，基于用戶的協(xié)同過濾推薦算法[6]被使用次數(shù)最多，并且效果最為理想，其主要思想為相似的用戶具有相同的偏好，所以推薦的準(zhǔn)確性更好。當(dāng)兩個(gè)用戶對(duì)同一物品的評(píng)分越接近，則說明用戶之間的相似性越高[7]，用戶之間共同評(píng)分的物品數(shù)越多，計(jì)算的相似度值也會(huì)更準(zhǔn)確。其相似度計(jì)算方法如下：

(1)

(2)

1.2 FunkSVD矩陣分解

在推薦系統(tǒng)中，包含許多用戶和物品的數(shù)據(jù)，但是，單一用戶的評(píng)分物品數(shù)經(jīng)常是稀疏的，通過將用戶對(duì)所有物品的評(píng)分值預(yù)測(cè)出來，可以將評(píng)分值高的物品推薦給用戶，間接達(dá)到推薦的目的。對(duì)于填充用戶物品評(píng)分矩陣這一問題，可以有很多的解決辦法，其中矩陣分解較為理想[8]。矩陣分解法有傳統(tǒng)的奇異值分解、BiasSVD算法、SVD++算法和FunkSVD算法[9]。奇異值分解簡(jiǎn)單直接，但是需要用戶物品評(píng)分矩陣中沒有缺失值，同時(shí)當(dāng)數(shù)據(jù)量很大時(shí)計(jì)算十分耗時(shí)；BiasSVD在計(jì)算中考慮了其他限制條件，比如若有干擾用戶評(píng)分因素的情況存在，則只適合應(yīng)用在特定的場(chǎng)景；SVD++在BiasSVD的基礎(chǔ)上又做了增強(qiáng)，增加考慮用戶的隱私反饋，算法較為復(fù)雜，在實(shí)際應(yīng)用中較少出現(xiàn)；而FunkSVD算法是奇異值分解的改進(jìn)，避開了數(shù)據(jù)稀疏的缺點(diǎn)，同時(shí)將矩陣分解成兩個(gè)新的矩陣計(jì)算時(shí)間較短，在實(shí)際中應(yīng)用十分廣泛[9]。

正如前文所述，F(xiàn)unkSVD是傳統(tǒng)奇異值分解的改進(jìn)版，它可以將目標(biāo)矩陣分解成兩個(gè)矩陣。將期望矩陣M進(jìn)行如下分解：

(3)

(4)

(5)

式中：λ為正則化系數(shù)，需要調(diào)參。對(duì)于這個(gè)優(yōu)化問題，一般通過梯度下降法進(jìn)行優(yōu)化得到結(jié)果。

分別對(duì)pi、qj求導(dǎo)得到：

(6)

(7)

則在梯度下降迭代時(shí)，pi、qj的迭代公式為：

(8)

(9)

通過迭代最終可以得到P和Q，進(jìn)而用于用戶評(píng)分預(yù)測(cè)。

然而，本文沒有將FunkSVD應(yīng)用在用戶評(píng)分矩陣中，而是提出了一種新的思路，將其應(yīng)用在用戶的相似度矩陣中，并且考慮到用戶偏好的情況，在得到初始相似度矩陣時(shí)利用了用戶評(píng)分?jǐn)?shù)據(jù)與物品標(biāo)簽數(shù)據(jù)進(jìn)行綜合計(jì)算。同時(shí)，提出了新的模型將矩陣分解后的相似度值再次加權(quán)，有效避免了用戶數(shù)據(jù)稀疏的情況。

2 用戶相似度計(jì)算

對(duì)于基于用戶的推薦算法而言，用戶相似度計(jì)算的準(zhǔn)確性高低是核心所在，同時(shí)，在本文提出的算法中也是極其重要的一步。

2.1 用戶物品標(biāo)簽相似度

傳統(tǒng)推薦算法是按照用戶物品評(píng)分?jǐn)?shù)據(jù)來計(jì)算用戶之間的相似度，當(dāng)兩個(gè)用戶對(duì)同一物品的評(píng)分相似時(shí)則說明兩者具有極高的相似性，同時(shí)，共同評(píng)分物品數(shù)越多，則可以更精確地刻畫出用戶之間的相似度，與式(1)相同(假設(shè)得到的相似度為sim(u,v)item)[10]。

當(dāng)數(shù)據(jù)稀疏時(shí)可以根據(jù)用戶偏好來計(jì)算用戶之間的相似度，用戶的偏好即為標(biāo)簽。例如，當(dāng)用戶A對(duì)物品1的評(píng)分為4分，物品1由標(biāo)簽a與b組成，則可以認(rèn)為用戶A對(duì)標(biāo)簽a與b的評(píng)分均為4分，如果對(duì)同一標(biāo)簽有多次評(píng)分，則取值為它們的平均值。用戶之間的標(biāo)簽相似度計(jì)算方法與式(1)類似，式(1)中的共同評(píng)分物品集合對(duì)應(yīng)為共同標(biāo)簽評(píng)分集合即可(假設(shè)得到的相似度記為sim(u,v)tag)[11]。

根據(jù)前文計(jì)算的用戶物品評(píng)分相似度與用戶標(biāo)簽相似度可以計(jì)算出用戶的物品標(biāo)簽相似度[12]，計(jì)算方法如下：

(10)

式中:con為用戶u與用戶v的共同評(píng)分物品數(shù)；φ為參數(shù)，用于平衡用戶物品評(píng)分相似度與用戶標(biāo)簽評(píng)分相似度對(duì)物品標(biāo)簽相似度值計(jì)算的影響程度，實(shí)驗(yàn)中會(huì)根據(jù)數(shù)據(jù)調(diào)出。當(dāng)兩個(gè)用戶的共同評(píng)分物品數(shù)一定時(shí)，參數(shù)值越小，則用戶物品評(píng)分相似度越接近用戶的物品標(biāo)簽相似度[13]；反之，則需要用戶標(biāo)簽相似度來共同刻畫。

2.2 FunkSVD矩陣分解相似度

根據(jù)式(10)可以計(jì)算出任意兩個(gè)用戶之間的相似度，經(jīng)過一系列的計(jì)算可以得到用戶的相似度矩陣，如表1所示。用戶與自身的相似度為1，與其他用戶之間的相似度滿足0≤sim(u,v)item_tag≤1。

表1 用戶相似度矩陣

當(dāng)兩個(gè)用戶的最小評(píng)分物品數(shù)非常少時(shí)，即小于參數(shù)?(與后文中的?一致，實(shí)驗(yàn)中會(huì)根據(jù)數(shù)據(jù)調(diào)出)，則可認(rèn)為由式(10)計(jì)算的相似度不夠準(zhǔn)確，并將相應(yīng)的用戶相似度記為0，如將表1中的用戶1與用戶2，用戶2與用戶3之間的相似度值替換為0，最終可以得到一個(gè)新的用戶相似度矩陣。然后，利用FunkSVD對(duì)其進(jìn)行矩陣分解，生成的相似度矩陣如表2所示，并記用戶u與用戶v之間的相似度值為sim(u,v)matrix。

表2 矩陣分解生成用戶相似度矩陣

2.3 用戶綜合相似度計(jì)算

根據(jù)用戶物品標(biāo)簽數(shù)據(jù)可以計(jì)算出用戶的相似度矩陣，同時(shí)，F(xiàn)unkSVD矩陣分解方法可以計(jì)算出一個(gè)新的用戶相似度矩陣，所以，最終的用戶綜合相似度計(jì)算方法為：

(11)

式中:?為參數(shù)，用于調(diào)節(jié)物品標(biāo)簽相似度與矩陣分解后的相似度對(duì)綜合相似度值的影響程度，實(shí)驗(yàn)中根據(jù)數(shù)據(jù)調(diào)出；m為用戶u的最小評(píng)分物品數(shù)；n為用戶v的最小評(píng)分物品數(shù)。當(dāng)兩個(gè)用戶的最小評(píng)分物品數(shù)一定時(shí)，參數(shù)值越小，則由物品標(biāo)簽算出的相似度值可以更好地表示為用戶之間的綜合相似度；反之，則需要由矩陣分解算出的相似度值來近似表達(dá)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)所用數(shù)據(jù)為Movielens 100K數(shù)據(jù)集，MovieLens是由明尼蘇達(dá)州大學(xué)的GroupLens項(xiàng)目組開發(fā)的，其中包含943名用戶對(duì)1 682部電影的評(píng)分，評(píng)分記錄多達(dá)100 000條。另外，每位用戶對(duì)超過20部電影有評(píng)分，數(shù)據(jù)集有動(dòng)作、冒險(xiǎn)、兒童，紀(jì)錄片等18種標(biāo)簽[14]。實(shí)驗(yàn)中，將數(shù)據(jù)集按照8∶2分為訓(xùn)練集與測(cè)試集。并采用平均絕對(duì)誤差(Mean Absolute Error，MAE)作為評(píng)價(jià)指標(biāo)，衡量算法的優(yōu)劣。設(shè)預(yù)測(cè)的用戶評(píng)分集合為{p1,p2,p3,…,pn}，對(duì)應(yīng)的實(shí)際用戶評(píng)分集合為{q1,q2,q3,…,qn}[10]，則平均絕對(duì)偏差MAE為：

(12)

式中：pi為用戶對(duì)物品i的預(yù)測(cè)評(píng)分；qi為用戶對(duì)物品i的實(shí)際評(píng)分。式(12)的值越小，說明預(yù)測(cè)值與實(shí)際值越接近，算法的準(zhǔn)確性也就越高。

3.2 實(shí)驗(yàn)步驟

本文提出了基于FunkSVD矩陣分解和相似度矩陣的推薦算法，該算法在考慮到用戶偏好的同時(shí)有效地緩解了用戶數(shù)據(jù)的稀疏性問題。在采用Movielens 100K數(shù)據(jù)集的前提下，算法步驟如下：

步驟1根據(jù)用戶評(píng)分?jǐn)?shù)據(jù)計(jì)算用戶之間的用戶物品評(píng)分相似度；

步驟2根據(jù)用戶的評(píng)分?jǐn)?shù)據(jù)及物品標(biāo)簽數(shù)據(jù)計(jì)算用戶的標(biāo)簽評(píng)分相似度；

步驟3利用式(10)對(duì)步驟1和步驟2中的相似度值進(jìn)行加權(quán)組合，所得即為用戶的物品標(biāo)簽相似度，同時(shí)，得到一個(gè)最初的用戶相似度矩陣；

步驟4將步驟3相似度矩陣中兩個(gè)用戶最小評(píng)分物品數(shù)小于參數(shù)?的相似度值設(shè)為0，并對(duì)修改后的相似度矩陣進(jìn)行矩陣分解生成新的用戶相似度矩陣；

步驟5對(duì)于步驟3和步驟4中的用戶相似度矩陣，對(duì)其中任意兩個(gè)相對(duì)應(yīng)的相似度值利用式(11)進(jìn)行加權(quán)計(jì)算，最終生成用戶的綜合相似度矩陣；

步驟6根據(jù)用戶的綜合相似度矩陣對(duì)目標(biāo)用戶采用式(2)進(jìn)行評(píng)分預(yù)測(cè)；

步驟7對(duì)預(yù)測(cè)的結(jié)果進(jìn)行平均絕對(duì)誤差分析，衡量算法優(yōu)劣。

經(jīng)過上述步驟可以測(cè)算出此算法的評(píng)分預(yù)測(cè)準(zhǔn)確性高低，同時(shí)，將與其他算法進(jìn)行比較來驗(yàn)證該算法相對(duì)優(yōu)劣。

3.3 參數(shù)調(diào)整

本文的算法在求解參數(shù)時(shí)經(jīng)過了大量的實(shí)驗(yàn)。對(duì)于式(11)，由于參數(shù)較多，可以分為前后兩部分進(jìn)行調(diào)試，對(duì)于用戶物品標(biāo)簽相似度中的參數(shù)，只要存在參數(shù)φ使得用戶物品標(biāo)簽相似度作為用戶的最終相似度時(shí)結(jié)果最優(yōu)，則該參數(shù)為最優(yōu)參數(shù)。同理，可得公式后半部分的最優(yōu)參數(shù)，將求解后的參數(shù)代入式(11)后可再由實(shí)驗(yàn)算出參數(shù)?。

在用戶物品標(biāo)簽相似度的計(jì)算中，參數(shù)φ可以平衡用戶物品評(píng)分相似度與用戶標(biāo)簽相似度對(duì)物品標(biāo)簽相似度值計(jì)算的影響程度。其值越小，則物品評(píng)分相似度可以近似刻畫用戶的物品標(biāo)簽相似度；反之，用標(biāo)簽相似度來描述較為合適。經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)參數(shù)φ變化跨度為10時(shí)MAE的值變化較為直觀，同時(shí),最優(yōu)的幾組數(shù)據(jù)在10到40之間，因此，不同參數(shù)φ與相似用戶數(shù)下MAE值的變化情況如圖1所示。

圖1 不同參數(shù)φ及相似用戶數(shù)對(duì)應(yīng)MAE統(tǒng)計(jì)圖

根據(jù)圖1中數(shù)據(jù)可以發(fā)現(xiàn)，當(dāng)參數(shù)為10或20時(shí)，MAE值的變化較為接近，且20較好；當(dāng)參數(shù)為30時(shí)，MAE的值整體較大；當(dāng)參數(shù)為40時(shí)，整體值最大。圖中數(shù)據(jù)也說明參數(shù)取值小于20時(shí)，參數(shù)值越小，用戶物品評(píng)分相似度作為用戶的物品標(biāo)簽相似度會(huì)導(dǎo)致評(píng)分預(yù)測(cè)越不準(zhǔn)確；參數(shù)取值大于20時(shí)，參數(shù)值越大，用戶標(biāo)簽相似度來補(bǔ)充計(jì)算用戶的物品標(biāo)簽相似度會(huì)使相似度不準(zhǔn)確，而預(yù)測(cè)結(jié)果也會(huì)隨之變差。最終，最合適的參數(shù)φ值應(yīng)為20。

在FunkSVD矩陣分解的計(jì)算中，經(jīng)過多次實(shí)驗(yàn)表明參數(shù)α為0.1、λ為0.02時(shí)結(jié)果較好。同時(shí)，分解的矩陣存在維度K，通常而言，維度K取值很小時(shí)矩陣分解的效果就已經(jīng)很好，且由多次實(shí)驗(yàn)發(fā)現(xiàn)最優(yōu)解在10以內(nèi)，因此可得圖2所示數(shù)據(jù)。

圖2 不同參數(shù)K及相似用戶數(shù)對(duì)應(yīng)MAE統(tǒng)計(jì)圖

由圖2可知，當(dāng)參數(shù)K值大于6時(shí)，參數(shù)值越大，不同相似用戶數(shù)下的MAE值整體越大，即結(jié)果越差。同時(shí)參數(shù)值小于6時(shí)，MAE值雖然整體較為接近取為6的值，但依然較差，固最優(yōu)參數(shù)K取值應(yīng)為6。

式(11)中，存在參數(shù)?，當(dāng)兩個(gè)用戶的最小評(píng)分物品數(shù)一定時(shí)，參數(shù)值越小，則物品標(biāo)簽相似度作為用戶的綜合相似度結(jié)果較好；反之，需要矩陣分解后的相似度作為補(bǔ)充，即加權(quán)組合才可以。多次實(shí)驗(yàn)發(fā)現(xiàn)最優(yōu)的幾組數(shù)據(jù)在參數(shù)值取為10到40的時(shí)候產(chǎn)生，可得圖3所示數(shù)據(jù)。

圖3 不同參數(shù)?及相似用戶數(shù)對(duì)應(yīng)的MAE統(tǒng)計(jì)圖

由圖3可以得出：當(dāng)參數(shù)值從10到30時(shí)，MAE的值整體逐漸變小；當(dāng)值為40時(shí)，MAE整體變?yōu)樽畲?。這說明了當(dāng)參數(shù)值為30時(shí)，用戶的物品標(biāo)簽相似度作為用戶綜合相似度會(huì)使用戶評(píng)分預(yù)測(cè)結(jié)果較好，參數(shù)值過小，則用戶物品標(biāo)簽相似度的計(jì)算不夠準(zhǔn)確；參數(shù)值過大，矩陣分解后的相似度值作為補(bǔ)充會(huì)使最終的評(píng)分預(yù)測(cè)準(zhǔn)確性降低。所以，最合適的參數(shù)?應(yīng)取值為30。

3.4 算法比較

本文的推薦算法通過準(zhǔn)確計(jì)算用戶之間的相似度值從而達(dá)到提高用戶評(píng)分預(yù)測(cè)準(zhǔn)確性的目的，為了驗(yàn)證該算法的有效性，將基于FunkSVD和相似度矩陣的推薦算法(recommendation algorithm based on FunkSVD matrix decomposition and similarity matrix，F(xiàn)SM-RA)與其他幾種經(jīng)典的推薦算法進(jìn)行比較，進(jìn)行比較的推薦算法有：Tag-CF(基于標(biāo)簽的協(xié)同過濾推薦算法)、Item-CF(基于物品的協(xié)同過濾推薦算法)和IT-CF(基于物品與標(biāo)簽的混合協(xié)同過濾推薦算法)。實(shí)驗(yàn)結(jié)果如圖4所示。

由圖4可知：基于物品的協(xié)同過濾推薦算法準(zhǔn)確性最差，而且隨著相似用戶數(shù)的增加沒有顯著變化；基于標(biāo)簽的協(xié)同過濾推薦算法的準(zhǔn)確性比基于物品的協(xié)同過濾推薦算法的較高。同時(shí)，隨著相似用戶數(shù)的增加，評(píng)分預(yù)測(cè)的準(zhǔn)確性會(huì)有所提升，可能在該數(shù)據(jù)集下，利用用戶偏好來計(jì)算用戶之間的相似度比基于物品評(píng)分效果較好；而基于物品和標(biāo)簽的混合協(xié)同過濾推薦算法與基于標(biāo)簽的相比，準(zhǔn)確性稍微高一點(diǎn)，隨著相似用戶數(shù)的增加準(zhǔn)確性有所增加，也說明了利用用戶評(píng)分與用戶偏好綜合計(jì)算相似度效果更好；最后，對(duì)于本文中的算法，即基于FunkSVD矩陣分解和相似度矩陣的推薦算法，評(píng)分預(yù)測(cè)的準(zhǔn)確性整體最高(MAE值最小)，表明了即使用戶數(shù)據(jù)稀疏也可以通過對(duì)相似度矩陣進(jìn)行矩陣分解，再與原先相似度矩陣加權(quán)的方式來更準(zhǔn)確地計(jì)算相似度值，同時(shí)也說明了本文算法是較優(yōu)的。

4 結(jié) 語

傳統(tǒng)基于用戶的協(xié)同過濾推薦算法在計(jì)算用戶相似性時(shí)經(jīng)常面臨數(shù)據(jù)稀疏的缺點(diǎn)，而利用標(biāo)簽或者物品標(biāo)簽混合的方法來計(jì)算用戶相似度可以較好地改進(jìn)這個(gè)缺點(diǎn)。但是，當(dāng)有新用戶或者物品數(shù)目過大時(shí)仍然面臨稀疏性的問題。因此，本文提出了一種基于FunkSVD矩陣分解和相似度矩陣的推薦算法。該算法在考慮用戶偏好的同時(shí)利用FunkSVD對(duì)相似度矩陣進(jìn)行矩陣分解，并采用新的模型，將矩陣分解前后的對(duì)應(yīng)相似度值進(jìn)行加權(quán)組合。經(jīng)過Movielens數(shù)據(jù)集的實(shí)驗(yàn)表明，該算法有效克服了數(shù)據(jù)稀疏的缺點(diǎn)，在評(píng)分預(yù)測(cè)的準(zhǔn)確性上相較于傳統(tǒng)算法有所提升。另一方面，該算法也驗(yàn)證了矩陣分解技術(shù)在相似度矩陣中的應(yīng)用會(huì)有奇效。

但是，在計(jì)算綜合相似度的過程中，多個(gè)參數(shù)的求解方式?jīng)]有嚴(yán)格的科學(xué)依據(jù)，有可能陷入局部最優(yōu)解，而非全局最優(yōu)解，因此，接下來會(huì)尋找關(guān)于參數(shù)求解的相關(guān)科學(xué)依據(jù)。同時(shí)，對(duì)于最近幾年比較火熱的技術(shù)，例如深度學(xué)習(xí)也可以用于推薦算法[15]，應(yīng)當(dāng)與這種方法也做一次比較，所以，也會(huì)繼續(xù)研究深度學(xué)習(xí)在推薦算法中的應(yīng)用[16]。