话题监测与发现之热点新闻发现技术

标签: 发现 热点 新闻 | 发表时间:2013-01-25 09:51 | 作者:
出处:http://fufeng.iteye.com

 

最近在帮朋友做一个关于“热点新闻发现”的需求。先解释下什么是热点新闻发现:即在海量的新闻文本中,找到内容相似的那一类新闻,如果这类新闻的数量达到一定阈值,便认为该类新闻属于热点新闻。

 

其实这一类型的课题早在几年前就已经开始研究,属于TDT(Topic Detecting and Tracking话题检测与发现)分支之一,而且方法也较为成熟,多半是在文本分析的基础上利用数据挖掘中聚类知识进行处理。

 

但是,笔者遇到的这个需求较为特殊:

第一,这里的文本类型是互联网搜索引擎爬下来的“新闻”;

第二,数据量大约是10W-100W之间;

第三,需要程序单机处理,并且硬件配置和普通PC无异(双核CPU,内存4G左右);

第四,程序要求在30分钟内处理完毕;

最后,程序得到的热点新闻必须在新浪、网易、腾讯等大型门户网站上有相关新闻。

(哎,这就是小公司的悲哀,老板们总希望用最小成本获得最大收益,“又想马儿跑又想马儿不吃草”,天下哪有这等便宜事,但是谁叫他是老板,作为“码农”,还是得想尽办法去满足老板的需求。)

 

理想情况,假设硬件资源充足的情况下,大家会怎么处理?

上图为简易的传统处理流程,如果硬件资源充足,即认为内存无上限,为了达到较快的运行时间,开发者理所当然将存储在硬盘上的文本文件全部Load进内存,然后:

1)对每篇新闻进行分词:文本分析中对文本进行分词处理是每篇文本特征化的第一步;

2)文本特征化:使用这种<分词,词频>来特征化每篇文本,当然你也可以使用较为常用的TF-IDF(即词3频-逆文档率)来进行特征化;

3)聚类:当获得每篇文本特征化表示方式后,开发者可以使用层次聚类、基于密度的聚类或者比较常用的划分式聚类(比如:k-means)来进行聚类分析;

 4)过滤处理:对聚类后的所有类簇进行匹配,如果类簇中的新闻数量未达到阈值则将其过滤,否则认为该类属于热点新闻。

 

理想很美好,现实很骨感。老板给的硬件环境只是普通PC,为了不发生OOM(out of memory)的事件,这就使得开发者不可能将所有数据load至内存。是否有其他解决办法呢?也许有人想到,是不是可以采用类似外排序那种处理方式,处理一部分数据后将其结果保存至外存储,然后再处理下一步部分数据,如此循环,最后对所有结果进行归并。

 

是滴,这确实是一个好办法,即传说中的用时间换空间。但是万恶的老板要求,所有数据必须在30分钟内处理完毕,时间条件上不允许,并且传统的聚类算法处理时间随着数据量的增长往往呈非线性增长趋势,在时间上也较难满足笔者需求。

 

正像其他的数据挖掘问题一样,熟悉业务可能比会使用“牛B”的算法更为重要。为了解决上述问题,笔者对业务本身以及数据源特征进行了梳理,并总结出“某些经验”(这是基于对业务理解所产生的,可能并不一定具有普遍性,但是如果读者的业务也和笔者相似,可以举一反三试用下)形成了下述流程。


 

如图所示,与理想情况相比,新流程多了无效新闻过滤环节和二次聚类环节,并且在第一次聚类过程中特征化方式不一样,这些都是基于业务经验总结出来的,详述如下:

1) 无效新闻过滤:由于互联网上的新闻质量参差不齐以及爬虫本身的问题,所以往往会导致无效新闻的产生,笔者将其分为四类——a)新闻标题为空;b)新闻正文为空;c)新闻正文内容过短;c)新闻标题与正文内容不符。

其中,前三类过滤非常简单,只需判断是否为空或者检查字符串个数是否达标即可,而新闻标题与正文内容不符笔者是这么处理的:

       首先,将标题进行分词(分词过程中需过滤无效词);

       第二,定义同义词库,查找出分词后标题词元的同义词;

       第三,在正文中查找是否出现标题词元,如果出现的词元个数大于阈值,即认为标题与正文相符(比如,标题词元有4个,在正文中出现了3个,阈值为2,则相符);否则,再将标题词元的同义词进行匹配,如果正文中匹配的个数大于阈值,也认为标题与正文相符;否则,判定为新闻内容与标题不相符。

