摘  要： 在文本分类中，特征空间维数可以达到数万维。使用信息度量的方法，如文档频率、信息增益、互信息等，对特征进行选择后的维数通常还是很大，降低阈值或减小最小特征数可能会降低分类效果。针对这个问题，提出基于粗糙集的二次属性约简。实验表明，该方法在有效降低特征维数的同时保证了分类效果。

　　关键词： 文本分类；粗糙集；属性约简

0 引言

　　特征选择在文本分类中有十分重要的作用，使用不同的特征选择方法会对文本分类的准确率有很大影响。常用的特征选择方法有文本频率（Document Frequency）、信息增益（Information Gain）、互信息（Mutual Information）、统计量（CHI Squared）、几率比（Odds Ratio）等。其中，信息增益在文本分类中有较好的效果。本文通过实验证明，上述方法在属性数目降低到一定程度时分类器准确率会达到瓶颈，继续减少属性可能会降低分类的准确率。

　　粗糙集理论是一种新型的处理不确定性和模糊性的数学工具，基于粗糙集理论的属性约简是该理论的一个重要分支。处理大数据集时，如果直接使用粗糙集进行约简，生成的决策表规模将会十分大，对于离散化和基于粗糙集的属性约简来说，计算复杂度太高，难以完成[1]。因此对于拥有成千上万维的文本集来说，直接使用粗糙集理论进行约简会显得笨拙且性能低下。

　　在上述背景下，本文提出了一种基于粗糙集的二次属性约简方法。该方法使用信息增益的方法对大数据集进行第一次约简，删除对分类无用或只含有少量信息的属性，使数据规模适用于粗糙集约简算法，得到的结果使用粗糙集进行二次约简，这样在保证分类准确率的情况下进一步对特征进行约简。最后通过实验验证了该方法的有效性。

1 常用特征选择方法

　　1.1 文档频率

　　文档频率DF（ti）表示训练文档中出现特征ti项的文档数，出现特征项多的文档包含更多对分类有用的信息，被保留的可能性大。在使用该方法时，需要设置阈值，小于该阈值的特征项全部去除。文档频率的缺点为可能会删除出现次数较少但是包含重要信息的稀有词。

　　1.2 信息增益

　　信息增益是最有效的特征选择方法之一，可以理解为特征项在文本中出现前后的信息熵之差。特征项的信息增益值越大，说明该特征项包含更多对分类有帮助的信息[2]。本文将使用信息增益进行第一次特征选择。特征项t的信息增益表示为：

　　其中，n是文档类别总数，P（ci）表示ci类文档出现的概率；P（t）表示特征项t出现在文档集中的概率；P（ci|t）表示出现特征项t的文档中，该文档属于ci类的概率；P（t）表示不包含特征项t的文档的概率；P（ci|t）表示不包含特征项t的文档中，属于ci类文档的概率。

　　1.3 统计量

　　统计量用来描述实际值与理论值的偏差，根据结果判断一个结论是否正确。在文本分类中，可以用来检验特征项t和ci类之间是独立还是相关关系。特征项t和ci类的统计量表示为：

　　其中，A是特征项t和ci类文档同时出现的次数；B是特征项t出现而ci类文档不出现的次数；C是不包含特征项t的ci类文档出现的次数；D是特征项t和ci类文档同时不出现的次数；N是训练集所包含的文本总数。

　　1.4 互信息

　　互信息用来度量特征项t与ci类别同时出现的关系。在类ci中出现概率高的特征项t比其他类别具有更高的互信息值。MI表示为：

　　其中，P（t|ci）表示ci类文档中特征项t出现的概率；P（t）表示特征项t出现的概率；P（ci）表示ci类文档的概率。

　　1.5 几率比

　　几率比着重关注目标类ci的值，其特别适用于二元分类器。特征项t的几率比表示为：

　　其中，P（t|pos）表示正例中特征项t出现的概率；P（t|neg）表示负例中特征项t出现的概率。

2 基于粗糙集的属性约简

