基于關(guān)聯(lián)規(guī)則與標(biāo)簽的好友推薦算法＊

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

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

1 引言

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

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

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

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

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

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

在好友推薦的應(yīng)用中，關(guān)聯(lián)規(guī)則推薦技術(shù)存在著自身的問題。（1）數(shù)據(jù)稀疏，如果數(shù)據(jù)量很大，則較難發(fā)現(xiàn)強(qiáng)關(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ī)則算法一般都認(rèn)為所發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫(kù)中是永恒有效的，沒有考慮到關(guān)聯(lián)規(guī)則的變化，它得到的是一種靜態(tài)的關(guān)聯(lián)規(guī)則。但是，在好友推薦中，用戶可以隨時(shí)添加好友或者解除好友關(guān)系，關(guān)聯(lián)規(guī)則是隨時(shí)間變化而變化的。靜態(tài)的關(guān)聯(lián)規(guī)則在某種程度上不能反映用戶好友關(guān)系發(fā)生變化或更新，從而導(dǎo)致推薦系統(tǒng)可能會(huì)向用戶推薦沒有好友關(guān)系的用戶。

2.2 協(xié)同過濾算法

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

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

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

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

其中，Iu（Iv）是用戶u（v）最喜愛的項(xiàng)目集。通過余弦相似性來度量?jī)蓚€(gè)向量之間的相似程度：

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

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

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

3 改進(jìn)的好友推薦算法

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

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

Figure 1 P matrix圖1 P 矩陣圖

Figure 2 A matrix圖2 A 矩陣圖

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

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

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

組合詞的相似度得分計(jì)算公式為：

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

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

算法 改進(jìn)的好友推薦算法

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

輸出 好友列表。

步驟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）計(jì)算r的值。

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

步驟6 計(jì)算Top-N 好友和目標(biāo)好友標(biāo)簽相似度。

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

Figure 3 實(shí)驗(yàn)數(shù)據(jù)庫(kù)表圖3 Experimental database tables

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

4.2 實(shí)驗(yàn)方法和度量

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

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

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

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

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

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

Figure 4 Precision圖4 準(zhǔn)確率

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

Figure 5 Recall圖5 召回率

5 結(jié)束語(yǔ)

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

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