齊會敏，劉 群，戴大祥

(重慶郵電大學重慶市計算機智能重點實驗室，重慶 400065)

1 引言

如今，隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡用戶和產(chǎn)生的信息量也成指數(shù)級飆升。因此，作為有效過濾冗余信息和鎖定目標信息的工具，推薦系統(tǒng)扮演的角色越來越重要。社交網(wǎng)絡的出現(xiàn)旨在幫助人們在網(wǎng)上建立虛擬的“朋友圈子”，實現(xiàn)信息共享和交流。然而，在海量的信息中找到“志同道合”的朋友并擴大自己的社交圈，對用戶而言變得越來越困難。所以，個性化的好友推薦不僅可以向用戶推薦其感興趣的潛在好友，而且可以提高用戶之間的黏性，增強用戶體驗，是社交網(wǎng)絡得以穩(wěn)固發(fā)展的必備功能。本文提出的結合用戶興趣的推薦算法在擁有推薦精度的基礎上，提高了用戶對推薦結果的滿意度。

2 相關工作

目前，推薦系統(tǒng)相關領域的研究主要分為：項目推薦和好友推薦。之前許多社交媒體的研究主要針對項目推薦，所采用的方法主要有基于內(nèi)容推薦[1]和協(xié)同過濾推薦[1 - 3]。而推薦潛在好友的研究相對較少，也是近年來研究的熱點，采用的推薦算法主要包括基于用戶特征的好友推薦[4]、基于網(wǎng)絡拓撲結構的好友推薦[5]以及利用概率矩陣分解進行推薦等方法[6]。

傳統(tǒng)的推薦系統(tǒng)廣泛地應用于以搜索引擎為代表的信息檢索中，或者向用戶推薦滿足其需求的資源，例如商品、音樂、熱點新聞等[7]。而向用戶個性化地推薦潛在好友的研究相對較少。目前相關研究大致可以分為三種：基于內(nèi)容的推薦[8]、基于共同興趣的推薦[7]和基于網(wǎng)絡拓撲結構的推薦。王玙等人[4]通過研究朋友之間的關系提出了基于關系的社交圈檢測算法，使擁有相似社交圈的用戶更易成為朋友。Jeckmans等人[9]通過計算文本資料內(nèi)容相似性進行潛在好友推薦。張鵬等人[10]分析用戶之間的網(wǎng)絡拓撲結構，提出了基于社區(qū)劃分和用戶相似性好友推薦方法。高永兵等人[8]在考慮有效鏈接和關鍵詞匹配的基礎上提出了基于內(nèi)容和鏈接的算法進行好友推薦。Liben-Nowell等人[11]通過鏈路預測為用戶推薦好友。He等人[12]通過構建語義網(wǎng)絡，找出用戶感興趣主題實現(xiàn)個性化推薦。利用用戶之間的網(wǎng)絡拓撲結構進行推薦偏重于現(xiàn)實生活中已經(jīng)認識的人而忽略虛擬網(wǎng)絡中感興趣的潛在好友推薦，社交網(wǎng)絡的緊密度和活躍度很難提高。僅根據(jù)內(nèi)容或興趣相似性為用戶推薦能夠更好地挖掘“志趣相投”的朋友，但推薦結果很容易被用戶忽略或者拒絕，推薦用戶的可接受度不高。

相對于陌生人而言，朋友的朋友更可能被認可，用戶也更愿意結識有相似主題興趣的潛在好友。本文提出的算法思想是在有相似興趣的基礎上，結合用戶的社交關系進行推薦，即在“朋友的朋友，更可能成為朋友”的理論基礎上引入先驗概率計算出有相同屬性的用戶成為朋友的概率，然后結合興趣主題相似性進行推薦。通過爬取2015年9月新浪微博數(shù)據(jù)驗證本文提出的算法，結果表明，該算法更能保證好友推薦結果的接受度和滿意度。

2.1 基于內(nèi)容的推薦

