（应用数学专业论文）基于粗糙集的数据分类及其在商业银行监管中的应用.pdf

重庆大学硕士学位论文中文摘要 摘要 粗糙集理论是8 0 年初由波兰数学家z p a w l a k 首先提出的一个分析数据的数 学理论。 作为一种新的数据分析方法，粗糙集理论能有效地分析和处理不精确、不一 致、不完整的各种数据信息，并且从数据信息中发现隐含的知识，揭示数据潜在 的规律。与其它经典数据分类方法相比，粗糙集有很多的优特点。 近2 0 年来，粗糙集理论有了长足的发展。它不仅在数学理论、算法设计上得 到不断的完善和提高，而且在其他领域也得到了成功的应用。 本论文首先较为系统地介绍了粗糙集理论的来源，优点，及其在理论、算法 和应用中的研究现状，利用粗糙集进行数学建模的整个流程等。 区分矩阵方法是一种能求出信息系统的所有约简的方法，但是这种方法的一 个巨大缺点是随着信息系统的维数的增高，其计算时间会发生指数级的上升。本 文根据不可区分关系，提出了不可区分矩阵的概念。在区分矩阵约简算法的启发 下，提出了一种基于不可区分矩阵的属性约简算法。这种算法根据不可区分与区 分两者之间的关系，在不可区分矩阵基础上先进行数据化简，然后根据两者互补 关系把不可区分关系又化回区分关系，得到约简。 决策规则的生成有许多种，但是大部分规则生成的方法都是针对条件等价类 进行分析，而很少有根据决策属性的类别特征进行分析的，本文利用a 不可区分 关系的概念，形成了a 决綮类，并在此基础上，构造了a 一决策矩阵，并且形成了 新的基于a 决策矩阵的规则生成算法和增量式算法。1 商业银行监管是由一系列定性和定量监管指标构成的，对商业银行进行分析， 本质上就是一种模式识别和数据分类。本文以把粗糙集方法应用到商业银行监管 中为实例，阐述了利用粗糙集方法进行数学建模的整个流程。 关键词：粗糙集，属性约简，决策规则，应用分析，商业银行监管 重庆大学硕士学位论文英文摘要 a b s t r a c t r o u g hs e tt h e o r y , a sam a t h e m a t i ca p p r o a c ho fa n a l y z i n gd a t a , w a sd e v e l o p e db y z p a w l a ki nt h e1 9 8 0 s a san e wd a t aa n a l y s i sa p p r o a c h , r o u g hs e tt h e o r yc a ne f f e c t i v e l yd e a lw i t ha l l k i n d so f i n a c c u r a t e ，i n c o n s i s t e n ta n di n c o m p l e t ed a t a i tc a nf i n do u tu s e f u li n f o r m a t i o n a n dr u l e i ni n f o r m a t i o ns y s t e m c o m p a r e dw i t ho t h e rc l a s s i cd a t ac l a s s i f i c a t i o n a p p r o a c h ，r o u g hs e t sh a v em a n ya d v a n t a g e s s i n c et h e19 8 0 s ，r o u g hs e t s i s f l o u r i s h i n gi ni t sm a t h e m a t i ct h e o r y , a l g o r i t h ma n da p p l i c a t i o n t l l i sp a p e r f i r s t l ys y s t e m a t i c a l l yi n t r o d u c e sr o u g hs e tt h e o r y so r i g i 丑 a d v a n t a g e s a n di t sd e v e l o p m e n t m a t h e m a t i cm o d e l i n gi n t e g r a t ef l o wu s i n gr o u g hs e ti sd e s c r i b e d i nt h ep a p e r d i s c e r n i b i l i t ym a t r i xa p p r o a c hc a ni n d u c ea l la t t r i b u t er e d u e t s b u tt h i sa p p r o a c h w i l lt a k em u c ht i m ei n 】l i g hd i m e n s i o ni n f o r m a t i o ns y s t e m t h i sp a p e rp r o p o s e st h e c o n c e p to fi n d i s c e m i b i l i t ym a t r i x ，t h e np r o v e st h er e l a t i o nb e t w e e nd i s c e r n i b i l i t ym a t r i x a n di n d i s c e m i b i l i t ym a t r i xa n di n t r o d u c e sa na t t r i b u t er e d u c t i o na l g o r i t h mb a s e do n i n d i s c e m i b i l i t ym a t r i x c o m p a r e dw i t hi n d i c e r n i b i l i t ym a t r i xa l g o r i t h m ，t h i sa l g o r i t h m g r e a t l yr e d u c e sr u n n i n gt i m ea n dm e m o r ys p a c e t h e r ea r em a n ya p p r o a c ho f d e c i s i o nr u l e sg e n e r a t i o n , b u tm a n yo f t h e r na r ef a c e d t oc o n d i t i o ne q u i v a l e n c ec l a s s t h i sp a p e rp r o p o s e st h ec o n c e p to fa - i n d i s c e m i b i l i t y r e l a t i o na n dp r o d u c e sa - d e c i s i o nc l a s s o nt h eb a s i s ，a - d e c i s i o nm a t r i xi sc o n s t r u c t e d ， a n dd e c i s i o nr u l e sg e n e r a t i o na l g o r i t h ma n di t si n c r e m e n t a la l g o r i t h mi sp r o p o s e d b u s i n e s sb a n ks u p e r v i s i o ni sc o m p o s e do f a l lk i n d so f r e l a t i v eq u a l i t a t i v ea n d q u a n t i t a t i v ei n d e x t oa n a l y z eb u s i n e s sb a n k s q u a l i t yi se q u i v a l e n tt od a s s i f yb u s i n e s s b a n k i nt h ep a p e r , r o u g hs e ta p p r o a c hi su s e dt op r o v i d eas e to f r u l e sa b l et o d i s c r i m i n a t eb u s i n e s sb a n kr a t i n g k e y w o r d s ：r o u g hs e t , a t t r i b u t er e d u c kd e c i s i o nr u l e ，b a n ks u p e r v i s i o n 重庆大学硕士学位论文1 绪论 1绪论 l 。l 粗糙集研究的起源 近十年来，随着计算机的应用与普及，各行各业都产生了越来越多的数据。 但是，人们对这些数据的解释与分析能力并没有随之同步提高。也就是说，所产 生的大量的数据并没有最终形成知识，以供相关各方利用。为了解决这一问题， 一种在某种可约束的条件下，应用数据分析和数据发现算法，从中获取某些特定 模式的新技术就应运而生了，这就是数据挖掘。数据挖掘是按照既定的业务目标， 对大量的企业数据进行探索、揭示隐藏其中的规律性并进一步将之模型化的先进、 有效的方法。数据分类是一种用于提取描述重要数据类的模型或预测未来的数据 趋势的数学方法。 粗糙集理论是8 0 年初由波兰数学家z p a w l a k 首先提出的一个分析数据的数学 理论。由于最初的研究是用波兰文发表的，因此，这项研究当时并未引起国际学 术界的重视，研究地域也仅局限于东欧各国。 作为一种具有极大潜力的知识获取工具，粗糙集理论在8 0 年代末吸引了世界 各国数据挖掘领域研究者的关注。从1 9 9 2 年至今，每年都召开以r o u g hs e t 为主 题的国际学术会议，国际上也成立了粗糙集学术研究会，并在i n t e m e t 上定期发表 公告，加速了粗糙集理论的发展与交流。由于粗糙集能够处理不精确、不完备、 不一致的信息，因此作为一种具有极大潜力的知识获取工具引起了数据挖掘领域 研究者的极大关注。 粗糙集理论是一种刻画不完整性和不确定性的数学方法，它能有效地分析和 处理不精确、不一致、不完整的各种数据信息，并且从数据信息中发现隐含的知 识，揭示数据潜在的规律。其数学假设是：某一特定范畴( 知识、数据等) 中的 每一个对象都能表示一定的信息，并且具有相同信息的对象是不可区分的。 目前进行数据分类的数学方法很多，例如统计学方法、判别分析方法、决策 树方法、模糊集方法、神经网络、遗传算法等。与其它数学方法相比，粗糙集有 如下优点： 它只是基于原始数据，而不需要任何额外的信息( 与统计方法中需要概率 分布，模糊集中需要隶属函数不同) ： 粗糙集方法不仅适用于分析定量属性，还适于分析定性属性； 它能够发现隐藏在数据信息后的重要事实，还能够把这一事实以自然语言 的形式一一决策规则形式表示出来； 通过粗糙集模型推导的决策规则集给予隐藏在信息表中的知识一个一般 重庆大学硕士学位论文 1 绪论 性的描述，并且消除了原始数据中的冗余信息； 根据粗糙集得来的决策规则是基于事实的基础上，因为每一个决策规则都 来自实际的样本中； 粗糙集的结果较易于理解( 与效用函数，占优关系不同) ，不需要解释一 些用户难以直观理解的技术参数。 1 2 粗糙集研究现状 目前，对应于粗糙集的概念发展了粗糙逻辑、粗糙代数等。粗糙集与其他相 关理论的联系也得到了研究和阐明，从而确立了粗糙集在数学中的独立地位。近 年来，粗糙集不仅在数学理论、算法设计上得到不断的完善和提高，而且在其他 研究领域也得到了成功的应用。 1 2 1 粗糙集理论的研究现状 目前粗糙集的理论研究主要集中于其数学性质。 ( 1 ) 粗糙近似算子的构造 文f 2 】中提出了基于邻域算子系统的粗糙集近似算子系统，使得传统的粗糙集 模型只应用于一步关系近似迈向多步关系近似迈出了实质性的一步。文【3 】中证明 了粗糙集具有s t o n e 代数结构。 ( 2 ) 粗糙集中的代数问题 文嗍利用代数方法讨论了两个信息系统同态下的不变特征。文5 1 中，作者在 商代数的意义下研究了粗糙集代数，并进一步研究了粗糙半群的概念。在文 6 】 中，作者在群中研究了粗糙模糊集的乘积结构，定义了粗糙t _ 模糊群。 ( 3 ) 粗糙集与拓扑空间的关系 文【7 】中讨论了粗糙集与拓扑空间的关系，提出了p a w l a k 粗糙集模型等价于 一类特殊的拓扑空间，一个拓扑空间对应于一个特殊的一般关系下的近似空间。 ( 4 ) 粗糙集理论中的度量 寻求个恰当的度量来刻画知识的不确定性也是粗糙集理论研究的一个重 要方向，文f 8 】中给出了粗糙熵的概念。 ( 5 ) 与其它不确定方法相互补充 对粗糙集模型进行的推广，例如模糊粗糙模型【们、随机粗糙模型 1 0 】、a - 粗 糙集【1 1 1 、变精度粗糙集【屹1 等。 1 2 2 粗糙集算法的研究现状 目前粗糙集的算法研究主要集中于属性约简的算法、决策规则生成算法。 ( 1 ) 粗糙集属性约简算法 2 重庆大学硕士学位论文1 绪论 文f b l 提出了基于区分矩阵的属性约简算法，文瑚提出了基于粗糙熵的属性 约简算法，文 1 4 钳论了信息的粗糙计算方法。 ( 2 ) 粗糙集决策规则生成算法 文 1 5 - 1 7 时论了决策规则生成的冗余决策规则算法、最小决策规则算法、强 决策规则算法，文【1 8 】讨论了不完全信息系统的最优决策规则算法。 ( 3 ) 粗糙集规则匹配算法 文f 1 9 】讨论了决策规则匹配的分类问题。文 2 0 1 中提出了一种值逼近关系的距 离测度。文2 1 疆出了一种规则间的占优关系。 1 _ 2 3 粗糙集应用的研究现状 目前粗糙集在许多领域中的应用都取得了成功。 ( 1 ) 在股票数据分析方面 、 文【2 2 1 应用粗糙集方法分析了十年间股票的历史数据，研究了股票价格与经济 指数之间的依赖关系，获得的预测规则得到了华尔街证券交易专家的认可。 ( 2 ) 模式识别 文1 2 3 】应用粗糙集方法研究了手写字符识别问题，提取出了特征属性。 ( 3 ) 地震预报 文阱】研究了地震前的地质和气象数据与里氏地震级别的依赖关系。 ( 4 ) 冲突分析 文 2 5 】应用粗糙集方法建立了反映以色列、巴勒斯坦、约旦、埃及、叙利亚 和沙特阿拉伯等六国关于中东和平问题各自立场的谈判模型。 ( 5 ) 从数据库中发现知识【2 6 0 7 k d d 又称数据挖掘( d a t a m i n i n g ) ，是当前人工智能和数据库技术交叉学科的研 究热点之一。粗糙集方法现己成为k d d 的一种重要方法，其导出的知识精练且更 便于存储和使用。 ( 6 ) 粗糙控制f 2 s - 3 4 1 粗糙集根据观测数据获得控制策略的方法被称为从范例中学习，属于智能控 制的范畴。基本步骤是：把控制过程中的一些有代表性的状态以及操作人员在这 些状态下所采取的控制策略都记录下来，形成决策表，然后对其分析化简，总结 出控制规则【2 8 j9 1 形式为：i fc o n d i t i o n = n 满足t h e n 采取d c c i s i o n = m 。粗糙集方 法是一类符号化分析方法，需要将连续的控制变量离散化，为此p a w l a k 提出了粗 糙函数的概念1 ，为粗糙控制打下了理论基础。文口1 3 2 1 应用粗糙控制研究了“小 车倒立摆系统”这一经典控制问题，取得了较好的结果在过程控制领域，文f 3 3 1 应用粗糙集方法成功地提取出了水泥窑炉的控制规则。粗糙控制的优点是简单迅 速、实现容易，不需要象模糊控制那样进行模糊化和去模糊化。因此在特别要求 重庆大学硕士学位论文1 绪论 控制器结构与算法简单的场合，采取粗糙控制较为合适。另外，由于控制算法完 全来自观测数据本身，其决策和推理过程可以很容易被检验和证实种新的有吸 引力的控制策略“模糊一粗糙控制( m 盟y - m u 曲c o n t r 0 1 ) ”正悄然兴起，其主要思路 是利用粗糙集获取模糊控制规则。 ( 7 ) 医疗诊断 粗糙集方法根据以往的病例归纳出诊断规则，用来指导新的病例现有的人工 预测早产的准确率只有1 7 3 8 ，应用粗糙集理论则可提高到6 8 9 0 t 弘l 。 ( 8 ) 专家系统 粗糙集抽取规则的特点，为构造e s 知识库提供了一条崭新的途径3 6 1 。 ( 9 ) 人工神经元网络。 训练时间过于漫长的固有缺点是制约a n n 实用化的因素之一。文 ”幢用粗糙 集化简神经网络训练样本数据集，在保留重要信息的前提下消除了多余的数据， 使训练速度提高了4 7 7 倍，获得了较好的效果文【3 8 - 3 9 1 将粗糙集与a n n 结合起来， 充分利用粗糙集处理不确定性的特长以增强a n n 的信息处理能力。 ( 1o ) 决策分析4 2 1 。 粗糙集的决策规则是在分析以往经验数据的基础上得到的。粗糙集允许决策 对象中存在些不太明确、不太完整的属性，弥补了常规决策方法的不足。希腊 工业发展银行e t e v a 应用粗糙集理论协助制订信贷政策，是粗糙集多准测决策方 法的一个成功范例。 1 3 粗糙集基本概念 为了研究的需要，本文先给出涉及粗糙集的一些基本概念【”1 。 1 3 1 信息系统、决策系统、区分关系 通常，数据是以关系数据库( 二维表) 的形式存储的。就象表格一样，每一 个表有许多条记录，每条记录有许多条属性，每一个属性表示待观察物体的某一 方面的性质。 定义1 1 信息系统 二维表s = ( u ，爿，v ，力被称为信息系统，其中u = 而，工) 是一个非空有限 集( 即记录集) ，称为范畴，a = d ，n 。) 是一非空有限集，称为属性集。a 中 的元素称为属性。矿= u 。圪，圪是属性口的值域。 定义1 2 信息函数 函数f ：u x 4 斗矿被称为信息函数，满足关系：f ( x ，吐) 圪，v a a 。 4 重庆大学硕士学位论文 1 绪论 在一个信息系统中，一般有两种不同的属性类，一种称为条件属性，一种称 为决策属性。 定义1 3 决策系统 信息系统被表示为s = ( u ，c ud ，v ，门，并且称为决策系统。此处c 是条件属 性集，d 是决策属性集。条件属性c 表示观察指标，而决策属性d 表示根据条件 属性所作出的判断指标。 定义1 4 不可区分关系 设s = ( u ，a ，v ，力是一信息系统，设p a ，x , y u 。在s 中我们说根据属性 集p ，工平吵是不可区分的，只要对于任意的属性a p 及任意的记录y u 满足 f ( x ，口) = f ，日) 。这样，对于每一个p a 在u 上生成的二元关系，我们称之为p 一 不可区分关系，记为，。 1 3 2 集合上、下近似、边界域 定义1 5 下近似 设p 互a ，y u ，集合l ，的p 下近似表示为r ，其定义如下： 一p y = 缸y ：i e ( 工) y ) ，即是指利用属性集p 判断肯定属于r 的( ，中元素 组成的集台。 定义1 6 上近似 集合y 的尸上近似表示为用7 ，其定义如下： p y = 扛y ：1 1 , ( x ) n y m ，即尸r 是那些利用属性集p 判断可能属于y 的u 中元 素组成的集合。 从近似的定义，我们可以直接得到上、下近似的下列性质： 定理1 1砑和蹦有下列性质： ( 1 ) _ e x x p x ； ( 2 ) 乡= 咧= 妒： ( 3 ) = p u = u ； ( 4 ) p ( x u y ) = p x u p y ： 重庆大学硕士学位论文1 绪论 ( 5 ) ( x ny ) = 譬n l r ( 6 ) r y r 旦： ( 7 ) 鼻y j 两匆； ( 8 ) ( 工uy ) 丛u 笪； ( 9 )_ ( n 】，) r n r ； ( 1 0 ) p ( - x ) = - p x ： ( 1 1 ) p ( 一砷= - p x ； ( 1 2 ) 旦( z ) = p ( x ) = _ p x ； ( 1 3 ) p ( p 石) = p ( p x ) = p x 定义1 7 边界域 集合y 的p 边界域表示为丑，( y ) ，其定义如下： 尉( y ) = p y 一 y ，即丑虬( y ) 是指那些利用属性集尸既不能判断肯定属于 y 又不能判断肯定属于u y 的u 中元素组成的集合。 集合的不精确性正是由边界域的存在引起的，集合的边界域越大，其精确性 越低。下面，我们引入近似精度和近似质量的概念。 例：在j 中，存在一属性集r i e ，其中u = 工1 ，工2 ，x3 ，x 1 0 ， x = x 1 如，工5 ，x 4 ，x 7 ，x 1 0 ) ，x u ，且r 有如下分类结果： e l = x 0 x l ；e 2 = 工2 ，x 6x g ；e 3 = ，x s ；e 4 = x 4 ，x 8 ) ；e 5 = 工7 ，x l o ； 蚪= e 3 u e 5 = x 3 ，x 7 ，x a o ； r x = e l o e 3 u e 4 u e 5 = 而，五，而，鼍，i ，而，五o ) ； b n e = e l u e 4 = 而，玉，x 4 ，黾 1 _ 3 - 3 近似精度和近似质量 定义1 8 近似精度和近似质量 s = ( u ，a ，矿，力，设p 是爿的一属性子集，y = f k ，e ，匕，l 是u 的一个划 分。此划分独立于属性集p 。子集e ( f _ l ，m ) 是u 的划分类。y 的r 下近似和上 6 重庆大学硕士学位论文 1 绪论 近似分别表示为：p _ y = 鲻，鹦，鹦，戥 ；p y = p z ，码，玛，巩 们= 哿一晰分类晶藤 ( y ) ：i 至车掣表示根据属性集p 对】，进行划分的近似质量。 注：当划分表示分类时，前者表示表示根据属性集p 对y 进行分类时，可能的 决策中正确决策的百分比；后者表示表示根据属性集p 对y 进行分类时，能准确划 入y 的分类中的对象的百分比。 1 4 本文研究的结构和内容 利用粗糙集方法进行数据分类分为几个子过程，而在不同的子过程中涉及到 不同的方法，因此下面将给出利用粗糙集进行数据分类的一般流程及在各子过程 中常用的方法。 图1 1 粗糙集建模流程图 f i g i 1r o u g hs e tm o d e l i n gf l o wc h a r t 本文的研究结构和内容如下： 第一章：介绍了粗糙集的来源，粗糙集的优点，粗糙集在理论、算法和应用 重庆大学硕士学位论文 l 绪论 中的研究现状以及粗糙集中的一些基本概念。 第二章：介绍了区分矩阵，以及在不可区分关系概念上建立了不可区分矩阵 和不可区分函数，并且在不可区分矩阵的基础上给出了基于不可区分矩阵算法， 给出了该算法的复杂度分析。 第三章：根据粗糙集理论，提出a 一不可区分关系的概念，建立了a 一决策表 及其a 一区分矩阵，利用决策函数，提出了一种在决策表中获取决策规则的算法。 并且提出在原有规则集的基础上进行规则和规则参数的增量式更新算法，这种算 法避免了为更新规则集而重新运行规则获取算法。 第四章：结合粗糙集方法，给出了该数据分类方法在商业银行中进行监管中 的应用。 重庆大学硕士学位论文 2 属性约简分析 2 属性约简分析 2 1 引言 属性约简是粗糙集理论的核心内容之一。我们知道，信息系统中属性并不是 同等重要的，甚至其中某些属性是冗余的。所谓属性约简，就是在保持现有数据 分类能力不变的条件下，删除其中不相关或不重要的属性。 一个信息系统中，在一般情况下，移去一些条件属性，信息系统不会产生歧 义，此类信息系统称为一致性系统。歧义是指两个记录有一样的条件属性值，但 是有不同的决策属性值，此类信息系统称为非一致性系统。本文讨论的是一致性 信息系统。当条件属性被移去而不产生歧义性时，信息系统就被认为可以化简， 化简后的系统被称为一个约简系统。 定义2 1 属性依赖性 设s = ( u ，a ，v ，力，p c u ，- 4 = 一，如果p p ，使得厶= i p _ ，则称p 为p 中 不必要的；否则称p 为p 中必要的。如果对v p p ，p 都是必要的，则称p 是独立的； 否则称p 为依赖的。 定义2 - 2 属性约简 设s = ，a ，v ，) ，p u ，r p ，如果月是独立的，且1 月= i e ，则称月为p 的 一个约简。p 的所有约简记为r e d ( p ) 定义2 3 核 设s = ，a ，v ，) ，p u ，令c o r e ( p ) = f l r e d ( p ) ，则称c o r e ( p ) 为尸的核。p 中 所有必要关系组成的集合成为户的核，记为c o r e ( p ) 。 从上面的定义可以看出，核的概念具有两方面的意义。首先，可作为计算所 有约简的基础，因为核包含于每一个约简之中，并且其计算是直接的。其次，核 可以理解为系统中最重要部分的集合，进行知识约简时不能删除它。 一般产生约简的方法是逐个向核中添加可省的关系，并进行检查。注意，可 省的关系集合的幂集的基数是多少，就有多少种添加的方式。最好的情况是所有 不可省的关系结合本身就是约简，此时的约简是唯一的。 目前求属性约简方法主要有两大类，一类是最小约简集算法，一类是次优约 简算法。最小约简集算法是求出信息系统的所有约简，在此基础上求出属性数最 小的约简。这种方法主要是在区分矩阵基础上进行化简，求出约简集，称为区分 矩阵法：次优约简法主要是一种启发式算法，它主要是从信息系统本身出发，根 据属性间的性质，求出某个或某些约简，称为启发式算法。 9 重庆大学硕士学位论文2 属性约筒分析 2 2 区分矩阵和区分函数 定义2 4 区分矩阵 设s = ( u ，a ，矿，) ，l u 胛。s 的区分矩阵是一n 片矩阵，此矩阵的元素值为： a ( x ，y ) = a a f ( x ，n ) f ( y ，n ) ) ，x ，y u ) 即a ( x , y ) 是区别对象衍吵的所有属性的集合。 区分矩阵消除了在分类中不起作用的信息，保持了信息系统中的差异信息， 直戏地表达了信息系统中记录间属性关系。 定义2 ，5 区分函数 设s = ( u ，a ，y ，门，如果d ( 工，y ) = q ，一吼) m ，则表达式口( 五y ) = u a ，； 如果。( y ) = 中，则表达式a ( x ，力= 1 ，区分函数表示如下： = 兀口( 工，y ) ( j ，y ) c = u x u 此处，a ( x ，y ) 正是区分矩阵中的一个元素 2 3 不可区分矩阵属性约简 本节根据不可区分关系，首次提出了不可区分矩阵的概念。在区分矩阵约简 算法的启发下，提出了一种基于不可区分矩阵的属性约简算法。这种算法根据不 可区分与区分两者之间的关系，在不可区分矩阵基础上先进行数据化简，然后根 据两者互补关系把不可区分函数转化为区分函数。 定义2 6 不可区分矩阵 设s = ( u ，v ，) ，j a | ：m ， u | _ m 。s 的不可区分矩阵是- - n x 疗矩阵，此矩阵 的元素值为： p ( x ，_ y ) = ( a l f ( x ，芦) = f ( y ，卢) ，x ，y 【，) 即声( x ，y ) 是对象x 和y 的所有不可区分属性的集合。 由区分矩阵与不可区分矩阵的定义，我们可以看到两矩阵中各项呈互补关系。 即设区分矩阵为尸，不可区分矩阵为q ，r 是一n x n 矩阵( 其中各项皆为整个属性 集4 = 缸，一矗。) ) ，贝有p + q = r ，其中口( x ，y ) + ( 工，y ) = a 。 定义2 7 不可区分函数 设s = ( u ，a ，v ，) ，如果卢( x ，力= ，以) m ，则表达式p ( x ，y ) = u p ， 1 0 重庆大学硕士学位论文 2 属性约简分析 如果芦( 五y ) - - - - - 中，则表达式f l ( x ，y ) = l ，不可区分函数表示如下： a i 。a = 兀f l ( x ，_ y ) ( z y ) e d z x u 由不可区分关系区分关系的互补性，我们得出区分函数也可以表示如下： = 兀( z - f l ( x ，_ y ) ) 定理2 1 m 1 设s = ( u ，4 ，矿，厂) ，区分函数为a ，设a 经运算后化为析取范式t ，即 i = v 只，其中只2 。，a e 为的一个合取范式，即e 中各元素为合取关系， l 型s i k 为中合取范式的个数，则信息系统s 的约简为e ( i = 1 孟) 。 该定理给出了一种计算约简的方法，即将区分函数从合取范式化为析取范式， 则每个子式所包含的属性即构成一个约简。 定理2 2 吸收律 设a 是一集合，子集b 彳，且存在集合c ，d 满足，中c d 爿。如果有 c 曰，则必有 a ) 、d 2 君，4 一b 三爿一d ； b ) 、d n 曰= d u b = ( 彳一d ) u ( 4 一b ) = a b = b 此定理表明，当区分函数中各区分项间存在包含关系时，可以消除包含项， 这等价于在消除各对应不可区分项间的被包含项后，取各剩余不可区分项的补集。 定理2 3 分解律 设a 是一集合，子集c 量a ，o = l 上) ，且有口a ，如果对v i ， = 1 ，上) 都有： a ) e c i 则必有a c i = a ) v ( ( c 一扣) ) ) 。 这个定理表明如果各项之间存在公共元素( 属性频率 2 ) ，则可以提取各项之 间的公共元素以降低属性频率。 定理2 4 扩充律 设f = c l c 2 c ka c k + l q 。且有口爿， ) c i ，( f = 1 ，上) ， a ) 呸c i ，( _ ，= k + l ，h ) 则有： f 2 ( 仝g ) ( q ) 重庆大学硕士学位论文。 2 属性约简分析 j1 。( 口 v ( 仝( q 一 4 ) ) ) ) ( q ) hi“ 2 ( 扣 ( 企q ) ) v ( 个( c f 一 口) ) ( a q ) ) 2 4 基于不可区分矩阵属性约简算法 选择不可区分矩阵来取代区分矩阵进行化简，是因为不可区分矩阵在算法上有 巨大的优势。它能够在时间花销和存储空间上有较大的改善和提高。 设s = ( u ，a ，v ，门，i u i _ n ，l a m ，a a 是信息系统中一属性，吒是其值域， l i 是值域数。设信息系统s 中属性口含各属性值的数量为只( f = l ，一i 圪l ，则区 ，j = l l l 分矩阵中含口数量为d i s 。= 层0 ，不可区分矩阵中含口数量为 in：昙熏l霉(卑一】)，inin 1 i n + d i s 。：要1 ，| 如一1 ) 。我们取圪： l ，2 ，3 为例， 2 n , g = i 霉( 卑一】) ，s 。= i 库如一1 ) 。我们取圪= l ，2 ，3 为例， 。i = l 系统s 中属性口含属性值i ，2 ，3 的数量分别为毋，忍，只，由对称性可假设三者 满足以县弓，则存在如下关系： 1 ) 只+ 另+ 只2 n 2 ) 区分矩阵中含口数量：只b + 置x 只+ e b ( 2 1 ) ( 2 2 ) 3 ) 不可区分矩阵含口数量：( 只x ( 只一1 ) + 最x ( 只一i ) + p 3x ( p 3 1 ) ) 2 4 ) 当刀充分大时， n c d 设( 8 1 ) 一只，上式近似为； ( 置置+ 只b + 只x b ) 2 ( 2 3 ) 根据区分矩阵与不可区分矩阵的关系： a f n - 1 ) 5 ) 鼻b + 只b + 只只+ ( 只鼻+ b 最+ 只x p ，) 2 = 广 _ !( 2 4 ) 要使不可区分矩阵含属性d 数量小于区分矩阵含属性口数量，需满足条件 ( 2 3 ) 声表示决策规则“扩at h e n 卢”，模式口 称为规则前件，模式口称为规则后件。决策规则反映了条件属性集和决策属性之 间的关系。 由于对象约简定义了最小模式，所以从决策表中挖掘最小决策规则集自然是利 用约简作为基础： r u l ( s ，x ，d ) = b ( x ) + ( a 口= a 口( 功) ；占r e d ( s ，五，d ) e u l ( s ，d ) = ur u l ( s ，工，d ) x r d l 在实际应用中，当规则用于识别未知对象时，一般利用近似约简代替严格意义 上的约简。 下面，我们介绍与决策规则相关的数量测度： ( 1 ) 支持量 决策规则a 斗口的支持量表示在决策表中同时具有性质a f f f l f l 的对象数量，表 示为s u p ( a 卢) 。 ( 2 ) 精度 决策规则a 斗口的精度定义为： 重庆大学硕士学位论文 3 决策规则生成分析 口c c 0 斗f 1 ) ：s u p ( a _ f 1 ) s u p ( a ) a c c ( a _ ) 测度了根据口能得出结论的可信度，并且是条件概率p r ( p l 国的 概率估计。 如果a c c ( a 斗卢) = 1 ，我们称此决策规则为确定性决策规则，否则称为非确定 性规则。 ( 3 ) 适用度 规则的支持量越大，其适用性越强，决策值的分布对规则的适用性也有影响。 决策规则a 呻的的适用度为： c o r ( 口，) ：s u p ( a af 1 )。 s u p ( f 1 ) c o v ( a 哼卢) 测度了规则的适用程度，并且是条件概率p r ( a 1 ) 的概率估计。 一条理想的规则应该同时具有较高的精度和较高的适用度，对于精度和适用 度的关系来说，可将规则分为四种类型，其示意图如图所示。该图显示有两个决 策类k 和墨时，决策规则的四种情况，其中每一个圆的面积表示s u p ( q ) ，即匹配 规则前件儡的对象数量。 国3 i 四种类型的决策规尉 f i g 3 1 d e c i s i o nr u l eo f f o u rc l a s s e s ( 4 ) 稳定度 如果决策规则口斗是由动态约简技术得到的，则可以定义规则的稳定度。 ( 5 ) 规则前件长度 规则前件长度是指规则前件中的属性数量，表示为i 口l 。一般地，随着规则前 重庆大学硕士学位论文3 决策规则生成分析 件中属性的增多，规则适用度降低，精度增加，即规则更加详细而精确，但不具 一般性。这种关系可由图3 2 示意。在实践中，精度和适用度的确定是很困难的， 并且与应用领域有关。出于规则评价的目的，有时也将规则a - - 的精度和适用 度组合为一个复合测度 很明显，我们需要精度和适用度都高的决策规则，而在两个数据测度之间定 义一个平衡点， 图3 2 规则前件对精度和适用度的影响 f i g 3 2i n f l u e n c et oa c c u r a c y c o v e r a g e 3 3 基于a 一决策矩阵的规则获取 对于一个决策系统，我们会发现有些对象有同样的条件属性值，但是却有不同 的决策属性值。下面我们给出具有这种形式的决策系统的定义。 定义3 2 不相容决策系统 设s = ( u ，c u d ，v ，力为一决簧系统，c 为条件属性集，其值域为屹， 田为 单决策属性，其决策值域为。如果存在工，y u ，使得： 对于任意的口c ，有f ( x ，a ) = f ( y ，口) 且厂d ) f ( y ，d ) 。 我们称此类决策系统为不相容决策系统。 定义3 _ 3口一决策值区分函数 设s = ( u ，c u d ，矿) 为一决策系统，c 为条件属性集， d 为单决策属性。 x u ，x 的决策值值域为a 口( x ) ，我们称( x ) 为一决策值区分函数。 定义3 4a 一不可区分关系 设s = ( u ，c u d ，v ) 为一决策系统，c 为条件属性集， d ) 为单决策属性集。 重庆大学硕士学位论文3 决策规则生成分析 b 至c ，设s 的一决策值区分函数为( ，定义a f 一不可区分关系n d ( c 7 ，) ：n d ( o ，) = ( x ，y ) u 2 ：( 工) = ( y ) ) 在不引起混淆的情况下，简称为o - 不可 区分关系 o - 不可区分关系将论域u 划分为 z l ，z 2 ，五。) ，其中z ，u = 1 ，2 ，卅) ) 称为第 - ，个0 一决策类。利用a 一不可区分关系可以将不相容决策表转化为相容的决策表， 这样得到的决策表称为0 一决策表。 设u 1 n d ( c ) = 五，互，以 ， 则对任意讳，置，i = l ，2 ，n ，有 ( 讳，= i 的参数： s 3 ：构造s 的a 一决策矩阵m ( s ) = ( ) ，由于a 一决策矩阵是对称矩阵，故设 m ( s 1 ) 为上三角矩阵； s 4 ：由a 一决策矩阵建立每个条件等价类正o = 1 ，2 ，n ) 的决策函数骂： e = ( 尘v 口) ( 全v 口) ；其中k = 1 ，2 ，j - l ；= i + l ，l ， 和v 分别表示合取和吸 t qo e m ， # x 4 t m 取运算。 s 5 ：利用第2 章介绍的定理2 2 ，2 3 ，2 4 化简决策函数为最小吸取范式，其中每 个合取子式对应一条规则的前件，由于合取予式中只有属性名，所以将各属性匹 配以五的属性值，并明确其决策值，得到墨的所有规则； s 6 ：重复过程( 4 ) 、( 5 ) ，得到s 中所有等价类的规则，并进行参数的合并，根据问 题的需要，利用一定的规则选取策略选择规则进行决策 例3 1 某决策表如图所示，条件等价类为x i ，f - l ，2 ，1 1 ，决策类的对象数分别为 i r o 净3 0 ，l xp 7 7 ，i e 卜9 7 ，l 墨 2 表3 1 决策表 t a b l e3 1d e c i s i o nt 曲1 e 等价类样本个数 条件属性决策属性 0 0 2 l b 0 0 1 l 2 2 0 l l 2 2 a o 1 1 0 o 1