汪毓鐸，黃太波

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101 )

?

基于社交網(wǎng)絡(luò)和協(xié)同過(guò)濾的微博好友推薦算法

汪毓鐸，黃太波

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101 )

微博作為近年來(lái)用戶(hù)數(shù)量較多的社交應(yīng)用，其用戶(hù)的信息壓力也相對(duì)較大，推薦技術(shù)對(duì)于微博用戶(hù)的體驗(yàn)和推廣有很明顯的幫助.本文將針對(duì)微博平臺(tái)的好友推薦進(jìn)行研究，分別采用基于社交網(wǎng)絡(luò)分析和基于協(xié)同過(guò)濾技術(shù)的推薦算法.經(jīng)過(guò)兩種算法的實(shí)驗(yàn)對(duì)比得出結(jié)論：基于協(xié)同過(guò)濾的好友推薦算法具有較好的性能，在推薦好友數(shù)量較多的情況下依然具有較高的綜合評(píng)價(jià)指標(biāo)，提高了好友推薦的質(zhì)量.

推薦技術(shù)；微博；社交網(wǎng)絡(luò)；協(xié)同過(guò)濾

隨著微博用戶(hù)人數(shù)的增加，用戶(hù)發(fā)布的微博量更是不計(jì)其數(shù)，信息量的急劇增長(zhǎng)導(dǎo)致人們?cè)絹?lái)越難獲取到自己真正感興趣的內(nèi)容，這就是所謂的信息過(guò)載效應(yīng)[1].解決信息過(guò)載的手段主要有搜索技術(shù)和推薦技術(shù).相比搜索技術(shù)，推薦技術(shù)具有更好的過(guò)濾效果、靈活性及推廣能力，因此被廣泛應(yīng)用于各大電商門(mén)戶(hù)網(wǎng)站及手機(jī)APP，如國(guó)內(nèi)的淘寶網(wǎng)、京東網(wǎng)及國(guó)外的Amazon等.互聯(lián)網(wǎng)和移動(dòng)終端設(shè)備的飛速發(fā)展，導(dǎo)致用戶(hù)對(duì)于社交網(wǎng)絡(luò)服務(wù)的需求也呈現(xiàn)急劇增長(zhǎng)的趨勢(shì).網(wǎng)絡(luò)社交已經(jīng)成為人們?nèi)粘Ｉ钪械闹匾M成部分.在國(guó)外著名的社交網(wǎng)站主要有Facebook和Twitter等；在國(guó)內(nèi)著名的社交網(wǎng)站主要有新浪微博、騰訊微博和人人網(wǎng)等.目前新浪微博的用戶(hù)總數(shù)量和用戶(hù)活躍數(shù)量均為國(guó)內(nèi)同類(lèi)產(chǎn)品之最，本文選擇新浪微博作為好友推薦的研究平臺(tái).

在微博社交網(wǎng)絡(luò)中，用戶(hù)獲取自己感興趣的用戶(hù)主要有以下幾種方式：1)通過(guò)自己感興趣的微博內(nèi)容來(lái)關(guān)注發(fā)布此內(nèi)容的用戶(hù)，但在海量的信息中，通過(guò)這種方式來(lái)尋找自己感興趣的用戶(hù)并不容易；2)通過(guò)設(shè)置不同特征條件對(duì)所有微博用戶(hù)進(jìn)行檢索，這種方式往往會(huì)返回大量的結(jié)果，使用戶(hù)無(wú)法進(jìn)行甄別和選擇；3)由微博運(yùn)營(yíng)平臺(tái)推薦好友，目前主要的推薦方式為給目標(biāo)用戶(hù)推薦其好友最近關(guān)注的用戶(hù)，這種推薦方式相對(duì)比較簡(jiǎn)單和盲目，其效果并不理想.因此，如何從海量的微博用戶(hù)中，挖掘出目標(biāo)用戶(hù)感興趣的用戶(hù)，并精準(zhǔn)地推薦給目標(biāo)用戶(hù)，是微博推薦系統(tǒng)中的一個(gè)很有意義的研究?jī)?nèi)容.在微博推薦領(lǐng)域，已有許多人展開(kāi)研究并獲得一定成果.比如根據(jù)用戶(hù)關(guān)注的群體來(lái)推測(cè)用戶(hù)的偏好，或者根據(jù)用戶(hù)的評(píng)論和參與的話(huà)題來(lái)預(yù)測(cè)用戶(hù)的關(guān)注點(diǎn)，然后為其推薦可能感興趣的用戶(hù)及話(huà)題[2-3].

