劉清 王帆 馮亮 夏天鶴 熊志奇 施濤

摘 要：為解決PersonalRank圖推薦算法在推薦系統(tǒng)應(yīng)用中的效率問題，從降低時(shí)間復(fù)雜度和減少迭代次數(shù)兩方面進(jìn)行算法優(yōu)化。首先，構(gòu)建推薦系統(tǒng)中用戶行為數(shù)據(jù)二分圖和迭代推薦模型;然后，建立轉(zhuǎn)移矩陣，通過矩陣運(yùn)算轉(zhuǎn)換傳統(tǒng)迭代模型，求解稀疏矩陣線性方程組直接得到系統(tǒng)穩(wěn)態(tài)，有效降低了推薦算法的時(shí)間復(fù)雜度;最后，通過確定游走概率，在不影響系統(tǒng)精度前提下，各節(jié)點(diǎn)概率值收斂前就提前停止迭代，大幅減少了系統(tǒng)迭代次數(shù)。實(shí)驗(yàn)表明，轉(zhuǎn)移矩陣法推薦效率比傳統(tǒng)迭代法提高了211倍左右，游走概率取值為0.1時(shí)精度趨于穩(wěn)定。優(yōu)化后的算法能有效提高推薦效率。

關(guān)鍵詞：圖推薦;轉(zhuǎn)移矩陣;游走概率;PersonalRank

DOI：10. 11907/rjdk. 191298 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）008-0049-03

Research on the Application of Efficient Graph Recommendation Algorithm

LIU Qing， WANG Fan， FENG Liang， XIA Tian-he， XIONG Zhi-qi， SHI Tao

（China Xi'an Satellite Control Center， Xi'an 710043，China）

Abstract： In order to solve the efficiency problem of the recommendation algorithm of PersonalRank graph in the application of the recommendation system， the algorithm optimization is carried out from two aspects of reducing the time complexity and the number of iterations. Firstly， a binary graph of user behavior data and an iterative recommendation model are constructed. Then， the transfer matrix is established， and the traditional iterative model is transformed by the matrix operation. The steady state of the system can be directly obtained by solving the linear equations of the sparse matrix， which can effectively reduce the time complexity of the recommendation algorithm. Finally， by determining the walk probability， on the premise of not affecting the accuracy of the system， the iteration of each node is stopped before the probability value converges， and the number of system iterations is greatly reduced. It can be seen from the experiment that the recommendation efficiency of the transfer matrix method is about 211 times higher than that of the traditional iterative method. When the walk probability is 0.1， the accuracy tends to be stable. The optimized algorithm can effectively improve the efficiency of recommendation.

Key Words：? graph recommendation; transfer matrix; walk probability; PersonalRank

作者簡介：劉清（1982-），男，碩士，中國西安衛(wèi)星測控中心工程師，研究方向?yàn)樵朴?jì)算、航天測控;王帆（1982-），男，碩士，中國西安衛(wèi)星測控中心工程師，研究方向?yàn)楹教炱鬈壍烙?jì)算;馮亮（1980-），男，碩士，中國西安衛(wèi)星測控中心工程師，研究方向?yàn)楹教炱鳒y控;夏天鶴（1988-），男，中國西安衛(wèi)星測控中心助理工程師，研究方向?yàn)楹教鞙y控;熊志奇（1992-），男，中國西安衛(wèi)星測控中心助理工程師，研究方向?yàn)楸倍穼?dǎo)航;施濤（1988-），男，中國西安衛(wèi)星測控中心高級技師，研究方向?yàn)楣┡潆?。本文通訊作者：王帆?/p>

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，人類從信息匱乏時(shí)代走進(jìn)信息過載時(shí)代，信息消費(fèi)者越來越難于從海量信息中找到自己感興趣的信息[1-2] ，信息生產(chǎn)者也難于確保生產(chǎn)的信息能夠得到廣大用戶關(guān)注[3-4]。隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，推薦算法逐漸在學(xué)術(shù)研究和工程應(yīng)用領(lǐng)域成為熱點(diǎn)，推薦系統(tǒng)較好地解決了這一矛盾[5-6]。國外關(guān)于推薦應(yīng)用的研究起步較早[7-9]，國內(nèi)近年來也有涉及[10-13]，但因算法時(shí)間復(fù)雜度過高，推薦效率直接制約著推薦算法的推廣應(yīng)用。推薦的實(shí)現(xiàn)主要有基于用戶行為數(shù)據(jù)、內(nèi)容標(biāo)簽數(shù)據(jù)和社交網(wǎng)絡(luò)信息等方式[14-17]。基于用戶行為數(shù)據(jù)的推薦包括協(xié)同過濾、基于圖模型和基于矩陣填充3種推薦算法[18-19]。PersonalRank 算法是一種圖模型推薦算法[20]，能夠較好實(shí)現(xiàn)信息推薦。本文在研究PersonalRank 算法基礎(chǔ)上，從降低時(shí)間復(fù)雜度和減少迭代次數(shù)兩方面進(jìn)行算法優(yōu)化，以有效解決推薦系統(tǒng)效率不高問題。

