研究与开发现代计算机2015.09中文章编号：1007-1423（2015）26-0036-04DOI：10.3969/j.issn.1007-1423.2015.26.009基于聚类的网络新闻热点发现研究万晓霞，赵佳（西华大学计算机与软件工程学院，成都610039)摘要：随着互联网的迅速发展，网络已成为各大媒体发布新闻和人们获取信息的主要渠道。而网络新闻复杂多样，并不是每一条新闻都是人们关注的热点。为了快速准确地获得用户关注的热点事件，提出将三种聚类算法相结合的话题发现算法和热度计算公式，并通过实验验证利用上述方法进行热点发现的可行性。关键词：热点事件；聚类算法；热度计算；可行性0引言在互联网技术飞速发展的今天，人们获取新闻信息的形式已不再仅限于传统的单一媒体，如报纸、电视，网络已成为各大媒体发布信息的主要渠道。但各大新闻门户网站每天都会发布各种报道，导致网络信息繁杂无序，并且不是每一个事件都是值得网民关注。因此，如何快速准确地从浩瀚的网络信息中挖掘出热点事件，让人们更好地了解和回顾历史事件，是一个值得探讨的问题。新闻热点事件的发现常用聚类的方法实现，如今，已有许多学者做出了大量的研究，如提出了基于层次聚类的网络新闻热点发现[1]和基于二次聚类的新闻推荐方法[2]，但单一的层次聚类方法由于计算量过大，会导致网络新闻这种大数据集的计算速度较慢，其他方法也需要人为设定初值，可能导致聚类结果的不准确。鉴于以上原因，本文提出了将三种聚类算法相结合的话题发现算法，并通过实验证明此方法能更准确地发现一年的网络新闻热点事件。1聚类算法研究1.1相关聚类算法简介聚类是一个无监督的学习过程，它可以将数据集里相似性较高的对象划分为一类，最终使得同组对象相似，而不同组对象则相异。聚类算法有划分聚类、层次聚类以及增量聚类等。划分聚类首先是要选定初始聚类中心，然后将剩下的数据划分到与之最近的聚类中心中去，使得在同一个子集中的点尽可能的相似。K-means是划分聚类算法中比较经典的算法。层次聚类算法是将所有的样本点自底向上合并成一棵树或者自顶向下分裂成一棵树的过程，最终达到预期的类簇或其他的终止条件，这两种方法分别称为凝聚和分裂。而增量聚类的其中一类是利用上一次聚类的结果,每次将一个数据点划分到已有簇中,即新增的数据点被划入中心离它最近的簇中并将中心移向新增的数据点,也就是说新增的数据点不会影响原有划分。1.2三种聚类算法相结合的提出网络新闻热点的发现过程从本质上讲是一个聚类的过程，一个热点事件通常会有很多的报道，并且报道的时间可能会持续很长。因此，如何选择高效且能准确地将大量的新闻报道中相同的事件聚集在一起，不同的事件区分出来是本研究的一个重要任务。根据对多种聚类算法的比较分析，我们将三种聚类算法共同用于本系统的研究，选择层次聚类对每天的新闻网页进行聚类得出微类，再选择K-means聚类算法对每月的微类进行聚类，最后将每个月的事件通过增量聚类得趦趷

