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

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

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

DOI：10. 11907/rjdk. 191298 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312 文獻標識碼：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)星測控中心工程師，研究方向為云計算、航天測控;王帆（1982-），男，碩士，中國西安衛(wèi)星測控中心工程師，研究方向為航天器軌道計算;馮亮（1980-），男，碩士，中國西安衛(wèi)星測控中心工程師，研究方向為航天器測控;夏天鶴（1988-），男，中國西安衛(wèi)星測控中心助理工程師，研究方向為航天測控;熊志奇（1992-），男，中國西安衛(wèi)星測控中心助理工程師，研究方向為北斗導航;施濤（1988-），男，中國西安衛(wèi)星測控中心高級技師，研究方向為供配電。本文通訊作者：王帆。

0 引言

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

1 Personal Rank算法

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

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

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

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

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

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

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

2 推薦算法優(yōu)化實驗

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

2.1 降低時間復雜度

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

圖2 有向節(jié)點圖

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

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

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

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

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

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

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

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

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

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

圖3 實驗結(jié)果對比

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

2.2 減少迭代次數(shù)

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

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

圖4 實驗精度對比

3 結(jié)語

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

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

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

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

[14] 裴中佑. 基于隨機游走的推薦技術研究及應用[D]. 成都：西南交通大學，2014.

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

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

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

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

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

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

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

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

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

（責任編輯：杜能鋼）