李 玲，李晉宏

（北方工業(yè)大學計算機學院 知識工程研究所，北京 100144）

0 引言

在當今的互聯(lián)網(wǎng)時代，海量的信息膨脹導致了嚴重的信息過載，如何幫助用戶在海量的信息中更準確的篩選所需，是當前研究的熱點方向。而個性化推薦系統(tǒng)[1-3]是解決這個問題的有效方法，通過分析用戶的行為特性進行興趣預測，為用戶推薦可能會感興趣的信息，從而提高了用戶篩選的效率，節(jié)約了信息篩選的時間。目前的推薦算法主要有協(xié)同過濾推薦算法（Collaborative Filtering，CF）[4]，基于內(nèi)容的推薦算法[5]，混合推薦算法和基于網(wǎng)絡結(jié)構(gòu)的推薦算法等等，已經(jīng)被大量的應用在商業(yè)化環(huán)境當中。協(xié)同過濾推薦算法是通過用戶對商品的評價，計算用戶之間的相似性，尋找鄰居，然后根據(jù)鄰居的信息進行推薦，但是往往存在數(shù)據(jù)稀疏性等問題?；趦?nèi)容的推薦算法是以用戶選擇過的商品信息為依據(jù)，選擇相似度高的商品推薦給用戶。該方法是對商品的信息（種類、用途等）和用戶的愛好進行分析并推薦，也屬于對信息的過濾，但是由于信息數(shù)據(jù)格式的限制，往往無法對非文本的商品信息（視頻等）進行處理。

現(xiàn)今基于二部圖網(wǎng)絡結(jié)構(gòu)的推薦技術(shù)（Network-Based Inference，NBI）[6-8]是個性化推薦領(lǐng)域一個越來越被人關(guān)注的研究熱點，由于其推薦復雜度低，準確性高和推薦的內(nèi)容多樣化而被大量關(guān)注。它的基本思想是把用戶和項目分別看作抽象的節(jié)點集合，將用戶對項目的選擇看成對節(jié)點的連邊。在物質(zhì)擴散的啟發(fā)下，zhou等人[6]提出了利用資源分配的推薦算法；在此基礎(chǔ)上，zhang等[9]引入了資源分配權(quán)重的概念，將評分看作權(quán)重，提出了加權(quán)的二部圖推薦算法，在不增加時間和空間計算復雜度的情況下提高了準確性；Wang等人[10]根據(jù)評分能量分配權(quán)重進行了算法的改進，并且添加了項目度與權(quán)值的比值，降低了推薦項目的流行性的影響，推薦的多樣性也得以提高；在此基礎(chǔ)上Li等人[11]在用戶推薦時增加了對項目相似性的考慮。

雖然學者們?yōu)樘岣咄扑]的準確度提出了多種方法，但是目前基于二部圖的推薦方法仍然有以下兩個不足：第一，設置權(quán)重時沒有更精細的劃分；第二，絕大多數(shù)的算法改進都是選擇評分或者人為選擇用戶行為或者項目因素進行加權(quán)計算或者推理的，這種人為選擇的因素在一定程度上忽視了其他特征因素對推薦結(jié)果準確性的影響，使得推薦結(jié)果說服力有限，應用局限性比較大。針對以上問題，本文提出了一種基于隨機森林修正的二部圖推薦算法（RF-WNBI），基本思想是先構(gòu)建用戶-項目特征二部圖，對項目進行初步的評分預測，再用隨機森林分類預測評分結(jié)果進行修正。在構(gòu)建二部圖時細化評分權(quán)重，考慮項目度和用戶之間共同評分項目影響，最終參考項目特征對評分修正。對比試驗結(jié)果，證明改進后的算法能夠有效提高推薦準確性和多樣性[12]。

1 相關(guān)工作

1.1 基于二部圖網(wǎng)絡結(jié)構(gòu)的推薦算法

