基于融合标签与蚁群的协同过滤微博推荐算法

李梁 魏赟

摘要：针对协同过滤算法中存在数据稀疏的问题，提出一种基于融合用户标签和蚁群的协同过滤微博推荐算法。将表示用户兴趣的标签引入推荐模型中，利用标签和用户以及标签和微博的关联度，建立用户对微博的兴趣度模型。另外结合蚁群聚类和协同过滤为目标用户进行用户聚类，计算出对目标用户的待推荐微博集。最后利用用户对微博的兴趣度模型从待推荐微博集中选出Top-N为目标用户进行推荐。实验引入标签和蚁群算法的有效性，将测试结果与传统协同过滤推荐算法和纯基于标签的微博推荐算法进行比较，该算法不仅改善了协同过滤算法中数据稀疏和冷启动的问题，而且推荐准确度有明显提高。

关键词：标签；文本分类；蚁群算法；协同过滤；微博推荐

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引言

微博是近年來出现的一种新型社交网络服务，每天产生数十亿计的微博信息。如何从海量数据中挖掘出用户感兴趣的内容向其推荐，成为目前研究热点。

在众多推荐算法中，基于协同过滤的推荐算法应用最广，其基本思想是以目标用户为中心，然后为目标用户寻找有相似兴趣爱好的邻居用户，根据邻居用户对某个资源的评价情况，统计出得分较高的资源推荐给目标用户。不过由于用户对资源的评价存在数据稀疏问题，导致推荐算法性能下降。因此一些研究人员[1-6]将标签应用到协同过滤推荐算法中，通过实验验证可以改善推荐算法的数据稀疏问题；还有研究人员[7-9]将群体智能算法和协同过滤算法结合起来，发现可以改善协同过滤算法冷启动问题，提高推荐质量。针对以上算法存在的数据稀疏和冷启动问题，本文提出一种基于融合标签与蚁群算法的协同过滤算法（TCFA）。利用TextRank[10-12]排序方法从用户发布的微博中提取关键词作为用户标签集，将标签作为用户和资源的中间纽带，建立用户对微博的兴趣模型；利用蚁群算法中蚂蚁觅食的原理，获取用户数据对象的聚类中心，将聚类的用户数据作为待推荐微博集，利用标签计算目标用户所发历史微博与待推荐微博之间相似度，最后选出用户最感兴趣的Top-N条微博向用户推荐。实验证明该算法改善了微博推荐的数据稀疏和冷启动问题。

1算法设计

1.1用户标签提取

用户标签可以由用户自己设定，但对于自身设定标签较少或者未设定标签的用户，需要从用户发布的微博中提取关键词，作为用户的标签。本文采用TextRank算法抽取关键词。

TextRank算法将文本看作是G（V，E）的有向图形式，点集V为文本中的词，边集E为词语之间的边，对于某个确定的Vi点，其分数可根据公式（1）计算得出：

1.2用户微博兴趣模型建立

随着微博用户和微博资源的激增，用户-微博资源的矩阵成为高维矩阵，而用户对微博资源的评分很少，造成微博资源-评分的矩阵十分稀疏。在协同过滤算法中引入获取到的标签，如图1所示。

根据图1，将用户-标签-微博资源拆分成用户-标签，标签-微博资源两个二维关系，利用TF-IDF，分别计算用户和标签的关联度、标签和微博资源的关联度，最后通过关联度的组合建立用户微博兴趣模型。

1.2.1用户与标签关联度

用户和标签的关联度[13]是指用户为自己添加该标签的可能性以及该标签与用户依赖程度，记为：

1.2.2标签与资源关联度

资源与标签的关联度是指从微博中提取出该标签的可能性或者该标签对于该条微博的重要度，记为：

1.3微博资源聚类中心计算

为了实现协同过滤算法中的用户聚类，基于“蚂蚁觅食”[14-15]的原理，将具有不同标签的微博用户看作是有不同属性的蚂蚁，蚂蚁寻找的“食物源”就是微博资源聚类中心，聚类过程如下：

