胡文江，胡大偉，高永兵，郝 斌

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

1 引言

在當前的網(wǎng)絡(luò)社會，大多數(shù)用戶的朋友來自那些在現(xiàn)實生活中的社會關(guān)系，如學校、隊友、同事等[1]。但事實上，用戶往往想通過社交網(wǎng)絡(luò)認識一些新朋友。對于一個用戶，特別是新加入的用戶，添加哪些用戶為自己的好友成了一個困難的問題。社交網(wǎng)站中好友推薦算法就是針對這一難題而提出的。

目前，針對社會網(wǎng)絡(luò)的好友推薦算法，研究人員已經(jīng)提出一些解決方案。Spertuse等[2]根據(jù)現(xiàn)在社區(qū)的用戶來推薦在線社區(qū)給用戶，并在一個社交網(wǎng)絡(luò)Orkut的大型研究中比較了幾種不同的相似性度量。Geye[3]利用社交網(wǎng)站的信息建立了一個系統(tǒng)來推薦自我描述的主題，指出基于社交網(wǎng)絡(luò)的推薦優(yōu)于簡單的內(nèi)容匹配推薦。

實驗結(jié)果通過與三種常用的好友推薦算法對比得出。第一種是簡單的頻率算法，它將好友最多的用戶推薦出來；第二種是關(guān)聯(lián)規(guī)則算法，通過關(guān)聯(lián)用戶間的好友關(guān)系推薦與目標用戶共同好友最多的用戶；第三種是協(xié)同過濾算法，通過計算用戶間的相似性進行推薦。第一種算法簡單、高效，但是忽略了社交網(wǎng)絡(luò)中需要推薦興趣愛好最相近的好友；第二種算法僅僅采取共同好友個數(shù)來推薦，不能利用社交網(wǎng)絡(luò)中更多的用戶信息去推薦；第三種算法雖然能計算出最相近的好友，但是效率值比較低。本文在已有研究工作的基礎(chǔ)上，綜合考慮以上算法的優(yōu)缺點，提出了改進的推薦算法。首先介紹關(guān)聯(lián)規(guī)則和協(xié)同過濾算法，以及它們的優(yōu)缺點，然后介紹改進的推薦算法，最后通過實驗對該方法進行評價。

2 相關(guān)算法分析

2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則挖掘[4]是搜索尋找項目與項目之間的關(guān)系，在數(shù)據(jù)庫中出現(xiàn)的頻率比較高。例如，如果項目B 在項目A 中出現(xiàn)，那么關(guān)聯(lián)規(guī)則表示為A＝＞B（如果A，那么B）。支持度和置信度是關(guān)聯(lián)規(guī)則的兩個評價措施，反映了關(guān)聯(lián)規(guī)則的實用性和確定性。支持度是指規(guī)則中所出現(xiàn)模式的頻率，如果事務(wù)數(shù)據(jù)庫D 有s%的事務(wù)包含AB，則稱關(guān)聯(lián)規(guī)則AB 在D 中的支持度為s%，實際上，可以表示為概率P（AB），即support（AB）＝P（AB）。信任度是指蘊含的強度，即事務(wù)D 中c%的包含A的交易同時包含AB。若X 的支持度是support（A），規(guī)則的信任度即為：support（AB）／support（A），這是一個條件概率P（B｜A），即confidence（AB）＝P（B｜A）。關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。

在好友推薦的應用中，關(guān)聯(lián)規(guī)則推薦技術(shù)存在著自身的問題。（1）數(shù)據(jù)稀疏，如果數(shù)據(jù)量很大，則較難發(fā)現(xiàn)強關(guān)聯(lián)規(guī)則。社交網(wǎng)絡(luò)中的用戶數(shù)據(jù)是龐大的，如果用戶的好友數(shù)量比較小，算法要找到用戶間的好友關(guān)系是困難的，從而影響了推薦系統(tǒng)的推薦效果。（2）靜態(tài)的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則算法一般都認為所發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫中是永恒有效的，沒有考慮到關(guān)聯(lián)規(guī)則的變化，它得到的是一種靜態(tài)的關(guān)聯(lián)規(guī)則。但是，在好友推薦中，用戶可以隨時添加好友或者解除好友關(guān)系，關(guān)聯(lián)規(guī)則是隨時間變化而變化的。靜態(tài)的關(guān)聯(lián)規(guī)則在某種程度上不能反映用戶好友關(guān)系發(fā)生變化或更新，從而導致推薦系統(tǒng)可能會向用戶推薦沒有好友關(guān)系的用戶。