假設在輸入中有m個用戶和n個項目，用戶 ui對項目 oj進行過選擇，那么在 ui與 oj之間就有一條邊相連，這樣就構(gòu)成了二部圖網(wǎng)絡結(jié)構(gòu)G。用U來代表用戶，用O來代表項目，定義一個|U|×|O|的鄰接矩陣A = ( aij)。如果用戶 ui對項目 oj進行過選擇，則 aαi= 1，否則 aαi= 0 。

受物理學中復雜物質(zhì)擴散理論的影響，Zhou等人[6]提出了利用資源分配思想的相似度計算方法。首先，假設給每個用戶分配一個單位的能量。接著，進行資源分配，按照平均分配的方式，各個用戶將能量分發(fā)給該用戶選擇過的各個項目，分配完成后每個項目將得到一定的能量。

下一步，將每個項目得到的能量值按照相同的方式再次傳遞給選擇過它的各個用戶，得到各個用戶此時擁有的能量值。simαβ表示的是用戶uα在分配過程中從用戶uβ獲得的資源比例，即用戶之間的相似性。能量分配的過程如圖1所示。

圖1 基于二部圖網(wǎng)絡結(jié)構(gòu)的能量分配過程Fig.1 Energy distribution process based on the two parts graph network structure

能量分配的過程可以由下列公式表示：

其中 d (uβ)表示的是用戶uβ的度（即該用戶選擇過多少個項目）； d(oi)表示的是項目 oi的度（即該項目被多少個用戶選擇過）。

目標用戶uα對未評分項目 oi的評分計算公式為：

傳統(tǒng)的基于二部圖網(wǎng)絡結(jié)構(gòu)的推薦算法是針對用戶與項目之間的關(guān)系進行能量分發(fā)來對用戶進行推薦的，忽略了用戶興趣的影響，不能充分發(fā)掘冷門項目，且不能對用戶的選擇進行充分的解釋。因此，文中融合了隨機森林算法對特征的分類模型，并以此修正對用戶推薦的評分。

1.2 隨機森林算法

隨機森林（Random Forest）是由Leo breiman[14]提出的，作為一種常用的分類方法，是建立多棵決策樹[15-16]將結(jié)果進行投票集成分類的。決策樹的根節(jié)點作為訓練集合，節(jié)點是作為測試屬性，節(jié)點分支代表基于單個特征作為分類，葉子節(jié)點代表分類結(jié)果。

構(gòu)建隨機森林有如下幾個步驟：

（1）用 bootstrap方法[17]有放回地隨機選擇訓練的樣本集，第k個樣本集生成隨機向量θk，使用h(x,θk)作為第k棵分類樹模型。

（2）對得到的樣本分別建立分類樹，使用在屬性集合中選擇最大信息增益的方式選擇分裂屬性。

首先計算樣本的熵，其中 pj表示第j個類別在節(jié)點D的概率：

然后計算按特征A劃分對樣本集合D劃分所需要的期望信息，樣本集合D被劃分的范圍為jD。

最后通過由式(4)與(5)得出信息增益，選出具有最大增益率的屬性作為分裂屬性。

（3）經(jīng)過分裂得到多個決策樹分類模型｛h(x, θk) ,k = 1 ,2… n ｝，參數(shù)集 ｛θk｝是獨立同分布的隨機向量。其最終結(jié)果為決策樹的投票集成：

其中 H (x)代表分類組合模型， Y是目標變量，I（°）表示指示函數(shù)。

2 基于隨機森林修正的加權(quán)二部圖推薦算法

2.1 改進相似度的加權(quán)二部圖推薦方法

傳統(tǒng)的二部圖網(wǎng)絡只關(guān)注用戶與項目之間是否有邊相連，即是否進行過選擇，并不對用戶對不同項目的喜愛程度進行區(qū)分，選擇過的項目即為 1，未選擇的項目即設為 0。而用戶對項目的評分在很大程度上是用戶對項目喜愛程度的反映，不加以區(qū)分會對推薦結(jié)果的準確性造成影響。而在文獻[9]算法直接將他認為的高分項目直接設定權(quán)重值為 1，這造成用戶信息的損失。在文獻[10]提出的算法中，直接忽略了低分項目，只認為得到高分的項目才被用戶選擇過，也是一定程度上的信息疏漏。

