加權(quán)填充與興趣相融合的相似度改進算法

黃迪　吳靜

摘 要：針對傳統(tǒng)協(xié)同過濾推薦算法在面臨用戶評分矩陣極端稀疏而導(dǎo)致推薦結(jié)果不佳的問題，文中提出了一種改進的協(xié)同過濾推薦算法。該算法的相似度值由用戶評分相似度值和用戶興趣相似度值組成，其中用戶興趣相似度用來擬補單獨填充值導(dǎo)致用戶個性化不足的問題。用戶評分相似度值采用混合加權(quán)填充值對用戶評分矩陣進行填充，即在原用戶評分矩陣上采用由用戶評分矩陣行和列的平均數(shù)、眾數(shù)、中位數(shù)等混合加權(quán)擬合成的最終值對未評分項目進行填充，加權(quán)值的權(quán)重取決于這三種值單獨填充的實驗結(jié)果。首先將加權(quán)填充后的矩陣作為偽矩陣，在偽矩陣上進行相似度計算。然后通過用戶興趣相似度值建立用戶興趣矩陣，擬采用用戶對項目屬性評價的次數(shù)來衡量用戶對不同項目屬性的偏好度，利用相似度計算公式計算用戶間的興趣相似度值。最后對Movielens電影數(shù)據(jù)集進行仿真實驗。實驗結(jié)果表明，相比傳統(tǒng)的協(xié)同過濾推薦算法，改進的評分矩陣混和加權(quán)填充與用戶興趣相結(jié)合的協(xié)同過濾推薦算法不僅有效緩解了數(shù)據(jù)稀疏問題的影響，同時也提高了推薦精度。

關(guān)鍵詞：推薦系統(tǒng)；相似度融合；協(xié)同過濾；混合加權(quán)填充 ；稀疏性；興趣

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2018）03-00-04

0 引 言

電子商務(wù)和社交網(wǎng)絡(luò)的快速發(fā)展，極大地改變了人們的生活方式，但同時網(wǎng)絡(luò)用戶量每年呈指數(shù)級的增長也造就了信息量的急速增長和膨脹，出現(xiàn)了“信息過載”現(xiàn)象[1]。為解決這一問題，多種方法已被提出。眾所周知，信息檢索技術(shù)需要手動輸入關(guān)鍵字，雖在一定程度上節(jié)約了大量時間，但該技術(shù)需要用戶明確查找的信息。而網(wǎng)絡(luò)信息量的增大，導(dǎo)致檢索的信息亦數(shù)量巨大，因此該項技術(shù)也面臨著越來越嚴峻的挑戰(zhàn)：如果無法準確給出檢索內(nèi)容，那么查找目標內(nèi)容就比較困難。推薦技術(shù)依賴于對用戶以往數(shù)據(jù)的分析，同時參考用戶的喜好和行為習(xí)慣[2]，可主動為用戶推薦，相當(dāng)于智能推薦。然而個性化的推薦技術(shù)依賴于用戶的行為信息，推薦精度也取決于用戶所遺留信息軌跡的多寡?，F(xiàn)有推薦算法主要面對的是數(shù)據(jù)稀疏性[2]、冷啟動 [3，4]以及可擴展性問題。

當(dāng)前各種改進算法層出不窮。李穎[5]等人利用稀疏的用戶項目評分矩陣，分析近鄰用戶組與推薦精度間的關(guān)系，提出一種基于雙重閾值近鄰查找的協(xié)同過濾算法；Sarwar[6]等人提出SVD分解技術(shù)降低稀疏矩陣的維數(shù)，提高了項目或用戶間的相似度，在一定程度上提高了推薦精度，但需注意，降維技術(shù)會損失部分信息；于世華[7]等人提出用戶-項目類別評分和用戶-項目類別興趣相似度融合的算法，提高了推薦精度，該算法對合適權(quán)值的選取會直接影響用戶的最終相似度值，影響推薦的質(zhì)量；黃創(chuàng)光[8]等提出不確定近鄰因子來預(yù)測評分產(chǎn)生推薦；陳宗言等人[9]提出一種基于項目特征屬性的稀疏數(shù)據(jù)預(yù)處理方法來提高推薦精度，該方法只對數(shù)據(jù)預(yù)處理進行了改進，并未對協(xié)同過濾算法進行改進，因此有待進一步研究。

本文在上述研究的基礎(chǔ)上，提出一種改進的協(xié)同過濾推薦算法。該算法首先在解決數(shù)據(jù)稀疏的問題上充分考慮了填充值對推薦質(zhì)量的影響，采用加權(quán)填充的方式，緩解矩陣的稀疏性。在預(yù)測精度上，充分利用用戶個性化的興趣信息，將融入的偽矩陣和興趣矩陣相似度值作為最終相似度值，最后把得到的相似度值在原矩陣上進行評分預(yù)測，采用Top-N算法篩選，利用平均絕對誤差值來衡量算法的優(yōu)劣。

