0 概述

随着信息技术的不断发展，网络上出现大量具有较高维度的包括文章、影评、垃圾邮件等文本数据。高维度能够使信息更加完整, 但其对分类器的要求较高, 还会产生维度灾难的问题^[1]。因此, 研究如何从海量文本数据中提取特征具有重要意义。

文本的特征提取是指从经过分词、归一化和去停用词等预处理操作的文本中，选择最具代表性的特征词集合。通过特征子集的选择, 从而达到降维的效果。特征维度的降低不仅提高了分类器的运算效率, 还避免了因维度灾难造成分类效果降低的现象。因此, 特征子集的选取直接影响了分类器的训练效率和分类精度。传统的特征词选取的方法有信息增益(Information Gain, IG)^[2], 文本词频(Document Frequency, DF), χ²统计量(CHI)^[3], 词频-逆文本率(TF-IDF)^[4]等。但传统的特征提取方法仅考虑了特征与文本类别以及文本类别之间的关系, 并没有考虑特征词之间存在的冗余性。

最大相关最小冗余(minimal Redundancy Maximal Relevance, mRMR)算法不仅考虑到特征与类别之间的关系, 同时也考虑到特征之间的独立性。文献[5]利用ReliefF算法选择权重较大的特征, 然后利用mRMR选择与目标类别最大相关且之间冗余性最小的特征子集。文献[6]通过mRMR选择特征子集。文献[7]引入权重因子α细化对特征相关性和冗余性的度量。文献[8]通过相关性分析(Correlation Analysis, CA)和mRMR这2种特征选择算法筛选出不同的特征变量, 结果表明, mRMR筛选出的特征更具优势。文献[6-8]使用mRMR算法进行特征子集的选择, 保证了特征子集语义的完整, 但生成特征子集的计算代价较大。为减小计算代价且不破坏语义完整性, 文献[9]提出一种基于改进TF-IDF函数的文本分类方法。文献[10]验证了信息增益算法分类效果优于TF-IDF算法。文献[11]引入类差分度的概念, 提出一种改进的互信息特征选择方法, 利用类差分度解决互信息方法未考虑到的特征项与类别之间关系问题。文献[12]利用信息增益与主成分分析(Principal Component Analysis, PCA)相结合的方法对数据进行降维, 提高检测率, 但PCA具有一定的模糊性, 不适用于区分不同的样本类。

本文介绍传统的信息增益以及mRMR特征选择方法, 引入类差分度对mRMR算法进行改进, 提出IG_CDmRMR方法。在此基础上, 使用IG、IG_mRMR以及IG_CDmRMR方法分别选择最优特征子集, 从而得到文本分类结果。

1 二阶段特征选择方法

文本分类流程如图 1所示。其中, 在特征选择过程中使用本文提出的IG_CDmRMR二阶段特征选择方法, 利用IG初步筛选较优特征子集, 使用改进的mRMR方法进行二阶段筛选, 去除存在冗余的特征词, 最终得到最优特征子集。

1.1 初次筛选

信息增益通过计算待分类集合的熵与选定特征的条件熵之差来衡量特征对分类的重要程度, 并筛选出最优的文本分类特征子集^[13]。在文本分类领域, 通过计算某个特征词w_i在类别C中出现的文本数进行统计计算特征词w_i对类别C的贡献程度^[14], 即特征词w_i的信息增益值, 其计算公式为:

