基于信息增益的中文网页SVM分类研究

,

(上海师范大学 信息与机电工程学院, 上海 200234)

0 引 言

随着互联网信息的迅猛发展,对海量信息进行有效组织和分类整理显得日益重要,而传统的人工分类方式已经变得几乎不可能,网页文本自动分类突显重要作用.文本分类是把未知文档归为已知类别中的一个或多个.目前,绝大多数文本分类模型采用空间向量形式表示文本文档,即文档向量由若干无序的词或词组形式特征项组成,但是,这些特征项的向量维数往往过高或者代表性不强,从而导致分类运算开销大、准确率低等缺点.所以特征降维方法的优劣成为影响文本分类效果好坏的关键因素.

一般的特征降维方法是从源文档特征集中抽取出对分类贡献大且具有代表性的特征项,本文作者结合词性过滤和同义词归并处理技术对特征项进行第一次降维处理.然后,选择有效特征选择方法对特征项进行二次处理,文献[1]指出目前比较成熟的特征选择方法包括文档频率法(DF)、信息增益法(IG)、互信息法(MI)和X2统计法(CHI)等等.文献[2]表明,在英文测试集上信息增益和CHI的效果最优,认真分析了传统信息增益方法的不足并对其做出改进,最后在传统信息增益基础上提出特征加权方法选择特征项.之后根据支持向量机(SVM)分类算法对包含特征项的中文网页文档集进行文本分类.目前,SVM分类算法被公认为是文本分类效果中比较好的一种文本分类方法.本文作者将通过理论分析和实验途径来对比中文网页文本分类中此方法改进前后分类效果.

1 特征降维方法

1.1 词性过滤

待归类的文档往往采用特征项向量形式表示,最基本的方法是把文档中所有词或词组作为特征项构成特征空间,然而文本中包含的词或词组的数量一般较庞大,如果将所有词或词组作为特征项则向量维数往往过高而导致数据稀疏[3]和计算量巨大等问题,这些问题会明显加大文本分类的时间和空间复杂度，从而降低文本分类效率.所以如何在不影响分类精度和效果的同时，尽量控制向量的维数成为一个重要问题,文献[4]表明文本分类预处理时词性选择非常重要.考虑到汉语当中很多词性表现力不强或并无实际意义,假如去掉这些字词不仅不会影响分类效果反而缩短了分类时间,所以选择在文本预处理时对特征项进行词性过滤.

1.2 同义词归并处理