基于內(nèi)容的推薦(Content-based Recommendation)是本文涉及的推薦算法，該方法根據(jù)用戶感興趣的微博信息，從推薦對象中選擇其他特征相似的對象作為推薦結果。這一推薦策略首先提取被推薦對象的興趣特征信息，然后與用戶興趣特征匹配，匹配度高的對象作為推薦結果。該推薦策略的匹配度得分計算公式如下：

score(u,v)=sim(feature_u,feature_v)

(1)

其中,feature_u表示用戶u的興趣特征向量，feature_v表示用戶v的興趣特征向量。采用的相似性計算方法是余弦相似性[4],如式(2)所示，然后將計算結果按大小排序，推薦給用戶。

(2)

2.2 FOF推薦算法

在社交媒體中好友推薦扮演著重要的角色，研究表明，高質(zhì)量的好友推薦可以提高用戶之間的交互，增強用戶對社交媒體的忠誠度。目前主要的方法是朋友的朋友推薦算法FOF(Friend-OF-Friend)和最短路徑推薦算法，本文主要涉及到FOF推薦算法。基礎理論是如果用戶A和用戶B之間存在一定數(shù)量的共同好友，則A和B也可能成為朋友。將y作為好友推薦給x的得分計算方法如公式(3)所示：

score(x,y):=Γ(x)∩Γ(y)

(3)

其中,Γ(x)作為用戶x的朋友集合，Γ(y)作為用戶y的朋友集合，若y是用戶x的推薦列表中的一員，則y在推薦列表中的排名用x、y共同擁有的好友數(shù)量來衡量。

3 面向用戶興趣主題的好友推薦算法ITOR

本文提出的面向用戶興趣主題的好友推薦算法ITOR(Topic-Oriented Recommendation base on Interest),主要依賴于上述兩個理論基礎，首先經(jīng)過統(tǒng)計分析目標用戶的直接好友、一跳好友與目標用戶之間的共鄰好友以及一跳好友中已經(jīng)成為目標用戶直接好友的用戶，利用先驗概率的知識計算擁有不同共鄰好友數(shù)的用戶成為目標用戶好友的概率。其次，根據(jù)k-core分析得出的興趣主題關鍵詞的分布情況來計算用戶之間興趣的相似性。

3.1 概率理論

Zhang等人[13]提出了基于總概率原則的推薦算法，某用戶成為目標用戶A好友的總概率的定義如下：

P(A)=∑P(A|xi)P(xi)

(4)

其中,xi(i∈{1,2,3,4,5,…,m})表示用戶第i個屬性(包括連續(xù)性屬性和離散性屬性)。

計算出成為目標用戶好友的每個屬性的概率，例如：擁有屬性i和j的用戶B成為目標用戶好友的先驗概率分別為0.6和0.8，則用戶B成為目標用戶好友的概率為1-0.4*0.2=0.92。通過公式(5)[13]得出候選者成為目標用戶好友的總概率。

(5)

根據(jù)大量數(shù)據(jù)的統(tǒng)計結果分析可知，該屬性和對應的概率之間總是表現(xiàn)出一種明顯的趨勢關系，我們可以通過回歸分析計算出該屬性對應概率的回歸函數(shù)，如式(6)所示。

P(x)=F(x)

(6)

其中，F(xiàn)(x)是通過分析統(tǒng)計結果得出的線性函數(shù)。

因此，根據(jù)目標用戶現(xiàn)有的好友關系，我們可以計算出目標用戶和每個用戶之間的共同鄰居數(shù)量，目標用戶的CN屬性的先驗概率可以基于目標用戶現(xiàn)有的朋友以及FOF所有信息統(tǒng)計得出，如表1所示。

Table 1 Prior probability of Common-Neighbors

在進行線性回歸分析前先用SPSS繪制表1中CN和p(CN)對應的散點圖，明顯可以看出呈線性關系，然后通過線性回歸分析的方法，得出方差分析表如表2所示。由于F明顯很大，Sig為0.000,即得出相關系數(shù)平方略小于1的線性函數(shù)，即式(6)中的F(x)。由此證明通過CN計算出的概率值具有可靠性。對于每個候選者通過計算CN和對應的概率P(CN)得出成為目標用戶好友的概率，式(6)有效地解決了因查找不到與目標用戶CN對應的先驗概率而造成無法推薦的問題。