1 混合加權(quán)填充方法和用戶喜好矩陣的建立

1.1 協(xié)同過濾推薦算法介紹

表1所列是一個用戶-項目評分矩陣R={rij}m×n。該評分矩陣中的m代表用戶數(shù)目，n代表項目數(shù)目。元素rij代表用戶i對項目j的評分，空缺值代表該項目沒有被評分。一般的協(xié)同過濾推薦算法主要分析用戶-項目矩陣，預(yù)測未評分項目值，向目標用戶推薦，基于用戶的協(xié)同過濾算法計算目標用戶與所有用戶的相似度值，找出最為相似的用戶集，選擇對目標項目評過分且相似度最大的前k個用戶作為目標用戶的鄰居集。通過評分預(yù)測公式計算出未評分項目評分。

常用的相似度計算方法包括余弦相似性[10]、Pearson相關(guān)相似性以及修正的余弦相似性[10]。這里采用Pearson相關(guān)相似性進行計算。

Pearson相關(guān)相似性公式如下：

1.2 各項填充值的計算以及混合加權(quán)方法

可采用填充值的辦法解決矩陣稀疏的問題。考慮到單獨值的填充過于單一且不具有代表性，則采用三種值混合填充，這里采用每行和每列的平均值、眾數(shù)值以及中位數(shù)值混合，這三個值分別用Fa，F(xiàn)p，F(xiàn)m表示。

（假設(shè)用戶u沒有對項目v評過分，Iu表示已被用戶u評過分的項目，而Uv表示已被評過分的用戶集合）

（1）評分矩陣行和列的平均值計算

（4）混合加權(quán)值計算

過于單一的值不具有代表性，相比單獨值，混合所有值考慮到了三種值的所有情況，更具說服力。在用戶-項目評分矩陣中將評分矩陣計算的三種值[11]（平均值，眾數(shù)，中位數(shù)）全部分配一定的權(quán)值（權(quán)值都小于1），即α，β，χ且α+β+χ=1，各種權(quán)值的大小取決于單獨填充實驗的準確度。

混和加權(quán)填充值的計算公式如下：

1.3 用戶喜好相似度的概述

單獨的矩陣填充能夠緩解數(shù)據(jù)的稀疏性，但填充值并未考慮到用戶的興趣，無法體現(xiàn)個性化用戶的偏好程度。因此，為擬補填充值緩解用戶數(shù)據(jù)稀疏帶來的用戶個性化問題的不足，引入了用戶-項目屬性的興趣相似度?？梢酝ㄟ^統(tǒng)計用戶評價的項目屬性次數(shù)之和來定義用戶-項目興趣的程度。例如，一個人看過很多電影（一部電影包含不止一個屬性），如果想對這個人看過的愛情屬性的電影進行統(tǒng)計，那么就可以從評價過的電影中包含愛情屬性的次數(shù)來衡量這個人對愛情電影的偏好程度，次數(shù)越高代表興趣程度越大。建立一個興趣矩陣sm×k，用以表示用戶對各項目屬性的感興趣程度。

其中：Cuv表示用戶u和用戶v評價過的所有項目屬性的集合，tu，c表示用戶u評價的項目包含屬性c的總次數(shù)，tv，c表示用戶v評價過的項目包含屬性c的總次數(shù)，和分別表示用戶u和用戶v評價所有項目屬性次數(shù)的平均值。

2 改進的協(xié)同過濾推薦算法

2.1 相似度融合

由 （1）式可知用戶評分的相似性，用戶評分相似度用simR（u，v）表示，而用戶對項目屬性偏好相似度用（8）式的simI（u，v）表示，將這兩種相似度融合得到最終相似度sim（u，v），這里引入一個權(quán)重參數(shù)w，。

sim（u，v）=wsimI（u，v）+（1-w）simR（u，v） （9）

2.2 混合加權(quán)填充和用戶興趣相結(jié)合的協(xié)同過濾推薦算法流程

輸入用戶評分信息，項目評分矩陣R={rij}m×n，項目屬性矩陣sm×k，鄰居數(shù)目k，輸出目標用戶的預(yù)測評分。算法簡要的步驟如下：

（1）通過掃描用戶評分矩陣R={rij}m×n，計算行和列的平均值、眾數(shù)、中位數(shù)等值，依次添加到空缺值部分，形成對應(yīng)的偽矩陣。

（2）在形成的偽矩陣上利用式（1）計算與目標用戶的相似度值，根據(jù)設(shè)定鄰居數(shù)目k選出各鄰居集合。

（3）利用評分預(yù)測式（2）在原矩陣上預(yù)測根據(jù)設(shè)定的k個鄰居用戶預(yù)測目標用戶評分，根據(jù)MAE比較各項填充實驗的精度大小。