研究与开发现代计算机2015.09中出一年的热点新闻事件。2网络新闻热点发现系统2.1系统思想与框架本文的目的主要是对一年的网络新闻报道进行话题发现的研究，通过聚类得出一年里网络上报道的较受关注的新闻，最后通过热点计算公式得出它们的热度，进而得出一年的热点事件。因此，如果直接对一年的新闻报道数据进行处理无疑会增加处理过程的复杂性，为了提高热点事件发现的精确性，降低系统的时间复杂度，本文利用分而治之的思想，将一年的新闻报道分为12个月分别存储，每个月的新闻又按每天的新闻进行存储，先对每一天的新闻报道进行话题发现，即进行凝聚聚类，找出每天的微类，再将每个月里的微类进行K-means聚类，最后将12个月里的话题类簇进行增量聚类，得出一年的话题新闻，并通过热点计算公式筛选和排序，得到一年的热点事件。系统的整体流程框架如图1所示。图1系统流程图2.2新闻网页预处理新闻网页是一种非结构化的数据类型，因此我们必须将其转化为结构化的数据类型才能被计算机所处理。首先将下载的网页通过分词软件进行切词、去除停用词以及词性的标注，接着我们将采用常用的向量空间模型（VSM）对新闻文档进行向量表示，这是通过计算机编程对新闻网页进行聚类处理的前提条件。每一个新闻文本d表示成如下所示的向量形式：V（d）=（t1，w1（d）；t2，w2（d）；…ti，wi（d）；tn，wn（d））（1）其中，ti为新闻文档的特征项，wi为特征项在文档d中所占的权值。对于特征项权值的计算，本文采用经典的TF-IDF算法，计算公式如下：W=tf×idf（2）2.3聚类算法的结合设计算法对于每日的网络新闻而言，我们无法预料究竟有多少话题数量，所以如果用给定聚类数K值的聚类算法可能会由于经验不足导致聚类结果偏差较大，因此我们将采用凝聚聚类算法并通过对阈值的控制来确定算法终止的条件，进而得出每日的话题簇。每日话题簇数量得出之后，通过求出一个月内每日话题簇的平均值，将之作为第二步使用K-means进行每月话题聚类的初始聚类数目，并选择K个话题簇中文档数较多的类簇作为初始聚类中心，进行每月话题簇的聚类发现。最后用增量聚类的算法得出一年的话题类簇。每日话题聚类和每月话题聚类的具体算法步骤如下所示：（1）每日话题凝聚聚类算法输入：包含n个数据的单日新闻数据集D，聚类终止条件阈值M输出：K个聚类后的话题簇①将每个对象作为一类，共n类②计算两两之间的相似度③找出相似度最大的两类并合并，并对它们重新进行表示④重新计算新类与其它类之间的相似度⑤重复③和④，UNTIL达到聚类终止条件⑥输出K个话题簇（2）每月话题凝聚聚类算法输入：第一次聚类后一个月的话题簇数据集D1输出：K个聚类后的话题簇①计算出一个月内每日的话题数均值K②从D1中选取出K个文档数最多的话题簇作为初始的聚类中心③分别计算D1中其他样本点与各中心的距离④将样本点划入与之距离最小的聚类中心簇中⑤更新中心对象⑥重复③-⑤⑦UNTIL聚类中心不再发生变化且所有的类均被划分完⑧输出一个月的K个话题簇2.4事件热度的计算一个事件要成为热点事件，则还需对它们进行热度的度量。热点事件必然也是新闻媒体报道的比较多，
   K-means  











!"趦趹

研究与开发现代计算机2015.09中
  