Table 2 Table of Anovab

其中，a.預測變量：(常量)neighber;b.因變量：piror。

3.2 k-core 分析

微博內(nèi)容是用戶傳遞個人信息途徑，很大程度上可以反映用戶的興趣偏好。因此，從微博內(nèi)容中提取的用戶興趣偏好比興趣標簽更具有準確性。

k-core是基于節(jié)點度的凝聚子群[14]，如果一個子圖的所有節(jié)點的度都不小于k，則定義該子圖為k-core圖。如圖1a所示的一個1-core初始圖,去除1、2號節(jié)點，則變成兩個3-core子圖。k-core算法可以描述節(jié)點位于圖的中心位置還是邊緣位置，本文以關鍵詞作為節(jié)點，關鍵詞的共現(xiàn)關系用節(jié)點之間的邊表示。節(jié)點的k值越大，說明該節(jié)點越接近于語義網(wǎng)絡的中心，該節(jié)點代表的關鍵詞越能表達用戶的興趣主題；k值越小，越不能表達用戶的興趣主題。

Figure 1 k-core圖圖1 k-core

從表3可知，用戶興趣特征詞構成一個對稱的共詞矩陣[15,16]，例如，用戶感興趣的主題詞中“抗戰(zhàn)”和“勝利”的共現(xiàn)度是4，“抗戰(zhàn)”和“老兵”沒有共同出現(xiàn)，即共現(xiàn)度為0。因此，“抗戰(zhàn)”節(jié)點總的度是與所有主題詞與“抗戰(zhàn)”共現(xiàn)度總和為12，即節(jié)點度的計算公式[14]如式(7)所示。

(7)

其中，co-occurrenceNumi,j表示節(jié)點i和節(jié)點j共同出現(xiàn)的次數(shù)，n是所有節(jié)點的個數(shù)，di表示i節(jié)點的度。通過對節(jié)點k-core分析，可得出用戶興趣主題關鍵詞的核分布情況，如圖2所示，核心層即代表用戶最感興趣的主題分布情況。

Table 3 Characteristic words and co-word matrix

Figure 2 Cores distribution of user’s interest topic-oriented圖2 用戶興趣主題的核心分布圖

3.3 相似性計算

每個用戶關注的興趣主題不同，由發(fā)布的微博內(nèi)容提取出的興趣主題詞也不同，因此每個用戶的興趣特征向量都具有個性化。所以，我們用興趣主題詞特征向量的相似性來衡量用戶關注的興趣主題相似性。我們利用“有相似興趣的用戶更愿意成為朋友”和“朋友的朋友中有共同屬性的用戶更可能成為朋友”的理論計算出用戶之間成為朋友的可能性。

定義1score(u,v)=α×st(u,v)+(1-α)sp(u,v)表示用戶v成為用戶u朋友綜合得分。其中，st(u,v)表示用戶v和用戶u興趣特征相似性，sp(u,v)表示用戶v和用戶u具有某屬性且成為u好友的概率(如表1所示)。

基于以上定義提出的ITOR算法，首先根據(jù)微博內(nèi)容提取用戶的興趣特征，在擁有相似興趣特征的基礎上計算不同CN屬性的用戶成為目標用戶好友的概率，最后綜合計算出成為目標用戶朋友的score，將排序后的候選者選取TOP-k推薦給目標用戶。步驟4到步驟6的時間復雜度為O(N)+O(NlogN)。

算法1面向用戶興趣主題的好友推薦

輸入：目標用戶vi，用戶集合V，用戶之間的關注關系。

輸出：推薦列表中的TOP-k用戶。

步驟1構建用戶vi的好友關系，vi朋友的朋友集合為Vt,Vt集合中已經(jīng)成為用戶朋友的集合Vf;

步驟2通過式(4)得出與目標用戶vi有共同好友的任意用戶vj成為vi好友的先驗概率;

步驟3通過k-core分析，初始化用戶v的興趣主題特征；

步驟4FORvj∈V

步驟4.1計算和目標用戶vi之間的st相似性以及sp值；

