姚彬修，倪建成，于蘋蘋，李淋淋，曹 博

(1.曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826； 2.曲阜師范大學(xué) 軟件學(xué)院，山東 曲阜 273100)

基于多源信息相似度的微博用戶推薦算法

姚彬修1，倪建成2*，于蘋蘋1，李淋淋1，曹 博1

(1.曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826； 2.曲阜師范大學(xué) 軟件學(xué)院，山東 曲阜 273100)

(*通信作者電子郵箱yaobinxiu02@163.com)

針對(duì)傳統(tǒng)的協(xié)同過濾(CF)推薦算法中存在的數(shù)據(jù)稀疏性和推薦準(zhǔn)確率不高的問題，提出了基于多源信息相似度的微博用戶推薦算法(MISUR)。首先，根據(jù)微博用戶的標(biāo)簽信息運(yùn)用K最近鄰(KNN)算法對(duì)用戶進(jìn)行分類；然后，對(duì)得到的每個(gè)類中的用戶分別計(jì)算其多源信息(微博內(nèi)容、交互關(guān)系和社交信息)的相似度；其次，引入時(shí)間權(quán)重和豐富度權(quán)重計(jì)算多源信息的總相似度，并根據(jù)其大小進(jìn)行TOP-N用戶推薦；最后，在并行計(jì)算框架Spark上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，MISUR算法與CF算法和基于多社交行為的微博好友推薦算法(MBFR)相比，在準(zhǔn)確率、召回率和效率方面都有較大幅度的提升，說明了MISUR算法的有效性。

多源信息；稀疏性；相似度；時(shí)間權(quán)重；豐富度權(quán)重

0 引言

隨著信息技術(shù)的迅猛發(fā)展，參與社交網(wǎng)絡(luò)的人越來越多，微博作為社交網(wǎng)絡(luò)的一種表現(xiàn)形式，擁有數(shù)以億計(jì)的用戶，如何在海量用戶中快速、準(zhǔn)確地實(shí)現(xiàn)好友推薦成為當(dāng)前研究的一個(gè)熱點(diǎn)問題。

傳統(tǒng)的用戶推薦的算法如協(xié)同過濾(Collaborative Filtering，CF)不僅能為用戶推薦出目標(biāo)好友，而且過程相對(duì)簡(jiǎn)單、高效且被廣泛使用; 然而，其中也存在著許多不足，數(shù)據(jù)存在稀疏性、推薦準(zhǔn)確率不高的問題是一直以來亟待解決的難題。目前，國(guó)內(nèi)外的許多學(xué)者對(duì)于以上問題相繼作出了研究，主要著眼于解決數(shù)據(jù)的稀疏性問題和提出新的推薦策略來提高推薦準(zhǔn)確率。

通過解決數(shù)據(jù)稀疏性來提高推薦準(zhǔn)確率的方法主要包括以下幾個(gè)方面：Hu等[1]為了緩解數(shù)據(jù)稀疏性問題提出了一種混合個(gè)性化隨機(jī)游走算法來推斷更多的間接用戶的相似性和服務(wù)的相似性，提高了推薦的準(zhǔn)確性； Xu等[2]提出了一種新穎的微博用戶特征表示方法，將待推薦問題轉(zhuǎn)換為二進(jìn)制的分類問題，側(cè)重于分析和提取微博用戶的多維特征，解決了傳統(tǒng)協(xié)同過濾算法的稀疏性缺陷，取得了良好的推薦效果； Yu等[3]為了克服算法在解決稀疏性問題時(shí)不適合高度動(dòng)態(tài)和大規(guī)模的環(huán)境，提出了一種新的基于聚類的協(xié)同過濾(Clustering-Collaborative Filtering，Clu-CF)方法，采用用戶聚類和服務(wù)聚類來解決數(shù)據(jù)稀疏性問題并且通過位置因素來進(jìn)行新用戶或者新業(yè)務(wù)的分類推薦； Xie等[4]為了解決數(shù)據(jù)稀疏性問題，提出了灰色預(yù)測(cè)(Grey Forecast，GF)模型，該模型的特點(diǎn)是在建立時(shí)需要更少的數(shù)據(jù)，在一定程度上能夠緩解數(shù)據(jù)稀疏性問題帶來的影響。Han等[5]將所有用戶分為多個(gè)二元組，把傳統(tǒng)的推薦問題轉(zhuǎn)換為二元組的分類問題，同時(shí)結(jié)合用戶社交內(nèi)容、社交等級(jí)和社交關(guān)系特征來進(jìn)行分類推薦，解決了傳統(tǒng)協(xié)同過濾算法稀疏性問題，提高了推薦的準(zhǔn)確率。

