基于SVD++與改進(jìn)Slope One 混合推薦算法研究*

葉 飛 邊 琳 楊林楠

（1.云南農(nóng)業(yè)大學(xué)大數(shù)據(jù)學(xué)院云南省高校農(nóng)業(yè)信息技術(shù)重點(diǎn)實(shí)驗(yàn)室 昆明 650201）（2.云南農(nóng)業(yè)大學(xué)水利學(xué)院云南省高校農(nóng)業(yè)遙感與精準(zhǔn)農(nóng)業(yè)工程研究中心 昆明 650201）

1 引言

近年來，隨著互聯(lián)網(wǎng)規(guī)模的擴(kuò)大，信息技術(shù)與應(yīng)用的快速發(fā)展，如何從過載的信息中篩選用戶喜好和興趣數(shù)據(jù)成為了影視、音樂、新聞、書籍、電商平臺(tái)亟待解決的難題。基于協(xié)同過濾算法的個(gè)性化推薦技術(shù)具有高效性、簡單性、準(zhǔn)確性特點(diǎn)，協(xié)同過濾算法是當(dāng)前個(gè)性化推薦系統(tǒng)應(yīng)用中效果做好的推薦算法［1］。推薦系統(tǒng)在應(yīng)用過程中，由于大部分用戶僅對部分項(xiàng)目進(jìn)行評分，導(dǎo)致評分矩陣十分稀疏［2］，推薦算法的準(zhǔn)確度較低。為解決數(shù)據(jù)稀疏性問題，SVD 算法［3］（Singular Value Decomposition，奇異值分解）用于解決用戶-項(xiàng)目矩陣中的數(shù)據(jù)稀疏性問題，通過將高維的稀疏評分矩陣降維，挖掘矩陣中特征值，補(bǔ)全矩陣中的缺失值，用預(yù)測值對未評分項(xiàng)目進(jìn)行填充。SVD++［4］算法將用戶的歷史評分行為矩陣加入到SVD算法中，提高了算法的準(zhǔn)確度。在SVD++算法對稀疏的評分矩陣進(jìn)行填充后，再通過改進(jìn)的 Slope One［5～6］算法對缺失值進(jìn)行二次預(yù)測，再次提高預(yù)測的準(zhǔn)確度。

因此，本文提出SVD++算法和融合項(xiàng)目相似度Slope One 算法結(jié)合的混合推薦算法通過調(diào)整預(yù)測評分，從而進(jìn)一步提高推薦的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，與原始的Slope One算法和SVD 算法相比，混合算法的推薦誤差較小。

2 相關(guān)工作

協(xié)同過濾（Collaborative filtering）［7］推薦算法是目前學(xué)者們研究較多的推薦算法之一，協(xié)同過濾分為兩類，一類為基于內(nèi)存的協(xié)同過濾另一類為基于模型的協(xié)同過濾?；趦?nèi)存的協(xié)同過濾需要在內(nèi)存中存儲(chǔ)較大的相似度矩陣，經(jīng)過算法處理提供推薦。它包含基于項(xiàng)目（item-based collaborative filtering，IBCF）和基于用戶（user-based collaborative filtering，UBCF）?；谀Ｐ停?］的協(xié)同過濾及為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的模型，它包括極大熵模型、馬爾科夫模型、概率相關(guān)模型、關(guān)聯(lián)規(guī)則模型、回歸模型、貝葉斯網(wǎng)絡(luò)模型和奇異值分解（SVD）聚類模型。協(xié)同過濾算法的原理是通過計(jì)算“用戶-項(xiàng)目”評分矩陣相似度對目標(biāo)用戶做推薦。

3 SVD++算法

3.1 SVD算法

SVD 可以將高維用戶項(xiàng)目評分矩陣通過奇異值分解降維成低維用戶、項(xiàng)目的特征向量矩陣，它是線性代數(shù)中的矩陣分解方法。用SVD 方法對評分矩陣進(jìn)行分解，通過奇異值挖掘潛在語義特征值進(jìn)行推薦。傳統(tǒng)的SVD算法［9］將評分矩陣分解為3個(gè)低維矩陣，為

式（1）中，A 為m×n 的原始評分矩陣，U 為m×m 的正交矩陣；V 為 n×n 的正交矩陣；Σ為 m×n 的對角矩陣。該公式表示矩陣A 的向量從V 按照Σ在各方向上的A的奇異值倍數(shù)進(jìn)行伸縮旋轉(zhuǎn)到U。

根據(jù)推薦系統(tǒng)的預(yù)測評分的實(shí)際需求，對式（1）進(jìn)行簡化：

根據(jù)式（2）、（3）可以將矩陣A轉(zhuǎn)換為

