当前位置:首页 >> 电力/水利 >>

基于文档频率的特征选择方法


第 36 卷 Vol.36

第 17 期 No.17

计 算 机 工 程 Computer Engineering
文章编号:1000—3428(2010)17—0033—03 文献标识码:A

2010 年 9 月 September 2010
中图分类号:TP18

·软件

技术与数据库·

基于文档频率的特征选择方法
杨凯峰,张毅坤,李 燕
(西安理工大学计算机科学与工程学院,西安 710048) 摘 要:传统的文档频率(DF)方法在进行特征选择时仅考虑特征词在类别中出现的 DF,没有考虑特征词在每篇文档中出现的词频率(TF) 问题。针对该问题,基于特征词在每篇文档中出现的 TF,结合特征词在类别中出现的 DF 提出特征选择的新算法,并使用支持向量机方法 训练分类器。实验结果表明,在进行特征选择时,考虑高词频特征词对类别的贡献,可提高传统 DF 方法的分类性能。 关键词:文本分类;特征选择;文档频率;词频率;支持向量机

Feature Selection Method Based on Document Frequency
YANG Kai-feng, ZHANG Yi-kun, LI Yan
(School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048) 【Abstract】In traditional Document Frequency(DF) method, the number of a term which is used in a category is the only information for feature selection, wihtout involving the times of a term appearing in a document. For solving the problem, a new feature selection method is proposed in which the Term Frequency(TF) of terms is taken into consider according to the terms’ document frequency, and the Support Vector Machine(SVM) method is used to train the classifier. It is shown by the experiment that considering the term with high term frequency during feature selection can improve the classification performance of the traditional DF method. 【Key words】text classification; feature selection; Document Frequency(DF); Term Frequency(TF); Support Vector Machine(SVM)

1

最初传统的文本分类是通过人工完成的。 在不同的领域, 受过训练的工作人员对文本进行标引和分类。但随着数字化 文档的日益增多,人工分类显得力不从心。为高效处理和组 织这样的文档数据,文本自动分类(简称文本分类)技术应运 而生。近年来,文本分类技术已经逐渐在网页分类、科技文 献分类、电子邮件过滤等众多领域得到了广泛应用,有效地 提高了信息服务的质量。随着信息量的日渐膨胀,文本分类 的效率和效果需要进一步的提升。因此,对文本分类中的各 项技术进行研究, 提高文本分类的性能成为了一个研究热点。 文本分类包含文本表示、特征选择、文本分类方法等关 键技术,其中,特征选择是文本分类中的一个重要环节,对 分类的正确率有着决定性的影响。文本文档通常采用向量空 间模型(VSM)来表示,即每个文档由所有出现的特征词构成 向量来表示。但这样的特征向量维数非常大,而且并非所有 的特征词都是对分类有贡献的,甚至有些特征词可能会误导 分类结果。因此,应对这样的特征向量进行特征选择,从原 始的特征词集中选取一个子集,将信息量小、 “不重要”的特 征词剔除,从而减少特征项的个数,提高分类的效率和效果。 常用的特征选择方法是根据某种特征评估函数计算各个特征 词的评分值,然后按评分值排序,选取评分值高的若干个特 征词作为特征向量。目前常用的基于统计的特征选择方法有 信 息 增 益 方 法 (IG)、 互 信 息 方 法 (MI)、 开 方 拟 和 检 验 方 法 (CHI)、文档频率方法(DF)等 [1-3]。文献[4]对上述特征选择方 法进行分析比较,结果显示 DF 方法与其他几种方法的分类 性能相差不多,但 DF 方法的实现简单、算法复杂度低。 本文在进行文本分类时选用基于 DF 的方法完成特征选

概述

择 , 即 根 据 特 征 词 在 类 别 中 出 现 的 文 档 频 率 (Document Frequency, DF)对特征词进行排序,保留出现频率高的前若干 个特征词构成特征向量。但传统的 DF 方法仅考虑了特征词 在类别中出现的文档频率(DF)进行特征选择,没有考虑特征 词在每篇文档中出现的词频率(TF)对分类效果的影响。针对 上述问题,本文在考虑特征词频率的基础上,采用基于 DF 的方法完成特征选择。

2