步驟4.2綜合考慮st相似性和sp概率，得出成為目標用戶好友的總score；

步驟5END FOR

步驟6按照score排序，選取Top-k；

4 實驗分析

4.1 數(shù)據(jù)的獲取與處理

新浪API是第三方應用程序接口，在爬取數(shù)據(jù)時受到訪問頻率和一次性獲取數(shù)據(jù)量的限制，爬取的數(shù)據(jù)有很大的局限性。所以，本實驗數(shù)據(jù)是利用模擬登錄獲取2015年1月到12月的新浪微博內(nèi)容以及用戶之間的關注關系。微博內(nèi)容發(fā)布方式多樣化、篇幅短小、口語化等特點，給根據(jù)博文內(nèi)容提取興趣主題帶來很大困難。因此，我們以用戶為單位只分析1 000名用戶9月份的微博內(nèi)容以及其對應的關注關系。為了更好地提取用戶興趣主題，我們采取的微博內(nèi)容處理方式為：首先，刪除字數(shù)小于15的微博內(nèi)容。其次，用中國科學院的分詞系統(tǒng)(NLPIR)對文本進行分詞和停用詞處理，根據(jù)式(8)計算詞頻，保留高頻關鍵詞。

(8)

其中，I表示詞頻為1的詞的數(shù)量。

4.2 評價指標

Top-k的推薦算法中常用到的評價指標是準確率(Precision)、召回率(Recall)和F度量(F-measure)。評價指標的定義如下：

(9)

(10)

其中，hitnum為推薦命中的次數(shù)，TestSet為目標用戶的真實好友集合，Top-k為向用戶推薦的好友數(shù)量。

F度量(F-measure)是把準確率和召回率綜合考慮的一個衡量值，定義如下所示:

(11)

為了降低實驗的復雜度,人為設定α值為0.5，用本文提出的個性化推薦算法ITOR和基于概率原則推薦的算法[13]進行對比分析，分別取Top-k的個數(shù)k=2，5，10，20這四種情況進行推薦性能評價。

4.3 實驗結果及分析

因為本文提出的算法是基于“共同好友”這一屬性基礎上結合用戶的興趣進行推薦，是對利用戶屬性信息強化推薦性能這一算法[13]的改進。所以，實驗結果僅對“共同好友”這一屬性進行對比分析。

圖3顯示了在α=0.5時，本文提出的算法和利用屬性的先驗概率進行好友推薦算法的對比。實驗結果表明，當k取5到10時，本文提出的推薦算法效果達到最好，之后隨著k值變大，性能逐漸降低。然而，對比算法k值為10性能達到最好但仍小于本文算法的性能，雖然k值為20時對比算法性能優(yōu)于本文提出的算法性能，但是人們在選擇被推薦的好友時一般只關注前兩頁的用戶，之后即便對比算法推薦效果略高于本文算法，由于目標用戶幾乎不關注那些被推薦的用戶，推薦也失去了實際意義。與基于概率原則推薦的算法[13]相比，本文提出的算法偏重于結果的準確度和滿意度，增加的時間開銷源于算法步驟4文本相似性的計算，總的時間復雜度相差不大。所以，實驗結果分析表明本文提出的結合“共鄰好友”屬性和用戶興趣主題偏好進行推薦的算法具有一定的有效性。

Figure 3 Performance comparison of two algorithms圖3 算法性能對比

5 結束語

本文提出一種結合用戶社交網(wǎng)絡關系和用戶興趣主題相似性的方法來發(fā)現(xiàn)社交網(wǎng)絡中用戶潛在的好友。在“朋友的朋友，更可能成為朋友”的理論基礎上引入先驗概率，計算出有相同屬性的用戶成為朋友的概率，然后結合興趣主題相似性進行薦。新浪數(shù)據(jù)驗證表明，本文提出的算法在一定程度上提高了推薦的性能，具有一定的可行性，結合興趣的推薦不僅能提高用戶對推薦結果的滿意度，而且更易于用戶接受。