為了細化評分對推薦的影響，考慮用戶對項目評分由于每個人的個人傾向不同而有所變化，因此，根據(jù)用戶對項目的喜愛程度（即顯式評分）進行標準化，來對用戶和項目的邊的權(quán)重iαω進行分配。

在式中，irα是用戶uα對項目oi的評分，maxr 是用戶α全部評分項目的評分最大值，minr 是用戶ua全部評分項目的評分最小值，為了預防出現(xiàn)分母為0的情況，設定一個極小值ε為0.01，同時為了區(qū)分低分項目與未評分項目，設定一個極小值λ為0.1。在資源分配過程中，引入 IUF系數(shù)（Inverse User Frequence）[11]來定義 θ：

其中，D(i)表示項目io的評分集合， ()Dα表示用戶uα評分的項目集合， ()Dβ表示用戶uβ評分項目的集合。θ的取值為0～1，一方面，衡量了用戶的共同評分項目，懲罰了其中的熱門項目，便于用戶選擇出更加符合個人喜好的項目；另一方面，降低了活躍用戶對相似性的貢獻，往往選擇項目少的用戶興趣點更明確，因此活躍度高的用戶對相似性的影響應當?shù)陀诨钴S度低的用戶。因此在算法中，經(jīng)過多次試驗，引入函數(shù)()fθδθ=+的sigmoid函數(shù)即可調(diào)節(jié)，θ的取值為0～1，其中δ為可調(diào)參數(shù)。進行兩步資源分配之后，最終得到的用戶相似性計算公式為：

式中υ是兩個用戶之間共同評分項目個數(shù)與目標用戶度的比值，即。 ()Dα表示用戶uα評分的項目集合， D （β） 表示用戶uβ評分項目的集合。在推薦算法中，兩個用戶選擇了同樣的項目，那么這個項目可以看作兩個用戶共同的興趣點所在，則二者的相似度就越高。但如果目標用戶選擇的項目很多，那么該用戶的興趣比較廣泛，目標用戶與其他用戶的共同評分項目就只能代表目標用戶的部分興趣；相反的，如果目標用戶選擇的項目較少，與其他用戶共同選擇的項目就更能代表目標用戶的興趣所在。

文獻[11]中提出，在評分預測中加入用戶的評分期望能夠提高預測精度，如式（9）所示，并經(jīng)過驗證，證明式（9）進行評分預測準確率明顯優(yōu)于式（2）。因此文中采用式（9）進行評分計算。目標用戶uβ對項目jo的評分預測公式：

這里 oj表示有過對 oi項目評分行為的用戶；sim(α ,β)表示用戶uα、uβ的相似性。rα，rβ表示用戶uα、uβ的平均評分。

2.2 生成推薦

給定用戶uα及其特征向量集合Ti= ｛ （xi, yi）｝，i∈N。其中x={,…}為特征向量，

+i∈ ｛ 0,1｝是類標簽。取特征向量集合構(gòu)建隨機森林，得到分類模型。

對用戶uα進行2.3節(jié)中基于加權(quán)二部圖的改進方法進行矩陣計算，得到了用uα戶的初步推薦結(jié)果N ′ = { (tj, rj)}， tj為項目， rj是評分。對已得到的用戶uα的推薦項目進行評分分類，得到分類結(jié)果N = { (tj, yj)}， tj為項目， yj是評分修正標簽。設定rj≥rα對應的評分標簽為1，rj＜rα對應的評分標簽為0。對比 rj與 yj，二者相同，保留該項目及評分，不同則降低該項目在評分列表中的排名。最終將推薦列表的前N個推薦給用戶。

