第6期 尹林子，等：规则分层约简算法 ·495· 需要保留， 约束条件，那么，在考虑相容性不变的情况下，可以 对于表1所提取出来的规则，可以利用上述定 把等价决策表认为是原来决策表经过离散聚类之后 理进行约简. 形成的，即在相容性不变基础上的数据离散化过程 第1层，先考虑同属性约简，c1和c2均可以用 的可能结果之一 来判断X,因此，可以将c属性的属性值1和2统一 等价决策表与传统的最简决策表相比可能会更 起来，即可以将1变成2或者将2变成1，这样的改 简单，比如对决策表1的规则提取，以传统的观点来 变在现有规则下不会产生歧义. 看，其决策表已经是最简的，无法做属性以及样本约 假设约掉c2->X(#粗)，即将决策表中的c2变 简；但是通过HRR算法，可以把样本#粗和粉化为重 成c1,得到c1->X(#1,#).再来考虑不同属性约 复样本，从而减少了样本数目.也可以利用等价决策 简，规则b2->X1(3),c1->X1(#1,#粉)，b2的关 表直接用传统的方法提取规则，该规则与HRR算法 联样本集为{3}，c1的关联样本集为{#1,3}，因此 得到的规则本质上是一致的，但是泛化能力相对弱 规则b2->X,可以约掉，b2可以转换为任何一个 一些因此，可以根据需要任意选取哪一种形式的规 值.考虑到粗糙集的连续数据离散化过程，应该将 则 b2转换为b属性已有的且未在规则中出现过的值， HRR算法的流程图以及与传统算法流程图的 所以，本例中b,应该转换为b。.因此，得到了约简的 比较见表1. 规则如表4. 表4约简规则表 Table 4 The concise rule table 原始 分层扯 规则 分层最 决策表 收规则 约简 简规则 c1->X(#粗，3)，b->X(料)： a2->X1(#2),a1->x(5). 离散系 等价 最简 相应的聚类约束为：c[2]->c[1](1); 类综码 决策表 规则 b[2]->b[0](3). 定义3等价决策表：将原始决策表按照基于 下近似提取的分层规则进行约简所获得的聚类约束 图1HRR算法的流程图 Fig.1 Flow chart of HRR 进行重编码，获得新的决策表称为原始决策表的等 价决策表， 此时得到的等价决策表如表5所示 表5等价决策表 原始 离散聚 届性 获取 决策表 类绵码 约简 规则 Table 5 Equivalence decision table U b d 图2传统算法的流程图 #1 0 2->1 Fig.2 Flow chart of traditional rough set 2 2 0 3 3 HRR算法应用与比较 #3 2->0 1 3.1与分层递阶属性约简算法的比较 #料 HRR算法吸收了分层递阶的思想，但是与其他 5 0 0 的分层递阶属性约简算法不相同.通常的分层递阶约 可见，如果该决策表来自于连续数据的离散化， 简算法属于一种局部启发式算法，如文献[10]在规则 则可以修改离散化的聚类规则，将b2和c2的编码 的判断上采用了基于条件属性选择的判断方法，先查 去掉；从而可以达到诚少离散化断点的目的，得到更 看某一组条件属性，将相容部分提取规则，对于不相 优的离散聚类集，同时，在等价决策表中，样本#1和 容部分则转入下一组属性处理.它的缺点是： 3是相同的，因此减少了决策表的样本数目. 1)属性值组的划分以及选择问题.属性分组的 2.3等价决策表研究 顺序对最后的约简结果有重要的影响，排在前面的 等价决策表有2个约束条件：一个是约简得到 属性很难被约掉；因此，由一个不合适的属性分组情 的规则；还有一个是规则约简时所产生的聚类约束. 况所产生的属性约简效果不一定好.文献[10]基于 只有在这2个前提下才是等价的.如果抛开这2个 数据采集难度、成本以及实时性等来划分，但是这种