关于新闻推荐算法的研究

李乐田，吴林，高永存

(中国传媒大学 理学院，北京 100024)



关于新闻推荐算法的研究

李乐田，吴林，高永存

(中国传媒大学 理学院，北京 100024)

随着互联网高速发展，越来越多的网友依赖于手机、PC获取外界讯息。其中较为广泛关注的当属新闻阅读，用户对新闻推荐的要求也越来越高，除了各大网站推出的头条外，不同用户渴望读到的新闻千差万别，那么如何更好的满足用户对新闻的个性需求就成为新闻推荐的一个难题，本文使用1000名用户的新闻阅读记录，挖掘用户的阅读习惯，发现用户阅读下一条新闻只与上一条有关，而与之前的行为无关，故本文使用马尔可夫算法对这一问题进行研究。

马尔可夫模型；新闻推荐；关联规则；数据挖掘

1　引言

信息时代万物千变万化，人们追求便捷的步伐刻不容缓，大数据随之而生，与之同时，针对大数据的软硬件创新层出不穷，先有阿里旗下的淘宝购物，极大方便了用户购物，后将其算法优化，对用户推荐有可能需要的商品，又极大的提高了淘宝日营业额。后电子地图、软件打车、电子外卖等陆续推出，无疑是给人们的高效生活增光添彩。在这样纷扰的社会中，读书看报的人越来越少，一个手机、一个电脑就能走天下，读书看报均能通过电子浏览器实现，方便又快捷。方式的改变并不影响生活的内容，人们还是会大量阅读新闻，了解时事热点话题，那么问题来了，新闻网站如何能提高用户的阅读效率呢？我们就此问题研发出了一个新闻推荐算法。

通过大量的前期工作，挖掘出用户的阅读习惯，发现用户阅读下一条新闻只与上一条有关，而与之前的行为无关，这刚好符合一阶马尔可夫过程，马尔科夫算法具有无后效性，即将来的取值只与现在的取值有关而与之前的无关，故本文用马尔可夫算法作为主算法结合其他算法对用户阅读新闻进行个性化推荐。

2　论文背景与数据集描述

大数据问题近两年成为信息技术学术界和产业界热论的焦点，普遍舆论认为，大数据问题已经成为信息科学技术领域的重要前沿课题之一。[1]

信息时代万物变化，大数据的重要性已经成为行业共识，针对大数据技术和应用的创新，其发展势不可挡。如何对大数据进行充分和有效的分析和挖掘，使之转换为有价值的信息和知识，用于解决各种各样的科学和应用问题，成为大数据时代信息技术发展的重大挑战，同时也是信息技术创新的制高点。[1]

2.1论文背景

基于某大数据竞赛中的数据，从国内某新闻网上随机选取的若干名用户于2014年3月的新闻浏览记录，每条记录包括用户编号、新闻编号、浏览时间(精确到秒)以及新闻文本内容。

随着近年来互联网的飞速发展，个性化推荐已成为各大主流网站的一项必不可少服务。提供各类新闻的门户网站是互联网上的传统服务，但是与当今蓬勃发展的电子商务网站相比，新闻的个性化推荐服务水平仍存在较大差距。一个互联网用户可能不会在线购物，但是绝大部分的互联网用户都会在线阅读新闻。因此资讯类网站的用户覆盖面更广，如果能够更好的挖掘用户的潜在兴趣并进行相应的新闻推荐，就能够产生更大的社会和经济价值。初步研究发现，同一个用户浏览的不同新闻的内容之间会存在一定的相似性和关联性，物理世界完全不相关的用户也有可能拥有类似的新闻浏览兴趣。[2]此外，用户浏览新闻的兴趣也会随着时间的变化而变化，这给推荐系统带来了新的机会和挑战。因此，希望通过对带有时间标记的用户浏览行为和新闻文本内容进行分析，挖掘用户的新闻浏览模式和变化规律，设计及时、准确的推荐系统预测用户未来可能感兴趣的新闻。

2.2本文数据集与研究问题阐述

