刘 云 肖 雪 黄荣乘

（昆明理工大学信息工程与自动化学院 昆明 650500）

1 引言

随着互联网技术的发展，大量电子文档出现日常生活中，文本分类技术［1～3］越来越重要。在文本分类过程中，文档的每个词都被看作一个特征。一个文档常具有数以万计个特征，由于这些特征大多数都是不相关或多余的，因此在分类过程中，这不仅增加了分类的计算复杂度，而且大量特征可能会对分类准确性产生负面影响。为了提高分类性能，有必要进行特征选择［4～5］，通常利用卡方统计（CHI）［6～7］、信息增益（IG）［8～9］等特征评估函数来选取出重要特征以保留具有最大歧义的特征。

Baykan等提出了基于信息增益和粒子群优化的特征选择算法［10］，该算法通过选择文档中特征的词根，创建特征向量空间，删除了使用频率较低的特征，然后基于粒子群优化算法对特征进行选择后，使用信息增益特征的重要性的降序排列。El⁃berrichi等提出了基于遗传算法的特征选择方法［11］，该算法使用遗传算法选择具有较高适应度值的特征，找到具有最小维数的特征子集，使的分类性能最大化。

本文提出了一种类别依赖特征选择算法（CD），首先通过给定的训练集，基于卡方统计量计算出每个特征的特征评估值（FEF），根据所有特征的FEF值计算出每个训练文档的关联值（DR），然后由这些已知类别的训练文档的DR值，计算出这个类别的阈值CT，并挑选出DR值大于其类别阈值CT的所有同类训练文档，最后在同一类别下的训练文档中根据特征评估函数，每个训练文档都计算出一个具有最大FEF值的特征，挑选出每个训练文档中具有最大FEF值的特征构成了该类的特征向量FS。

2 相关工作

在朴素贝叶斯分类器［12～14］中，针对一个N分类问题，根据最大后验概率规则，将文本x归为后验概率最大的类别：

p(x|ci)是特征的类概率密度函数，p(ci)是类的先验概率。其中为了避免零概率问题，使用“拉普拉斯平滑”技术［15～17］进行处理，并使用极大似然估计［18～20］方法，对c类下每个特征词的概率p̂ic进行估计，估计值为

lic是c类的文档中第i个特征词出现的次数，lc是c类文档中特征词的总数，λ1=1和λ2=M是恒定的平滑参数。

由式（1）得，特征的类概率密度函数直接影响到了贝叶斯分类器的分类性能，所以需要找到最优的特征子集使得分类器的性能最大化。

为了找到最优特征子集，本文提出了一种类别依赖特征选择算法。由图1知，其中训练集Dtr包含di∈NV个文档，其中V是词汇量。首先通过给定的训练集，基于卡方统计量计算出每个特征的特征评估值FEF，根据所有特征的FEF值计算出每个训练文档的文档关联值DR，然后由这些已知类别的训练文档的DR值，计算出这个类别的阈值CT，将DR值大于其类别阈值CT的训练文档挑选出来，并找出其中具有最大EEF值的特征存入FS向量中，将所有训练文档遍历一遍，最终得到了该类的特征向量FS。

图1 类依赖特征选择算法

其中，由于某些文档包含了大量低FEF值的特征使得文档的DR值超过了阈值将其保留，却丢弃了含有少量高FEF值特征的文档，导致具有高辨别力特征的文档被忽略。为了避免该现象，本文将文档的DR值由其特征的FEF值的平均值所计算出，类别的CT值由该类别的所有文档的DR平均值计算出。

因此，本文旨在通过解决这两个问题来提高分类准确度：阈值定义和DR值的计算。所提出的算法基于其文档的重要性为每个类别定义不同的阈值，并将DR值大于其类别CT值的文档用于特征选择。这样就能找到每个类别最具有歧义的特征向量，使得分类器分类性能得以提升。

3 类依赖特征选择算法

3.1 特征向量的构建

根据训练集，基于卡方统计量计算出每个特征的FEF值，并将FEF值存储在S向量中：

