基于融合標簽與蟻群的協(xié)同過濾微博推薦算法

李梁 魏赟

摘要：針對協(xié)同過濾算法中存在數(shù)據(jù)稀疏的問題，提出一種基于融合用戶標簽和蟻群的協(xié)同過濾微博推薦算法。將表示用戶興趣的標簽引入推薦模型中，利用標簽和用戶以及標簽和微博的關聯(lián)度，建立用戶對微博的興趣度模型。另外結合蟻群聚類和協(xié)同過濾為目標用戶進行用戶聚類，計算出對目標用戶的待推薦微博集。最后利用用戶對微博的興趣度模型從待推薦微博集中選出Top-N為目標用戶進行推薦。實驗引入標簽和蟻群算法的有效性，將測試結果與傳統(tǒng)協(xié)同過濾推薦算法和純基于標簽的微博推薦算法進行比較，該算法不僅改善了協(xié)同過濾算法中數(shù)據(jù)稀疏和冷啟動的問題，而且推薦準確度有明顯提高。

關鍵詞：標簽；文本分類；蟻群算法；協(xié)同過濾；微博推薦

DOI：10.11907/rjdk.172865

中圖分類號：TP312

文獻標識碼：A文章編號：1672-7800（2018）007-0083-04

Abstract：Aimingattheproblemsofsparseandcoldstartofdatainmicro-blogrecommendation，thispaperproposesafusiontagandantcolonycollaborativefilteringmicro-blogrecommendationalgorithm.Thetagwillbeinterestedintherecommendedmodeltoestablishauserinterestratemodelofmicro-blogbyusingtherelevanceoftag-userandtag-blog.Inaddition，antcolonyclusteringandcollaborativefilteringforthetargetuserclusteringareusedtocalculatetherecommendedmicro-blogsetforthetargetusers.Finally，theuser'sinterestratemodelofmicro-blogfromtherecommendedmicro-blogisfocusedonTop-Nmicro-blogrecommendedforthetargetusers.Theresultsshowthatcomparedwiththetraditionalcooperativefilteringrecommendationalgorithmandthepurelybasedmicro-blogrecommendationalgorithm，thealgorithmnotonlyimprovesthedatasparseandcoldstartinthecooperativefilteringalgorithmoftheproblem，butalsotherecommendedaccuracyisimprovedsignificantly.

KeyWords：tag；textrank；antcolonyalgorithm；collaborativefiltering；micro-blogrecommendation

0引言

微博是近年來出現(xiàn)的一種新型社交網(wǎng)絡服務，每天產(chǎn)生數(shù)十億計的微博信息。如何從海量數(shù)據(jù)中挖掘出用戶感興趣的內容向其推薦，成為目前研究熱點。

在眾多推薦算法中，基于協(xié)同過濾的推薦算法應用最廣，其基本思想是以目標用戶為中心，然后為目標用戶尋找有相似興趣愛好的鄰居用戶，根據(jù)鄰居用戶對某個資源的評價情況，統(tǒng)計出得分較高的資源推薦給目標用戶。不過由于用戶對資源的評價存在數(shù)據(jù)稀疏問題，導致推薦算法性能下降。因此一些研究人員[1-6]將標簽應用到協(xié)同過濾推薦算法中，通過實驗驗證可以改善推薦算法的數(shù)據(jù)稀疏問題；還有研究人員[7-9]將群體智能算法和協(xié)同過濾算法結合起來，發(fā)現(xiàn)可以改善協(xié)同過濾算法冷啟動問題，提高推薦質量。針對以上算法存在的數(shù)據(jù)稀疏和冷啟動問題，本文提出一種基于融合標簽與蟻群算法的協(xié)同過濾算法（TCFA）。利用TextRank[10-12]排序方法從用戶發(fā)布的微博中提取關鍵詞作為用戶標簽集，將標簽作為用戶和資源的中間紐帶，建立用戶對微博的興趣模型；利用蟻群算法中螞蟻覓食的原理，獲取用戶數(shù)據(jù)對象的聚類中心，將聚類的用戶數(shù)據(jù)作為待推薦微博集，利用標簽計算目標用戶所發(fā)歷史微博與待推薦微博之間相似度，最后選出用戶最感興趣的Top-N條微博向用戶推薦。實驗證明該算法改善了微博推薦的數(shù)據(jù)稀疏和冷啟動問題。

