判别大作业-一种基于向量空间模型和类别特征提取的Web新闻自动分类方法

1、一种基于向量空间模型和类别特征提取的Web新闻自动分类方法王某某（北京航空航天大学 计算机学院 北京 100191）作者简介：王某某，北京航空航天大学研究生 邮箱：bnuwjx。摘 要：互联网时代，网络信息呈几何级数激增，对Web新闻的分类提出了更高的要求，即要求能够快速、准确地对Web新闻进行分类。本文通过改进tf-idf算法，提出了一种基于向量空间模型和类别特征提取的文本分类方法，并对Web新闻进行了两级类目（5个一级类目，36个二级类目）分类；通过多次测试，确定了类别特征提取的最佳维度，通过降低新闻关键词向量的维度，一定程度上改善了交叉类别的分类效果，从而实现Web新闻的高效自动分类；最

2、后，通过交叉验证法对分类的效果进行了评价，结果表明本方法在一级类目的分类上有较高的准确率（平均准确率为86.92%），而在二级类目的分类上效果不够理想（平均准确率为58.58%）。关键词：文本分类 向量空间模型 特征提取 中文分词 余弦相似度一、研究背景随着国际互联网的高速发展，网络信息呈几何级数激增，CNNIC在其2015年1月发布的第35次中国互联网络发展状况统计报告中显示：截至2014年12月，中国网站数量已达到335万个，年增长率为4.6%；中国网页已达到1899 亿个，年增长率为 26.6%1。如何将海量的网页信息进行合理的组织，从而帮助网络用户更好的利用互联网资源，是一个亟待解决的

3、问题。在网页信息中，有一类非常重要的信息，那就是Web新闻。随着信息存储技术和网络通信技术的飞速发展，互联网已经成为人们获取新闻信息的重要渠道2，同时也已成为最为方便的渠道。当今社会的每时每刻都会出现大量的新闻，这对用户选择自己喜欢的或有价值的新闻造成了困难，因此必须对新闻进行合理的分类。但基于网络新闻信息量大，杂乱无章的特点2，传统的人工分类方式，不仅耗费大量的人力和金钱，同时也需要大量的时间。因此有必要借助技术手段来解决新闻分类的问题，以提高工作效率3，文本分类技术应运而生。所谓文本分类技术，就是机器学习人工事先制定的规则，再根据规则对给定的文本进行自动的归类。目前已有的文本分类方法基本都

4、是采用基于词语为特征项的向量空间模型4。向量空间模型就是通过选择若干带有权重的关键词构成的向量来表示一篇文章的主要内容，但是它有一个最大的缺陷，就是向量的维度难以控制，有的文章可能需要用成百上千的关键词表示，有的文章可能只需要几十个甚至几个关键词就能被概括。文本向量的高维度容易导致数据稀疏、数据噪音等问题，致使文本分类效果较差。因此，在文本分类前，有必要对文本的原始特征进行降维处理4。关于向量降维的方法，潘正高等人4在他们的论文中运行了一些常用的算法，并在此基础上提出了基于命名实体的降维方法。下文由如下几部分构成：第二部分介绍了本次研究的数据集，包括新闻来源、新闻特征项以及训练集和测试集的选取

5、方法；第三部分介绍了新闻文本向量化的过程，主要包括中文分词、设置词权重、选择关键词构成新闻关键词向量；第四部分详细介绍了类别特征提取的方法：在改进的tf-idf算法的基础上，不断修改类别特征的维度，结合测试结果确定最佳维度；第五部分介绍了一级类目和二级类目的分类方法及测试结果，并通过降低文本关键词的维度改善了交叉类别的分类效果；第六部分介绍了本次研究的创新及不足之处；最后在第七部分对未来的研究加以展望。二、数据集1 数据来源本次研究选定了中新网5 IT、财经、教育、军事、娱乐等5个一级类目以及这5个一级类目下总计36个二级类目（各个一级类目以及二级类目的信息见表1），通过编写java网页爬虫抓

6、取新闻，在每个二级类目下最多各抓取500条，抓取新闻的数据项包括新闻标题、新闻内容、新闻发布时间、一级类目、二级类目、编辑、网址，最终共抓取到新闻15951条。（抓取部分结果见表2，每类新闻数量统计见表1）。表 1 中新网一、二级类目下样本抓取数量表表 2 IT类样本抓取部分结果示例2 训练集和测试集的选取本研究通过交叉验证法来评价分类结果，为此现将数据集分为训练集和测试集。训练集是用来训练（构建）模型的数据集，测试集则是在模型构建结束后用来测试模型性能的数据集。训练集和测试集共同构成了数据集。本次研究在每个二级类目下随机选取80%的新闻作为测试集，剩余20%的新闻作为测试集。在完成新闻自动分

