高永兵，楊紅磊，劉春祥，胡文江

（內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭014010）

伴隨著Web2.0的到來，各種各樣的社交網(wǎng)站不斷涌現(xiàn)。如國外的Facebook、twitter、Flickr，國 內(nèi) 的新 浪微博、人人網(wǎng)等。在這些社交網(wǎng)站上，用戶能夠添加自己在日常生活中已經(jīng)認(rèn)識的好友，也可以在網(wǎng)絡(luò)上結(jié)交新的朋友[1]。

經(jīng)研究，Savage[2]發(fā)現(xiàn)在Facebook這類網(wǎng)站上用戶主要是和自己在生活中認(rèn)識的人進(jìn)行交流；Dimicco[3]則發(fā)現(xiàn)在twitter等網(wǎng)站上用戶則更傾向于和自己不認(rèn)識的人結(jié)交好友；Ehrlich[4]介紹了依據(jù)用戶的聊天信息來幫助用戶尋找專家的方法，但是不能夠給用戶推薦個性化好友。

在社交網(wǎng)絡(luò)中，用戶想要添加的好友不僅僅是自己在日常生活中的好友，同時那些雖然用戶不認(rèn)識但極為感興趣的其他用戶也是理想的好友。無論是為用戶推薦現(xiàn)實中已經(jīng)認(rèn)識的朋友還是推薦和用戶有共同興趣的好友，目前的好友推薦算法都不能很好地解決問題。本文通過分析現(xiàn)有好友推薦算法的不足之處，綜合考慮用戶日常生活中的好友以及用戶的興趣愛好等個人信息，有效地解決了好友推薦中遇到的冷啟動（為新注冊用戶推薦好友）、用戶個人信息過少而無法推薦好友等問題。

1 社會過濾算法

社會過濾算法(social filtering)建立在這樣一個前提下：如果甲的朋友是乙的朋友，那么甲有可能是乙的朋友。已經(jīng)有很多社會網(wǎng)絡(luò)分析方法采用了類似的方法找到了鄰居和合適的途徑。這種推薦方法不僅僅是通過考慮用戶的興趣愛好，還通過分析隱含在用戶每一個好友身上的信息，來給用戶準(zhǔn)確地推薦好友[5]。這種算法主要用在社交網(wǎng)絡(luò)中的“你可能認(rèn)識的人”這一板塊。

在介紹算法之前，給出以下定義：在社交網(wǎng)絡(luò)中，如果用戶b是用戶a的好友，那么定義為F(a，b)。算法描述如下：

假設(shè)存在用戶a和用戶u，用戶u的推薦好友候選集定義為RC(u)，用戶a是用戶u的好友,同時用戶c又是用戶a的好友，則用戶c為用戶u的推薦候選集中的一個用戶。用公式表達(dá)為：

RC(u)={c|F(u，a)∧F(a，c)∧?F(u，c)}

共同好友集定義為MF(u，c)，公式表達(dá)為：

MF(u，c)={a|F(u，a)∧F(a，c)}

通過共同好友的關(guān)系，在用戶u和用戶c之間添加了聯(lián)系。然后通過計算共同好友集MF(u，c)得出用戶c的可推薦百分比。通過候選集中用戶可推薦百分比的高低排序給目標(biāo)用戶u推薦得分最高的用戶Top-N。

該算法較為適合與現(xiàn)實社會有較大聯(lián)系的社交網(wǎng)站，其較大的不足之處為目標(biāo)用戶必須有一定的好友數(shù)量的積累。對于一個新注冊或者好友數(shù)量較少的用戶來說，不能夠使用該算法來給用戶推薦好友。

2 基于內(nèi)容推薦算法

基于內(nèi)容推薦算法基于以下思想：如果兩個人有相似的話題，他們也許會更愿意去認(rèn)識對方。換句話說，這個算法是努力地尋找與目標(biāo)用戶有相似愛好的用戶。這與信息挖掘領(lǐng)域的發(fā)現(xiàn)文檔之間相似內(nèi)容的方法極為相似。