根據(jù)用戶項(xiàng)目的評分?jǐn)?shù)據(jù)集可以構(gòu)建評分矩陣R，其中矩陣中的行為用戶，列為項(xiàng)目，矩陣中的值代表評分值。將評分矩陣R進(jìn)行奇異值分解，為

式（5）中u 表示用戶數(shù)量，i 代表項(xiàng)目數(shù)量，k 代表選取的隱形特征值數(shù)。SVD 算法通過矩陣R中過已有數(shù)據(jù)對P、Q矩陣進(jìn)行訓(xùn)練，然后使用訓(xùn)練好的p、q矩陣對R矩陣進(jìn)行擬合從而實(shí)現(xiàn)對未評分項(xiàng)進(jìn)行評分預(yù)測，計(jì)算公式為

式（6）中表示矩陣P的某一行數(shù)據(jù)，qi表示矩陣Q的某一列數(shù)據(jù)，r^ui表示用戶u 對項(xiàng)目i的評分預(yù)測。

在實(shí)際模型中，用戶評分和商品得到的評分標(biāo)準(zhǔn)各不相同，用戶、項(xiàng)目各自本身包含特有屬性［10］。引入?yún)?shù)u表示在訓(xùn)練集中所有已有評分?jǐn)?shù)據(jù)平均數(shù)；參數(shù)bu表示用戶特有屬性，意義為特殊用戶的評分習(xí)慣與項(xiàng)目本身關(guān)聯(lián)性較小。綜合以上實(shí)際背景，對SVD公式進(jìn)行改進(jìn)為以下形式：

3.2 SVD++算法

為進(jìn)一步優(yōu)化評分預(yù)測的準(zhǔn)確度，SVD模型將用戶的歷史行為記錄擴(kuò)展到用戶的特征矩陣中，構(gòu)建成為 SVD++［11］模型。

根據(jù)項(xiàng)目的協(xié)同過濾算法（IBCF）［12］關(guān)于用戶歷史行為數(shù)據(jù)對評分預(yù)測的計(jì)算公式：

式（8）中N(u)表示用戶u 的歷史行為數(shù)據(jù)，它包含用戶評分項(xiàng)目和歷史瀏覽記錄的項(xiàng)目集。N(u)的次方是一個(gè)經(jīng)驗(yàn)值。fm，n表示項(xiàng)目間的相似度矩陣，它可以分解成向量積的形式，即因此公式可以轉(zhuǎn)化為

將歷史用戶行為記錄模型和SVD模型相結(jié)合，從而得到SVD++模型，該模型表示為

為避免參數(shù)對SVD++模型的過擬合，可以將式（9）進(jìn)行qi對xi的置換處理，經(jīng)過整合式（10）可得：

3.3 SVD++算法描述

本文采用隨機(jī)梯度下降算法更新SVD++模型中相關(guān)參數(shù)，隨機(jī)梯度下降法通用的表達(dá)

式為：y(x+1)←y(x)+?*h(x) ，其中 ? 為學(xué)習(xí)速率，可以是較小的常數(shù)，也可以是一個(gè)函數(shù)表達(dá)式；h(x)是y(x)的梯度；x為迭代次數(shù)。為保留原始評分矩陣數(shù)據(jù)的真實(shí)性設(shè)定奇異闕值γ［13］，通常γ值取成0.99。

SVD++算法

輸入：訓(xùn)練數(shù)據(jù)集R′，測試數(shù)據(jù)集R″，閾值γ，迭代次數(shù)n，學(xué)習(xí)速率?，隱特征數(shù)k，正則化系數(shù)λ。

輸出：預(yù)測填充結(jié)果數(shù)據(jù)集。

1）初始化特征矩陣P和Q，使向量pu，qi的值為random(0，1)/sqrt(k)，并把偏置項(xiàng)bu，bi和向量yj中的值初始化為0。

2）根 據(jù) 預(yù) 測 評 分和 實(shí) 際 評 分ru，i通 過 公 式計(jì)算誤差值。

3）梯度下降法的最小化損失函數(shù)為

式（12）中前半部分表示部分，后半部分表示防止訓(xùn)練出現(xiàn)過擬合的正則化部分。最小化損失函數(shù)通過對特征變量bu，bi，pu，qi和yj求偏導(dǎo)，得到特征變量的梯度向量，沿著梯度方向更新特征變量，直到梯度向量趨向于零。特征變量的迭代更新公式為

通過更新得到上述特征參數(shù)，執(zhí)行步驟2）判斷誤差eu，i是否小于閾值γ，若小于γ則停止訓(xùn)練，否則跳到步驟2）。

通過訓(xùn)練得到的參數(shù)，對測試數(shù)據(jù)集R″中未評分項(xiàng)進(jìn)行預(yù)測評分，然后進(jìn)行填充，輸出填充預(yù)測結(jié)果的評分矩陣。

