关联规则与粗糙集结合的约简算法（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∩Ｘ≠ }
集合 BN
R
(X)= R
-
(X)- R
-
(X)称为 X 的 R 边界。
我们也把 pos
R
(X)= R
-
(X)称为 X 的 R 正域，把 neg
R
(X)=U- R
-
(X)称为 X 的 R 负域，把
BN
R
(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 中，t
m
、t
n
分别为规则 m 和规则 n 的条件属性，s
m
、s
n
分别为规
则 m 和规则 n 的决策属性，若 s
m
＝s
n
，并且 t
n
Í t
m
，则称规则 m 被规则 n 所包含。
输入：决策表 DT
1
评论1