文本分类特征选择算法_特征选择算法在层次分类中的比较研究

　　摘要:特征证选择算法在文本分类中非常重要,本文就对其在层次分类中的应用进行了分析。通过比较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 层次分类算法
　　层次分类因为更能满足实际应用的需求,所以受到了越来越多的关注。因为在每一层一些分类不是很明显的类别之间,总存在一些文本处在类与类的交界处,这些文本很容易被错误地分到别的类别中。训练一个平面分类器时,一开始就试图区分那些差别不大的类别,选择训练样本的范围太大,能够代表类别之间细小差别的训练样本可能会被其他样本所“淹没”,分类器难免错分那些处于类别交界处的文本。层次结构的语料库中,差别不大的小类组成一个大类,而大类之间区分得很开,准确率比较高。将大类分开之后,再在一个大类中区分差别不大的小类,其准确率比平面分类器要高。
　　本文使用自顶向下的层次分类方法,在层次分类学习阶段,对文档集合的每一个内部节点分别建立一个分类器,它将一个类中的所有训练文档合并为一个文档,在提取各类模型时只在同层同一结点下的训练文档间进行比较;而在分类阶段,当一个待分类文档到来后,先用根结点分类器把文档分到相应的大类中,然后再利用该大类所在节点对应的分类器对文档继续分类,如此进行下去,直到将文档分到一个叶子类为止。这种分类过程产生的问题是:如果上面层次的分类器出现了分类错误,则一错到底。
　　2.2 层次分类的特征选择
　　对于大规模的层次分类,有几百个类别,成千上万的特征,如果单纯沿用传统的平面分类的特征提取方法,并不符合实际要求。我们对于文本特征的要求,会随着文本所到达的层次而改变。如在第一层上,根据特征“计算机”我们可以比较容易判断出该文档是属于“体育”还是“计算机”;可是如果我们要进一步判断这篇文档是属于“计算机”大类中的哪个子类别时,比如是属于“硬件”还是“软件”类,“计算机”这个特征并不具有很强的区分度,因为待分类的文档都是属于计算机这个大类的。在这种情况下,我们应该适当的削弱它的权重,甚至可以去除该特征,可以逐层改变文本的特征,即将文档用相应层次的特征来表示。
　　本文采用二次特征选择的方法,它的特点是每个类结点分类器的训练特征都不同,都需要另外进行特征选择。在本文中,我们使用三种不同的特征选择方法文档频率(DF) 、互信息(MI)、 以及卡方统计量(X2)来进行层次特征选择,并分析各种方法的表现。
　　
　　3 实验和总结
　　层次分类必须要有类别的层次性,我们选择了20NewsGroups 数据集进行试验。此数据集中总共有20个不同的新闻组,七个大类。本文的评价指标采用精确率和召回率,层次分类的具体实现步骤如下:
　　首先,我们需要将待分类的文档即测试文档分入第一层的七个大类中,这里我们对训练文档集合进行特征选择,将所有文档用选择的特征来表示,训练SVMLight 分类器并将所有测试文档归类。
　　然后,我们根据第一层分类的结果,提取出已经到达叶子类别的文档,为每个类别重新选择出相应的类别特征,并且降低特征数目。本文采取父类特征数的一半进行实验,例如在第一层上选择了1000个特征,我们就在第二层上用同样的方法选择500个特征;然后将该类别的训练文档以及测试文档,均用 这500个特征表示,进行分类。
　　最后,在第二层分类的基础上,提取出已经到达叶子类别的文档,在需要进一步细分的类别上进行特征选择,然后用这些特征来表示该类别的训练文档以及第二步操作后被分类到此类的测试文档;最后用 SVMLight 分类器进行分类,将测试文档归为子类别。
　　其中每个非叶子类别都用各自的特征集来进行训练和分类,且都用相同的特征选择算法计算。本文是研究特征选择算法在层次分类中性能比较,分类器都统一使用SVMLight,特征权重使用LTC计算公式,表1是这三个特征选择算法在不同维数下的20个类的微平均和宏平均值。
　　从表中我们可以明显发现X2方法要比其他两种方法表现更优异,并且在各个特征维数下都表现的非常稳定,DF方法其次,MI方法最差。随着维数的增加,每种特征选择方法都有提高,随着维数增长,最佳值可趋于相同,因为维数越大,特征之间的重复率就越大。在维数增长的同时,这些方法增长的速度不同, X2方法在维数较低时就达到比较好的结果,到5000维时已经几乎没有增长,而其他两种方法增长的速度一直都很快,受维数增长因素较大。X2方法可以在较低维时就达到较好效果,它在2000维的结果已经接近DF在7000维的结果,而MI方法直到7000维的结果还是非常低。我们分析了这个原因估计是MI本身特征导致,它比较倾向选择罕见词,而在层次分类的第一层分类(即在20NewsGroup数据集上分成7个大类)时,如果加重了罕见词的分量,肯定会使得第一层的分类效果不好,首层的分类好坏直接影响后面层次的分类。
　　层次分类是现在文本分类中一个比较重要的研究方向,而特征选择在层次分类中又显得尤为重要,本文经过实验证明X2比DF,MI,方法性能表现的更优越。在层次分类这个特殊任务中,今后我们还可以考虑不同类别层次使用不同的特征选择算法来进行研究。
　　
　　参考文献
　　[1] Sunax LMEP. Hierarchical Text Classification and Evaluation. Proceedings of the 2001 IEEE International Conference on DataMining[C]. California, USA, 2001. 521 - 528.
　　[2] A.Weigend, E.Wiener, J.Pedersen. Exploiting hierarchy in text categorization[J],Information Retrieval,1999.
　　[3] Yang YM. An Evaluation of Statistical Approaches to Text Categorization [J]. Journal of Information Retrieval, 1999, 1(2): 67 - 88.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文