首先使用文本內(nèi)容創(chuàng)建一個詞向量代表每一個用戶。從用戶的個人設(shè)置項和狀態(tài)信息(發(fā)布的文章信息、對個人的描述等)中提取關(guān)鍵詞[6]，也可以提取用戶工作所在地等信息。所有保留的詞通過一個詞向量Vu=(vu(w1)，…，vu(wm))來描述用戶u，m代表所有單詞的數(shù)量，每一個vu(wi)代表用戶u的興趣詞，wi代表這個詞在用戶所有的興趣中的權(quán)重。單詞vu(wi)的權(quán)重通過TF-IDF算法來計算：

其中u(wi)代表用戶u使用過的保留詞，W代表用戶u使用過的所有單詞。

其中E代表所有的用戶，U代表在所有用戶中使用過單詞vu(wi)的用戶數(shù)。

vu(wi)=TFu(wi)×IDFu(wi)

通過余弦相似度來計算用戶a和用戶b的兩個向量Va和Vb的相似度?？梢灾庇^地認(rèn)為如果用戶a和用戶b在日常使用中分享了相同的關(guān)鍵詞，而其他用戶很少分享這些關(guān)鍵詞，則他們有很大的相似性。作為一個被推薦的用戶c，在所有分享的關(guān)鍵詞中，只顯示前10個數(shù)量積最高的關(guān)鍵詞。直觀地認(rèn)為它們是用戶u和用戶c分享的最具有代表性的關(guān)鍵詞。

基于內(nèi)容和鏈接的算法主要是通過使用社交網(wǎng)絡(luò)中的社交鏈接信息加強基于內(nèi)容匹配算法的準(zhǔn)確度[7]。算法通過將那些社交網(wǎng)絡(luò)中的弱約束和隱式用戶顯示出來，目標(biāo)用戶更樂意于接受這種算法。此算法與基于內(nèi)容的算法中計算相似度的方法有很大的相似之處。然而，與向用戶推薦前幾位相似度最高的用戶方法不同的是，如果用戶u和用戶c之間存在有效的鏈接，給用戶u和用戶c之間的相似度加50%的權(quán)重，即如果用戶u和用戶c之間存在聯(lián)系，那么在推薦時它的推薦順序?qū)旁诨趦?nèi)容相似度之前。

一個有效的鏈接的定義為：將若干個用戶排成一隊，第一個用戶作為目標(biāo)用戶，最后一個用戶作為被推薦用戶，每兩個用戶a和b之間都必須至少滿足以下3個條件之一：

(1)a主動聯(lián)系過b；

(2)a對b有過評論；

(3)b主動聯(lián)系過a。

該定義確保了兩個用戶之間存有社會鏈接并且最低限度地認(rèn)為他們或者他們的好友之間是熟人或者有一定的互動關(guān)系。例如用戶a給用戶c評論過，而用戶b和用戶c又是好友關(guān)系，則認(rèn)為用戶a和用戶b之間存在一個有效鏈接。

在推薦時使用有效鏈接，同時還考慮相同關(guān)鍵詞的內(nèi)容匹配技術(shù)，也可以把鏈接作為一種擴(kuò)展，包括考慮用戶u和候選集中用戶c之間的所有鏈接。在推薦的用戶中，至少77.8%都需要考慮有效鏈接信息。

3 個性化好友推薦算法

為了解決社會過濾算法遇到的冷啟動問題以及基于內(nèi)容相似性算法的準(zhǔn)確率較低問題，根據(jù)對現(xiàn)有算法的總結(jié)，本文提出了改進(jìn)的個性化好友推薦算法。經(jīng)過實驗驗證，本算法能夠有效地解決這些問題。

根據(jù)用戶的個人特征信息，計算出與目標(biāo)用戶詞特征向量最為相似的用戶集，即要產(chǎn)生一個與用戶u的特征信息相似性從大到小排列的推薦集。對于目標(biāo)用戶u，通過他的個人特征信息及特定相似度函數(shù)，計算出與他的特征信息最相近的N個用戶作為目標(biāo)用戶u的最近鄰居集，即為目標(biāo)用戶u的Top-N推薦集。

(1)收集用戶信息

在社交網(wǎng)站中，用戶會描述自己的興趣以及個人信息。例如在人人網(wǎng)中，用戶注冊時會選擇自己所在學(xué)校、專業(yè)、班級、地理位置等，這些就代表了用戶的個人特征；在微博中，用戶會選擇自己感興趣的方向、擅長的領(lǐng)域等標(biāo)簽，這些也同樣代表了用戶的個人特征。推薦算法給用戶推薦好友時，應(yīng)該充分利用用戶的這些個人特征信息。