通過重復(fù)大量實(shí)驗(yàn)調(diào)整參數(shù)n，?，k，λ使得算法最優(yōu)，SVD++預(yù)測的精準(zhǔn)度達(dá)到最高。

4 相似度算法

本文采用項(xiàng)目相似度，常用的相似度算法為歐式距離相似度、余弦相似度、修正余弦相似度［14］、Pearson相似度［15］和Jaccard相似度。SVD++算法對評分矩陣做了初步的數(shù)據(jù)填充，數(shù)據(jù)稀疏性大大降低，采用修正余弦相似度和Pearson 相似度的權(quán)重計(jì)算融合相似度，該融合相似度的值即為改進(jìn)Slope One算法中的權(quán)值。

4.1 修正余弦相似度

余弦相似度通過改進(jìn)用戶沒有考慮評分尺度問題，計(jì)算相似度時(shí)減去用戶對項(xiàng)目的平均評分，從而達(dá)到去中心化的目的。

式（14）中ru，i，ru，j分別表示用戶u對項(xiàng)目i，j的評分，分別表示所有用戶對項(xiàng)目i，j評分的平均值。

4.2 Pearson相似度

Pearson 相似度是基于Pearson 相關(guān)系數(shù)計(jì)算項(xiàng)目間的相似度，Pearson 相關(guān)系數(shù)反映變量間的線性相關(guān)性程度，當(dāng)兩個(gè)變量線性關(guān)系增強(qiáng)時(shí)相關(guān)系數(shù)趨向于1 或者-1。Pearson 相關(guān)系數(shù)大于0 時(shí)變量正相關(guān)，小于0時(shí)負(fù)相關(guān)。

式（15）中ru，i，ru，j分別表示用戶u對項(xiàng)目i，j的評分，表示同時(shí)對項(xiàng)目i和j都評分的用戶集合Ui，j對項(xiàng)目i的評分平均值，表示同時(shí)對項(xiàng)目i和j都評分的用戶集合Ui，j對項(xiàng)目j的平均值。

4.3 融合相似度

針對上述提到的修正余弦相似度和Pearson 相似度可以通過引入權(quán)重的方式進(jìn)行融合，計(jì)算出最終的項(xiàng)目相似度。

θ的取值范圍為［0，1］，調(diào)整θ參數(shù)即為設(shè)置相似度的權(quán)重，通過測試數(shù)據(jù)集試驗(yàn)選取適當(dāng)?shù)闹?，使得提高推薦的準(zhǔn)確度。

5 改進(jìn)Slope One算法

Slope One 算法是一種基于線性回歸的項(xiàng)目評分的算法，應(yīng)用公式f(x)=x+b來預(yù)測評分，x表示評分值，b為項(xiàng)目間的評分偏差。計(jì)算項(xiàng)目i和j之間的偏差公式為

ru，i，ru，j表示用戶u對項(xiàng)目i，j的評分，Si，j表示同時(shí)對項(xiàng)目i，j評分的用戶集合，| |Si，j表示集合Si，j中用戶數(shù)。

根據(jù)偏差式（17）可以轉(zhuǎn)化為用戶u對項(xiàng)目i的評分預(yù)測公式為

S(u)表示用戶u評分的項(xiàng)目集合，S(u)-{i} 表示用戶u與項(xiàng)目i同時(shí)評分的項(xiàng)目集合。

加權(quán)Slope One 算法［16］對評分矩陣中缺失值進(jìn)行二次預(yù)測，進(jìn)一步提升推薦的準(zhǔn)確性，計(jì)算得到最終的評分矩陣。進(jìn)行Slope One 算法改進(jìn)時(shí)使用的評分矩陣為填充完整的評分矩陣，Si，j就是完整的用戶集U。將融合相似度sim(i，j)加入到Slope One算法中，得到改進(jìn)Slope One公式為

本文S(u)-{i} 集合選取相似度鄰近集合中N個(gè)最大的項(xiàng)目集合。

改進(jìn)Slope One算法

輸出：預(yù)測評分pre(u，i)和最終填充矩陣Ri，j。

1）設(shè)定大小合適的w組成S(u)-{i} 項(xiàng)目集合；

3）根據(jù)式（19）使用相似度鄰近集合最大值集合S(u)-{i} 、項(xiàng)目相似矩陣Kn，n中項(xiàng)目相似度值和項(xiàng)目偏差值deνi，j求得pre(u，i)；

4）輸出pre(u，i)，并使用pre(u，i)更新評分矩陣，輸出最終評分矩陣Ri，j。

6 實(shí)驗(yàn)與結(jié)果分析

