程倩倩，王路路，鄭 濤，姬東鴻

(武漢大學(xué)計(jì)算機(jī)學(xué)院，武漢430072)

1 概述

隨著Web2．0的迅速發(fā)展，社交網(wǎng)絡(luò)與人們的生活越來越密切，成為人們生活中必不可少的一部分。一方面，社交網(wǎng)絡(luò)能夠幫助用戶認(rèn)識有相同愛好的人，聯(lián)系現(xiàn)實(shí)生活中的好友、分享信息等。另一方面，社交網(wǎng)絡(luò)也為用戶提供了海量社交信息，使大家可以共同分享與交流。社交網(wǎng)絡(luò)的運(yùn)作蘊(yùn)藏了巨大商機(jī)，挖掘和利用這些信息已經(jīng)在各領(lǐng)域展開，但是隨著用戶數(shù)量和信息量的增大，信息過載問題變得越來越嚴(yán)重，如何從大量用戶中為目標(biāo)用戶推薦感興趣的用戶，即好友推薦系統(tǒng)是一個(gè)重要的研究方向。

好友推薦系統(tǒng)研究在學(xué)術(shù)界引起了高度關(guān)注，存在諸多推薦算法，主要包括:基于協(xié)同過濾的推薦，基于內(nèi)容的推薦，基于關(guān)聯(lián)規(guī)則技術(shù)的推薦，基于聚類技術(shù)的推薦等。其中，基于協(xié)同過濾的推薦算法是目前最受歡迎的推薦技術(shù)，不依賴物品本身，主要依賴目標(biāo)用戶或與目標(biāo)用戶相似的用戶對物品的評分矩陣進(jìn)行推薦。但是社交網(wǎng)絡(luò)中不存在這種共同的打分項(xiàng)，所以，這種經(jīng)典的推薦算法不能直接用于用戶社交網(wǎng)絡(luò)的好友推薦，并且也存在一些難以克服的問題，比如:可信問題，冷啟動問題和數(shù)據(jù)稀疏問題等［1］。

由于在用戶微博內(nèi)容中隱含用戶感興趣的話題和領(lǐng)域，因此基于用戶內(nèi)容的推薦算法也是一項(xiàng)重要技術(shù)。文獻(xiàn)［2］對用戶的Twitter內(nèi)容進(jìn)行處理，發(fā)現(xiàn)用戶的興趣點(diǎn)，進(jìn)而為目標(biāo)用戶推薦具有相同興趣的用戶。這是對基于用戶內(nèi)容的推薦算法的一個(gè)運(yùn)用。但是這種推薦算法僅使用用戶的內(nèi)容信息，推薦結(jié)果往往過于專一化，更傾向于推薦具有相同興趣愛好的陌生人［3］。

一些研究者將基于內(nèi)容的推薦算法和社交網(wǎng)絡(luò)的好友關(guān)系相結(jié)合。文獻(xiàn)［4］提出Twittomender系統(tǒng)，根據(jù)目標(biāo)用戶的Twitter內(nèi)容、好友、粉絲以及好友和粉絲的Twitter內(nèi)容進(jìn)行建模。文獻(xiàn)［5］利用概率模型進(jìn)行協(xié)同過濾，進(jìn)而為目標(biāo)用戶進(jìn)行推薦最感興趣的用戶，概率模型綜合考慮Twitter內(nèi)容和用戶間的關(guān)系。但是上述研究都沒有使用大量存在的用戶間的交互信息和用戶的個(gè)人信息。

綜上所述，目前在好友推薦系統(tǒng)中采用的信息過于單一，沒有綜合利用多種信息特征，導(dǎo)致推薦效果不佳。本文歸納了影響用戶推薦的4類信息:用戶標(biāo)簽信息，用戶內(nèi)容信息，用戶交互信息，用戶社交拓?fù)湫畔?，利用這些信息計(jì)算出相關(guān)特征，并采用分類算法為目標(biāo)用戶進(jìn)行好友推薦。

2 相關(guān)知識

2．1 線性判別分析主題模型