1 Personal Rank算法

PageRank算法是一種隨機(jī)游走算法[20]，能為一張圖的每個(gè)節(jié)點(diǎn)求得一個(gè)反映這個(gè)節(jié)點(diǎn)在圖中重要程度的權(quán)值。如果該圖是強(qiáng)連通的，那么隨機(jī)游走必然會收斂[20]。PersonalRank算法是PageRank算法的變形，是一種典型的圖推薦算法，增加了用戶的個(gè)性化，考慮了不同用戶下的最大可能性，在度量節(jié)點(diǎn)間相似程度方面得到應(yīng)用。在推薦系統(tǒng)中，用戶行為數(shù)據(jù)可以表示成圖的形式。行為數(shù)據(jù)集由一系列（u，i）二元組組成，表示為用戶u對物品i產(chǎn)生過行為。假設(shè)用戶對產(chǎn)生過行為的物品興趣度相同，則只考慮“感興趣”和“不感興趣”兩種狀態(tài)。

使用PersonalRank算法對電商用戶作商品推薦，使其能利用當(dāng)前的訪問行為數(shù)據(jù)向用戶推薦將來可能感興趣的商品。首先要將用戶和商品信息構(gòu)建成一張二分圖。二分圖中有兩類節(jié)點(diǎn)，一類是代表用戶的節(jié)點(diǎn)，一類是代表商品的節(jié)點(diǎn)。當(dāng)某個(gè)用戶訪問過一個(gè)商品時(shí)，就將兩者之間連一條邊，構(gòu)成二分圖[21] ，過程如圖1所示。

圖1 行為數(shù)據(jù)二分圖構(gòu)建

圖1中，圓形節(jié)點(diǎn)代表用戶，方形節(jié)點(diǎn)代表商品，圓形節(jié)點(diǎn)和方形節(jié)點(diǎn)之間的邊代表用戶對商品的訪問，圖中用戶A和商品節(jié)點(diǎn)a、b、c 相連，說明用戶A有對a、b、c商品的訪問行為。令G（V，E）表示用戶商品的二分圖，其中V=Vu∪Vi，由用戶頂點(diǎn)集合Vu 組成。對于數(shù)據(jù)集中的每一個(gè)二元組（u，i），圖中都有一套對應(yīng)的邊e（vu，vi），其中vu∈Vu 是用戶u對應(yīng)的頂點(diǎn)，vi∈Vi是商品中i對應(yīng)的頂點(diǎn)。

由于PersonalRank算法不區(qū)分用戶節(jié)點(diǎn)和商品節(jié)點(diǎn)，并假設(shè)每條邊代表感興趣程度相同，當(dāng)需要為用戶A推薦商品時(shí)，實(shí)際上就轉(zhuǎn)化為計(jì)算用戶A相對于節(jié)點(diǎn)A、B、 C、 D、a、b、c、d、e的重要度各是多少。

