基于內容與社會過濾的好友推薦算法研究

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

（內蒙古科技大學 信息工程學院，內蒙古 包頭014010）

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

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

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

1 社會過濾算法

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

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

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

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

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

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

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

該算法較為適合與現實社會有較大聯系的社交網站，其較大的不足之處為目標用戶必須有一定的好友數量的積累。對于一個新注冊或者好友數量較少的用戶來說，不能夠使用該算法來給用戶推薦好友。

2 基于內容推薦算法

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

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

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

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

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

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

基于內容和鏈接的算法主要是通過使用社交網絡中的社交鏈接信息加強基于內容匹配算法的準確度[7]。算法通過將那些社交網絡中的弱約束和隱式用戶顯示出來，目標用戶更樂意于接受這種算法。此算法與基于內容的算法中計算相似度的方法有很大的相似之處。然而，與向用戶推薦前幾位相似度最高的用戶方法不同的是，如果用戶u和用戶c之間存在有效的鏈接，給用戶u和用戶c之間的相似度加50%的權重，即如果用戶u和用戶c之間存在聯系，那么在推薦時它的推薦順序將會排在基于內容相似度之前。

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

(1)a主動聯系過b；

(2)a對b有過評論；

(3)b主動聯系過a。

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

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

3 個性化好友推薦算法

為了解決社會過濾算法遇到的冷啟動問題以及基于內容相似性算法的準確率較低問題，根據對現有算法的總結，本文提出了改進的個性化好友推薦算法。經過實驗驗證，本算法能夠有效地解決這些問題。

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

(1)收集用戶信息

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

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

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

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

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

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

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

(5)檢測目標用戶好友數

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

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

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

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

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

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

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

設P是n個用戶之間的好友關系矩陣。在這個矩陣里，如果用戶i和用戶j是好友關系，則Pij為1，否則為0。

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

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

s=u×A

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

根據目標用戶與推薦集中用戶的共同好友個數，產生一個與目標用戶的共同好友數從多到少的好友推薦候選集s。

(8)選定合適的權重

選定權重的值，新算法的計算公式如下：

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

其中NF表示新算法，α表示權重。

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

4 實驗結果及分析

4.1 測試數據集

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

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

4.2 評價標準

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

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

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

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

4.3 實驗結果

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

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

由實驗結果分析可知，本文提出的結合社會過濾算法和內容推薦算法的個性化好友推薦算法，能夠有效地處理社交網絡中好友推薦時遇見的冷啟動、標簽冗余等問題，同時推薦的準確性也有了進一步的提高。

表1 算法性能對比

在以后的研究中應更加重視用戶在使用社交網絡中的動態信息，多考慮用戶的興趣變化，根據用戶的興趣變化實時地給用戶推薦好友。

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