在推薦方法 RF-WNBI中，改進相似度的加權(quán)二部圖推薦方法（IWNBI）不但可以生成初始推薦評分，也可以作為推薦方法之一。

2.3 算法流程

算法設計流程如圖如圖2所示。

圖2 總體流程圖Fig.2 The overall flow diagram

RF-WNBI的算法描述如下

輸入：用戶-項目評分矩陣，特征矩陣，目標用戶uα，近鄰數(shù)k，可調(diào)參數(shù)δ。

輸出：用戶uα的Top N推薦項目

參數(shù)：可調(diào)參數(shù)δ，近鄰數(shù)k

（1）對于 uα?U 且 β≠α，根據(jù)公式計算 sim(α,β)，找到分值最高的k個作為最近鄰居；

（2）利用步驟(1)的結(jié)果，根據(jù)公式計算評分iVα；

（3）找出評分值最高的m個項目，依照評分進行降序排序，構(gòu)成對uα的推薦列表l；

（4）隨機森林分類器對l中的項目進行分類；

（5）根據(jù)分類結(jié)果對 l進行重排序，形成新的推薦列表l'；

（6）取l′中的前N個，形成Top N推薦。

3 實驗分析

3.1 數(shù)據(jù)集

本文使用GroupLens實驗室在MovieLens數(shù)據(jù)集提供的擴展數(shù)據(jù)庫中的公開數(shù)據(jù)集（http://ir.ii.uam.es/hetrec2011/datasets.html）進行實驗，檢測算法性能。數(shù)據(jù)集中包含了800000條數(shù)據(jù)記錄，其中包括 2113名用戶和 10197部電影。將數(shù)據(jù)集分為80%的訓練集和 20%的測試集，數(shù)據(jù)集中每條記錄包含以下字段：用戶ID、項目ID、用戶評分（1～5）、特征向量集合Ti。本數(shù)據(jù)的矩陣密度為：

3.2 評價標準

本文采用平均排序值、平均絕對誤差（MAE）、均方根誤差（RMAE）[18]和漢明距離來度量推薦的質(zhì)量。

（1）平均排序值（Ranking score）用評測用戶推薦列表準確度的高低，在測試集中，用戶選擇過項目io，io排在推薦列表的位置為iL，N代表推薦列表的長度。用戶實際選擇項目在推薦列表中排名越高，證明推薦結(jié)果越準確。當目標用戶不同時，對每個 r求均值，即得到算法的平均排序值。則平均排序值（Ranking score）計算公式為：

（2）根據(jù)預測值與實際誤差值得偏差來表示評分準確率的高低，平均絕對誤差值越小，推薦精度越高，如：預測用戶的評分集合是{ p1, p2, p3,p4, … pN-1, pN}，用戶實際評分集合是{q1， q2， q3，q4， …qN-1，qN}，則平均絕對誤差與均方根誤差為：

（3）漢明距離（HD）根據(jù)不同用戶推薦列表中相同項目的數(shù)量來評價預測結(jié)果的多樣性。用戶ui與 uj推薦列表之間的漢明距離為：

其中：ijQ代表用戶iu與ju推薦列表之間公共項目的集合，|ijQ|代表集合ijQ 中元素的個數(shù)，L代表推薦列表長度。如果兩個推薦列表是完全一致的，則ijQ=0；如果兩個推薦列表沒有任何相同的項目，則ijQ=1。所有用戶的漢明距離的平均值即是整個系統(tǒng)的漢明距離HD：

其中：m表示用戶數(shù)量。漢明距離越大，表示推薦結(jié)果的多樣性越高。

3.3 動態(tài)可調(diào)參數(shù)δ校準

圖3展示了動態(tài)δ對算法準確率的影響。從圖中可知，當δ變化時，產(chǎn)生的推薦結(jié)果的MAE和RMSE也隨之變化，當δ取到0.4左右的值時，效果最好。

圖3 動態(tài)因子δ對算法準確性的影響Fig. 3 The effect of dynamic factor δ on the accuracy of algorithm