本文使用向量空间模型(VSM)来表示每篇文档,即一篇 文档将表示为如下向量: Doc=<Term1, Term2, …, Termn> (1) 其中,Termi(1≤i≤n)为在这篇文档中出现的特征词,n为在 这篇文档中出现的特征词的个数。本文主要研究中文文档的 分类方法,中文文档不同于英文文档,词语与词语之间没有 间隔符号,因此,需要先对每篇文档进行分词处理。本文使 用 ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System)系统完成文档的分词及词性标注。 ICTCLAS系统是由中国科学院计算技术研究所开发,系统的 源代码及相关文档可在http://ictclas.org/index.html处下载。 通过使用 ICTCLAS 系统,每一篇连续的中文文档被分 割为特征词列表,并且标明了每个特征词的词性。从得到的 特征词列表中删除具有对分类几乎无贡献的词性(如量词、数 词、感叹词等)的词、停用词和单字词,用剩下的特征词构成
基金项目:陕西省自然科学基金资助项目(2009jm8003-1)。 作者简介:杨凯峰(1971- ),男,讲师,主研方向:数据挖掘; 张毅坤,教授;李 燕,讲师 收稿日期:2010-05-28 E-mail:kfyang@xaut.edu.cn

数据准备

—33—

表示文档的特征向量,为后续的特征选择工作做好准备。

3

虽然在数据准备阶段已删除大量与分类无关的特征词, 但是对于构造分类器,剩下的这些特征词数量仍然很多,而 且其中有很多特征词并不能很好地反映类别信息,甚至会误 导分类结果。因此,为提高构造分类器时的效率,得到更好 的分类效果,就需要从这些特征词中进一步挑选出对类别贡 献大的特征词构成特征向量。 文档向量的构成 如前所述,在构造每篇文档的特征向量时,如果一个特 征词出现在该文档中,则这个特征词将作为表示该文档的特 征向量的一个分量。但一个特征词在一篇文档中可能出现了 多次,也可能仅出现了一次。经过分析发现,一个特征词在 一篇文档中的出现次数——词频率(Term Frequency, TF)并不 绝对对应于这个特征词在该文档中的重要性。也就是说,出 现次数多(TF 值高)的特征词并不一定比出现次数少(TF 值低) 的特征词更能体现文档的主题。实验结果表明,存在某些出 现次数多的特征词比出现次数少的特征词更能体现文档的 主题。 为验证上述结论,需要重新构造每篇文档的特征向量, 即在构造特征向量时,除了用原来的特征词构成特征向量以 外,再将在该文档中以高词频出现的特征词补充到向量列表 中。用一个特征词在一篇文档中的绝对出现次数来衡量显然 是不合理的。本文通过式(2)计算每个特征词在一篇文档中的 相对出现频率: 3.1
lg(TFi + 1) TFi = max lg(TF j + 1)
' 1≤ j≤nt

特征选择

以实现特征空间的降维,提高分类的效率,又可以删除那些 对分类无用的甚至会误导分类结果的特征词,改善分类的效 果。在引言中提到过,目前常用的基于统计的特征选择方法 有:信息增益方法(IG)、互信息方法(MI)、开方拟和检验方法 (CHI)、文档频率方法(DF)等。 (1)信息增益方法(Information Gain, IG) 在信息增益方法中,首先统计一个特征词在每个类别的 所有文档中出现和未出现的文档数,然后采用式(5)计算每个 特征词的权重:
G (t ) = ?∑ Pr (ci ) lg( Pr (ci )) + Pr (t )∑ Pr (ci t ) lg Pr (ci t ) +
i =1 i =1 m m

Pr (t )∑ Pr (ci t )(lg Pr (ci t ))
i =1

m

(5)

其中,Pr (ci ) 为一篇文档在第 i 个类别中的出现概率;Pr (t ) 为

特征词 t 在一篇文档中的出现概率; P r (t ) 为特征词 t 不在一 出现概率; Pr ci | t 为特征词 t 不在第 i 个类别中出现的概率;

篇文档中出现的概率;Pr (ci | t ) 为特征词 t 在第 i 个类别中的

( )

m 为类别个数。所有的特征词将按照其计算所得的权值 G(t) 排序,权值大的特征词被保留的可能性大。 (2)互信息方法(Mutual Information, MI) 在互信息算法中,采用式(6)计算特征词 t 和类别 c 之间 的相关度:
I (t , c) ≈ lg AN ( A + C )( A + B)
(6)

(2)