線性判別分析(Linear Discriminant Analysis，LDA)是一種非監(jiān)督學(xué)習(xí)技術(shù)，可以用來挖掘大規(guī)模文檔集或語料庫中潛藏的主題信息。它采用詞袋的方法，將每一篇文檔視為一個(gè)詞頻向量，從而將文本信息轉(zhuǎn)化為易于建模的數(shù)字信息。每一篇文檔被看作主題的一種概率分布，主題又被看作是單詞的一種概率分布。

對于語料庫中的每一篇文檔，LDA定義了如下的生成過程:

(1)選擇N～Possion(ξ);

(2)選擇一個(gè)多項(xiàng)式分布參數(shù)θ～Dir(i);

(3)對于文檔中的每個(gè)詞:

1)選擇一個(gè)topic z～Multinomial(θ)，z是從以θ為參數(shù)的多項(xiàng)式分布中選出，共有k個(gè)topic;

2)從概率分布p(wn|zn，β)中選擇一個(gè)詞 wn，p為topic zn下的一個(gè)多項(xiàng)式分布。

上述過程可以用圖1所示的貝葉斯網(wǎng)絡(luò)圖來表示。

圖1 貝葉斯網(wǎng)絡(luò)

在圖1中，α是θ的超參數(shù);β是Φ的超參數(shù);θ是文檔-主題概率分布;Φ是主題-詞概率分布;z是詞的主題分布;w是詞;D是文檔數(shù);N是詞數(shù);T是主題數(shù)。整個(gè)貝葉斯網(wǎng)絡(luò)圖的聯(lián)合概率為:

2．2 K最近鄰算法

K最近鄰(K Nearest Neighbor，KNN)分類算法的核心思想是如果一個(gè)對象在特征空間中的k個(gè)最相似的對象中的大多數(shù)屬于某一個(gè)類別，則該對象也屬于該類別，并具有該類別上對象的特性。

使用KNN算法對未知類別的點(diǎn)進(jìn)行分類，具體步驟如下:

(1)計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與該點(diǎn)之間的距離;

(2)按照距離遞增次序排列;

(3)選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn);

(4)確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率;

(5)返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類。

3 微博好友推薦算法

本文通過分析總結(jié)了影響好友推薦的4類關(guān)鍵用戶信息:(1)用戶內(nèi)容信息，主要是指用戶發(fā)布、轉(zhuǎn)發(fā)的微博內(nèi)容;(2)用戶標(biāo)簽信息，這是用戶注冊時(shí)對自己興趣愛好的一組標(biāo)簽描述;(3)用戶交互信息，這是用戶間評論、轉(zhuǎn)發(fā)、贊等交互行為;(4)用戶社交拓?fù)湫畔?，這是用戶的關(guān)注列表和用戶的被關(guān)注列表，即粉絲列表。在這4類關(guān)鍵信息的基礎(chǔ)上，利用LDA主題模型從用戶內(nèi)容信息中挖掘用戶潛在的興趣愛好，并計(jì)算用戶間的主題相關(guān)度;通過用戶標(biāo)簽信息，計(jì)算用戶間的顯式的興趣相關(guān)度;從用戶交互信息和社交拓?fù)湫畔⒅?，利用加?quán)最小信息比率(Weighted Minimum-message Ratio，WMR)［6］算法計(jì)算用戶間的親密度;最后將主題相關(guān)度、興趣相關(guān)度、親密度作為特征向量，利用KNN分類方法進(jìn)行好友推薦。

3．1 主題相關(guān)度計(jì)算