在具有社交功能的應(yīng)用場(chǎng)景里，用戶(hù)推薦是很重要的功能之一.目前微博用戶(hù)的推薦方法主要有以下幾種： 1)社交網(wǎng)絡(luò)推薦一般都是通過(guò)對(duì)用戶(hù)好友的關(guān)注關(guān)系網(wǎng)進(jìn)行分析并推薦，由于用戶(hù)與其好友的關(guān)系建立并不都是基于共同興趣，因此推薦準(zhǔn)確率較低；2)基于內(nèi)容的推薦不依賴(lài)于用戶(hù)的評(píng)分?jǐn)?shù)據(jù)，而是根據(jù)用戶(hù)的歷史行為來(lái)判斷是否對(duì)用戶(hù)進(jìn)行推薦，在動(dòng)態(tài)預(yù)測(cè)推薦方面具有優(yōu)勢(shì)；3)協(xié)同過(guò)濾推薦是推薦系統(tǒng)中最常用的方法，通過(guò)用戶(hù)之間的評(píng)分?jǐn)?shù)據(jù)來(lái)進(jìn)行相似度計(jì)算進(jìn)行推薦，具有良好的操作性及推薦效果，被廣泛應(yīng)用于各大網(wǎng)站;4)混合推薦將多種推薦算法應(yīng)用于推薦系統(tǒng)中，可以使不同推薦算法的優(yōu)點(diǎn)結(jié)合起來(lái)進(jìn)行推薦，具有良好的推薦效果.

協(xié)同過(guò)濾是利用與用戶(hù)興趣行為相似的最近的鄰居的偏好信息向當(dāng)前用戶(hù)產(chǎn)生推薦結(jié)果，以解決用戶(hù)所面臨的信息過(guò)載的問(wèn)題[4].協(xié)同過(guò)濾這一概念最先由Goldberg[5]等提出，并將其應(yīng)用于基于協(xié)同過(guò)濾的推薦系統(tǒng)Tapestry中，這是一個(gè)郵件處理系統(tǒng)，用來(lái)幫助用戶(hù)從每天接收的大量郵件中篩選和分類(lèi)郵件.在協(xié)同過(guò)濾推薦算法中，有很重要的一個(gè)步驟，就是根據(jù)目標(biāo)用戶(hù)對(duì)于目標(biāo)項(xiàng)目的評(píng)價(jià)行為找出與其興趣相似的用戶(hù).盡管根據(jù)用戶(hù)對(duì)項(xiàng)目的評(píng)價(jià)行為確實(shí)可以在一定程度上找出興趣相似的用戶(hù)，但這種做法卻忽略了用戶(hù)之間的社交關(guān)系[6].在社交網(wǎng)絡(luò)上往往越靠近的用戶(hù)越具有相同的興趣愛(ài)好[7]，所以將用戶(hù)之間的社交關(guān)系融入到協(xié)同過(guò)濾算法當(dāng)中來(lái)是非常有必要的，這就要利用到社交網(wǎng)絡(luò)分析的知識(shí).

社交網(wǎng)絡(luò)分析是數(shù)據(jù)挖掘的一個(gè)分支學(xué)科，它是一種鏈接分析技術(shù)，意在分析社交網(wǎng)絡(luò)中的結(jié)構(gòu)和行為[8].在社交網(wǎng)絡(luò)上，學(xué)者們已經(jīng)對(duì)利用社交關(guān)系進(jìn)行個(gè)性化推薦做出了各種嘗試.Spertus[9]等使用了不同的相似度計(jì)算策略在在線社區(qū)Orkut上進(jìn)行個(gè)性化推薦.Geyer[10]等在網(wǎng)絡(luò)社區(qū)上根據(jù)社交網(wǎng)絡(luò)信息實(shí)現(xiàn)的話(huà)題推薦被證實(shí)比基于內(nèi)容的推薦具有更好的效果.