（4）根據(jù)步驟（3）得到的實驗結(jié)果，分配三種值的權(quán)重，利用式（6）計算得到混合加權(quán)值，再重復(fù)步驟（2）得到用戶評分相似度值和鄰居集。

（5）掃描項目屬性矩陣sm×k，利用式（8）計算用戶間的偏好相似度值。

（6）融合步驟（4）和步驟（5）計算的相似度值（融合參數(shù)實驗部分包括如何選取）。

（7）重復(fù)步驟（3）得到預(yù)測評分以及MAE值。

3 實驗結(jié)果與分析

3.1 實驗所用的數(shù)據(jù)集

采用著名的Movielens數(shù)據(jù)集[12]進行實驗，該數(shù)據(jù)集可以在線獲得，它提供了用戶信息表、電影信息表和評分信息表。用戶信息表包含用戶的年齡、國籍、性別等，評分信息表包括943位用戶、1 682部電影以及100 000條評分，評分范圍為1～5分，電影信息表包含電影的發(fā)布時間以及電影類型等。每個用戶至少對20部電影有過評分。我們用x表示該數(shù)據(jù)集稀疏程度：x=1-100 000/（943×1 682）=0.936 9。將數(shù)據(jù)集隨機分為訓(xùn)練集和測試集，比例為4∶1。訓(xùn)練集用來進行算法實驗與預(yù)測估算，測試集用來比對預(yù)測估算的結(jié)果。

3.2 實驗評估標準

本實驗為驗證混合加權(quán)填充值，結(jié)合用戶喜好的改進算法的推薦效率比未填充以及單獨填充的傳統(tǒng)協(xié)同過濾推薦效率高，采用平均絕對誤差（MAE）衡量其推薦精度。這種衡量推薦精度的辦法比較容易理解，其實質(zhì)是計算預(yù)測值和真實值之間的平均偏差。用pi表示預(yù)測值，qi表示真實值，那么MAE的表達式如下：

平均絕對誤差值越小，推薦的結(jié)果就越準確，推薦算法性能就越好。

3.3 實驗結(jié)果

3.3.1 混合加權(quán)填充值α，β，χ的確定

為確定混合加權(quán)填充值權(quán)值關(guān)系的大小，可分別進行單獨的填充實驗，即平均數(shù)、眾數(shù)、中位數(shù)填充實驗。為保證實驗的準確性，可采用多次實驗得到的MAE計算平均值（即5-交叉測試方法）。鄰居集的大小從5增加到40，比較三種填充值實驗得出的推薦精度的大小關(guān)系，精度越好給它的混合權(quán)重就越大。實驗采用Person相關(guān)相似性在各填充后的偽矩陣上計算相似度，評分預(yù)測在原矩陣上進行。實驗結(jié)果如圖1所示。

觀察圖1可知，平均數(shù)、眾數(shù)、中位數(shù)作為填充值會生成不同的偽矩陣，并以偽矩陣作為信息矩陣，計算各用戶的相似度，然后，在原矩陣上進行評分預(yù)測。實驗結(jié)果表明，相比較傳統(tǒng)的協(xié)同過濾算法，三種填充實驗均有效改善了推薦精度，并且可知，選擇中位數(shù)填充得到的推薦精度依次好于眾數(shù)和平均數(shù)填充。因此，對于混合加權(quán)填充權(quán)重的大小關(guān)系有χ>β>α>0，且，這三種填充值均滿足式（6）條件。

3.3.2 相似度融合參數(shù)ω的確定

式（9）中的相似度參數(shù)ω會直接影響最終相似度值的大小，即最終的推薦質(zhì)量。為確保融合參數(shù)的可靠性，將數(shù)據(jù)集按1∶4的比例隨機分成兩組不同的測試集和訓(xùn)練集，分別用D1和D2表示。分別在D1和D2數(shù)據(jù)集上進行仿真實驗，將最近鄰居用戶數(shù)k設(shè)為15，25，35，參數(shù)ω的步長設(shè)為0.1，，實驗同樣采用5-交叉測試方法，取5次測試實驗的平均值作為最后結(jié)果。D1數(shù)據(jù)集上MAE的仿真結(jié)果如圖2所示，D2數(shù)據(jù)集上MAE的仿真結(jié)果如圖3所示。

從圖2和圖3 可知，不同的用戶鄰居集影響最終的平均絕對誤差，當(dāng)實驗中鄰居集中的用戶個數(shù)為35時，相比鄰居用戶個數(shù)為15或25的情況，可取得較精確的推薦結(jié)果。同時從兩組圖中可以觀察到，當(dāng)相似度融合因子為0.3時，推薦系統(tǒng)的MAE取得最小值，表明最合適的相似度融合參數(shù)為0.3。因此對于式（9），在用戶總的相似度計算過程中，用戶評分相似度所占的權(quán)重為0.7，用戶興趣相似度權(quán)重為0.3。