通過構(gòu)造新的推薦模型來提高推薦準(zhǔn)確率的方法主要包括以下幾個(gè)方面：Shang 等[6]在用戶興趣方面采用文檔主題生成模型LDA(Latent Dirichlet Allocation)建模，社交網(wǎng)絡(luò)方面使用帶權(quán)重的PageRank算法進(jìn)行建模，提出了一種融合用戶興趣和社交網(wǎng)絡(luò)的混合推薦算法，提高了推薦的準(zhǔn)確率; 徐志明等[7]主要討論了微博用戶關(guān)系分析技術(shù)，分別給出了基于多種用戶屬性的用戶相似度計(jì)算方法，并應(yīng)用于用戶推薦的相關(guān)實(shí)驗(yàn)中，取得了良好的推薦效果; Tang 等[8]提出了一種基于微博用戶相似度模型的好友推薦方法，整合了用戶之間相似度的計(jì)算方法，提出了混合相似度計(jì)算策略; Yan等[9]通過對(duì)用戶標(biāo)簽信息進(jìn)行張量分解來構(gòu)造新穎的推薦框架，提高了推薦的準(zhǔn)確率。

本文在上述研究基礎(chǔ)上不僅考慮解決推薦過程中數(shù)據(jù)的稀疏性，而且考慮到相似度的大小會(huì)隨著時(shí)間段的改變而改變這一特性，據(jù)此提出了新的推薦算法MISUR(User Recommendation algorithm based on the Similarity of Multi-source Information)。首先將微博的標(biāo)簽信息運(yùn)用K最近鄰(K-Nearest Neighbor,KNN)[10]算法對(duì)用戶進(jìn)行分類，然后對(duì)于得到的每個(gè)預(yù)分類中的用戶分別計(jì)算其社交信息相似度、微博內(nèi)容相似度和交互關(guān)系相似度，最后融合各個(gè)分相似度得出兩個(gè)用戶的總相似度來進(jìn)行推薦。算法的優(yōu)點(diǎn)主要表現(xiàn)為： 一方面充分利用了用戶的多源信息(即微博內(nèi)容、社交信息和交互行為)來進(jìn)行推薦，并在計(jì)算用戶之間相似度時(shí)引入了豐富度權(quán)重，過濾掉數(shù)據(jù)稀疏的用戶，解決了傳統(tǒng)協(xié)同過濾算法的數(shù)據(jù)稀疏性問題； 另一方面引入時(shí)間權(quán)重，適應(yīng)隨著時(shí)間變化，微博用戶的多源信息對(duì)用戶相似度的反映程度不斷變化的特點(diǎn)，從而在解決稀疏性的基礎(chǔ)上進(jìn)一步提高用戶推薦的準(zhǔn)確率。

1 多源信息相似度計(jì)算

1.1 用戶微博內(nèi)容相似度計(jì)算

微博內(nèi)容短小精悍，字?jǐn)?shù)限定在140字左右，能夠便于用戶隨時(shí)隨地地發(fā)表自己的見解感觸，同時(shí)還能夠轉(zhuǎn)發(fā)、評(píng)論其感興趣用戶的微博內(nèi)容，這些微博內(nèi)容在一定程度上都能夠反映出用戶間的興趣，因此本文通過計(jì)算用戶微博內(nèi)容的相似度來進(jìn)行用戶推薦。

首先，將用戶u某個(gè)時(shí)間段內(nèi)的微博內(nèi)容拼接成一個(gè)文檔d，并進(jìn)行分詞處理；然后，將分詞后的詞語運(yùn)用TextRank排序方法[11]，選取節(jié)點(diǎn)分?jǐn)?shù)較大的詞語作為用戶微博內(nèi)容的關(guān)鍵詞表；最后，使用詞頻-逆向文檔頻率(Term Frequency-Inverse Document Frequency, TF-IDF)方法來計(jì)算關(guān)鍵詞表的權(quán)重信息。計(jì)算方法如式(1)、(2)所示:

(1)

(2)

其中:tfi表示詞語ti出現(xiàn)的頻率，N表示訓(xùn)練集中所有文檔的數(shù)量，dfti表示包含詞語ti的文檔出現(xiàn)頻率。將用戶u的微博內(nèi)容表示成文本向量的形式即m(u)=(wu1,wu2, …,wun), 用戶v的微博內(nèi)容表示為文本向量形式即m(v)=(wv1,wv2, …,wvn)，并通過余弦相似度計(jì)算兩個(gè)用戶u和v的微博內(nèi)容相似度。計(jì)算方法如式(3)所示:

(3)

1.2 用戶交互行為相似度計(jì)算

用戶交互行為是指用戶間的直接或間接交互關(guān)系的緊密程度，本文利用兩個(gè)用戶間對(duì)彼此微博的興趣度來計(jì)算用戶交互行為相似度。