重要度用PR表示，初始賦值為0。即對于A來說，其自身的重要度為1，其它節(jié)點(diǎn)的重要度均為0。計(jì)算重要度時(shí)，首先選中一個(gè)節(jié)點(diǎn)作為計(jì)算與其重要度的中心節(jié)點(diǎn)，然后開始在圖上游走。每次游走都是從PR不為0的節(jié)點(diǎn)開始，往前隨機(jī)游走一步，然后按照一定的游走概率決定繼續(xù)游走到下一節(jié)點(diǎn)或返回中心節(jié)點(diǎn)。游走概率用α表示，繼續(xù)游走的概率是α，停留在當(dāng)前節(jié)點(diǎn)的概率是1-α。如果決定繼續(xù)游走，那么游走到相鄰接點(diǎn)的概率按算法迭代計(jì)算。這樣經(jīng)過多次迭代，每個(gè)節(jié)點(diǎn)的權(quán)值會收斂到一個(gè)固定值，這個(gè)權(quán)值就是其與中心節(jié)點(diǎn)的重要度，如公式（1）所示。

[PR（v）=αv∈in（v）PR（v）out（v）? ? ? ? ? ? ? ? ? ? ? ? ? （v！=vu）（1-α）+αv∈in（v）PR（v）out（v）? ? ? ? ? ?（v=vu）]? （1）

其中，u和v是待推薦的節(jié)點(diǎn)，PR（v）是v節(jié)點(diǎn)的權(quán)值，α是繼續(xù)游走的概率，out（v）是v節(jié)點(diǎn)的出邊，in（v）是v節(jié)點(diǎn)的入邊。

不同節(jié)點(diǎn)重要度隨著迭代過程不盡相同，會在一定次數(shù)迭代計(jì)算后收斂，收斂后每個(gè)節(jié)點(diǎn)的權(quán)重表示該點(diǎn)的重要程度，此時(shí)選擇用戶A沒有產(chǎn)生過商品訪問行為中重要度最大的一個(gè)商品向用戶A推薦。

2 推薦算法優(yōu)化實(shí)驗(yàn)

雖然PersonalRank算法可通過隨機(jī)游走進(jìn)行較好的理論解釋，但該算法在時(shí)間復(fù)雜度上有明顯缺陷。當(dāng)為每個(gè)用戶進(jìn)行推薦時(shí)，都需要在整個(gè)用戶商品二分圖上進(jìn)行迭代，直到整個(gè)圖上每個(gè)頂點(diǎn)的PR值收斂，這一過程的時(shí)間復(fù)雜度非常高，不僅無法在線提供實(shí)時(shí)推薦，甚至離線生成推薦結(jié)果也非常耗時(shí)。為解決算法時(shí)間復(fù)雜度高的問題，可從降低時(shí)間復(fù)雜度和減少迭代次數(shù)兩個(gè)方面進(jìn)行優(yōu)化。

2.1 降低時(shí)間復(fù)雜度

為解決時(shí)間復(fù)雜度過高問題，避免多次迭代游走，可以建立狀態(tài)轉(zhuǎn)移矩陣[21] 。從矩陣論出發(fā)，經(jīng)過一次矩陣運(yùn)算就可直接得到系統(tǒng)的穩(wěn)態(tài)[22-23] ，能夠有效降低時(shí)間復(fù)雜度。如圖2所示的4個(gè)關(guān)系節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的出邊權(quán)值之和為1，可以建立如式（2）的轉(zhuǎn)移矩陣。

圖2 有向節(jié)點(diǎn)圖

[001/301/201/3101001/201/30]? ? ? ? ? ? ? ? ?（2）

該轉(zhuǎn)移矩陣每一列表示一個(gè)節(jié)點(diǎn)出邊的權(quán)重，例如第一列表示節(jié)點(diǎn)A的出邊，它對B、D 兩個(gè)節(jié)點(diǎn)分別有一條邊，權(quán)重各為1/2。

這樣，迭代公式（1）可轉(zhuǎn)換為式（3）的矩陣表示形式。

[r = （1-α）r0+αMTr]? ? ? ? ? （3）

