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

DOI：10.19850/j.cnki.2096-4706.2021.08.036

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

關(guān)鍵詞：二分圖;馬太效應(yīng);用戶可信度;資源分配;推薦算法

中圖分類號：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? 引? 言

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

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

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

1? 基于馬太效應(yīng)商品過度推薦的改進

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

原始項目初始資源值f=1，本文通過引入一個可調(diào)參數(shù)α，節(jié)點熱門度估計重新設(shè)定為：

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

2? 用戶可信度

2.1? 項目偏好平均值

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

輸入：項目評分數(shù)據(jù)集

輸出：項目偏好平均值RIPV

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

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

Step 3.根據(jù)Step 1中計算得出的期望和標準差，剔除異常數(shù)據(jù)后重新計算統(tǒng)計值，結(jié)束后執(zhí)行Step 2;

Step 4.RIPV=E（x），算法結(jié)束。

2.2? 用戶誤差平均值

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

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

2.3? 用戶可信度

為了防止用戶誤差平均值對結(jié)果產(chǎn)生決定性影響，將用戶誤差平均值以激活函數(shù)的形式定義出，公式為：

3? UTMT算法

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

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

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

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

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

算法偽代碼為：

4? 實驗與結(jié)果分析

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

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

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

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

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

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

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

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

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

5? 結(jié)? 論

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

參考文獻：

[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] 郝治翰，陳陽，王蒲生.“馬太效應(yīng)”與科研網(wǎng)絡(luò)中的擇優(yōu)依附 [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—），女，蒙古族，內(nèi)蒙古赤峰人，碩士研究生，研究方向：推薦系統(tǒng)、數(shù)據(jù)分析。

收稿日期：2021-01-10