(2)建立用戶的詞特征向量(UserVector)

建立一個詞特征向量Vu=(w1，…，wi，…，wm)來描述用戶u，其中m代表用戶的單詞數(shù)量，wi代表用戶的個人信息（興趣愛好、地理位置等）。此處按照每個網(wǎng)站中的特定順序來給用戶的詞特征向量中的每一個詞排序。

(3)計算用戶特征向量之間的相似度

通過相似度的計算，得到與目標(biāo)用戶u特征信息最為相似的Top-N推薦集。

(4)生成推薦好友候選集

取出N個最靠前的用戶作為目標(biāo)用戶的推薦好友候選集，即產(chǎn)生一個與目標(biāo)用戶u的個人信息相似度從高到低排列的推薦好友候選集r。

(5)檢測目標(biāo)用戶好友數(shù)

根據(jù)目標(biāo)用戶u的好友數(shù)量來確定是否繼續(xù)使用社會過濾推薦算法。如果目標(biāo)用戶u沒有好友，則直接將推薦出來的推薦好友候選集推薦給用戶u；如果目標(biāo)用戶u有好友，則繼續(xù)使用社會過濾推薦算法給用戶u推薦好友。

(6)計算目標(biāo)用戶和推薦好友候選集中每個用戶的共同好友數(shù)

目標(biāo)用戶u的推薦好友候選集定義為RC(u)，用戶a是用戶u的好友，用戶c又是用戶a的好友，同時用戶c不是用戶u的好友。則用戶c為用戶u的推薦候選集中的一個用戶。用公式表達(dá)為：

RC(u)={c|F(u，a)∧F(a，c)∧?F(u，c)}

共同好友集定義為MF(u，c)，公式表達(dá)為：

MF(u，c)={a|F(u，a)∧F(a，c)}

通過共同好友的關(guān)系，在用戶u和用戶c之間添加了聯(lián)系。然后通過計算共同好友集MF(u，c)得出用戶c的可推薦百分比。

設(shè)P是n個用戶之間的好友關(guān)系矩陣。在這個矩陣?yán)?，如果用戶i和用戶j是好友關(guān)系，則Pij為1，否則為0。

設(shè)A為從矩陣P計算得出的關(guān)聯(lián)矩陣，含n個用戶彼此關(guān)聯(lián)規(guī)則的置信度。A是n×n的一個矩陣，n為用戶的數(shù)量，ai，j是i?j關(guān)聯(lián)規(guī)則的置信度。ai，j表示同時是用戶i、j的好友的用戶在所有用戶N中的比例。

目標(biāo)用戶u的偏好向量u為一個1×n的矩陣，uij表示目標(biāo)用戶u和用戶j的共同好友關(guān)系，它是P矩陣的橫向量。為目標(biāo)用戶推薦的矢量s可以從計算關(guān)聯(lián)矩陣A和目標(biāo)用戶的偏好向量u的乘積得出，計算公式為：

s=u×A

(7)根據(jù)共同好友數(shù)對推薦好友候選集重新排序

根據(jù)目標(biāo)用戶與推薦集中用戶的共同好友個數(shù)，產(chǎn)生一個與目標(biāo)用戶的共同好友數(shù)從多到少的好友推薦候選集s。

(8)選定合適的權(quán)重

選定權(quán)重的值，新算法的計算公式如下：

NF=α×r+(1-α)s

其中NF表示新算法，α表示權(quán)重。

(9)將重新排序后的Top-N好友推薦給目標(biāo)用戶。

4 實驗結(jié)果及分析

4.1 測試數(shù)據(jù)集

實驗采用的數(shù)據(jù)是從人人網(wǎng)收集的好友信息數(shù)據(jù)集。本次實驗共收集了將近5萬個用戶信息，為提高實驗算法的準(zhǔn)確性，此處過濾掉好友數(shù)量少于20的用戶，最終得到7 630個用戶，包含268 943個好友關(guān)系，每個用戶約有20～50個好友關(guān)系。本實驗采用交叉驗證[8]，將數(shù)據(jù)集80%的訓(xùn)練集和20%的測試集對不同的算法進(jìn)行分析。同時為驗證實驗的準(zhǔn)確性，實驗也將每一個用戶的好友隨機(jī)分為80%的使用集和20%的驗證集，并對實驗數(shù)據(jù)進(jìn)行多次運算取平均值。