主題模型已經(jīng)成功應(yīng)用于很多文本挖掘任務(wù)中，比如熱點(diǎn)主題發(fā)現(xiàn)、用戶興趣發(fā)現(xiàn)、文本分類等［7-9］。本文采用LDA主題模型對用戶潛在的興趣進(jìn)行發(fā)現(xiàn)。由于微博內(nèi)容長度必須限制在140字以內(nèi)，而一些研究者指出LDA模型應(yīng)用于短文本時(shí)準(zhǔn)確率較低［10］，它適合用于長文本。但文獻(xiàn)［11］實(shí)驗(yàn)證明在特定參數(shù)設(shè)置下，LDA模型應(yīng)用于短文本時(shí)同樣可以取得和長文本一樣的效果。另外，文獻(xiàn)［12］通過在WebMd數(shù)據(jù)集上的實(shí)驗(yàn)證明，即使在平均長度僅為5．2個(gè)詞的短文本上LDA模型也可以取得很好的效果。為準(zhǔn)確挖掘用戶感興趣的主題，本文把用戶的所有微博內(nèi)容集中到一個(gè)文檔中，即一個(gè)用戶對應(yīng)一篇內(nèi)容文檔;然后利用漢語詞法分詞系統(tǒng)(Institute of Computing Technology，Chinese LexicalAnalysis System，ICTCLAS)對文檔進(jìn)行分詞，由于名詞和動詞對主題的辨識作用較大，因此只提取出文檔中的名詞和動詞，去掉其他詞性的詞語以及停用詞;然后利用LDA主題模型挖掘每篇文檔的主題，結(jié)果存儲到矩陣中;最后使用Jensen-Shannon散度計(jì)算主題的相關(guān)度:

3．2 標(biāo)簽相關(guān)度計(jì)算

標(biāo)簽是用戶在完善個(gè)人資料時(shí)填寫的關(guān)于個(gè)人興趣愛好描述的一組關(guān)鍵字，是表征用戶興趣愛好的一種重要信息。用戶相同的標(biāo)簽越多，用戶與標(biāo)簽的關(guān)聯(lián)度越大，則2個(gè)用戶的興趣愛好越相似。本文采用式(1)計(jì)算2個(gè)用戶的標(biāo)簽相似度:

其中，c為用戶 i、用戶 j共同的標(biāo)簽集合;t∈c，w(i，t)表示標(biāo)簽 t與用戶 i的關(guān)聯(lián)度，w(i，t)的初始值為1，標(biāo)簽每次在用戶i的關(guān)注用戶中出現(xiàn)一次值增加0．1，最后對Simlabel值進(jìn)行歸一化處理。

3．3 親密度計(jì)算

用戶交互信息即微博用戶間的信息交互行為，包括評論、轉(zhuǎn)發(fā)、贊等動作。交互行為直接反映了用戶間社交關(guān)系的強(qiáng)弱，即用戶間的親密度，交互越頻繁說明用戶間的關(guān)系越親密。文獻(xiàn)［13］將用戶網(wǎng)絡(luò)分成2個(gè)部分，即相似用戶網(wǎng)絡(luò)和熟悉用戶網(wǎng)絡(luò)，并通過比較這2類網(wǎng)絡(luò)的推薦情況，證明基于熟悉用戶網(wǎng)絡(luò)推薦的效果要好于基于相似網(wǎng)絡(luò)的推薦。因此，構(gòu)建一個(gè)以用戶為頂點(diǎn)、交互次數(shù)為邊的有向網(wǎng)絡(luò)是十分有必要的。根據(jù)文獻(xiàn)［14］中提出的小世界理論，任何2個(gè)陌生人最多不超過6個(gè)中間人就可以互相認(rèn)識。所以，只需以目標(biāo)用戶為根節(jié)點(diǎn)，向外延伸6層即可。用戶間的交互信息可以使用圖2的網(wǎng)絡(luò)圖進(jìn)行模擬。

圖2 用戶交互網(wǎng)絡(luò)

本文結(jié)合文獻(xiàn)［6］中提出的WMR算法，計(jì)算用戶間的親密度。首先用戶交互是一個(gè)雙向的行為，取2邊中較小的一個(gè)值，這樣可以有效防止騷擾性的用戶交互;然后取消同層用戶間交互的信息，因?yàn)檫@些信息對最終不同層用戶與目標(biāo)用戶的親密度的計(jì)算沒有影響，經(jīng)過處理，得到如圖3所示的一個(gè)無向的網(wǎng)絡(luò)圖;最后使用式(2)計(jì)算用戶間的親密度。