用戶對(duì)一條微博可以有多種且重復(fù)的交互行為，如：轉(zhuǎn)發(fā)(retweet)、評(píng)論(comment)、點(diǎn)贊(like)和@某條微博(at)等，而這些行為也在一定程度上代表了用戶對(duì)微博的喜愛程度, 因此可以根據(jù)用戶對(duì)一條微博的交互行為來計(jì)算用戶對(duì)該微博的興趣度。設(shè)所有微博用戶集合為user，所有用戶發(fā)布的微博集合為blog，同時(shí)用wi表示這四種交互行為的權(quán)重，通常認(rèn)為wretweet>wcomment>wat>wlike，且wretweet+wcomment+wat+wlike=1。因此用戶u對(duì)一條微博j的興趣度uj通過式(4)進(jìn)行計(jì)算：

(4)

其中:numi表示用戶u對(duì)微博j的第i種交互行為的次數(shù)。 且umax表示所有微博用戶中對(duì)微博興趣度的最大值，用來歸一化用戶對(duì)微博的興趣。

計(jì)算完用戶對(duì)一條微博的興趣度，便可根據(jù)該興趣度計(jì)算用戶u和用戶v交互行為相似度，計(jì)算方法如式(5)所示:

(5)

1.3 用戶社交關(guān)系相似度計(jì)算

用戶關(guān)注與被關(guān)注的社交關(guān)系能夠反映出用戶重要的社交信息，因此用戶社交關(guān)系的相似度計(jì)算與關(guān)注用戶及粉絲用戶密切相關(guān)。那么對(duì)于兩個(gè)用戶(u,v)來說，用戶(u,v)的共同粉絲越多，用戶間的相似性越大，用戶(u,v)的共同關(guān)注用戶越多，用戶間也越相似，兩者的社交信息可以分別表示為Relation(u)={Following(u),Follower(u)}，Relation(v)={Following(v),Follower(v)}。因此用戶(u,v)之間的社交關(guān)系相似度計(jì)算可以轉(zhuǎn)換為用戶(u,v)的關(guān)注用戶和粉絲用戶的相似度計(jì)算問題，計(jì)算方法分別如式(6)和式(7)所示:

sim(Following(u),Following(v))=

(6)

sim(Follower(u),Follower(v))=

(7)

最后，考慮將用戶(u,v)的關(guān)注用戶相似度和粉絲用戶相似度進(jìn)行加權(quán)融合來計(jì)算用戶社交關(guān)系相似度，如式(8)所示:

sim3(u,v)=w1×sim(Following(u),Following(v))+w2×sim(Follower(u),Follower(v))

(8)

其中：wi是關(guān)注用戶相似度和粉絲用戶相似度的權(quán)值，且w1+w2=1。

2 MISUR微博用戶推薦算法

MISUR微博用戶推薦算法旨在向用戶推薦其可能感興趣的用戶，為了保證推薦的準(zhǔn)確率，算法首先加入了分類功能，使其在一個(gè)類簇內(nèi)進(jìn)行推薦，從而縮小了推薦范圍，增加了算法的可行性。因此MISUR微博用戶推薦算法主要包括下面幾個(gè)部分。

1)微博用戶分類；

2)影響多源信息總相似度的因素；

3)微博用戶推薦。

2.1 微博用戶分類

在新浪微博中，用戶可以添加標(biāo)簽信息對(duì)自己進(jìn)行描述，以此來表明自己的個(gè)人興趣或者屬性。因此本文根據(jù)微博的用戶標(biāo)簽信息利用KNN分類算法對(duì)微博用戶進(jìn)行分類。

據(jù)研究統(tǒng)計(jì)，新浪微博中有許多用戶沒有為自己添加標(biāo)簽或者添加的標(biāo)簽信息過少，所以為避免用戶標(biāo)簽信息過于稀疏對(duì)分類精度造成的影響，本文對(duì)于沒有為自己添加標(biāo)簽或者添加很少的標(biāo)簽用戶使用1.1節(jié)提到的TextRank排序方法從用戶微博中抽取分?jǐn)?shù)較大的前10個(gè)關(guān)鍵詞作為用戶的標(biāo)簽信息，運(yùn)用此方法減少標(biāo)簽稀疏性對(duì)分類效果的影響。

同時(shí)k值的選取對(duì)KNN算法的分類效率和準(zhǔn)確率有很大影響：如果k值選取較小，就會(huì)獲得較少的近鄰數(shù)，噪聲數(shù)據(jù)的干擾也會(huì)加大，從而得到較低的分類準(zhǔn)確率；如果k值選取較大，就極易引入不同類的數(shù)據(jù)而產(chǎn)生異類噪聲，造成分類不準(zhǔn)確，降低分類效率。因此采用交叉檢驗(yàn)的方法得出k值與準(zhǔn)確率的關(guān)系，從而選取準(zhǔn)確率最大情況下的k值來進(jìn)行分類。