1算法設計

1.1用戶標簽提取

用戶標簽可以由用戶自己設定，但對于自身設定標簽較少或者未設定標簽的用戶，需要從用戶發(fā)布的微博中提取關鍵詞，作為用戶的標簽。本文采用TextRank算法抽取關鍵詞。

TextRank算法將文本看作是G（V，E）的有向圖形式，點集V為文本中的詞，邊集E為詞語之間的邊，對于某個確定的Vi點，其分數(shù)可根據(jù)公式（1）計算得出：

1.2用戶微博興趣模型建立

隨著微博用戶和微博資源的激增，用戶-微博資源的矩陣成為高維矩陣，而用戶對微博資源的評分很少，造成微博資源-評分的矩陣十分稀疏。在協(xié)同過濾算法中引入獲取到的標簽，如圖1所示。

根據(jù)圖1，將用戶-標簽-微博資源拆分成用戶-標簽，標簽-微博資源兩個二維關系，利用TF-IDF，分別計算用戶和標簽的關聯(lián)度、標簽和微博資源的關聯(lián)度，最后通過關聯(lián)度的組合建立用戶微博興趣模型。

1.2.1用戶與標簽關聯(lián)度

用戶和標簽的關聯(lián)度[13]是指用戶為自己添加該標簽的可能性以及該標簽與用戶依賴程度，記為：

1.2.2標簽與資源關聯(lián)度

資源與標簽的關聯(lián)度是指從微博中提取出該標簽的可能性或者該標簽對于該條微博的重要度，記為：

1.3微博資源聚類中心計算

為了實現(xiàn)協(xié)同過濾算法中的用戶聚類，基于“螞蟻覓食”[14-15]的原理，將具有不同標簽的微博用戶看作是有不同屬性的螞蟻，螞蟻尋找的“食物源”就是微博資源聚類中心，聚類過程如下：

1.4微博相似度計算

1.4.1基于標簽的相似度計算

利用標簽，將用戶為自己設置的標簽以及從用戶微博中提取的標簽作為微博資源的特征信息，用于相似度計算，主要依據(jù)對于微博Ri和Rj中提取的標簽相似個數(shù)，標簽相似個數(shù)越多，則代表微博Ri和Rj越類似的原則，同時考慮到從用戶微博中提取的標簽不同則取值為0，兩個標簽相同或類似則取值為1，所以采用Jaccard系數(shù)[16-17]進行計算，計算公式如下：

1.4.2興趣度預測

根據(jù)用戶對微博的興趣模型，可以求出用戶對微博資源的興趣度。從式（8）的結果Iu，r中可以計算得到用戶U對自己發(fā)過的歷史微博集Ri的興趣度，然后通過計算用戶所發(fā)的歷史微博集Ri和待推薦微博資源集Rj的相似度，從而求得用戶U對于待推薦微博資源集Rj的興趣度，記為：

2TCFA算法模型

本文提出的基于融合標簽和蟻群的微博推薦算法，主要是在傳統(tǒng)協(xié)同過濾推薦算法的基礎上，引入標簽和蟻群算法，利用標簽和用戶以及微博資源的關聯(lián)度計算，建立用戶對微博的興趣模型，另外，利用蟻群算法對海量微博數(shù)據(jù)進行聚類，依據(jù)擁有相同標簽的用戶興趣相近的原則，為目標用戶聚類一批有相同興趣的用戶，將聚類出的用戶所發(fā)微博數(shù)據(jù)作為待推薦微博集，再利用標簽計算目標用戶所發(fā)歷史微博與待推薦微博之間的相似度，最后選出用戶最感興趣的Top-N條微博向用戶推薦。具體的算法流程如下：

Step1：將原來的三維微博關系用戶-標簽-微博資源分解為兩個二維關系用戶-標簽和標簽-微博資源。利用式（4）和式（5）計算用戶和標簽的TF（u，t）和IDF（u，t），利用式（6）和式（7）計算標簽和微博資源的TF（r，t）和IDF（r，t）；

Step2：構建用戶對微博資源的興趣模型。根據(jù)Step1求得的結果，分別按照式（3）和式（6）計算得到用戶與標簽的關聯(lián)度，標簽和微博資源的關聯(lián)度，利用兩個關聯(lián)度構建出感興趣模型；