3.4 不同的近鄰數(shù)K對推薦準確度的影響

選擇適合的最近鄰居個數(shù)，能夠提高計算精度，降低計算時間。由圖4可以看出，當隨著近鄰數(shù)K的增加，平均絕對誤差(MAE)和均方根誤差(RMAE)也隨之下降，這是因為當選取相似度高的用戶增多時，進而帶來的推薦結(jié)果更加準確。但當K達到45左右時，MAE和RMAE曲線變得平穩(wěn)，因此設定K值為50。

圖4 近鄰數(shù)K對算法準確性的影響Fig.4 The influence of nearest neighbor K on the accuracy of algorithm

3.5 算法結(jié)果分析

下面進行對比實驗，在實驗中選擇動態(tài)因子 的值為0.4，近鄰數(shù)閾值設為50。對比試驗結(jié)果如下。

（1）對比平均排序值（Ranking score）

將文獻[6]提出的基于二部圖的推薦算法（NBI）、文獻[11]提出的基于增加相似度系數(shù)的加權(quán)二部圖推薦算法（ISWNBI）、改進相似度的加權(quán)二部圖推薦方法（IWNBI）、本文基于隨機森林修正的加權(quán)二部圖算法（RF-WNBI）進行Ranking score的對比，實驗結(jié)果如圖5所示。

圖5 各算法關(guān)于Ranking score的實驗對比圖Fig.5 The experimental comparison of ranking score of each algorithm

由上圖所示，隨著推薦列表長度增大，四種算法的平均排序比都逐漸增大且IWNBI和RF-WNBI在推薦列表長度增加時均低于另外兩種算法NBI和ISWNBI的平均排序值。并且RF-WNBI的Ranking score明顯相對更低。說明本文提出的RF-WNBI會命中更多實際推薦列表中的項目。因此在推薦精度和多樣性方面只對NBI、ISWNBI和RF-WNBI進行比較。（2）對比精度（MAE、RMSE）和多樣性（HD）圖 6是 NBI、ISWNBI和 RF-WNBI關(guān)于 MAE、RMSE和HD的對比。

圖6 各算法關(guān)于推薦精度與推薦多樣性的比較Fig.6 The comparison between the proposed algorithm and the recommended diversity

由上圖對各MAE和RMSE的對比可以知道，RF-WNBI在推薦精度上明顯優(yōu)于NBI和ISWNBI，可以證明 RF-WNBI具有較高的精度，更容易為用戶推薦其喜愛的項目。對三個算法的HD進行對比，RF-WNBI比 NBI的多樣性更好，雖然比 ISWNBI的多樣性低，但也具有較好的多樣性。

綜合以上實驗結(jié)果，可以看出本文提出RF-WNBI具有較好的合理性和較強的推薦效果。

4 結(jié)語

文中構(gòu)建了基于隨機森林修正的加權(quán)二部圖推薦算法，通過對評分權(quán)重作出更細致的劃分，平衡了項目的權(quán)重，充分考慮到對冷門項目的挖掘。完善了相似度計算，提高了推薦的精度。將特征數(shù)據(jù)進行標準化后建立隨機森林模型，對二部圖算法階段產(chǎn)生的預測列表進行評分區(qū)間的修正校驗。通過和基于加權(quán)二部圖的推薦算法（NBI）和基于增加相似性系數(shù)的加權(quán)二部圖推薦算法（ISWNBI）進行比較，證明本文算法在保證了較好多樣性的同時，提高了推薦的準確性和推薦精度。

[1] Ricci F, Rokach L, Shapira B. Introduction to recommender systems handbook. Recommender Systems Handbook. Springer US, 2011: 1-35.

[2] Xu HL, Wu X, Liu XD, Yan BP. Comparison study of Internet recommendation system[J]. Journal of software, 2009,20(2): 1-10(in China). [許海玲, 吳瀟, 李曉東, 等. 互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]. 軟件學報, 2009, 20(2): 1-10.]