$ \begin{array}{l} IG\left( {{w_i}} \right) = P\left( {{w_i}} \right)\sum\limits_i^m {P\left( {{C_t}\left| {{w_i}} \right.} \right){\rm{lb}}\frac{{P\left( {{C_t}\left| {{w_i}} \right.} \right)}}{{P\left( {{C_t}} \right)}}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;P\left( \overline{{{w}_{i}}} \right)\sum\limits_i^m {P\left( {{C_t}\left| \overline{{{w}_{i}}} \right.} \right){\rm{lb}}\frac{{P\left( {{C_t}\left| \overline{{{w}_{i}}} \right.} \right)}}{{P\left( {{C_t}} \right)}}} \end{array} $

(1)

其中, m表示文本类别总数, C_t表示第t类文本, P(w_i)表示特征词w_i在文本中出现的概率, P(C_t)表示第t类文本在总文本中出现的概率, P(C_t|w_i)表示文本中包含特征词w_i并且属于C_t类的条件概率, P($\overline{{{w}_{i}}} $)表示文本中不包含特征词w_i的文本概率, P(C_t|$\overline{{{w}_{i}}} $)表示文本不包含特征词w_i时但属于C_t类的条件概率。

1.2 二次筛选

在经过IG筛选的特征子集中, 特征词之间仍存在冗余性, 因此要对筛选的特征子集进行二次特征提取。mRMR算法是经典的基于空间搜索的过滤方法, 使用互信息衡量特征之间的相关性与冗余度^[15]。最大相关表示特征与类别之间相关度大, 即最大程度反映文本类别信息。最小冗余表示特征词之间相关度小, 即特征词之间的冗余度小^[6]。

在二次特征筛选时, 使用信息增益初步筛选获得的特征词集D₁={w₁, w₂, …, w_n}, 其中初步筛选的特征集合中包含n个特征词, 在D₁的n个特征词中使用mRMR标准选取一个合适的特征子集S, S⊂D₁。

mRMR算法中最大相关和最小冗余定义分别如式(2)和式(3)所示。

$ \max D\left( {S,C} \right),D = \frac{1}{{\left| S \right|}}\sum\limits_{{w_i} \in S} {I\left( {{w_i};C} \right)} $

(2)

$ \min R\left( S \right),R = \frac{1}{{{{\left| S \right|}^2}}}\sum\limits_{{w_i},{w_j} \in S} {I\left( {{w_i};{w_j}} \right)} $

(3)

其中, |S|表示特征子集S已经存在的单词的个数, I(w_i; C)表示特征词w_i与文本类别C之间的互信息值, I(w_i; w_j)表示特征词w_i与特征词w_j之间的互信息值。

由上述的2种约束条件产生mRMR, 有:

$ \max \phi \left( {D,R} \right),\phi = D - R $

(4)

特征词与类别之间以及特征词与特征词之间的计算公式如下:

$ \begin{array}{l} I\left( {{w_i};C} \right) = \sum\limits_t^m {\left[ {P\left( {{w_i},{C_t}} \right){\rm{lb}}\frac{{P\left( {{w_i},{C_t}} \right)}}{{P\left( {{w_i}} \right)P\left( {{C_t}} \right)}} + } \right.} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {P\left( {\overline{{{w}_{i}}},{C_t}} \right){\rm{lb}}\frac{{P\left( {\overline{{{w}_{i}}},{C_t}} \right)}}{{P\left( \overline{{{w}_{i}}} \right)P\left( {{C_t}} \right)}}} \right] \end{array} $

(5)

$ \begin{array}{l} I\left( {{w_i};{w_j}} \right) = P\left( {{w_i},{w_j}} \right){\rm{lb}}\frac{{P\left( {{w_i},{w_j}} \right)}}{{P\left( {{w_i}} \right)P\left( {{w_j}} \right)}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P\left( {{w_i},\overline{{{w}_{j}}}} \right){\rm{lb}}\frac{{P\left( {{w_i},\overline{{{w}_{j}}}} \right)}}{{P\left( {{w_i}} \right)P\left( {\overline{{{w}_{j}}}} \right)}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P\left( {{w_i},\overline{{{w}_{j}}}} \right){\rm{lb}}\frac{{P\left( {\overline{{{w}_{i}}},{w_j}} \right)}}{{P\left( \overline{{{w}_{i}}} \right)P\left( {{w_j}} \right)}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P\left( {\overline{{{w}_{i}}},\overline{{{w}_{j}}}} \right){\rm{lb}}\frac{{P\left( {\overline{{{w}_{i}}},\overline{{{w}_{j}}}} \right)}}{{P\left( \overline{{{w}_{i}}} \right)P\left( {\overline{{{w}_{j}}}} \right)}} \end{array} $

(6)

其中, P(w_i, C_t)表示C_t类中包含特征词w_i的文档概率, P($\overline{{{w}_{i}}} $, C_t)表示C_t类中不包含特征词w_i的文档概率, P(w_i)表示包含特征词w_i的文档概率, P($\overline{{{w}_{i}}} $)表示不包含特征词w_i的文档概率, P(C_t)表示C_t类文档数占总文档数的概率, P(w_i, w_j)表示同时包含特征词w_i、w_j文档数占总文档数的概率, i≠j, P(w_i, $\overline{{{w}_{j}}} $)表示包含特征词w_i但不包含特征词w_j的文档数占总文档数的概率, P($\overline{{{w}_{i}}} $, $\overline{{{w}_{j}}} $)表示既不包含特征词w_i又不包含特征词w_j的文档数占总文档数的概率。

文本数据包含大量的特征词, 计算特征词之间的互信息值时, mRMR算法通常采用增量式搜索思想获得最优特征集合S。假设已经筛选出特征子集S_k－1, 即特征子集里已经包含k－1个特征词, 然后从剩余的特征词集合{D₁－S_k－1}中选择第k个特征词^[9], 第k个特征词的选取计算公式如下:

$ \mathop {\max }\limits_{{w_i} \in {D_1} - {S_{k - 1}}} \left[ {I\left( {{w_i};C} \right) - \frac{1}{{k - 1}}\sum\limits_{{w_j} \in {S_{k - 1}}} {I\left( {{w_i};{w_j}} \right)} } \right] $

(7)

2 改进的mRMR特征选择方法

传统mRMR算法直接计算最大相关和最小冗余差值, 难以准确选择相关性和冗余性的权重。文献[7]对mRMR算法的最大相关与最小冗余进行线性加权, 并通过实验验证, 当最大相关部分的权重为0.25时, 分类精确度最高。因此, 本文引入类差分度差值α, 并动态设置最大相关部分的权重。

2.1 类差分度差值

类差分度是指具有较强影响力的特征项应该集中出现在某一或某几类中, 且在类别包含的文档中均匀分布^[16]。类差分度将类间的离散度(AC)和类内特征项的耦合度(DC)结合, 既考虑特征项在不同类文本中出现的频数, 也考虑了特征项在同一类文本中分布的差异性。

类间离散度表示特征词在各个类别文档中的分布情况, 表征能力强的特征词集中出现在某一类文档中, 而不会在所有类别文档中均匀分布。类间离散度的计算公式如下:

$ AC = \sqrt {\frac{1}{{m - 1}}\left( {\sum\limits_{t = 1}^m {{{\left( {{f_t}\left( {{w_i}} \right) - \overline {f\left( {{w_i}} \right)} } \right)}^2}} } \right)} $

(8)

其中, m表示文本所属类别数, f_t(w_i)表示在类别C_t中包含特征词w_i的文档数, $ \overline{f({{w}_{i}})} $表示包含特征词w_i的总文档在每个类别中的平均文档数。AC值越大, 表明该特征词w_i在对类别的区分能力越强。

类内耦合度表示特征词在某类文档内部的分布情况, 表征能力强的特征词在类内呈现均匀分布, 不会集中出现在某几篇或者某一片文档之中。类间耦合度计算公式如下:

$ D{C_t} = \sqrt {\frac{1}{n}\sum\limits_p^n {{{\left( {{g_p}\left( {{w_i}} \right) - \overline {g\left( {{w_i}} \right)} } \right)}^2}} } $

(9)

其中, DC_t表示特征词w_i在C_t类中的类内耦合度值, n表示属于C_t类的文档总数, g_p(w_i)表示特征词w_i在C_t类第p篇文档中的词频数, $ \overline{g({{w}_{i}})} $表示在C_t类所有文档中特征词w_i的平均词频数。DC_t值越小, 表示该特征词对类别C_t的表征能力越强。

2.2 改进的mRMR算法

mRMR算法考虑了特征词对所有类别的互信息值, 本文引入类差分度β的差值来细化互信息值。具体地, 本文选取所有类别中类差分度β最大的2个值作差。差值越大, 表示该特征只在某一类中类差分度较大, 在其他类中类差分度较小, 说明该特征只在某一类中集中出现, 在其他类中出现频率较低, 因此该特征能够唯一确定某一类, 对该类的表征能力较强, 对其他类的表征能力较弱。然而, 差值越小, 表示该特征至少在2个类中出现的频率相近, 即特征不能确定类别, 对类别的表征能力较弱。此外, 引入差值后借助对数处理对其进行尺寸压缩。在不改变数据性质以及特征与类别之间相关性的基础上使数据更加平稳。其计算公式如下:

$ \alpha = {\rm{lb}}{\left( {\beta _{\max }^1 - \beta _{\max }^2} \right)^{\frac{1}{\lambda }}} = {\rm{lb}}\left( {\frac{{AC}}{{DC_{\min }^1}} - \frac{{AC}}{{DC_{\min }^2}}} \right)\frac{1}{\lambda } $

(10)

其中, β_max¹=AC/DC_min¹和β_max²=AC/DC_min²表示特征词w_i在所有类别中最大的2个类的类差分度值, λ是一个常数, α表示类差分度差值, 并对差值取对数。

将上述类差分度引入mRMR方法, 计算公式如下:

$ \mathop {\max }\limits_{{w_i} \in {D_1} - {S_{k - 1}}} \left[ {\alpha I\left( {{w_i};C} \right) - \frac{1}{{k - 1}}\sum\limits_{{w_j} \in {S_{k - 1}}} {I\left( {{w_i};{w_j}} \right)} } \right] $

(11)

基于改进的mRMR特征词选择算法具体描述如下:

输入  初次IG算法选择特征词集igFeatureList, 按信息增益值降序排序, 文档数据集data, 最终所需的特征数selectNum

输出  最终选择特征词集合selectFeature

1.WordsClassMIDict//存放特征词与类别之间的互信//息值

2.alpha//存放特征词的类差分度

3.selectFeature//存放最终选择的特征词集合

4.//计算特征词与类别之间互信息值, 并降序排序, 存//入WordsClassMIDict

5.WordsClassMI=CalculateWordClassMI(data, igFeatureList)

6.//计算每个特征词的类差分度, 存入alpha

7.Alpha=CalculateWordClassDiffDegree(data)

8.//选择igFeatureList中信息增益值最高的特征词, 存//入selectFeature

9.selectFeature.append(igFeatureList[0])

10.//创建一个字典存放特征词和最后一个选择的单词//的互信息值(MI_ij)的累加和

11.for i in range(1, len(WordClassMIDict)):

12.sumDict[WordClassDict[i]] = 0.0

13.while(len(selectFeature) <= selectNum):

14.maxNum = 0.0

15.for i in range(1, len(WordsClassMIDict)):

16.word_i = WordsClassMIDict[i]

17.Word_j=selectFeature[-1]

18.//计算2个特征词之间的互信息值

MI_ij=Calculate2WordsMI(word_i, word_j)

19.sumDict[word_i] += MI_ij

20.temp=alpha[word_i]×WordClassMI[word_i]- (sumDict[word_i]/len(selectFeature))

21.if (temp > maxNum):

22.tempWord = word_i

23.maxNum = temp

24.//添加tempWord到selectFeature

25.selectFeature.append(tempWord)

26.//sumDict中移除tempWord

27.sumDict.pop(tempWord)

28.//特征词集合中移除tempWord

29.WordClassMIDict.pop(tempWord)

30.//返回最终的特征词集合

31.return selectFeature

3 实验结果与分析

为验证算法的分类效果, 本文选取IMDB、康奈尔影评以及ling-spam垃圾邮件作为实验数据集。为保证语料的结构化, 对语料库的停用词进行预处理, 去掉标点符号及其他特殊字符。本文实验选取70%的数据作为训练集, 30%作为测试集, 分类器采用高斯核的支持向量机模型, 实验平台使用Python3.6。

本文利用信息增益、信息增益与最大相关最小冗余(IG_mRMR)以及信息增益与改进最大相关最小冗余(IG_CDmRMR)分别筛选出各自特征子集, 并利用各自的特征子集对文本进行向量化处理。本文使用词频-逆文本数(TF-IDF)算法对文本进行向量化, 并进行归一化处理, 实验采用十折交叉验证方法, 选择查准率(Precision)、召回率(Recall)以及F1值作为评价标准。

本文使用IG、IG_mRMR、IG_CDmRMR这3种方法选取IMDB、康奈尔影评以及垃圾邮件数据集各自特征子集, 且特征子集的维度为10~100(间隔10), 其中, IMDB与康奈尔影评提取的特征子集结果如表 1所示(选取前20维特征子集)。IMDB与康奈尔影评只分为积极与消极2种类型, 根据文献[17]对文本情感的分析, 评价词在文本情感中具有重要的作用, 主要包括形容词、副词的情感词。从表 1可以看出, IG、IG_mRMR、IG_CDmRMR提取的IMDB评价词语(加粗)分别有14个、15个、17个, 提取康奈尔影评的评价词分别为16个、17个、18个。

为比较3种特征选择方法分类效果, 本文选择数据集中10维~100维特征进行准确率增长性分析, 对数据集中100维~1 000维特征进行F1值的稳定性分析, 如图 2和图 3所示。从图 2可以看出, 随着特征维度的增加, 3种特征提取方法最终分类准确率呈明显上升趋势。当最终分类准确率达到80%时, 本文提出的IG_CDmRMR特征提取方法所需特征数量最少, 比其他2种方法特征词数量减少5个~10个。当选择相同数量的特征子集时, 本文提出的IG_CDmRMR方法准确率最高, 比其他2种方法提升约2%。从图 3可以看出, 当特征维度达到一定维度(IMDB数据集是400维左右, 康奈尔影评数据集是300维左右, 垃圾邮件数据集是700维左右), 能够准确地区分文本类别的大部分特征词, 此时分类效果最佳。当继续增加筛选的特征子集的维度时, 表征能力弱的特征词将被筛选进入特征子集, 造成干扰, 从而导致分类准确率下降。本文提出的IG_CDmRMR方法相比其他2种方法, 其相同特征维度下F1值平均高出1个~2个百分点, 正确分类文本数增加15篇~25篇。

4 结束语

传统特征提取方法仅考虑特征与文本类别之间的相关性, 忽略了特征词之间的冗余信息。因此, 本文通过结合信息增益和改进的最大相关最小冗余, 提出一种基于IG_CDmRMR两阶段的特征选择方法。利用IG和mRMR进行特征筛选, 去除存在冗余的特征词, 最终得到最优特征子集。实验结果表明, 本文提出的特征词提取方法能够准确地选择合适的特征子集。后续将对该方法进行改进, 进一步提高文本的分类准确率。