通常認(rèn)為被分為一類的用戶相似度較大，而且與目標(biāo)用戶在同一類中的用戶被推薦的可能性也較大，為提高推薦算法的準(zhǔn)確性本文將目標(biāo)用戶所屬類別中其他的用戶作為待推薦的用戶集，也只考慮向目標(biāo)用戶推薦待推薦用戶集中的用戶。

2.2 影響多源信息總相似度的因素

不同的用戶關(guān)注的內(nèi)容不盡相同，有的可能對(duì)微博內(nèi)容相似的用戶感興趣、有的可能對(duì)交互行為相似的用戶感興趣，還有的可能是對(duì)社交關(guān)系比較相似的用戶感興趣，因此，為產(chǎn)生較好的推薦集，算法應(yīng)結(jié)合實(shí)際情況，考慮影響權(quán)重信息的主要因素。

現(xiàn)有的方法在進(jìn)行相似度計(jì)算時(shí)，都是將所有時(shí)間段的微博信息以及微博關(guān)系當(dāng)作一個(gè)整體來考慮，而這種方式并沒有考慮到相似度會(huì)隨時(shí)間段的變化而變化，為避免這種變化，本文相似度計(jì)算中引入時(shí)間權(quán)重信息，認(rèn)為一個(gè)時(shí)間段就是一個(gè)時(shí)間粒度，并設(shè)置時(shí)間粒度的單位為月, 那么根據(jù)時(shí)間粒度便可定義時(shí)間權(quán)重如下。

定義1 時(shí)間權(quán)重。是指當(dāng)前時(shí)間所在的時(shí)間粒度date與用戶發(fā)布某些微博i所在的時(shí)間粒度timei之差的倒數(shù)，則相似度計(jì)算中的時(shí)間權(quán)重wt的計(jì)算公式,如式(9)所示:

(9)

同時(shí)為了減少用戶微博信息以及微博關(guān)系所具有的稀疏性影響，本文考慮將豐富度權(quán)重加入到相似度計(jì)算中，并將豐富度小于某個(gè)閾值的用戶微博信息及微博關(guān)系信息過濾掉。豐富度權(quán)重定義如下。

定義2 豐富度權(quán)重。在某個(gè)時(shí)間粒度timei中，用戶所具有的某種多源信息(即用戶微博內(nèi)容、交互行為和社交關(guān)系三種多源信息中的某一種)的微博數(shù)mi與用戶所在類簇中所有用戶平均具備這種多源信息的微博數(shù)ni之間的比值，則豐富度Ai的計(jì)算公式如式(10)、式(11)所示：

(10)

(11)

在式(10)中，k表示用戶微博內(nèi)容、用戶交互行為和用戶社交關(guān)系三種多源信息，例如，當(dāng)k=1時(shí)，考慮用戶微博內(nèi)容相似度的豐富度，即在時(shí)間粒度timei中，用戶所發(fā)布的微博的數(shù)目mi與用戶所在類簇中所有用戶平均發(fā)布的微博數(shù)目ni之比，那么ai即為三種多源信息相似度的豐富度之和。計(jì)算完之后，便可對(duì)用戶微博信息及微博關(guān)系進(jìn)行過濾，即如式(11)所示，將ai<α的部分信息過濾掉以減少用戶微博信息及微博關(guān)系的稀疏性影響。

2.3 微博用戶推薦

2.3.1 多源信息總相似度計(jì)算

進(jìn)行微博用戶推薦時(shí)，首先需要對(duì)多源信息總相似度進(jìn)行計(jì)算，如圖1所示，多源信息總相似度是將用戶微博內(nèi)容相似度、交互行為相似度和社交關(guān)系相似度3部分相似度進(jìn)行擬合并計(jì)算得到。

圖1 多源信息總相似度框架Fig. 1 Framework of total similarity about multi-source information

多源信息總相似度的計(jì)算方法如下所示。

1)首先以時(shí)間粒度月為單位，將每個(gè)類簇中的所有用戶的微博信息、交互信息與社交信息根據(jù)時(shí)間粒度進(jìn)行劃分，并將一個(gè)時(shí)間粒度(即一個(gè)月份)內(nèi)的微博信息合并成一個(gè)大文檔i進(jìn)行處理。劃分完成后，計(jì)算類簇中的目標(biāo)用戶與同類簇中的所有用戶在一個(gè)時(shí)間粒度內(nèi)的多源信息總相似度，計(jì)算公式如式(12)所示：

(12)

