关联规则与粗糙集结合的约简算法（RDDM）及应用 2 几个基本概念 2.1 等价类与不可分辨关系 设 U 是非空的论域，当 R 为 U 上的等价关系（equivalence relation），则 U/R 为 R（或 U 的分类）的所有等价类族，或称 U 的分类；用[x]R 表示 R 中包含 x 的等价类（equivalence class）。 若 P  R，则  P（P 中全部等价关系的交集）也是一个等价关系，称为 P 上的不可 分辨关系（indiscernibility relation），且记为 ind(P)。 2.2 上、下近似与粗糙集 假设给定知识库 K=(U,R)，对于每个子集 X∈U 和一个等价关系 R∈ind(K)，可以根 据 R 的基本集合的描述来划分集合 X。 X 中包含在 R 中的最大可定义集称为 X 的 R 下近似(lower approximation)： R-(X)={x∈U：[x]R  X} X 中包含 R 的最小可定义集称为 X 的 R 上近似（upper approximation）： R-(X)={x∈U：[x]R∩Ｘ≠} 上近似、下近似也可用下面的等式表达： R-(X)=  {Y∈U/R：Y  X} R-(X)=  {Y∈U/R：Y∩Ｘ≠} 集合 BNR(X)= R-(X)- R-(X)称为 X 的 R 边界。 我们也把 posR(X)= R-(X)称为 X 的 R 正域，把 negR(X)=U- R-(X)称为 X 的 R 负域，把 BNR(X)称为 X 的边界域。 当且仅当 R-(X)= R-(X)，X 为 R 可定义集；粗糙集可以近似地定义为：当且仅当 R-(X)  R-(X)，对于 R，X 称为粗糙集。 2.3 决策表、约简与核 RS 理论中应用决策表(decision table)来描述论域中对象。它是一张二维表格，每一行描 述一个对象，每一列描述对象的一种属性。属性分为条件属性和决策属性，论域中的对象根 据条件属性的不同，被划分到具有不同决策属性的决策类。对于分类来说，并非所有的条件 属性都是必要的，有些是多余的，去除这些属性不会影响原来的分类效果。约简 (reduction) 定义为不含多余属性并保证分类正确的最小条件属性集。一个决策表可能同时存在几个约 简，这些约简的交集定义为决策表的核 (core)，核中的属性是影响分类的重要属性。 3 算法描述 针对第一小节所提出的问题，我们设计了一种粗糙集约简算法，能有效解决所述问题。 在该算法中，我们引入关联规则中的支持度概念，并重新定义了这个概念。 定义 1：在决策表 DT 中，t 为条件属性，s 为决策属性，规则 ts 的基数 card（ts） 称作规则 ts 的支持度，记为 sup(ts)；属性 t 的基数 card（t）称作属性 t 的支持度，记为 sup(t)。 定义 2：在决策表 DT 中，tm、tn 分别为规则 m 和规则 n 的条件属性，sm、sn 分别为规 则 m 和规则 n 的决策属性，若 sm＝sn，并且 tn tm，则称规则 m 被规则 n 所包含。 1 