綜上所述，社交網(wǎng)絡(luò)分析對(duì)于個(gè)性化好友推薦是一個(gè)非常重要的方法和影響因素.而協(xié)同過(guò)濾算法則是推薦系統(tǒng)中經(jīng)典且高效的推薦算法.本文作者將采用基于社交網(wǎng)絡(luò)分析和基于協(xié)同過(guò)濾兩種算法來(lái)對(duì)于微博平臺(tái)上的好友推薦進(jìn)行研究.

1 基于社交網(wǎng)絡(luò)分析的好友推薦算法

基于社交網(wǎng)絡(luò)分析的微博好友推薦算法.利用目標(biāo)用戶(hù)的關(guān)注關(guān)系數(shù)據(jù)，統(tǒng)計(jì)出每個(gè)用戶(hù)的關(guān)注用戶(hù)和粉絲用戶(hù)數(shù)據(jù)，計(jì)算用戶(hù)的相似群體，根據(jù)相似度排序向用戶(hù)做好友推薦.

1.1 算法步驟描述

算法的具體步驟描述如下：1)從數(shù)據(jù)集中提取出所有用戶(hù)關(guān)系的子數(shù)據(jù)集，并對(duì)子數(shù)據(jù)集進(jìn)行預(yù)處理；2)計(jì)算預(yù)處理后的子數(shù)據(jù)集中所有用戶(hù)間的相似性；3)對(duì)用戶(hù)相似群體進(jìn)行相似度排序，獲取目標(biāo)用戶(hù)的相似群體；4)取相似群體中相似度最高的前N個(gè)用戶(hù)的關(guān)注對(duì)象來(lái)對(duì)目標(biāo)用戶(hù)進(jìn)行推薦.

1.2 相似性度量

社交網(wǎng)絡(luò)中沒(méi)有評(píng)分?jǐn)?shù)據(jù)，但卻包含著非常豐富的用戶(hù)社交關(guān)系數(shù)據(jù).在微博的社交網(wǎng)絡(luò)中，用戶(hù)關(guān)注的好友并不是在現(xiàn)實(shí)生活中熟悉的朋友，很大程度上是因?yàn)閷?duì)其某些言論的認(rèn)同或者興趣才建立的社交關(guān)系.這種社交關(guān)系包括互相關(guān)注關(guān)系和單向關(guān)注關(guān)系.

常見(jiàn)的用戶(hù)相似性度量方法，如余弦相似度、Pearson相關(guān)系數(shù)及修正的余弦相似度等，對(duì)于用戶(hù)項(xiàng)目的評(píng)分向量比較依賴(lài).考慮到微博中并沒(méi)有用戶(hù)評(píng)分機(jī)制，故這里采用不同用戶(hù)節(jié)點(diǎn)的“出度”和“入度”來(lái)進(jìn)行相似度計(jì)算.這里的“出度”指的就是目標(biāo)用戶(hù)的關(guān)注用戶(hù)集合，“入度”指的是目標(biāo)用戶(hù)的粉絲用戶(hù)集合.

具體的相似性度量方法為：假設(shè)用戶(hù)u的出度為out(u)，入度為in(u)；用戶(hù)v的出度和入度分別為out(v)和in(v).則用戶(hù)u與用戶(hù)v的相似性sim(u, v)的計(jì)算有以下幾種方法.

1)in方法，計(jì)算公式為

(1)

2)out方法，計(jì)算公式為[11]

(2)

3)采用in方法和out方法，計(jì)算公式為

(3)

2 基于協(xié)同過(guò)濾的好友推薦算法

協(xié)同過(guò)濾推薦算法分為兩種，分別為基于內(nèi)存和基于模型.基于內(nèi)存的協(xié)同過(guò)濾算法也分為兩種，分別為基于用戶(hù)和基于項(xiàng)目[12].本文研究的是微博平臺(tái)的好友推薦，故采用基于用戶(hù)的協(xié)同過(guò)濾算法來(lái)對(duì)目標(biāo)用戶(hù)進(jìn)行好友推薦.