其中，Sh∈Pk(j)∩L(h)，h=1，2，…，6;j∈L(h)且h≠1;Cij表示用戶i和用戶j之間交互的次數(shù);L(h)表示在網(wǎng)絡(luò)圖中所有屬于第h層的用戶;Pk(j)表示從根節(jié)點(diǎn)即目標(biāo)用戶開始到達(dá)用戶j的第k條路徑;Pk(j)．CSum表示路徑Pk(j)上交互次數(shù)的總和;L(h)．CSum表示第h層交互次數(shù)的總和;C(i，j)表示 Cij占 L(h)．CSum 的比例，用戶 i∈L(h-1)，用戶j∈L(h);Intimacy(o，j)表示用戶j與目標(biāo)用戶o的親密度。

圖3 改進(jìn)后的用戶交互網(wǎng)絡(luò)

3．4 利用KNN分類算法的微博好友推薦

目前用戶推薦研究采用的信息都比較單一［15-16］，且都是采用排序函數(shù)實(shí)現(xiàn)排序，最終得到推薦列表，這樣的推薦模型在參數(shù)較多的情況下效果都不理想。因此，本文充分考慮用戶內(nèi)容的主題相似度Simtopic、用戶的標(biāo)簽相似度Simlabel，以及用戶的親密度Intimacy，然后利用KNN分類算法進(jìn)行分類推薦。推薦框架如圖4所示，帶箭頭的虛線表示用戶間的關(guān)注關(guān)系。訓(xùn)練數(shù)據(jù)是由目標(biāo)用戶u的部分好友以及非好友組成的集合，如果用戶i是用戶u的好友，標(biāo)記為+1，否則標(biāo)記為-1。測試數(shù)據(jù)使用的用戶數(shù)據(jù)類型和訓(xùn)練數(shù)據(jù)相同，對于每個(gè)測試用戶i，利用KNN算法計(jì)算分類結(jié)果。然后根據(jù)式(3)計(jì)算測試用戶i的推薦得分，最后根據(jù)得分降序?yàn)槟繕?biāo)用戶u產(chǎn)生一個(gè)好友推薦列表。

其中，P(i)表示測試用戶的特征向量;P(j)表示訓(xùn)練用戶的特征向量;k為KNN算法中k的取值;label表示用戶i的分類結(jié)果，label的取值為+1，-1。

圖4 利用KNN分類算法的微博好友推薦框架

4 實(shí)驗(yàn)結(jié)果及評估

4．1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

新浪微博是在國內(nèi)使用人數(shù)最多、最受歡迎的微博，用戶可以標(biāo)示自己的興趣愛好、添加好友、關(guān)注主題等。本文實(shí)驗(yàn)使用新浪微博API抓取用戶的標(biāo)簽信息，用戶的微博以及每條微博的交互信息，如:評論，轉(zhuǎn)發(fā)，贊。從8個(gè)不同的領(lǐng)域選取一些用戶作為目標(biāo)用戶，采用廣度優(yōu)先的算法，抓取了2萬個(gè)用戶從2013年10月16日-2014年1月16日的數(shù)據(jù)。為了提高實(shí)驗(yàn)算法的準(zhǔn)確性，首先對數(shù)據(jù)進(jìn)行清洗:

(1)排除粉絲數(shù)超過10萬但好友人數(shù)小于500的用戶。這類用戶通常是非常出名的用戶，這些用戶的微博有大量粉絲的轉(zhuǎn)發(fā)、評論，但是鮮有互動，因此本文暫不考慮這類用戶。

(2)排除粉絲數(shù)少于10且微博數(shù)少于10的用戶。這些用戶粉絲和微博數(shù)過少，說明這些用戶很少使用微博，因此為他們推薦的意義不大。

經(jīng)過處理后，得到5 224個(gè)用戶數(shù)據(jù)，其中包括266 627條微博，105 583條交互信息。本文采用交叉實(shí)驗(yàn)，將數(shù)據(jù)集劃分為80%訓(xùn)練集和20%測試集并進(jìn)行多次實(shí)驗(yàn)以驗(yàn)證本文算法。