其中，r是n維向量，每個(gè)元素代表一個(gè)節(jié)點(diǎn)的PR重要度;r0也是n維向量，第i個(gè)位置上是1，其余元素均為0;M是n階轉(zhuǎn)移矩陣。對于迭代公式（1）左邊的PR（j）和PR（i），i是j一條入邊，最終迭代概率（權(quán)重）在r中表示。當(dāng)要為第i個(gè)節(jié)點(diǎn)進(jìn)行推薦時(shí)，可表示為式（4）。

[Mij=1out（i）? ? ? ? ? （j∈out（i））? ? 0? ? ? ? ? ? ? ? ? （j！∈out（i））]? ? ? ? （4）

由式（3）變形可得到式（5）：

[（1-αMT）r=（1-α）r0]? ? ? ? ? ? （5）

因?yàn)镸是稀疏矩陣，所以[1-αMT]也是稀疏矩陣[22]。因此，只需要一次[（1-αMT）-1]矩陣運(yùn)算，就可通過解稀疏矩陣的線性方程組得到系統(tǒng)穩(wěn)態(tài)。

推薦算法的衡量指標(biāo)包括準(zhǔn)確率（precision）、召回率（recall）、流行度（Popularity）和多樣性（diversity）等，使用轉(zhuǎn)移矩陣前后推薦指標(biāo)對比如圖3所示。

圖3 實(shí)驗(yàn)結(jié)果對比

通過實(shí)驗(yàn)發(fā)現(xiàn)，不使用轉(zhuǎn)移矩陣的傳統(tǒng)迭代法經(jīng)過46次迭代后，所有節(jié)點(diǎn)的概率值趨于收斂，用時(shí)9 647ms;根據(jù)狀態(tài)轉(zhuǎn)移矩陣，經(jīng)過一次矩陣運(yùn)算就可直接得到系統(tǒng)的穩(wěn)態(tài)，計(jì)算出各節(jié)點(diǎn)的概率值用時(shí)45.7ms。由此結(jié)果可知，轉(zhuǎn)移矩陣法的推薦效率比傳統(tǒng)迭代法提高了211倍左右，推薦效果技術(shù)指標(biāo)基本一致。因此，利用稀疏矩陣的線性方程解法，能有效降低推薦算法的時(shí)間復(fù)雜度，快速得出推薦結(jié)果。

2.2 減少迭代次數(shù)

在收斂之前就提前停止迭代，雖然可以減少迭代次數(shù)，但可能會因游走概率（α）的取值不同而影響最終精度。為探討不同游走概率對算法的影響，通過實(shí)驗(yàn)測試不同α取值情況下算法的召回率、準(zhǔn)確率和覆蓋度變化情況，實(shí)驗(yàn)結(jié)果如圖4所示。

從實(shí)驗(yàn)數(shù)據(jù)可知，算法精度總體上隨著游走概率（α）的減少而變好。當(dāng)取值為0.1時(shí)精度趨于穩(wěn)定，算法效果最好。因此，設(shè)置游走概率為0.1時(shí)可在保證推薦精度前提下，大幅減少算法迭代次數(shù)，從而有效提高推薦效率。

圖4 實(shí)驗(yàn)精度對比

3 結(jié)語

PersonalRank算法在推薦系統(tǒng)應(yīng)用中的時(shí)間復(fù)雜度過高，影響推薦效率，可從降低時(shí)間復(fù)雜度和減少迭代次數(shù)兩方面進(jìn)行算法優(yōu)化。本文研究發(fā)現(xiàn)，從矩陣論出發(fā)建立狀態(tài)轉(zhuǎn)移矩陣，經(jīng)過一次矩陣運(yùn)算就直接得到系統(tǒng)穩(wěn)態(tài)，避免多次迭代過程，有效降低了時(shí)間復(fù)雜度;另一方面，選取游走概率為0.1時(shí)，在各節(jié)點(diǎn)概率收斂之前就提前停止迭代，既可保證精度，又能大幅減少迭代次數(shù)，提高操作效率。本文為推薦系統(tǒng)提供了一個(gè)高效的實(shí)現(xiàn)方法。