2.2 協(xié)同過濾算法

協(xié)同過濾算法是基于這樣一個假設(shè)：如果用戶對一些項目的評分比較相似，則他們對其它項目的評分也比較相似；如果大部分用戶對一些項的評分比較相似，則當前用戶對這些項的評分也比較相似。協(xié)同過濾算法主要分為兩種：基于項目的算法和基于用戶的算法。

（1）基于項目的方法[5]：此算法建立在項目具有一些確定的特點，而這些特點可以用標簽具體地表現(xiàn)出來，通過用戶對標簽的喜歡程度，反映用戶對項目的喜好程度。例如，用戶的所有標簽可以模擬在TF-IDF模型[6]中，它能夠告訴這個用戶不同詞語的重要性。具體來說，設(shè)置所有標簽B，W 是所有獨特的字出現(xiàn)在B 中，BJ∈B 是用戶uj感興趣的標簽，而用戶Ok，J感興趣的字Wk恰好出現(xiàn)在BJ中。參考TF-IDFk，j模型，計算公式如公式（1）：

取得感興趣的標簽后，就可以知道一個用戶可能是對“足球”、“世界杯”有興趣，而另一個用戶可能對“電影”、“奧斯卡”更感興趣。

（2）基于用戶的算法：依靠計算用戶之間的相似度，找到與目標用戶具有相似興趣度的用戶，并稱這些用戶為目標用戶的鄰居；然后認定鄰居感興趣的項目，則目標用戶對這些項目也是感興趣的。而計算用戶之間的相似度是一個研究重點。例如，Halpin[7]通常用來計算“標簽相似性”：

其中，Iu（Iv）是用戶u（v）最喜愛的項目集。通過余弦相似性來度量兩個向量之間的相似程度：

其中，u、v是u、v的矢量，Iu，j表示用戶u 對 第j 個項目感興趣。最大相似性Similarity（u，v）表示用戶u和用戶v 也有類似的興趣。

隨著社交網(wǎng)絡(luò)規(guī)模的擴大，用戶數(shù)目和標簽的信息數(shù)據(jù)急劇增加，使得用戶-標簽的矩陣數(shù)據(jù)稀缺，導致用戶相似性和標簽相似性準確率下降，使推薦質(zhì)量急劇下降。

綜合以上兩種算法的問題，本文提出的改進推薦算法包含三個關(guān)鍵的創(chuàng)新：（1）用戶間的好友關(guān)系。每位用戶都有好友，社交網(wǎng)絡(luò)中共同好友的個數(shù)越多，說明他們相似性越強，這使得好友推薦更實用、更準確。（2）標簽的相似性。每位用戶都有自己的標簽來顯示用戶的喜好、特點，比較兩位用戶的標簽相似性，提高推薦效率，增加推薦的權(quán)重。（3）結(jié)合上述兩種算法，得出改進算法的公式。

3 改進的好友推薦算法

本文提出的改進推薦算法描述如下。首先利用關(guān)聯(lián)規(guī)則的算法，即通過用戶之間的好友用戶之間共同好友的個數(shù)，建立矩陣，計算并輸出排序結(jié)果。設(shè)P 是n 個用戶之間的偏好矩陣。在這個矩陣里，如果用戶i和用戶j 是好友關(guān)系，則Pi，j是1，否則為0。圖1表示的是P 矩陣圖。

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

Figure 1 P matrix圖1 P 矩陣圖

Figure 2 A matrix圖2 A 矩陣圖

