494 智能系统学报 第3卷 2)对于A:的其他样本u∈A:,一旦u生X, 2.2规则约简与聚类原则 则A不是X的子集，结束；如果A:中的所有样本均 从上面的实例可以看出，分层提取所得到的规 包含在X中，则A:为X的子集， 则往往存在冗余，需要约简，规则约简的基础是基于 可见，在最坏情况下的计算量为1U1+（IA:I- 规则关联样本集的隶属关系。顺序为：先行后列，先 1)1X1.由于IA:1,IXI≤IU1,时间复杂度为 同属性后不同属性，约简的过程可以遵循以下的一 0(1U12).因此，结合步骤1)以及步骤2)得到每层 些定理进行，同时，在约简的时候将产生相应的聚类 规则提取的时间复杂度为O(1U12).假设进行了n 约束， 次分层提取，则规则提取的总的时间复杂度为 定义2聚类约束：P:C[v]->C[o](X), C[]为约束的前件，C[w]为约束的后件，X,为本 名010.其中：U,1=1U1,1u1为第i-1 约束所适应的样本集合，即样本X,对应C属性的 次分层提取之后剩下的样本数目. 属性值v转化为w. 考虑文献[9]中的决策表，见表1，条件属性集 定理1如果有某个条件属性在同一层的不同 C={a,b,c,决策属性集D={d},U={#1,#2,#3, 属性值指向同一个决策属性值，即S:C,-> 料，5}.运用HHR算法提取规则。 D(X)且S2:C2->D(X2),则这两条规则可以合 表1决策表1 并，新规则的关联样本为X=XUX2· Tablel Decision table 1 聚类原则1：对于定理1中的规则合并，被约掉 U 的规则的前件可以转换成任何一个值，考虑最大聚 b d 1 0 2 类的情况，应该将其改为保留规则的前件，并产生对 1 #2 2 0 3 1 应的聚类约束。 粥 1 2 1 1 定理2于规则S:C:->D(X),如果同一层 料 2 1 3 0 与其具有相同后件的其他规则集S(X)={S 揽 1 0 3 0 C->D,(X),C≠C,D=D,X=UX满足X1S 首先，根据决策属性将U划分为2个子集，即 X,则规则S:可以约掉。 U/R={X1,X;Xg={#4,#5},X1={#1,#2,#3}. 聚类原则2：对于定理1中约掉的规则，其前件 可以寻找到相关于X,的下近似为b2和c1,c2,相关 可以转换成任何一个值，考虑最大聚类的情况，应该 于X,的下近似为b.因此，可以提取出第1层规则： 将其转化为该属性值中有但是没有在规则中出现过 b2->X1（#3),c1->X1（#3),c2->X1（#1), 的属性值。 b1->X(#料).将含有第1层规则的样本删除，得到 考虑聚类原则1，可以得到定理3. 表2. 定理3第i层某个规则S1:C:->D(X1),第 表2抽取第1层规则之后的决策表 i+1层的规则中与S1具有不同后件的规则集 Table 2 Decision table after first abstraction S+1(X)={SIC->D(X),D≠D:,X=UX},且 U b d S的关联样本集X,的属性中不含有C,则规则S 2 2 0 3 1 可以转到第i+1层. 证明规则S1:C:->D(X)如果要转到下一 5 1 0 3 0 层，则要保证该规则与规则集S:+1没有冲突，即不会 此时，X1={#2},X。={#5}.寻找X,的下近似 产生规则歧义，因为在第i+1层引入了新的样本集 有a2·X2的下近似有a1·因此，第2层的规则为： X1,因此，需要保证X,中每一个样本的所有属性中 a2->X1(#2),a1->X(#5).将与第2层规则相 不含有C值，否则，肯定会产生冲突.由此得证， 关的样本删除，由于此时样本集为空，因此，算法结 定理4在规则里面出现过的条件属性为冗余 束.得到了规则表述如下： 属性，可以约掉。 表3规则表 聚类原则3：对于规则里面没有出现过的条件 Table 3 Rule table 属性值，可以将其聚类为同一个值。 b2->X1(#粉)，c1->X(粉)，C2->X(#1), 定理5对于最后一层的规则，如果后件一致， b1->X(料)； 均为D,则倒数第二层中规则后件为D:的规则可 a2->X1(#2),a1->X(5) 以转到最后一层；同时，最后一层的规则以及属性不