參考文獻(xiàn)：

[1] HAN J，KAMBER M，PEI J. Data mining： concepts and techniques[M]. Morgan Kaufmann，2006.

[2] JANNACH D，ZANKER M，F(xiàn)ELFERNIG A，et al. Recommender systems： an introduction[M]. Cambridge University Press，2010.

[3] KOREN Y，BELL R. Recommender systems handbook[M]. Advances in collaborative filtering. New York：Springer，2011.

[4] LIU T Y. Learning to rank for information retrieval[J]. Foundations and Trends in Information Retrieval， 2009， 3（3）： 225-331.

[5] RICHARD HAMMACK，OWEN PUFFENBERGER. A prime factor theorem for bipartite graphs[J]. European Journal of Combinatorics，2015（4）：542-549.

[6] CHEN L，CHEN G，WANG F. Recommender systems based on user reviews：the state of the art[J]. User Modeling and User-Adapted Interaction，2015，25（2）：99-154.

[7] LU C，SHUAI H，YU P S. Identifying your customers in social networks[C]. Shanghai：Proceedings of the 23rd ACM International Conference on Information and Knowledge Management，2014.

[8] TAY D B H，LIN Z. Design of near orthogonal graph filter banks[C]. IEEE Signal Processing Letters，2015：701-704.

[9] RAKESH V，CHOO J，REDDY C K. Project recommendation using heterogeneous traits in crowdfunding[C]. Ninth International AAAI Conference on Web and Social Media，2015：1-10.

[10] 項(xiàng)亮. 推薦系統(tǒng)實(shí)踐[M]. 北京：人民郵電出版社，2012.

[11] 許海玲，吳瀟，李曉東，等. 互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]. 軟件學(xué)報(bào)，2009，20（2）：350-362.

[12] 王子政，姚衛(wèi)東. 一種改進(jìn)的組合推薦算法研究[J]. 軍民兩用技術(shù)與產(chǎn)品，2015（23）：46-47.

[13] 劉琳竹. 基于數(shù)據(jù)挖掘的個(gè)性化推薦算法研究[D]. 北京：北京理工大學(xué)，2016.

[14] 裴中佑. 基于隨機(jī)游走的推薦技術(shù)研究及應(yīng)用[D]. 成都：西南交通大學(xué)，2014.

[15] 吳迪. 高校畢業(yè)生就業(yè)推薦系統(tǒng)的設(shè)計(jì)與開發(fā)[D]. 大連：大連理工大學(xué)，2010.

[16] 金連旭. 面向企業(yè)的高校畢業(yè)生就業(yè)推薦算法研究[D]. 濟(jì)南：山東師范大學(xué)，2017.

[17] 金連旭，王洪國，丁艷輝，等. 基于興趣敏感度的高校畢業(yè)生就業(yè)推薦算法[J]. 計(jì)算機(jī)與數(shù)字工程，2017（2）：201-205，253.

[18] 魏麗芹. 基于歷史信息的就業(yè)推薦算法研究與可視分析[D]. 濟(jì)南：山東大學(xué)， 2013.

[19] 陳天，劉文浩. 相似度算法分析與比較研究[J]. 現(xiàn)代計(jì)算機(jī)：專業(yè)版，2012（18）：18-20.

[20] 吳迪，周利娟，林鴻飛. 基于隨機(jī)游走的就業(yè)推薦系統(tǒng)研究與實(shí)現(xiàn)[J]. 廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版：2011（1） ：179-185.

[21] 王偉，陳偉，祝效國，等. 眾籌項(xiàng)目的個(gè)性化推薦：面向稀疏數(shù)據(jù)的二分圖模型[J]. 系統(tǒng)工程理論與實(shí)踐，2017（4）：1011-1023.

[22] 黃譚，蘇一丹. 基于混合用戶模型的二分圖推薦算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2014（6）：145-148，152.

[23] 張紹飛. 矩陣論教程[M]. 北京：機(jī)械工業(yè)出版社，2012.

（責(zé)任編輯：杜能鋼）