2)按照上述方式可計(jì)算目標(biāo)用戶與同類簇中用戶在每個(gè)時(shí)間粒度內(nèi)的用戶多源信息總相似度，然后將每個(gè)時(shí)間粒度內(nèi)的多源信息總相似度相加，可得到所有時(shí)間粒度內(nèi)多源信息總相似度，即最后的總相似度。目標(biāo)用戶與同類簇中用戶在所有時(shí)間粒度內(nèi)的多源信息總相似度的計(jì)算公式,如式(13)所示:

(13)

其中：time表示每個(gè)類簇中的微博用戶信息、交互信息或者社交信息中具有的最早時(shí)間所在的時(shí)間粒度;date表示當(dāng)前時(shí)間所在的時(shí)間粒度;k表示三種多源信息相似度。

2.3.2 用戶推薦過程

計(jì)算完每個(gè)類簇中的多源信息總相似度后，可對(duì)用戶進(jìn)行用戶推薦。推薦步驟具體如下：

1)按照用戶的分類功能，找到目標(biāo)用戶所在類簇中的其他用戶；

2)獲得每個(gè)時(shí)間粒度內(nèi)目標(biāo)用戶與其所在類簇用戶的多源信息(微博信息、社交信息和社交關(guān)系)；

3)根據(jù)獲得的多源信息、豐富度權(quán)重和時(shí)間粒度，運(yùn)用式(13)計(jì)算目標(biāo)用戶與其所在類簇中的其他用戶的多源信息總相似度;

4)選擇類簇內(nèi)與目標(biāo)用戶總相似度較高的TOP-N用戶進(jìn)行推薦。

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

3.1 實(shí)驗(yàn)環(huán)境

硬件配置 由4塊CPU為六核，主頻2.10 GHz，內(nèi)存8 GB，硬盤2 T的服務(wù)器組成的集群。

軟件配置 服務(wù)器虛擬化平臺(tái)軟件VMware ESXI，服務(wù)器的客戶端應(yīng)用程序vSphere Client，并行計(jì)算框架Spark 1.4.0，程序開發(fā)工具Eclipse4.3，操作系統(tǒng)Ubuntu14.04.3-Server-AMD64，中科院分詞系統(tǒng)ICTCLAS。

3.2 實(shí)驗(yàn)數(shù)據(jù)與預(yù)處理

目前，對(duì)于新浪微博的研究還沒有統(tǒng)一的、標(biāo)準(zhǔn)的數(shù)據(jù)集。本文使用的實(shí)驗(yàn)數(shù)據(jù)是通過新浪微博API采集的2015-10-15— 2015-12-15共3萬個(gè)用戶發(fā)布的微博數(shù)據(jù)，抓取了用戶的標(biāo)簽信息(30 000條)、用戶的微博內(nèi)容(30 000條)、用戶的交互信息(457 680條)和社交關(guān)系信息(150 890條)。

為了保證數(shù)據(jù)的有效性，在實(shí)驗(yàn)中對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行以下預(yù)處理：

1)去除部分沒有意義的微博，即微博內(nèi)容少于10個(gè)字或者被交互次數(shù)少于5次的微博；

2)去除部分交互行為和社交關(guān)系較少的用戶，即用戶的點(diǎn)贊+評(píng)論+轉(zhuǎn)發(fā)的行為不超過20次或者關(guān)注數(shù)+被關(guān)注數(shù)少于30的用戶；

3)去除停用詞、表情符號(hào)和URL鏈接等對(duì)主題沒有貢獻(xiàn)的內(nèi)容。

經(jīng)過處理后，得到了21 364個(gè)用戶的數(shù)據(jù)，其中包括用戶的標(biāo)簽信息(21 364條)、用戶的微博內(nèi)容(21 364條)、用戶的交互信息(307 450條)和社交關(guān)系信息(100 853條)。選取17 000個(gè)用戶的數(shù)據(jù)作為訓(xùn)練集，剩余的4 364個(gè)用戶的數(shù)據(jù)作為測(cè)試集。

3.3 實(shí)驗(yàn)過程

中科院分詞系統(tǒng)提供了在Hadoop上去停詞的源碼，所以去停詞結(jié)果以〈key,value〉鍵值對(duì)的形式輸出，然后用TF-IDF對(duì)向量中每一維的權(quán)重進(jìn)行計(jì)算，計(jì)算結(jié)果以〈word,textID〉形式進(jìn)行表示。調(diào)用Spark[12]中的FSOutputStream函數(shù)從Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System, HDFS)中讀取標(biāo)簽信息數(shù)據(jù)作為訓(xùn)練集，并將訓(xùn)練集分發(fā)到由分布式緩存機(jī)制構(gòu)成的6個(gè)節(jié)點(diǎn)中，然后Map函數(shù)通過靜態(tài)的方法UseDistributedCache()實(shí)現(xiàn)對(duì)緩存數(shù)據(jù)的調(diào)用。

