大数据背景下新闻筛选的分布式算法研究

一、研究题目现实意义

    随着时代的发展，网络上的信息呈现爆炸式的增长，门户网站的新闻媒体已经不再是互联网内容的主要来源，各种社交平台，微博，论坛等每天都会产生海量的信息。在大量的信息中及时，有效的提取出有价值的信息便成为了各大新闻网站所面对的首要问题。人民网作为国际互联网上最大的综合性网络媒体之一，一直致力于及时发布有价值的信息，对信息时效性的要求也越来越高，在某一个版面将最具价值的信息及时的展现给用户也成为了网站的必然要求，如何快速的筛选新闻文本也成为了网站亟待解决的问题。

    新闻文本的筛选问题本质上可以归结为文本的二类分类问题，但同传统的文本分类相比而言又有着明显的差异性。一是文本类间界限的不明确性，即分类的标准是由人为确定的所谓新闻价值决定；二是随着信息产业的发展，尤其是Internet的爆炸式增长，需要分析的新闻数据呈现海量性特点，传统的文本分类算法如KNN、SVM、贝叶斯等，在计算性能上已经难以达到要求。

    本研究课题选取信息检索领域经典的Rocchio算法，并对其进行了基于MapReduce编程模型的并行设计。使其能满足在大数据的时代背景下及时的将新闻进行分类，发掘出其中有价值的信息，满足网站对新闻时效性的要求。

二 、相关技术介绍

2.1基于改进TF-IDF算法的特征选择方法

    TF-IDF算法是信息检索领域内常用的特征表示方法。其基本思想为，若某词条在某一文档中出现的词频TF(Term Frequency)较高，但包含此词条的文档较少，即词条的文档频率DF(Document Frequency)较低，则认为此词条具有很好的类别区分能力，应赋予较高权重。即：

， (1)

    其中IDF(Inverse Document Frequency)表示倒文档频率。TF和IDF的基本定义如下：

， (2)

， (3)

    式中，freqij表示第i个词在第j篇文档中出现的次数，Maxfreqj表示第j篇文档中频度最高的词出现的次数；N为总文档数，ni为包含第i个词的文档数。

    但这种传统的TF-IDF算法在应用于文本分类时存在不足。实际上，若某词条在一个类别文档中频繁出现，则说明该词条能够很好代表这个类的的特征，应赋予较高的权重。故张玉芳等[1]提出一种针对文本分类的改进TF-IDF算法，改进了IDF公式，即对于某一类文本C，IDF为：

， (4)

    其中，mci为某类C中包含第i个词的文档数。如果除C类外，包含第i个词条的文档数为ki，则公式变为：

， (5)

    从公式中可以看出IDFi的值与mci正相关，与ki负相关。因此，以上公式可以体现出这种改进思想。

2.2相似度算法

    文本Doci在经过分词、去停词后，通过上文所述的TF-IDF方法算出权重wij并提取特征[2]，便可以表示为向量空间模型(Vector Space model, VSM)的形式，形成文本向量，形如：

 

    此处n、m分别表示文档数与词空间的维度。若采用余弦相似度，则Doci与Docj本文相似度simij为：

， (6)

2.3 Rocchio算法

    Rocchio算法是一种基于类中心向量分类方法，其思想在于通过总括实例对每个类别的贡献而得到的泛化实例（Generalized Instances），即所谓的类中心向量作为模型来进行分类[3] 。因此这种算法相对于KNN等其他分类算法而言高效而易于实现。虽然在分类精度上一般不及其他算法，但非常适合只有两类的分类问题，即区分A与~A的问题，因而特别适用于信息的过滤[4]。

    对于类中心向量的训练，设初始状态时，类别Ci的中心向量ci的每一维度的权值都是0，则类别向量ci的第j维的权值cij为：

， (7)

其中wij为文本向量di第j维的特征权值，C为文本总体，k为迭代次数。典型情况下，，，

2.4 MapReduce编程模型

MapReduce模型[5-9]是Google公司率先提出的一种分布式编程模型，专用于大规模数据集的分布式计算。此后Apache基金会又推出开源MapReduce编程框架Hadoop。。

MapReduce的处理过程如下图所示：

          图 1 MapReduce的工作流程图

    Fig.1 The workflow diagram of MapReduce

 

    MapReduce将分布式运算抽象成Map和Reduce两个主要步骤。在MapReduce中，数据是以<key, value>的形式存在的。Map步骤负责将输入的<key, value>进行处理后生成同样形为<key, value>的中间结果。中间结果根据key值的不同经过Combine、Sort、Shuffle过程将数据按相同的key合并为<key, list[value]>分发到不同的节点进行Reduce操作。Reduce步骤则将所有分发过来的中间结果根据Key进行合并以及处理，最后生成最终的处理结果。

    在整个处理过程中，开发者不需要关心任何有关底层分布式处理的事情，只需要关注自己的Map和Reduce函数逻辑即可。这极大简化了并行计算的实现过程，并使开发者将更多的精力放到问题本身。

