一种改进的文本特征选择算法
时间：2022-05-16 09:29:20
摘 要：在文本挖掘中，文档通常以特征向量的形式表示。为了提高文本挖掘算法的运行速度，降低占用的内存空间，过滤掉不相关或相关程度低的特征，提出一种改进的特征选择算法，该算法对特征进行综合考虑，从而更加准确地选取有效的特征。实验验证了改进算法的可行性和有效性。
中图分类号：TP18，TP393文献标识码：B
文章编号：1004-373X(2008)08-097-03オ
Improvement for Feature Selecting from Text Mining
ZHU Haodong1,CAI Lecai1,LIU Zhongying2
(1.Sichuan University of Science and Engineering,Zigong,643000,China;2.Xihua University,Chengdu,610036,China)オ
Abstract：In text mining,documents are usually mean with the form of the eigenvector.In order to enhance the operating speed and reduce the memory space occupied and filter out irrelevant or lower degree of features,an improved feature selection algorithm is presented.We comprehensively considered features,so features can be more effective and accurate selected.And the algorithm is verified exactly with the instance in this paper.
Keywords：textmining;feature selection;eigenvector;document
传统数据挖掘所处理的数据是结构化的，其特征通常不超过几百个；而非结构化或半结构化的文本数据转换成特征向量后，特征数可能高达几万甚至几十万。理论上讲，文本集的特征越多就能越好地表示文本，而实践证明并非总是如此。过大的特征空间将导致此后的文本挖掘过程耗费更多的时间和空间资源，因此从原始特征集中选取最具代表性的特征是十分必要的。本文分析几种常见的特征评估方法，提出了一种改进的特征评估方法。
1 一些常用的文本特征评估函数
在目前所采用的文档表示方法中,存在一个共同的不合人意的地方是文档特征向量具有惊人的维数,使特征子集的选择成为文本挖掘过程中必不可少的一个环节.特征选择即进行维数压缩的工作,这样做的目的主要有:提高程序效率和运行速度;提高分类精度,快速筛选出针对该类的特征项集合.
常用的文本特征评估函数有基于词频法、基于文档频法、信息增益、交叉熵、互信息等。对于这几种方法下面简单介绍一下。
1.1 信息增益
信息增益(Information Gain,IG)表示文本中包含某一特征时文本类的平均信息量，定义为某一特征在文本中出现前后的信息熵之差。信息增益的不足之处在于他同时考虑了特征出现与未出现两种情况。虽然某个词不在文本中出现也可能对判断文本类别有所贡献，但实验证明，这种贡献往往远小于其所带来的干扰。特别在样本分布和特征分布不均匀的情况下，某些类别中出现的特征词通常只占全部特征词很少的一部分，绝大多数特征词在这些类别中是“不出现”的，即此时信息增益大的特征主要是信息增益公式中后一部分大(代表词不出现情况)，而非前一部分大(代表词出现情况)，导致信息增益的效果大大降低。
1.2 交叉熵
与信息增益相似，二者的主要不同是信息增益需要计算所有可能特征分词的平均特征值，而交叉熵仅考虑在一篇文档中出现的词。
1.3 互信息
互信息(Mutual Information,MI)用于表征特征与类别之间的相关性。互信息没有考虑单词发生的频度，这是互信息一个很大的缺点，他导致互信息评估函数经常倾向于选择稀有词。
1.4 基于词频方法
[HTH]定义 [HTSS]词频特征f的词频是指特征f在一篇文档出现的次数，记为TF 。
如果用词频(TF)计算特征评估函数中的概率，则评估函数中用到的概率公式计算方法为:
ИP(c)=|c||D|(1)
P(f)=TF(f,D)|D|(2)
P(f)=TF(f,D)|D|(3)
P(c|f)=TF(f,c)TF(f,D)(4)
P(c|f)=TF(f,c)TF(f,D)(5)И
其中，TF(f,c)表示特征f在c类文档中出现的次数;TF(f,c)表示类别c文档中非特征f出现的次数;TF(f,D)表示特征f在整个文档集D中出现的次数;TF(f,D)表示整个文档集D中所有非特征f出现的次数;|c|表示属于类别c的文档数;|D|表示整个文档集的文档数。И
将式（1）~（5）代入互信息方法或其他方法中形成基于词频的方法。
基于词频的方法往往选取在某类别中比其他类别更频繁出现的词作为特征词，而忽视词在不同文档中的出现情况。
1.5 基于文档频方法
[HTH]定义 [HTSS]文档频指特征f的文档频是指出现特征f的文档数，记为DF 。
如果用文档频(DF)计算特征评估函数中的概率，则评估函数中用到的概率公式计算方法为:
ИP(c)=|c||D|（6）
P(f)=DF(f,D)|D|（7）
P(f)=DF(f,D)|D|（8）
P(c|f)=DF(f,c)DF(f,D)（9）
P(c|f)=DF(f,c)DF(f,D)（10）И
其中，DF(f,c)表示类别c中出现特征f的文档数；DF(f,c)表示类别c中没出现特征f的文档数；DF(f,D)表示整个文档集D中出现特征f的文档数；DF(f,D)表示整个文档集D中没出现特征f的文档数；|c|表示属于类别c的文档数；|D|表示整个文档集的文档数。И
将式（6）~（10）代入互信息方法或其他方法中就形成了基于文档频的方法。
基于文档频的方法仅考虑特征词在文档中出现与否，忽视了在文档中出现的次数。由此带来的问题是如果特征词的DF(f,c)和DF(f,D)相同，那么其在文档中出现多次和仅出现一次的相关度相同。而文档中仅出现一次的词经常是噪声词。
2 本文方法思想
这里认为特征词的重要性不仅与他在文档中是否出现以及出现的次数有关，而且他在文档中的位置、他与类别的相关程度以及在类内的分布情况也有很大关系，为此，对特征词进行综合考虑，提出一种改进的特征词选择算法。
3 特征词重要性度量
3.1 最小词频的文档频
[HTH]定义 [HTSS]最小词频的文档频：特征f的最小词频的文档频是指出现特征f次数达到一定数目的文档数，记为DFn 。其中n为特征词在文档中至少出现的次数。
如果用最小词频的文档频DFnЪ扑闾卣髌拦篮数中的概率，则评估函数中用到的概率公式计算方法为:
ИP(c)=|c||D|（11）
P(f)=DFn(f,D)|D|（12）
P(f)=DFn(f,D)|D|（13）
P(c|f)=DFn(f,c)DFn(f,D)（14）
P(c|f)=DFn(f,c)DFn(f,D)（15）И
其中，DFn(f,c)表示类别c中，特征f至少出现n次的文档数；DFn(f,c)表示类别c中，特征f出现少于n次的文档数；DFn(f,D)表示整个文档集D中，特征f至少出现n次的文档数；DFn(f,D)表示整个文档集D中，特征f出现少于n次的文档数；|c|表示属于类别c的文档数；|D|表示整个文档集的文档数。И
3.2 相关性
特征词应该集中出现在某一类或几类中，而不是分散地出现在各类文档中。为此定义特征与类别的相关性。
[HTH]定义 [HTSS]相关性表示特征fi与类别cj的相关程度，用ρij表示。в捎谝桓隼啾鸬奶卣鞔视卸喔觯因此：
ИЕij=∑m[SX（B]k=1[]k≠j[SX）](DFn(fi,cj)－DFn(fi,ck)∑iDFn(fi,cj))2（16）И
其中，m为类别cj的特征词个数；DFn与3.1节定义相同。那么该特征词的分类能力也就越强，即该特征词也就越重要。
3.3 分散度
如果一个特征词对某个类别较重要，那么他应该是普遍分布在这一类的大部分的文本中，而不是平凡地出现在这类的个别文本中。这里用分散度来表征这种特性。
[HTH]定义[HTSS] 特征fi在类别cj中的分散度表示特征fi在类别cj的文档集中的分布情况，用sijП硎尽
Иsij=DFn(fi,cj)∑mk=1DFn(fk,cj)×TF(fi,cj)∑mk=1TF(fk,cj)（17）И
sij越小则表示特征词fi只出现在cj的个别文档中，不能作为cj的代表属性。DFn与3.1节定义相同，TFв1.4节定义相同。
3.4 位置的重要性
在自然语言中，特征词的位置是表征特征重要性的一个关键指标。人工分类时，人们不一定要阅读全文，往往只需要阅读标题和第一段就有可能准确地确定文本的类别。这说明不同位置的特征对文本的作用也是不一样的，有些词虽然出现频率不高，却很能反映文本的特性。因此，对于不同位置的特征进行多重加权来处理。
位置重要性定义为：
ИLij=c*rij，若特征fi出现在标题或摘要中
d*rij，若特征fi出现在首段或引言中
e*rij，若特征fi出现在其他位置中 （18）И
其中rij=(a肠ij+b*sij)2；a，b，c，d，e为调节系数，且c>d>eА＊
3.5 同义词度量
同义词度量是为了解决在中文文本中普遍存在的同义词和近义词问题而提出来的。例如，微机和计算机表示的是同一个东西，如果不对他们做任何处理而看成2个特征，就很可能造成分类错误。在这个问题的处理上，现在普遍的做法是通过主题词词典或同义词词典对同义词或近义词作标准化处理，即将同义词作为一个词处理。这种做法虽然简单、直观且易于实现，但他没有考虑同义词、特别是近义词之间的语义关系和区别。针对这个问题，本文是利用同义词集将同义词看成一个基于类别的同义概念来处理的。对于特征词fi和类别cj，首先定义fi的同义词集tfi={fk|fk∈T，fp∈tfi，fk≈fp}，其中≈表示同义，T表示类别cj的特征集。从而特征词fi在类别cjе械耐义因子可定义为：
ИTij=DFn(fi,cj)∑|tfi|k=1DFn(fk,cj)/|tfi|（19）И
3.6 特征词fi对类别cjё酆现匾性为
特征词fi对类别cjё酆现匾性为：
ИWij=∑|tfi|k=1Tkj*LkjИ
其中，各项依据上面定义给出即可。
4 本文算法描述
设T为原始特征集，C为类别集。对于cj∈C，设cj的训练文档集为D，cj的特征词选择算法如下：
对于每个fi ∈T，给定n，a，b，c，d，e以及特征词重要度阀值ω。
（1） 计算fi的DFn(fi,cj)，TF(fi,cj)，ρij，sij，Lij，Tij，Wij；
（2） 若wij
（3） 若T中还存在没考察的元素则转到（1），否则算法结束。
5 验 证
在人民网(www．people．corn．cn)上下载了一些新闻分别作为训练和分类样本进行实验，分为IT、经济和体育3个大类，进行的是开放性测试。为便于比较，在实验中测试了2种特征值提取方法：一是本文使用本文的方法；二是词频方法。在实验中，通过计算待分类的文本向量与各个类别向量的夹角余玄来计算相似度。具体的试验结果如表1所示。
表1 试验结果
从表1可以看出，所提出的特征值提取方法的准确率要比基于出现概率的特征值提取方法的准确率平均高12个百分点，维数压缩率则远远高于词频方法，这说明本文的算法有较好的使用价值。
6 结 语
本文综合考虑了特征词的各个方面，从而提出一个特征词选择算法，在某种意义上改变了传统的以词为单位的向量空间，取而代之以同义概念为特征词，从而降低向量空间的维数。本文以特征词提取为重点讨论中文文本分类。实验证明，本文的特征词提取方法比基于词频的特征词提取方法有较高的准确率和维数压缩率。
参 考 文 献
［1］Han Jiawei,Micheline Kamber.数据挖掘概念与技术\[M\].范明,孟小峰,译.北京：机械工业出版社，2001
［2］王继成,潘金贵.Web 文本挖掘技术研究［J］.计算机研究与发展,2000,37 (5):513 520.
［3］邹娟,周经野,邓成,等.基于多重启发式规则的中文文本特征值提取方法［J］.计算机工程与科学,2006,28(8):7879，104.
［4］李荣陆，王建会，陈晓云，等.使用最大嫡模型进行中文文本分类\[J\].计算机研究与发展,2005,42(1):94101.
［5］陈晓云，胡运发.基于规则权重调整改进文本关联分类\[J\].计算机研究与发展,2004,41(增刊):193198.
［6］Delgado M,MartinBautista M J,Sanchez D,et al.Mining Text Data:Special Features and Patterns.In Proceedings of ESF Exploratory Workshop,London,U.K.,2002.［7］Drucker H,Wu D,Vapnik V N.Support Vector Machines for Spam Categorization.IEEE Transactionson Neural networks,1999,10(5).
［8］Dong G.Zhang X,Wong L,et al.CAEP:Classification by Aggregating Emerging Patterns\[C\].In Proceedings of the Second International Conference on Discovery Science,Tokyo,Japan,1999:3042.
［9］Escudero G,Marquez L,Rigau G.Boosting AppliedtoWordSense Disambiguation\[C\].In Proceedings of ECML-00,Ilth European Conference on Machine Learning,Barcelona,Spain,2000:129141.
［10］Fayyad U,Piatetsky-Shapiro G,Smyth P.FromDataMiningto Knowledge Discovery:An Overview.In Advances in Knowledge Discovery and Data Mining,MIT Press,Cambridge,Mass.,1996:136.
［11］Feldman R,Dagan L.Knowledge Discovery in Textual Databases (KDT)\[C\].In Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD95),Montreal,Canada,1995:112117.
［12］Feldman R,Hirsh H.Mining Associations in Text in Presence of Background Knowledge\[C\].In Proceedings of 2nd Intl.Conf.on Knowledge Discovery and Data Mining,KDD′96,1996:343346.
［13］Feldman R,Hirsh H.Finding Associations in Collections of Text.In Machine Learning and Data Mining\[M\].John Wiley&Sons,1997.
［14］Feldman R,Dagan I.Mining Text Using Keyword Distributions\[J\].Journal of Intelligent Information Systems,1998,10:281300.
［15］Friedman N,Geiger D,Goldszmidt M.Bayesian Network Classifiers.Machine Learning,1997,29:131163.
作者简介 蔡乐才 1968年出生，教授，硕士生导师。研究方向为网络安全。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