我从国内某著新闻网站—财新网随机选取了10000名用户，并抽取了这10000名用户在2014年3月的所有新闻浏览记录，每条记录包括用户编号、新闻编号、浏览时间(精确到秒)以及新闻文本内容。本研究的目的是尽可能准确地预测每个用户浏览的最后一条新闻(这条新闻之前曾被其他用户浏览过)，该数据用于评判算法最后成绩。每个用户最后一条浏览记录之前的的所有新闻浏览记录和新闻文本数据，作为训练集以供算法分析和建模使用。研究问题需要根据训练集中的浏览记录以及新闻的详细内容，尽可能多的预测出测试集中的数据，即预测每一个用户最后一次浏览的新闻编号。预测的准确程度将成为量化的评价指标。

3　本问题国内研究现状

研究问题“对新闻浏览推荐的算法”要求尽可能准确地预测每个用户浏览的最后一条新闻。当前比较经典的主流推荐系统主要包含三类。基于内容的推荐算法，主要分析文本等内容来寻找相似文本，然而协同过滤推荐算法则是寻找相似用户，根据相似用户具有的相似兴趣进行推荐。混合推荐方法，试图平衡上述两种方法的有点和缺点，扬长避短。除此上述三种之外，常见的推荐算法还有基于规则的推荐算法和基于图的推荐算法。

我们的工作是以马尔科夫模型为基础。首先，我们提出了通过衰减窗口来弥补一阶马尔科夫模型巨大的时间和空间需求，减少计算量。第二，通过信任度修剪训练集中得到的较弱规则。第三，在修剪之后的强规则基础上，来修剪每个用户的状态空间。这样我们不仅提高了预测准确度和召回率，还大大减少了计算的时间和空间消耗。

以马尔科夫链作为主算法，计算用户对此算法的适应度作为优化方式，适应度优化算法核心思想即尽可能删除错误数据，从而在稳定准确率的同时，提高召回率。研究问题是删除用户访问记录的最后一条作为数据集，适应度算法删除用户访问的倒数第二条新闻作为数据集进行计算。例如，推测出的倒数第二条新闻与真实数据不符则认为该用户不适用于此算法，故不用此算法进行新闻推荐，以此类推至倒数第五条作为阀值和评分标准，去除所有新闻完全预测错误的用户，用此算法将f值提高到了34.654%。

4　算法分析

在这一章里，将会介绍我们的工作里关于马尔科夫模型的相关背景知识。

4.1马尔科夫链

针对上述算法中遇到的问题，我认为加强推荐关联性才是提高推荐准确度的关键。为了加强关联性，我不再进行用户的关联，而是转为进行新闻的关联。对此我引用马尔科夫链的概念。

人们常把事物的随机变化过程称作马尔可夫过程。它具有无后效性，即事物的将来呈什么状态、取什么值，仅与它现在的状态和取值有关，与它以前的状态和取值无关。马尔可夫链则是事物在连续一段时期内若干马尔可夫过程的总称，表明事物状态由过去到现在、由现在到将来，一环接一环，像一根链条。在预测领域，人们用其对预测对象各个状态的初始分布和各状态间的转移概率进行研究，描述状态的变化趋势，并由此来预测未来。[3]

设随机过程{X(t)，t∈T}的状态空间为I。如果对时间t的任意n个数值t1

X(tn-1)=xn-1下X(tn)的条件分布函数，即

P{X(tn)≤xn|X(t1)=x1，X(t2)=x2，···X(tn-1)=xn-1}=P{X(tn)≤xn|X(tn-1)=xn-1}，xn∈R，

由于许多用户的新闻阅读数目有限，直接限制了链长的长度，所以我从三阶马尔科夫链开始，作为尝试。提取某用户最后三条新闻ID，然后在所有用户中寻找阅读过这三条新闻，并且相互紧邻的用户，统计其下一条新闻，进行推荐投票操作，获得票数最高的新闻，在一定票数阈值限制下可以进入推荐名单。票数相同的新闻可以采用全部推介或者取新闻ID号最大者，或者随机取值的方案。