三、基于MapReduce的Rocchio算法

3.1基于MapReduce的文档词频统计算法

    输入数据的格式如表1所示：

 

其中文档属性用来区分文本是属于相关类、非相关类还是待分类，分别用R、NR、Non相应表示。

Map过程：先将文档D解析为文档编号ID、文档内容C、文档属性A三部分，再把内容分词去噪，最后把得到的词条作为value输出，把词条所属的<文档号,属性>对作为key输出。伪代码如下：

Input: D

Output: <key, value>

(1) (ID, C, A) = parse(D)

(2) T = segment(C)

(3) for term in T do

(4) key = make_pair(ID, A)

(5) value = term

(6) output(key, value)

Reduce过程：Map的结果输入到Reduce过程之前，相同key的value会被合并在一起，形成<key, value_list>，然后对每一个key统计其value_list中不同value（此时的value即为词条term）的频数，最后key原样作为Reduce的key输出，其对应value_list中不同的value和其频数作为Reduce的value输出。伪代码如下：

Input: <key, value_list >

Output: <key, value>

(1) for term in value_list do

(2) freq = count(term, value_list)

(3) list.add( make_pair(term, freq))

(4) value = list

(5) output(key, value)

最后得到如下数据形式：

 

3.2训练阶段

    对训练数据集应用2.1所述基于MapReduce的文档词频统计算法，得出针对每一文档的词频统计结果。然后根据1.1所述的基于改进TF-IDF算法的特征选择方法，计算出每个文档中每个词的权重wij，然后取权重最大的前K个词作为此文档的特征词合并所有文档的特征词，组成特征词空间，即为VSM的维度空间，记为V，

    然后将之前得到的文本权重结果映射到特征词空间上，就可得到文本的特征向量，即为：

    其中，Ai的值为R或NR。将以上的结果带入公式(7)中，并令，，，可得出相关类的类中心向量cR和非相关类的类中心向量cNR，即：

由公式(7)可知，

3.3分类阶段

    对待分类数据集应用2.1所述基于MapReduce的文档词频统计算法，得出针对每一文档的词频统计结果。然后算出每一文档在特征词空间V上的权值，得到：

    其中Non表明以上文本都是待分类。分类过程主要集中在Map阶段，以目标文档与类中心向量的距离为依据，并且在分类过程中通过公式(8)不断更新类中心向量，以达到反馈的效果。

(8)

    其中ci为第i类的类中心向量，wi是刚分为第i类的文档向量，a、b为反馈系数，且a + b = 1。

    Map过程：将上述处理过的待分类文本向量VD解析为文档号ID，文档的特征向量wD = (w1,w2, … ,wm)，然后依据上述基于类中心向量cR、cNR分类与反馈机制进行分类，最后将文档号作为value输出，文档所属类别作为key输出。伪代码如下：

Input: VD, cR, cNR

Output: <key, value>

(1) (ID, wD ) = parse(VD)

(2) value = ID

(3) sR = cos_similarity(wD , cR)

(4) sNR = cos_similarity (wD , cNR)

(5) if sR > sNR then

(6) key = “R”

(7) cR = a *cR + b * wD

(8) else

(9) key = “NR”

(10) cNR = a * cNR + b* wD

(11) output(key, value)

上述算法将原来的单一反馈变为分布式的多反馈，如图2，因而可以有效平摊误差，提高准确度。

图 2 单一反馈到多反馈

Fig.2 Single feedback to multiple feedback

Reduce过程：同样，在Map过程和Reduce过程之间，相同key的<key, value>对合并，成为<key, value_list>，将其稍加处理原样输出即可。伪代码如下：

Input: <key, value_list>

Output: <key, value>

(1) for doc in value_list do

(2) list.add(doc)

(3) values = list

(4) output(key, value)

经过以上算法处理，就可得到最后的分类结果如下：

四、实验及分析

4.1实验方案

    实验将从对新闻文本处理的准确率和速度两个方面来着手，通过将基于MapReduce的Rocchio相关反馈算法与传统的Rocchio算法、KNN算法和SVM算法作对比，来验证本文所提出算法的性能。

    实验环境采用分布式计算平台Hadoop(版本0.20.2)，共有6个节点，每个节点的配置：CUP为4核3.2GHz，4GB内存，500GB硬盘，千兆网卡，操作系统为Ubuntu 11.04。

 实验数据集为网上收集到的海量信息文本。数据集共包含文本61800条，新闻相关类样本1400条，新闻非相关类样本60400条，每条文本的数据格式如表2所示。抽取其信息并转化为表1所示的格式。其中表2的编号为表1的文档编号，表2的标题、表述、网页内容作为表1的文档内容，表1的文档属性则按文档的性质相应标注。

    实验指标包括召回率(Recall)、查准率(Precision)、F1值和加速比(Speed-up Ratio)。令N表示总的新闻文本集合，C0表示实际的新闻相关类集合，C1为实际新闻非相关类集合，D0表示被判别的新闻相关类集合，D1表示被判别的新闻非相关类集合，T0为改进前的分类时间，T1为改进后的分类时间。则有：