其中,1≤i≤nt,nt 为在一篇文档中出现的特征词的总数,TFi 为第 i 个特征词在这篇文档中的出现次数。借鉴模糊特征的 思想,将每个特征词的 TF’值进行二值化,如果一个特征词 在一篇文档中出现,则将其 TF’值置为 0;如果一个特征词在 一篇文档中以高频出现, 则将其 TF’值置为 1。 本文设计式(3) 来完成二值化处理:
?0 ? TFi = ? ?1 ?
'

其中,A 为在类别 c 中特征词 t 出现的文档数;B 为在除了类 别 c 的其他类别中特征词 t 出现的文档数;C 为在类别 c 中 特征词 t 未出现的文档数;N 为所有类别中的文档数的总和。 如果共有 m 个类别,那么每个特征词将得到 m 个相关度值, 取这 m 个值的平均值作为每个特征词的权值, 权值大的特征 词被保留的可能性大。 (3)开方拟和检验方法( χ 2 -test, CHI) 在开方拟和检验算法中,为了改进互信息算法,设计 式(7)计算特征词 t 和类别 c 之间的相关度:
χ 2 (t , c ) =
N ( AD ? CB ) 2 ( A + C )( B + C )( A + B )(C + D )

0 < TFi ' ≤1 Tmax < TFi ' ≤1

(3)

(7)

在式(3)中, 设定了一个阈值 Tmax, 如果一个特征词的 TF’ 值大于该阈值,则认为该特征词以高频出现。 则一篇文档将被表示为
Doc = < Term1 , TF1' >, < Term2 , TF2' >,L , < Termn , TFn' >
(4)

其中,n=n0+nh。n0 为在这篇文档中出现的特征词的个数;nh 为在这 n0 个特征词中以高频出现的特征词的个数。 也就是说, 如果一个特征词 Termi 出现在这篇文档中,那么在这篇文档 的表示向量中就有一个分量<Termi, 0>。 如果该特征词是以高 频出现的,那么在这篇文档的表示向量中再补充进去另外一 个分量<Termi, 1>。 但在这些特征分量中, 须判断哪些对类别的贡献比较大, 能用来构造分类器。这就需要设计合适的特征选择算法,挑 选出能够较好的标识类别信息的特征分量,用于构成类特征 向量。 类特征向量的构成 构造类特征向量的过程实际上就是对构成文档的特征词 根据其对类别的贡献大小进行特征选择的过程。通过特征选 择,那些对类别信息贡献小的特征词将被删除,这样做即可 3.2 —34—

其中,A 为在类别 c 中特征词 t 出现的文档数;B 为在除了类 别 c 的其他类别中特征词 t 出现的文档数;C 为在类别 c 中 特征词 t 未出现的文档数;D 为在除了类别 c 的其他类别中 特征词 t 未出现的文档数;N 为所有类别中的文档数的总和。 与互信息算法类似,如果共有 m 个类别,那么每个特征词将 得到 m 个相关度值, 取这 m 个值的平均值作为每个特征词的 权值,权值大的特征词被保留的可能性大。 (4)文档频率方法(Document Frequency, DF) 在文档频率方法中,使用特征词在一个类别中出现的文 档数 来表示这个特征词与该类别的相关度。出现的文档数多 的特征词被保留的可能性大。 显然,文档频率方法实现最 简单、算法复杂度最低,而 且 DF 方法与其他几种方法的分类性能也差不多 [4]。因此,本 文将采用基于 DF 的方法完成特征选择。 本文使用复旦大学整理的语料库进行 分类的训练和测 试。 在这个语料库中,各个类别中的文档数不一样,如果直 接使用特征词在每个类别中出现的文档数来表示该特征词和 类别的相关度显然是不合适的。因此,设计式(8)计算特征词 t 在类别 c 中的相对出现频率来表示特征词与类别之间的相

关度。
lg( DFt ) DF '(t , c) = lg( N c )
(8)

其中, DFt 为特征词 t 在类别 c 中出现的文档数; N c 为类别 的特征词的 DF ′ 值小于该阈值,则认为该特征词在这个类别 的样本文档中 出 现的次数太少,对标识类别信息无贡献,将 其删除。同时,有些特征词在一个类别中的 DF ′ 值很高,但 是这些特征词在其他类别中的 DF ′ 值也很高, 那 么认为这些 特征词也不能很好的反映类别信 息 ,也将其删除。剩余的所 有特征词将根据其 DF ′ 值进行排序, DF ′ 值较大的特征词将 被保留下来构成类特征向量,如式(9)所 示 。
C i = < Term1 , TF1' >, < Term2 , TF2' >,L , < Termn , TFn' >
(9)