Step3：根據(jù)目標用戶的標簽，利用蟻群算法進行用戶聚類，為目標用戶聚類出標簽相同數(shù)較多的用戶集Ui，再利用協(xié)同過濾算法，對目標用戶ui微博資源與用戶集Ui的微博資源進行篩選，得出對于目標用戶ui的待推薦微博集Rj；

Step4：計算微博資源的相似度，利用目標用戶ui的標簽，計算目標用戶的歷史微博Ri和待推薦微博集Rj的相似度，采用式（11）計算微博資源間的相似度；

Step5：根據(jù)建立的興趣模型，以及求得的目標用戶的歷史微博Ri和待推薦微博集Rj的相似度，根據(jù)式（8）計算得到目標用戶ui對于歷史微博Ri的興趣度；

Step6：利用式（12）的興趣度模型，求得目標用戶ui對于待推薦微博集Rj的興趣度，從高到低排序，選取前N條微博對用戶進行推薦。

3實驗結果與分析

3.1實驗數(shù)據(jù)與相關工具

本文實驗數(shù)據(jù)采集于新浪微博，實驗利用爬蟲技術、調用新浪微博提供的API接口，采集500名用戶發(fā)布的所有歷史微博數(shù)據(jù)，同時采集除其他用戶發(fā)布的1000條微博數(shù)據(jù)作為實驗數(shù)據(jù)集。將采集到的微博數(shù)據(jù)進行預處理，去除微博文本中無用數(shù)據(jù)URL、表情符號等。分詞工具為Python中文分詞組件jieba。統(tǒng)計發(fā)現(xiàn)大部分的用戶標簽為名詞，本文選取分詞后的名詞，利用上文1.1中的方法生成用戶標簽。實驗數(shù)據(jù)集被隨機分為訓練集和測試集，其中750條微博數(shù)據(jù)作為訓練集，250條微博數(shù)據(jù)作為測試集。開發(fā)壞境為Spyder，開發(fā)語言為Python。

3.2評價指標

指標在最終為用戶推薦的N條微博中，包含目標用戶發(fā)過的微博條數(shù)，所以準確率（Precision）和召回率（Recall）兩個指標可以用于評價算法的優(yōu)劣，公式為：

Precision=推薦微博是用戶自身發(fā)布的微博個數(shù)推薦的微博個數(shù)N

Recall=推薦微博是自身發(fā)布的微博個數(shù)用戶自身發(fā)布的微博總個數(shù)

3.3實驗結果和分析

微博用戶在瀏覽微博時，通常只會對排在前面的微博感興趣，所以研究排名較前的微博更有實際意義。本文重點測試Top-3、Top-7、Top-11、Top-15四種情況下微博推薦的性能。為了驗證本文算法的有效性，在同等數(shù)據(jù)集的基礎上，與傳統(tǒng)的協(xié)同過濾推薦算法（CF）、基于標簽的協(xié)同過濾算法（TCF）[3]和基于用戶標簽的微博推薦算法（TR）[7]進行對比實驗，對比實驗結果如圖2、圖3所示。

由圖2和圖3的結果可以看出，本文提出的TCFA算法與傳統(tǒng)的協(xié)同過濾算法（CF），以及融合標簽的協(xié)同過濾算法（TCF）和基于用戶標簽的微博推薦算法（TR）相比，準確率及召回率都有提高，在N=7時，準確率是最高的，所以在利用本文推薦算法給用戶推薦微博時，選擇N=7進行推薦。傳統(tǒng)協(xié)同過濾算法存在數(shù)據(jù)稀疏的問題，融合標簽的協(xié)同過濾算法雖然改善了微博推薦的數(shù)據(jù)稀疏問題，但還存在冷啟動的問題。本文提出的TCFA算法不僅改善了數(shù)據(jù)稀疏問題，也較好地解決了冷啟動問題，提高了微博推薦結果的準確性，證明了本文算法的有效性。

4結語