基于用戶(hù)的協(xié)同過(guò)濾算法的原理為，根據(jù)當(dāng)前用戶(hù)的鄰居用戶(hù)的偏好信息來(lái)對(duì)當(dāng)前用戶(hù)進(jìn)行推薦.所謂鄰居用戶(hù)，指的是對(duì)于某些項(xiàng)目的評(píng)分與目標(biāo)用戶(hù)比較接近的用戶(hù).基于用戶(hù)的協(xié)同過(guò)濾算法可分為：表示階段、計(jì)算鄰居用戶(hù)階段和推薦結(jié)果生成階段3個(gè)階段[13].

1)表示階段.C(n ,m)是一個(gè)n×m階矩陣.協(xié)同過(guò)濾推薦算法所要處理的數(shù)據(jù)形式就是與此類(lèi)似的用戶(hù)-項(xiàng)目評(píng)分矩陣[14]，用下式表示為

(4)

式中:n表示用戶(hù)數(shù);m表示項(xiàng)目數(shù);矩陣元素cij表示用戶(hù)i對(duì)項(xiàng)目j的評(píng)分;與喜歡程度成正比.評(píng)分可以采用不同的分制，如用1和0分別表示喜歡和不喜歡,或者用10分制來(lái)度量喜歡的程度.

利用協(xié)同過(guò)濾算法在進(jìn)行微博好友推薦時(shí)，表示階段的矩陣應(yīng)為用戶(hù)-用戶(hù)評(píng)分矩陣，矩陣的每個(gè)元素是由對(duì)應(yīng)用戶(hù)間的關(guān)注關(guān)系量化而來(lái)的評(píng)分?jǐn)?shù)據(jù)，比如，當(dāng)用戶(hù)i和用戶(hù)j的關(guān)系為相互關(guān)注時(shí)，對(duì)應(yīng)的矩陣元素cij為1，否則cij為0.

2)計(jì)算鄰居用戶(hù)階段.計(jì)算鄰居用戶(hù)階段是基于用戶(hù)的協(xié)同過(guò)濾算法中的關(guān)鍵階段.在此階段中，算法通過(guò)計(jì)算不同用戶(hù)關(guān)注關(guān)系的相似度來(lái)衡量不同用戶(hù)興趣的相似度.相似度的取值范圍為[-1,1]，其大小表示用戶(hù)的鄰近程度.因此相似度越接近1表示用戶(hù)興趣越相似，即為鄰居用戶(hù).

在表示階段，已經(jīng)將用戶(hù)的關(guān)注關(guān)系量化為評(píng)分形式的用戶(hù)-用戶(hù)評(píng)分矩陣.矩陣的每一個(gè)行向量表示對(duì)應(yīng)用戶(hù)對(duì)集合中所有用戶(hù)的評(píng)分.則用戶(hù)之間的相似度可以用余弦相似度進(jìn)行計(jì)算.設(shè)I為所有用戶(hù)的集合，向量u和v分別表示用戶(hù)u和v在I上的所有評(píng)分信息.于是，用戶(hù)u和v之間的余弦相似度表示為

(5)

式中，Rui和Rvi分別表示用戶(hù)u對(duì)項(xiàng)目i的評(píng)分和用戶(hù)v對(duì)項(xiàng)目i的評(píng)分.

3)推薦結(jié)果生成階段.在對(duì)用戶(hù)的相似度進(jìn)行排序后即可得到目標(biāo)用戶(hù)的鄰居用戶(hù)集合.不同于為相似用戶(hù)推薦項(xiàng)目，這里并不需要進(jìn)行目標(biāo)項(xiàng)目的評(píng)分計(jì)算.采用的推薦方式為給當(dāng)前用戶(hù)推薦與興趣最相似的N個(gè)鄰居用戶(hù)有互相關(guān)注關(guān)系的用戶(hù).

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)來(lái)自于數(shù)據(jù)堂，數(shù)據(jù)集為63 641個(gè)用戶(hù)的新浪微博數(shù)據(jù)集，包括微博信息、微博轉(zhuǎn)發(fā)關(guān)系、用戶(hù)信息和用戶(hù)好友關(guān)系等數(shù)據(jù).本文主要利用用戶(hù)的互相關(guān)注數(shù)據(jù)來(lái)對(duì)用戶(hù)進(jìn)行相似度計(jì)算和好友推薦，故實(shí)驗(yàn)采用的數(shù)據(jù)為用戶(hù)好友關(guān)系數(shù)據(jù).