　　2.1 粗糙集预备知识

　　粗糙集是继概率论、模糊集、证据理论之后的又一个处理不确定性的数学工具[3]。基于粗糙集的属性约简是粗糙集理论的一个重要分支，其核心思想是在不影响原模型表达能力的情况下删除冗余属性。属性约简方法主要分为两类：基于可分辨矩阵的约简算法和启发式约简算法。本文采用Johnson约简算法[4]。在具体介绍算法之前，先进行以下定义。

　　定义1 决策系统由四元组S=（U，A，V，F）表示。其中U称为论域，是有限对象的集合；A是属性的集合，也可以表示为A=C∪D，C∩D=，C代表条件属性，D代表决策属性。

　　定义2 在决策系统中，假设存在属性集A，且BA，则A和B的不可区分关系可定义为：

　　其中，IND（A）表示一个等价关系，A中的所有等价关系的集合记为U/IND（A）。

　　定义3 假设R是等价关系族，令Q=R-{r}，r∈R且r≠，当IND（R）=IND（Q）时，r代表冗余属性，而Q称为R的一个约简。R中所有必要关系的集合称为P的核，记为CORE（R）。

　　定义4 假设存在决策系统S，简写为S=（U，C∪D），可辨识矩阵[5]M=（mij）表示为：

　　2.2 属性约简算法

　　（1）基于可辨识矩阵的属性约简算法

　　该方法的基本思想是决策系统的约简与可辨识矩阵的任意非空项的交集不为空，并且可辨识矩阵中单个元素构成的项的并集就是决策系统的核。

　　（2）启发式约简算法

　　目前主要的启发式约简算法有两种，一种是基于可辨识矩阵，算法的基本思想是可辨识矩阵中出现频率越大的属性越重要，区分对象的能力也越强；另一种是基于属性重要性，算法以核作为起点，以属性依赖度作为启发式信息，对属性空间进行搜索，一般情况下能够得到决策系统的最小约简[6]。

　　本文采用Johnson约简算法，该算法是上面第一种基于可辨识矩阵的启发式约简算法，算法描述如下：

　　输入：决策系统S=（U，A，V，F），其中A=C∪D，C=ai。

　　输出：决策系统的相对约简RED

　　（1）令；

　　（2）计算可辨识矩阵M，As={mij:mij≠}；

　　（3）计算属性ai在As中出现的次数ai（As）；

　　（4）选择ai（As）值最大的属性，记为a，RED=RED∪{a}；

　　（5）清除As中包含属性a的项；

　　（6）如果As=，则停止；否则转入步骤（3）。

3 实验结果与分析

　　3.1 性能评测

　　假设任务为一个二分类问题，即实例只能被分为正例和负例。如果一个正例被预测为正类，则称为真正类（True positive），若被预测为负类，则称为假负类（False negative）。同理，如果一个负例被预测为负类，则称为真负类（True negative），若被预测为正类，则称为假正类（False positive）。二分类问题的混合矩阵如表1所示。

　　（1）准确率（Accuracy）

　　准确率是指一个分类器正确预测类标号未知实例的能力。准确率表示为：

　　（2）召回率（Recall）

　　召回率又称为查全率，广泛应用于信息检索和统计学，在数据挖掘领域中通常表示为正确分类正例数占所有正例数的比率。召回率表示为：

　　（3）F值（F-Measure）

　　F值是准确率和召回率的综合指标，能够更好地反应一个分类器的性能。F值表示为：

　　（4）约简率（Reduction Rate）

　　在特征选择中，约简率代表数据集中特征的约简程度。约简率表示为：

　　其中，RAAR（Reduced Attributes After Reduction）表示约简掉的属性个数，AOOD（Attributes Of the Original Data set）表示原数据集属性个数。

　　3.2 实验结果分析

　　本实验数据来源于数据堂中文文本分类语料库，适用于小规模的研究。数据集共分为10个分类，分别是环境、计算机、交通、教育、经济、军事、体育、医药、艺术和政治，共有2 816篇短文档。各类文档分布如表2所示。