本文在傳統(tǒng)協(xié)同過濾推薦算法的基礎上，引入蟻群算法和標簽，設計實現(xiàn)融合標簽和蟻群的協(xié)同過濾微博推薦算法（TCFA）。該算法利用標簽在用戶和微博資源之間建立橋梁，標簽作為兩者的紐帶，將用戶-標簽-微博資源的三維關系分解成兩個用戶-標簽和標簽-微博資源的二維關系，再計算兩者關聯(lián)度。利用蟻群目標用戶進行用戶聚類，根據(jù)標簽相同個數(shù)多的用戶興趣也會相似的特征，為目標用戶聚類產(chǎn)生待推薦微博集，最后利用協(xié)同過濾推薦算法進行推薦，最終得到TOP-N個微博推薦集。一方面該算法降低了數(shù)據(jù)稀疏性問題，引入標簽和蟻群算法緩解了新用戶得不到微博推薦的冷啟動問題，然后再利用相似度計算，提高微博推薦的準確率。實驗結果表明，TCFA算法的準確率及召回率都有提高。該算法雖然改善了數(shù)據(jù)稀疏和冷啟動問題，但在今后的工作中，冷啟動問題和數(shù)據(jù)稀疏問題仍然是研究的重點，核心問題是用戶在沒有相關操作時如何提高推薦算法的準確率。在用戶沒有相應標簽的情況下，標簽提取的準確度也會對推薦結果產(chǎn)生影響，因此下一步需要重點研究如何提高標簽的質量，以提高推薦性能；另外，針對目前日益增長的大量數(shù)據(jù)，考慮到推薦的實時性，可嘗試將本文提出的算法在分布式平臺上實現(xiàn)，提高推薦系統(tǒng)的實時性和可擴展性。

參考文獻：

[1]張怡文，岳麗華.基于共同用戶和相似標簽的好友推薦方法[J].計算機應用，2013，33（8）：2273-2275.

[2]王寧寧，魯燃，王智昊，等.基于用戶標簽的微博推薦算法[J].計算機應用研究，2017，34（1）：58-61.

[3]蔡強，韓東梅.基于標簽和協(xié)同過濾的個性化資源推薦[J].計算機科學，2014，41（1）：69-71.

[4]郭彩云，王會進.改進的基于標簽的協(xié)同過濾算法[J].計算機工程與應用，2016，52（8）：56-61.

[5]MAHF.Tagcorrelationandusersocialrelationbasedmicroblogrecommendation[C].Vancouver：InternationalJointConferenceonNeuralNetworks，2016.

[6]DENGL，HUANGJMJ.Thepredictionofusertopicinterestbasedontagsandinteractionofusers[C].DataScienceinCyberspace，2016：20-26.

[7]王寧寧，魯燃，王智昊.融合標簽與人工蜂群的微博推薦算法[J].計算機應用，2016，36（10）：2789-2793.

[8]吳月萍，王娜，馬良.基于蟻群算法的協(xié)同過濾推薦系統(tǒng)的研究[J].計算機技術與發(fā)展，2011，21（10）：73-76.

[9]碩良勛，柴變芳，張新東.基于改進最近鄰的協(xié)同過濾推薦算法[J].計算機工程與應用，2015，51（5）：137-141.

[10]BLEIDM，NgAY，JORDANMI.Latentdirichletallocation[J].JournalofMachineLearningResearch，2003，3：993-1022.

[11]李鵬，王斌，石志偉，等.Tag-Textrank_一種基于tag的網(wǎng)頁關鍵詞抽取方法[J].計算機研究與發(fā)展，2012，49（11）：2344-2351.

[12]MIHALCEAR，TARAUP.Textrank：bringingorderintotexts[C].ProceedingofConferenceonEmpiricalMethodsinNaturalLanguageProcessing，2004：404-411.

[13]劉健，張琨，陳旋.基于標簽和協(xié)同過濾的個性化推薦算法[J].計算機與現(xiàn)代化，2016，（2）：62-65.

[14]BOBADILLAJ，ORTEGAF，HEMANDOA.Improvingcollaborativefilteringrecommendersystemresultsandperformanceusinggeneticalgorithms[J].Knowledge-BasedSystems.2011（8）：1310-1316.

[15]WEIY，KUMARA.Antcolonyoptimizationfordisasterreliefoperations[J].TransportationResearch（PartE），2007，43（6）：660-672.

[16]BOBADILLAJ，ORTEGAF，HEMANDOA.Acollaborativefilteringsimilaritymeasurebasedonsingularities[J].InformationProcessingandManagement，2012，48（2）：204-217.

[17]李斌，張博，劉學軍.基于Jaccard相似度和位置行為的協(xié)同過濾推薦算法[J].計算機科學，2016，43（12）：200-205.

（責任編輯：江艷）