3.2 數(shù)據(jù)預(yù)處理

原始數(shù)據(jù)為兩列用戶(hù)的uid數(shù)據(jù)(每一個(gè)用戶(hù)擁有一個(gè)唯一的身份識(shí)別碼)，表示第1列用戶(hù)關(guān)注第2列用戶(hù)，故需要對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理和過(guò)濾操作.

1)在基于社交網(wǎng)絡(luò)分析的推薦算法實(shí)驗(yàn)中，由于微博用戶(hù)存在好友數(shù)量異常的垃圾用戶(hù)及粉絲過(guò)多的認(rèn)證用戶(hù)，這些用戶(hù)對(duì)于實(shí)驗(yàn)對(duì)象的一般性有所影響，故在原有數(shù)據(jù)集中去除這部分用戶(hù).原始數(shù)據(jù)中用戶(hù)的關(guān)注關(guān)系數(shù)據(jù)共有1 391 718條，從這些關(guān)注關(guān)系數(shù)據(jù)統(tǒng)計(jì)得到有關(guān)注的用戶(hù)為61 972個(gè)，有粉絲用戶(hù)為24 890個(gè).為了提高實(shí)驗(yàn)的準(zhǔn)確性和用戶(hù)的普遍性，選取了關(guān)注人數(shù)大于20且小于500，粉絲人數(shù)大于20人且小于5 000的用戶(hù)作為研究目標(biāo)用戶(hù)，最終的目標(biāo)群體為3 104位用戶(hù).

2)在基于協(xié)同過(guò)濾的推薦算法實(shí)驗(yàn)中，為了提高實(shí)驗(yàn)的精度，從用戶(hù)數(shù)據(jù)集中選取了互相關(guān)注人數(shù)大于10的用戶(hù)，共有1 044位用戶(hù)作為最終的研究目標(biāo)，與這一群體有關(guān)注關(guān)系的用戶(hù)共有5 311位.由于微博平臺(tái)中并沒(méi)有用戶(hù)對(duì)于用戶(hù)的評(píng)分，所以本文將用戶(hù)之間的相互關(guān)注關(guān)系作為評(píng)分來(lái)構(gòu)建用戶(hù)-用戶(hù)評(píng)分矩陣.在本實(shí)驗(yàn)中，則是根據(jù)1 044位用戶(hù)和涉及到的5 311位用戶(hù)的互相關(guān)注關(guān)系來(lái)構(gòu)建一個(gè)1044×5311用戶(hù)-用戶(hù)評(píng)分矩陣.矩陣的某一行為對(duì)應(yīng)用戶(hù)對(duì)于集合中所有用戶(hù)的評(píng)分向量.

3.3 評(píng)價(jià)指標(biāo)

采用Top-N推薦中的準(zhǔn)確率(Precision)、召回率(Recall)和F度量(F-measure)作為衡量算法的評(píng)價(jià)指標(biāo)[15].通過(guò)基于社交網(wǎng)絡(luò)的好友推薦算法(in法和out法)和基于協(xié)同過(guò)濾的好友推薦算法進(jìn)行準(zhǔn)確率、召回率和F值的比較來(lái)對(duì)算法進(jìn)行評(píng)價(jià).

準(zhǔn)確率定義為

(6)

召回率定義為

(7)

式中：U表示所有用戶(hù)合集；R(u)表示推薦算法生成的推薦列表；T(u)表示用戶(hù)實(shí)際的好友列表.

將準(zhǔn)確率P和召回率R值融合成一個(gè)度量值，就是F度量.其定義為

(8)

式中，α為參數(shù)，當(dāng)α=1時(shí)，則認(rèn)為準(zhǔn)確率和召回率的權(quán)重是一樣的.常用的F度量為F2和F0.5.F2表明召回率具有更高的權(quán)重，F(xiàn)0.5則表明準(zhǔn)確率具有更高的權(quán)重.在微博好友推薦場(chǎng)景下，推薦的準(zhǔn)確率應(yīng)該比召回率更加重要，這時(shí)就應(yīng)該調(diào)整參數(shù)α的取值.本實(shí)驗(yàn)中取α=0.5.

3.4 結(jié)果分析

