面向興趣主題的個性化好友推薦

齊會敏，劉 群，戴大祥

(重慶郵電大學(xué)重慶市計算機(jī)智能重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

1 引言

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

2 相關(guān)工作

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

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

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

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

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

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

(1)

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

(2)

2.2 FOF推薦算法

在社交媒體中好友推薦扮演著重要的角色，研究表明，高質(zhì)量的好友推薦可以提高用戶之間的交互，增強(qiáng)用戶對社交媒體的忠誠度。目前主要的方法是朋友的朋友推薦算法FOF(Friend-OF-Friend)和最短路徑推薦算法，本文主要涉及到FOF推薦算法?；A(chǔ)理論是如果用戶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),主要依賴于上述兩個理論基礎(chǔ)，首先經(jīng)過統(tǒng)計分析目標(biāo)用戶的直接好友、一跳好友與目標(biāo)用戶之間的共鄰好友以及一跳好友中已經(jīng)成為目標(biāo)用戶直接好友的用戶，利用先驗(yàn)概率的知識計算擁有不同共鄰好友數(shù)的用戶成為目標(biāo)用戶好友的概率。其次，根據(jù)k-core分析得出的興趣主題關(guān)鍵詞的分布情況來計算用戶之間興趣的相似性。

3.1 概率理論

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

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

(4)

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

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

(5)

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

P(x)=F(x)

(6)

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

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

Table 1 Prior probability of Common-Neighbors

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

Table 2 Table of Anovab

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

3.2 k-core 分析

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

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

Figure 1 k-core圖圖1 k-core

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

(7)

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

Table 3 Characteristic words and co-word matrix

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

3.3 相似性計算

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

定義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)容提取用戶的興趣特征，在擁有相似興趣特征的基礎(chǔ)上計算不同CN屬性的用戶成為目標(biāo)用戶好友的概率，最后綜合計算出成為目標(biāo)用戶朋友的score，將排序后的候選者選取TOP-k推薦給目標(biāo)用戶。步驟4到步驟6的時間復(fù)雜度為O(N)+O(NlogN)。

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

輸入：目標(biāo)用戶vi，用戶集合V，用戶之間的關(guān)注關(guān)系。

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

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

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

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

步驟4FORvj∈V

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

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

步驟5END FOR

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

4 實(shí)驗(yàn)分析

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

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

(8)

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

4.2 評價指標(biāo)

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

(9)

(10)

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

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

(11)

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

4.3 實(shí)驗(yàn)結(jié)果及分析

因?yàn)楸疚奶岢龅乃惴ㄊ腔凇肮餐糜选边@一屬性基礎(chǔ)上結(jié)合用戶的興趣進(jìn)行推薦，是對利用戶屬性信息強(qiáng)化推薦性能這一算法[13]的改進(jìn)。所以，實(shí)驗(yàn)結(jié)果僅對“共同好友”這一屬性進(jìn)行對比分析。

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

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

5 結(jié)束語

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

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

[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)

附中文參考文獻(xiàn):

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

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

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

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

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