!"#$%#&’()*+,-./012*+34,-./0,565789:;<=>&’(?@ABCDEFGHIJKLMNOPQ?@ABCDERSTUV-WXYZZ[\]^_‘abcadKefghijkTlmLnopqrstuvwxyS
.z{jkGHI|V 而且受关注度也较高的事件，根据这个思路，本文首先找出能度量热点事件的特征量，然后总结出公式对热点事件进行热度的计算。由于我们要得出的是一年的热点事件，那么事件在一年内的报道数量越多或者其报道的天数越多，其热度便会越高。我们将一年的天数定义为D，一年中的事件报道总数为N，而该事件的报道总天数定义为d，报道篇数为n。其热度R的计算公式如下：Ri=dD×nN（3）3实验与分析3.1实验数据来源与处理本实验使用网络爬虫从腾讯、新浪、网易三个门户网站上下载了从2014年1月1日到2014年12月31日的国内国际社会新闻网页，总计162510篇。由于网页数目庞大，并且具有时序的特点，故将这一年的新闻按月份存储在12个文件夹里，每个文件夹里再将每天的网页分别存储。3.2系统的实现步骤根据系统的整体框架流程图，我们进行实验的步骤如下：①对每天的网页数据用分词软件进行分词、去除停用词和词性标记等的处理；②对文档的特征项进行权值的计算，并进行向量表示；③对每天的网页数据进行自底向上的凝聚聚类，通过相似度阈值确定聚类终止条件，并选取类簇中文档数大于某一阈值的话题类参与下一层的聚类；④求出每天的平均话题类数K，并选取K个文档数较多的类，将之作为K-means聚类的初始中心，对每月的话题类进行二次聚类；⑤将每月的话题类用增量聚类的方法再次聚类得出一年的事件列表；⑥根据热点计算公式求得热点事件排序。3.3实验结果对比分析为了验证本文的方法对新闻热点事件发现的可行性与准确性，将本实验的结果通过与网上发布的由数亿网民评选的十大社会热点事件进行对比，对比结果如表1所示：表1实验对比结果根据表1可以得出，本文的实验结果中有5个与网民评选结果相同，说明了本实验聚类算法发现热点事件的可行性。之所以选择用网民评选的结果作为对比，是因为热点事件必然也是网民比较关注的事件，而事件报道时间较长，篇数较多也是网民关注的条件之一，因此即使少数网民评选的结果不足为据，但数亿的网民便可让结果具有一定的说服性。但网民评选的结果毕竟还是带有一定程度的主观性，所以和本实验的实验结果会有所偏差，相比而言，本实验的结果则更加客观。4结语本文提出了将凝聚聚类算法、K-means聚类算法和增量聚类算法相结合的话题发现方法，并根据热点事件的特征提出了事件的热度计算公式，最后通过进行实验和结果对比验证了本研究方法的可行性与准确性。本文的不足之处是热点计算公式提的较为简单，计算中未加入用户的评论数，因此在以后的研究中可考虑加入这个因素，以提高热点事件排名的精确度。趦趻

研究与开发现代计算机2015.09中
  





!"#$%#&’()*+,-./012*+34,-./0,565789:;<=>&’(?@ABCDEFGHIJKLMNOPQ?@ABCDERSTUV-WXYZZ[\]^_‘abcadKefghijkTlmLnopqrstuvwxyS
.z{jkGHI|V ResearchonNetworkNewsHotDiscoveryBasedontheClusteringWANXiao-xia，ZHAOJia（SchoolofComputerandSoftwareEngineering，XihuaUniversity,Chengdu610039）Abstract：WiththerapiddevelopmentoftheInternet,thenetworkhasbecomethemainchannelformediatoreleasenewsandthepeopletoobtaininformation.However,thenetworknewsiscomplexanddiverse,noteverypieceofnewsisthefocusofattention.Inordertoquicklyandaccuratelyobtainhoteventsthatusersconcerned,presentsatopicdetectionalgorithmwhichcombinesthreekindsofclusteringalgo-rithmsandaheatcalculationformula.Andthroughtheexperiment,weverifythefeasibilityofusingtheabovemethodsforhotfound.Keywords：HotEvent;ClusteringAlgorithms;HeatCalculation;Feasibility参考文献：[1]彭楠赟，王厚峰，凌晨添.基于层次聚类的网络新闻热点发现.中国计算语言学研究前沿进展（2009-2011），2011.[2]古万荣，董守斌，何锦潮，曾之肇.基于二次聚类的新闻推荐方法[J].华南理工大学学报（自然科学版），2014,7.[3]刘星星，何婷婷，龚海军，陈龙.网络热点事件发现系统的设计[J].中文信息学报，2008,11.作者简介：万晓霞（1989-），女，四川泸州人，硕士研究生，研究方向为计算机网络与信息安全系统赵佳（1992-），女，四川成都人，硕士研究生，研究方向为计算机网络与信息安全系统收稿日期：2015-07-16修稿日期：2015-08-15趦趽