7、类之后，通过交叉验证方法对分类效果进行评价。 三、新闻文本向量化文本额分类不同于简单的数字分类，需要先对文本进行预处理，将文本转化为数字向量。为了能够完成类别特征提取以及后期的新闻自动分类，首要的工作就是将新闻文本转化为由带有权重的关键词构成的向量，也就是文本处理领域常用的向量空间模型。文本向量化一般包含如下三个步骤：1、中文分词（包括文本分词、去除停用词、替换同义词等）；2、设置词权重，合并关键词；3、选择带权重的关键词，构成文本向量。1 中文分词本次研究采用国内最好的中文分词系统ICTCLAS，ICTCLAS 是中国科学院计算技术研究所经过多年探索研究后所开发的一个汉语词法分析系统，分词精

8、度达到98.45%2；该系统还允许用户导入外部词典，以进一步提高分词的准确性。我们在java程序中导入官方的ICTCLAS包，并导入自己建立的词典、同义词表和停用词表，对新闻的标题和正文进行了分词，部分标题最终分词结果如表3所示： 表 3 样本标题分词结果示例2 设置词权重并合并关键词对于新闻来讲，能够表达新闻内容的关键词来自新闻标题和正文，但是来自标题和正文的词的重要程度是不同的。标题是一篇新闻的眼睛，是决定读者是否阅读一条新闻的重要依据，很明显标题中的词语更为重要，因此需要对标题中的词语和正文中的词语设置不同的权重。本次研究将标题中词语的权重设为1.0，将正文中词语的权重设为0.1，这样的

9、设置方法或许不一定合理，但是可以通过多次更改权值，对比每次更改权值后的测试结果确定一个较优的分配方式。在对词语设置不同的权值后，需要合并来自标题和来自正文的关键词，合并的方法就是将同一关键词的各个权值相加，例如关键词“手机”在标题出现2次，在正文出现10次，那么手机的最终权重就是2*1.0+10*0.1=3.0。3 选择关键词，构成文本向量有关研究表明，30%的关键词就足以有效地代表文本6，在文本关键词很多的情况下，可以采用这样的方法有效地降低向量的维度数。在新闻文本中，关键词的数量不是很多，为此我们保留所有关键词，按照关键词权重进行降序排序，最终每篇新闻可以用如下形式表示：ITemi=k1,

10、w1,k2,w2,kj,wj,(km,wm)其中，ITemi表示第i篇新闻，kj,wj中kj表示该新闻的第j个关键词，wj表示第j个关键词的权重，部分新闻向量化结果如下（对于关键词较多的样本，只列举出了比重前九位的部分）：表 4 部分样本新闻向量化结果四、类别特征提取 目前常用的分类算法有支持向量机、贝叶斯算法和KNN算法等，其中KNN算法以其简单、有效的特性被广泛使用4。KNN算法的主要思想就是计算训练集中每篇文本与待分类文本的相似度，选取与待分类文本最为相似的前K篇文本，根据这K篇文本的类别判断待分类文本所属的类别。这里可以看出KNN算法的一个不足之处：每一篇待分类的文本都需要与训练集中的

11、每篇文本进行相似度计算，这样的做法计算量大，增加了时间成本，为此本文提出一种提取类别特征的方法，能够有效地将时间成本转移到线下，从而保证分类的性能。总体来说，这种类别特征提取方法操作过程如下：首先根据类别下已有文本的特点，抽取出部分能够用来代表该类别文本的带有权重的关键词，构成特定类别新闻的类别特征向量。对于一篇待分类的新闻，只需要将新闻文本向量与每个类别的类别特征向量进行相似度计算即可，类别特征提取的过程虽然耗时，但是可以离线进行，因此既保证了新闻分类的效率，又保证了新闻分类的性能。在选取能够表示类别特征的关键词的时候，我们采用了在信息检索领域非常有效的tf-idf算法，这里首先简要介绍tf

12、-idf算法。tf-idf算法是一种统计方法，用来评估某个词汇对于一篇文本的表达能力。其中tf值=（该词汇在该文本中出现的次数）/（该文本词汇总数），用以表示该词汇在文本中出现的频率，tf值越高说明该词对这篇文本重要性越大；idf值表示逆文本频率，代表了词汇区分文本的能力，之所以引入idf值，是因为单单采用tf值并不能用来表示一篇文本，例如在所有的文本中，“的”字出现的频率最高，但是虚词“的”在多数语境下却是没有意义的。idf值=（出现该词汇的文本数/文本总数）。最终的idf值就是tf值与idf值的乘积，我们可以看出，tf-idf值具有去掉一般词汇，保留特定文本重要词汇的能力。1 改进tf-i