使用了兩種推薦算法分別在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并進(jìn)行實(shí)驗(yàn)結(jié)果的對(duì)比.第1種是基于社交網(wǎng)絡(luò)的好友推薦算法，其中采用了兩種不同的相似度計(jì)算方法(in方法和out方法)進(jìn)行比較，在實(shí)驗(yàn)中分別被簡(jiǎn)稱(chēng)為SN-in方法和SN-out方法.第2種是基于協(xié)同過(guò)濾的好友推薦算法(簡(jiǎn)稱(chēng)CF方法).

1)給出了基于社交網(wǎng)絡(luò)的推薦算法的SN-in方法和SN-out方法的準(zhǔn)確率與召回率對(duì)比如圖1所示.

圖1中從準(zhǔn)確率對(duì)比可以看出：1)SN-in方法的準(zhǔn)確率和召回率均相對(duì)高于SN-out方法.2)隨著推薦人數(shù)的增加，準(zhǔn)確率逐漸下降，相反召回率則逐漸上升，且兩個(gè)指標(biāo)最終都趨于平穩(wěn).由此說(shuō)明，準(zhǔn)確率和召回率是一對(duì)相互制約的評(píng)價(jià)指標(biāo)，而且推薦人數(shù)增加到一定數(shù)量時(shí)，準(zhǔn)確率和召回率都不再變化，算法同時(shí)也達(dá)到極限.

2)給出了SN-in方法和SN-out方法的F值對(duì)比如圖2所示.

從圖2中可以看出，隨著推薦人數(shù)的增加，F(xiàn)值達(dá)到峰值后略微下降，最終趨于平穩(wěn).SN-in方法在平均推薦人數(shù)為50人時(shí)，F(xiàn)值達(dá)到峰值0.193 8.SN-out方法在平均推薦人數(shù)為60人時(shí)，F(xiàn)值達(dá)到峰值0.152 9.這里可以看到，SN-in方法的F值始終高于SN-out方法，所以根據(jù)微博用戶(hù)的粉絲群體相似度計(jì)算來(lái)進(jìn)行推薦的效果要好于根據(jù)用戶(hù)的關(guān)注群體進(jìn)行推薦.

3)給出了基于協(xié)同過(guò)濾的好友推薦算法(CF方法)的準(zhǔn)確率、召回率及F0.5度量與推薦鄰居數(shù)的對(duì)應(yīng)關(guān)系,如圖3所示.通過(guò)對(duì)數(shù)據(jù)集的計(jì)算，在不同鄰居數(shù)的情況下，1 044位用戶(hù)分別可以得到長(zhǎng)度不同的用戶(hù)推薦列表.為了便于進(jìn)行不同算法的推薦性能對(duì)比，實(shí)驗(yàn)中使鄰居數(shù)不變，將所有用戶(hù)的推薦人數(shù)相加后做平均計(jì)算即可得到鄰居數(shù)與實(shí)際推薦人數(shù)的對(duì)應(yīng)數(shù)據(jù).如表1所示.

表1 推薦鄰居數(shù)-平均推薦人數(shù)對(duì)應(yīng)表Tab.1 Corresponding data between recommendation and actual average recommendation number

結(jié)合表1和圖3可以看出，CF方法在推薦人數(shù)較多的情況下，F(xiàn)值依然沒(méi)有趨于恒定.

由于SN-in方法和SN-out方法推薦好友的方式是根據(jù)用戶(hù)與其關(guān)注或粉絲群體中個(gè)體的相似度進(jìn)行計(jì)算和排序，然后選擇最相似的前K個(gè)用戶(hù)進(jìn)行推薦，而CF方法則是直接計(jì)算某用戶(hù)與鄰居用戶(hù)之間的相似度并排序，然后將與鄰居用戶(hù)互相關(guān)注的用戶(hù)推薦給該用戶(hù)，具體推薦人數(shù)的多少與推薦鄰居數(shù)的多少并不成正比例關(guān)系.

4)在對(duì)比這3種方法時(shí)，根據(jù)CF方法不同鄰居數(shù)對(duì)應(yīng)的推薦人數(shù)取出了前兩種方法在同樣推薦人數(shù)下的F值數(shù)據(jù)來(lái)進(jìn)行對(duì)比.給出了SN-in、SN-out和CF方法在推薦人數(shù)統(tǒng)一的情況下的F值對(duì)比如圖4所示.