將待測(cè)樣本集的預(yù)處理結(jié)果存入HadoopRDD中，在Map過程中計(jì)算待測(cè)樣本向量m與訓(xùn)練樣本向量n的距離，選出與m距離最近的k個(gè)訓(xùn)練樣本組成樣本集。計(jì)算測(cè)試樣本m屬于每個(gè)類別的權(quán)重w，比較權(quán)重w的大小，將測(cè)試樣本向量m歸入到權(quán)重最大的類別中，Reduce過程結(jié)合Map過程的結(jié)果判定是否進(jìn)行下一步迭代，并進(jìn)行規(guī)約操作輸出結(jié)果。

利用partitionNum()從partitionRDD中讀入上述分類操作得到的數(shù)據(jù)，并確定分區(qū)個(gè)數(shù)，同時(shí)通過調(diào)用User_sim_dict={}方法計(jì)算用戶微博內(nèi)容相似度、交互行為相似度和社交關(guān)系相似度，然后在此基礎(chǔ)上融合時(shí)間權(quán)重和豐富度權(quán)重計(jì)算總相似度并將結(jié)果存入 SimilarityRDD中。使用usersSimi=usersSimiLines.map{}.cache語句導(dǎo)入總相似度。最后通過bestUser.get.predict().collect().sortBy().take(n)向用戶推薦TOP-N個(gè)好友。

3.4 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

本文采用以下3個(gè)指標(biāo)對(duì)所提出的推薦算法進(jìn)行評(píng)價(jià)。

1)準(zhǔn)確率Pm。

定義原本是好友關(guān)系的用戶列表作為推薦列表中已經(jīng)成為好友的集合，為了保證推薦的準(zhǔn)確性，在推薦出的TOP-N個(gè)好友名單中統(tǒng)計(jì)計(jì)算實(shí)際存在的好友數(shù)目與算法推薦出的好友數(shù)目的比重，即能用來判斷推薦的性能。由此得到具體計(jì)算公式,如式(14)所示:

Pm=(Pa/Pb)*100%

(14)

其中：Pa表示推薦列表中已經(jīng)成為好友的數(shù)目，Pb表示算法推薦出的好友數(shù)目。

2)召回率Pn。

在推薦出的TOP-N個(gè)好友名單中，統(tǒng)計(jì)計(jì)算實(shí)際存在的好友數(shù)目與測(cè)試集中好友總數(shù)目的比重。由此得到具體計(jì)算公式,如式(15)所示:

Pn=(Pa/Pc)*100%

(15)

其中:Pc表示測(cè)試集中好友總數(shù)目。

3)平均處理時(shí)間T。

在相同數(shù)據(jù)集的情況下，使用平均處理時(shí)間T來探究隨著節(jié)點(diǎn)數(shù)量增加運(yùn)行時(shí)間的變化情況。

(16)

其中：n表示節(jié)點(diǎn)個(gè)數(shù),ti表示第i個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間。

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

在實(shí)驗(yàn)中，分別取TOP-N的N為10、20、30、40、50時(shí)的5種情況，在保證相同的實(shí)驗(yàn)數(shù)據(jù)集的前提下，將本文提出的基于多源信息相似度微博用戶推薦算法MISUR與傳統(tǒng)的CF算法和在分類框架下基于多社交行為的微博好友推薦算法MBFR[5]分別進(jìn)行10次實(shí)驗(yàn)，在準(zhǔn)確率、召回率和平均時(shí)間方面取多次實(shí)驗(yàn)的平均值進(jìn)行比較，得出的實(shí)驗(yàn)結(jié)果如圖2～4所示。

圖2和圖3展示了本文提出的MISUR算法、MBFR算法和傳統(tǒng)的CF算法在準(zhǔn)確率和召回率的對(duì)比情況。從整體上看，隨著推薦好友數(shù)的不斷增加，各算法的準(zhǔn)確率逐漸降低，這是因?yàn)樵跀?shù)據(jù)集中的每個(gè)節(jié)點(diǎn)分配的好友數(shù)是固定的，隨著推薦好友數(shù)目的不斷增加，推薦的準(zhǔn)確率必然會(huì)逐漸降低。而隨著推薦好友數(shù)的不斷增加，各算法的召回率不斷增加，這是因?yàn)闇y(cè)試集中的好友總數(shù)目是固定不變的，隨著推薦好友數(shù)目中已經(jīng)成為好友的數(shù)目的不斷增加，召回率呈遞增趨勢(shì)。在TOP10時(shí)算法準(zhǔn)確率達(dá)到最高，因此本文所提算法最佳的用戶推薦數(shù)目為10。同時(shí)還可以看出本文提出的MISUR算法在準(zhǔn)確率和召回率方面都高于MBFR算法和傳統(tǒng)的CF算法：通過圖2可以看出MISUR算法在準(zhǔn)確率方面相比MBFR算法和CF算法分別提高了約8.4%和16.8%，通過圖3也可以看出，在召回率方面MISUR算法比MBFR算法和CF算法分別提高了約9.6%和19.1%。這是因?yàn)閭鹘y(tǒng)的CF算法存在數(shù)據(jù)稀疏性的問題； MBFR算法雖然考慮了多種社交行為來解決數(shù)據(jù)稀疏性的問題，但是該算法沒有考慮到時(shí)間對(duì)多種社交行為的影響，而本文算法不但考慮了多種信息融合來計(jì)算相似度，而且在計(jì)算相似度的同時(shí)加入豐富度來更好地解決稀疏性問題，加入時(shí)間權(quán)重適應(yīng)用戶興趣的變化，從而在解決稀疏性的同時(shí)提高了推薦準(zhǔn)確率。