c 中的文档总数。然后,设置一个阈值 Dmin ,如果计算得到

文档 进行分词处理和词性标注。得到每篇文档的特征词列表 后, 删除其中对分类无贡献的词性的词(在本文中仅保留了名 词)、停用词和单字词。则每篇文档被表示为如式(1)所示的特 征词向量。 (2)根据式 (2)计算每篇文档中每个特征词的 TF ′ 值。再根 据式 (3)给出的规则完成对每个特征词的 TF ′ 值的二值化处 理。在本文中,取 Tmax=0.5。这样,每篇文档被表示为如式(4) 所示的特征词向量。 (3)统计每个特征词 在每个类别中出现的文档频率,根据 式(8)计算每个特征词在每个类别中的 DF ′ 值。如第三部分所 述,删除 DF ′ 值过小的特征词,本文取 Dmin = 0.2 。再删除以 相似频率出 现 在多个类别中的特征词。 将剩余的 特征词根据 其 DF ′ 值按降序排列,在本文中,对于 TF ′ = 0 和 TF ′ = 1 的 特征词分别排序。取 TF ′ = 0 的前 500 个特征词和 TF ′ = 1 的 前 100 个特征词构成类特征向量,如式(9)所示。 (4)根据每篇文档的特征词向量和每个类别的特征词向 量,使用式(10)和式(11)的规则构造训练集和测试集,得到 SVM 方法需要的数据格式。在本文中,先使用 TF ′ = 0 的特 征词构成类特征向量,进行分类器的训练和测试 ;再补 充高 词频(即 TF ′ = 1 )特征词构成类特征向量,进行分类实验。分 别使用上 述 2 种 方法进行分类的性能比较如表 1 所示。
表1
类别 Art S pace C omputer E nvironment Agriculture Economy Politics Sports 召回率 92.86 80.46 88.31 83.38 87.59 82.20 83.63 95.89

其中,1≤i≤nc,nc 为类别的个数,n 代表经过特征选 择后保 留下来表示类别 Ci 的特征词的个数。

4

经过特征选择,用 于训练和测试分类器的数据集就准备 好了 。 本文选用对于文本分类效果较好的支持向量机(Support 完成分类性能的测 Vector Machine, SVM)方法来训练分类器, 试。具体过程如下: (1)将训练和测试数 据集转换为使用 SVM 所需的数据格 式。 在 SVM 中,每个数据实例是用一个实数向量表示的。 因此,需要将用特征词向量表示的训练集和测试集转换为实 数向量。根据第 3 节的描述,文档 Docm 表示为如式(4)所示 的特征词向量,类 Ci 表示为如式(9)所示的特征词向量。在本 文中,设计如下式(10)和式(11)所述规则将特征词向量转换为 实数向量。
在表示类C i的特征向量中的第p个特征词 ?1 ? 在表示文档Docm的特征向量中出现 xp = ? ? ?1 其他 ?

分类器构造

分类性能比较
补充高词频特征词 召 回率 95.15 87.79 90.73 86.20 91.82 85.76 88.63 96.69 准确率 95.30 97.05 96.53 96.72 91.56 93.16 91.72 97.78

(%)
准确率 96.84 97.12 96.88 96.83 91.92 93.94 93.10 98.28

未补充高词频特征词

(10) (11)

Docm 属于Ci ?1 ? i ym = ? ??1 其他 ?

其中, 1≤p≤n, 为表示类 Ci 的特征向量中的特征词的个数; n Docm 为第 m 个文档。这样,文档 Doc m 对应于类 Ci 的实数向 量可描述为
( X , y ), X = [ x1 , x2 ,L, xn ]
i m i m i m

在表 1 中,召回率(Ri)和准确率(Pi)的计算方法如下: Ncpi (13 ) Ri = Nc i

Pi =

(12)

Ncpi Npi

(14)

对每篇文档使用上述规 则构造对每个类别的训练和测试 集, 实现文档向量的实数化。 (2) 使 用 核 函 数 完 成 非 线 性 映 射 。 选 用 Radial Basis Function(RBF)[5]核完成非线性映射。 (3)参数优化。优化、选择在 RBF 核中使用的 2 个参数 C 和γ 。 (4)训练分类器。使用LIBSVM系统和准备好的训练集数 据 训 练 分 类 器 。 LIBSVM 系 统 的 源 代 码 及 相 关 文 档 可 在 http://www.csie.ntu.edu.tw/~cjlin/libsvm处下载。 (5)测试。使用 LIBSVM 系统和测试集数据测试分 类器 性能 。

