特征提取算法在KNN中的比较

丁 琼

（华东交通大学 软件学院，江西 南昌 330013）

文本分类指将文本按照其内容含义划分到不同的类型中去.自动分类的一般做法是，预先确定好文本的类别，并且对每个文本类别提供一批预先分好类的文本（称为训练文本集），分类系统通过训练文本集学习分类知识，在实际分类时，再根据学习到的分类知识为需要分类的文本确定一个或者多个文档类别.国外的自动分类研究大体上可以分为三个阶段：第一阶段（1958年－1964年）主要进行了自动分类可行性研究；第二阶段（1965年－1974年），自动分类的实验研究；第三阶段（1975年－至今），自动分类的实用化阶段.国内自动分类研究起步较晚，始于20世纪80年代初期.国内的研究基本上是在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识，然后应用于中文之上，继而形成中文文本自动分类研究体系.[1]

1 特征提取算法

在文本处理中，一些常用特征提取评估函数有文档频数（document frequency）、信息增益（information gain）、期望交叉熵（expected cross entropy）、互信息（mutual information）、χ2统计（CHI）、文本证据权（the weight of evidence for text）等.[2,3,4]

1.1 文档频数DF

它是最简单的评估函数，值为训练集合中该单词发生的文本数.DF评估函数理论假设稀有单词可能不包含有用信息，也可能太少而不足以对分类产生影响，也可能是噪音，因此可以删去.显然它在计算量上比其他评估函数小很多，但是实践运用中它的效果却很好.DF的缺点是稀有单词可能在某一类文本中并不稀有，也可能包含着重要的判断信息，错误的舍弃，可能影响分类器的精度.因此，在实际运用中一般并不直接使用DF.

1.2 信息增益（Information Gain）

信息增益表示文档中包含某一特征值时文档类的平均信息量.它定义为某一特征在文档中出现前后的信息熵之差.

1.3 互信息（Mutual Information）[5]

MI是信息论中的概念，用于衡量一个消息中两个信号之间的相互依赖程度.在特征选择领域中，文档类别c和特征f的互信息体现了特征和类别的相关程度，在某个类别中出现的概率高，而在其他类别中出现概率低的特征f将获得较高的互信息.

1.4 χ2统计[6]

统计也是表征两个变量间的相互关性，但是它比互信息更强，因为它同时考虑了特征存在和不存在时的情况.

1.5 交叉熵(Cross Entropy)[7]

交叉熵和信息增量相似，不同之处在于信息增量中同时考虑到了特征在文本中发生与不发生时的两种情况，而交叉熵只考虑特征在文本中发生一种情况.

1.6 证据权值(Weight of Evidence)

证据权值反映的是类概率与在给定某一特征值下的类概率的差.

2 KNN分类方法简介

KNN分类方法把文本表示为D(T1,W1;T2,W2;…TN,WN)形式的加权向量.对于测试文本，计算该文本向量和训练样本集中每个样本的相似度，找出K个最相似的文本，在这K个近邻中，依次计算每类的权重，最后把测试文本分到权重最大的类中.

3 特征提取在KNN中的性能比较

实验目的：我们用KNN分类器比较常用的文本特征提取方法：IG、CE、MI、χ2、WE及 DF特征提取方法.训练集样本数为1882.我们采用开放性测试，即训练数据不同的测试集进行测试，测试集样本数为934.

实验环境：分类算法KNN，特征预处理采用禁用词表，权重计算公式TF*IDF，K值取35，特征数目从50到10000.为评价分类效果我们采用最通用的性能评价方法：准确率(Precision)来对各种提取方法进行比较.

实验结果：

表1 特征提取方法在KNN中的比较

图1 特征提取方法在KNN中的比较

用KNN分类器比较常用的文本特征提取方法，比较结果见表1和图1.各种方法的分类准确率表现出随特征数的增加先增加后降低的变化曲线.对于中文文本分类来说，特征向量空间过大或过小时，分类准确度都不高.选用的特征词过少时，不能反映各个类别的特征，不能准确地区分各个类别的文档；而选用的特征词过多时，一些区分度很低的冗余词汇也被加了进来，这样那些区分度较高的词在其中被“稀释”了，不能有效地为区分文档做贡献.IG、CE、χ2、WE、DF五种特征提取方法在 KNN分类器中性能接近，并且在特征空间维度为1000时，分类正确率达到最大.互信息(MI)特征提取方法随着特征数的提高分类性能提高得较快，当特征数目较小时分类性能极差.原因可能是互信息没有考虑特征词出现的频度，导致互信息评价函数不选择高频的有用词而有可能选择稀有词做文本的最佳特征.此外MI是基于类别信息的特征提取方法.当训练语料库未达一定规模时，特征空间中必然存在相当数量的出现频率很低（如低于三次）的特征.而因它们较低的出现频率，必然只属于较少的类别.而使用类别信息的统计方法认为这些低频词携带较为强烈类别信息，从而对他们有不同程度的倚重.但是研究发现，这些低频词中只有不到20%的词确实带有较强的类别信息，大多数都是噪音词，不应成为特征.当选择较少数目的特征时，选取的大多是低频词，这些词对分类并无很大作用，所以当特征数目较少时分类的正确率很低，随着特征数目的增加性能一步一步的提高.最后因我们训练集的文本都不太长，故当特征数目达到100000时，基本上所有特征都包含进去，故最后分类效果趋于相同.

〔1〕李荣陆.文本分类若干关键技术研究[D].上海：复旦大学，2005.20-25.

〔2〕庞剑锋，卜东波，白硕.基于向量空间模型的文本自动分类系统的研究与实现[J].计算机应用研究，2001，21（9）：23-26.

〔3〕朱华宇，孙正兴，张福炎.一个基于向量空间模型的中文文本自动分类系统 [J].计算机工程，2001，27（2）：36-40.

〔4〕孙健，等.基于K一最近距离的自动文本分类研究[J].北京邮电大学学报，2001，24(1)：41-44.

〔5〕田文颖.文本特征提取方法研究.http://blog.csdn.net/tvetve/archive/2008/04/14/2292111.aspx.

〔6〕于瑞萍，张明.中文文本自动分类中特征词选择算法研究[J].硅谷,2009（12）：61.