第6期 尹林子，等：规则分层约简算法 ·493· 与条件信息量的关系，定义新的属性重要性，并以此 面有3个三好学生，2个五好学生；山2队里面有3个 为启发信息，给出了计算新的条件信息量的高效算 五好学生，还有2个差学生；d队里面有5个差学 法；文献[7]模拟人类认知的分层递阶原则，将信息 生.那么，可以把每一个队伍(d,d2,d)看成是决策 系统或决策系统的知识在由部分属性所构成的多种 属性d的一个决策属性值，存在一个条件属性c的 层次和多种粒度上表示出来，然后分别对各个属性 属性值则是三好学生c1,五好学生c2以及差学生c 层次进行递阶约简，具有较强的实用性和较好的动 这3个值，而每一个学生作为一个样本含有一个条 态特性，但该算法中属性层次划分的依据不是来源 件属性c,一个决策属性d.则对于d1队来说，它针 于数据分析，而是基于数据采集难度、成本以及实时 对条件属性c的下近似为：三好学生c;五好学生在 性等，对应用的场合有所依赖. 边界.也就是说，一旦某一个学生是三好学生c1,那 本文从另一个角度出发，利用规则约简来代替 么他肯定在d,队，而如果它是五好学生，则可能在 属性约简，提出了规则分层约简算法HRR(hierar- d1队，也可能在d2队. chical reduction of rule):首先利用下近似从决策表 这样就为规则的提取提供了一种思路，即一旦 分层提取规则，然后对规则进行约简，并通过规则约 某一个条件属性值为某个决策属性值的下近似（即 简过程得到新的数据离散化聚类，在此基础上形成 正域)，那么，肯定可以使用这个条件属性值作为该 等价决策表.本算法的优势在于避开了NP难题，同 决策值的一个充分规则：因此，可以将下近似理解为 时又不需要任何先验知识，避免了属性分层约简算 可以进行决策的关键特征， 法的层次划分依赖问题， 然后利用分层思想，将决策表中提取出规则的 相关样本删除，重新再寻找下近似，一直到决策属性 1 粗糙集的基本概念 值只有一个值或者所有样本均已经被规则提取.如 决策表：一个决策表S可以定义为四元组S= 果这两个条件不能满足，并且不能提取新的规则，则 〈U,A,Vf),其中：U为论域；A=CUD,C,D分别为 意味着原始的决策表可能为含有不相容情况等特殊 关于U的条件和决策属性集；V=UaeCuD Va,V.表 情况，剩下的样本为特殊样本 示属性a的值域；f:U×(CUD)→V是一个信息 在本算法中，对提取的规则结构进行了新的定义. 函数，即对任意x∈U,a∈CUD,有f八x,a)∈V 定义1规则的表示方法为：S:C,->D(X); 不可分辨关系：对于子集B∈A,则B在U上的 C:为规则的前件；D:为规则的后件；X1为本规则所适 不可分辨关系定义为 应的样本集合，称为规则S的关联样本集 IND =(x,x')EUI a E B,a(x)=a(x'). 规则分层提取算法如下： 等价类：对于元素x∈U,它的等价类定义为 1)将原始决策表根据条件以及决策属性值对 [x]a={yI(x,y）∈WD(B). 论域进行划分，获得U/a,aeA以及U/D; 下近似与上近似：对于任意一个对象集合X∈U 2)找到每一个条件属性相对于每个决策属性 以及属性集合B∈A.X的B下近似定义为：B,X= 值的下近似，提取规则，如果提取失败，则提取结束， {xI[x]g∈X},X的B上近似定义为：BX= 否则执行步骤3)； {xl[x]a∩X≠0}. 3)将规则的关联样本删除； B.X实际上是由那些根据已有知识判断肯定 4)判断样本集是否为空或者决策属性值只有 属于X的对象所组成的最大的集合，也称为X的正 一个，是则结束，否则，返回步骤2). 域(positive region). 算法分析：步骤1)可以采用文献[8]中的算法 2 HRR算法 E实现，其时间复杂度为O(1U12),最坏情况下为 IU1·(IU川-1)/2.步骤2)可以将U/a中的子集与 HRR算法包括了3个部分：基于下近似的规则 U/D子集比较，一旦U/a中的某个子集为U/D某 分层提取、规则约简以及基于规则的聚类， 个子集的子集，则U/a中的该子集为所寻找的下近 2.1基于下近似的规则分层提取 似.该过程的实现方法如下：设 下近似是粗糙集里面一个最基本的概念.例如： U/a={A1,A2,…,An}, 集X相对于属性B的下近似是所有在B属性下肯 U/D={X,X2,…,Xm}. 定属于X的对象集合，假设有3个队伍，d1队伍里 1)对于uad∈A:,寻找X满足uaa∈X;