結(jié)合表1和圖4可以看出，在推薦人數(shù)比較多的情況下，SN-in和SN-out方法的F值均不再變化，算法在曲線趨于恒定的臨界點(diǎn)上達(dá)到推薦人數(shù)的極限.CF方法在同樣的情況下，依然具有變化的F值，不僅沒(méi)有達(dá)到算法的極限而且CF方法的F值在臨界點(diǎn)之前都高于SN-in和SN-out方法.

由此可以看出，CF方法的性能要優(yōu)于其他兩種算法，而且在推薦人數(shù)較多的情況下，CF方法將擁有比其他兩種方法更加優(yōu)秀的推薦質(zhì)量.

4 結(jié)語(yǔ)

1)對(duì)于基于用戶(hù)的協(xié)同過(guò)濾算法進(jìn)行適用于好友推薦的改進(jìn)，把傳統(tǒng)方法中的用戶(hù)-項(xiàng)目(user-item)評(píng)分矩陣轉(zhuǎn)換為用戶(hù)-用戶(hù)(user-user)關(guān)系描述矩陣，使得用戶(hù)之間的關(guān)注關(guān)系量化為矩陣中的對(duì)應(yīng)元素，用戶(hù)相似度的計(jì)算量化為矩陣行向量的余弦相似度計(jì)算.從大量的用戶(hù)關(guān)系數(shù)據(jù)中進(jìn)行挖掘和計(jì)算來(lái)獲取推薦結(jié)果，推薦結(jié)果全面且不失個(gè)性化.

2)在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)和對(duì)比可以看到基于協(xié)同過(guò)濾的好友推薦算法(CF算法)具有較好的性能.由圖4可以看出，在推薦好友數(shù)量為75時(shí)，SN-in、SN-out和CF方法的F度量值分別為0.190 6、0.152 7和0.238 9，此時(shí)SN-in和SN-out方法的推薦效果都已達(dá)到最佳，但是F度量值均小于CF方法.實(shí)驗(yàn)結(jié)果說(shuō)明，在推薦人數(shù)較少時(shí)，CF方法具有更好的性能.同樣由圖4可以看到，在推薦好友數(shù)量較多的情況下，CF方法依然具有較高的綜合評(píng)價(jià)指標(biāo)，比傳統(tǒng)的基于社交網(wǎng)絡(luò)的好友推薦算法有著更好的推薦效果，在一定程度上提高了好友推薦的質(zhì)量.在研究過(guò)程中遇到數(shù)據(jù)集不夠完美，算法實(shí)驗(yàn)難以進(jìn)行統(tǒng)一度量對(duì)比等問(wèn)題.但在信息急劇膨脹的時(shí)代，本文的研究具有一定的積極意義.

[1] BAWDEN D, HOLTHAM C, COURTNEY N. Perspectives on information overload[C]. Aslib Proceedings, 2013, 51(8): 249-255.

[2] 王晟, 王子琪, 張銘. 個(gè)性化微博推薦算法[J]. 計(jì)算機(jī)科學(xué)與探索, 2012, 6(10): 895-902. WANG Sheng, WANG Ziqi, ZHANG Ming. Personalized recommendation algorithm on microblogs[J].Journal of Frontiers of Computer Science and Technology, 2012, 6(10): 895-902.(in Chinese)

[3] 鄭志嫻. 微博個(gè)性化內(nèi)容推薦算法研究[J]. 電腦開(kāi)發(fā)與應(yīng)用, 2012, 25(12): 23-25. ZHENG Zhixian.A personalized recommendation algorithm on microblogs[J].Computer Development & Applications, 2012, 25(12): 23-25.(in Chinese)

[4] 楊博, 趙鵬飛. 推薦算法綜述[J]. 山西大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011, 34(3): 337-350. YANG Bo, ZHAO Pengfei. Review of recommendation algorithms[J]. Journal of Shanxi University: Nat Sci Ed, 2011, 34(3): 337-350.(in Chinese)

[5] GOLDBERG D, NICHOLS D, OKI B M, et al. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM, 1992, 35(12): 61-70.