3.3.3 填充值和用戶興趣相結(jié)合實驗結(jié)果

從圖2和圖3的實驗結(jié)果可知混合加權(quán)填充值之間的關(guān)系，即χ>β>α>0，用戶評分相似度和用戶興趣相似度融合參數(shù)為w=0.3。因此，實驗隨機選取滿足條件的混合加權(quán)值權(quán)重即可，這里取中位數(shù)權(quán)重為0.5，眾數(shù)權(quán)重為0.3，平均數(shù)權(quán)重為0.2，將得到的混合加權(quán)填充值與用戶興趣相似度相結(jié)合進行實驗，并與傳統(tǒng)的協(xié)同過濾算法實驗進行比較，實驗結(jié)果如圖4、圖5所示。

由圖4和圖5的實驗結(jié)果可知，混和加權(quán)填充原始矩陣與用戶興趣相結(jié)合的算法比傳統(tǒng)的基于Pearson相關(guān)相似性的協(xié)同過濾推薦算法推薦精度有明顯改善。說明混合加權(quán)填充和用戶興趣相結(jié)合的推薦算法在改善了數(shù)據(jù)稀疏性的情況下，更近一步提高了推薦質(zhì)量。

4 結(jié) 語

本文主要針對傳統(tǒng)的協(xié)同過濾推薦中數(shù)據(jù)稀疏問題進行了研究。考慮到數(shù)據(jù)稀疏問題的解決一般都采用填充數(shù)值的辦法，而過于單一的數(shù)值不具有代表性，且忽略了用戶的個性化興趣。因此，本文從數(shù)據(jù)稀疏和用戶個性化興趣兩方面入手，在緩解用戶項目數(shù)據(jù)稀疏性方面采用混合加權(quán)填充值的辦法豐富了填充值的多樣性，其中，混合加權(quán)值權(quán)重依賴于各項填充值單獨實驗的預(yù)測效果。為進一步提高用戶間相似度計算的精度，引入了用戶興趣模型，將用戶評分相似度和用戶興趣相似度通過單獨的實驗找到合適的擬合參數(shù)，得到最終的相似度值，經(jīng)實驗驗證了該方法的可靠性。未來將進行如何在合理的加權(quán)值中找到最優(yōu)權(quán)值與用戶興趣受多種因素影響的研究。

參考文獻

[1]劉魯，任曉麗.推薦系統(tǒng)研究進展及展望[J].信息系統(tǒng)學(xué)報，2008，4（1）：82-90

[2]吳杰，馮峰.綜合用戶偏好和優(yōu)先新品推薦的協(xié)同過濾推薦算法[J].計算機應(yīng)用與軟件，2014，10（31）：285-287.

[3] MOSHFEGHI Y，PIWOWARSKI B，JOSE JM.Handing data sparsity in collaborative filtering using emotion and semantic based features[C].In proceeding of the 34th international ACM SIGIR conference on research and development in information retrieval，2011，Bejing，China：625-634.

[4] PARK S，PENNOCK D，MADANI O，et al.Naive filterbots for robust cold-start reco-recommendations[C].In proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining，2006，Philadelphia，PA，USA：699-705.

[5]李穎，李永麗，蔡觀洋.基于雙重閾值近鄰查找的協(xié)同過濾推薦算法[J].吉林大學(xué)學(xué)報（信息科學(xué)版）2013，31（6）：647-653.

[6] SARWAR B，KAPYPIS G，KONSTAN J，et al.Application of dimensionality reduction in recommender system：a case study [C] //Proceeding of the ACM Web KDD Workshop on Web Mining for E Commerce.New York，USA：ACM，2000：82-90.

[7]于世彩，謝穎華，王巧.協(xié)同過濾的相似度融合改進算法[J].計算機系統(tǒng)應(yīng)用，2017，26（1）：135-140.

[8]黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學(xué)報，2010，33（8）：1369-1377.

[9]陳宗言，顏俊.基于稀疏數(shù)據(jù)預(yù)處理的協(xié)同過濾推薦算法[J].計算機技術(shù)與發(fā)展，2016，26（7）：59-64.

[10]任看看，錢雪忠.協(xié)同過濾算法中的用戶相似性度量方法的研究[J].計算機工程，2015，41（8）：18-22，31.

[11]夏建勛，吳非，謝長生.應(yīng)用數(shù)據(jù)填充緩解稀疏問題實現(xiàn)個性化推薦[J].計算機工程與科學(xué)，2013，35（5）：15-19.

[12] ZHAO K， LU P Y. Improved collaborative filtering approach based on user similarity combination [C].International conference on management science & engineering，2014：238–243.