1.4微博相似度计算

1.4.1基于标签的相似度计算

利用标签，将用户为自己设置的标签以及从用户微博中提取的标签作为微博资源的特征信息，用于相似度计算，主要依据对于微博Ri和Rj中提取的标签相似个数，标签相似个数越多，则代表微博Ri和Rj越类似的原则，同时考虑到从用户微博中提取的标签不同则取值为0，两个标签相同或类似则取值为1，所以采用Jaccard系数[16-17]进行计算，计算公式如下：

1.4.2兴趣度预测

根据用户对微博的兴趣模型，可以求出用户对微博资源的兴趣度。从式（8）的结果Iu，r中可以计算得到用户U对自己发过的历史微博集Ri的兴趣度，然后通过计算用户所发的历史微博集Ri和待推荐微博资源集Rj的相似度，从而求得用户U对于待推荐微博资源集Rj的兴趣度，记为：

2TCFA算法模型

本文提出的基于融合标签和蚁群的微博推荐算法，主要是在传统协同过滤推荐算法的基础上，引入标签和蚁群算法，利用标签和用户以及微博资源的关联度计算，建立用户对微博的兴趣模型，另外，利用蚁群算法对海量微博数据进行聚类，依据拥有相同标签的用户兴趣相近的原则，为目标用户聚类一批有相同兴趣的用户，将聚类出的用户所发微博数据作为待推荐微博集，再利用标签计算目标用户所发历史微博与待推荐微博之间的相似度，最后选出用户最感兴趣的Top-N条微博向用户推荐。具体的算法流程如下：

Step1：将原来的三维微博关系用户-标签-微博资源分解为两个二维关系用户-标签和标签-微博资源。利用式（4）和式（5）计算用户和标签的TF（u，t）和IDF（u，t），利用式（6）和式（7）计算标签和微博资源的TF（r，t）和IDF（r，t）；

Step2：构建用户对微博资源的兴趣模型。根据Step1求得的结果，分别按照式（3）和式（6）计算得到用户与标签的关联度，标签和微博资源的关联度，利用两个关联度构建出感兴趣模型；

Step3：根据目标用户的标签，利用蚁群算法进行用户聚类，为目标用户聚类出标签相同数较多的用户集Ui，再利用协同过滤算法，对目标用户ui微博资源与用户集Ui的微博资源进行筛选，得出对于目标用户ui的待推荐微博集Rj；

Step4：计算微博资源的相似度，利用目标用户ui的标签，计算目标用户的历史微博Ri和待推荐微博集Rj的相似度，采用式（11）计算微博资源间的相似度；

Step5：根据建立的兴趣模型，以及求得的目标用户的历史微博Ri和待推荐微博集Rj的相似度，根据式（8）计算得到目标用户ui对于历史微博Ri的兴趣度；

Step6：利用式（12）的兴趣度模型，求得目标用户ui对于待推荐微博集Rj的兴趣度，从高到低排序，选取前N条微博对用户进行推荐。

3实验结果与分析

3.1实验数据与相关工具

本文实验数据采集于新浪微博，实验利用爬虫技术、调用新浪微博提供的API接口，采集500名用户发布的所有历史微博数据，同时采集除其他用户发布的1000条微博数据作为实验数据集。将采集到的微博数据进行预处理，去除微博文本中无用数据URL、表情符号等。分词工具为Python中文分词组件jieba。统计发现大部分的用户标签为名词，本文选取分词后的名词，利用上文1.1中的方法生成用户标签。实验数据集被随机分为训练集和测试集，其中750条微博数据作为训练集，250条微博数据作为测试集。开发坏境为Spyder，开发语言为Python。

3.2评价指标

指标在最终为用户推荐的N条微博中，包含目标用户发过的微博条数，所以准确率（Precision）和召回率（Recall）两个指标可以用于评价算法的优劣，公式为：

Precision=推荐微博是用户自身发布的微博个数推荐的微博个数N

