第4卷第5期 智能系统学报 VoL.4 No.5 2009年10月 CAAI Transactions on Intelligent Systems 0ct.2009 doi:10.3969/j.i8sn.16734785.2009.05.011 基于粗糙集的文本分类特征选择算法 张志飞12，苗夺谦12 (1.同济大学计算机科学与技术系，上海201804；2.同济大学嵌入式系统与服务计算教有部重点实验室，上海201804) 摘要：文本分类是根据未知文本的内容将其划分到一个或多个预先定义的类别的过程，是许多基于内容的信息管 理任务的重要组成部分.文本分类问题的难点是特征空间的高维性，通常采用特征选择作为降维的重要方法.将属 性约简和文本分类的特点相结合，提出了一种基于粗糙集的特征选择算法即改进的快速约简算法.实验表明该算法 是有效的，不仅可以降低特征空间的维度，而且能够维持高精度 关键词：文本分类；粗糙集：特征选择；快速约简 中图分类号：TP391文献标识码：A文章编号：1673-4785(2009)05045305 Feature selection for text categorization based on rough set ZHANG Zhi-fei2,MIAO Duo-qian.2 (1.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China;2.The Key Laboratory of Embed- ded System and Service Computing,Ministry of Education,Shanghai 201804,China) Abstract:Text categorization assigns text documents to one or more predefined categories based on their contents. This assists content-based information management.A difficult problem in this task is the high dimensionality of the feature space.To resolve this,a feature selection method was employed to reduce the dimensions.A new approach based on rough sets,that we call it the improved quick reduction (IQR)algorithm,was proposed.It involved both attribute reduction and text categorization.The experimental results demonstrated the effectiveness of the proposed algorithm.It reduced the dimensionality of feature space,while maintaining high accuracy. Keywords:text categorization;rough set;feature selection;quick reduction 自20世纪80年代以来，信息化的浪潮席卷全 了特征项和类别的负相关程度，可能选择在某类中 球.“信息爆炸”虽然提供了丰富多彩的信息资源， 出现较少而在其他类中普遍存在的特征，这会对分 但是限制了人们有效地获取信息的能力.文本分类 类结果产生干扰 是根据给定文本的内容将其判为事先确定的若干个 粗糙集理论是20世纪80年代由波兰数学家 文本类别中的某一类或某几类的过程1]，具有广 Pawlak首先提出的一个分析数据的数学理论.它不 泛的应用.但其面临的一大难题就是，文本特征空间需要任何预备的或额外的有关数据信息，能够有效 的高维性，因此需要在保证一定分类精度的同时对 地分析和处理不完备、不一致、不精确的数据4).粗 文本特征进行降维.降维的2种常用方法是特征选 糙集的核心是属性约简、删除冗余属性、获取对于决 择和特征抽取.特征选择是指从原始特征项集中选 策分类最有用的属性，与特征选择有相似之处.于 取一个子集构造新的特征空间.常用算法是基于阈 是，将粗糙集的属性约简和文本分类的特点相结合， 值的过滤，如卡方(CHI)统计、信息增益(information 提出改进的快速约简(improved quick reduction, gain,lIG)、互信息(mutual infomation,MI).Yang] IQR)算法，选择有用的特征表示文本，并通过实验 通过实验分析说明了CHⅢ的分类效果比IG和MI 验证了该算法的有效性。 好.但是CⅢⅡ也存在一个不足之处，即过多地考虑 1粗糙集的基本理论 收稿日期：2008-11-16. 基金项目：国家自然科学基金资助项目(60775036,60475019)：高等 1.1基本概念 学校博士学科点专项科研基金资助项目(20060247039). 通信作者：张志飞.E-mail:2zfj01@126.com. 在粗糙集理论中，一个信息表定义为二元组
·454· 智能系统学报 第4卷 I=(U,A),其中非空有限集合U称为论域，非空有 特征项集T={t1,t2,…,tm},每篇文本在特征项上 限集合A称为属性集.对于任一属性a∈A,存在一 的取值为1和0，分别表示该特征项在文本中出现 个信息函数f:U→V.,V。称为属性a的值域.通常 和不出现.将D作为论域，T作为条件属性集，文本 属性集A可以划分为2个子集：条件属性集和决策 类别c作为决策属性，c的值域V.={c1,c2,…,cp}, 属性集，分别用符号C和D表示，此时的信息表称 构成文本分类决策表，如表1所示. 为决策表。 表1文本分类决策表 设属性子集BCA,称二元关系ND(B)为论域 Table 1 A decision table for text categorization U上的B-不可分辨关系，定义4] T ND(B)={(x,y）∈U2IHa∈B, D a(x)=a(y). (1) 2 如果(x,y)∈ND(B),则称对象x和y在属性集B d 0 0 上是不可分辨的.显然，ND(B)是一个等价关系， 0 1 [x]a表示包含对象x的ND(B)的等价类， 设论域子集XCU和属性子集BCA,X的B-下 de 1 0 近似和B-上近似分别用BX和BX表示，定义俐 BX =xI [x]X, (2) 在文本分类中，此决策表具有如下特点： BX={x[x]anX≠0. (3) 1)条件属性集规模庞大，即m值很大，原因是 前者表示根据B可以确定归入到X中的对象集合，后 文本向量空间的高维性 者表示根据B可能归人到X中的对象集合；而集合 2)属性取值极不均匀，即0、1分布差异大，原 POS(X)=BX (4) 因是每篇文本的项相对很少， 称为X的B-正域 2.2改进的快速约简 1.2属性约简 文本分类决策表的约简要求不是很严格，既不 约简是保证正域不变的最小属性集合.一个信 需要是最小约简，也不需要具有完备性.因此可 息表可能存在多个约简.计算最小约简是NP-hard 以栖性完备性，以减少时间上的开销. 问题，因此采用启发式方法寻找最优或次优约简，如 2.2.1改进的不可分辨关系 Maudal提出的基于正域的快速约简算法[]，苗夺谦 粗糙集的基础是不可分辨关系，传统意义上认 等人提出的基于互信息的属性约简算法[等. 为2个对象在属性集B上不可分辨当且仅当B中 快速约简(quick reduction,QR)算法]的基本 所有属性的取值都相等.由于文本分类决策表中0、 思想是不断选择使正域大小变化最大的属性，直到 1分布很不均匀，传统概念过于严格，使得2个文本 正域大小和条件属性正域的大小相等为止， 算法：快速约简(QR)算法. 在属性集上总是不可分辨的，无法进行后续的分析 输入：决策表I=(U,CUD) 于是引入差异度的概念，表示在属性集上取值不相 输出：约简属性R. 等的属性所占的比例 1)初始化R=0. 设对象x和y,属性子集BCT,x和y在B上的 2)令辅助集合T=R 差异度定义为 3)对每个属性x∈C-R,如果满足 Da(x,y)= card(POSRUL(D))>card(POS(D)), card({a∈Bla(x)≠a(y)}) (5) 则令T=RU{x}. card(B) 4)令R=T,如果满足 设定阈值B,只要2个对象的差异度低于该阈值，就 card(POSR(D))=card(POSc(D)), 说明2个对象在给定的属性集上不可分辨.于是不 则转到5)；否则转到2). 可分辨关系可修改为 5)输出约简属性R,算法终止 IND'(B)={(x,y)∈U2IDa(x,y）<B.(6) 2基于粗糙集的特征选择 2.2.2属性局部排序和筛选 利用统计学的方差来衡量属性在类别间的波动 2.1模型构建 情况.波动越大，属性越具有类别区分度.对于波动 根据训练文本集D={d1,d2,…,dn}得到候选 特别不明显的，将其删除.因此该步骤在一定程度上
第5期 张志飞，等：基于粗糙集的文本分类特征选择算法 ·455· 删除了不具有类别区分度的属性.为了适合本文的 则令T=RU{x. 模型，对文献[7]中的方法做一定的修改 5)令R=T,如果满足 算法：属性局部排序和筛选算法 card(POSg(c))card(D), 输入：决策表I=(D,TU{c}). 则转到6)：否则转到3). 输出：条件属性子集T, 6)初始化特征项集S=R 1)将决策表I按文本类别分割成类别矩阵. 7)根据属性局部排序和筛选算法中得到的Z 2)对每个类别矩阵，计算每个列向量的和（即 和B,将T-R中的属性按照B的值分组，组内按照 属性在该类别中的文档频率)，得到向量X. Z的值从大到小排序. 3)将不同类别的向量X组成一个矩阵M,计算 8)平均从每组中按序选择属性构成N-IR|个 每个列向量的方差，得到向量Z,同时记录每个列向 属性添加到S. 量中最大值对应的文本类别，得到向量B. 9)输出特征项集S,算法终止， 4)按照Z中的值将属性从高到低排序，然后将 与快速约简QR算法的区别在于增加了第1) 大于指定阈值（一般为接近0的较小正数）的属性 步，对属性集进行局部排序和筛选，时间复杂度为 依序添加进T. O(1V。ID1),相比约简复杂度O(IT121D2)来说 5)输出条件属性子集T,算法终止 影响不大此外，属性集规模减小，能够避免盲目搜 2.2.3阙值的计算 索，有助于快速找到约简，提高整个算法的效率.算 根据训练文本计算改进的不可分辨关系中的阈 法还增加了第7和8步，得到约简之后，按照剩余属 值.原则是保证各类训练文本在T上是可分辨的， 性的类间波动及出现最多的类别补充一定数目的属 此时有card(POSr(D))=card(D). 性，构成文本分类的特征项集，时间复杂度相比约简 算法：改进不可分辨关系的阈值计算， 可以忽略.之所以这样做，是因为若约简出的特征词 输入：决策表I=(D,TU{c})和属性子集T. 较少，很多文本因不含这些特征词而表示为空，导致 输出：阈值B. 分类器无法识别，误分几率增大，分类效果降低。 1)初始化B=1. 2)对D中的每一篇文本和之后的所有文本进 3实验及其分析 行如下操作： 3.1实验设置 a)如果2篇文本的类别相同，则转d); 实验采用中科院计算所谭松波提供的语料库，共 b)计算2篇文本在T上的差异度t; 有财经、电脑、房产教育、科技、汽车、人才、体育、卫生 c)如果满足tcard(POS(c)), 个类别中抽取4个类别，每个类别30篇训练文本
·456 智能系统学 报 第4卷 50篇测试文本.得到在不同组合下属性约简结果如 1.00 表2所示，以及IQR和CHⅢ在不同的特征维度下的 0.95 微平均F1对比情况，如图1所示. A 0.90 表24种组合下属性约简结果 Table 2 Results of four combinations'attribute reduction 0.85 &一CH ×一1QR 属性维度 组合 微平均F 0.8040 60 80100120140160180200 原始约简 特征数 财经+教育+人才+娱乐7696 11 0.665 (c)教育/汽车/人才/卫生类组合 0.95 电脑+房产+汽车+科技6329 12 0.745 教育+汽车+人才+卫生6531 11 0.740 0.90 科技+汽车+体育+卫生653612 0.740 0.85 从表2可以看出，经过快速约简之后，特征维度 0.80 A—CHI ×—IQR 从六七千维减小到十几维，降低幅度很大，此时的微 平均F,值为70%左右，说明用粗糙集属性约简方 0.754 60 80100120140160180200 特征数 法得到的特征词具有很强的分类能力. (d)科技/汽车/体育/卫生类组合 结合表2和图1可以看出，补充适量的特征词 增大特征维度之后，例如40维时，微平均F1值为 图14种组合下IQR、CHⅢ微平均F比较 80%以上，提高的幅度很大.原因在于，当特征维度 Fig.1 Micro_F comparison of four combinations'IQR and 太小时，一部分文本因不含有这些特征词而表示为 CHI 空，导致分类器无法识别，误分几率增大 综合考虑以上4种组合的情况，如图2所示.对 从图1可以看出，特征维度增大到一定量时，微 于原始维度在7000左右的小文本集，用IQR和CHⅢ 平均F1值将达到90%以上，分类效果较佳；同时发 将维度降到200左右，均能保持相当好的分类效果， 现当特征维度继续增大时，微平均F值反而减小， 而且IQR比CⅢ的分类效果有一定程度的提高.主 说明过多的特征词会对分类产生干扰， 要原因是：IQR用快速约简得到的特征词具有很强的 0.92 分类能力，再根据波动性和类别情况补充特征词，不 0.90 0.88 仅尽可能解决了文本表示为空的问题，而且能够区分 义 0.86 有些低频词，所以分类效果比CⅢ稍好. 0.84 0.94 0.821 一IQR 0.92 0.80406080100120140160180200 特征数 0.9( &一CHI (a)财经/教育/人才/娱乐类组合 0.88 ×—IQR 0.8640 6080100120140160180200 1.00 特征数 0.95 图2IQR、C田微平均F,比较 0.90 Fig.2 Micro_F comparison of IQR and CHI 0.85 A一CHI 4 结论 X—1QB 0.8040 6080 100120140160180200 文本分类的分类效果很大程度上取决于文本特 特征数 征项的选取.在小文本集上，IQR的效果比CHⅢ稍 (b)电脑/房产/汽车/科技类组合 好，验证了QR算法的有效性.但实验仍存在不足 之处：
第5期 张志飞，等：基于粗糙集的文本分类特征选择算法 ·457· 1)决策表的属性值为布尔型，丢失了部分信 duction of knowledge[J].Computer Research and Develop- 息，可尝试用词频表示； ment,1999,36(6):681684. 2)IQR和CHⅢ的对比验证是在小文本集上完 [7]盛晓炜，江铭虎.基于Rough集约简算法的中文文本自 成的，没有推广到大文本集上，原因在于本实验采用 动分类研究[J].电子与信息学报，2005,27(7)：1047 1052. 的属性约简算法的时间复杂度高。 SHENG Xiaowei,JIANG Minghu.Automatic classification 因此，本文下一步的工作主要在于设计时间复 of Chinese documents based on rough set and improved 杂度较小的属性约简算法，以提高约简速度，并将其 quick-reduce algorithm J].Electronics and Information 应用到大文本集上，分析其实际应用效果 Technology,2005,27(7):1047-1052. 参考文献： [8]AAS K,EIKVIL L.Text categorisation:a survey[R].Os- lo:Norwegian Computing Center,1999. [1]苗夺谦，卫志华.中文文本信息处理的原理与应用 作者简介： [M].北京：清华大学出版社，2007：214-230 张志飞，男，1986年生，硕士研究 [2]周屹.基于Naive Bayes的文本分类器的设计与实现 生，主要研究方向为文本挖掘、智能信 [J].黑龙江工程学院学报，2007,21(2)：2830. 息处理， ZHOU Yi.A text classifier's design and realization based on Naive Bayes method[J].Journal of Heilongjiang Institute of Technology,2007,21(2):28-30. [3]YANG Yiming,PEDERSEN J O.A comparative study on feature selection in text categorization[C]//Proceedings of 苗夺谦，男，1964年生，教授、博士 the Fourteenth International Conference on Machine Learn- 生导师.中国计算机学会人工智能与模 ing.Nashville,USA,1997:412-420. 式识别专业委员会委员，中国人工智能 [4]王国胤.Rough集理论与知识获取[M].西安：西安交 学会理事，上海市计算机学会理论与人 通大学出版社，2001：1-100. 工智能专业委员会委员.主要研究方向 [5]MAUDAL O.Preprocessing data for neural network based 为粗糙集理论、粒计算、主曲线、网络智 classifiers:rough sets vs principal component analysis[R]. 能、数据挖掘等.已主持完成多项国家、省部级自然科学基金 Edinburgh:University of Edinburgh,1996. 与科技攻关项目，并参与完成“973”计划子项目1项，“863” [6]苗夺谦，胡桂荣.知识约简的一种启发式算法[J].计 计划项目2项.曾获国家教委科技进步三等奖、山西省科技 算机研究与发展，1999,36(6)：681684. 进步二等奖、教育部科技进步一等奖等.发表学术论文120 MIAO Duogian,HU Guirong.A heuristic algorithm for re- 余篇，其中被SCI和E等收录50余篇，出版学术专著3部. 欢迎订阅《机器人技术与应用》杂志 《机器人技术与应用》是由国家863机器人技术主题专家组和北方科技信息研究所共同主办的一本综合信息 类刊物，是我国惟一一本介绍机器人信息，传播机器人知识的刊物.本刊为国际机器人联合会(FR)会员单位，创 刊于1988年，是中国学术期刊（光盘版）与《中国期刊网》全文收录期刊，在国内自动化领域享有很高的声誉. 《机器人技术与应用》主要报道工业自动化、智能化工程机械及零部件、数控机床、机器人技术领域所取得的 新技术、新成果、科技动态与信息.传播企业信息和市场行情，交流业内创新成果，推动行业技术进步 《机器人技术与应用》杂志为双月刊，大16开本，48页.国内统一刊号：CN11-3520/TP;广告经营许可证号：京 商工商广字0041号；邮发代号：82675.全国各地邮局均可订阅，也可以直接与本社联系邮购. 每期定价10.00元，全年定价60.00元. 地址：北京2413信箱41分箱《机器人技术与应用》杂志社 邮编：100089 电话传真：01068961813 网站：www.ta.org.cn E-mail robot@onet.com.cn