4.2相似用户推荐

为了针对用户的行为模式进行分析，为每个用户寻找与其浏览行为较为相似的用户作为参照，并将相似用户中原用户未浏览的新闻根据一定的原则选取进行推荐。

先要针对每名用户选取相似用户，相似用户的选取主要是以用户浏览新闻的相似度为基础的，在权衡计算机的计算效率与结果可用度的前提下，初步将相似度选取的阈值定为相似性新闻数在原用户中不不低于50%，在对应用户中不低于50%。相似用户选取后，每个用户都有与其对应的若干相似用户，根据相似程度与新闻相关数据可以进行推荐指数的排序。

recommend_indexnews

此方法得到的结果较上一种方法有了提升，f值在0.11～0.12之间，准确率约在15%左右，召回率再10%左右，经过对阈值的详细调整，结果再次得到提高，不过这样的结果显然并不算好。

沙门氏菌、志贺氏菌、金黄色葡萄球菌、单核细胞增生李氏特菌、蜡样芽胞杆菌、铜绿假单胞菌、阪奇肠杆菌、致泻性大肠埃希氏菌8种致病菌的监测检验。

经过对数据的再次研究与讨论，我发现数据中有很多的浏览记录为重复浏览，即同一用户多次浏览同一条新闻，这样的记录为数不少，推测此类记录出现的原因大致是因为网络刷新、误操作等原因导致，所以并不能对其直接删除，另新闻记录不全的条目因为类似原因同样不能删除。

同时此次的算法虽然不再基于新闻内容，但在用户关联的处理仍旧未做到密切关联，导致很多误导新闻被导入且无法推荐重复新闻(依靠此方法关联用户)，导致准确率偏低。但此方法在经济预测上可取得一定的效果。

4.3.APRIORI算法

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。其原本被应用于预测超市购物商品摆放顺序，通过提炼大量用户选择的各种不同商品的数据，进行关联，最终找到各商品间的关联方式。但目前该算法已经被广泛的应用到商业、网络安全等各个领域。

需要注意的是，在规则概率为1的情况下，对于用户未知购物行为的预测是最有利的。但是在此模型下，概率为1的规则必须舍弃。将阈值设置为0.7，支持度设置为139所获得的规则为3000多条。对用户历史记录中的新闻条数与规则中的新闻条数差不超过2，则可以用此条规则预测用户的下一次行为。用此算法得到的结果f值约为8.6%。

4.4基于内容的协同过滤算法

此处我使用基于item的协同过滤，通过用户对不同item的评分来评测item之间的相似性，基于item之间的相似性做出推荐。[6]

协同过滤算法首先根据所有相似用户新闻浏览行为对某个用户浏览的新闻进行打分，形成评分矩阵。基于各用户浏览新闻的分数用改进的余弦公式计算用户之间的相似度。统计相似用户范围内，统计浏览次数最高的前50条新闻。根据用户相似度乘以评分矩阵中新闻分数计算出前50条新闻的推荐分数，选择此分数最高的新闻作为推荐新闻。用此算法得到的结果f值约为16.2%。

4.5算法综合

考虑到各种算法的局限性以及正确率，我综合考虑上述优化过主算法与辅算法，将辅算法中待选集交集以外的部分在主算法中加以排除，再将所有辅算法的交集并入主算法待选集之中，得到最终结果。用集合论表示，其公式为：

O=(AIBIC)Y[D-D

I[A-AIB-AIC+AIBIC

+B-BIA-BIC+AIBIC

+C-CIA-CIB+AIBIC]]

用韦恩图具体表示如下，其中阴影部分即为最终提交的结果集。使用SPSS软件实现的最终结果f值为34.940%。

图1　结果集韦恩图　

4.6算法实验

步骤1：分别对用户操作：设用户浏览本条新闻、点击浏览相关新闻、浏览其他新闻、评论新闻、分享新闻、五个动作分别为S1，S2，···S5，用户在Si状态

(1)

步骤2：记所有用户五个状态概率ai，(i=1，2，...，5)，为初始状态，根据初始状态概率向量和转移矩阵，对以后用户动作进行预测，下一次这五个动作概率将变为：