圖2 三種算法準(zhǔn)確率對(duì)比Fig. 2 Precision comparison of three algorithms

圖3 三種算法召回率對(duì)比Fig. 3 Recall comparison of three algorithms

圖4 三種算法隨著節(jié)點(diǎn)數(shù)變化的運(yùn)行時(shí)間對(duì)比Fig. 4 Running time comparison of three algorithms in different nodes

圖4展示了在Spark并行計(jì)算框架下，隨著節(jié)點(diǎn)數(shù)的增加，算法運(yùn)行時(shí)間逐漸減少。因?yàn)榘阉杏脩羝骄值?個(gè)節(jié)點(diǎn)上進(jìn)行并行計(jì)算，同時(shí)利用KNN算法預(yù)先對(duì)微博用戶標(biāo)簽數(shù)據(jù)進(jìn)行分類，所以本文提出的MISUR算法與MBFR算法和傳統(tǒng)的CF算法相比，提高了算法的運(yùn)行效率。同時(shí)，對(duì)三種算法在1～6個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間進(jìn)行計(jì)算可以得出本文提出的MISUR算法比MBFR算法縮短了1.7%～9.3%，比傳統(tǒng)的CF算法縮短了9.1%～17.9%?？傮w來說，本文提出的MISUR算法在準(zhǔn)確率、召回率和執(zhí)行效率上都有一定的提高。

4 結(jié)語

本文針對(duì)傳統(tǒng)的協(xié)同過濾推薦算法存在數(shù)據(jù)稀疏性和推薦準(zhǔn)確率不高的問題，提出了基于多源信息相似度的微博用戶推薦方法。算法充分運(yùn)用了多源信息相互融合能夠提高推薦準(zhǔn)確率的優(yōu)勢(shì)，同時(shí)引入豐富度權(quán)重和時(shí)間權(quán)重解決了協(xié)同過濾中存在的數(shù)據(jù)稀疏性問題。通過實(shí)驗(yàn)驗(yàn)證，不僅推薦準(zhǔn)確率得到了一定的改善，而且由于在并行計(jì)算框架Spark上運(yùn)行算法，算法運(yùn)行效率得到了較大的提高。然而，本文并沒有考慮到使用微博用戶的網(wǎng)絡(luò)結(jié)構(gòu)信息來進(jìn)行好友推薦。因此，下一步的工作是研究融合網(wǎng)絡(luò)結(jié)構(gòu)的微博好友推薦算法。

References)

[1] HU Y, PENG Q, HU X. A time-aware and data sparsity tolerant approach for Web service recommendation[C]// Proceedings of the 2014 IEEE International Conference on Web Services. Washington, DC: IEEE Computer Society, 2014: 33-40.

[2] XU Y, ZHOU M, HAN S. Feature representation for microblog followee recommendation in classification framework[C]// Proceedings of the 7th International Conference on Advanced Computational Intelligence. Piscataway, NJ: IEEE, 2015: 318-322.

[3] YU C, HUANG L. CluCF: a clustering CF algorithm to address data sparsity problem[M]// Service Oriented Computing & Applications. Berlin: Springer, 2016: 191-199.

[4] XIE F, CHEN Z, SHANG J, et al. Grey forecast model for accurate recommendation in presence of data sparsity and correlation[J]. Knowledge-Based Systems, 2014, 69:179-190.

[5] HAN S, YAN X. Friend recommendation of microblog in classification framework: using multiple social behavior features[C]// Proceedings of the 2014 International Conference on Behavior, Economic and Social Computing. Piscataway, NJ: IEEE, 2014:1-6.

[6] SHANG Y, ZHANG P, CAO Y. A new interest-sensitive and network-sensitive method for user recommendation[C]// Proceedings of the 8th IEEE International Conference on Networking, Architecture and Storage. Piscataway, NJ: IEEE, 2013:242-246.