　　中文分词阶段使用Lucene中文分词系统，去除停用词、稀有词后，选择词频大于5的特征词，共有505个特征词。为了尽量减小实验误差，采用十折交叉验证的方法进行实验。

　　实验首先使用信息增益的方法对特征进行选择，通过设定不同的最小特征数选取指定数量的特征，并分别使用NaiveBayes、KNN和C4.5三种分类器对不同特征数目下的数据集进行分类实验，得到分类准确率、召回率和F值，实验结果如图1~图3所示。

　　由图1~图3可以看出，准确率、召回率和F值三个指标均显示出随着特征的选择，分类器的性能逐步提高。而且，当特征数目在100~130之间时，三种分类器性能达到最高值。特征数目为100时，虽然KNN和C4.5两种分类器的性能有一定程度的提高，但是三个指标都显示出NaiveBayes的性能已经出现了明显的下滑趋势。所以认为，特征数在减少到130个时，特征选择达到瓶颈，各个分类器总体表现最好，继续减少特征数，分类器性能会出现显著的下降趋势。

　　此时将第一步处理结果中整体准确率表现最佳的特征集（130维）作为第二步粗糙集属性约简的输入，使用Johnson约简算法计算出相对约简，计算结果包含70个特征项，根据式（10）可计算出约简率为46.2%，相对于原特征空间，第一步约简率74%，第二步约简率86%，整体提升了12%，在使用信息度量的方法已经无法继续减少特征数时，进一步压缩了特征空间。将使用粗糙集属性约简前后三种分类器的准确率、召回率和F值进行对比，结果如表3所示。

　　由表3可以看出，使用粗糙集进行属性约简后，NaiveBayes在准确率、召回率和F值三项指标上都有所提高，KNN和C4.5有所降低，但是增加和减少的幅度均较小。根据表中数据可以分析出，三种分类器的性能基本保持不变。说明该方法在使用信息增益的方法进行特征选择的基础上，能进一步删除冗余属性并且不对分类器性能造成较大影响，验证了基于粗糙集二次属性约简的有效性。

4 结束语

　　本文提出一种基于粗糙集的二次属性约简方法，该方法相比单独的信息增益特征选择和粗糙集属性约简有以下优点：

　　（1）信息增益在处理不平衡数据时性能很差，并且缺少对特征项的进一步筛选[7]。使用基于粗糙集的二次属性约简可以剔除冗余属性，一定程度上弥补了信息增益的缺点；

　　（2）粗糙集具有一定的局限性，在处理大数据集时效率非常低[8]，因此面对大数据集时，先采用信息增益处理可以得到适用于粗糙集的数据集，减小粗糙集的计算复杂度。

　　参考文献

　　[1] 张翔，周明全，耿国华．基于粗糙集的中文文本特征选择方法研究[J].计算机应用与软件，2010，27（3）：4-5.

　　[2] Yang Yiming， PEDERSON J O． A comparative study on feature selection in text categorization[C]. Proceedings of the 14th International Conference on Machine Learning，Nashville： Morgan Kaufmann， 1997：412-420.

　　[3] 王平．基于粗糙集属性约简的分类算法研究与应用[D]．大连：大连理工大学，2013.

　　[4] 陈桂芬，马丽，董玮，等．聚类、粗糙集与决策树的组合算法在地力评价中的应用[J]．中国农业科学，2011，44（23）：4833-4840.

　　[5] 杨传健，葛浩，李龙澍．可分辨矩阵及其求核方法[J]．计算机工程，2010，36（9）：87-89.

　　[6] 洪雪飞．基于粗糙集的数据挖掘算法的研究与应用[D]．北京：北京交通大学，2008.

　　[7] 任永功，杨荣杰，尹明飞，等．基于信息增益的文本特征选择方法[J]．计算机科学，2012，39（11）：127-130.

　　[8] 史军．基于粗糙集理论的属性约简算法研究[D]．青岛：青岛大学，2009.