（应用数学专业论文）基于粗糙集理论的不确定型决策系统研究.pdf

武汉理t 大学硕士学位论文 摘要 随着社会的进步和发展，决策信息系统的研究和应用已取得很大的进展， 但在信息社会到来的今天，人们所面临的决策问题同趋复杂，大量的、不完全 的、有噪声的、模糊的、随机的实际数据干扰着决策者提取隐含的、有价值的 决策信息。因此，提供一套解决含有此类不确定信息的决策信息系统一不确定 型决策信息系统的决策方法已迫在眉睫。 粗糙集理论是二十世纪八十年代初由波兰数学家- - z p a w l a k 提出的一种刻 画不确定性和不完整性知识的数学工具，这为处理不确定型决策信息系统提供 了一条新思路。该理论近年来日益受到广泛关注，己在人工智能、知识发现、 故障诊断、模式识、专家系统等方面得到了成功的应用。以粗糙集为工具处理 不确定型决策信息系统为我们提供了一条新思路。 本文通过对现有复杂决策问题特征的深入分析，在大量检索国内外资料、 跟踪国际前沿技术，总结和借鉴前人经验的基础上，将粗糙集理论与决策问题 相结合，本文的具体研究内容如下： 研究了决策信息系统的数据预处理过程，在噪音数据的有效识别问题上， 提出了一种粗糙聚类算法。在属性约简方面，提出了基于同族矩阵的属性约简 方法，并研究了同族矩阵的性质。在连续属性的离散化问题上，从聚类相似度 以及分类质量、分类精度的角度对经典离散化方法进行了比较，得到了离散化 方法相同的优劣序。 在不确定决策信息系统的设计上，将粗糙集与神经网络结合，构造了粗糙 神经网络决策系统，实证分析表明粗糙神经网络缩短了网络的训练时间，同时 分类精度也有了明显提升。 针对属性值为区间数的决策系统，提出一种新的离散化方法，并结合灰色 系统理论，定义了决策规则，通过对比神经网络，该区问数型粗糙灰色决策系 统简化了决策规则，提高了智能决策效率。 关键词：粗糙集属性约简属性离散化神经网络遗传算法灰色关联度 武汉理工大学硕士学位论文 a b s t r a c t a ss o c i a lp r o g r e s sa n dd e v e l o p m e n t ，r e s e a r c ho nd e c i s i o ni n f o r m a t i o ns y s t e m a n di t sa p p l i c a t i o nh a sm a d eg r e a tp r o g r e s s ，h o w e v e r , i nt h ei n f o r m a t i o ns o c i e t yi s c o m i n g ，t h ed e c i s i o i np r o b l e m sw ea r cf a c i n ga r eb e c o m i n gm o r ea n dm o r e c o m p l i c a t e d , v a l u a b l ei n f o r m a t i o n 晰t l ll a r g e ，i n c o m p l e t e ，n o i s y , 呱r a n d o md a t a i n t e r f e r ew i t l ld e c i s i o nm a k e r ss e e k i n gi n t e r e s t i n ga n dv a l u a b l ei n f o r m a t i o n s oi ti s u r g e n tt op r o v i d eas u i to fd e c i s i o nm e t h o d sw h i c hc a ns o l v et h eu n c e r t a i nd e c i s i o n i n f o r m a t i o ns y s t e m t h er o u g hs e tt h e o r yp r o p o s e db yp a w l a k ( 1 9 8 2 ) i se s t a b l i s h e do nt h eb a s i so f d a t a b a s e ，w h e nd a t a b a s ei su n c e r t a i no ri n c o m p l e t e i tp r o v i d e so n en e ww a yf o ru s t os o l v et h eu n c e r t a i nd e c i s i o ni n f o r m a t i o n s y s t e m t h er o u g hs e tt h e o r yh a s p r e f e r a b l ea p p l i c a t i o no na r t i f i c i a li n t e l l i g e n c ea n dk n o w l e d g ed i s c o v e r y ，p a t t e m r e c o g n i t i o n , f a u l td e t e c t i o n , e x p e r ts y s t e m s ，e t c b a s e do ng r e a ts e a r c h i n go fi n t e r n a la n de x t e r n a li n o f m r a t i o na n d f o l l o w i n gc l o s e l y i n t e r n a t i o n a la d v a n c e dt e c h n o l o g yid e e p l ya n a l y z et h ec h a r a c t e r i s t i co ft h ec o m p l e x d e c i s i o na n dc o m b i n er o u g h ts e t st h e o r y 、析t hc l a s s i c a ld e c i s i o nm e t h o d s t h em a i n c o n t e n t so ft h i sp a p e ra r ea sf o l l o w s ： o nt h ed a t ap r e p r o c e s s i n go f d e c i s i o ni n f o r m a t i o ns y s t e m , 0 1 1a c c o u n to f d i s t i n g u i s h i n gn o i s yd a t a , o n er o u g hc l u s t e ra l g o r i t h mi sp r o p o s e d i nr e s p e c to f a t t r i b u t e r e d u c t i o n , t h er e d u n d a n ts e to fa t t r i b u t e si so b t a i n e db yc o n s t i t u t i n g h o m o g e n o u sm a t r i xw h o s ep r o p e r t i e sa r ed i s c u s s e dl a t e r , w h e r e a st h a td i f f e r sw i t h c l a s s i c a lm e t h o d i nt e r m so fd i s e r e t i z a t i o n ，f o u rk i n d so ft y p i c a ld i s c r e t i z a t i o n a l g o r i t h m sw e r ec o m p a r a t i v e l ya n a l y z e df r o mt w oa s p e c t s 砸也e x a m p l e s ，o n e r e f e r r e dt ot h ev a r i a b l eq u a l i t yo fc l a s s i f i c a t i o na n da c c u r a c yo fa p p r o x i m a t i o nu n d e r d i f f e r e n tp a r a m e t e r , t h eo t h e rw a st h es i m i l a r i t yd e g r e e sb e t w e e nr e d u c t e dv a r i a b l e s e t sa n dt h eo r i g i n a lv a r i a b l es e t ，f i n a l l y , t h ec o n s i s t e n tc o n c l u s i o no np r e f e r e n c eo f d i s c r e t i z a t i o na l g o r i t h m sw c r g a i n e d a sf a ra su n c e r t a i nd e c i s i o ni n f o r m a t i o ns y s t e mi sc o n c e r n e d ，a na p p r o a c ho fb a c k i i 武汉理t 大学硕士学位论文 p r o p a g a t i o nn e u r a ln e t w o r kw i t hr o u g hs e t ( r s b p ) i sp r e s e n t e d ，s i m u l a t i o nr e s u l t s i n d i c a t et h i sm o d e l ，c o m p a r e dw i t ht h ec o n v e n t i o n a lb pn e u r a ln e t w o r km o d e l ，c a l l r e d u c et h et r a i n i n gt i m ea n di m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n i nr e s p e c to fi n f o r m a t i o ns y s t e mw i t hi n t e r v a ln u m b e r s , a d i s c r e t i z a t i o na l g o r i t h mi s p r o p o s e d c o m b i n g w i t h g r e ys y s t e mt h e o r y , d e c i s i o nr u l e s i r e d e f i n e d ， s i m u l a t i o nr e s u l t si n d i c a t et h a ti n t e r v a lr o u g h - - g r e yd e c i s i o ni n f o r m a t i o ns y s t e m s i m p l i f y t h e d e c i s i o n - m a k i n gr u l e s a n di m p r o v et h e e f f i c i e n c y o f i n t e l l i g e n t d e c i s i o n m a k 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 t i o n ；d i s c r e t i z a t i o n ；n e t u r a ln e t w o r k ；g e n e t i c a l g o r i t h m ；g r e yr e l a t i o n a ld e g r e e i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特另日加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 签名：日期： 关于论文使用授权的说明 本人完全了饵武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名 日期： 武汉理工人学硕士学位论文 i i 研究背景 第1 章绪论 随着计算机软件与硬件技术的迅速发展以及数据库管理系统和数据仓库技 术的广泛应用，使得各个领域诸如政府、企业、银行、科研机构等的数据和信 息急剧增加。因特网的出现与发展，进一步加剧了这种趋势，并且由于人类的 参与使数据与信息系统的不确定性更加显著。这给人类的智能信息处理能力提 出了前所未有的挑战。如何从大量的、杂乱无章的、强干扰的数据中挖掘潜在 的、有利用价值的信息以预测未来，指导政府、企业决策，以获取更大的经济 效益和社会效益，这些都迫使人们去寻找新的、更为有效的数据分析手段，对 信息系统进行有效的挖掘以发挥其应用潜能。可以说，数据挖掘和数据库知识 发现是信息技术发展到一定阶段的必然产物，是拥有大规模数据库、高效的计 算能力和商业需求共同作用下的必然产物。 在数据挖掘和数据库知识发现的诸多方法中，粗糙集理论与方法对于处理 复杂系统不失为一种较为有效的方法，因为它与概率方法、模糊集方法和证据 理论方法等其它处理不确定性问题理论的最显著区别是它无需提供问题所需处 理的数据集合之外的任何先验信息。同时，由于该理论未能包含处理不精确或 不确定原始数据的机制，所以与其它不确定理论有很强的互补性。 1 2 研究目的和意义 粗糙集理论是建立在数据库基础上的，因此数据库的深入研究推动了粗糙 集理论的发展，特别是在商业智能中要面对更加复杂数据库，比如数据中取值 是连续值的情况，或者是模糊值、区间值的情况，也就是数据库取值本身是不 确定的情况，甚至数据库本身是不完备的情况。对于这些复杂的数据库要挖掘 决策规则，必须推进对粗糙集理论的研究。面对现实决策的实际问题，不断推 进粗糙集理论的研究，通过粗糙集理论的发展，解决更广泛的决策问题。 值得一提的是，在决策问题中，属性集的冗余性问题，也是棘手而久攻不 决的难点。冗余性常常干扰和影响决策的质量和结果的准确性，粗糙集理论的 武汉理t 大学硕士学位论文 另一特点是它的属性约简原理，即在信息融合的过程中具有对冗余信息进行筛 选剃除、组合归类的功能和特性。将其与多属性决策相融合，有利于冗余性问 题的解决。 在经典的决策中，还要求属性值是可以运算的，在日常的多属性决策问题 中，许多属性值是无法直接运算的逻辑值，而在粗集理论中的属性约简算法中 可以通过析取与合取范式进行逻辑运算，从而解决不可直接运算的多属性决策 问题。即通过粗集理论本身所具有的归纳学习、融合推导、规则提炼、属性约 简等特点，有望在较大程度上突破经典决策理论和方法的局限性。将二者融合 建立起一门新的粗集决策理论和方法，将决策的专家评判、模型推理与粗集理 论的归纳学习和信息融合方法进行集成，既可融合二者的优势，在方法论上取 得突破，又可在实际应用中开辟一条决策科学的新路径，其学术价值和实际意 义重大而深远。 l 。3 粗糙集理论的发展及研究现状 1 9 8 2 年p a w l a k 提出的粗糙集理论是建立在数据库基础上的，在数据库取值 是不确定的情况下，有着较好的应用前景。w z i a r k 以粗糙集理论为背景提出了 模式识别技术；a g j a c k s o 把租糙集理论应用在数据分析上，使之作为材料设计 与过程设计领域的一种预处理工具。f q u e s t i e 将粗糙集应用于无监督聚类的特 征提取：在与原始属性集的聚类结果保持一致的前提下删除冗余属性。z h ix i a o 结合神经网络良好的容错性及抗干扰性，利用粗糙集方法简化神经网络的输 入，对重庆地区的短期电力系统负荷进行了较精确的预测。而在规划领域，粗 糙集理论也得到了成功的应用。 基于以信息系统为研究对象的粗糙集的不确定决策为从数据表中提取知识 提供了一种有效的工具，而数据表形式化了信息系统( p h i l i p p ef o r t e m p se ta 1 ， 2 0 0 8 ；j e r z yb l a s z c z y n s k ie ta 1 ，2 0 0 7 ) 。为了表达、推理知识，2 0 0 2 年p a w l a k 提出了 决策规贝i j ( d r ) 。d r 可看作在数据表框架下的经典决策规则，但是从知识表达的 角度来看，非经典决策规则的广义化也是有价值的。例如，为了处理不确定以 及不完全信息，一些广义的决策规则被提出( m e i l i a nl i a n ge ta l ，2 0 0 4 ；m i n g l ih u a n ds i f e n gl i u ，2 0 0 7 ) 。当粗糙集应用于多属性决策分析以及多属性分类( g r e c oe t a 1 ，1 9 9 7 ，2 0 0 1 ；s l o w i n s k ie ta 1 ，2 0 0 2 ) ，控制下上近似的不可分辨关系被优势关系 2 武汉理工大学硕士学位论文 取代( d e m b c z y n s k ik r z y s z t oe ta l ，2 0 0 5 ) 。这一方法可以从样本决策中得到决策规 则以形成综合的规则库，为新的决策环境提供参考。 1 4 小结 本章为绪论，介绍了论文的研究背景、研究目的和意义，以及国内外的研 究进展。 3 武汉理工大学硕十学位论文 2 1 信息系统 第2 章粗糙集及其相关理论 “知识一这个概念在不同的范畴内有多种不同的含义。粗糙集理论认为知 识实际上源于人对各种事物的分类能力，而分类实际上就是按照某种特征属性 将具有相同属性值的对象分别归纳在各自的集合中，即按照某种等价关系进行 分类。我们通常处理的不是一个等价关系，而是一些等价关系，并试图发现各 个属性和分类结果之间的关系，找到描述分类结果的本质特征属性发现分类 规则。所以，知识与分类等价等概念息息相关。 知识的表示通过知识表达系统完成。知识表达系统的基本成分是被研究对 象的集合，关于这些对象的知识是通过制定对象的属性和它们的属性值来描述 的。因此，可以用信息系统来表示知识。 信息系统被定义为如下的四元组：s = ( u ，a ，f ，v ) 。其中s 为知识表达系统； u = 毛，x 2 ，毛 为对象的非空有限集合，也称论域；a = 口l ，a 2 ，a m 为属性的 非空有限集合；y 为属性值域，y - - o 。_ g o ；f ：u a v 为一信息函数，表示 对每一个a a ，工u ，我们有厂( x ，口) v o 。 进一步，信息系统中属性彳可以划分为两个不相交的子集，条件属性集c ， 和决策属性集d ，a = c u d ，并且c n d = a ，这种具有条件属性集合c 和决 策属性集合d 的信息系统称为决策信息系统，记为s = ( u ，c u d ，厂，矿) ，有时将 其记为s - - ( v ，c o d ) 。 一个决策信息系统中的决策属性有时是唯一的，则称其为单一决策信息系 统；如果决策信息系统中的决策属性不唯一，则称其为多决策信息系统。对于 具有多个决策属性的决策信息系统，我们可以通过多种方法将其转化成为单一 4 武汉理工大学硕士学位论文 决策信息系统。比如将多决策信息系统分解成为多个不同决策属性的单一决策 信息系统，或者通过综合多决策信息系统中所有决策属性的取值来形成一个综 合决策属性，从而将多决策问题转化成为单一决策问题的。因此在以后的讨论 中，为了有利于问题的简化和求解，对决策信息系统将只考虑单一决策信息系 统的情形，但研究结果也可以推广至多决策信息系统。 2 2 粗糙集及其近似 设u 是论域，= ( 而，) k ( 毛) = 石( _ ) ，口，曰 是u 上的等价关系。 对于任意xsu ，记 曼( x ) = x e u ：口( x ) x ) ， 否( x ) = x e u ：b ( x ) n x a ， 称旦( x ) 为x 的下近似，b ( x ) 为x 的上近似。 若垦( x ) = b ( x ) ，称x 为可定义的集合，否则称x 为粗糙集 2 3 正域、负域和边界域 有了下近似和上近似的定义，下面介绍正域、负域和边界域的定义： 我们把集合p 帆( x ) = 里( x ) 称为集合x 的b 正域，把n e g b ( x ) = u 一垦( x ) 称 为x 的口负域，称b n n ( x ) = b ( x ) 一垦( x ) 为属性集合口定义的边界域。 ：1 或p o s s ( x ) 或下近似垦( x ) 是那些对于等价关系能完全确定地属于x 的 对象的集合。类似地，负域n e g n ( x ) 是那些对于等价关系毫无疑问不属于x 的 对象的集合，它们是属于x 的补集。边界域是某种意义上论域的不确定域，对 于等价关系，属于边界域的对象不能确定地划分是属于x 或是一x 。x 的上近 似是由那些对于等价关系不能排除它们属于x 的可能性的对象构成的；从形式上 看，上近似就是正域和边界域的并集。 气 武汉理工大学硕士学位论文 边界域之所以存在，是因为用来描述概念的知识( 基本概念) 是有粒度的。 极限情况下，知识的粒度足够细，每个基本概念仅仅包含单个样本，显然它就 能精确定义任何概念( 对象集合) 。边界域概念的引入和定义，使粗糙集理论能够 描述和处理模糊不确定的信息，并最终使其成为分析处理不确定性信息的有效 工具。 x 的- f近似 露黟w $ ”7 ”w 2 蹋 黔”甲” 4 紫拶j 3 霸 r 。x l ，。 i 目鲑乩。幽觚m i “i o 。，矗娥捌 0爿 瓯。蒯，x f勺边界 r 2 。4 近似精度和分类质量 集合的不精确性是由于边界域的存在而引起的。集合的边界域越大，其精确 性则越低。为了更准确的表达这一点，我们引入精度的概念。由属性集合b 定 义的集合x 的近似精度为： 卯) = 舞c a r a 渊 i 髟i 五i i 精度用来反映我们了解集合x 的知识的完全程度。显然，o 鳓( x ) s 1 ， 当心( x ) = 1 时，工为可定义的集合。 僻捌c a r d ( u ) 6 武汉理工大学硕士学位论文 表示在条件属性b 下能够确切的划入决策在u d 的对象占论域中对象数的 比率，表达了决策属性d 对条件属性b 的依赖程度。由分类质量我们可以得到 属性重要性的定义： 蝻 ( 6 ：f ) = 掣 可以将s 辔盆( 6 f ) 理解为当属性包被除去时，所发生的分类错误率。 2 5 连续属性离散化 连续属性的离散化是数据挖掘和机器学习的重要预处理步骤，直接关系到 挖掘或学习的效果。p a w l a k z 提出的粗糙集理论为进行数据挖掘提供了一个很 好的工具，但该理论只适用于离散属性，而不能直接处理连续属性，这就大大 限制了粗糙集理论的应用范围，为了使粗糙集理论能够处理连续属性，就需要 将连续属性进行离散化。而离散化的方法不同，结果也往往存在差异。 离散属性也称是符号的、名称的、或类别的属性，这些属性是用少量的离 散值表示的，例如颜色、形状等：连续属性也称是实数的、或有序的、或数值的 属性，这些属性表示了对象的一种可测量的属性。所谓连续属性的离散化就是 在特定的连续属性的值域范围内设定若干个离散化划分点，将属性的值域范围 划分为一些离散化区间。 2 6 属性约简 在一个信息系统中，来自于实际系统的信息量常常包含有不确定性。大多 数情况下，信息系统中存在一些对某个给定的学习任务无关的、不重要的属性。 如果去除这些荣誉属性，并能找到最小的相关属性集，具有与全部属性相同的 分类能力，就能简化信息系统。 属性约简是指可以找到一个较小的属性集曰彳，使得可用么描述的对象集 合必然可用b 描述。也就是在保持原有信息系统分类能力的情况下，尽可能地 消除冗余属性。属性约简简化了分类的标准，同时也使人们更加深入地认识分 7 武汉理工大学硕士学位论文 类的本质。 目前，关于粗糙集中属性约简问题已有不少的研究，现已证明求取粗糙集 中的全部最小约简过程是n p h 硼问题。如何得到一种最佳的属性约简方法， 从而获得更为简洁的决策规则，就成为粗糙集理论中的基本问题之一。 在约简算法中，最常见的约简算法就是删除法。此方法为依次从数据表中 删除属性，将删除属性后的信息表与原信息表的决策类的不可分辨关系进行比 较，如果不可分辨关系没有变化，那么可以继续从新生成的信息表中删除属性， 继续比较，如果不可分辨关系发生了改变，则恢复到前一个信息表，删除另一 属性。具体算法概括如下： 删除重复的行，即删除重复的实例。 去除决策表中的中的某一属性列。 如果决策表不可分辨关系为发生变化，则删除该属性；如果决策表中不 可分辨关系发生了变化，则保留该属性。 举一例说明此算法： 设有决策表如下，其中c t - - ( a t ，呸岛) 为条件属性，d = d 为决策属性，求 其属性约简。 表2 - 1 决策表 首先删除冗余属性口l ，决策表中的不可分辨关系没有改变，这时，如果删 除条件属性q ，呜中的任意一个，则不可分辨关系将发生改变，由此可得到一 个约简 a 2 ，a 3 ；而如果先删除属性啦，则由属性q ，a 3 ，d 构成的决策表中，再删 除属性口3 ，不可分辨关系仍不会改变，从而得到另一个约简 q ) ；如果先删除口3 ， 8 武汉理工大学硕士学位论文 则由属性q ，a 2 ，d 构成的决策表中，再删除属性口2 ，其不可分辨关系仍不会改变， 从而同样可以得到另一个约简为 a 。) 。因此，对于本信息系统可以得到两个属性 约简集： 口2 ，口3 和 口1 上面的约简算法是基于不可分辨关系的，具有一定的局限性，当信息系统 中条件属性数与记录数都较少的情况下，采用此方法能得到满意的结果。但当 条件属性数很多，并含有大量实例时，采用此方法会产生很多的约简组合，而 且每一属性约简结果的产生都必须经过大量的是否改变信息系统不可分辨关系 的比较运算，计算复杂度较高。 2 7 小结 粗糙集理论是一种处理含糊和不确定性问题的新型数学工具。本章对粗糙 集理论的一些基本概念进行了概述，并举例进行了说明。主要描述了本文后续 工作的基础概念如粗糙集的信息系统、粗糙集及其近似、正负域及边界域，分 类精度和分类质量等。在这些概念的基础上，对基于粗糙集理论的不确定决策 系统研究的侧重点：连续属性离散化和属性约简的相关概念作了简要的介绍。 9 武汉理| t 大学硕+ 学位论文 第3 章粗糙决策系统的数据预处理 当今现实世界中的数据库极易受噪音数据、遗漏数据和不一致数据的侵扰， 因为数据库太大，常常多达数千兆甚至更多。不完整数据的出现可能有多种原 因。可能只是因为输入时认为是不重要的。相关数据数据没有记录是由于理解 错误，或者因为设备故障。此外。记录历史或修改的数据可能被忽略。 数据含噪音( 具有不正确的属性值) 可能有多种原因。收集数据的设备可 能出现故障：人或计算机的错误可能在数据输入时出现；数据传输中的错误也 可能出现。这些可能是由于技术的限制，如用于数据传输同步的缓冲区大小的 限制。不正确的数据也可能是由命名或所用的数据代码不一致而导致的。 参与数据挖掘和知识发现数据的质量，是挖掘出精确、实用知识的前提。 无法想象在虚假、劣质数据泛滥的数据集上，能发现、找到有用的知识和规则。 统计发现：在整个数据挖掘过程中，数据预处理要花费6 0 左右的时间，而后的挖 掘工作仅占总工作量的1 0 左右。对数据进行预处理，不但可以节约大量的空间 和时间，而且得到的挖掘结果能更好地起到决策和预测作用。高质量的决策必然 依赖于高质量的数据，因此数据预处理是知识发现过程的主要步骤。检测数据 异常、尽早地调整数据，将在决策制定时得到高回报。 连续属性的离散化是数据挖掘和机器学习的重要预处理步骤，直接关系到 挖掘或学习的效果。在数据挖掘和机器学习等领域中，许多算法都只能对离散 化的数据进行处理。例如在分类应用中比较好的i d 3 系列决策树法，就只能运 用在离散属性上。粗糙集理论为进行数据挖掘提供了一个很好的工具。但遗憾 的是该理论只适用于离散属性，而不能直接处理连续属性，这就大大限制了粗 糙集合理论的应用范围，为了使粗糙集合理论能够处理连续属性，就需要将连 续属性进行离散化。 现在实际的数据库规模往往很大，里面存储了大量的数据，如果直接以这 些数据来进行挖掘获取或进行学习，其时间和空间的代价不言而喻。如果将连 续的属性进行离散化，就能够从这些含有连续属性的数据库中取得好的数据集， 得到简洁且有效的规则。离散化结果将会减小系统对存储空间的实际需求，加 快后继数据挖掘和机器学习算法的运行速度，减小后继算法的空间开销，提高 分类精度。 本章将对数据清理和数据离散化方法进行研究，使粗糙集方法能够更好地 1 0 武汉理工大学硕士学位论文 适用于知识发现过程。 3 1 粗糙决策系统的数据清理 本节基于粗糙集理论对噪音数据的识别以及冗余属性的剔除进行研究，而遗 漏值的处理不在粗糙集框架下解决，因此本文不做讨论。 3 1 1 基于粗糙聚类算法的噪音数据识别 ，、 根 伽 趟 褂 v 稠 恻 牺f 图3 1 不同轿车载重量盒图 首先，我们以盒图的形式展示离群点。图3 1 给出了1 9 7 0 年至1 9 8 2 年间六个 国家生产的轿车载重量的盒图，我们可以清楚的识别出3 个可疑的离群点，即图 武汉理工大学硕士学位论文 中红色加号。在典型情况下，盒的端点在四分位数上使得盒的长度是i q r ，中 位数用盒内的线标记，盒外的两条线( 称作胡须) 延伸到最小和最大观测值。 基于以下粗糙集的性质，本文提出了一种改进的粗糙k 均值聚类算法用以 识别可疑的离群点，避免了原算法中的下近似集合、边界集合为空集所带来的 算法不稳定性。 性质l ：一个数据对象最可能属于下近似的一员。 性质2 ：一个属于某类下近似的数据对象，同时属于这类的上近似。 性质3 ：一个不属于任何类下近似的数据对象，至少属于两个类的边界域以 及对应的上近似。 随机指定每个数据到一个下近似集合，按照粗糙集的思想，每个数据也对 应的分配到一个上近似集合。 计算新的聚类中心： m k2 m 丕自+ 屹荟南+ 荟南，g 翊 掣翊 哪丕卣+ 吨互南鱼翊 掣翊 也互商+ 荟南刍翊 掣翊 其中，坼、心、分别为聚类下、上、边界区域的权重，l c i 为c 中向量的个 数。 如果 d ( ，) = 捌m 2 - i l l 省( ，) ， 则 毛百 其中， d ( x ，y ) = ( 一苁) 2 + ( _ 一只) 2 。 给定阀值占，如果d ( 毛，惕) 一d ( ，m h ) - n a i v e s c a l e r - e q u a lf r e q u e n c y - b r & r s 我们再从约简变量集合与原始变量集的相似度的角度评价四种离散化方法。 由于属性约简集的非唯一性，我们引用包含度理论选取每一种离散化方法所对 应的属性约简集： 定义1 设u 为有限论域，对于任意x ， y e u ，称d ( y x ) 为包含度，若满足以下条件： o s d ( y x ) s l ： 当xe j ，时，d ( y x ) = 1 ； 当xg 】，ez 时，d ( x z ) sd ( x r ) 本她糊取o ( v x ) = 眢。 设尸i = 日n ，碍，磷 为第f 种离散化方法所对应的属性约简集的全体所构成 的集合，其中，1 s i 4 。若 d ( 露q ) = i m j a x 1 ) 后再重复这一步。最后f ( x ) 会 下降。如果某一步产生了更小的f ( x ) ，则蜥在下一步被除以p ，这样算法就接 近于高斯一牛顿算法，该算法提供牛顿法的速度和保证收敛的最速下降法之间 的一个折衷。 4 1 2 粗糙神经网络决策系统仿真实验 利用从u c i 机器学习数据库得到的g l a s s 数据集作为分析对象。该数据集由 v i n as p i e h l e r 收集，共有2 1 4 个案例，去掉主键i dn u m b e r 之后共有1 0 个条 件属性，1 个决策属性( g l a s s ) 。数据集的基本信息如表4 1 所示，均值与s d 是 针对连续属性。 表4 - 1 数据集的基本描述 。、 属性 r i l k a 15 ikc ab f g l a s s 描述 类型连续连续连续连续连续连续连续连续连续整型 。均值 1 5 1 8 41 3 4 0 7 92 6 8 4 51 4 4 4 97 2 0 5 4 90 4 9 7 18 9 5 70 1 7 5o 0 5 7 s do 0 0 3 8 0 0 1 6 61 4 4 2 40 4 9 9 30 7 7 4 50 6 5 2 21 4 2 3 20 4 9 7 2o 0 9 7 4 + 最小值1 5 1 1 2l o 7 300 2 96 9 。8 lo5 。4 3o0l b “武盐， 最大值 1 5 3 3 91 7 3 84 4 93 57 5 4 16 2 l1 6 1 93 1 5o 5 l7 将不同的决策属性对应的前7 0 案例作为训练集，在应用n a i v e s e a l e r 算法 离散连续属性值后，离散结果如表4 - 2 所示。 武汉理i ：人学硕十学位论文 表4 - 2 离散化结果 n如 ls ik妇hr i l l5 2 0 4 8 ,【1 36 0 ，1 4 1 3 4 0 2 ，l l0 8 ，1 7 15 4 ,呻0 6 ,1 8 7 3 n h i5 2 l i4 ) i ) 6 5 ) 11 1 ) 7 l “)0 0 7 l b7 6 ) i ) 0 o i ) 【1 , 5 1 7 4 5 1 1 38 9 1 35 9 5 0 0 【1 3 6 ，【7 27 3 ，1 0 拈【78 1 i 【 i5 1 7 6 9 j 1 3 ) 36 0 5 0 0 l3 8 )7 27 6 ) 0 5 i ) 7 8 5 )l 0 0 1 l 【1 5 1 6 1 &1 1 3 4 8 p5 4 5 0 0 ,【1 5 4 ，【7 29 7 呻3 9 ，【7 , 6 9 ,n【- i5 1 6 2 l1 35 5 )35 5 5 0 0 ll5 5 )7 30 0 )o4 2 ) 7 8 1 )i ) 0 0 ij 【1 , 5 1 7 4 5 1 1 3 1 5 ，1 3 6 8 5 0 0 【1 2 9 【7 25 8 呻5 7f 8 2 2 i o 【， i5 1 7 6 9 ) i ，2 3 ) 37 3 5 0 0 ) f 3 i l 7 26 3 l o5 b ) 8 2 3 )1 ) 0 , 0 l l 应用遗传算法进行属性约简，共得到1 7 个约简结果，如表4 - 3 所示。 表4 3 属性约简结果 ( r i ，n a ，m g , a i ，s l ，k ，c a , f e 1 6 8 f r i ，n a ，m g , a i ，k ，c a , b a l 2 4 7 f r i ，n a , m g a i s i ，c a ，b a , f e 28 f r i ，n a , m g , a l ，k ，c a ，b a ，f e ) 28 f r i ，i q a ，m g , a i ，k ，c a , f e l l7 f r l ，n a ，m g , a i ，s i ，k ，c a 37 f r i ，n a , m g , a 1 ，s i ，k ，f e 37 r i ，n a ，m g , a i ，s i ，k ，c a , b a ) 28 r 1 ，n a ，m g , s i ，k ，c a ，b a ，f e l8 r i ，n a , a i ，s i ，k ，c a , b a , f e l8 r i ，n a ，m g , a i ，s i ，c a , f e ) 3 7 r i ，n a ，m g , a i ，s i ，f e l l6 r i ，n a , m & s i ，k ，c a , f e l7 r i ，n a , m 8 ，a i ，k ，c a , b a i 7 n a ，m g , a i ，s i ，k ，c a , b a ，f e l 28 r i ，n a ，a i ，s i ，k ，c a ，f e l7 n m g a 1 ，s i ，k ，c a , f e 27 在约简集的确定上，在拥有较少属性的情况下，选取支持数较大的约简集 作为优选对象。本例巾我们选择 r i ，n a ，m g ，a i ，k ，c a , b a 】而不选择支持数为 l 的 r i ，n a m g ，a i ，s i ，f e 】。 将删除属性值s i 和f e 后的训练集用于神经网络学爿。按照k o l m o g o r o v 定 武汉理工大学硕士学位论文 籁 称 求 器 目 籁 煳 分类正确数对比 对应的隐含层神经元数 图4 3 分类正确数对比 迭代次数对比 对应的隐含层神经元数 图4 - 4 训练时间对比 3 l 武汉理工大学硕士学位论文 理，隐含层应有1 5 个神经元，但k o l m o g o r o v 定理毕竟是一个经验公式，仅以 此作为参考，我们将隐含层神经元数分别设定为9 ，1 2 ，1 5 ，1 8 ，2 1 ，2 4 ，2 7 进行网络学习。针对目标属性并不具有类别以外的实际意义，在神经网络学习 中，可以用不同的基向量来表示，本例中，l ，2 ，3 ，4 ，5 ，6 ，7 分别用不同的 7 维基向量表示。 将不同的决策属性对应的后3 0 案例作为测试集进行预测，其网络性能和 预测结果与属性约简前对比如图4 3 、图4 - 4 所示。从总体上来说，粗糙神经网 络缩短了网络的训练时间，同时分类精度也有了明显提升。 4 2 区间数型粗糙灰色决策系统的设计 图4 - 5 区间数型粗糙灰色决策系统结构 本文结构安排如下：在第二节，我们改进了粗糙聚类算法使其更合理于粗糙 集的核心概念，用以离散区间型属性值。之后我们通过构造同系矩阵得到了属 性冗余集并讨论了其性质，这与传统的方法有所不同。通过属性问的相对重要 性的定义我们得到了属性权重。在本节最后，当决策库中部分决策规则已知时， 3 2 武汉理t 大学硕士学位论文 基于灰色关联分析技术，提出了任意条件属性下的决策规则。在第三节，通过 对比b p 神经网络我们验证了灰色决策规则的可信性以及优势。最后，在第4 节， 我们讨论了本文的主要工作以及将来的研究方向。详细过程见图4 5 。但是，对 于测试样本，离散化与属性约简的顺序刚好相反，仅仅是为了提高智能决策的 效率。 4 2 1 区间数型属性值的离散化 首先，给出相关定义。 定义3 设二= 口，口u = x l 口xs 口f ，) ，称二为区间数。特别地，当口上* - a 时， 二为普通的实值函数。 定义4 设三= c lc u 为固定区间数，对于v 二， d ( 五三) = 励( 口) 2 + ( ) 2 为区间数二到三的距离。 定义5 四元组s = ( u ，a ，v ，) 称为一个区间型信息系统。其中u = 而，屯，毛 为对象的非空有限集合，也称论域；a = 口l ，a 2 ，) 为属性的非空有限集合； y = u 为属性集值域，是一个区间数，称为属性q 的值域，设_ ( 1 s j f 刀) 岛t 在q 下的属性区间数为 巧，彰 ，则满足下列条件： 对于任意的z t ，彰 ( 1s s 刀) ，有z ；对于任意的满足条件的， 嘭f ：u x a v 为一信息函数，表示对每一个a 彳，x u ， ( x ，口) 圪。当信息系统中属性4 = c ud ，其中c 为条件属性集，d 为决策 属性集时，信息系统也称为决策系统。 决策信息系统中的属性值往往是连续的，或者是一个真实的数据。而由 z p a w l a k 提出的以不可分辨关系为核一心的；l 日糙集方法处理的是离散属性值，因 3 3 武汉理t 大学硕+ 学位论文 此有必要对区例型连续属性值进行离散化处理。 连续属性的离散化就是在特定的连续属性的值域范围内设定若干个离散化 分点，将属性的值域范围划分成一些离散化区间，将属性值用所属区间的编号 代替。也就是对信息函数作了一次等价变换。离散化后，原来的决策信息系统 被一个新的决策信息系统所代替。 依照这一思想，对区问型连续属性值作如下离散化处理： 对于吃= 乞，么 ， 由定义知： 乞= m 证 i i l f 嘭，彰 i l sj fs 一 ， = 一 s u p 彰 | l s 刀 o 我们选取一个断点集合q = 茚，霹，吃j ，其