其中P(ω|cj)表示类别cj中出现特征ω的文本的概率，P(ωˉ|cˉj)表示除了类别cj的其他类别中没有出现特征ω的文本的概率，P(ω|cˉj)表示除了类别cj的其他类别中出现特征ω的文本的概率，P(ωˉ|cj)表示类别cj中没有出现特征ω的文本的概率，p(cj)表示类别cj的文本出现的概率，p(ω)表示有特征词ω的文本出现的概率。然后，计算出每个训练文档的DR值：

其中di是文档，V是词汇量，sh是第h个特征的FEF值，ωh，i是第i个文档的第h个特征。如果在第i个文档中有第h个特征，则νalued(·)的函数将返回1，否则返回0。下一步是计算CT向量，该向量存储了每个类别的阈值。CT的计算公式为

其中cj是类别，D是训练集中的文档数，di是第i个文档。如果文档di属于类别cj，则函数belοngs(·)返回1，否则返回0。

通过给定的训练集，基于卡方统计量计算出每个特征的特征评估值FEF，根据所有特征的FEF值计算出每个训练文档的DR值，由这些已知类别的训练文档的DR值，计算出这个类别的阈值CT，挑选出DR值大于其类别阈值CT的所有训练文档，并提取出该文档具有最大EEF值的特征。在这过程中，如果每当出现一个新特征，则将新的特征存储在FS向量中并按降序排列。然后，继续下一个文档，重复该过程，最后得到了这个类最终的特征向量FS。

3.2 评价指标

在对文本进行分类时，为评估系统的性能，常使用准确率，精确率和召回率指标，其定义如下：

TP表示判定为正确时属于此类的文本数，TN表示判定为正确时不属于此类的文本数，FP表示判断为错误时不属于此类的文本数，FN表示判定为错误时不属于此类的文本数。为了更全面地进行性能分析，使用精确率和召回率得到了F1指标［21～22］，定义如下：

4 仿真分析

本文采用了REUTERS数据集［23］，REUTERS数据集包含了各类新闻和金融数据的多媒体新闻。其中REUTERS中的ModApte数据集有65个类由12902个文本构成，随机选择了9603个文本作为训练集，并把3299个文本作为测试集，其中抽取了数据集REUTERS-10中的前10个类来进行判定。

基于朴素贝叶斯分类器，本文将CD算法与IG-PSO和GA两种算法进行对比。用分类准确率和F1指标来对三种特征选择算法的性能进行评估，选择的特征词数量范围从10个到1000个。

图2和图3分别代表了CD算法和IG-PSO、GA算法进行实验时其准确率和F1指标的曲线图。由图2看出当特征词数量为50时，本文提出的CD算法的准确率接近最高值93%，大幅领先GA算法，且IG-PSO算法当特征词数量为100时准确率才接近CD算法。由图3看出当特征词数量为50时，提出的CD算法的F1指标接近最大值为89.14%，在特征词个数较少时F1指标大幅领先于IG-PSO算法和GA算法。

图2 三种不同算法的准确率对比图

图3 三种不同算法的F1指标对比图

从上述数据得知，CD特征选择算法与其他两种特征选择算法相比，CD特征选择算法在特征词数量相对少的时候，就可以获得较高的准确率和F1指标，其他对比算法需要更多的特征词数量参考，才能达到相近的准确率和F1指标。

5 结语

在对文本分类时，特征选择会影响分类的精度，所以本文提出了一种类依赖特征选择算法。通过给定的训练集，计算出每个特征的FEF值，对特征的FEF值求平均后得到文档的关联值DR，又通过对训练文档的DR值求平均后得到类别的阈值CT，挑选出DR值大于其类别阈值CT的训练文档进行特征选择得到了每个类的特征向量FS。仿真结果表明，对比IG-PSO和GA两种特征选择算法，CD特征选择算法根据不同类别的训练文档得到特有的特征子集，并在特征选择时通过对EEF和DR取平均值，使得含有少量高FEF值特征的文档得以保留。通过上述优化，使用本文提出的CD特征选择算法能明显提高分类的性能，特别是只需要选取少量特征词就能获得同其他算法一样的分类精度。