[7] 徐志明, 李棟, 劉挺,等. 微博用戶的相似性度量及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1):207-218.(XU Z M, LI D, LIU T, et al. Similarity measurement and its application to the users of micro-blog[J]. Chinese Journal of Computers, 2014, 37(1): 207-218.)

[8] TANG F, ZHANG B, ZHENG J, et al. Friend recommendation based on the similarity of micro-blog user model[C]// Proceedings of the 2013 IEEE International Conference on Green Computing and Communications. Piscataway, NJ: IEEE, 2013:2200-2204.

[9] YAN Z, ZHOU J. User recommendation with tensor factorization in social networks[C]// Proceedings of the 2012 IEEE International Conference on Acoustics. Piscataway, NJ: IEEE, 2012:3853-3856.

[10] COVER T, HART P. Nearest neighbor pattern classification [J].IEEE Transactions on Information Theory, 1967, 13(1):21-27.

[11] MIHALCEA R, TARAU P. TextRank: bringing order into texts[EB/OL].[2016-06-20]. https://www.mendeley.com/catalog/textrank-bringing-order-texts/.

[12] WINLAW M, HYNES M B, CATERINI A, et al. Algorithmic acceleration of parallel ALS for collaborative filtering: speeding up distributed big data recommendation in Spark[C]// Proceedings of the 2015 IEEE 21st International Conference on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2015:682-691.

This work is partially supported by the National Natural Science Foundation of China(61402258),the Research Project of Teaching Reform in Undergraduate Colleges and Universities in Shandong Province(2015M102), the Research Project of Teaching Reform in Universities (jg05021).

YAO Binxiu, born in 1991, M. S. candidate. His research interests include distributed computing, data mining, microblog recommendation.

NI Jiancheng, born in 1971, Ph. D., professor. His research interests include distributed computing, machine learning, data mining.

YU Pingping, born in 1991, M. S. candidate. Her research interests include distributed computing, data mining.

LI Linlin, born in 1991, M. S. candidate. Her research interests include parallel and distributed computing, data mining.

CAO Bo, born in 1992, M. S. candidate. Her research interests include parallel and distributed computing, data mining.

Micro blog user recommendation algorithm based on similarity of multi-source information

YAO Binxiu1, NI Jiancheng2*, YU Pingping1, LI Linlin1，CAO Bo1

(1.CollegeofInformationScienceandEngineering,QufuNormalUniversity,RizhaoShandong276826,China;2.CollegeofSoftware,QufuNormalUniversity,QufuShandong273100,China)

Focusing on the data sparsity and low accuracy of recommendation existed in traditional Collaborative Filtering (CF) recommendation algorithm, a micro blog User Recommendation algorithm based on the Similarity of Multi-source Information, named MISUR, was proposed. Firstly, the micro blog users were classified byK-Nearest Neighbor (KNN) algorithm according to their tag information. Secondly, the similarity of the multi-source information, such as micro blog content, interactive relationship and social information, was calculated for each user in each class. Thirdly, the time weight and the richness weight were introduced to calculate the total similarity of multi-source information, and the TOP-Nrecommendation was used in a descending order. Finally, the experiment was carried out on the parallel computing framework Spark. The experimental results show that, compared with CF recommendation algorithm and micro blog Friend Recommendation algorithm based on Multi-social Behavior (MBFR), the superiority of the MISUR algorithm is validated in terms of accuracy, recall and efficiency.

multi-source information; sparsity; similarity; time weight; richness weight

2016-10-14;

2016-11-02。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402258);山東省本科高校教學(xué)改革研究項(xiàng)目(2015M102); 校級(jí)教學(xué)改革研究項(xiàng)目(jg05021)。

姚彬修(1991—)，男，山東青州人，碩士研究生，CCF會(huì)員，主要研究方向：分布式計(jì)算、數(shù)據(jù)挖掘、微博推薦； 倪建成(1971—)，男，山東曲阜人，教授，博士，CCF高級(jí)會(huì)員，主要研究方向：分布式計(jì)算、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘； 于蘋蘋(1991—)，女，山東濟(jì)南人，碩士研究生，主要研究方向：分布式計(jì)算、數(shù)據(jù)挖掘； 李淋淋(1991—)，女，山東德州人，碩士研究生，主要研究方向：并行與分布式計(jì)算、數(shù)據(jù)挖掘； 曹博(1992—)，女，黑龍江伊春人，碩士研究生，主要研究方向：并行與分布式計(jì)算、數(shù)據(jù)挖掘。

1001-9081(2017)05-1382-05

10.11772/j.issn.1001-9081.2017.05.1382

TP301.6

A