传统特征降维方法仅仅基于统计学而忽略了特征项之间蕴含的语义关联.汉语词义丰富、表达多元,不同词语之间往往包含相同或相似的内在联系,比如“比赛”和“竞赛”属于相同语义关系,“科技”和“高科技”属于相关语义关系等等,所以作者将同一文档中出现的若干同义词进行归并降维处理.《哈工大信息检索研究室同义词词林扩展版》(http://www.ir-lab.org/)在《同义词词林》[5]原有3层分类体系基础上细分类增加2层最终得到5层分类体系,共收词53,859条,同时提供5层编码.其中词分为大、中、小3类,大类有12个,中类有97个,小类有1,400个.每个小类里都有很多词或词组,这些词或词组根据词义远近和相关性分成若干个词群(段落).每个段落中词语又进一步分成若干行,同一行词语或词义相同(有的词义十分接近),或词义有很强相关性.

表1 文档集特征项同义词归并处理示例

结合以上两者方法的特征降维步骤如下:

(1) 采用中科院分词工具(ICTCLAS)进行切词和词性标注,然后仅选择汉语中的名词、动词和形容词以及中英文缩写词等较具代表性的词性建立词性过滤表,将通过词性过滤表处理后的词项组成文档特征项.

(2) 完成步骤(1)后,进一步采用《哈工大信息检索研究室同义词词林扩展版》词典对词项进行同义词归并处理,即将具有相同字典编码的词项文档频率进行加权合并,如表1所示.

如表1所示,文档集中文本经过分词后的“科技”和“科学”两个词语分别为“科技/n/Dk03”和“科学/n/Dk03”,此两个词语的后缀字典编码相同,则归为相同词项,假如给定文本类别Ci,文档集D和特征项t及其同义词s,其相关文档频率概率公式如下:

(1)

(2)

(3)

(4)

2 改进的信息增益公式

2.1 传统信息增益公式

1850年,熵由物理学家克劳修斯提出,用来表示一种能量在空间中分布的均匀程度,其中能量分布越均匀越不确定熵就越大.1948年,信息论之父Shannon将熵应用于信息处理并提出了“信息熵”概念.

文献[6]指出信息熵被描述为信息量的不确定程度度量.如果设X为随机变量,那么描述它不确定程度的信息熵[6]被定义如下:

(5)

通过观察随机变量Y后获得的X的不确定程度描述为条件熵[6],定义为:

H(X|Y)=-∑xyp(xy)logp(x|y) .

(6)

信息增益为两者熵之差,表示为消除不确定程度后获得的信息量,定义为:

IG(X)=H(X)-H(X|Y) .

(7)

在文本分类领域,把类别C看成一个符合某种概率分布的信息源,则根据文档类别C的信息熵和是否存在特征项T后的条件熵的差值可以确定该特征项T的贡献的信息量,即特征项T的信息增益.所以传统的信息增益计算公式[7]如下:

(8)

2.2 传统信息增益的改进

观察公式(8)发现传统信息增益方法根据特征的文本数考察了特征对整个系统的分类贡献.所以在不同类中分布相同或相近的特征项信息增益最小,即在所有类中都分布均匀的特征项对系统贡献最低,这说明该方法特别适合用来做全局的特征选择,即所有的类使用相同的特征集合,但是,每一个类别都有自己的特征集合,特别是只在1个类内，分布比较均匀的特征项往往对此类具有更好的代表性和区分能力.为了提高分类精度,尝试弥补和改进传统信息增益方法.

(9)

使用归一化的特征项t的平均偏差平方来近似表示方差D(t),代入公式(9),则有公式为:

(10)

如果特征项t在某类文档中分布越均匀则D(t)越小,相应的就越大.所以本文选择使用加权因子D(t)来改进特征项t的信息增益权重.

结合1.2节中同义词归并处理算法,将公式(1)～(4)带入公式(8),再结合特征项加权公式(10),得到改进信息增益公式如下:

(11)

3 SVM分类算法

在特征提取后将选择采用SVM分类算法来测试特征降维方法和改进的信息增益方法对文本分类效果的影响.当前较为著名的文本分类算法包括支持向量机(SVM),K近邻法(KNN),朴素贝叶斯法(NB),神经网络法(NNet),线性最小二乘法(LLSF)等.其中支持向量机(SVM)算法凭借其理论和实践上的优势被广泛应用于文本分类领域.

1963年,支持向量机[7](SVM)由Vapnik等人提出并应用于函数模拟、模式识别和数据分类等领域,其方法建立在统计学的VC维理论和结构风险最小原理基础之上,具体实现思想是通过内积函数定义的非线性变换把输入向量映射到一个高维特征空间,然后在这个空间中构造最优超平面来进行文本分类.其中文本分类效果的好坏取决于核函数是否择优选择.常用的核函数[8]包括以下4种:

(1) 线性核函数:

(12)

(2) 多项式核函数:

(13)

(3) 径向基(RBF)核函数:

K(xi,xj)=exp(-γ||Xi-Xj||2),γ>0 .

(14)

(4) Sigmoid核函数:

(15)

其中γ,r和d都是核函数参数.文献[9]和文献[10]都表明针对不同的数据集选择不同的核函数会有不同的分类效果.其中文献[8]指出对于数据量偏大的文本分类选择线性核函数较好.作者将在实验部分做出对比测试和分析.

4 实验结果和分析

4.1 评估指标

评估文本分类系统好坏的2个常用指标分别为准确率(precision)和召回率(recall).其中,准确率反映了返回文档集中相关文档在所有相关文档集中所占比重,而召回率反映了有多少相关文档出现在返回文档集中.两者公式如下:

(1) 准确率(precision):

P=系统预测相关文档数/文档集中相关文档总数 .

(16)

(2) 召回率 (recall):

R=系统预测相关文档数/系统返回相关文档总数 .

(17)

准确率和召回率反映了文本分类的两个不同方面,一般情况下二者不能偏废，必须综合考虑,则釆用F-测度(F-measure)来表示准确率和召回率的调和加权平均,其公式如下:

(18)

通常情况下,取参数a为1,则得到综合考虑的评估指标F1公式如下:

(19)

4.2 实验结果与分析

从两大门户网站腾讯网(http://www.qq.com/)和新浪网(http://www.sina.com.cn/)中科技栏目和包括体育、财经、教育、军事等在内的非科技栏目爬虫下载网页文章,经过文本解析处理后选择平均长度为500～600字左右的4000篇文档作为语料库.其中选取科技和非科技各1600篇文章共3200篇文档作为训练集,并从训练集中随机抽取800篇文章作为封闭测试集,剩余800篇文章作为开放测试集.

目前,应用比较成熟的SVM分类器主要有LibSVM[9]和SVMLight两种.在本实验中采用台湾大学林智仁教授开发的LibSVM软件包进行分类测试,此软件包操作方便分类快速有效,可以解决分类问题(包括c-SVC和n-SVC)、回归问题(包括e-SVR和n-SVR)以及分布估计(one-class-SVM)等问题,作者选择此分类器工具和其提供的4个常用核函数进行文本分类实验,将经过词性过滤、同义词归并处理及特征加权和未经相关处理的信息增益方法进行封闭测试和开放测试对比,具体实验结果及分析如下:

表2 封闭测试集中不同核函数不同方法下分类测试结果

表3 开放测试集中不同核函数不同方法下分类测试结果

如表2所示,在封闭测试集中,特征降维和改进信息增益方法使文本分类准确率和召回率均有所提高,其宏平均F1值也明显优于传统信息增益方法,此外,选择线性核函数的性能最优,多项式和径向基核函数次之,Sigmoid核函数较差.事实上,词性过滤方法大大降低了文本向量空间的稀疏性和运算量,同义词归并处理和特征加权算法提高了类别区分能力,综合以上几点很大程度上提高了分类效率.由表3知,在开放测试集中,分类精度均有所下降,但是改进的信息增益方法分类准确率、召回率和F1值均有较大提高,而且线性核函数分类精度仍为最高,多项式和径向基核函数次之,Sigmoid核函数的精度最低.

综上,特征降维和改进信息增益方法使4种核函数的分类精度均有很大提高.其中,线性核函数的分类精度最优,多项式和径向基核函数次之,Sigmoid核函数的精度较差.故此实验表明使用词性过滤、同义词归并处理和特征加权算法后确实提高了中文网页分类系统的精度并且效果显著.

5 结束语

在传统信息增益基础上引入词性过滤、同义词归并处理和特征加权算法,改进了特征降维和传统信息增益方法的缺点和不足,提出并应用了特征降维和一种优化的信息增益公式(11),该公式充分考虑了同义词特征项和类内部分布均匀特征项对判别该类的重要影响,从而大大提高了中文网页分类系统的效率和精度.在下一步工作中,将考虑将此方法应用于更多的分类领域来检验它的适用性,并进一步完善此特征加权算法公式来更好地提高系统性能和分类精度.

参考文献:

[1] MANNING C D,RAGHAVAN P,SCHÜTZE H.Introduction to information retrieval[M].Cambridge:Cambridge University Press,2008.

[2] YANG Y M,PEDERSON J O.A comparative study on feature selection in text categorization[C]∥ICML′97 Proceeding of the Fourteenth International Coference on Machine Learing.San Francisco:Morgan Kaufmann Publishers Inc,1997.

[3] 张玉芳,陈小莉,熊忠阳.基于信息增益的特征词权重调整算法研究[J].计算机工程与应用,2007,43(35):159-161.

[4] 李英.基于词性选择的文本预处理方法研究[J].情报科学,2009,27(5):717-719.

[5] 梅家驹,竺一鸣,高蕴琦,等.同义词词林[M].上海:上海辞书出版社,1983.

[6] 周萌清.信息理论基础[M].北京:北京航空航天大学出版社,2002.

[7] VAPNIK V.The nature of statistical learning theory[M].New York:springer,1999.

[8] CHANG C C,LIN C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology (TIST),2011,2(3):27.

[9] 贾泂,梁久祯.基于支持向量机的中文网页自动分类[J].计算机工程,2005,31(10):145-147

[10] 张国梁,肖超锋.基于 SVM 新闻文本分类的研究[J].电子技术,2011,38(8):16-17.