（应用数学专业论文）知识约简与规划获取.pdf

k n o w l e d g er e d u c t i o na n dr u l ea c q u i s i t i o n l o n gz h u o b s ( h u n a nu n i v e r s i t yo fs c i e n c e t e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e a p p l i e dm a t h e m a t i c s c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rl i uw e n u n a p r i l ，2 0 1 1 咖405 肌48哪8iiil舢y 长沙理工大学 学位论文原创性：声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律后果由本人承担。 作者签名： 茹涛 日期： 妒| f 年s 月烨日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后试用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名：名革 导师繇s 1 ) s 奇 日期： 2 ，f f年岁月午日 日期： 幽1 1 年f 月心日 摘要 经典粗糙集方法在进行规则的获取时，处理的对象基本上都是具有离散型属性 值的决策表，也就是属性值只是一些与对象的分类有关的标识符的决策表国内国 外的一些学者们在这方面已经做了很多的研究，并且取得了相当丰富的成果然而 对于普遍存在的连续值决策表，其规则的获取问题对于经典粗糙集的模型来说是一 种很大的挑战 本文主要是研究连续值决策表的扩展粗糙集的模型的，探讨连续值决策表的知 识约简 第 类技术 量的约 简集上 第 概念与 类质量 第 盖集的 了模型 第 关键词 a b s t r a c t c l a s s i c a lr o u g hs e tt h e o r yf o c u so nd i s c r e t ed e c i s i o nt a b l e ，i nw h i c ht h ev a l u e o fc o n d i t i o na t t r i b u t e si sj u s tas y m b o lt h a td e s c r i b eaf e a t u r eo fo n eo b j e c t e x - t e n d e dr e s e a r c h e so ni th a v eb e e nd o n ea n ds o m er e s u l t sh a v eb e e nm a d ep r e s e n t e d h o w e v e r ，t h e r ea r ea l s om a n yc o n t i n u o u sd e c i s i o nt a b l e s ，w h i c hi sd i f f i c u l tt od e a l w i t ho rg e tg e n e r a l i z a t i o nk n o w l e d g eb yc l a s s i c a lr o u g hs e tm o d e l s i nt h i sp a p e r ，w ea r ec o n c e r n e dw i t ha p p f i c a t i o n so fe x t e n s i o nr o u g hs e tm o d - e l si nc o n t i n u o u sd e c i s i o nt a b l e s e s p e c i a l l ya t t r i b u t er e d u c t i o na n dd e c i s i o nr u l e s a c q u i s i t i o ni nc o n t i n u o u sd e c i s i o nt a b l e s t h ep a p e ri so r g a n i z e da sf o l l o w s ： i nc h a p t e r3 ，ak n o w l e d g er e d u c t i o nm e t h o db a s e do nf u z z yc l u s t e r i n gi ss t u d i e d i nt h ef i s tp l a c e ，am e t h o do fc o m p u t i n gt h ec l a s s i f i c a t i o nq u a l i t yi sg i v e n s e c o n d l y , a 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 nt h ec l a s s i f i c a t i o nq u a l i t ya r ep r o p o s e d t h e nt h er e a s o nt ou s es u p p o r tv e c t o rm a c h i n et om i n ed e c i s i o nr u l e si sp r e s e n t e d f i n a l l y ，w eu s ea ne x a m p l et os h o wt h ep r o c e s so ft h e s ea l g o r i t h m s i nc h a p t e r4 ，s o m ec o n c e p t sa n dp r o p e r t i e so fl i n e a rs e p a r a b i l i t ya n dc o n v e x h u l la r eg i v e na tf i r s t s e c o n d l y , an e wr o u g hs e tm o d e lb a s e do nc o n v e xl m ui s p r o p o s e d t h e n ，a na l g o r i t h mf o rc o m p u t i n gt h ec l a s s i f i c a t i o nq u a l i t yi sp r e s e n t e d n e x t ，a na t t r i b u t er e d u c t i o na l g o r i t h mi sp u tf o r w a r da c c o r d i n gt ot h ec l a s s i f i c a t i o n q u a l i t y f i n a l l y ，a l le x a m p l ei ss h o w e dt oe x p l a i nt h ep r o c e s so fr u l ea c q u i s i t i o n i nc h a p t e r5 ，t h ed e f i n i t i o no ft h ec o v e r i n gs i m i l a r i wa n dt h ed e f i n i t i o no ft h e c o v e r i n gs e ta r eg i v e na tf i r s t s e c o n d l y , an e wr o u g hs e tm o d e li sp r o p o s e d t h e n ， a na l g o r i t h mf o rc o m p u t i n gt h ec l a s s i f i c a t i o nq u a l i t yi sp r e s e n t e d n e x t a na t t r i b u t e r e d u c t i o na l g o r i t h mi sp u tf o r w a r da c c o r d i n gt ot h ec l a s s i f i c a t i o nq u a l i t y f i n a l l y , a ne x a m p l ei st a k e nt oi l l u s t r a t et h ep r o c e s so fr u l em i n i n g i nc h a p t e r6 ，t h ev e c t o rm e t h o do fa t t r i b u t er e d u c t i o ni sp r e s e n t e d k e yw 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 ；r u l ea c q u i s i t i o n ；f u z z yc l u s - t e r i n g ；c o n v e xh u l l i i 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 粗糙集理论的研究背景及意义1 1 2 知识约简的研究现状2 1 3 本文的主要工作4 第二章预备知识 2 1 粗糙集基本定义5 第三章一种基于分类质量的粗糙集模型 3 1 分类质量的计算算法7 3 2 基于分类质量的约简算法1 1 3 3 规则获取一1 1 3 4 实例演练1 2 第四章一种基于凸壳的粗糙集模型 4 1 线性可分性与凸壳1 7 4 2 一种基于凸壳的新粗糙集模型1 8 4 3 分类质量的计算算法1 9 4 4 知识约简及规则获取? 2 0 4 5 实例演练2 l i i i 第五章一种基于覆盖相似度的粗糙集模型 5 1 覆盖相似度与覆盖集2 4 5 2 基于覆盖相似度的粗糙集模型2 4 5 3 分类质量的计算算法2 6 5 4 知识约简与规则获取2 7 5 5 实例演练2 7 3 3 。3 4 3 5 第一章绪论 1 1 粗糙集理论的研究背景及意义 早在1 9 0 4 年，谓词逻辑的创始人f r e g e 就提出含糊一词，并把它归结到边界线 区域，也就是说在全域上存在一些个体既不能在其某个子集上被分类，也不能在 该子集的补集上分类时至1 9 8 2 年，波兰数学家z p a w l a k 教授提出粗糙集理论【1 1 ， f r e g e 的边界域思想才得以实现1 9 9 1 年，z p a w l a k 出版了第一本关于粗糙集理论的 专著r o u g hs e t s ：t h e o r e t i c a la s p e c t so r e a s o n i n ga b o u td a t a ( 2 ) 拉开了粗糙 集研究热潮的序幕 1 9 9 2 年在波兰k i e k r z 召开了第l 届国际粗糙集讨论会1 9 9 3 年在加拿大b a n f f 召 开了第2 届国际粗糙集与知识发现研讨会1 9 9 4 年在美国的s a nj o s e 召开了第3 届国 际粗糙集与软计算研讨会1 9 9 5 年，粗糙集理论及应用的几位主要倡导者在当年 第1 1 期a c m 通讯上撰文( 【3 】) ，概括性地介绍了粗糙集理论的基本概念，及其在机器 学习、知识获取、决策分析等领域的具体研究项目和进展同年，在美m w i l l m i n g t o n 召开了第4 届模糊理论与技术国际研讨会，在这次会议上，针对粗糙集与模糊集合的 基本观点与相互关系展开了激烈的讨论，较大地促进了粗糙集的研究1 9 9 6 年底，在 日本东京召开了第5 届国际粗糙集研讨会，这是第一次在亚洲地区召开的范围广泛 的粗糙集研讨会1 9 9 9 年1 1 月在日本召开了”第7 届国际粗糙集、数据挖掘、粒度及 软计算的国际学术研讨会”2 0 0 3 年1 0 月，在中国重庆召开了”第9 届国际粗糙集、模 糊集、数据挖掘和粒度计算的国际学术研讨会”，这是第一次在中国召开的范围广泛 的粗糙集研讨会2 0 0 6 年7 月，第1 届”粗糙集与知识技术”研讨会也在中国重庆召开 这些以粗糙集理论为主题的国际研讨会，推动了粗糙集理论的拓展和应用 目前，在许多关于人工智能、模糊理论、信息管理与知识获取等期刊上经常可 以看到涉及粗糙集的论文 奠i i e e e 的会刊中知识与数据工程( k & d e ) 、模式分析 与机器智能( p a & m i ) 、系统、人与控$ 1 ( s m c ) 、模糊系统( f s ) 等杂志，f u n d a m e n t a i n f o r m a t i c a e 、l n c st r a n s a c t i o n so nr o u g hs e t s 、i n f o r m a t i o ns c i e n c e 等杂志，荷 兰e l s e v i e r 电子期刊全文数据库( s c i e n c e d i r e c t ) 的模式识另i j ( p a ) 、模式识别快报等杂 志，中国的计算机学报、软件学报、计算机研究与发展、电子学报等杂志中都有讨 论粗糙集理论及其应用的文章 1 经过近二十年的研究和发展，粗糙集理论已经在信息系统分析、人工智能及应 用、决策支持系统、知识与数据发现、模式识别与分类、故障检测、医疗诊断等方面 取得了较为成功的应用 1 2知识约简的研究现状 知识约简与决策规则的获取是粗糙集理论最为重要的应用4 7 】根据决策表有 无缺省值，可分为完备的和不完备的两种根据条件类与决策类是否相容，决策表 可以分成协调决策表和不协调决策表离散型协调决策表的研究已经取得了丰富成 果而离散型不协调决策表方面，区分矩阵方法及各种约简及其关系的探讨成为研 究的热点另外连续值决策表方面也已经有了一些优秀成果 ( 1 ) 关于离散型完备系统的经典粗糙集方法s k o w r o n 等在文献 8 - 9 1 中首次提出 了用区分矩阵方法求核与约简接着，h u 等学者在文献1 1 0 1 中提出一种改进区分矩阵 求核的方法而后叶东毅等人在文献 1 1 1 中用反例指出h u 算法的不足，又在h u 的基 础上给出了一个求核的新区分矩阵方法王国胤在文献 1 2 l 中给出了引起h u 算法错 误的原因，深度探讨y r o u g h 集代数观和信息观两者之间的关系，指出它们在核和约 简上的差异性，提出决策表中核的计算方法闫德勤在文献【1 3 】中提出一种规范化方 法及其相应的区分矩阵构造法来处理不相容问题g u a n 等人在文献【1 4 】中构造的改 进区分矩阵，在协调决策表上体现了与h u 和叶的一致性，而在不协调决策表上却有 着更好的性能：它不单可以求出一般约简，还可以对协调对象子矩阵求出p a w l a k 约 简 k r y s z k i e w i c z 在1 5 1 中总结并比较了不协调决策表的五种属性约简之间的关系， 指出本质上只有分布约简和分配约简两种z h a n g 等人在k r y s z k i e w i c z 的基础上提 出了最大分布约简的概念，讨论了近似约简、分配约简与分布约简、最大分布约简 之间的关系，给出了四种知识约简的判定定理以及相应的区分矩阵，据此得出不协 调决策表知识约简的方法 1 6 】张文修等在 1 7 】中以协调近似空间的概念为理论基石 系统地研究各种信息系统，并给出了协调集判定定理、属性约简方法、三类不同属 性( 核、相对必要属性、不必要属性) 的特征定理邓大勇等在1 1 8 1 中研究了不协调决 策表中的绝对约简与各种相对约简唐建国等在 1 9 】中提出一种直接求核的方法，简 化了信息系统和决策表的约简工作 ( 2 ) 关于离散型完备系统的变精度粗糙集模型与p a w l a k 粗糙集不同，z i a r k o 在 2 f 2 0 1 中以多数包含关系定义集合的上、下近似，提出变精度粗糙集模型这种模型 允许适当的分类误差，边界域大小可作调整m i 等在【2 l 】中根据变精度粗糙集理论 及包含度理论提出了不协调决策表的上、下分布约简，研究了它们之间的关系，并 给出其判定定理以及基于区分矩阵的求解方法袁修久等在 2 2 1 中将不协调决策表 转换成协调决策表，证明了变换前后卢上( 下) 分布约简相同；定义了不协调决策表 的卢上( 下) 分布核属性、p 上( 下) 分布属性集重要度，并且证明了它们分别同对应的 协调决策表的核属性、属性集重要度是相同的 ( 3 ) 关于离散型完备系统的优势关系模型g r e c o 在 2 3 】中研究了基于优势关系 的粗糙集模型，并应用到银行金融风险管理徐伟华等人在【2 4 】中在基于优势关系下 不协调决策表中引入了分配约简和近似约简的概念，研究了二者之间的关系，得到 了分布和最大分布约简的判定定理以及区分矩阵、基于区分矩阵的分布与最大分布 约简的求法陈娟等在f 2 5 1 中基于优势关系在不协调信息系统中引入正域约简的概 念并提出了优势关系下基于属性重要性的正域约简算法文献【2 6 】研究了粗糙分级 优势关系下的多决策规则，定义了分级模糊优势关系，给出了决策规则优势模型 ( 4 ) 关于离散型不完备系统k r y s z k i e w i c z 在 2 7 2 8 】中提出了处理不完备系统的 粗糙集方法王国胤在f 2 9 1 中提出了一种基于限制容差关系的扩展模型，比较分析了 它与基于相似关系、容差关系和量化容差关系等扩展模型之间的差异l e u n g 在【3 0 】中 采用关于容差关系的最大协调块方法解决真决策规则和最优决策规则的获取以及相 应的属性约简问题黄兵等通过在限制容差关系模型中引入集对联系度建立了一种 基于集对联系度的粗糙集扩展模型【3 1 】管延勇等在【3 2 】给出条件属性的b 相对约简 的概念及其区分函数求法在文献【3 3 1 中，管延勇等利用描述子来表达决策规则并对 描述子进行简化和约简 对于遗漏型和丢失型未知属性值共存的不完备信息系统( f 3 4 】) 文献 3 5 】构造了 满足自反性的特征关系及基于特征关系的粗糙集模型文献 3 6 】注意到由文献【3 5 】的 特征关系所导出的特征类存在不合理的情况，提出一种新的特征关系以及基于特征 关系的论域的完全覆盖，并且在完全覆盖的基础上生成了两种不同的知识表达系统 文献【3 7 】在广义不完备目标信息系统中引进上、下近似分布约简，给出了相应的判定 定理与区分公式文献f 3 8 1 提出了处理未知属性值的二种不同的方法 此外，y a n g 等在3 9 】中提出了相似优势关系，在此基础上定义了四种近似分布约 简，并给出相应的判定定理和区分矩阵w h 在文献 4 0 】中讨论了基于证据理论的不 3 完备信息，提出了似然约简和信任约简，相对似然约简和相对信任约简，并给出了它 们的性质和相互关系 ( 5 ) 连续值系统李然在 4 1 1 中提出两种新的知识约简，讨论了系统误差对规则提 取的影响闰德勤等在【4 2 】中将连续值决策表的每个规则看成多个连续函数的采样， 用模糊集的相似度量寻找等价类，结合粗糙集约简规则y a n g 等在文献【4 3 】中通过定 义相容关系构造不可分辨集，获得允许误差内的决策规则刘文军融合模糊聚类及 粗集的属性重要性定义，提出了一种属性权重的确定方法 4 4 】g u a n 等在文献【4 5 】中 定义了两种不同的下、上近似，提出了基于最大相容类的知识约简及决策规则优化， 并建立了区分函数求这些约简 对于一些集值、区间值、模糊值以及混合系统的约简问题，也有了大量的研究 1 3 本文的主要工作 本文主要研究( 完备) 连续值决策表的扩展粗糙集模型，探讨连续值决策表的知 识约简与决策规则的获取问题研究的主要内容分为以下部分： 第三章研究一种融合模糊聚类的粗糙集模型的知识约简问题首先基于模糊聚 类技术提出了一种计算连续值决策表的分类质量算法然后提出了一种基于分类质 量的约简算法，而后通过分析模型可能存在的状况给出了采取支持向量机方法在约 简集上挖掘决策规则的理由最后通过实例演示了算法过程 第四章研究一种基于凸壳的粗糙集模型首先给出了线性相关性与凸壳的相关 概念与性质，然后给出了基于凸壳的粗糙集模型的一些基本概念，并给出了模型分 类质量的计算算法与属性约简的算法最后通过实例演示了规则获取过程 第五章研究一种基于覆盖相似度的粗糙集模型首先给出了覆盖相似度与覆盖 集的概念然后给出了基于覆盖相似度的粗糙集模型的一些基本概念接着给出了 模型的分类质量计算算法与属性约简算法最后用实例演示了规则挖掘过程 第六章给出了属性约简的向量表示法 4 第二章预备知识 弟一早 耿亩大u 状 2 1粗糙集基本定义 定义2 1 1 【4 l 设r 为论域u ( u 咖) 上的等价关系族，记叫r 为由冗确定的所有 等价类组成的集合，【叫r 表示含有元素z u 的r 等价类，它构成u 的一种划分u _ h 的一族划分称为关于u 的一个知识库，或者说一个知识库就是一个关系系统k = ( 配r ) 定义2 1 2 f 4 】设兄为u 上的一个等价关系族，若p r ，且有p ，则n p 也是一 个等价关系，称为尸上的不可区分关系，i 己为i n d ( p ) ，且纠伽碳p ) = np 】r u i n d ( p ) 表示与等价关系族p 相关的知识，简记为u p ，称为k e e 关于【厂的p 基本知识i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴有时也直接称p 为基本知识 定义2 1 3 【4 1 给定知识库k = ( 兄) ，r 为u 上的等价关系，对每个子集xsu ， x 的冗下近似集旦x 和r 上近似集页x 定义如下： 宣x = u ( y u r i y 冬x ) ，瓦x = u ( y 叫r i y n x 多， 定义2 1 4 1 2 设p 和q 是u j = 的等价关系，q 的尸正域p o s p ( q ) 定义为： p o s p ( q ) = = u x u f q 隧 q 的p 边界域b n p ( q ) 定义为： b n p ( q ) = u p o s p ( q ) p 对q 的近似质量仰( q ) ( 也称为分类质量) 定义为： 仰( q ) = 可i p o s p ( q ) l 正域是根据知识p 能够准确地划分到q 中的等价类的对象集，边界域是不能准确划 分的对象集，分类质量可以反映p 对q 的近似能力，或者说p 相对于q 的正确分类能 力 。 定义2 1 5 1 4 1 四元组s = ( u ，a ，v ，) 被称为一个知识系统其中，u 是非空有限 对象集，称为论域：a 是非空有限属性集；v = uk 是属性值集，k 是属性。的值 5 域；，：u 肖_ y 是一个信息函数它为每个对象的每个属性赋予一个信息值， 即v o a ，z 阢，( z ，a ) 圪，有时也将，( z ，n ) 简记为口( 占) 定义2 1 6 【4 】在知识表达系统s = ( 阢a ，k ，) 中，对p a ，定义属性集p 的不 可区分关系i n d ( p ) 为 i n d ( p ) = ( z ，y ) u u l v a p ，n ( z ) = n ( 可) 】 定义2 1 7 【4 】一个决策表是一个知识表达系统s = ( 阢a ，e ，) ，其中a = cu d ，cnd 多，c 称为条件属性集，d 称为决策属性集有时决策表也记作s = ( 以a ，gd ) 定义2 1 8 1 4 0 设s = ( 阢a ，c ，d ) 是一个决策表，如果条件属性集c 的子集b 满 勋d s b ( d ) = p o s c ( d ) 且v a b ，p o s b 一 口，( d ) p o s b ( d ) ，则称b 为c 相对于d 的约 简，也称为决策表s 的约简 6 第三章一种基于分类质量的粗糙集模型 经典粗糙集只能够处理离散数据，对于连续数据需要进行离散化文献【4 6 系统 地总结了一些离散化方法，其中以逐个属性各自离散化为主流单属性离散化方法 由于极大地忽略了属性之间的关联性容易造成大幅度信息损失，且离散化方法及其 参数的选择直接决定着决策规则获取的质量，而不恰当的属性离散化方法将对规则 生成造成严重影响，比如引入冲突无法得到确定规则，存在无法决策的条件属性值 组合或一条数据对应多个规则，甚至可能会在约简后删去相对于约简集中属性来说 决策性能更好更重要的属性因此，本文采用模糊聚类方法对在整个属性空间中划 分论域形成条件类，在此基础上进行约简 3 1分类质量的计算算法 约简之前我们得先介绍一下分类质量的计算算法 设t = ( 阢a ，c ，d ) 是一个规范化了的连续值决策表( 即为防止”大数吃小数”的 现象已经将决策表的各条件属性的取值范围变换到了同一个区间里) ，c 是连续的条 件属性集，d 是离散的决策属性集，u = u l ，u n 为丁的论域又设b = a l ， a m ) 是c 的子集，a t i = a t ( 蛳) 是l “关于属性a t 的属性值分类质量伯( d ) 的计算算法如 下： 算法3 1 s t e p1i n p u tb s t e p2c o m p u t et h es i m i l a r i t yb e t w e e na n yt w oo b j e c t sa c c o r d i n gt o ，冶u i 7 勺) = 1 一d i s 忑( u , - , u a ， w h e r e d i s ( u ，) = ( ( 口“一。巧) 2 ) 1 7 2 i st h ee u c l i d e a nd i s t a n c eb e t w e e n 讹a n d i na t t r i b u t es p a c eb ，a n dm a xi st h em a x i m u mv a l u eo f d i s ( u i ，u a l u , 哟【厂) b u i l du pt h ef u z z ys i m i l a rm a t r i xr = ( p b ( u i ，u a ) t i n s t e p3c o m p u t et h et r a n s i t i v ec l o s u r eo fr d e n o t e db yt ( r ) = ( r , a t i n 【4 7 】 s t e p4a s c e r t a i nt h et h r e s h o l do ff u z z yc l u s t e r i n ga c c o r d i n gt ot h ef o l l o w i n g p r o c e s s ： 7 i ) s o r ta l lt h ee l e m e n t so f 7 巧k 歹) f r o mb i gt os m a l l ，d e n o t ea 1 a 2 a 七： i i ) c o m p u t es u p a i a l + i i i = 1 ，七一1 ，w h e r e 入i 一入“1r e p r e s e n t st h e s t a b i l i t yo ft h er e s u l to ft h et t hc l u s t e r i n ga n dd i s s i m i l a r i t ya m o n gt h ec l a s s e s p r o d u c e di nt h ei - t hc l u s t e r i n g ； i i i ) c h o o s e 入= s u p a 8 i a 。一入s + 1 = s u p h i 一入 + x l i = 1 ，忌一1 ) ) a st h et h r e s h - o l do ff u z z yc l u s t e r i n gt ok e e pa l le l e m e n t so ft h es a m ec l a s sp r o d u c e db yf u z z y c l u s t e r i n gs i m i l a re n o u g h s t e p5a c q u i r ec o n d i t i o nc l a s s e sb yc o m p u t i n gt h ea - c u tm a t r i x ( r ) a s t e p6c 。r e p u t et h ec l a s s i f i c a t i o nq u a l i 锣a u c c o r d i n gt o 佃( 。) = p 0 1 s 两b ( 一d ) i 在步骤2 中，我们必须先算出对象与对象两两之间的距离： d i s ( 呦) = ( ( 。圹口巧) 2 ) 1 2 , i ，歹= l ，n 然后求出这些距离中的最大值m a x ，并利用公式： p b ( 撕，呦) = 1 一d i s 忑( u i - , u i ) 求出u i 与哟之间的相似度p b ( u i ，呦) 接着，建立模糊相似矩阵冗= ( i u b ( u i ，) ) n n 在步骤3 中，采取文献【4 7 】中提到的平方自迭代方法求模糊相似矩阵r 的传递闭 包( 冗) ： r 一譬- - 4 ( r 2 ) 2 - 4 , _ r 2 2 = t ( r ) ， 平方法至多只需要 1 0 9 2 n 】+ 1 步便可得到传递闭包，其中舻= ro 兄表示冗的自合 成 步骤4 为模糊聚类阈值的选取流程：先将传递闭包( r ) 中的部分元素 r o l l 歹) 取出，按从大到小排列，设为入1 a 2 入七然后计算相邻阈值差 儿一 a i + i l i = 1 ，k 一1 的最大值并找出使其达到最大值的阈值作为模糊聚类阈值入， 如果有多个a i 对应最大相邻阈值差，取其中的最大者这样选取的目的是使等价类 与等价类之间足够相异，而同一等价类成员之间足够相似我们知道模糊聚类过程 其实是随着聚类阈值的跃迁动态进行的，随着阈值的逐步降低，类数目会越来越少 直至最后成为一类在这个过程中，如果对象集从某一聚集状态到下一聚集状态需 8 要把相似度的限制放宽很多，即某个邻近阈值差较大，那么我们认为这一阈值下的 类聚集情况是比较稳定的不仅如此，按照模糊聚类的思想，如果在本次聚类中，某 个等价类中有一元素与其它等价类的某一元素的相似度大于或者等于下一较小( 邻 近) 相似度阈值，则它们会合成一类，聚类状态便发生改变，这是由传递闭包的传递 性决定的这一信息告诉我们，如果对象们从这一聚集状态到下一聚集状态需要对 相似度阈值放宽的尺度越大，各等价类类与类之间相异程度也越大，否则总有两类 能很容易( 不需大幅度减少相似度阈值) 地合成一类 步骤5 是用来获取条件类的由于相似矩阵的传递闭包是等价矩阵，而等价矩 阵的截矩阵也是等价矩阵设等价矩阵t ( r ) = ( n j ) n n 的截矩阵( r ) a = 一f ，其 中7 乞_ 【o ，1 ) ，那么t “与属于同一类当且仅当r 0 = 1 ，由此便能得到决策表的条件 类而决策类仍按经典粗糙集定义处理由于这些条件类也都是等价类，所以可以 挪用经典粗糙集方法找到正域进而按步骤6 中的公式求取分类质量 由于本算法是在保持对象集自然聚集形态的基础上获取的条件类，所以不同于 经典粗糙集那样，即便决策表本身在属性集b 上是协调的，其所得到的分类质量，y b ( _ d ) 仍然有可能小于1 另外在经典粗糙集中，对于任意两个c 的属性子集b 1 ，岛，如 果b lgb 2 ，那么我们有i n d ( b 1 ) 2i n d ( b 2 ) ，【x b 。2m b 。以及3 b 。( d ) 7 b ：( d ) 7 c ( d ) 而在这一算法模型中该结论却不一定仍然成立 实际上，7 b ( d ) 根本不会随b 的变化而出现规律性变化，至少没有明显的变化规 律看下面这些例子 例3 1 表3 1 c ， 口1n 2 u l 0 10 8 u 2 0 3 0 1 u 3 0 70 2 i z 4 0 90 9 表3 1 是一个连续值决策表，a l 和a 2 是连续的条件属性，d 是离散的决策属性根据 分类质量算法，我们有7 t 口。) ( 1 z ) = 1 ，饥口： ( d ) = 0 ，y 口1 ，4 。) ( d ) = 0 5 ，于是可以得 至0 ，y t 。? ) ( d ) ，y 口。，。2 ) ( d ) ，y a l ( d ) ； 例3 2 表3 2 v n 1 n 2 牡1 0 20 1 i t 2 0 30 3 u 3 0 50 4 让4 0 60 6 表3 2 是一个连续值决策表，a l 和a 2 是连续的条件属性，d 是离散的决策属性根据 分类质量算法，我们有，y a 。 ( d ) = 1 ，饥口。 ( d ) = 0 5 ，1 a 1 , 1 1 2 ( d ) = 0 ，于是可以得 n t 口。，口。( d ) ，y 口：( d ) ，y 。 ( d ) 例3 3 表3 3 u 口1a 2 d 1 0 30 81 u 2 0 90 1 1 u 3 0 70 32 u 4 0 10 22 表3 3 是一个连续值决策表，口1 和a 2 是连续的条件属性，d 是离散的决策属性根据 分类质量算法，我们有7 口。) ( d ) = 0 ，y 口。 ( d ) = 0 2 5 ，饥口。m ( d ) = 0 5 ，于是可以得 至0 ，y 口。 ( d ) ，y t 口。 ( d ) ，y 口。： ( d ) 类似地，对于有两个以上的条件属性的决策表也可以举出相应地例子为什么 会出现这种现象呢? 事实上，无论是经典粗糙集的分类质量还是算法3 1 所得的分类 质量，对于给定数据集，都可以看作是属性集b 到离散点列0 ，l ，i i u l 的映射，从 某种程度上说7 b ( d ) 是j e 7 的函数，因此b 中的元素( 即条件属性) 之间的相互作用直接 决定t t b ( d ) 的大小在算法3 1 中，分类质量是由条件类决定的，条件类是由两两 之间的相似度( 大小及其顺序) 决定的，相似度是由对象集两两之间的欧几里得距离 决定的，因此在算法3 1 中，7 s ( d ) 是由属性之间通过欧几里得距离相互作用而得到 的然而欧几里得距离并不能保证在某属性集上各对象间距离的排列顺序与其子集 上各对象间的排列顺序一致，即便排列顺序一致，欧几里得距离也不能保证邻近值 1 0 的差的大小顺序一致正是由于欧几里得距离得到的相似度不具备这种差值保序性， 才造成- j y b ( d ) 变化不规律 然而这种现象是可以接受的在现实生活中，并不像经典粗糙集那样得到的信 息越多越利于决策( 正域随条件属性的增加单调不减) ，事实上有的信息是不必要的， 还有的信息甚至是干扰的，会降低人的分类能力，干扰决策，起负作用由此，我们 便提出了下面的启发式约简算法，试图删去一些与其它属性相抵触的负面因素或者 相对于其它属性来说不必要的因素，从而得到较高的分类质量 3 2基于分类质量的约简算法 设t = ( 阢a ，c ，d ) 是一个规范化了的决策表，c 是连续的条件属性集，d 是离 散的决策属性集分类质量的计算方法如下： 算法3 2 s t e p1c o m p u t eq o = 似( d ) s t e p2i n i t i a l i z et h ea t t r i b u t er e d u c t ，s e tb = c s t e p3 i fl b i 1 ，t h e nf o re a c h b ，c o m p u t e 怡一 口j ) ( d ) s t e p4e n df o r s t e p5c o m p u t eg m “= s u p “b 一 口j ( d ) l a j b 】= s t e p6i f 口m 醢q 0 ，t h e nq o = q m = ，b = b 一叼，w h e r e 哟i sa n yo n eo ft h e a t t r i b u t e ss a t i s f y i n g 佃一h ( d ) = q m 旺，g ot os t e p3 s t e p7o u t p u tt h ea t t r i b u t er e d u c tb 算法流程是这样的：首先找到这样一个属性，如果删掉这个属性所得属性集的 分类质量要比删去其它属性所得属性集的分类质量都大，且删除这个属性所得属性 集的分类质量比初始属性集分类质量还大，则删去它重复这个过程直至所有属性 都不可删 3 3规则获取 虽然经过约简处理后，我们有e d 耐( d ) 7 c ( d ) ，然而这并不能保证* 。d 眦t ( d ) 能够达到一个令人满意的阈值，边界域的存在直接影响着分类质量的高低事实上， 1 1 当某一个条件类的聚集粒度较大时，该条件类的元素具有不同决策值的可能性也会 增大，因而边界域扩增的风险也随之增大，这对于分类知识获取是很不利的为了保 持能被正确分类的正域而缩减边界域，我们用支持向量机方法来寻找一些划分超平 面来解决分类问题 ： “一对一 方法是多分类支持向量机的一个主要方法 4 8 】设t = ( u ，a ，c ，d ) 是连续值决策表，c 为连续的条件属性集，d = d 】为离散的决策属性又设决策 表丁有k 个决策类，记为u d = j d l ，d k ，第i 类d i 的决策属性值为d i “一对一” 方法就是构建k ( k 一1 ) 2 个分类器，每一个分类器都是从两个决策类训练来的对 于来自第i 类和第j 类的训练数据，我们需要解决以下问题： 沙m i n p 抄凡巧+ 尸莩 ( t s t ( u 巧) r 垂( u ) + 护1 一，i fd ( 饥) = d l ( 臼) r 圣( 1 “) + 一l + 夕i fd ( u t ) = 由 f y 0 ，地= ( a i r ，a 2 t n n t ) 瞅( 3 1 ) 其中训练数据砒通过函数西被映射到一个更高维的空间，p 是罚参数 当所有的分类器( 七( 后一1 ) 2 个) 都建立完毕，我们采取以下的投票策略：如果符 号函数s g n ( ( w i j ) t 垂c u ) + 护) 通知说z 在第i 类，那么第i 类得一票否则，第j 类增加 一票然后我们以最大票数决定未知类对象u 的类别这种投票方法被称之为”m a x w i 璐”策略而如果两个类别得票数目一样，则认为该策略失效，不是一个好策略，所 以转而选择票数稍小一点的类别