驗證算法所用的硬件平臺為Intel?CoreTM2 Duo CPUE7400，主頻為2.8 GHz,2 GB內(nèi)存,320 GB硬盤。操作系統(tǒng)為Windows Professional sp3，所有算法用Visual C++語言實現(xiàn)。

4.2 評價標(biāo)準(zhǔn)

測試結(jié)果的評價指標(biāo)采用Top-N推薦中使用的準(zhǔn)確率(Precision)、召回率(Recall)和F度量(F-measure)。準(zhǔn)確率定義為：

其中，hit為命中的數(shù)量，Test為驗證集，N為向用戶推薦的好友數(shù)量。

將這兩個度量值融合成一個度量值，就是F度量(F-measure)：

此處首先根據(jù)實驗結(jié)果，取得個性化算法最優(yōu)推薦時的α值，并對個性化算法(NF)、社會過濾算法(SF)、基于內(nèi)容推薦算法(CB)3種算法進(jìn)行評價。在本實驗中，對推薦出的Top-N的個數(shù)N=2，4，6，8，10這5種情況分別進(jìn)行評價。

4.3 實驗結(jié)果

圖1顯示了個性化好友推薦算法在α取不同值時的F-measure值。結(jié)果顯示，當(dāng)α取0.4時F-measure值最大，此時個性化推薦算法(NF)最優(yōu)。

圖2顯示了3種不同推薦算法F-measure的比較結(jié)果。表1顯示了不同情況下，各算法詳細(xì)數(shù)據(jù)記錄，數(shù)據(jù)顯示當(dāng)推薦用戶不斷增加時，各個指數(shù)性能也隨之增加，在4～8個推薦用戶時達(dá)到最大。這說明一次給用戶推薦的好友數(shù)不宜太多，6個左右最佳，同時也顯示出本文的好友推薦算法比單一算法效率更高。

由實驗結(jié)果分析可知，本文提出的結(jié)合社會過濾算法和內(nèi)容推薦算法的個性化好友推薦算法，能夠有效地處理社交網(wǎng)絡(luò)中好友推薦時遇見的冷啟動、標(biāo)簽冗余等問題，同時推薦的準(zhǔn)確性也有了進(jìn)一步的提高。

表1 算法性能對比

在以后的研究中應(yīng)更加重視用戶在使用社交網(wǎng)絡(luò)中的動態(tài)信息，多考慮用戶的興趣變化，根據(jù)用戶的興趣變化實時地給用戶推薦好友。

[1]GOU L，YOU F，GUO J，et al.Sfviz：interest-based friends exploration and recommendation in social networks[C].In Proceedings of the 2011 Visual Information Communication-International Symposium，ACM，2011.

[2]SAVAGE S，BARANSKI M，CHAVEZ N E，et al.I’m feeling loco：a location based context aware recommendation system[C].In Advances in Location-Based Services：8th International Symposium on Location-Based Services，Vienna，2011.

[3]DIMICCO J，MILLEN D，GEYER W，et al.Motivations for social networking at work[C].ACM CSCW，2008.

[4]EHRLICH K，LIN C，MILLEN D，et al.Recommending topic for self-descriptions in online user profiles[C].ACM RecSys，2008.

[5]GROH G，EHMIG C.Recommendations in taste related domains：collaborative filtering vs.social filtering[C].Proc.ACM Group’07：127-136.

[6]LINDEN G，SMITH B，YORK J.Amazon.com recommendations：Item-to-Item collaborative filtering[J].IEEE Internet Computing，2003，7(1)：76-80.

[7]HALPIN H，ROBU V，SHEPHERD H.The complex dynamics of collaborative tagging[C].In Proc.of WWW’07：211-220.

[8]ALJANDAL W，BAHIRWANI V，CARAGEA D，et al.Ontology-aware classification and association rule mining for interest and link prediction in social networks[C].In SSS’09：AAAI Spring Symposia 2006 on Social Semantic Web，2009.