加權填充與興趣相融合的相似度改進算法

黃迪　吳靜

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

關鍵詞：推薦系統；相似度融合；協同過濾；混合加權填充 ；稀疏性；興趣

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

0 引 言

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

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

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

1 混合加權填充方法和用戶喜好矩陣的建立

1.1 協同過濾推薦算法介紹

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

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

Pearson相關相似性公式如下：

1.2 各項填充值的計算以及混合加權方法

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

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

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

（4）混合加權值計算

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

混和加權填充值的計算公式如下：

1.3 用戶喜好相似度的概述

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

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

2 改進的協同過濾推薦算法

2.1 相似度融合

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

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

2.2 混合加權填充和用戶興趣相結合的協同過濾推薦算法流程

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

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

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

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

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

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

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

（7）重復步驟（3）得到預測評分以及MAE值。

3 實驗結果與分析

3.1 實驗所用的數據集

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

3.2 實驗評估標準

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

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

3.3 實驗結果

3.3.1 混合加權填充值α，β，χ的確定

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

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

3.3.2 相似度融合參數ω的確定

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

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

3.3.3 填充值和用戶興趣相結合實驗結果

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

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

4 結 語

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

參考文獻

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

[2]吳杰，馮峰.綜合用戶偏好和優先新品推薦的協同過濾推薦算法[J].計算機應用與軟件，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]李穎，李永麗，蔡觀洋.基于雙重閾值近鄰查找的協同過濾推薦算法[J].吉林大學學報（信息科學版）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]于世彩，謝穎華，王巧.協同過濾的相似度融合改進算法[J].計算機系統應用，2017，26（1）：135-140.

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

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

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

[11]夏建勛，吳非，謝長生.應用數據填充緩解稀疏問題實現個性化推薦[J].計算機工程與科學，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.