在接下來的工作中，將考慮到α值的優(yōu)化，降低文本相似度計算的時間開銷，采用隱形主題模型LDA(Latent Dirichlet Allocation)提取用戶興趣主題以及用戶興趣的變化等方面問題，根據(jù)興趣變化實時為用戶推薦好友。

[1] Yu S J.The dynamic competitive recommendation algorithm in social network services[J].Information Sciences,2012,187(1):1-14.

[2] Ma Hong-wei, Zhang Guang-wei, Li Peng.Survey of collaborative filtering algorithms[J].Journal of Chinese Computer Systems,2009,30(7): 1282-1288.(in Chinese)

[3] Liu F,Hong J L.Use of social network information to enhance collaborative filtering performance[J].Expert Systems with Applications,2010,37(7):4772-4778.

[4] Wang Yu, Gao Lin.Social circle-based algorithm for friend recommendation in online social networks[J].Chinese Journal of Computers,2014,37(4):801-808.(in Chinese)

[5] Armentano M G,Godoy D,Amandi A A.Followee recommendation based on text analysis of micro-blogging activity[J].Information Systems,2013,38(8): 1116-1127.

[6] Jamali M,Ester M.Trustwalker: A random walk model for combining trust-based and item-based recommendation[C]∥Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2009: 397-406.

[7] Weng J,Lim E P,Jiang J,et al.Twitterrank: Finding topic-sensitive influential twitterers[C]∥Proc of the 3rd ACM International Conference on Web Search and Data Mining,2010: 261-270.

[8] Gao Yong-bing, Yang Hong-lei,Liu Chun-xiang,et al.Research on the content and social filtering algorithm for friend recommendation[J].Microcomputer & Its Applications,2013,32(14): 75-78.(in Chinese)

[9] Jeckmans A,Tang Q,Hartel P.Poster: Privacy-preserving profile similarity computation in online social networks[C]∥Proc of ACM Conference on Computer and Communications Security(CCS 2011),2011:793-796.

[10] Zhang Peng, Qiao Xiu-quan,Li Xiao-feng, et al.Friend recommendation based on community dvision and user similarity[EB/OL].[2010-11-02].http:∥www.paper.edu.cn/releasepaper/content/201011-53.(in Chinese)

[11] Liben-Nowell D.An algorithmic approach to social networks[M].Massachusetts:Massachusetts Institute of Technology,2005.

[12] He Y,Tan J.Study on sina micro-blog personalized recommendation based on semantic network[J].Expert Systems with Applications,2015,42(10): 4797-4804.

[13] Zhang Z,Liu Y,Ding W,et al.Proposing a new friend recommendation method,FRUTAI,to enhance social media providers' performance[J].Decision Support Systems,2015,79(C):46-54.

[14] Carmi S,Havlin S,Kirkpatrick S,et al.A model of internet topology using k-shell decomposition[J].Proceedings of the National Academy of Sciences,2007,104(27): 11150-11154.

[15] Su H N,Lee P C.Mapping knowledge structure by keyword co-occurrence: A first look at journal papers in technology foresight[J].Scientometrics,2010,85(1): 65-79.

[16] Hu Chang-ping, Chen Guo. A new feature selection method based on term contribution in co-word analysis[J].New Technology of Library and Information Service,2013,7(8): 89-93.(in Chinese)

附中文參考文獻:

[2] 馬宏偉,張光衛(wèi),李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計算機系統(tǒng),2009,30(7): 1282-1288.

[4] 王玙,高琳.基于社交圈的在線社交網(wǎng)絡朋友推薦算法[J].計算機學報,2014,37(4):801-808.

[8] 高永兵,楊紅磊,劉春祥,等.基于內(nèi)容與社會過濾的好友推薦算法研究[J].微型機與應用,2013,32(14): 75-78.

[10] 張鵬，喬秀全，李曉峰.基于社區(qū)劃分和用戶相似度的好友推薦[EB/OL].[2010-11-02].http:∥www.paper.edu.cn/releasepaper/content/201011-53.

[16] 胡昌平,陳果.共詞分析中的詞語貢獻度特征選擇研究[J].現(xiàn)代圖書情報技術,2013,7(8): 89-93.