输入：决策表 DT 输出：所产生的确定规则集 Rk 步骤一：对决策表进行属性约简，采用文献[1]所提到的属性约简算法进行。 步骤二：k 赋值为 1。 步骤三：计算候选集 Ck 中每个属性的属性支持度和规则支持度。 步骤四：若该规则的属性支持度等于规则支持度，检查在 Rk－1、Rk－2、……、R1 中是否有包 含该规则的项，若有，则删去该规则，否则将该规则移入规则集 Rk。 步骤五：将 Ck 扩展为 Ck+1：首先扫描 Ck，将 Ck 中的每两项组合成具有 k+1 个属性的候选 项，插入 Ck+1 中。将 k 赋值为 k+1。 步骤六：若 Ck 不为空，则转步骤三。 步骤七：结束。 算法中的符号含义如下： DT——决策表 Ck——条件属性数目为 k 的候选集 Rk——条件属性数目为 k 的确定规则集 4 算法举例 院内感染数据挖掘系统针对病人数据资料挖掘出与院内感染有关的因素，从而预测出病 人发生感染的概率，在此基础上合理预防，以减少发生院内感染的几率。这里我们希望找到 所有与院内感染有关的因素，所以并不十分关注于属性约简，同时我们需要知道每条规则的 支持度是多少，以便作相应处理，因此前面提出的算法在本问题和类似问题中就是最合适的 算法。已知病人资料表见表 5，其中侵袭性操作、既往病史、手术、季节为条件属性，何种 感染为决策属性。 侵袭性操作 既往病史 手术 表 5 病人资料表 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 引流 引流 引流 引流 穿刺 穿刺 穿刺 穿刺 穿刺 备皮 备皮 备皮 备皮 备皮 备皮 备皮 慢性病 慢性病 慢性病 无 无 慢性病 慢性病 无 无 慢性病 慢性病 无 无 慢性病 无 无 先将该表转化为表 6 所示形式。 季节 冬春 冬春 夏秋 冬春 夏秋 冬春 夏秋 冬春 冬春 夏秋 夏秋 夏秋 冬春 冬春 夏秋 冬春 何种感染 呼吸道 呼吸道 胃肠道 呼吸道 术后伤口 呼吸道 呼吸道 呼吸道 呼吸道 呼吸道 胃肠道 呼吸道 呼吸道 呼吸道 术后伤口 呼吸道 无 有 无 无 有 有 有 有 无 有 无 无 无 有 有 有 2 

表 6 转化后的病人资料表 a 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 b 2 2 2 1 1 2 2 1 1 2 2 1 1 2 1 1 U 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 一、 进行属性约简，采用文献[1]中提到的属性约简算法进行约简，即约去决策_可省略的属 c 1 2 1 1 2 2 2 2 1 2 1 1 1 2 2 2 d 1 1 2 1 2 1 2 1 1 2 2 2 1 1 2 1 e 3 3 2 3 1 3 3 3 3 3 2 3 3 3 1 3 性。经过计算容易得出表中只有属性 a 是 e_可省略的，可以从表中约去属性 a。 二、进行值约简。首先计算每个属性的属性支持度和规则支持度，形成条件属性数目为 1 的候选集 C1。依次检查表中的每一项，若某项属性支持度等于规则支持度，则将其作 为确定规则，移入规则集 R 中，表中只有规则(d,1) (e,3)是确定规则，将其从表中移 入 R1。条件属性数目为 1 的候选集参见表 7。表中“#”表示已移入规则集的确定规则。 表 7 条件属性数目为 1 的候选集 决策属性 (e,1) (e,2) (e,3) 条件属性 (b,1) (c,2) (d,2) (b,2) (c,1) (d,2) (b,1) (b,2) (c,1) (c,2) (d,1) (d,2) 规则支持度 2 2 2 2 2 2 6 6 5 7 9 3 属性支持度 8 9 7 8 7 7 8 8 7 9 9 7 确定规则 # 三、形成条件属性数目为 2 的候选集 C2。对 C1 进行扩展，将表 7 中决策属性相同的每两项 结合成条件属性数目为 2 的项。计算其属性支持度和规则支持度。表中(b,1) (c,1)  (e,3) 和(b,2) (c,2)  (e,3)的规则支持度等于属性支持度，将其作为确定规则移入确定规则集 R2 中。见表 8。 表 8 条件属性数目为 2 的候选集 3 

