特征选择算法在层次分类中比较研究.docVIP

特征选择算法在层次分类中比较研究 　　摘要:特征证选择算法在文本分类中非常重要,本文就对其在层次分类中的应用进行了分析。通过比较DF,MI,和X2三个经典的特征选择算法在20NewsGroups数据集的表现,我们发现在SVMLight分类器下X2方法在层次分类中能够表现的更优秀,实验结果显示它在各个不同的特征维数下都能够保持稳定的优势。 　　关键词:层次分类 特征选择算法 　　中图分类号:TP391 文献标识码:A文章编号:1007-9416(2010)05-0000-00 　　 　　引言 　　文本自动分类可以在较大程度上解决目前网上信息杂乱的现象,方便用户准确地定位所需的信息,因此文本分类技术已经成为处理和组织文本数据的关键技术之一。 但是随着信息量的爆炸增长,仅仅通过一层对信息进行组织分类越来越不适合, 平面分类的性能会受到很大制约,文本层次分类可以很好的解决这个问题。层次分类是把分类系统构造为层次结构,即把各类按照一定的层次关系组织成树状结构[1],使文本的定位更准确,分类精度更高。 　　特征选择是是文本分类的重要环节,它根据某个准则从众多原始特征中选择部分最能反映模式类别统计特性的相关特征。目前常用的特征选择算法有:文档频率DF、互信息MI 以及X2统计量等,已有研究者对这些特征选择函数性能的差异做了深度的分析和比较[3],但是在层次文本分类这个领域目前并没有一个很好的定论,本文就是在层次分类背景下探讨各特征选择算法,分析各个函数的性能差异,在20NewsGroup语料库的试验表明,X2性能最好。 　　 　　1 常用特征选择算法 　　我们对常用的特征选择算法文档频率(DF) 、互信息(MI)、卡方 统计量(X2)进行概述。这些方法的基本思想都是对每一个特征即词条,计算它的某种统计的度量值,然后设定一个阈值T,把度量值小于T的那些特征过滤掉。剩下的即认为是有效特征。 　　1.1 文档频率 　　词条的文档频率就是指在训练样本集中出现该词条的文档数,计算训练集中每个词条的文档频率,滤除掉低于某个设定阈值的词条.其理论假设在于稀有词条携带少量有用信息或对分类影响不大.文档频率是最简单的一种特征选择方法,易于实现,一定程度上起到了特征降维的作用,并取得了一定的分类效果, 　　1.2 互信息MI 　　如果用A来表示词条t且属于类别c的文档频率,B表示为包含词条t但是不属于类别c的文档频率,C表示属于类别c但是不含词条t的文档频率,N表示整个训练语料库中的文档总数,词条t与类别c之间的互信息可以下面公式计算: 　　当t与c相互独立时,MI(c,t)自然为0.如果训练集有m个类,对于每个词条w 都有m 个互信息量,取它们的最大值作为每个词条的全局互信息量,然后将全局互信息值进行排序,将低于设定阈值的词条从原始特征空间中移除,保留高于阈值的词条构成特征空间,从而降低了特征空间的维数。 　　1.3 X2统计量 　　X2统计方法度量词条与文档类别之间的相关程度,并假设词条与类别之间符合具有一阶自由度的X分布.词条对于某个类别的X2统计量越高,表明它与该类之间的相关性越大,所携带的类别信息也就越多。令A表示属于类别C且包含词条w 的文档频率,B表示不属于类别C但包含词条w 的文档频率,C表示属于类别C但不包含w 的文档频率,D表示既不属于类别C也不包含词条w 的文档频率,则词条W对于类别C的X2统计量由下列式子计算: 　　X2 统计量的值越高,说明词条与类别之间的独立性就越小.为了将X2统计量应用到所有的类别中与互信息的处理类似。 　　 　　2 文本层次分类方法 　　2.1 层次分类算法 　　层次分类因为更能满足实际应用的需求,所以受到了越来越多的关注。因为在每一层一些分类不是很明显的类别之间,总存在一些文本处在类与类的交界处,这些文本很容易被错误地分到别的类别中。训练一个平面分类器时,一开始就试图区分那些差别不大的类别,选择训练样本的范围太大,能够代表类别之间细小差别的训练样本可能会被其他样本所“淹没”,分类器难免错分那些处于类别交界处的文本。层次结构的语料库中,差别不大的小类组成一个大类,而大类之间区分得很开,准确率比较高。将大类分开之后,再在一个大类中区分差别不大的小类,其准确率比平面分类器要高。 　　本文使用自顶向下的层次分类方法,在层次分类学习阶段,对文档集合的每一个内部节点分别建立一个分类器,它将一个类中的所有训练文档合并为一个文档,在提取各类模型时只在同层同一结点下的训练文档间进行比较;而在分类阶段,当一个待分类文档到来后,先用根结点分类器把文档分到相应的大类中,然后再利用该大类所在节点对应的分类器对文档继续分类,如此进行下去,直到将文档分到一个叶子类为止。这种分类过程产生的问题是