13、df算法传统的tf-idf算法用于表示词汇对于某特定文本的重要程度，我们可以将这样的概念借鉴到词汇对特定类别的重要程度中，改进的tf-idf算法就是用来选出那些对于特定类别比较重要的关键词。在词汇对特定类别重要程度中，tf值我们用c_tf表示，idf值我们用c_idf表示。对于c_tf值，我们定义如下计算公式：c_tfi=wiw其中，c_tfi表示某类中关键词ki的tf值，wi表示该类中每篇文章中关键词ki的权重wi之和，w表示该类中所有关键词的权重之和。对于c_tf值，我们定义如下计算公式：c_idfi=c_tfic_tf其中，c_idfi表示某类中关键词ki的idf值，c_tf表示每个类中

14、关键词ki的tf值之和。相比传统的tf-idf值，这里的c_tfi的定义没有太大变化，只不过把词数之比换成了词权重之和的比，加入了词权重的影响。而tf-idf值相比传统计算公式有较大改动。试想这样一种情况：A词和B词在文章1中出现的频率相同且较大；A词在其它文章中出现的频率很大，B词在其他文章中都只出现1次。按照原有的方法，在文章1中，A词和B词的tf-idf值将会是一样的，而显然A词表达文章1的重要程度不及B词。而通过我们重新定义的方法，这种问题则可以得到有效改善。部分关键词在所有一级类目中的tf-idf值如下：表 5 部分关键词在五个一级类目中的tf-idf值 对于某个一级类目下的关键词在

15、每个二级类目中tf-idf的值可以用同样的方法算出，这里不再赘述。2 选择类别特征关键词由于每个类别下都有几千个关键词，类别特征向量维度较高，容易造成数据噪音等问题，因此降低关键词向量的维度迫在眉睫。一个最直接的方法就是根据前面计算的tf-idf值进行筛选。在实际操作中，我们分别测试了下列几种情况得到的类别特征的分类效果，以此确定了类别特征提取的最佳维度：考虑所有的关键词构成类别特征向量；考虑以tf-idf值大于0.0001的关键词构成的类别特征向量；考虑以tf-idf值大于0.001的关键词构成的类别特征向量；考虑以tf-idf值大于0.01的关键词构成的类别特征向量；考虑以tf-idf值大

16、于0.05的关键词构成的类别特征向量。五、距离判别及分类结果本文采用距离判别法对新闻进行自动分类。在实际分类的时候，需要计算待分类项与各个类别之间的距离，常用的距离有欧氏距离，马氏距离等7。在计算新闻文本向量与类别特征向量的相似度时，我们采用在文本领域广泛运用、且被证明是有效的余弦相似度方法。具体来说，就是将待分类的新闻文本向量与每个类别特征向量进行相似度的计算，把新闻分给与之相似度最大的类别。通过比较待分类新闻原始类别和模型预测的类别来评价分类效果。例如两篇文本U和V，其中U的关键词向量为：U=ku1,wu1,ku2,wu2,kuj,wuj,(kum,wum)而V 的关键词向量为：V=kv1

17、,wv1,kv2,wv2,kvj,wvj,(kvm,wvm)那么U和V的余弦相似度可以由如下公式计算：Sim(U,V)=kuKVwui*wvi|UW|*|VW|其中，Sim(U,V)表示U和V的余弦相似度，分子表示U和V共有的那部分关键词的权重的乘积之和，分母表示U和V各自权重的模的乘积。由于各个关键词的权重非负，因此余弦相似度一定在0,1之间，Sim(U,V)值越大表示二者越相似，值越小表示二者越不相似。1 一级类目自动分类在一级类目分类中，我们将测试集中的每一条新闻向量与5个一级类目的特征向量进行余弦相似度计算，把新闻分至与之余弦相似度最大（也就是距离最小）的一级类目，分类结果及准确率如下

18、表所示：表 6 新闻分类结果及准确率（一级类目）上表中，第1列和第1行表示待分类的大类，第2列表示对应大类中待分类新闻的数量，中间的数字表示该行对应大类下的新闻有多少被分到该列对应的大类，最后一列则表示分类的正确率。例如第2行表示IT类有新闻415条，其中307条分到了IT类，92条分到了财经类，IT类新闻的分类正确率为73.98%。由表中可以看出，娱乐类新闻的正确率最高，达到了96.12%。此外我们分别测试了前面介绍的5种不同关键词阈值的类别特征提取方法，得到了各个情况下一级类目分类的平均正确率，测试结果如下： 图 1不同类别特征提取阈值下的分类平均准确率可以看出，整体分类准确率达到87%，