目標用戶K 的偏好向量u 是一個1×n 的矩陣，uk，j表示目標用戶k 和用戶j 的共同好友關(guān)系，它是矩陣P 的行向量。為目標用戶推薦的矢量r，可以通過關(guān)聯(lián)矩陣A 和目標用戶的偏好向量u 的乘積得出：

然后，計算目標用戶標簽和推薦出的top-N用戶的標簽的相似度。算法的核心是計算出和目標用戶標簽最相近的用戶集，即用戶u要產(chǎn)生一個根據(jù)其標簽的相似度大小排列的“鄰居”集Nu＝｛N1，N2，…，Nk｝，sim（u，N1）＞sim（u，N2）＞…＞sim（u，Nk），sim（i，j）表示兩個用戶之間的相似性。在社會網(wǎng)絡(luò)中標簽不是特定的詞語，用戶可以根據(jù)自己的愛好來設(shè)定喜好標簽。因此，本文采用語義標簽相似度算法計算標簽與標簽之間的相似性，進而通過得分的高低來評價相似度的高低。單個詞的相似度得分計算公式為：

其中，n 為tagRefVector 中的參照標簽個數(shù)，key為單個標簽詞，tagRefi為第i個參照標簽。

組合詞的相似度得分計算公式為：

最后，對得出的r 和得到的相似度V 進行權(quán)重的賦值：

其中，α 是改進的好友推薦算法的參數(shù)，本文實驗中假定在社會網(wǎng)絡(luò)的好友關(guān)系中，共同好友的權(quán)重要強于標簽相似度的權(quán)重，實驗中采取經(jīng)驗估值，設(shè)α＝0.6。

算法 改進的好友推薦算法

輸入 用戶-用戶ID 表，用戶-用戶好友關(guān)系表，標簽-標簽ID 表，用戶-標簽表。

輸出 好友列表。

步驟1 設(shè)矩陣P，如果用戶i和用戶j 是好友關(guān)系，則Pi，j是1，否則為0。

步驟2 偏好向量u 是1×n 的矩陣，是P 向量的行向量。

步驟3 矩陣A 是n×n 矩陣，n 為用戶的數(shù)量，ai，j表示既是用戶i 的好友、又是用戶j的好友在所有用戶N 中的比例。

步驟4 利用公式（4）計算r的值。

步驟5 根據(jù)r值輸出好友列表Top-N。

步驟6 計算Top-N 好友和目標好友標簽相似度。

步驟7 利用公式（5）和公式（6）計算V 的值。

步驟8 輸入r值、α值和V 值。

步驟9 利用公式（7）得到最終W 值。

步驟10 輸出推薦的好友列表。

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

4.1 實驗數(shù)據(jù)集與環(huán)境

實驗數(shù)據(jù)是從一個音樂社交網(wǎng)站last.fm[8]、通過網(wǎng)站提供的開放API抓取下來的。為了提高實驗的準確性，選取1 111個用戶，包含3 114個好友關(guān)系。數(shù)據(jù)集存儲在mySQL 數(shù)據(jù)庫中，建立四個數(shù)據(jù)庫表，分別是用戶-用戶ID 表、用戶-用戶好友關(guān)系表、標簽-標簽ID 表和用戶-標簽表。圖3顯示的是數(shù)據(jù)庫中各個數(shù)據(jù)庫表，分別只截取了前10個數(shù)據(jù)。

Figure 3 實驗數(shù)據(jù)庫表圖3 Experimental database tables

實驗硬件平臺為Intel（R）Core（TM）2Duo CPUE 7400，主頻為2.8GHz，2GB內(nèi)存，160GB硬盤。操作系統(tǒng)為Windows professional SP3，所有算法用Java語言實現(xiàn)。

4.2 實驗方法和度量