(Tip:其实这个匹配过程属于多字符串匹配过程,笔者选用AC算法进行处理。)

最后,即可获得有效新闻,通过此步骤,可以过滤掉大量无效新闻,优化后续处理步骤的空间和时间。

 

2) 初次聚类:在第一次聚类过程中,笔者的特征提取方式和普通文本特征提取不太一样(传统处理可能选词频或者TF-IDF作为文本特征),笔者选取每篇文本的最长句作为新闻文本特征。这是基于业务特性的经验总结,因为笔者发现互联网上的新闻发表方式多为转载,或者是在各大门户网站所发表新闻的基础上进行局部修改。在此步骤中,如果两篇文章中最长的一句话是相同的,笔者即认为它们是相似新闻。

在此步骤中,笔者将最长句作为文本特征,并采用Hashtable作为存储结构,其中key:是文本最长句,而value是具有该最长句的新闻集合。

 

3) 过滤初次聚类结果:在此步骤中,笔者设定了过滤阈值,如果某个类簇(新闻集合)中新闻数量低于阈值,则将其过滤。

当然,读者会说,此时最好不应该进行过滤,因为通过后续第二次聚类处理,某些小于阈值的类簇有可能形成一个大类簇。对,这确有可能发生,笔者之所以这么做,是在精确度和时空复杂度之间进行了取舍,如果加入此过滤步骤,将会为第二次聚类优化大量时间和空间。

 

4) 二次聚类:或许读者已发现初次聚类并不是一个十分严谨的聚类,假如两篇文本内容相似但是不拥有相同的最长句,那么它们很可能被拆分成两类新闻,而这步骤便是要解决该问题。

经过对初次聚类结果过滤后,其实此时得到的类簇数量已经远远低于最开始的新闻文本数量(笔者针对自己的数据实验,最开始时新闻文本数量有30W,经过初次聚类并过滤后将只剩下2k个类簇),此时选取每个类簇的新闻标题作为原始文本,采用理想硬件条件下的普通的聚类方式进行聚类处理,即完成了二次聚类。

(虽然普通的聚类方式会随着数据量增加时间会曾非线性增长,但是经过多次过滤处理,第二次聚类过程所处理的数据量已骤减(只有2K左右),因此可以选用该算法。)

 

5) 最后,再将二次聚类合并后的类簇进行阈值过滤,即得到热点新闻。

(TIP:在该步过滤环节中,笔者还引入了指定网站过滤——即如果某个类簇中不包含五大网站(sina/sohu/qq/ifeng/163)的新闻便将其过滤,原因是考虑到五大网站的影响力和权威性,如果连它们都没有录入新闻,我们有理由认为这类新闻很难成为热点新闻。)

 

总结一下,笔者的解题思路其实是遵循这么一个模式:为了解决时间和空间问题,需要一步一步的过滤或合并数据,但是每次在过滤或合并数据时选择的处理方式的效率一定要高,即要考虑收获与成本之间的差异,即多引入一个流程所带来的时空开销一定要远远小于后续流程所节省的时空量;其次是关于算法准确率问题,为了获得时空上的优化可能是需要牺牲算法准确率(比如初次聚类的过滤问题),笔者建议读者最好多准备几组实验数据以确定阈值,从而达到准确率和时空复杂度之间的平衡。

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [发现 热点 新闻] 推荐:

话题监测与发现之热点新闻发现技术

- - 一个只愿意做到80分的懒人
最近在帮朋友做一个关于“热点新闻发现”的需求. 先解释下什么是热点新闻发现:即在海量的新闻文本中,找到内容相似的那一类新闻,如果这类新闻的数量达到一定阈值,便认为该类新闻属于热点新闻. 其实这一类型的课题早在几年前就已经开始研究,属于TDT(Topic Detecting and Tracking话题检测与发现)分支之一,而且方法也较为成熟,多半是在文本分析的基础上利用数据挖掘中聚类知识进行处理.

限流系统如何发现系统的热点

- - 阿里中间件团队博客
限流系统是对资源调用的控制组件,主要涵盖授权、限流、降级、调用统计等功能模块. 限流系统有两个基础概念:资源和策略,对特定的资源采取不同的控制策略,起到保障应用稳定性的作用. 限流系统提供了多个默认切入点覆盖了大部分使用场景,保证对应用的低侵入性;同时也支持硬编码或者自定义aop的方式来支持特定的使用需求.

