（基础数学专业论文）粗糙集理论的推广及若干应用问题.pdf

粗糙集理论的推广及若干应用问题 摘 要 自z . p a w l a k 从1 9 8 2 年提出 粗糙集理论以来， 该理论的应用已引起了人们 的广泛关注. 在不一致信息系统研究中， z i a r k o提出了一种归类质量， 进而在 这种归类质量的基础上提出了 近似约简， 而由这种近似约简形成的决策规则 对一部分个体的归类会产生较大的偏差. 本文的工作之一是先将不一致信息 系统进行约简， 再形成近似决策规则， 这样能一定程度上缓解偏差. 众所周知， 无论是决策树分类器，还是粗糙集中的信息系统，都有一个共同的缺陷:都 会由于训练样本分布不均匀可能引起分类规则的不完全，导致分类出现 “ 盲 区” 。 北师大研究生李凤通过引入决策树模糊化及分支激活度的概念解决了决 策树的 “ 盲区”问题，本文的另一工作就是将这一思想引入到粗糙集中来， 使落入信息系统 “ 盲区”的个体不但能归类，而且有其合理性。 关键词:变精度粗糙集; 近似决策规则; 信息系统模糊化:规则模糊化;近似推 理 。 粗糙集理论的椎广及若 干应用问题 ab s t r a c t s i n c e r o u g h s e t t h e o r y w a s p u t f o r w a r d b y z .p a w l a k i n 1 9 8 2 ,i t h a v e a t t r a c t e d a c o n s i d e r a b l e d e a l o f a tt e n t i o n . i n t h e r e s e a r c h o f t h e i n c o n s i s t e n t i n f o r ma t i o n s y s t e m , z i a r k o p u t f o r w a r d t h e m e a s u r e o f q u a l i t y o f c l a s s if i c a t i o n a n d i n t r o d u c e d a p p r o x i m a t e r e d u c t s . s u c h d e c i s i o n r u l e s w o u l d p r o d u c e a b i g d e v i a t i o n o n a p a r t o f o b j e c t s . o n e m a i n a i m o f t h i s p a p e r i s t o r e d u c e t h e i n f o r m a t i o n s y s t e m , a n d f o r m a p p r o x im a te d e c i s i o n r u l e s t h e n . i t c a n a m e l i o r a t e t h e d e v i a t i o n . n o t o n l y d e c i s i o n t r e e c l a s s i f i c a t i o n s ,b u t a l s o i n f o r m a t i o n s y s t e m s a r e in c o m p l e t e d u e t o t h e d i s t r i b u t i o n o f s a m p l e s a n d t h e t r e e p r u n i n g ,w h i c h c a n p r o d u c e b li n d r e g i o n d u r i n g c l a s s i f i c a t i o n . l i f e n g i n t r o d u c e d t h e f u z z i f i c a t i o n o f d e c i s i o n t r e e a n d p r o p o s e d a n a d a p ti v e c l a s s i f ic a t io n a l g o r i t h m .a n o t h e r m a i n a i m o f th i s p a p e r i s t o i n tr o d u c e t h e i d e a i n t o i n f o r m a ti o n s y s t e m s . k e y w o r d s : v a r i a b l e p r e c i s i o n r o u g h o f i n f o r m a t i o n s y s t e m s ; ma t e r e a s o n i n g . s e t s ; a p p r o x i m a t e d e c i s i o n r u l e ; f u z z i f i c a t i o n f u z z i f i c a t i o n o f c l a s s i f i c a t i o n r u l e s ; a p p r o x i - 粗糙集理论的推广及若干应用问题 引言 当今， 社会已 经进入网络信息时代， 计算机与网 络信息技术的飞速发展使得 各个领域的数据和信息急剧增加， 并且由于人类的参与使数据与信息系统中的不 确定性更加显著. 如何从大量的杂乱无章的强干扰的数据中 挖掘潜在的有利用价 值的信息， 这给人类的智能信息处理能力提出了前所未有的挑战， 由 此产生了人 工智能研究的一 个崭新领域 一一数据挖掘 ( d m ) 和数据库知识发 现 ( k d d ) . 在d m 和k d d 诸多方法中 ， 粗糙集理论与方法是一种很有效的 方法， 因 为它无 需提供问题所需处理的数据集合之外的任何先验信息. 粗糙集理论是波兰数学家 z . p a w l a k 于1 9 8 2 年提出的一种数据分析理论。1 9 9 0 年前后， 由于该理论在数据 决策与分析、模式识别、机器学习与知识发现等领域的成功应用， 才逐渐引起世 界各国学者的广泛关注。 国 外的z . p a w l a k , , w . z i a r k o ，国内的 刘清教 授， 刘大有教授在这方面作了大 量的工作。 w . z i a r k o 6 1 提出近似约简的 概念， 从而利用近似约简来形成决策规则， 这种 方法对大部分个体的归类很有效。 但通过研究发现， 这种决策规则有时会对一部 分个体的归类产生较大的偏差。 本文的工作之一就是缓解这一偏差，因为 z i a r k o 提出的近似约简注重的是 ( 在q 精度下) 保持能归 类的 个体数目 的 相同。 研究发现: 有些个体原来不能 归类， 而利用近似约简却能归类。 有些个体原来能归类， 利用近似约简又不能归 类。 有些个体的归类甚至不在原来的决策类集里。 本文这方面的工作就是先将 各条件类进行约简， 再形成近似决策规则。 这样， 可以保证在任何精度下任何个体 都能归类且是在原来的决策类集里。同时， 将此方法运用到物种挑选问题中，得 到较满意的结果。 众所周知， 无论是决策树分类器， 还是粗糙集中的信息系统， 都有一个共同 的 缺陷: 都会由于训练样本分布不均匀可能引起分类规则的不完全， 导致分类出 现 “ 盲区” 。北师大研究生李凤通过引入决策树模糊化及分支激活度的概念解决 了决策树的 “ 盲区”问题，本文的另一工作就是将这一思想引入到粗糙集中来， 使落入信息系统 “ 盲区”的个体不但能归类，而且有其合理性。 粗糙集理论的推广及若干应用问 题 第1 章近似决策规则的形成及其应用 自z . p a w l a k 从 1 9 8 2 年提出 粗糙集理论以来1 1 ， 该理论的应用18 - 1 1 1 己引起了 人们的广泛关注。在对不一致信息系统的研究中， 前人做了一系列重要的工作， 且使用的方法也多种多样。 z i a r k o在变精度粗糙集的基础上提出 近似约简， 但在研究这种近似约简的 过程中发现:寻找近似约简很费劲。 s k o w r o n和 r a u s z e r 把这一问题称为n p 完全问 题2 7 1 ; 同 时， k o m o r o w s k i e t a l . 也 指出 一个 有， 个属性的 信息系统的 近 似约简的 数目 随m的 增加而增加迅速， 即数目 较大1 2 1 。在以前的研究中， 寻找近 似约简的文献有 1 7 - 2 4 0 尽管选取近似约简的文献也很多9 ,11 ,25 , 6 ， 但始终没 有一种令人完全信服的办法。 更重要的是这样的决策规则是以牺牲小部分个体的 正确归类为代价的， 本文提出的近似决策规则从一定程度上缓解了这一情况。本 文先介绍有关信息系统规则的约简;然后研究了用z i a r k o的近似约简在归类时 存在一些问题的基础上， 提出利用近似决策规则进行归类的方法， 并与 z i a r k o 的 决策规则进行比 较;最后是近似决策规则的应用。 1 . 1 有关约简的预备知识1,3 ,7 ,1 6 1 定义 1 设u是一个论域， a 是 属性集， a = p u q , p为 条件属性集， q 为决 策属 性 集， 则称t = n, a , p , q ) 是 信息 系统 ( 简称 决策表) 。 信 息 系 统 中 每 一 行 就 是 一 条 决 策 规 则 “ : d x ll = :;, d x iq 。 其 中 d x l， 表 示 u 中 的 个体x 关于属性集b的属性值。 定 义2称决 策规 则d x 是 一 致的 . 如 果 信息 系 统t 中 决 策规则d x 和咖( x s 力满 足 : 叫 ， 一 叫， 二 叫 。 = 叫 。 ; 否 则 ， 称 “ 是 不 一 致 如 果 信 息 系 统 t 中 每 条 规 则都是一致的， 则称t 是一致的;否则， t 是不一致的。 定 义3 设 t 是 一 致 信 息 系 统 ， d x : d x l， 二 d x j。 是 一 条 决 策 规 则 ， 如 果 去 掉 条 件 属 性 。 ， 所 得 到 决 策 规 则 叫p - lo 二 叫。 在 信 息 系 统 中 仍 是 一 致 的 ， 则 称 属 性 。 关 于 规则d x 是可省的;否则， 属性a 是不可省的。 定 义 4 设 t 是 一 致 信 息 系 统 ， 规 则 d x . a l， 二 叫 。 的 所 有 不 可 省 属 性 所 组 成 的 集 合称为 规则的 核 ， 记为c o r e ( d x ) 。 定 义5 设 t 是 一 致 信 息 系 统 。 对 规 则 d x : d x l， 二 叫。 有 : 若 存 在 p 的 子 集 r ， 规 则 叫 : 。 叫 。 在 t 中 是 一 致 的 ; 但 对 任 何 ; 的 真 子 集 b ， 叫 ， 二 叫 。 在 t 中 都 粗糙集理论的推广及若干应用问题 是 不一致的 . 则 称r 为 规则d x 的 一 个约 简， 记为r e d ( d x ) . 定 义6 设 t 是 一 个 不 一 致 信 息 系 统 ， 且 规 则 “ : d x l， 二 叫 。 在 : 中 是 不 一 致 的 如 果 删 去 属 性 。 ， 所 得 到 的 规 则 d x p _ (u ， 二 叫 。 在 t 中 不 会 增 加 新 的 不 一 致 ， 则 称 属性a 关于规则d x 是可省的:否则， 属性a 是不可省的， 规则 e e ( p ) ， 如 果 存 在矶e e ( q ) , 使 x . c 叽 成 立 ， 则 把 x . 归 为 决 策 类耳 ， 记 为x ; e l 优) ( 其 中 e ( b ) 为 u 关 于 属 性集b的等价类集)3 ,4 。 显 然 ， 当 t 为 一 致 信息 系 统 时 ， 对 任意戈e e ( p ) ， 一 定 存 在耳 e e ( q ) ， 使 x . c 叽 成 立但 当 t 为 不 一 致 信 息 系 统 时 ， 则 必 存 在 某 个 x ; e e ( p ) ， 不 存 在 任 何 艺 e e ( q ) ， 使 x ; c 耳 成 立 ， 即 存 在 条 件 类 不 完 全 包 含 在 任 何 一 个 决 策 类 中 。 这 时 ， 引 入变精度粗糙集的思 想: 只要求条件类中属于某决策类的 个体超过一定的比 例， 则把条件类的所有个体都归入该决策类。 引入变精度 个数) 。 121 ,6 e (0 .5 ,1 1 ， 记 p r(y , lx ,) 罕 ( 其 lp iz 代 表 集 合 z 的 元 素 的 归 类 方 法: o d p r ( y j ix i ) : ,6 = 戈 与供) ， 此 时 称 条 件 类戈以 精 度q 归 入 决 粗糙集理论的推广及若干应用问题 策 类 耳 ; p r 代龙 ) s 1 - 刀 劝 戈o l e 必 ) ， 此 时 认 为 条 件 类 x ; 在 精 度 q 下 一 定 不 属 于 决 策 类 y , : o l - q p r ( y ix ,) x , e l e ( y ; ) 1 . 3 . 2 多决策值规则的形成 传统的 变精 度思想中: 若对 给定的,l3 e ( 0 .5 , 1 ， 存在 某 个条件类戈， 对 任意 艺 e e ( q ) ， 都 有 p r ( y , l x ) _ , 6 ， 且 : 中 任 意 真 y , . y 子 集 都 不 具 备 这 一 性 质 ， 则 x o e l a y ) 例 如 : 给 定 ,8 e ( 0 .5 ,1 1 ， 若 p r ( y j i x , ) , i 且 p r ( y k ix ; ) 0 .5 ， 可 知 当 ,6 e ( 0 .5 , a , i 时 ， 能 形 成 单 一 决 策 值 规 则 ， x ; e l b ( y i ) o 能 形成双决 策值规 则的j6 取值范围 的 确定 算 出x ; 中 属 于 各 双 决 策 类 集的 个 体 比 例 ， 设 值 分 别 为 f 2 , 4 ， . . . , 属 k )22且 满 足 x)0,2) p l i - c a t i o n s , c a s e s t u d i e s a n d s o f t w a r e s y s t e m s , p h y s i c a - v e r l a g , h e i d e l b e r g , 1 9 9 8 , p p . 4 7 2 - 4 9 2 2 0 j . w r o b l e w s k i , c o v e r i n g w i t h r e d u c t s - a f a s t a l g o r i t h m f o r