Recall=推荐微博是自身发布的微博个数用户自身发布的微博总个数

3.3实验结果和分析

微博用户在浏览微博时，通常只会对排在前面的微博感兴趣，所以研究排名较前的微博更有实际意义。本文重点测试Top-3、Top-7、Top-11、Top-15四种情况下微博推荐的性能。为了验证本文算法的有效性，在同等数据集的基础上，与传统的协同过滤推荐算法（CF）、基于标签的协同过滤算法（TCF）[3]和基于用户标签的微博推荐算法（TR）[7]进行对比实验，对比实验结果如图2、图3所示。

由图2和图3的结果可以看出，本文提出的TCFA算法与传统的协同过滤算法（CF），以及融合标签的协同过滤算法（TCF）和基于用户标签的微博推荐算法（TR）相比，准确率及召回率都有提高，在N=7时，准确率是最高的，所以在利用本文推荐算法给用户推荐微博时，选择N=7进行推荐。传统协同过滤算法存在数据稀疏的问题，融合标签的协同过滤算法虽然改善了微博推荐的数据稀疏问题，但还存在冷启动的问题。本文提出的TCFA算法不仅改善了数据稀疏问题，也较好地解决了冷启动问题，提高了微博推荐结果的准确性，证明了本文算法的有效性。

4结语

本文在传统协同过滤推荐算法的基础上，引入蚁群算法和标签，设计实现融合标签和蚁群的协同过滤微博推荐算法（TCFA）。该算法利用标签在用户和微博资源之间建立桥梁，标签作为两者的纽带，将用户-标签-微博资源的三维关系分解成两个用户-标签和标签-微博资源的二维关系，再计算两者关联度。利用蚁群目标用户进行用户聚类，根据标签相同个数多的用户兴趣也会相似的特征，为目标用户聚类产生待推荐微博集，最后利用协同过滤推荐算法进行推荐，最终得到TOP-N个微博推荐集。一方面该算法降低了数据稀疏性问题，引入标签和蚁群算法缓解了新用户得不到微博推荐的冷启动问题，然后再利用相似度计算，提高微博推荐的准确率。实验结果表明，TCFA算法的准確率及召回率都有提高。该算法虽然改善了数据稀疏和冷启动问题，但在今后的工作中，冷启动问题和数据稀疏问题仍然是研究的重点，核心问题是用户在没有相关操作时如何提高推荐算法的准确率。在用户没有相应标签的情况下，标签提取的准确度也会对推荐结果产生影响，因此下一步需要重点研究如何提高标签的质量，以提高推荐性能；另外，针对目前日益增长的大量数据，考虑到推荐的实时性，可尝试将本文提出的算法在分布式平台上实现，提高推荐系统的实时性和可扩展性。

参考文献：

[1]张怡文，岳丽华.基于共同用户和相似标签的好友推荐方法[J].计算机应用，2013，33（8）：2273-2275.

[2]王宁宁，鲁燃，王智昊，等.基于用户标签的微博推荐算法[J].计算机应用研究，2017，34（1）：58-61.

[3]蔡强，韩东梅.基于标签和协同过滤的个性化资源推荐[J].计算机科学，2014，41（1）：69-71.

[4]郭彩云，王会进.改进的基于标签的协同过滤算法[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]吴月萍，王娜，马良.基于蚁群算法的协同过滤推荐系统的研究[J].计算机技术与发展，2011，21（10）：73-76.

[9]硕良勋，柴变芳，张新东.基于改进最近邻的协同过滤推荐算法[J].计算机工程与应用，2015，51（5）：137-141.

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

[11]李鹏，王斌，石志伟，等.Tag-Textrank_一种基于tag的网页关键词抽取方法[J].计算机研究与发展，2012，49（11）：2344-2351.

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

[13]刘健，张琨，陈旋.基于标签和协同过滤的个性化推荐算法[J].计算机与现代化，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相似度和位置行为的协同过滤推荐算法[J].计算机科学，2016，43（12）：200-205.

（责任编辑：江艳）