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

李梁 魏赟

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

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

DOI：10.11907/rjdk.172865

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)絡(luò)服務(wù)，每天產(chǎn)生數(shù)十億計(jì)的微博信息。如何從海量數(shù)據(jù)中挖掘出用戶感興趣的內(nèi)容向其推薦，成為目前研究熱點(diǎn)。

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

1算法設(shè)計(jì)

1.1用戶標(biāo)簽提取

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

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

1.2用戶微博興趣模型建立

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

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

1.2.1用戶與標(biāo)簽關(guān)聯(lián)度

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

1.2.2標(biāo)簽與資源關(guān)聯(lián)度

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

1.3微博資源聚類中心計(jì)算

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

1.4微博相似度計(jì)算

1.4.1基于標(biāo)簽的相似度計(jì)算

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

1.4.2興趣度預(yù)測(cè)

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

2TCFA算法模型

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

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

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

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

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

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

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

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

3.1實(shí)驗(yàn)數(shù)據(jù)與相關(guān)工具

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

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

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

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

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

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

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

[3]蔡強(qiáng)，韓東梅.基于標(biāo)簽和協(xié)同過濾的個(gè)性化資源推薦[J].計(jì)算機(jī)科學(xué)，2014，41（1）：69-71.

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

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

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

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

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

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

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

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

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

[13]劉健，張琨，陳旋.基于標(biāo)簽和協(xié)同過濾的個(gè)性化推薦算法[J].計(jì)算機(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]李斌，張博，劉學(xué)軍.基于Jaccard相似度和位置行為的協(xié)同過濾推薦算法[J].計(jì)算機(jī)科學(xué)，2016，43（12）：200-205.

（責(zé)任編輯：江艷）