基于資源分配的推薦算法研究

DOI：10.19850/j.cnki.2096-4706.2021.08.036

摘? 要：針對馬太效應中過度流行性偏見問題，通過定義新的節點權重來初始化項目資源值，達到降低項目流行性的目的;進一步考慮用戶可信度因素，結合統計學中的3σ原則，根據數據統計量篩選出系統中存在的異常用戶或欺詐用戶。在此基礎上給出一個新的推薦算法（UTMT）。在數據集MovieLens_100K上對算法進行試驗，并與資源分配中的熱傳導算法作比較，結果表明，構建的UTMT推薦算法預測結果的準確率較之熱傳導算法有較大的提升。

關鍵詞：二分圖;馬太效應;用戶可信度;資源分配;推薦算法

中圖分類號：TP391.3? ? ? 文獻標識碼：A ? 文章編號：2096-4706（2021）08-0127-03

Research on Recommendation Algorithm Based on Resource Allocation

CHI Luyang

（College of Sciences，Northeastern University，Shenyang? 110004，China）

Abstract：Aiming at the problem of excessive popularity bias in Matthew effect，a new node weight is defined to initialize the project resource value，so as to achieve the aim of reducing the project popularity. Further considering the user credibility factor and combining with the 3σ principle of statistics，the abnormal users or fraudulent users existing in the system are filtered out according to the data statistics. On this basis，a new recommendation algorithm（UTMT）is proposed. Test the algorithm on the dataset MovieLens_100k and make a comparison with heat conduction algorithm in resource allocation. The final results show that the constructed recommendation algorithm UTMT has a big improvement in the accuracy rate of predict outcomes than that of the heat conduction algorithm.

Keywords：bipartite graph;Matthew effect;user credibility;resource allocation;recommendation algorithm

0? 引? 言

隨著互聯網的飛速發展，網絡中爆發式增長的資源雖然能滿足人們的各項需求，但卻突破了人們可以有效利用的范圍，嚴重導致了信息過載問題。這在一定程度上凸顯了采用個性化推薦系統的關鍵性和重要性。近年來，將復雜網絡與推薦系統相結合的思想也應運而生。一些研究將網絡中節點鏈接關系預測方法應用到推薦系統中。Zhu等人^[1]通過分析共同鄰居節點來預測推薦效果。Zhang等人^[2]運用似然分析法評估節點之間推薦的可能性。

基于二分圖的推薦算法^[3]可視為一個資源分配的過程，科研人員經常采用單模映射的方法壓縮二分圖來展示其中復雜的節點關系。通常，最原始的方法是把二分圖映射到一個無權圖上^[4]，如果一個圖上只有A節點，那么這就是A的單模映射結果。若映射結果中兩個節點存在一條無向邊，那么說明兩個節點至少有一個共同鄰居。無權重的單模映射會導致在資源傳遞的過程中丟失很多信息，因此需要在映射圖中設置每條邊的權重。在此基礎上，Zhou等人提出了一種計算邊權值來解決問題的方法^[5]，根據節點權重經過多次迭代得出用戶推薦列表。基于二分圖的推薦算法的原理是通過對這些連接的邊進行分析，預測用戶的喜好和傾向，與此同時計算出每個項目對應于不同用戶的資源值。最終計算出的項目資源值則作為推薦列表中排序的依據。在二分圖中通過資源傳遞來模擬得出節點（包括用戶和項目）的資源值。但是以上對節點的分析屬于單一類型的研究，沒有考慮到節點復雜性的情況，有些算法不適用于實際網絡，并且其中涉及的復雜理論研究的結果仍存在可解釋性問題。

本文是在基于二分圖的推薦算法上進行改進，提高算法性能。具體做法是通過引入用戶可信度來改進原始的資源分配推薦算法。此外，由于原始推薦算法存在流行偏見問題，在進行用戶推薦時可解釋性較低，所以在此基礎上考慮了更改資源值的方法以解決相關問題。

1? 基于馬太效應商品過度推薦的改進

馬太效應反映的是強者越發強大、弱者越發弱小的現象。如果推薦系統是以資源分配為框架，那么就會增大流行和非流行項目之間的熱門度差距，從而使信息領域也存在馬太效應^[6]。商品越熱門，就越容易被推薦給用戶，從而該商品就會越來越流行;此時，非熱門商品反而不容易出現在推薦列表中，導致非熱門商品越來越冷門。而對于那些熱門項目，不需要借助推薦系統這一媒介，用戶也能獲取熱門項目的資源。本文根據馬太效應，推薦那些用戶可能會喜歡但不一定是熱門的項目。本文選擇在推薦過程中降低熱門節點的初始值，對其進行適度懲罰，從而降低推薦度。

原始項目初始資源值f=1，本文通過引入一個可調參數α，節點熱門度估計重新設定為：

其中a_ij=0或1，當用戶i不喜歡項目j時，a_ij=0;當用戶i喜歡項目j時，a_ij=1。k（Oj）為項目j的度。參數α就是降低熱門項目程度的關鍵性指標，通過實驗得出使推薦效果達到最優時α的取值。

2? 用戶可信度

2.1? 項目偏好平均值

實驗過程中，考慮到數據集中可能存在異常數據，所以在實驗過程中對噪聲數據進行了篩選。一般認為評分數值不在均值±3個標準差范圍內的屬于異常數據，應做剔除處理。項目偏好平均值（簡記為RIPV）的計算過程為：

輸入：項目評分數據集

輸出：項目偏好平均值RIPV

Step 1.對已清洗好的數據集的評分數據逐一掃描。計算每個項目的期望值E（x）、每個項目評分數值的最小值min、最大值max及相應的標準差σ;

Step 2.若某個項目的[min，max]?[E（x）-3δ，E（x）+3δ]，執行Step 4，否則執行Step 3;