[3] Li S-T, Xiao B. Recommender system based on social network [J]. Software, 2013, 34(12): 41-45. [李善濤, 肖波. 基于社交網(wǎng)絡的信息推薦系統(tǒng)[J]. 軟件, 2013, 34(12): 41-45.]

[4] Schafer J-B, Frankowski D, Herlocker J, et al. Collaborative filtering recommender systems[A]. In: The Adaptive Web,Springer-Verlag, 2007: 291-324.

[5] Jiang Z-F, Jiang J, E J-H. A content-based recommendation algorithm with social tagging. Software, 2015, 36(1): 1-5. [江周峰, 楊俊, 鄂海紅. 結(jié)合社會化標簽的基于內(nèi)容的推薦算法[J]. 軟件, 2015, 36(1): 1-5.]

[6] ZHOU T, REN J, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E,2007, 76(4): 6116-6123.

[7] LIU Jian-guo, ZHOU Tao, CHE Hong-an, et al. Effects of high-ordercorrelations on personalized recommendations for bipartite networks[J]. Physica A, 2010, 389: 881-886.

[8] SHANG Ming-sheng, LV Lin-yuan, ZHANG Yi-cheng, et al.Empirical analysis of Web-based user-object bipartite networks[J]. Europhysics Letters, 2010, 90(4): 48006．

[9] ZHANG X M, JIANG S Y. Personalized recommendation algorithm based on weighted bipartite network[J]. Journal of Computer Applications, 2012, 32(3): 654-657. (in Chinese).[張新猛, 蔣盛益. 基于加權(quán)二部圖的個性化推薦算法[J].計算機應用, 2012, 32(3): 654-657.]

[10] WANG Q, DUAN S-Y. Improved recommendation algorithm based on bipartite networks[J]. Application Research of Computers, 2013, 30(3): 771-774 (in Chinese). [王茜, 段雙艷. 一種改進的基于二部圖網(wǎng)絡結(jié)構(gòu)的推薦算法[J]. 計算機應用研究, 2013, 30(03): 771-774.]

[11] LI Z-D, LUO Q, SHI L L. Weighted bipartite network recommendation based on increasing similarity coefficient[J].Computer Science, 2016, 43(7): 259-264 (in Chinese). [李鎮(zhèn)東, 羅琦, 施力力. 基于增加相似度系數(shù)的加權(quán)二部圖推薦算法[J]. 計算機科學, 2016, 43(07): 259-264.]

[12] HE Lei. Research of information recommendation algorithm based on bipartite network[D]. Nanchang;Nanchang Hangkong University, 2013(in China). [何磊. 基于網(wǎng)絡結(jié)構(gòu)的信息推薦算法的研究[D]. 南昌航空大學, 2013.]

[13] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering.[C]//Proceedings of the 14th Conference on Uncertainty in Artifi-cial Intelligence. San Francisco, CA: Morgan KaufmannPublishers, 2013: 43-52．

[14] Breiman L, 2001a. Random forests. Mach. Learn. 45: 5-32.

[15] Breiman L. Bagging Preditors[J]. Machine Learning, 1996,24(2).

[16] Ho T K. The Random Subspace Method for Constructing Decision Forests[J]. Trans.on Pattern Analysis and Machine Intelligence, 1998, 20(8).

[17] Ma H, Wang Q, Han Z-D, Zhang X-X, Hao G. Application of decision tree algorithm to personal book recommendation.Software, 2012, 33(8): 100-101. [馬華, 王清, 韓忠東, 張西學, 郝剛. 決策樹分類算法在個性化圖書推薦中的應用[J]. 軟件, 2012, 33(8): 100-101.]

[18] Sexton J, Laake P. Standard Errors for Bagged and Random Forest Estimators[J]. Computational Statistics& Data Analysis, 2009, 53(1).

[19] Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen,John T. Riedl. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS). 2004(1): 5-53.