(2)

步骤3：重复步骤(1)、(2)，经过n次计算，求得稳定状态下a(n)，则a(n)表示五个动作用户选择的概率。

步骤4：计算

(3)

bij表示用户由动作i转为执行动作j的概率，从中可得到每个用户下一步可能的动作。

步骤5：综合(1)(2)(3)对用户可能进行的下一步操作给出两个预测。

用这种方法，我进行了二阶和一阶马尔科夫链的尝试。其中，一阶马尔科夫链的f值在不同的票数的条件下，效果优于二阶、三阶的结果，基本能保持在f值29%之上的成绩。在票数为20的条件下，达到了31.787%的效果。二阶和三阶马尔科夫链的效果略次于之。其算法流图如下。

图2　主算法流图 　

4.7评价标准

本实验采用召回率和准确率来评价实验结果，定义如下：

(4)

其中U为要推荐的用户的集合，表示推荐给用户的新闻中，确实在测试集中被此用户浏览的个数。由于本次试验每个用户在测试集中只有一条记录，所以的值为0或1。表示推荐给用户的推荐列表长度。

(5)

其中为测试集中用户真正浏览的新闻数目，在我们的测试环境中，等于推荐的用户总数。

5　结束语

本研究良好的迎合了当前信息业发展的趋势，为浏览其用户提供了个性化的新闻推荐，从而提高用户浏览体验。论文中使用了一种简单易懂但却卓有成效的主算法——马尔可夫算法，结合适应度优化算法并综合各种辅算法，在良好的预测f值的基础上进一步拔高，获得了优异的推荐结果，并对不同的算法作了尝试和总结，找出更适合本问题的推荐算法，当然，一定还存在着更准确的推荐算法，这些算法及其思想在其本质上是有着扎实数学与概率学基础的，潜力无穷，在未来的数据挖掘应用中必将呈现其价值，为商业经济提供技术支持与保障。相信在又一代数据研究者的开发与推动之下，大数据时代将提高人们的生产及生活体验，促进生产力与效率的提升，福荫后世。

[1]黄哲学，曹付元，李俊杰.面向大数据的海云数据系统关键技术研究[J].网络新媒体技术，2012，1(6)：20-26.

[2]B Yang，P F Zhao. Recommendation algorithm overview[J].Journal of Shanxi University (Nat Sci Ed)，2011，34(3)：337-350.

[3]F Abel，N Henze，D Krause. Exploiting additional Context for Graph-based Tag Recommendations in Folksonomy System[J].2008 IEEE/WIC/ACM International Conference on Web Intelligence an Intelligent Agent Technology，2008：148-154.

[4]盛骤，谢式千，潘承毅.概率论与数理统计[M].高等教育出版社，1979，319-320.

[5]S Bin，L Page. The anatomy of a large-scale hypertext web search engine[J].In：Seventh International World-Wide Web Conference (WWW 1998)，April 14-18，1998.

[6]J M Kleinberg. Authoritative sources in a hyperlink environment[J].Journal of the ACM，1999，46(5)：604-632.

(责任编辑：马玉凤)

Study on Recommendation Algorithm News

LI Le-tian，WU Lin，GAO Yong-cun

(School of Science，Communication University of China，Beijing 100024)

With the rapid development of the Internet，more and more users intend to rely on mobile phones，PC access to get external information. The news reading has got more widespread attention，the users’ requirements of the news recommendation are increasingly high. In addition to the headlines of the websites，different users have different need and interest of different topics. Therefore，it has been a difficulty to satisfy the individual eager of the users. By studying on the record of 1000 users and mining the user’s reading habits，this paper found that users read the news related to the last one，has nothing to do with the previous behavior. So we use Markov Model study on this issue.

markov model；news recommended；association rules；data mining

2015-09-27

李乐田(1991-)，女(汉族)，山西大同人，中国传媒大学研究生.E-mail：liletian@cuc.edu.cn

O29

A

1673-4793(2016)01-0040-05