Step 3.根據Step 1中計算得出的期望和標準差，剔除異常數據后重新計算統計值，結束后執行Step 2;

Step 4.RIPV=E（x），算法結束。

2.2? 用戶誤差平均值

本文定義用戶誤差平均值，簡記為UMRE。用戶誤差平均值是指將每個用戶對項目的評分值與RIPV之間的差值的累加，最后除以用戶已經評價的項目數量的總和。它代表用戶的評分誤差度，UMRE的數值越小，說明用戶越可信。用戶誤差平均值（UMRE）計算公式為：

其中，W_ij為用戶U_i對項目Ii的評分，|W_ij>0|表示用戶U_i已經評價，可以看出RIPV是以每個項目為對象計算出的結果，UMRE是以每個用戶為對象計算出結果的項目總個數。

2.3? 用戶可信度

為了防止用戶誤差平均值對結果產生決定性影響，將用戶誤差平均值以激活函數的形式定義出，公式為：

3? UTMT算法

在以上分析的基礎上給出一個新的推薦算法，記為UTMT，算法主要步驟為：

（1）在全體用戶數據集中選擇目標用戶U_i，根據式（1）初始化目標用戶喜歡的所有項目的資源值。

（2）在基于資源傳遞的框架上，目標用戶U_i喜歡的項目的初始資源值通過“項目—用戶”的傳遞過程，將初始資源值傳遞給每一個也同樣喜歡該項目的其他用戶，同時計算出每個用戶的資源值。

（3）計算出用戶可信度UT值，將UT值以權重乘積的方式集成到“用戶—項目”資源傳遞過程中，累計不同用戶傳遞給項目的資源值，通過相似度進行相似性搜索，完成最終的資源分配。資源傳遞終止時項目的資源值，就是該目標用戶Ui對各個項目的喜愛程度。

（4）將迭代后項目對應的最終資源值按照從大到小的順序排列，排除目標用戶已選擇過的物品，排名前L的項目就形成了UTMT算法中目標用戶的推薦列表。

算法偽代碼為：

4? 實驗與結果分析

利用MomieLens_100K數據集對算法進行實驗，該數據集包含943位用戶對1 682部電影的100 000條評分數據，用戶對電影的評分為1～5分制，每位用戶至少對20部電影進行了評分。整個實驗數據集須進一步劃分為訓練集和測試集。

利用準確率和MAP指標評價本文算法的有效性。

準確率^[7]是常用的評價推薦準確程度的指標。用戶的平均準確率為：

其中，n為用戶總數量，L為推薦列表的長度，d_i（L）為在推薦列表中有物品被準確預測的個數。準確率P值越高，推薦效果越好。

MAP為考慮了物品推薦排序的平均準確率。MAP值定義為：

其中，D（i）為測試集中物品的總數量，rc為第c個共同物品在推薦列表中的排序位置。在推薦結果中，推薦準確的物品排序越小，MAP值越大，推薦效果則越好。

圖1和圖2分別是用MATLAB實現UTMT算法，取α∈[0，1]，根據式（1）進行仿真實驗，得出使得算法推薦準確率最高的參數α和最佳推薦個數L的折線圖。

計算結果通過五次獨立實驗得到。由實驗可知，當參數α=0.15、L=10時，推薦算法的準確率最高，性能最好。取這組參數，在MovieLens_100K數據集上，將提出的UTMT算法與熱傳導算法HC^[8]進行實驗對比，結果如表2所示。

表2中每行的準確率和MAP值是5次獨立實驗結果的平均值。表2中最后一行表示UTMT（α=0.15）算法相對HC算法的性能提升幅度。與經典的熱傳導（HC）算法相比，本文提出的算法UTMT具有更好的推薦效果，P值和MAP值分別提升了9.349 9%和3.240 0%。

5? 結? 論

UTMT算法不僅可以抑制熱門物品，提升冷門物品推薦度，解決用戶個性化推薦問題，還考慮了可信用戶的行為特征和評分特征，將用戶作為共同鄰居的節點，增加了推薦結果的可解釋性。同時實驗表明，本文提出算法的準確率相較于傳統算法有較大的提升。

參考文獻：

[1] ZHU J Q，LU L，MA C M. From Interest to Location：Neighbor-Based Friend Recommendation in Social Media [J].Journal of Computer Science and Technolog，2015（30）：1188-1200.

[2] ZHANG W，DU Y，SONG W. Followee Recommendation Based Formal Concept Analysis In Social Network [J].International journal of innovative computing，information & control：IJICIC，2015，11（4）：1155-1164.

[3] ZHOU T，REN J，MEDO M. Bipartite network projection and personal recommendation [J].Physical Review E，2007，76（4）：046115.

[4] NEWMAN M E. The structure of scientific collaboration networks [J].Proceedings of the National Academy of Sciences of the United States of America，2001，98（2）：404-409.

[5] ZHOU T，REN J，MEDO M，et al. How to project a bipartite network？ [J/OL].arXiv：0707.0540v2[physics.soc-ph].（2007-07-31）.https：//arxiv.org/abs/0707.0540v2.

[6] 郝治翰，陳陽，王蒲生.“馬太效應”與科研網絡中的擇優依附 [J].自然辯證法研究，2019，35（11）：39-45.

[7] L? L Y，MEDO M，YEUNG C H，et al. Recommender systems [J].Physics Reports，2012，519（1）：1-49.

[8] ZHANG Y C，BLATTNER M，YU Y K. Heat conduction process on community networks as a recommendation model [J].Physical Review Letters，2007，99（15）：154301.

作者簡介：遲露陽（1996—），女，蒙古族，內蒙古赤峰人，碩士研究生，研究方向：推薦系統、數據分析。

收稿日期：2021-01-10