數(shù)據(jù)集分為80%的訓練集和20%的測試集，平均分為5種不同的測試集（5倍交叉驗證）用來測試[9]。為了確保推薦的準確性，在測試中隱藏每個用戶的一個好友數(shù)據(jù)，并推薦預測偏好最高的N 項偏好信息，計算預測的精度比例。如果隱藏的好友實際上包含在Top-N 推薦名單中，就是所謂的命中。采用準確率（Precision）和召回率（Recall）兩個指標對簡單的頻率方法（SF）、單層次關(guān)聯(lián)規(guī)則方法（AR＋）、協(xié)同過濾方法（CF）和改進的推薦方法（GR）四種算法進行評價，定義如下：

準確率（Precision）＝推薦出的已經(jīng)成為好友的用戶／推薦出的好友用戶

查全率（Recall）＝推薦出的已經(jīng)成為好友的用戶／好友總個數(shù)

在本實驗中，使用推薦好友個數(shù)N＝10，2.，30，40，50五種情況分別對每個N 測量的準確率和召回率進行計算。

4.3 實驗結(jié)果

圖4顯示了四個不同的推薦算法準確率（Precision）的比較結(jié)果。圖4結(jié)果顯示，與AR＋相比GR 算法對Top-N 的每個值都優(yōu)化，達到2.5%、1.2%、1.3%、1.8%和2.0%，準確率（Precision）得以提高。這一結(jié)果表明，改進的算法是有效的。GR 算法在N＜20的時候，推薦的準確率要比CF的差，但是當N≥30時，GR 算法的推薦率要明顯強于CF。

Figure 4 Precision圖4 準確率

圖5顯示了四個不同的推薦算法召回率（Recall）的比較結(jié)果。當N＜20 時，與CF 相比，GR性能稍差，但當N＞30 時，表現(xiàn)出較高的召回率（5.4%、1.5%和8.6%）。隨著N 的增加，CF的性能變得相對低下，由于數(shù)據(jù)稀疏，CF方法不能預測許多項目的偏好。

Figure 5 Recall圖5 召回率

5 結(jié)束語

本文提出一種基于好友之間的關(guān)系推薦和喜好標簽的相似度推薦相結(jié)合的推薦方法。通過Last.fm 數(shù)據(jù)集的實驗表明，改進的推薦算法能夠提高推薦的準確性。和簡單的頻率方法（SF）、單層次關(guān)聯(lián)規(guī)則的方法（AR＋）、協(xié)同過濾方法（CF）相比，改進的算法顯示了更好的性能。

[1]Gou Liang，You Fang，Guo Jun，et al.SFViz：Interest-based friends exploration and recommendation in social networks[C]∥Proc of 2011Visual Information Communication-International Symposium，2011：15-24.

[2]Spertus E，Sahami M，Buyukkokten.Evaluating similarity measures：Large seale study in the Orkut social network[C]∥Proc of SIGKDD'05，2.05：678-684.

[3]Geyer W，Dugan C，Millen D，et al.Recommending topic for self-descriptions in online user profiles[C]∥Proc of 2008 ACM Conference on Recommender Systems，2008：1.

[4]Aljandal W，Bahirwani V，Caragea D，et al.Ontology-aware classification and association rule mining for interest and link prediction in social networks[C]∥Proc of AAAI Spring Symposia 2006on Social Semantic Web，2009：1.

[5]Linden G，Smith B，York J，et al.Recommendations：Itemto-item collaborative filtering[J].IEEE Transactions on Internet Computing，2003，7（1）：76-80.

[6]Caragea D，Bahirwani V，Alj W，et al.Ontology-based link prediction in the livejournal social network[C]∥Proc of 2009 Association for the Advancement of Artificial Intelligence，2009：1.

[7]Halpin H，Robu V，Shepherd H.The complex dynamics of collaborative tagging[C]∥Proc of WWW'07，2.07：211-220.

[8]Last.fm[EB／OL].[2009-08-01].http：／／www.lastfm.com.

[9]Hsu W H，King A L，Paradesi M S R，et al.Collaborative and structural recommendation of friends using weblog-based social network analysis[C]∥Proc of AAAI Spring Symposia 2006on Computational Approaches to Analysing Weblogs，2006：1-16.