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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 多源信息相似度計算

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

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

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

(1)

(2)

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

(3)

1.2 用戶交互行為相似度計算

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

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

(4)

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

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

(5)

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

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

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

(6)

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

(7)

最后，考慮將用戶(u,v)的關(guān)注用戶相似度和粉絲用戶相似度進行加權(quán)融合來計算用戶社交關(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微博用戶推薦算法旨在向用戶推薦其可能感興趣的用戶，為了保證推薦的準確率，算法首先加入了分類功能，使其在一個類簇內(nèi)進行推薦，從而縮小了推薦范圍，增加了算法的可行性。因此MISUR微博用戶推薦算法主要包括下面幾個部分。

1)微博用戶分類；

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

3)微博用戶推薦。

2.1 微博用戶分類

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

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

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

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

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

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

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

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

(9)

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

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

(10)

(11)

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

2.3 微博用戶推薦

2.3.1 多源信息總相似度計算

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

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

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

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

(12)

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

(13)

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

2.3.2 用戶推薦過程

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

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

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

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

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

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

3.1 實驗環(huán)境

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

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

3.2 實驗數(shù)據(jù)與預處理

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

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

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

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

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

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

3.3 實驗過程

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

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

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

3.4 實驗評價指標

本文采用以下3個指標對所提出的推薦算法進行評價。

1)準確率Pm。

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

Pm=(Pa/Pb)*100%

(14)

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

2)召回率Pn。

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

Pn=(Pa/Pc)*100%

(15)

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

3)平均處理時間T。

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

(16)

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

3.5 實驗結(jié)果分析

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

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

圖2 三種算法準確率對比Fig. 2 Precision comparison of three algorithms

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

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

圖4展示了在Spark并行計算框架下，隨著節(jié)點數(shù)的增加，算法運行時間逐漸減少。因為把所有用戶平均分到6個節(jié)點上進行并行計算，同時利用KNN算法預先對微博用戶標簽數(shù)據(jù)進行分類，所以本文提出的MISUR算法與MBFR算法和傳統(tǒng)的CF算法相比，提高了算法的運行效率。同時，對三種算法在1～6個節(jié)點的運行時間進行計算可以得出本文提出的MISUR算法比MBFR算法縮短了1.7%～9.3%，比傳統(tǒng)的CF算法縮短了9.1%～17.9%。總體來說，本文提出的MISUR算法在準確率、召回率和執(zhí)行效率上都有一定的提高。

4 結(jié)語

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

國家自然科學基金資助項目(61402258);山東省本科高校教學改革研究項目(2015M102); 校級教學改革研究項目(jg05021)。

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

1001-9081(2017)05-1382-05

10.11772/j.issn.1001-9081.2017.05.1382

TP301.6

A