其中,1≤i≤nc, nc 为类别的个数; Npi 是指分类器预测为第 i 类的文档数; Nci 是指专家认为属于第 i 类的文档数, Ncpi 是指专家和分类器都认为属于第 i 类的文档数,即被正确 分 类的文档数。 可见,在进 行特征选择时,补充部分高词频特征词可以 提高 分类的召回率和准确率。

6

5

本文使 用复旦大学整理的语料库进行分类实验。复旦大 学整 理的语料库共有 20 个类别,分为训练集和测试集。本文 选取其中包含文档数超过 600 个的 8 个类别进行分类效果的 检验。实验步骤如下: (1)使用 ICTCLAS 系 统对这 8 个类别的训练集和测试集

实验

本文选用 基于文档频率的方法完成特征选择。不同于传 统的 文档频率方法,本文考虑了特征词在每篇文档中出现的 词频率对类别信息的贡献。根据特征词在每篇文档中出现的 词频率标示出以高词频出现的词,后再根据特征词在类别中 出现的文档频率完成特征选择。实验证明,在进行特征选择 时,补充部分高词频特征词可以提高文本分类的性能。 文本分类是目前的一个研究热点,研究、改进用于文 本 分类 的特征选择算法是提高文本分类性能的一个方面。下一 步将同时研究文本分类算法,提高文本分类性能。 (下转第 38 页) —35—

结束语


相关文章:
浅谈基于特征选择的文本聚类方法
浅谈基于特征选择的文本聚类方法_计算机软件及应用_IT/计算机_专业资料。两种聚类...考察特征词的文档频数和在文档中出现的次数, 使选出的特征子集更具有较好的代...
05 基于类别概念的特征选择方法 王琳
通过对传统的特征选择方法及其存在的问题的分析,提出了基于类别概念的特征选 择...一般的统计度量值都取作词频的函数,比较有代表性的有文档频率(DF, Document ...
特征选择
喜欢此文档的还喜欢 特征选择算法综述 7页 免费 Ch...,x 基于类间距离的可分离判据 一般来讲,不同类的...为类 的样本频率; 为类 的样本均值向量; 为总的...
文本分类中的特征提取和分类算法综述
本文主要对文本分类中所涉及的特征选择和分类 算法...[2] 1、几种经典的特征提取方法 1.1 文档频率(...文本分类方法文本分类方法主要分为两大类:基于规则的...
常见的特征选择或特征降维方法
暂无评价|0人阅读|0次下载|举报文档常见的特征选择...一种主流的特征选择方法基于机器学习模型的方法。有...比如可以统计某个特征被认为是重要特征的频率(被选为...
2016年公需科目94分试卷2
在 A-U 创新模型中,工艺(流程)创新在( )频率较...的可行性体现了知识创新在选题立项上的哪一特点( )...文档贡献者 gs990431 贡献于2016-10-09 ...
特征选择提取
暂无评价|0人阅读|0次下载|举报文档 特征选择提取_...而通信工程人员则会关心其频率、噪声等性能参数,而 ...但是, 基于类分布常常未知和错误概率的计算复杂, ...
模式识别期末试题
暂无评价|0人阅读|0次下载|举报文档模式识别期末试题...构成单元包括: 模式采集 、 特征提取与选择 和 ...第 8 页共 9 页 二十、定性说明基于参数方法和...
文本分类入门(十)特征选择算法之开方检验
针对英文纯文本的实验结果表明:作为特征选择方法时,开方检验和信息增益的 效果最佳(相同的分类算法,使用不同的特征选择算法来得到比较结果) ;文档 频率方法的性能同...
文章特征
特征词选择算法 有:文本特征选择的算法有基于文档频率 (Document Frequency) 、信息增益 (Information Gain, IG) 、开方拟 和检验方法 (CHI 统计 ) 、互信息 ...
更多相关标签:
特征选择方法 | 特征选择的方法 | 文本特征选择方法 | 特征选择方法综述 | filter特征选择方法 | 特征选择方法的比较 | 特征选择方法有哪些 | 特征选择的标准方法 |