當(dāng)用LDA模型挖掘用戶微博的主題時(shí)，本文根據(jù)文獻(xiàn)［17］，采用貝葉斯統(tǒng)計(jì)中的標(biāo)準(zhǔn)方法對LDA模型的參數(shù)進(jìn)行設(shè)置。令α=50/T，T是主題數(shù)，取T=50，迭代次數(shù)為100次。該設(shè)置為經(jīng)驗(yàn)值，經(jīng)過多次實(shí)驗(yàn)結(jié)果表明，這些值在本文數(shù)據(jù)集上為最佳參數(shù)值。

4．2 評價(jià)指標(biāo)

對于實(shí)驗(yàn)結(jié)果，本文采用準(zhǔn)確率(precision)、召回率(recall)、F1度量值(F1-measure)作為衡量標(biāo)準(zhǔn)。

準(zhǔn)確率是推薦列表中正確推薦個(gè)數(shù)Nrt與推薦總數(shù)Nr之比，其值越高說明推薦準(zhǔn)確率越大。

召回率是推薦列表中正確推薦個(gè)數(shù)Nrt與用戶總的好友個(gè)數(shù)Nf之比，值越高表示推薦效果越好。

F1度量值(F1-measure)是準(zhǔn)確率和召回率的加權(quán)調(diào)和平均，它綜合了準(zhǔn)確率和召回率的結(jié)果。F1度量值越高說明推薦效果越好。

在本文實(shí)驗(yàn)中，取不同推薦個(gè)數(shù)(N=2，4，6，8，10)進(jìn)行對比。

4．3 結(jié)果分析

本文針對基于內(nèi)容的推薦算法、基于社會過濾的推薦算法［18］和基于多因素分類的推薦算法(本文算法)分別進(jìn)行實(shí)驗(yàn)并進(jìn)行對比。當(dāng)N取不同值時(shí)3種算法的準(zhǔn)確率、召回率、F1度量值分別如圖5～圖7所示。

圖5 算法準(zhǔn)確率對比

圖6 算法召回率對比

圖7 算法F1度量值對比

當(dāng)N≤4時(shí)，基于內(nèi)容的算法準(zhǔn)確率高于基于社會過濾的推薦算法的準(zhǔn)確率，而隨著N的增大，基于內(nèi)容的算法準(zhǔn)確率低于基于社會過濾的算法，它是這3種算法中準(zhǔn)確率最低的，本文算法準(zhǔn)確率最高。當(dāng)N=4時(shí)，本文算法準(zhǔn)確率達(dá)到最高的16．5%。

在召回率方面，當(dāng)N＜10時(shí)，基于多特征分類的算法的召回率最高，基于社會過濾的算法次之，基于內(nèi)容的算法最低。當(dāng)N=10時(shí)，本文算法召回率最低。當(dāng)N=6時(shí)，本文算法的召回率達(dá)到了最高的26．8%。

從F1度量值方面，本文算法的推薦效果最好，而基于內(nèi)容的算法推薦效果最差。一方面可能是因?yàn)槲⒉﹥?nèi)容簡短，而且內(nèi)容中存在大量符號、表情、縮寫等，導(dǎo)致效果不好;另一方面，本文算法綜合考慮了用戶的主題相似度、標(biāo)簽相似度和用戶間的親密度，利用更多的特征，所以取得了較好的推薦效果。而本文算法效果好于基于社會過濾的算法效果，是因?yàn)楸疚脑谟?jì)算用戶親密度時(shí)已經(jīng)隱含利用用戶的社交網(wǎng)絡(luò)信息，而且還進(jìn)一步利用用戶的主題相似度和標(biāo)簽相似度來提高推薦效果。當(dāng)N=6時(shí)，本文算法的F1度量值達(dá)到最高的19．2%。

綜上所述，本文提出的基于多特征分類的推薦算法要優(yōu)于其他推薦算法。

5 結(jié)束語

本文總結(jié)影響微博用戶推薦的4類信息，并提出如何使用這些信息的方法，通過在新浪微博數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明本文提出的基于多特征分類的推薦算法能有效為用戶進(jìn)行好友推薦，但其對于新用戶，由于缺少用戶內(nèi)容信息、交互信息和社交拓?fù)湫畔?，因此退化為類似基于?biāo)簽的推薦算法，推薦效果不理想。在今后工作中，將研究使用微博用戶的其他信息進(jìn)行好友推薦，如用戶的影響力、傳播范圍等，進(jìn)一步改善推薦效果。