6.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)采用美國Minnesota大學(xué)公開的MovieLens數(shù)據(jù)集，本文選用100K 數(shù)據(jù)集包含943個(gè)用戶，1682 個(gè)項(xiàng)目，100000 條評分記錄，數(shù)據(jù)稀疏度為0.937。實(shí)驗(yàn)過程中為避免隨機(jī)性對實(shí)驗(yàn)結(jié)果產(chǎn)生影響采用五折交叉法，80%的評分?jǐn)?shù)據(jù)集作為訓(xùn)練集，另外20%的評分?jǐn)?shù)據(jù)集作為測試集。

6.2 評價(jià)指標(biāo)

實(shí)驗(yàn)使用均方根誤差（Root Mean Squared Error，RMSE）和平均絕對誤差（Mean Absolute Error，MAE）作為預(yù)測評分精準(zhǔn)度評價(jià)指標(biāo)。

1）平均絕對誤差（Mean Absolute Error，MAE）

MAE 用來衡量所有用戶對于項(xiàng)目的預(yù)測值和真實(shí)值差的平均值，MAE 值越小，預(yù)測精度就越高。

式（20）中，ru，i表示用戶u對項(xiàng)目i的實(shí)際評分，表示用戶u對項(xiàng)目i的預(yù)測評分，N表示項(xiàng)目集，|N|表示項(xiàng)目集的大小。

2）均 方 根 誤 差（Root Mean Squared Error，RMSE）

RMSE 作為預(yù)測值精準(zhǔn)度的評價(jià)指標(biāo)，RMSE值越小，預(yù)測值精準(zhǔn)度越高。

6.3 結(jié)果與分析

6.3.1 SVD++模型中訓(xùn)練迭代次數(shù)實(shí)驗(yàn)

通過實(shí)驗(yàn)研究SVD++模型中訓(xùn)練迭代次數(shù)n的大小對評分矩陣預(yù)測準(zhǔn)確率的影響，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 不同訓(xùn)練迭代次數(shù)下RMSE的值

圖中橫坐標(biāo)為訓(xùn)練的迭代次數(shù)，縱坐標(biāo)為RMSE 的值。分析本圖發(fā)現(xiàn)訓(xùn)練迭代次數(shù)在25 時(shí)趨向穩(wěn)定，所以本文SVD++模型訓(xùn)練迭代次數(shù)n 選用25。

6.3.2 SVD++模型中隱形特征數(shù)實(shí)驗(yàn)

本文實(shí)驗(yàn)研究SVD++模型中隱形特征數(shù)k 的大小對評分矩陣預(yù)測準(zhǔn)確率的影響，并確定效果最好的隱形特征數(shù)。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 不同隱形特征數(shù)下RMSE的值

圖中橫坐標(biāo)為隱含特征數(shù)，縱坐標(biāo)為RMSE 的值。分析發(fā)現(xiàn)隱形特征數(shù)在80 時(shí)趨向穩(wěn)定，所以本文SVD++模型隱形特征值k選用80。

6.3.3 相關(guān)算法對比試驗(yàn)

為驗(yàn)證SVD++與改進(jìn)Slope One 混合算法的精準(zhǔn)性，本文選取SVD Slope One算法、加權(quán)Slope One算法兩組組模型進(jìn)行對比，分別測試評分矩陣測試集的MAE 的值?？紤]到項(xiàng)目的相似度鄰近集合最大值W對推薦精準(zhǔn)度的影響，本文將三組模型結(jié)合鄰近集合最大值W進(jìn)行實(shí)驗(yàn)，結(jié)果如圖3所示。

圖3 不同鄰近集合最大值W與三種算法MAE值

實(shí)驗(yàn)結(jié)果表明，本文提出的SVD++與改進(jìn)Slope One 混合算法模型推薦效果最佳，MAE 值最小。鄰近集合最大值W 在到100時(shí)，MAE值趨向穩(wěn)定，推薦效果較好。SVD++與改進(jìn)Slope One 混合算法較SVD Slope One 算法、加權(quán)Slope One 算法的MAE值提升了2.89%和6.87%。

7 結(jié)語

本文針對傳統(tǒng)協(xié)同過濾算法存在評分矩陣數(shù)據(jù)稀疏性問題提出SVD++算法對缺失評分?jǐn)?shù)據(jù)進(jìn)行預(yù)測評分并進(jìn)行填充，針對稀疏矩陣填補(bǔ)空值過于單一提出在初步填充后使用改進(jìn)Slope One 算法進(jìn)行二次預(yù)測，項(xiàng)目間的相似度計(jì)算本文提出融合相似度方法，提高推薦的精準(zhǔn)度。下一步研究的方向?yàn)榻鉀Q冷啟動(dòng)問題和有效地減少算法計(jì)算時(shí)間以及有效節(jié)約系統(tǒng)計(jì)算資源。