决策属性 (e,1) (e,2) (e,3) 条件属性 (b,1)(c,2) (b,1)(d,2) (c,2)(d,2) (b,2)(c,1) (b,2)(d,2) (c,1)(d,2) (b,1)(c,1) (b,1)(c,2) (b,1)(d,2) (b,2)(c,1) (b,2)(c,2) (b,2)(d,2) (c,1)(d,2) (c,2)(d,2) 规则支持度 2 2 2 2 2 2 4 2 1 1 5 2 1 2 属性支持度 4 4 4 3 4 3 4 4 3 3 5 4 3 4 确定规则 # # 四、形成条件属性数目为 3 的候选集 C3。对 C2 进行扩展，将表 8 中决策属性相同的每两项 结 合 成 条 件 属 性 数 目 为 3 的 项 。 计 算 各 规 则 的 属 性 支 持 度 和 规 则 支 持 度 。 表 中 (b,1)(c,2)(d,2)(e,1)和(b,2)(c,1)(d,2) (e,2)的规则支持度等于属性支持度，将其作为确定规 则移入确定规则集 R3 中。在表中(b,1)(c,1)(d,2)(e,3) 的规则支持度等于属性支持度，但在 R2 中有一条规则(b,1) (c,1)  (e,3)包含该规则，故将其删去。同理，(b,2)(c,2)(d,2)(e,3)也 被(b,1)(c,1)(e,3)所包含，故也将其删去。属性数目为 3 的候选集 C3 参见表 9, 表中用×表 示该规则已被删去。 表 9 条件属性数目为 3 的候选集 决策属性 (e,1) (e,2) (e,3) 条件属性 (b,1)(c,2)(d,2) (b,2)(c,1)(d,2) (b,1)(c,1)(d,2) (b,2)(c,2)(d,2) 属性支持度 2 2 1 2 五、条件属性数目为 4 的候选集 C4 已为空，算法到此结束。 六、最后将所有 Rk 合并得到约简表 10。 规则支持度 2 2 1 2 确定规则 # # × × 表 10 经过约简后的决策表 U 1 2 3 4 5 b — 2 1 2 1 c — 2 1 1 2 d 1 — — 2 2 e 3 3 3 2 1 规则支持度 9 5 4 2 2 从该表中我们可以看到，经过约简之后形成如下规则： 支持度 9 (季节，冬春)  (何种感染，呼吸道) (既往病史，慢性病)  (手术，有)  (何种感染，呼吸道) 支持度 5 (既往病史，无)  (手术，无)  (何种感染，呼吸道) 支持度 4 (既往病史，慢性病)  (手术，无)  (季节，夏秋) (何种感染，胃肠道) 支持度 2 (既往病史，无)  (手术，有)  (季节，夏秋) (何种感染，术后伤口) 支持度 2 4 

5 总结 粗糙集理论是分析不完整、不精确的信息系统和决策支持系统的有力工具。在粗糙集理 论中，约简是非常重要的一个研究课题。本文研究了已有的粗糙集约简算法，分析了这些算 法中存在的问题，提出一种粗糙集约简算法，该算法以实用性作为设计目标，重点不在于求 得最佳属性约简，而在于求得满足用户需求的最佳值约简，同时对支持度不同的规则分别 作不同处理，以满足用户的不同需要。该算法主要针对某些类型的实用系统进行值约简。利 用该算法进行院内感染系统的数据挖掘，该算法的性能良好，挖掘出的结果基本符合日常生 活，具有很好的实用价值。 参考文献 [1] 曾黄麟. 粗集理论及其应用[M]. 重庆：重庆大学出版社, 1996. 1－60. [2] 韩祯祥,张琦,文福拴.粗糙集理论及其应用综述[J].控制理论与应用,1999,16(2): 153-157. [3] 杜金莲,池忠先,翟巍.基于属性重要性的逐步约简算法[J].小型微型计算机系统, 2003, 24(6):976-978. [4] R.Agrawal, R.Srikant. Fast algorithms for mining association rules[C]. Proceedings of the 20th VLDB Conference, Santiago,Chile. Sep 1994. 487-499. T.Y.Lin. Rough set theory in very large databases[C]. In Proceedings of CESA’96, 1996, [5] volume 2, pages 936-941. 5