［1］ 李克潮，梁正友．基于多特征的個(gè)性化圖書推薦算法［J］．計(jì)算機(jī)工程，2012，38(11):34-37．

［2］ Piao S，Whittle J．A Feasibility Study on Extracting Twitter Users’Interests Using NLP Tools for Serendipitous Connections［C］//Proceedings of the 3rd International Conference on Privacy，Security，Risk and Trust and the 3rd International Conference on Social Computing．Washington D．C．，USA:IEEE Press，2011:910-915．

［3］ Chen J，Geyer W，Duguan C，et al．Make New Friends，But Keep the Old:Recommending People on Social Networking Sites［C］//Proceedings of SIGCHI Conference on Human Factors in Computing Systems．New York，USA:ACM Press，2009:201-210．

［4］ Hannon J，Bennett M，Smyth B．Recommending Twitter Usersto Follow Using Contentand Collaborative Filtering Approaches［C］//Proceedings of the 4th ACM Conference on Recommender Systems．New York，USA:ACM Press，2010:199-206．

［5］ Jamali M，Ester M．A Matrix Factorization Technique with Trust Propagation for Recommendation in Social Networks［C］//Proceedings of the 4th ACM Conference on Recommender Systems．New York，USA:ACM Press，2010:135-142．

［6］ Lo S，Lin C．WMR——A Graph-based Algorithm for Friend Recommendation［C］//Proceedingsof2006 IEEE/WIC/ACM InternationalConferenceonWeb Intelligence．Piscataway，USA:IEEE Computer Society，2006:121-128．

［7］ Blei D M，Ng A Y，Jordan M I．LatentDirichlet Allocation［J］．Journal of Machine Learning Research，2003，(3):993-1022．

［8］ Zeng Jianping，Zhang Shiyong．Variable Space Hidden Markov Model for Topic Detection and Analysis［J］．Knowledge-based Systems，2007，20(7):607-613．

［9］ Zeng Jianping，Duan Jiangjiao，Wang Wei，etal．Semantic Multi-grain Mixture Topic Model for Text Analysis［J］．Expert Systems with Applications，2011，38(4):3574-3579．

［10］ Titov I，McDonald R．ModelingOnline Reviews with Multigrain Topic Models［C］//Proceedings ofthe17th International Conference on World Wide Web．New York，USA:ACM Press，2008:111-120．

［11］ Duan J，Zeng J．Web Objectionable TextContent Detection Using Topic Modeling Technique［J］．Expert Systems with Applications，2013，40(15):6094-6104．

［12］ Denecke K，Brosowski M．TopicDetection in Noisy Data Sources［C］//Proceedings of the 15th International Conference on Digital Information Management．Piscataway，USA:IEEE Press，2010:50-55．

［13］ Guy I，Zwerdling N，Carmel D，et al．Person-alized Recommendation of Social Software Items Based on Social Relations［C］//Proceedings of the 3rd ACM Conference on Recommender Systems．New York，USA:ACM Press，2009:53-60．

［14］ Milgram S．TheSmall World Problem［J］．Psychology Today，1967，2(1):60-67．

［15］ Zhou T C，Ma H，Lyu M R，et al．UserRec:A User Recommendation Framework in Social Tagging Systems［C］//Proceedings of the 24th AAAI Conference on Artificial Intelligence．Palo Alto，USA:AAAI Press，2010．

［16］ Koga H，Taniguchi T．Developing aUser Recommendation Engine on Twitter Using Estimated Latent Topics［M］//Jacko J A．Human-computer Interaction．Design and Development Approaches．Berlin，Germany:Springer，2011:461-470．

［17］ Weng J，Lim E P，Jiang J，et al．Twitterrank:Finding Topic-sensitive Influential Twitterers［C］//Proceedings of the 3rd ACM International Conference on Web Search And Data Mining．New York，USA:ACM Press，2010:261-270．

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