·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}得到候选 特别不明显的，将其删除.因此该步骤在一定程度上