最近一周热点新闻爆笑点评 (豆瓣 我们爱讲冷笑话小组)

- lonelymc - 豆瓣: 我们爱讲冷笑话小组的讨论
新闻:外媒称意大利希望中国大量购买其国债. 点评:泱泱大国,穷的只剩下钱了. 新闻:人民日报:卡扎菲罔顾民生 丧失执政合法性. 点评:当初叫人家小甜甜,现在叫人家牛夫人,哼~. 新闻:党报对比中美物价水平 称纽约交通费是北京10倍. 点评:工资接近非洲,物价接轨欧美,税收接近欧洲,房价赶超英美,福利接近南极洲.

2010年心理学十大发现:有自信就能成功_新闻中心_新浪网

- mzhair - 牛博山寨 编辑推荐
心理”虽然看不见摸不着,却与我们的生活息息相关,它主宰着你的心情、影响你的效率,还能指点你的为人处世. 如今,对心理学感兴趣的人也越来越多了. 日前,美国《今日心理学》杂志评选出了“2010年度十大心理学发现”,我们不妨关注一下心理学界去年的“大事记”. 数字时代,电脑游戏成了很多人的休闲伙伴. 2010年3月,美国爱荷华州立大学特聘教授克雷格·安德森等人指出,有“打打杀杀”等暴力情节的游戏会让人滋生暴力倾向.

新闻还是新闻吗?

- tiger - SocialBeta
这是个很有趣的问题,在有新闻历史以来,我们一直将选择吸收资讯种类的生杀大权交在少数的新闻编辑手中,当然因为许多出类拔萃的新闻人或是媒体人的报导及故事,我们获得了许多珍贵的资讯,当时讲故事的能力还操纵在少数新闻集团手中,但这样产生了几个问题,第一,编辑们选择大部分人想看到或是应该知道的新闻,但这些不见得是我想要知道的讯息,也许也不是我认为跟我个人相关的资讯 ; 第二,什么才叫做新闻.

新闻与评论

- - 新闻跟帖局
核心提示:青海体工队要求残奥会金牌教练汪成荣上交奖金,遭拒后将其停职. 汪成荣表示,自己是代表国家比赛不是代表青海比赛,不应和其他教练一样上交奖金,并不想把事情闹大,但体工队不能给出可信服解释也只能坚持下去. 青海体育局称将在看到体工队书面材料后作出回应. 分享网易新闻《残奥金牌教练拒交奖金遭停职 称不会妥协》的精彩跟帖.

如何炮制假新闻

- 跨栏高手 - 桃花坞
Shared by 跨栏高手. 除了假新闻之外,假科学、假辟谣和真广告也比较多. 上个星期,一则“IE用户智商低于平均水平”的新闻出现在众多电视新闻和报纸上,CNN、BBC、PC World、英国的《每日电讯报》、《每日邮报》和《卫报》等都做了报道. 新闻的来源是一家加拿大的咨询公司 AptiQuant,在这家公司网站的新闻稿中称这家公司对10万名网络用户做了智商测试,发现IE用户的智商低于平均水平,其它浏览器的用户的智商则稍高于或是远高于平均水平.

如何识别假新闻?

- 策策啃鸡腿 - 左岸读书_blog
“谣言止于智者”说的是智者不会轻信传言,更不会传播谣言. 虽然有技术含量比较高的假新闻,需要费很大力气才搞清楚. 但有一些新闻,是一眼就可以看出是假的,至少,一眼就可以判断出是不可信的. 我们来把这样的“新闻”特征给捋一捋,让大家方便识别. 第一,五个“W”不全的,即WHEN、WHERE、WHO、WHAT、WHY.

如何炮制假新闻

- 着相鱼 - 桃花坞
上个星期,一则“IE用户智商低于平均水平”的新闻出现在众多电视新闻和报纸上,CNN、BBC、PC World、英国的《每日电讯报》、《每日邮报》和《卫报》等都做了报道. 新闻的来源是一家加拿大的咨询公司 AptiQuant,在这家公司网站的新闻稿中称这家公司对10万名网络用户做了智商测试,发现IE用户的智商低于平均水平,其它浏览器的用户的智商则稍高于或是远高于平均水平.