（应用数学专业论文）关于粗糙集理论中若干问题的研究.pdf

摘要 波兰数学家z p a w l a k 提出的粗糙集概念，可以看作古典集合概念的扩展，足用来 表征和处理不完全不确定信息的工具。粗糙集与在该论域上的等价关系密切相关。一个 给定的论域的子集可以用上下近似描述。上下近似是由等价类构成的。下近似是包含在 集合中的等价类的并集，而上近似是所有与该集合有非空交集的等价类的并集。自然要 i 刈，若用代数结构代替论域，将会有什么结论。本文定义了粗糙集的并、交、补和粗糙 子集的概念，讨论粗糙集和环论的关系，在环中引入了相对于理想的上下近似、粗糙子 环和粗糙理想的概念，并证明了他们的若干性质。 决策表的简化方法是粗糙集理论中的另一重要内容。本文首先给出了计算决策表的 所仃舰则的所有约简的一种算法。以此为基础从三个不同的角度( 即最小算法包含的约 简数最少，或其中每个约简所含合取项最少，或其中所有约简的合取项数之和最少) 讨 论了最小算法的优化问题，分别证明它们是n p h a r d 问题，给出了最小算法三种优化问 题的启发式算法，并对其时间复杂度进行了分析。 关键词粗糙集环理想决策表约简n p h a r d 问题启发式算法 a b s t r a c t i nt h i sp a p e r , f i r s t l y , ar e l a t i o n s h i pb e t w e e nr o u g hs e t sa n dr i n gt h e o r yi sd i s c u s s e d i n f a c t 也en o t i o no fr o u g hs u b r i n g ( r e s p i d e 扪w i t hr e s p e c tt oa l li d e a lo far i n gi si n t r o d u c e d a n ds o m ep r o p e r t i e so f t h el o w e ra n dt h eu p p e ra p p r o x i m a t i o n si nar i n ga r ep r o v e d s e c o n d l 弘a na l g o r i t h mf o rc o m p u t i n ga l lr e d u c t so fe v e r yd e c i s i o nr u l e i nad e c i s i o n t a b l ei sp r o p o s e da n dp e r f o r m e d t h e nt h r e eo p t i m a lp r o b l e m so ft h em i n i m a la l g o r i t h m so fa d e c i s i o nt a b l ea r ei n v e s t i g a t e da n dt h e i rn p h a r dn a t u r ei sp r o v e d 。a n dt h r e eh e u r i s t i c a l g o r i t t u n sf o rt h et h r e eo p t i m a lp r o b l e m sa r ep r e s e n t e da n dp e r f o r m e d k e yw o r d s ：r o u g hs e t s ，r i n g ，i d e a l ，d e c i s i o nt a b l e s ，r e d u c t s ，n p h a r d n e s s ， h e u r i s t i ca l g o r i t h m s i i 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 八已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作背签名邀趣鱼e l 期：勉年仨月i 日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 i 、保密口，在年月日解密后适用本授权声明。 2 、不保密留。 ( 请在以上相应方格内打“4 ”) 作者签名：逊日期：趁丝年三月曼 e 1 日期：丝年z 兰目主日 第1 章前言 第1 章前言 1 1 课题研究的背景 波兰数学家z p a w l a k 提出的粗糙集概念，可以看作古典集合概念的扩展，是用来 表征和处理不确定信息的工具。粗糙集与在该论域上的等价关系密切相关。在粗糙集理 论中，一个给定的论域的子集可以用上下近似描述。上下近似是由等价类构成的。下近 似足包含在集合中的等价类的并集，而上近似是所有与该集合有非空交集的等价类的并 集。自然要问，若用代数结构代替论域，将会有什么结论。k u r o k i 在半群中引入了粗糙 理想的概念。类似地，我们将在环中引入粗糙子环和粗糙理想的概念，还将给出环中上 下近似的一些性质。 决策表的简化，是粗糙集理论中的另一重要内容。所谓决策表的简化就是先对属性 进行约简，再对规则进行值约简，删去多余的规则，最后得到所谓最小算法。 但是，最小算法按其定义来说是不唯一的。那么，是否存在这样的最小算法，它包 含的规则的约简最少且每个约简所含的原子公式最少? 如果这样的最小算法不存在，怎 样修改它，使得符合新标准的最小算法存在? 如何求出这些最小算法? 1 2 本课题的工作、结果和意义 本课题在以下几方面展开工作并取得了一些结果。 ( 1 ) 相对于环的理想引入粗糙子环和粗糙理想的概念。 ( 2 ) 设计了一个算法，实现了p a w l a k 技术求决策表所有规则的所有约简的方法。 ( 3 ) 探索了决策表最小算法的三类优化问题，证明了它们是n p h a r d 问题。利用 j j 发式信息提出了它们的启发式算法，并予以实现。 本文定义了粗糙集的并、交、补和粗糙子集的概念，讨论粗糙集和环论的关系，在 环t 吲入了相对于理想的上下近似、粗糙子环和粗糙理想的概念，并证明了他们的若干 性质。决策表最小算法的三类优化问题的讨论有一定的实用价值和理论意义。 1 3 本文的结构 本文分为4 章。第一章首先介绍了课题的背景、所做工作、结果和意义以及本文的 组织结构。第二章对粗糙集理论的有关知识，作了简明的介绍。第三章在环中引入了粗 1 河北大学理学硕士学位论文 糙理想的概念，做了初步探讨，并得出了一些结论。第四章给出了一种求所有约简的算 法，并对决策表的最小算法进行了探索，研究了最小算法的三类优化问题，证明它们分 别足n p h a r d 问题，并分别给出了启发式算法。 第2 章预备知识 第2 章预备知识 为使本文具有一定的完整性和相对独立性，本章简要介绍本课题涉及到的粗糙集的 相关知识。 2 1 粗糙集简介 2 1 1 上近似、下近似及粗糙集 没u 是个非空集合，u 的一个划分p 是的非空子集构成的集类，使得u 的每一个 儿索包含在且仅包含在尸的一个元素当中。u 的一个等价关系是定义其上的个具有自 反性，对称性和传递性的二元关系。u 上的每一个划分可以导致队的一个等价关系 x $ 静x ，y 属于同一个等价类；反过来，u 上的每一个等价关系也可以决定一个上的 蝴m = 咖良，y e l h 。 定义2 1 ( u ，臼 u ，p 是u 的一个等价关系，称为一个近似空问。 定义2 2 设妙，口) 是一个近似空间，称尸 ) _ p p ) 尸 ) 的映射却r ： a p ，) = k ( j ) ，面( ) ) 为一个近似算子，这里堑( x ) = 扛eu 陋kc ， 一a p t ( x ) 2xe u l 4 一n x 分别称为_ 在妙，口) 中的上下近似。 定义2 3 xc u ，若满足鱼芝( 彳) = 4 ( z ) ，则称为可定义的。否则，称为粗糙集。 2 1 2 信息系统、决策表 基于粗糙集的数据分析的起点是信息系统。所谓信息系统就是一个数据表，表的列 用属性标识，行名为感兴趣的事物，行列交叉处为属性的值。形式上，我们用s = ( u ，a ) 表示信息系统，这里u 和a 为有限的、非空的集合，即论域，a 称为属性集。对于每 个属性a a ，把a 的所有值组成的集合称为a 的值域，记为圪。a 的子集b 决定u 上的 一个二元关系“b ) ，称为不可区分关系：沁力，( 印当且仅当对于每个a a 有 “( x ) = 目( y ) ，其中a ( x ) 代表属性a 在元素x 上的值。显然，( b ) 是一个等价关系。这个 等价关系决定的所有等价类的集合。构成u 的一个划分，记为u ，( b ) ，或u b 。，( 圄决 洞北大学理学硕士学位论文 l _ _ _ _ _ _ _ - - - l l - _ - - _ l 口_ - _ _ _ _ _ i i i i l _ _ - _ _ _ l _ _ _ _ _ _ _ 自自i ，目| 定的等价类中包含x 的等价类记为雪( 茁) 。 如果( x ，y ) x ( b ) ，我们称x 和y 是b 不可区分的。 ，( b ) 决定的等价类称为曰基本 集或8 颗粒。 如果在一个信息系统中，属性集分成了两个不相交的集合，分别称为条件和决策， 则这个信息系统称为一个决策表，记为s = ( u ，c ，d ) ，这里c 和d 分别是条件属性和决 策属性的集合。 21 3 决策规则、决策算法 本节我们用逻辑术语描述决策表。 设s = ，a ) 为一信息系统。对于4 的任一子集曰，称属性值对0 ，v ) 用逻辑与、逻 辑或和逻辑非连接得到的式子为一个公式，这里口b ，v 圪。并用f o r ( b ) 删 样公式组成的集合。 对于任意o f o r ( b ) ，我们用归虬表示在系统s 中满足公式的所有石u 组成的 集合，并称之为m 在s 中的意义。 任何一个蕴涵式。哼甲称为一个决策规则。这里中f o r ( c ) ，甲f o r ( d ) ，和甲 分别叫做公式的前件和后件。 若由呻甲在s 中为真，则称咖呻甲在s 中是相容的，否则，称为在s 中不相容的。 对决策规则中寸甲，如果中是一个c 基本公式，、壬，是一个d 基本公式，则称中斗甲是 一个c d 基本决策规则。 若o l 斗掣，中2 掣，斗甲都是基本决策规则，则决策规则 中。v m ：v v 。斗甲称为这些基本决策规则的复合决策规则。 任何一个决策规则的有限集称为一个决策算法，对应地，任何一个基本决策规则 的有限集称为一个基本决策算法。如果在一个基本决策算法中，所有的决策规则都是c d 规则，则称该决策算法是个c d 决策算法。 一个决c d 策算法在s 中是可许的，如果它是所有的可许c | d 规则所成的集合。 一个决c d 策算法在s 中是完备的，如果对每一个x u ，存在算法中的一个决c d 策规则中一甲，使得x 。m 、壬，；否则称该算法是非完备的。我们以后考虑的算法都 是可许且完备的。 2 1 4 核与约简 ( 1 ) 属性的核与约简 定义2 4 ( 相对正域) 设p 和q 是论域u 上的等价关系族，称p o s ，( q ) = u 只( z ) f u ，a 为等价关系族p 的q 一正域。 定义2 5 ( 可省、独立) 设p 和q 是论域u 上的等价关系族，r p 。若 p ( 蛤m i p ) ( d ( q ) ) = p 0 俘m ( p 一 r ) ( 刷d ( q ) ) ，则称关系r 在尸中是q 一可省的，否则称为 q 一不可省的。如果j p 中每个关系都是q 一不可省的，则称p 关于q 是独立的，否则称为 依赖的。 定义2 6 ( 相对约简、相对核) s p 称为_ p 的q 一约简，当且仅当s 是p 的q 一 独立的子集，h p o s 。( q ) = p o s 口( q ) ；p 中所有9 一不可省的关系的集合，称为p 的o 一 核，记作c o r e o ( p ) 。 定理2 7p 的q 一核等于p 的所有q 一约简的交集，即c o r e 。( p ) = n r e d 。( p ) 。 ( 2 ) 决策规则的核、约简 设o _ v 为p qj 观8 1 ，d p ，当且仅当 。中一t f 蕴涵 。巾1 ( p 一 口) ) 呻甲，我们 称属性口在规则m 一、壬，中是可省的。否则，称a 在规则中斗、王，中是不可省的。 在规则巾呻甲中，若所有属性是不可省的，则称规则巾- - 4 , 甲是独立的。当巾- 9 , 甲 是独立的，且 。巾_ 甲蕴涵 s m 陋斗甲时，属性子集r p 称为规则m 甲的约简。 此时，r 称为既约的。 m 一_ 的所有不可省的属性的集合称为规则中哼、王，的核，电作c o r e ( o 呻掣) 。 定理2 8c o r e ( o 寸甲) = n r e d ( o 一甲) a 其中，r e d ( q d 寸甲) 是m 专甲的所 有约简构成的集合。 ( 3 ) 最小算法概念 设s = ( u ，4 ) 是一个信息系统，f 是一个基本算法，以r 表示算法f 中所有具有 后件甲的基本规则的集合；以岛表示日中所有规则的前件的集合。 算法f 中的一个规则中- - 4 甲是可省的，如果 。v 岛s v ( 岛一 卿) 。否则，称该规 则是不可省的。如果r 中的所有规则都是不可省的，则称目是独立的。 e j 可北大学理学硕士学位论文 _ _ _ _ _ _ _ l - _ _ - _ l - - l _ _ - _ _ l - l _ _ l _ _ - - - _ - _ - i _ l _ _ _ _ _ i i _ - _ _ _ 日_ 自_ _ l | i _ _ r 的一个子集乓称为目的一个约简，如果目是独立的，且 。v 0 ；v p 甲。 个决策规则集r 称为既约的，如果它是自己的一个约简。 一个基本算法f 称为最小算法，如果其中的每一个规则是既约的且对每一个决策 规则由- 甲，乓是既约的。 因此，为了简化一个c d 算法，我们首先必须进行整体属性约简，再对每一个规 则进行规则约简，最后从算法中去掉多余的规则。 第3 章环中的粗糙理想 第3 章环中的粗糙理想 3 1 粗糙集的并，交，补及粗糙子集 定义3 1 设4 = 乜，j l b = 也，百) 是两个粗糙集，定义a u b = 乜u 旦，j u 百) ， 。4r t b = 乜n 垦，j n 百) 爿c _ b 营彳n b = 爿。 当a 互b 时，称爿是口的粗糙子集。因此，a 是曰的粗糙子集当且仅当a 的上下近 似分别是b 的上下近似的子集。粗糙集的包含关系具有普通集合包含关系的性质。 类似地，定义粗糙集的补集如下4 。= 乜。，j 。) ，定义爿和口差集 爿一b ；乜一百，j 一里) 3 2 粗糙子环和粗糙理想 设r 是一个环，是胄的一个理想，是r 的一个非空子集。称 一a p r ，( x ) = 扛月卜+ ，x l 鬲，( ) = 仁r i ( x + 1 ) n x 分别为x 相对于，的上下 近似。 设，是r 的一个理想，a , b e r 。如果a b j ，则称a ，6 关于模j 同余，记作 s6 ( m o d ，) 。容易看出，同于关系口- - - b ( m o d i ) 一个等价关系。因此，当u = ，而臼 为 葑述同余关系时，近似空间p ，口) 就成为( r ，j ) ，j 的上下近似记为型，( z ) ，却，( 爿) 。 命题3 2 设( r ，) 是一个近似空间，一，b r 是任意两个子集合，则 ( 1 ) 生( x ) ，劬，( x ) ( 2 ) 坐) 。妒2 缈删) ( 3 ) a p _ 5 舻) 2 r 2 却7 朋) ( 4 ) 若爿曰，则坐) 垒p ) ，一a p t ) 面邝) 由上述命题，立即可得 引理3 3 对任意近似空间( 尼j ) ，- 一一 河北大学理学硕士学位论文 t _ - _ l - - - _ _ l - _ _ - l _ _ _ - - l _ _ _ _ _ - _ _ _ i l -_ i _ _自i _ _ ( 1 ) 对任意爿至r ，堑，( 彳) ，劬，( 4 ) 都是可定义的集合； ( 2 ) 对任意x r ，x + 是可定义集合。 对 r 的非空 子集 a , b ， 我们 引 入 记号 一台= 缸。6 。+ a 2 b ：+ + a b 。k e n ，口，4 ，b ；b 命题3 4 设，是r 的理想，a , b 是r 的非空子集，那么面，( a ) a p r ，( b ) = a p r ，( a b ) 。 i f _ 明：设x a p r ，) a p ，( 扪，则存在a i a p r ，( 爿) ，b ，面，( 曰) 使得 x 2 ：- q 五。因此，如，+ 1 ) c t a 妒，( 6 ，+ i ) n b ，故对1 f 行，存在- q ，+ ) r 、a ， 只s 够，+ j ) n 曰 ，有：，一_ y 一4 丑 。又2 ，”二a ，6 十 ，故 ( x + 1 ) n a b ，x 丽( 一丑) ，所以石，( a ) 一a p r 舻) 丽( 一扪。 反过来，设x a p r , ( a b ) 。因g + i ) n a b ，故存在y x + ，y a b ，使得 少。：；。，皿，口t 爿，6 ；曰。故有z y 十，= 二口，6 t + ，= ：。( q + ，) p ，+ n ，进而存在 x ，日，十，_ y ，6 ，+ ，使得z = ：l x c m 。由于口。( 茸，+ ，) n 爿，6 ，( m + ，) n b ，便有 。r 爿，( a ) ，y ，a p r ，( 扪 ， 进而有 x a p r ( a ) a p r ，( 斟 。 因此 a p r , ( a b ) 仁_ 一a p r ) 面，( 扪。 根据a + b 的定义，对命题3 4 的证明稍做修改可得 命题3 5 设，是r 的理想，爿，b 是r 的非空子集，那么 万川) + 万，( b ) = a p r ，( a + b ) 。 命题3 6 设，是胄的理想，爿，曰是五的非空予集，则有尘型( 彳理堕( 动熟( 爿动。 证明：对任意x 生翌( 爿) 尘翌( 戚，存在a i 爿，包b 使x = ：。q 矗。因此 “，十，爿，6 ，+ ，日，1 j 5 门 。 因为 e t 1 ( 口t + ，) ( 6 i + ，) 一曰 ，故 ：t q 6 ，+ 72 。+ k a b 。所以雅一a p r , ( a b ) 。 。，。，：，。，。，。i!二：l_。i：21：92i!。，一i一 ! 目e ! ! ! ! 自目= ! 目自目l _ 目- _ _ _ _ l _ _ _ 日l e ! - _ 口! _ e = _ _ e 口o = 日一 利用a + b 的定义，对命题3 6 的证明稍作修改可得 命题3 7 设，是r 的理想，哇，丑是r 的非空子集， 则 丝堕( 彳) 兰堕( b ) a p r j ( a + 动。 不难证明 引理3 8 设f ，是晟的理想，j j ，a 是r 的非空子集，则 ( 1 ) a p _ s r ( 4 ) 堑，( m ； ( 2 ) a p r i ( a ) a p r s ( a ) 。 由引理3 8 易得如下推论 推论3 9 设，j 是r 的理想，j ，a 是r 的非空子集，则 ( 1 ) a p _ z _ r j ( 爿) n 丝j ( 一) ca p _ _ l 一( 爿) ( 2 ) a p t w ( 4 ) a p r t ( a ) n 4 p r j ( 爿) 命题3 1 0 设j ，是太的理想，则铆，( j ) 是r 的理想。 证明：设日，b a p t ，( j ) ，r r ，那么陋+ i ) n j 痧，( 6 + j ) n j ，因此存在 x ( 日+ j ) n j ，y ( 6 + d n i ，。由于j 是r 的理想，故5 一y j ， x y ( 口+ ，) 一( 6 + j ) = a 一6 + j 。因此一6 十j ) n j ，从而口一6 印7 ，u ) ，而且 蹦j ，r x ，+ ，) = r a + i ，故( r 口+ ，) n ，庐，r aa p t ，( n 。所以妒，( l ，) 是r 的 理想。 类似地，若，是月的理想，是月的予环，则妒，( j ) 是月的子环。 命题3 1 1 设，是r 的理想，则塑( j ) 是r 的理想。 证明：设a , b 堑，( ，) ，7 月，那么0 + ) ，( 6 + ，) ，。易知0 6 + ，) i ， ( ，口+ 惦，。因比口一6 生) ，恍a p _ _ z r ) 。 类似地，若是只的理想，l ，是r 的子环，则型，( ，) 是足的子环。 定义3 1 2 设，是只的理想，4 肼0 ) = 乜曼，( 彳) ，丽，( 爿) ) 是近似空间似，) 的一个 粗糙集。如果a p t ，( 椰，。妒7 ，( 4 ) 是露的理想( 或子环) 那么称4 研0 ) 是一个粗糙理想 ( 或粗糙子环) 。粗糙子环简称粗糙环。 从定义易得 推论3 1 3 ( 1 ) 设，j ：星i r 的理想，则p _ p ) 和却。( ，) 是粗糙理想； ( 2 ) 设，j a r 的理想，是胄的子环，则4 ( 卅是一个粗糙环。 命题3 1 4 设，l ，是晨的理想置是r 的子环，那么 ( 1 ) 一4 p r ，( k ) 一a p r ( k ) 主一a p r m ( 足) ： ( 2 ) a p r ，( 足t 丝，( k ) 2 墨堡，“( k ) 。 证明： ( 1 ) 设工e 万，( k ) 一a p r ，( 鼢，则存在qe 面肛) ，i 石肚使z = 和& 。 区j 此， r + ，) n k 妒， ( 6 一+ ，) n k 妒。故存在x ，y r 使石，( 口。+ ，) n k ， ，( 6 | + ，) n 世。由于k 是胄的子环，故二_ y t k 。 另外有 ：。一y ，：。( q + ，) ( 6 一+ j ) = ：。口，6 j + ，+ ，因此，( ：。q 6 。+ ，+ ，) n 足。故 6 ，万一( m 。 ( 2 ) 设。堑，( 茁) 坐。( 眉) ，则存在口，堑，( k ) ，b a p _ _ z 。( 足) ，使。= ：，q6 _ 。 睁“，+ ，k b ，+ ，k 前有二( 口；+ 顶6 j + ，) 量k砖：】q b ，+ ，+ l ，k k bk k k 因此“，+ ， ，+ ， 。故有乞f 1 1 ( 口一十坝6 j + ，) 量，或乙f = 】日，+ + l ，。 从而z t = 。a , b ，丝。( k ) 。 反过来，因为，5 ，+ z ，s l + j ，由引理3 1 0 可得型m ( 世) c _ n p _ ! r ，( 置) ， 丝一) c a p r ，( 囝。因此有垒一( k ) 坐一( k ) 堑) 堑 ( 鼢。 由于 a p t “，( 足) 是r 的子环，所以墨型，+ ，( 足) 鱼婴，( x ) 垒坚，( 足) 。 命题3 1 5 设，j 是五的理想，置是矗的子环。那么坐( 置) + 堑，( 拦) 2 堑一( k ) 。 证明：因为7 7 + ，g 1 + j ，由引理3 1 0 可得堑m ( k ) c a p r ，( k ) ：! 坐h ，( k ) c a p r ，( x ) ， p aa p t ，+ ，( k ) c a p r ，( k ) + a p z r ，( 石) 设56 a p r ( k ) + 彳p r ( 豳，则存在堂，( 目，6 堑，( 的使。：口枷。因此 l 暑k 矗+ j k ，从而x + i + j2 n + b + j + j = 。+ j + b + j g k 十x ；k ? 甄以 肫a p t m ( 鼢。 命题3 1 6 设，j 是月的理想， k 是r 的子环， 那么 a p r 一肚) + a p r ，( 幻= a p t “。( 鼢。 证明：因为，+ ，vc l + j ，由引理3 1 0 可得a p t j ( k ) g a p r m ( 足) a p r ，( 丘) a p r ，+ ，( 丘) 。所以：万，( 世) + 面；，( ) 面i ，+ ，( 足) 反过来，对任意石a p “( k ) ，有 + ，十j ) n k 妒。故存在口使 ( m + 帅足妒， 从而舢万，( 鼢。另外， 由于饿， 故 ( 训帅耳= 7 n 世妒，口e 面肛) ，所以x = - - o + ( h 口) 石肛) + 万朋) 设月，矗是两个环，厂：五呻r 是从r 到r 的一个同态映射。我们知道，缸矿是矗的 理想。 定理3 1 7 设r ，r 是两个环，：r _ r 是从月到r 的同态映射。若彳是r 的非空 子集，则，( 石埘( 一) ) = 刑) 。 证明：因为爿万n 圹( m ，故朋) 量厂( 面聊。 反过来， y e f ( a p r x , o , ( 一) ) ，那么存在6 x e r f 使口= x + 6 ，即x ：盯6 ，故有 ，2 3 ( 口) 一邝) 2 八口) 厂( m ，所以八面撕( 彳) ) g ，( 小 没：月哼靠是从詹到冠的同态映射，爿是冠的子集。显然，f ( a p r k 。矿( 彳) 厂) 但是，f 面的例子表明，般来说逝聊r o ) ( 御。 上下近似可用下述等价形式表示。 设 ， 是 r 的 理 想 ， 4 是 r 的非空 子集 ， 则 丝，( 爿) = 日+ ，”，爿) 面) = 疗+ ，胁加爿矿 命题3 1 8 设，是r 的理想，贝t 一a p t ，( ，是彤的理想。 证明：设口+ 7 ，b + ，e , t p r ，( n ，7 十。则( 口+ ，) n j 声，( 6 + ，) n ，妒，从 2 一 tp 而存在。( a + 1 ) n j ，y ( 6 + i ) n j 。由于j 是r 的理想，故z y ，r x j ，且 x y + ，) 一( 6 + ，) = 口一b + l ，麒er 0 + ，) 2r a + l 。 因此 一b + 1 ) n j ， ( ，n + ，) n j 妒。从而( 玎+ ) 一( 6 + ，) a p t ，( 以，p + 顸d + ，) a p r ，( n 。所以a p r ( l ，) r 是的理想。 容易证明 命题3 1 9 设，是r 的理想，a p r r ，( ，是的理想。 类似地，若，是r 的理想，是r 的子环，则丝，( ，及荔，( ，是的子环。 第4 章决策表最小算法的优化 第4 章决策表最小算法的优化 4 1 问题的提出 求出一个决策表的所有约简后，就可以组合出决策表的所有最小算法。但是，一般 来说，不必求出决策表的所有最小算法。按照剃刀原理“3 ，我们希望找到其中这样的最 小算法，它包含的约简最少且每个约简含的和取项最少。当一个决策表的每个规则的约 简各不相同时，我们确实可以从每个规则的约简中取出含和取项最少的约简，组成这样 的最优最小算法( 实际上，这种情况可视为下述三类优化问题的特殊情形) 。然而，在 多数情况下，决策表的某些规则会有相同的约简，这时，这种最优算法可能不存在。如 表l 是某个决策表的三个规则( 分别记为1 ，2 ，3 ) 的约简结果( 其中，a ，b ，c 是条件 属性，d 是决策属性) ： 表l 8bcd 111 1 1 +0 +1 21l 1 2 0 +l 3 +0 2 从中共可组合出四个最小算法：( 1 ，3 ) ， 1 ，2 ，3 ， 1 ，2 ，3 ) ， 1 2 ，3 ) 。其 中，第一个最小算法的约简最少，而第四个最小算法的每一个约简的和取项最少。 因此，我们定义以下决策表最小算法的优化问题： 1 最少约简问题：求决策表的约简最少的最小算法； 2 最短约简问题：求决策表的每个约简最短的最小算法； 3 最小规模问题：求决策表的各个约简的和取项之和最少的最小算法。 河北大学理学硕士学位论文 以下，我们分别证明它们是n p h a r d 问题，并分别给出它们的启发式算法。 4 ，2 最少约简问题 设决策表t = ( u ，a ) ，其中u 为论域，a 为属性的集合。可按以下算法求该决策表的 所有约简。 算法4 1 输入：决策表t = ( u ，a ) ，输出：决策表所有约简构成的表r r 约去可省的属性 2 。求t 中每规则的核，得到所有核组成的表 3 。对c 中的每一核，判断其是否为对应规则的约简。若是约简，将其记入r ；若 不是约简，则转4 4 4 用向核中逐步添加非核值的办法，求出该规则的所有约简组成的表r 。 设决镱表t ：( u ，a ) 共有n 个规则，分别记为l ，2 ，n 。各规则的约简结果如下 表2 l n ，1 ，2 ，1 ， 2 r 2 ，1 ，2 ，2 ，2 2 n 1 ，2 一， 令r 。= 乜。，1 ：， 矗坞= ，2 ，屹：，吒bl ，r = k ，：，r o j 。 可从每个 r ，i = 1 , 2 ，阼，中取出一个约简，组成一个最小算法冠+ 。这样可以作出所有的最小算法。 最少约简问题就是要找出其中基数最小的r 来。为证这是n p h a r d 问题，我们引入 定义4 2 ：设f 是一个有限集，x ，墨，x 。是f 的1 1 1 个非空子集。从x ，( i = 1 ，m ) 中各墩一个元素组成f 的一个子集y 。这样的y 不唯一。在所有这样的y 中寻找基数 最小的y - 的问题称为f 的最优元素选择问题。 1 5 已证明 第4 章决策表最小算法的优化 j i 理4 3 ；f 的最优兀秉选择问题是n p h a r d 问题。 由此引理，可证 定理4 4 ：最少约简问题是n p h a r d 问题。 汪明：令f 。r l u r 2 u u r 。z l = 矗，z 。= r 。，由引理可知，定理成立。 口 设决策表的约简结果如上表所示下面给出最少约简问题的启发式算法。 算法4 5 输入：决策表的所有约筒r ，输出；最小算法r _ m i n l 令q = r l ，坞，r 。 ，r m i n i 宣m ， 1 。统计每个_ ，i = 1 , 2 ，n ，= i l , i 2 , , - - , i 。在中出现的次数，即计算t “，j = ，其 中2 k = ：糍， 2 选择出现次数晟多的。并记为，即，满足r o ) = 硝哥h * ， 3 从n 中去掉包吉r 的所有集合，b p 4 - n = q 、忸? ，直，r ? r + r ? ，r 0 且令 一m i n l = 一m i n lv o p j ， 4 。若q m ，则转14 ；否则rm i n l 为所求决策表的最优算法。 4 3 最短约简问题 要求解最短约简问题，司以先将各个规则的约简中最短的约简取出构成新的集合 i ，月：。一r ，由于这些集合可能有共同的约简，再对这些约简的集合求出约简最少的 最小算法。因此，有 定理4 6 晟短约简问题是n p h a r d 问题。 证明：从各个规则的所有约简中取出最短约简构成新的集合矗i 琏，砖 至多需 要o ( n ) 步而由定理l 可知，从r l ，只，r ：中作出最简约简是n p h 问题。故最短约简 问题是n p h a r d 问题。 假设决策表的约简结果如表2 所示，可按如下算法求解最短约简问题： 算法4 7 输入：决策表的所有约简r ，输出：最小算法rm i n 2 16 对n 个原始规则做出n 个由晟短约简组成的集合r 。，r ：，一r 。 1 5 ，i 。一。一。耋2 ：耋皇兰兰! ! 圭：鲨銮。，。，。 2 按最少约简问题的算法，从r 。，r ：，r 。中得出最短约简问题的解。 4 4 最小规模问题 我们将最小算法中各约简的和取项的个数之和称为最小算法的长度。容易知道，约 简最少或者约简最短都不一定能使最小算法的长度最短。反之亦然。因此，最小规模 问题与前两类问题相互独立。 下面，我们用计算理论的技术证明最小规模问题是 n p h a r d1 9 题。 首先引入 旅行商问题嘲：已知城市集合为 g ，c ：，c o ，以及由非负整数d 。构成的对称矩阵 p ， 。，其中d , j 表示城市c ；与c j 之间的距离，要求找出这些城市之间的最短巡回路线。 6 已证明 引理4 8 ：旅行商问题是n p 完全问题 下面，我们通过将旅行商问题在多项式时间内归约到最小规模问题的方式证明 定理4 9 ：最小规模问题n p h a r d 问题 证明：首先，如下建立旅行商问题到最小规模问题的归约f ： 在旅行商问题中， 对r 城市c l ，存在它到其它n 一1 个城市的距离d 1 2 ，d 。，d 。令每个d 。，对应一个长度为 d 。，的约简1 ，这a a $ c ，对应一个约简的集合月。= “：，l ”， 。对于城市c 2 ，存在 它到其它n 一1 个城市的距离d z l ，d ：”，d 2 。，令每个d ：，对应一个长度为d 2 ，的约简， 且_ ，与_ ，各不相同。这a a $ c ：对应一个约简的集合胄：= 址，嘞，r 2 。) 。依次类推， 城市c 。对应一个约简的集合月。= k 。，厶：，。 。这里的n ( n 1 ) 个约简互不相同。 并且，从城市q 到e ，的旅行路线c f lc 2 对应r 。中的一个约简，从而一条巡回路线 c 。( 7 。c 矿- q c 。对应一个最小算法h ，。，f 。显然，这个归约的时间复杂度为 o k j ) + o o ) = o ( n2 ) 。 其次 ， 由于巡回 路线 c i , c f 2 c 。c 。 的长 度为 d 。：+ d 叫，+ + d = i _ 。：i + h b 卜+ i f ，这里h 表示约简的长度，而n 个约简的长度 之和即最小算法k ， 的规模。所以，在归约f 下，一个巡回路线吒q c 1 c 。 最短当切仅当最小算法r 【c 。c q e 。j 规模最小。 1 6 第4 章决策表最小算法的优化 这样，我们就在多项式时间内将旅行商问题规约到最小规模问题，因此，后者也是 n p h a r d 问题。口 设决策表的原始规则的约简结果如表1 所示令q = 球。，垦，r 。 ，r = o ，则可按以下算 法求出最小规模问题的解。 算法4 1 0 输入：决策表的所有约简r ，输出：最小算法r _ m i n 3 1o 统计每个勺在中的重复次数丁k j 和勺的和取项数目h e , 并计算= 丁屯圪； r m i n 3 = 中， 2 。找出使得最大的白并记为i ， 3o 令q = q 也? ，r ；，月? j ，这里r ? ，五- 并令r r a i n 3 = r m i n 3 w 如 ， 4 。若q 中，则转1 。：否则，r 即为所求 4 5 例子 我们用m a t l a b 语言对以上各算法编程，并在以下例子上运行： 例l 我们对m a c h i n el e a r n i n gd a t a b a s e s 中t a e 数据库的全部1 4 6 个规则进行最 少规则优化，得到由8 1 条约简组成的最小算法( 略) 。 例2 设决策表如表3 所示( 见下页) 。其中，a 1 ，a 2 ，a 3 ，a 4 ，a 5 为条件属性，d 为决策属性。对其进行最短规则优化得到最小规则为 a 4 2 l d 2 3 ，a 3 = 2 a 7 = 3 一d = 2 ，a 4 = 2 a 7 = l d = 3 a 2 = 2 a a 7 = 2 一d = 3 ，a l = l a 7 = 4 - - d = l ，a l = 3 a s = l - d = l ，a 5 = 3 a 6 = 2 一d = 2 ，a 3 = l a 5 = l - d = 2 ，a l = 3 a 7 = 3 一d = 2 ， a 6 = 3 一d = 3 例3 设决策表如表4 所示( 见下页) 。其中，a l ，a 2 ，a 3 ，a 4 ，a 5 ，a 6 为条件属性， d 为决策属性。经过最小规模优化后，得最小算法为 a 3 = 2 一d ：1 ，a 3 = l a 4 = l - - d = 3 ，a 4 = o d = 3 ，a 3 = l a 4 = 2 一d = 2 河北大学理学硕士学位论文 表3 t u l e a l a 2a 3a 4a 5 a 6a 7d 111223 o 4l 21222123l 32122o 13l 4 3l 2 2l 12l 5 ll 1 23 20 2 6l2124212 7211202l2 822121 40 2 932122132 1 01l1122o3 1 l1 1 212 4 13 1 212l13l03 1 3122 1 l00 3 1 42l1l3313 1 521 2l4 4 o3 1 6 2211o21 3 1 72221ll23 1 822 22 oo23 1 93lll2243 2 0311 2 43o3 2 l312133l3 2 23 2 1 14 4o3 2 332212343 2 4 3 2222223 1 0 - 第4 章决策表最小算法的优化 表4 r u ea la 2a 3 a 4 a 5d 12l11l3 22 1 l 0 13 322 11 l3 4 11l003 5l 1ll 0 3 6211212 7221 2 12 83 21212 93222ll 1 033221l i 儿 332 1 1l 1 23o 2 1l 1 4 6 以上三类优化问题启发式算法的时间复杂性分析 以最小规模问题为例，分析算法的时间复杂度设决策表的所有约简如表2 所示， 约简总数nf ，= s ，则算法的( 1 。) 需要o g ：) 步，( 2 。) 需要0 0 ) ，( 3 。) 和( 4 。) 决定的循环次 r 副 数最多为n 步。因此，整个算法的时间复杂度为 1 0 0 2 ) + 0 0 ) j = 刀o g 2 ) = o b 2 ) 。 同理，可分析其它两种优化算法的时间复杂度也是。扣2 ) 。 河北大学理学硕士学位论文 结束语 本文定义了粗糙集的并、交、补和粗糙子集的概念，讨论粗糙集和环论的关系，在 环中引入了相对于理想的上下近似、粗糙子环和粗糙理想的概念，并证明了他们的若干 性质。 其次，本文设计了一个算法，用来计算决策表的所有约简。并且，考证了决策表最 佳最小算法( 即所含约简最少，且每个约简最短) 不是对任何决策表都存在的。有鉴于 此，本文以三类次佳的最小算法为目标，讨论了最小算法的优化问题，分别证明了它们 是n p h a r d 问题，并给出了它们的启发式算法，分别对三个例子演示了优化结果。 最后，本课题下一步要做的工作是研究最小算法作为目标概念类的p a c 一可学习性。 参考文献 参考文献 1 n k u r o k i ，r o u g h i d e a l si ns e m i g r o u p s ，i n f o r m s c i 1 0 0 ( 1 9 9 7 ) 1 3 9 1 6 3 2 】聂灵沼。丁石孙代数学引论高等教育出版社2 0 0 2 3 】j i a w e ih a r t ，m i c h e l i n ek a m b e n 数据挖掘概念与技术机械工业出版社 f 4 zp a w l a k r o u g hs e t