n
2013 年
P（ C i | t） 表示文档包含词条 t 时属 中包含词条 t 的文档的概率， 珋 P（ t ） 表示语料中不包含词条 t 的文档的概 于 C i 类的条件概率， P（ C i | 珋 t ） 表示文档不包含词条 t 时属于 P（ C i ） 的条件概率， 率， m 表示类别数。 显然， 某个特征项的信息增益值越大， 贡献越大， 对分类也 越重要。因此， 在进行特征选择时， 通常选取信息增益值大的若 干个单词构造文本的特征向量 。
D ic （ t， Ci ）
= 槡
1 n
∑ （ f （ t）
ij j
－ f i （ t） ）
2
n f i （ t） n 槡 －1
（ 5）
f ij （ t） 表示词条 t 在 C i 类的第 j 篇 其中 n 代表 C i 类中的文档个数， f i （ t） 表示词条 t 在 C i 类文档中的平均词频。 类 文档中的词频， 说明该词条越集中分布在该类中， 其区分本类别 内离散度越本分类的流程包括中文文本分词 、 特征选择、 构造分类器
和测试评估四个部分， 中文分词包括文本分词和去停用词两个 部分。
3． 1
特征选择
特征选择算法已在第一部分中详细介绍过， 词条 t 的 IG、
和类内分散度
［7］
有关 。
2． 1
类间离散度
ECE 和 MI 的函数值分别按照式（ 1 ） 、 式（ 2 ） 、 式（ 3 ） 计算， 根据 2． 3 节所示的类别区分词的选取方法计算出词条 t 的 CDW 的 值， 然后对所有的词条 t 按照对应函数值的大小降序排列， 分别 选取前 N 个词条作为本次特征选择函数选出的特征词条构成 特征向量空间。
不按类别计算统计值， 选 出 的 特 征 项 都 是 全 局 意 义 上， 没有 从局部考虑特征项对单个类别的区分能力， 全局意义上的词 但是有些词条的单类类别意义非 可能存在多类的指示意义， “足 协” 、 “股 权” 、 “患 者 ” 常明显， 比 如“导 弹”、 等 等， 它们 几乎就只出现 在 某 一 类 文 档 之 中， 这些词称之为类别区分 词 。 类别区分词有着极强的类别指示意义， 但是如果从全局 ECE 和 MI 的函数值不 是 很 大， 意义上来考虑， 这些词的 IG 、 有可能 被 移 除 掉 。 类 别 区 分 词 的 选 取 与 词 条 的 类 间 离 散 度
［4 ， 8 ］
1． 3
互信息（ MI ）
互信息根据特征和类别共同出现的概率， 度量特征和类别
的相关性。计算公式如（ 3 ） 所示： P（ C i | t） MI （ t） = ∑ P（ C i ） log P（ t） i =1
m
：
（ 1 ） 对每一个词条 t 按照式（ 6 ） 计算出该词条在每个类别 中的类别区分度。 （ 2 ） 从 Distribute（ t） 中按照类别区分度的大小选择出词条 t 中的最大者 Max1 和次大者 Max2 。 （ 3 ） 计算词条 t 的 Max1 和 Max2 的差值， 记为 CDW （ t ） = Max1Max2 。 （ 4 ） 按照 CDW 的值对所有的词条 t 作降序排列， 取前 N 个 词条作为特征向量来对文本进行分类 。
式（ 3 ） 中各个变量的含义与式（ 1 ） 、 式（ 2 ） 中变量的含义是一致 的。互信息的值越大， 说明特征项与类别的相关性越强， 这样的 特征项就越应该筛选出来构造文本的特征向量空间 。
2
类别区分词
IG 、 ECE 和 MI 并 从式（ 1 ） 、 式（ 2 ） 和式（ 3 ） 中可以看出，
IDF （ Term Fre用的权重计算公式是特征频率 反文档频率 TF9 ］ quencyInverse Document Frequency） ［7， 计算公式， 文档 j 中第 i
IDF 计算公式如公式（ 8 ） 所示： 个词条 T ij 在 TFW （ T ij ） = tf（ t ij ） × log（ N / n ik + 0 ． 1 ）
ECE （ t） = P（ t）
∑ P（ C
i =1
i
| t） log
P（ C i | t） P（ t）
式（ 2 ） 中各个概率值的含义与式（ 1 ） 中的含义是一致的。 特征 项的期望交叉熵的值越大， 说明特征项对分类的作用越明显， 这 样的特征项越应该保留 。
词条 t 在各个类别中的类别区分度分布如下公式（ 7 ） 所示， m 表示类别数： Distribute（ t） = ｛ CD（ t， C1 ） ， CD（ t， C2 ） ， …， CD（ t， Cm ） ｝ （ 7） 类别区分词的选择方法如下 （ 3）
0
引
言
数值， 然后根据函数值的大小对特征词条进行降序排列， 然后选 取前 N 个词条作为文本分类的特征向量。常用的特征选择函数
［3 ］ 有信息增益 IG （ Information Gain ） ， 期望交叉熵 ECE （ Excepted ［5， 6 ］ Cross Entropy ） ［4］， 互信息 MI（ Mutual Information） 等。
IG （ t） = －
∑P（ C ） logP（ C ）
i i i =1 m
+
P（ t）
∑ P（ C
i =1 m i =1
i
| t） logP（ C i | t） + （ 1）
P（ 珋 t ） ∑ P（ C i | 珋 t ） logP（ C i | 珋 t）
P（ t） 表示语料 其中 P（ C i ） 表示 C i 类文档在语料中出现的概率，
After analysing some of the feature selection methods，a new feature selection method based on classdiscriminating words is proposed． Experimental results show that the new feature selection method is superior to traditional approaches in categorisation efficiency，therefore verifies the validity of the new method． Keywords cross entropy 对向量空间中的每一个特征项即词条， 用特征选择函数计算其函 Text categorisation Feature selection Class discriminating word Information gain Mutual information Excepted
1
特征选择函数
在文本分类中， 常用的特征选择是基于阈值的， 基本思想是：
CCF 会 员 （ E2000172 收稿日 期： 2012 － 04 － 10 。 周 奇 年， 教 授， 52M） ， 研究方向为物联网， 云计算及数据挖掘。 张振浩， 硕士生。 徐登 彩， 硕士生。
194
计算机应用与软件
特征选择是中文文本分类过程中的一个重要过程， 特征项选择的优劣直接影响文本分类的准确率 。 在分析几种特征选 择方法的基础上， 提出一种类别区分词的特征选择方法 。实验结果表明， 类别区分词的特征选择方法的分类效率高于传统方法， 从
要
而验证了该方法的有效性 。 关键词 中图分类号 文本分类 TP391 特征选择 类别区分词 A 信息增益 互信息 期望交叉熵
类间离散度用来描述特征词条在类间的分布情况， 特征词 条的类间离散度计算如式（ 4 ） 所示：
DI ac （ t） =
槡
1 （ f i （ t） － f（ t） ） m － 1∑ i =1 f（ t）
m
2
3． 2
（ 4）
词条权重
词条的权重反映了该词条对本篇文本分类的重要程度， 常
f i （ t） 表示既包含特征词条 t 在类别 C i 的中的频度， f（ t） 表 m 表示类别 示包含特征词条 t 在各个类别中的频度的平均值， 那些集中分布在个别类或者几个类别 数。式（ 4 ） 中可以看出， 的特征词条， 其类间离散度的值比较大， 这些特征词条一般具有 较强的类别区分能力。
文本分类的主要任务是在给定的分类体系下， 根据文本内 ［1 ］ 容将未知文本划分到一个或者多个类别中 。 当前， 随着互联 网上海量文本信息资源的出现， 文本分类在信息检索、 文档组织 管理、 信息过滤等方面都有广泛的应用 。
［1 ， 2 ］ 在基于向量空间模型（ VSM ） 的文本分类体系中， 文本 由特征项和特征项的权重构成的向量来表示， 一篇文本 D 被表
1． 1
信息增益（ IG ）
信息增益是一种利用熵信息的评估方法， 广泛应用在机器
通过计算某一特征项在文本中出现前后的信息熵之 学习领域， 差， 来表示该特征项为整个分类所提供的信息量 。 计算公式如 式（ 1 ） 所示：
m
w1 ） ， （ t2 ， w2 ） ， （ t3 ， w3 ） ， …， （ tn ， wn ） ｝ ， 示为如下形式｛ （ t1 ， 其中 t i w i 表示特征项的权重， 表示特征项， 一般直接选择中文文本信息 的基本单位即文本的词来作为特征项 。通常由于文本分类训练 样本比较大， 造成了高维的文本向量空间， 高维的文本向量空间 而且特征项也不明显， 严重影响了文本分 通常含有大量的噪声， 类的性能。因此， 特征降维便是文本分类过程中最为关键的一 步。特征选择作为特征降维中常用的方法， 目的在于从高维的 减小文本 特征向量空间中筛选出具有区分类别能力的特征项， 的特征向量维数， 去除冗余特征， 以提高分类系统的效率 。
第 30 卷第 3 期 2013 年 3 月
计算机应用与软件 Computer Applications and Software