基于依赖度求解属性约简的方法

( 4) D 对属性集 { b, c} 依赖度为 c (D ) = 8 / 8 = 1 . 为了求解属性集依赖度, 作者在文 [ 3] 中提出了 ASDM 算法 , 由该算法可分别求得决策属性集 D 对 单属性、 二属性集的依赖度 , 分别见表 2 、 3 .
表 2 决策属性对单属性的依赖度 属性 依赖度 a 0. 25 b 0 . 375 c 0. 375 d 0 表 3 决策属性对二 属性集的依赖度 属性集 依赖度 ab 0. 75 ac 0. 375 ad 0. 75 bc 1 bd 0. 5 cd 1
33
性集. 传统的依赖度的定义 , 依然满足求解属性集依赖度的要求. 设 P 与 Q 是全域 U 上的等价关系簇集, 如果 Q 的所有种类都可以用 P 的种类来定义 , 则由 P 可以得到 Q, 即 Q 依赖于 P. 若从知识 P 中可部分 推导知识 Q, 或者知识 Q 有部分是依赖于知识 P 的, 称作知识 Q 对知识 P 的部分依赖性 . 定义 4 设 K = ( U, R ) 是一个近似空间, 且 P, Q 识 P, 记作 P Q, 当且仅当 k = rp (Q ) = R, 称知识 Q 以依赖度 k ( 0 k 1 ) 依赖于知
粗糙集合理论作为一种新的处理不确定性的有效数学工具, 在计算机科学与技术领域中发挥了重 要的作用. 该理论由波兰数学家 P aw lak . Z于 1982 年首先提出, 并在 20 世纪 90年代得到快速发展. 在粗糙集合理论中, 知识的约简有两种方法. 一种是按定义求解, 另一种是分辨矩阵求解. 按定义计 算所有约简已被证明是 NP - 完全问题 , 无法实际应用. A. Skow on 于 1991 年提出分辨矩阵方法 , 该方法在求解过程中, 需要比较任意两个非同决策对象的 所有属性值 , 会产生海量矩阵元素, 占用大量存储空间 , 且时空性能差 . 近年来, 很多学者对分辨矩阵的 方法进行了改造 , 包括矩阵本身的构造和算法 . 但无论怎样改造, 都无法从根本上改变分辨矩阵法时空 性上存在的缺陷 . 作者从传统属性依赖度概念出发 , 对属性集和属性集依赖度两个概念进行了扩展 , 提出了通过属性 集依赖度求解知识约简和知识核的新方法 , 即依赖度法 . 实验证明 , 依赖度法的时空性能比分辨矩阵法 优越得多, 依赖度法是独立于定义求解分辨矩阵法之外的新的方法 .
策对象比较次数为 R, R = Cm - (Cm 1 +
2
2
+ Cm n ) = Cm i= 1
2
2
Cm i ; ( 2) 存储过程 : 为了求最小析取范式,
2
由 ( 1)比较所得的每一个分辨矩阵元素都需要存储. 若采用数据表存储 , 这个数据表的记录数为 R; ( 3) 析取过 程: 对 分 辨 矩 阵 数 据 表 的 所 有 记 录 进 行 极 小 范 式 化 简 提 取, 各 记 录 间 需 要 正 反 比 较 R (R - 1 ) 次. 过程 ( 1) 、 ( 3) 耗时巨大, 而过程 ( 2) 需海量存储空间 . 基于分辨矩阵方法的缺陷 , 作者 从求解属性集依赖度出发 , 开辟了求解属性约简的新途径. 采用分辨矩阵的方法 , 可求出表 1 的核属性为 c, 两个约简分别为 cb 和 cd; 而表 3中 2个依赖度为 1 的二属性集恰恰就是 cb 和 cd. 作者对多个一致性决策表做了相同的计算, 都发现了这个相同的性质. 推论 依赖度为 1 的最小属性集就是决策表 C 属性的约简 . 依赖度法求解约简过程描述: ( 1) 从小到大, 依次计算所有单属性、 所有二属性集、 、 所有 n 属性集的依赖度 . 如表 1 中, n = 2 时 , 分别计算 D 对 ab、 ac、 ad、 bc、 bd、 cd 的依赖度 ; ( 2) n 为某一值时 , 若出现 1个或多个依赖度为 1 的属性集 , 则这 1个或多个属性集都是 C 的约简, 计算结束; ( 3) n 为某一值时, 若所有属性集的依赖度均不为 1 , 则继续计算 (n + 1) 属性集的依赖度, 直到找到; ( 4) 特别地 , 当 n = N 时, 条件全属性集 C 只有 1个 , 如果它的依赖度仍不为 1 , 则这个决策表不是 一致性决策表.
[ 1]
1 属性集、 属性集依赖度概念及属性依赖度的求解方法
定义 1 称 4元有序组 S = (U, A, V, f ) 为信息系统 , 其中 U 为所考虑对象的非空有限集合 , 称为论 域 ; A 为属性的非空有限集合; V = a A Va, 而 Va 为属性 a 的值域 ; f: U A V 是一个信息函数 , x U, a C A, f ( x, a ) Va, 对于给定对象 x, f ( x, a ) 赋予对象 x 在属性 a 下的属性值 . 定义 2 在信息系统 S = ( U, A, V, f ) 中, 若 A 可划分为条件属性 C 和决策属性 D, 即 C D =
[ 1]
D = A,
, 则称该信息系统为决策表. IND (C ) 的等价类称为条件类, I ND (D ) 的等价类称为决策类 .
在决策表中 , 条件属性或决策属性往往是由多个属性构成的 (只有单个属性构成的为特例 ), 研究 决策属性集对条件属性集的依赖度有着更加重要的意义 . 为区分传统属性集概念 , 作者对属性集概念作 以下扩展: 定义 3 决策表的条件属性或决策属性中, 2 个属性构成的属性集合称作二属性集, n 个属性构成 的属性集合称作 n 属性集 , 所有条件属性构成的属性集合称作条件全属性集 (C ) , 所有决策属性构成的 属性集合称作决策全属性集 (D ), 这些属性集都称作多属性集. 特别地, 属性集只含单个属性, 称作单 属性. 因决策属性集和条件属性集的构造方法及分类方法相同, 作者只对多个条件属性构成的条件属性 集依赖度进行研究, 决策属性集 D 是由单属性构成的 , 下文所述属性集 , 如果无特别指出 , 均指条件属
表 5 依赖度法与 分辨矩阵法时空性能比较实验值 数据集名称 文 [ 4] 表 1 UC I- Iris UC I- Balance U C I- M ushroo m U C I- M ushroo m U C I- M ushroo m 某借书数据表 1 某借书数据表 2 记录数 /m 条件属性数 /N 35 150 625 8 124 8 124 8 124 100 000 1 000 000 8 4 4 11 14 22 6 6 依赖度法索引次数 255 15 15 2 047 16 383 4 194 303 63 63 依赖度法耗时 / s 分辨矩阵法第 1 步耗时 / s 0. 938 0. 078 0. 141 131. 562 1 336. 406 566 020. 947* 125. 357 1 222. 676 0 . 094 0 . 719 9 . 734 3951 . 833* 5 789 . 346* 8 539 . 056* 441 989. 889 * 143 402 895. 314*
属性集依赖度的研究 , 给出了从 属性集依赖度出发求解属 性约简 和核的 方法 , 即依赖 度法 , 开辟了 独立 于分辨矩阵法之外又一新途径 . 研究表明 , 依赖度法的时空性能比分辨矩阵法更加优 越 . 关键词 : 粗糙集 ; 属性集 ; 依赖度法 ; 时空性能 中图分类号 : T P301 文献 标识码 : A 文章编号 : 1000- 2162( 2008) 04- 0032- 04
* *
C | m ij = { a}, 1 { m },若 C
* ij
*
, j i
n}
*
=
C, 对所有 m ij
,C
m ij
*
,且
34
2
安徽大学学报 ( 自然科学版 )
2 2 2
第 32 卷
有条件属性值相比较的次数为 Cm , 所有同决策对象比较次数为 Cm 1 + C m 2 +
n
+ Cm n. 令任意 2个非同决
3 依赖度法与分辨矩阵法时空性能比较
设一致性决策表条件属性数为 N, 决策属性数为 1 , 对象数为 m. 对两种方法归纳, 得到依赖度法与 分辨矩阵法时空性能比较的理论值, 见表 4 .
表 4 依赖度法与 分辨矩阵法时空性能理论值比较 时 空性能 决策表索引次数 比 较次数 中间 值存储数 矩阵元 素比较次数 依赖度法最坏情况 2 - 1 使用 1 个内存变量 , 共比较
2 分辨矩阵方法的缺陷
定义 5 决策表分辨矩阵是一个对称的 n 阶方阵, 其元素定义为 m ij =
*
{a | a
C 且 f (x, a)
F (x j, a ) }, ,
* ij
( x i, x j ) ( x i, x j )
*
I N D (D ) I N D (D )
在构建决策的分辨矩阵时 , 若 x i , x j 不属于同一个决策 , m 是可以区分 x i , x j 所有属性的集合; 若 x i , x j 属 于同一个决策, m ij 为 . C 的 D 核是分辨矩阵中所有单个元素 m ij 的并, 即 CORED (C ) = { a 定义 6 决策表分辨函数定义为 C 是极小子集, 则 C 是 C 的 D 约简 . 设一致性决策表按决策属性被分为 n 个等价类 , 各等价类包含的对象数分别为 m 1, m 2, m2 + , m n (m 1 + + m n = m ). 由定义 5 、 6可知, 分辨矩阵法求解包括 3个过程: ( 1) 比较过程: 任意两个对象的所
N (m - 1 ) ( 2 - 1) 次 0 N
分辨矩阵法 ( 第 1 步 ) 0 使用 (N + 1 ) 个内存变量 ,
2 共比较 Cm 次 2 Cm 2 2 Cm ( Cm - 1)
0
由表 4 可见, 依赖度法后 2 项的值都为 0 , 而分辨矩阵法的后 2 项都为巨值. 作者将依赖度法求解全 过程与分辨矩 阵法 的第 1 步进行 了比 较实 验. 实验 是以 P4, 3 . 1 GH z , 512 M 内存 为硬 件环 境, 以 W in dow s V ista 、 VFP9 . 0 为软件开发环境, 比较结果见表 5 .