新闻文本的筛选问题本质上可以归结为文本的二类分类问题，但同传统的文本分类相比而言又有着明显的差异性。一是文本类间界限的不明确性，即分类的标准是由人为确定的所谓新闻价值决定；二是随着信息产业的发展，尤其是Internet的爆炸式增长，需要分析的新闻数据呈现海量性特点，传统的文本分类算法如KNN、SVM、贝叶斯等，在计算性能上已经难以达到要求。
本研究课题选取信息检索领域经典的Rocchio算法，并对其进行了基于MapReduce编程模型的并行设计。使其能满足在大数据的时代背景下及时的将新闻进行分类，发掘出其中有价值的信息，满足网站对新闻时效性的要求。
2.1基于改进TF-IDF算法的特征选择方法
TF-IDF算法是信息检索领域内常用的特征表示方法。其基本思想为，若某词条在某一文档中出现的词频TF(TermFrequency)较高，但包含此词条的文档较少，即词条的文档频率DF(DocumentFrequency)较低，则认为此词条具有很好的类别区分能力，应赋予较高权重。即：
，(1)
其中IDF(InverseDocumentFrequency)表示倒文档频率。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)
2.2相似度算法
文本Doci在经过分词、去停词后，通过上文所述的TF-IDF方法算出权重wij并提取特征[2]，便可以表示为向量空间模型(VectorSpacemodel,VSM)的形式，形成文本向量，形如：
此处n、m分别表示文档数与词空间的维度。若采用余弦相似度，则Doci与Docj本文相似度simij为：
，(6)
2.3Rocchio算法
Rocchio算法是一种基于类中心向量分类方法，其思想在于通过总括实例对每个类别的贡献而得到的泛化实例（GeneralizedInstances），即所谓的类中心向量作为模型来进行分类[3]。因此这种算法相对于KNN等其他分类算法而言高效而易于实现。虽然在分类精度上一般不及其他算法，但非常适合只有两类的分类问题，即区分A与~A的问题，因而特别适用于信息的过滤[4]。
对于类中心向量的训练，设初始状态时，类别Ci的中心向量ci的每一维度的权值都是0，则类别向量ci的第j维的权值cij为：
，(7)
其中wij为文本向量di第j维的特征权值，C为文本总体，k为迭代次数。典型情况下，，，
2.4MapReduce编程模型
MapReduce模型[5-9]是Google公司率先提出的一种分布式编程模型，专用于大规模数据集的分布式计算。此后Apache基金会又推出开源MapReduce编程框架Hadoop。。
MapReduce的处理过程如下图所示：
图1MapReduce的工作流程图
Fig.1TheworkflowdiagramofMapReduce
MapReduce将分布式运算抽象成Map和Reduce两个主要步骤。在MapReduce中，数据是以
三、基于MapReduce的Rocchio算法
3.1基于MapReduce的文档词频统计算法
输入数据的格式如表1所示：
Map过程：先将文档D解析为文档编号ID、文档内容C、文档属性A三部分，再把内容分词去噪，最后把得到的词条作为value输出，把词条所属的<文档号,属性>对作为key输出。伪代码如下：
Input:D
Output:
(1)(ID,C,A)=parse(D)
(2)T=segment(C)
(3)forterminTdo
(4)key=make_pair(ID,A)
(5)value=term
(6)output(key,value)
Reduce过程：Map的结果输入到Reduce过程之前，相同key的value会被合并在一起，形成
Input:
(1)forterminvalue_listdo
(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，
然后将之前得到的文本权重结果映射到特征词空间上，就可得到文本的特征向量，即为：
由公式(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
(1)(ID,wD)=parse(VD)
(2)value=ID
(3)sR=cos_similarity(wD,cR)
(4)sNR=cos_similarity(wD,cNR)
(5)ifsR>sNRthen
(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.2Singlefeedbacktomultiplefeedback
Reduce过程：同样，在Map过程和Reduce过程之间，相同key的
(1)fordocinvalue_listdo
(2)list.add(doc)
(3)values=list
(4)output(key,value)
经过以上算法处理，就可得到最后的分类结果如下：
四、实验及分析
4.1实验方案
实验环境采用分布式计算平台Hadoop(版本0.20.2)，共有6个节点，每个节点的配置：CUP为4核3.2GHz，4GB内存，500GB硬盘，千兆网卡，操作系统为Ubuntu11.04。
，(9)
，(10)
，(11)
，(12)
4.2实验结果分析及与传统算法对比
由以上两表可以得到在不同规模集群的条件下MR-Rocchio算法与各算法的加速比如图3所示。其中SR表示加速比，N为集群节点数量。
图3MR-Rocchio算法与KNN、SVM、Rocchio的加速比变化图
Fig.3Trendlinesofspeed-upratioofMR-RocchiowithKNN,SVM,Rocchio
五、结语
参考文献
[1]张玉芳,彭时名,吕佳.基于文本分类TFIDF方法的改进与应用.计算机工程,2006,32(19)：76-78．
[2]张海龙,王莲芝.自动文本分类特征选择方法研究.计算机工程与设计,2006,27(20)：3838–3841
[3]张治国.中文文本分类反馈学习研究[D].西安:西安电子科技大学,2009
[4]刘培德,刘玉国,刘培玉.网络信息过滤系统的设计与实现.计算机工程与应用,2005(21)：156—158．
[5]RLmmel.Google’smapreduceprogrammingmodel—revisited.ScienceofComputerProgramming70(1)(2008)1–30.
[6]Y.Liu,Z.Hu,K.Matsuzaki.Towardssystematicparallelprogrammingovermapreduce.Euro-Par2011ParallelProcessing,PartII,Vol.6853ofLNCS,Springer,2011:39-50.
[7]J.Dean,S.Ghemawat.Mapreduce:simplifieddataprocessingonlargeclusters.CommunicationsoftheACM,2008,51:107–113.
[8]C.Buckley,G.Salton,J.Allan.Theeffectofaddingrelevanceinformationinarelevancefeedbackenvironment,InternationalACMSIGIRConference,1994:292-300.
[9]T.White.Hadoop:TheDefinitiveGuide.O’ReillyMedia,2009.