， (9)

， (10)

， (11)

， (12)

4.2实验结果分析及与传统算法对比

    将基于MapReduce的Rocchio相关反馈算法（以下简称为MR-Rocchio算法）与传统的Rocchio算法、KNN算法和SVM算法的性能进行对比，可得到结果如表3所示 。

    然后更改集群规模，让Hadoop集群分别采用1个、2个、3个、4个、5个和6个配置相同的节点，计算MR-Rocchio算法完成上述相同的任务所用的时间，得到的结果如表4所示。

    由以上两表可以得到在不同规模集群的条件下MR-Rocchio算法与各算法的加速比如图3所示。其中SR表示加速比，N为集群节点数量。

图 3 MR-Rocchio算法与KNN、SVM、Rocchio的加速比变化图

Fig.3 Trend lines of speed-up ratio of MR-Rocchio with KNN, SVM, Rocchio

 

    由以上实验结果可以看出，在分类筛选的准确率方面基于MapReduce的Rocchio相关反馈算法相对于传统的Rocchio算法有较大提升，并且优于KNN算法，只是稍稍逊于SVM算法。但是在分类筛选的处理速度方面，基于MapReduce的Rocchio相关反馈算法充分利用了MapReduce技术在大数据处理方面的优势，执行的速度和效率远远高于其他算法，并可以在一定范围内随着集群规模的增加而不断增加。

五、结语

    新闻文本的分类筛选在新闻版块内容设置上有着重要的地位和作用，但随着信息的爆炸式增长，传统的文本分类算法在保证效果的前提下，处理速度难以达到要求。本文以Rocchoi算法为基础，进行了改进，突破在大规模新闻数据集上运行时的性能限制，解决了针对特定类别而进行的海量新闻文本的分类筛选问题。并引入MapReduce技术，利用其处理海量数据的优势，提高的算法的处理速度。研究表明，基于MapReduce的Rocchio相关反馈算法能在保证准确度的情况下大大提高系统的执行速度和效率。满足了新闻对时效性的要求，能及时的从大规模的新闻数据中筛选出有价值的新闻。

    目前，国外像雅虎这样的著名的互联网门户网站已经在基于MapReduce的技术上走在了网络传媒行业的前列，并以此取得了长足可观的连锁效应；此外像在Facebook，以及国内的网易等相关平台上也已经有了广泛的应用，未来注定是大数据进行广泛普及应用的时代，而网络新闻传媒行业也肯定会融入时代的趋势，人民网作为国内以新闻为主的大型网上信息交互平台，也是国际互联网上最大的综合性网络媒体之一，如果想在未来网络大数据时代中继续占据优势位置，基于MapReduce的Rocchio相关反馈算法将会是一大助力，并且基于MapReduce方向的其他相关的数据挖掘技术也会促进人民网业务多样性的拓展，并使人民网更加欣欣向荣。

    在大数据的时代背景下，对已有文本挖掘算法进行分布式的研究具有极强的现实意义。本文依然有需要改进之处，未来的工作重点会放在相关反馈系数a、b取值的优化以及文本特征选择的优化上。

 

参考文献

[1] 张玉芳,彭时名,吕佳. 基于文本分类TFIDF方法的改进与应用. 计算机工程, 2006, 32(19)：76-78．

[2] 张海龙,王莲芝. 自动文本分类特征选择方法研究. 计算机工程与设计, 2006, 27(20)：3838–3841

[3] 张治国. 中文文本分类反馈学习研究[D]. 西安: 西安电子科技大学, 2009

[4] 刘培德,刘玉国,刘培玉. 网络信息过滤系统的设计与实现. 计算机工程与应用, 2005(21)：156—158．

[5] R L?mmel. Google’s mapreduce programming model—revisited. Science of Computer Programming 70 (1) (2008) 1–30.

[6] Y. Liu, Z. Hu, K. Matsuzaki. Towards systematic parallel programming over mapreduce. Euro-Par 2011 Parallel Processing, Part II, Vol.6853 of LNCS, Springer, 2011: 39-50.

[7] J. Dean, S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 2008, 51: 107–113.

[8] C. Buckley,G. Salton, J. Allan. The effect of adding relevance informationin a relevance feedback environment, InternationalACM SIGIR Conference,1994: 292-300.

[9] T. White. Hadoop: The Definitive Guide. O’Reilly Media,2009.