[6] KAUTZ H, SELMAN B, SHAH M. Referral Web: combining social networks and collaborative filtering[J]. Communications of the ACM, 1997, 40(3): 63-65.

[7] 秦繼偉, 鄭慶華, 鄭立德，等.結(jié)合評(píng)分和信任的協(xié)同推薦算法[J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(4): 100-104. QIN Jiwei, ZHENG Qinghua, ZHENG Lide, et al. Collaborative recommendation algorithm based on rating and trust[J].Journal of Xi'an Jiaotong University, 2013, 47(4): 100-104.(in Chinese)

[8] 韓慧, 王建新, 孫俏，等. 數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M]. 北京: 清華大學(xué)出版社, 2009. HAN Hui, WANG Jianxin, SUN Qiao, et al. Data warehouse and data mining[M]. Beijing: Tsinghua University Press, 2009.(in Chinese)

[9] SPERTUS E, SAHAMI M, BUYUKKOKTEN O. Evaluating similarity measures: a large-scale study in the Orkut social network[C]. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 2005: 678-684.

[10] GEYER W, DUGAN C, MILLEN D R, et al. Recommending topics for self-descriptions in online user profiles[C]. Proceedings of the 2008 ACM Conference on Recommender Systems, 2008: 59-66.

[11] 賀銀慧, 陳端兵, 陳勇,等. 一種結(jié)合共同鄰居和用戶(hù)評(píng)分信息相似度算法[J]. 計(jì)算機(jī)科學(xué), 2010, 37(9): 184-204. HE Yinhui, CHEN Duanbing, CHEN Yong, et al. Similarity algorithm based on user's common neighbors and grade information[J]. Computer Science, 2010, 37(9): 184-204.(in Chinese)

[12] 鄧愛(ài)林, 朱揚(yáng)勇, 施伯樂(lè). 基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法[J]. 軟件學(xué)報(bào), 2003, 14(9): 1621-1628. DENG Ailin, ZHU Yangyong, SHI Bole.A collaborative filtering recommendation algorithm based on item ratingprediction[J]. Journal of Software, 2003, 14(9): 1621-1628.(in Chinese)

[13] 吳振慧. 推薦技術(shù)的比較研究[J]. 計(jì)算機(jī)光盤(pán)軟件與應(yīng)用, 2011(19): 44-45. WU Zhenhui. Comparative study of the recommendedtechniques[J]. Computer CD Software and Applications, 2011(19): 44-45.(in Chinese)

[14] 張超. 結(jié)合社交網(wǎng)絡(luò)分析和協(xié)同過(guò)濾技術(shù)的推薦算法研究[D]. 吉林: 吉林大學(xué), 2013. ZHANG Chao.Research on recommendation algorithm based on social network analysis and collaborative filtering[D]. Jilin: Jilin University,2013.(in Chinese)

[15] 石麗麗. 面向微博用戶(hù)的內(nèi)容與好友推薦算法研究與實(shí)現(xiàn)[D]. 北京: 北京郵電大學(xué), 2014. SHI Lili.Research and implementation of content and friend recommendation algorithm for microbloggingusers[D]. Beijing: Beijing University of Posts and Telecommunications,2014.(in Chinese)

Recommendation algorithm of microblogging friends based on social networking and collaborative filtering

WANGYuduo,HUANGTaibo

(School of Information and Communication Engineering, Beijing Information Science and Technology University, Beijing 100101, China)

As a social application that has a large number of users in recently years, the information pressure of microblogging users is relatively powerful. Recommendation technology is helpful to user experience and promotion of microblogging. The paper studies on the friend recommendation on the microblogging platform, and the recommendation algorithms based on social network analysis and collaborative filtering are respectively introduced. After experimental comparison of the two algorithms, it comes to conclusion that friend recommendation algorithm based on collaborative filtering has better performance and has good evaluation index under the large number of friend recommendation. It also can improve the quality of friend recommendation.

recommendation technology; microblogging;social network; collaborative filtering

2016-06-02

汪毓鐸(1960—)，男，遼寧北鎮(zhèn)人，教授.研究方向?yàn)閿?shù)據(jù)采集與信號(hào)處理. email: wangyuduo@bistu.edu.cn.

TP391

A

1673-0291(2016)05-0070-06

10.11860/j.issn.1673-0291.2016.05.012