19、而且类别特征提取的阈值可以设定为0.0001，这样大大降低了类别特征关键词向量的维度（大约减少了60%的关键词），并且分类正确率也没有明显变化。具体从每个大类的分类效果看，IT类的分类正确率最差，只有74%左右。究其原因，我们发现原本属于IT类的文本中，有一小部分分给了财经类，出现这样的结果是因为IT类和财经类有部分内容交叉。在IT事业中，部分内容会与财经事业紧密联系，这样的类别我们称为交叉类别，交叉类别严重影响了分类准确率。通过不断测试，我们发现这样的问题可以通过降低待分类新闻文本向量的维度加以改善。我们分别按照100%，30%，20%，10%，5%，4%，3%，2%的比例从原始关键词向量中

20、选取关键词作为新闻文本向量的关键词，计算了每种情况下的IT大类下分类的正确率，各种情况下分类正确率变化的折线图如下：图 2 各新闻向量维度下IT类分类正确率可以发现，随着关键词维度数量的降低，分类正确率不断提高，在相对于原始3%的关键词时分类正确率最高，达到83.13%；而后分类正确率又随着关键词数量减少而降低。因此，当某类别的分类效果不是很好的时候，可以适当降低新闻关键词向量的维度，以降低数据噪音对分类效果的影响。2 二级类目自动分类在对一级类目进行分类测试后，我们认为类别关键词的最佳阈值可以设为0.0001，因此在二级类目分类中，我们首先用在类别特征中关键词权重超过0.0001的关键词构成

21、类别特征向量，并且只测试了在此类别特征向量的情况下各个二级类目的推荐效果，测试结果如下图所示：图 3 各一级类目下二级类目分类正确率可以看出，二级类目分类的正确率不足一级类目，评价只有58.57%。这主要是因为相对于一级类目来说，同一个一级类目下的二级类目间相似度比较高，不易区分，尤其是财经类下的二级类目之间相似度很大，给机器的自动分类造成了困难。同样我们减少新闻文本向量的维度，发现在关键词比例为10%的时候分类的正确率最高，不过也仅仅提高了1-2%。可能的解决方法是提高idf值的权重，因为idf值能够反映词区分类别的能力。在前面的研究中，我们得到idf值直接使用tf值*idf值，那么是不是增

22、加idf值在tf-idf中的权重可以改善这种在类别相似度较高的情况下分类效果呢？由于本次研究使用的计算机性能不足，每更改一次tf-idf值所带来的时间成本较大，鉴于时间因素，这种猜想只能留到以后加以验证。六、创新与不足1 创新本项研究的创新之处如下：在前人研究的基础上，提出了一种不同于KNN分类算法的、基于类别特征提取的分类方法，该方法的优点就是将传统KNN算法的时间成本转移到线下，大大提高了新闻分类的效率；通过降低新闻关键词向量的维度，一定程度上提高了交叉类别的分类正确率；自行抓取中新网上已有分类体系下最新的新闻作为数据集，保证了数据的可靠性与新颖性；相比已有的研究，增加了对二级类目的分类测

23、试。2 不足考虑到时间的限制，未能够对新闻标题和正文的权重进行多次设置；同时也未能够对tf值和idf值进行不同权重的分配。因此大类分类正确率以及交叉类别的分类效果都还有一定的改进空间。由于和已有研究在数据集上不一致，加之时间的限制，未能够将本次研究所提出的分类方法与已有方法进行比较，从而难以衡量本次研究是否提高新闻自动分类的效果。七、结束语本文在文本分类领域经典的向量空间模型的基础上，改进了tf-idf算法，提出了类别关键词提取的方法，将传统分类方法的时间成本转移到线下，保证了分类的性能。最后通过降低新闻文本向量维度的方法，一定程度上改善了交叉类别的分类效果。我们将来的研究将主要集中在以下几点

24、：进一步改善本文研究的不足之处；除了考虑新闻的标题和正文，我们将结合新闻的时间、人物以及词位置等特征加以深入研究。希望能为Web新闻自动分类乃至更为复杂的网页信息自动分类做出自己应有的贡献。参考文献1 中国互联网络信息中心. 中国互联网络发展状况统计报告 EB/OL. 2015-3-18. 2 沈加. 基于SVM模型的新闻分类系统设计与实现D.电子科技大学,20133 周远阳. 基于朴素贝叶斯方法的新闻分类系统的实现D.暨南大学,20124 潘正高,侯传宇,谈成访. 基于命名实体的Web新闻文本分类方法J. 合肥工业大学学报(自然科学版),2011,08:1178-11825 中国新闻社. 中国新闻网 EB/OL. 2015-3-18. http:/www.chinA6 魏程,刘鲁,翟铭. 一种四维向量空间模型的Web新闻文本分类方法J. 微计算机应用,2010,03:58-627 孙海燕, 周梦, 李卫国, 冯伟. 数理统计M. 北京航空航天大学出版社, 2016An automatic classification for Web-News based on Vector Space Model and Categ