（计算机应用技术专业论文）模糊扩张矩阵中的参数优化研究.pdf

摘要 ! 曼自! ! ! ! 兰! e ! ! ! ! ! ! ! ! ! ! ! ! 曼! ! ! ! 曼! ! ! 目! ! ! ! ，! 目目自自目蕾i ! ! 篁e ! ! ! ! ! ! ! g ! ! ! ! ! ! 暑! ! ! ! ! ! ! # ! 量 摘要 同前，扩张矩阵学习已成为归纳学习的一个重要的分支。而模糊扩张矩阵是存 扩张矩阵基础上引入了模糊思想，使之能处理与人的思维和感觉有关的不确定性数 据，因而得到了广泛的应用。在模糊扩张矩阵的规则抽取过程中，由于生成的规则 所覆盖的示例之间有一定的重叠，则引入参数口、反，使之能在一定程度上减少 这种熏叠，从而减少生成规则的不确定性，提高分类结果的准确性。那么，如何选 取这三个重要参数是本文研究的中心问题。 本文首先讨论了扩张矩阵理论及其模糊扩张矩阵理论，对决策树与扩张矩阵、 清晰扩张矩阵与模糊扩张矩阵进行了比较，并提出了用遗传算法进行模糊扩张矩阵 参数优化的思想。进一步分析了参数对模糊扩张矩阵的分类结果在训练准确率、测 试准确率、规则数等方面所表现出的敏感性，详细论述了用遗传算法进行参数优化 的实旋方案。最后在c + + b u i l d e r 软件开发平台及m a t l a b 的基础上，通过实验对这 种方法进行了验证。实验结果证明，利用遗传算法得到的参数较优，可以使模糊扩 张矩阵的分类结果达到较好。所以，利用遗传算法获得优化参数是人们在用模糊扩 张矩阵以获得最优分类结果的一个良好方法。 关键词归纳学习；扩张矩阵；模糊扩张矩阵：模糊熵；遗传算法 a b s t r a c t n o w a d a y se x t e n s i o nm a t r i xl e a r n i n gh a sb e c o m ea ni m p o r t a n tb r a n c ho fi n d u c t i v e l e a r n i n g d u et oi n t r o d u c eo ft h ef u z z yi d e a ，t h ef u z z ye x t e n s i o nm a t r i xc a nd e a lw i t h u n c e r t a i n t ya s s o c i a t e dw i t hh u m a nt h i n k i n ga n dp e r c e p t i o n ，s oi ti su s e dm o r ea n dm o r e w i d e l y d u r i n gt h ep r o c e s so ft h er u l ee x t r a c t i o n ，t h ec a s e sc o v e r e db yt h er u l eh a v e s o m eo v e r l a p s ot h ee n t i r ep r o c e s so fb u i l d i n gf u z z ye x t e n s i o nm a t r i xi sb a s e do no 【、b 、 y t h ei n t r o d u c eo fp a r a m e t e r sc a nr e d u c es u c ho v e r l a pt os o m ee x t e n t ，d e c r e a s et h e u n c e r t a i n t yo fc l a s s i f i c a t i o na 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 nr e s u l t t h u s ，h o w t os e l e c tt h et h r e ei m p o r t a n tp a r a m e t e r si st h ec e n t r a lp r o b l e mo ft h ep a p e r i nt h i sp a p e r ，w ef i r s t l yd i s c u s st h et h e o r yo fe x t e n s i o nm a t r i xa n dt h ef u z z y e x t e n s i o nm a t r i x ；t h ed e c i s i o nt r e ea n dt h ee x t e n s i o nm a t r i xa r ec o m p a r e da sw e l la st h e e x t e n s i o nm a t r i xa n dt h ef u z z ye x t e n s i o nm a t r i x ；w ep r o p o s et h ei d e ao fo p t i m i z i n g f u z z ye x t e n s i o nm a t r i xp a r a m e t e r sb yt h eg e n e t i ca l g o r i t h mb a s e do nt h i st h e o r y s e c o n d l y w ef u r t h e ra n a l y z e dt h es e n s i b i l i t yo fp a r a m e t e r st ot h ef u z z ye x t e n s i o nm a t r i x c l a s s i f i c a t i o nr e s u l to nt h et r a i n i n ga c c u r a c y t h et e s t i n ga c c u r a c ya n dt h er u l en u m b e r a n dt h ei m p l e m e n t i n gs c h e m eo ft h eo p t i m i z i n gp a r a m e t e r sm e t h o dw i t hg e n e t i c a l g o r i t h mi s d i s c u s s e di n d e t a i l f i n a l l y , t h i sm e t h o d h a sb e e nv e r i f i e d t h r o u g h e x p e r i m e n tb a s e do nb o r l a n dc 十+ b u i l d e rd e v e l o p m e n tp l a t f o r ma n dm a t l a b t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eo p t i m a lp a r a m e t e rv a l u eg a i n e db yt h i sm e t h o dm a k e s f u z z ye x t e n s i o nm a t r i xo b t a i n i n gt h eb e s tc l a s s i f i c a t i o nr e s u l t s o ，g e t t i n go p t i m i z a t i o n p a r a m e t e rb yg ai s ag o o dw a yt o g a i nt h eb e s tc l a s s i f i c a t i o nr e s u l tb a s e df u z z y e x t e n s j o nm a t r j x k e y w o r d s ：i n d u c t i o nl e a r n i n g ；e x t e n s i o nm a t r i x ；f u z z ye x t e n s i o nm a t r i x ；f u z z y e n t r o p y ；g e n e t i ca l g o r i t h m 河北大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：至盈；三日期：塑年l 月止日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他 复制手段保存论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密囱。 ( 请在以上相应方格内打“”) 作者签名： 垂聱丝 导师签名：坦 日期：尘笪年月卫曰 日期：塑【年上月! 日 第1 章绪论 1 1 背景知识 第1 章绪论 学习是人类提高能力、获取知识的基本途径，而机器学习是使计算机系统具有智能 的t 要手段。机器学习是人工智能的核心问题之一，也是近年来此领域中的一个热门学 科，在知识获取、系统性能改进等方面广受重视。 正如人类有各种各样的学习方法一样，机器学习也有许多种学习方法。若按学习系 统使用的学习方法分类，一个学习系统按温斯顿1 9 7 7 年提出的分类方法可以分为机械 式学习、指导学习、解释学习、类比学习和示例学习等。其中示例学习( l e a r n i n gf r o m e x a m p l e s ) 是一种以归纳推理为基础的学习，示例学习是机器学习中较为成熟的分支， 它是从多个示例中归纳出一般性概念或一般规律的学习方式，即从某一概念的己给的正 例集合和反例集合中归纳产生出描述所有正例并排除所有反例的该概念的一般规则，故 示例学习又称概念获取，它已被公认为是专家系统发展的瓶颈。示例学习过程对领域知 识要求较少，但需有多个实例，是一种从特殊到一般的学习过程，所以又称为“一一般化” 学习方法，即归纳学习方法。被广泛的应用到模式识别、智能控制及专家系统的知识获 取等领域。 示例学习，是目前研究得较多的学习方法，其学习目的是为了获得新的概念、构造 新的规则或发现新的理论。示例学习，又可称为归纳学习。归纳学习就是从大量的经验 数据中归纳抽取一般的判定规则和模式。目前归纳学习的研究按研究方法的类型又可划 分为规则学习、决策树归纳学习、扩张矩阵学习和神经网络学习。其中，决策树( d e c is i o i l f r e e ) 学习是以实例为基础的归纳学习算法，通过一组无次序、无规则的实例推理出决 策树表示形式的分类规则。其中以o u i n l a n 于1 9 8 6 年提出的i d 3 为代表的算法“1 ，具 有描述简单、分类速度快、计算量小的特点，能归纳出一种较“好”的树，且适用于丈 规模数据集的学习问题。1 。，现已成为归纳学习的一个重要分支。而扩张矩阵学习”。1 能 够壹接生成规则，计算速度快，分类精度高，且适用于小规模数据集的学习问题”1 。 现确的示例学习算法主要分成两大类：覆盖算法和分治算法。覆盖算法生成归纳规 洞北大学工学硕士学位论文 则，一般是析取范式1 2 】；分治算法生成决策树。著名的覆盖算法有a q l l 、a q l 5 ”1 、a e i 、 a e 9 、h c v 、f c v 、g s 、i l ae 1 “、扩张图方法 1 5 ；分治算法有c l s 、i d 3 等。其中，扩 张矩阵的a e 算法系列的核心部分是扩张矩阵，将一些启发式策略用于扩张矩阵的路径 搜索 1 6 , 1 7 】，抽取一条规则实际等价于在扩张矩阵中搜索一条路径。优点是每次都试图寻 找覆盖例子数目最多的一致公式，这样可使覆盖整个正例集的一致公式的总数最少；不 足之处是仍不能保证总能找到最优解。相继出现的h c v 、f c v 算法主要的改进是在扩张 矩阵中提出新的进行搜索的启发式策略 1 8 , 1 9 。 随着现实数据的复杂性和不精确性的增加，具有精确描述特征的示例学习已不能适 应系统中不精确知识自动获取的要求，研究不确定环境中的示例学习显得尤为必要。模 糊思想表达了不精确知识，它的引入能处理与人的思维和感觉有关的不确定性，把模糊 理论引入到扩张矩阵的示例学习中，那么，在容许不精确数据、冲突数据和信息短缺等 方面，模糊扩张矩阵归纳学习具有较大的优势，因此，在现实生活的分类问题中应用更 为广泛。目前，模糊扩张矩阵属性选择的启发式算法是研究的热点 2 0 - 2 5 】，利用信息熵作 为启发式进行扩展属性的选择，效果非常理想。熵的概念出自c s h a n n o n 于1 9 4 8 年引 入的基于概率不确定性的信息论 。基于模糊扩张矩阵的启发式算法n 2 7 是扩张矩阵归 纳学习算法的一种推广，它使用最小路径模糊熵作为启发式来选择扩展属性。而模糊熵 是熵的概念的模糊推广。在模糊扩张矩阵寻找路径的过程，就是利用路径的模糊熵作为 选取属性的启发式函数，选择模糊熵最小的路径，得到的路径即为对应着的模糊规则。 生成的模糊规则对示例分类具有速度快、准确度高的优点，且适合处理模糊数据，得到 的模糊规则更鲁棒、更接近于自然，可应用于模糊专家系统等领域。 在模糊扩张矩阵的产生过程中，用模糊熵选择的路径不能像经典扩张矩阵那样将类 清晰的分开。这是因为生成的模糊规则( 即路径) 所覆盖的例子之间有一定的重叠，因 此由模糊扩张矩阵抽取规则的过程是在给定的参数哦胁y 的基础上进行的。参数龈且 ，的引入能在一定程度上减少这种重叠，从而减少分类的不确定性，提高分类结果的准 跚 生。ja 、肛y 的值在很大程度上影响路径模糊熵的大小，进而影响生成的路径( 即规 则) 和模糊扩张矩阵最终的分类结果。而这些值一般由领域专家根据经验或需要直接给 i ，这种人为的参与过分依赖于专家知识，从而可能使实际分类结果在规则数、准确率 方面达不到晟优。可见，研究参数吼从) ，取何值最优，对改善模糊扩张矩阵的分类结 第1 章绪论 果具有重要意义。 1 2 模糊扩张矩阵参数优化及其研究现状 我们通过不同的学习算法( 如a q l l 算法，a e l 学习算法以及改进算法) 构造扩张 矩阵。对扩张矩阵的评价有一些量化的评价标准，除最终分类的正确性应当放在第一位 给于考虑外，对于如何生成扩张矩阵，以及对带有模糊的语言术语也应给予考虑，这就 涉及到如何选取参数进行模糊程度的判断，从而更清晰地区分正负例是另外一一个需要考 虑的重要因素。 选择参数是为了减少语言术语所覆盖例子的重叠，降低分类的不确定性。但参数值 仍是人为给定的，并没有分析参数与模糊熵之间更为定性的关系，从而使参数对模糊扩 张矩阵分类结果的敏感性研究没有上升到理论阶段；并且参数选择是根据领域专家人为 给定的，对于不同情况的数据，参数的选择并没有理论支持。在这里，我们采用遗传算 法对参数进行优化，把优化值用于模糊扩张矩阵的规则抽取，使得正负示例分类准确率 较高，并且生成的规则简单。 目前，用遗传算法进行参数优化的方法已经得到了广泛的讨论，并在实际中得到成 功的应用。然而，这种方法在模糊扩张矩阵中使用是否是最优的，还有待于下一步继续 的研究。 本课题的研究得到了国家教育部重点项目( 0 3 0 1 7 ) 、河北省自然科学基金项目 ( f 2 0 0 4 0 0 1 2 9 ，6 0 3 1 3 7 ) 和河北省教育厅项目( b 2 0 0 3 1 1 7 ) 的支持。 1 3 本文主要研究内容 参数弧从y 的引入可以减少属性术语所覆盖例子的重叠，降低分类的不确定性。 口、肛y 取值的大小对分类结果会产生很大影响，而过去它的值基本由领域专家人为的 给定，这将导致分类结果达不到最优。本文试图分析给出的参数苏从y 与模糊熵之间 的关系，在很大程度上为我们对不同特征( 如数据对类的模糊性、模糊化中心的个数、 类的个数等) 的数据库，当用模糊扩张矩阵进行分类时如何选取参数积从y 提供了理 论依据，从而使产生的总规则数、分类准确率等方砸达到最优。本文主要内容如下： 河北大学工学硕士学位论文 第1 章简要介绍了机器学习中扩张矩阵归纳学习的产生及研究现状，简述了模糊扩 张矩阵的产生背景，随着示例学习研究的深入，具有精确描述特征的示例学习已不能适 应一一个系统中不精确知识自动获取的要求，研究不确定环境中的示例学习已非常必要。 然后讨论了模糊扩张矩阵产生过程中如何引入参数弧从r 及研究其最优值的意义。 第2 章介绍了模糊扩张矩阵的定义，并对决策树与扩张矩阵、扩张矩阵与模糊扩张 矩阵进行了比较，探讨了数据模糊化的方法。 第3 章描述了模糊扩张矩阵的启发式算法，详细介绍了参数矾晟y 的定义、作用 及意义，并利用遗传算法在模糊扩张矩阵产生过程中对参数以肛) ，进行了优化，对参 数甜、夙y 的最优取值有一个感性的认识，分析了不同的参数对模糊扩张矩阵产生规则 数、准确度的影响，而后还分析了选取不同中心点与参数之间的关系，以及对最终分类 结果的影响。 第4 章对应用于模糊扩张矩阵的参数选择及优化进行了实验，并对实验结果进行分 析。本章首先对多个数据库进行了测试并比较，对其中的i r i s 、p i h l a 、b r e a s t c a n c e l 数 据库给出了详细的数据资料，从参数的变化对模糊扩张矩阵产生的规则个数、精确度方 面进行了比较，并对实验结果进行了分析。 第5 章对本文所做的工作进行总结，阐述了尚待解决的问题及未来研究工作的方向。 4 第2 章扩张矩阵及模糊扩张矩阵 第2 章扩张矩阵及模糊扩张矩阵 示例学习是机器学习的一个核心领域，示例学习是对一些给定的正例集和负例集通 过洲练归纳产生识别正例和负例的概念的方法，它为专家系统的知识获取瓶颈问题的解 决提供了一条有效途径。目前国际上最有影响的示例学习系统有以i d 3 为代表的决策树 学习算法和以a q l 5 ( a e l ) 为代表的规则学习方法。扩张矩阵是研究示例学习的强有力工 具，它不仅是研究可学习理论的有力工具( 如示例学习的最优覆盖、最简公式、最优示 例学习问题都是n p 困难的证明) ，也是研究规则学习算法的有力工具( 如在a q l 5 算法 基础上，以扩张矩阵为工具发展起来的a e 类规则学习算法) 。 2 1 扩张矩阵的基本概念 近年来，人们越来越重视扩张矩阵在示例学习中的应用，比较而言，扩张矩阵这种 表示方法容易操作且易于实现。给出一个正例集和一个负例集，利用扩张矩阵方法对正 负示例进行正确的分类。下面简要描述扩张矩阵的基本概念8 1 。 定义1 假没有正例集及负例集分别为p e 和n e ，e + e p e ，e n e 。 p + = ( v l + ，v 2 + ，v n + ) ，e - = ( 。1 一，v 2 一，v n - ) ，p + 在p 一背景下的扩张矩阵定义如下： e m ( p + ip 一) 是一个矢量。 e m ( g + ie - ) = ，屹，r n 韩球，箩孑写 8 称为“死元素”，e m ( p + p 一) 称为正例p + 在负例p 一背景下的扩张矩阵。 定义2 矿在所有负例n e 下生成的扩张矩阵记为e m ( e + i n e ) ，即： 河北大学工学硕士学位论文 _ l e m ( p + ) 。2 k v ，! ，( v + v - ) 其吼铲k 帅一) 设e m ( p e ，n e ) 是p e 在n e 背景下的连接扩张矩阵，从中抽取规则等价于在e m 伊石，n e ) 中找一条由非死无素( 区分能力强的特征) 组成的路径，该路径涉及不同数 嗣的列( 特征) ，且选择信息熵最小的路径对应的生成规则。 2 2 决策树与扩张矩阵的比较 示例学习是机器学习中较为成熟的分支，它是从某一概念的已给的正例集合和负例 集合中归纳产生出描述所有正例并排除所有负例的该概念的一般规则，因而也被称作概 念获取。根据示例学习的知识表示可分为两大类一决策树归纳与决策规则归纳 2 8 - 3 1 1 ，前 者以i d 3 为代表，其特点是训练与分类速度都很快，适用于大规模的学习问题；后者以 a q l 5 或a e l 为代表，其特点是分类精度高，知识表达力强，适合于专家系统的知识自 动获取，其中a e l 以扩张矩阵( e x t e n s i o nm a t r i x ) 理论为基础，特别适合于专家系统的 知识自动获取，因而在专家系统领域引起更大的关注。a e 以扩张矩阵理论为基础，比 a q 训练速度快很多，但是其产生的决策规则有时不如a q 。 决策树与扩张矩阵的比较如下： 【d 决策树学习算法以i d 3 为代表，以决策树为知识表达形式，具有描述简单、分 类速度快的特点，特别适合于大规模的数据处理；扩张矩阵的特点是分类精度赢，其知 识表达力强，适合于专家系统的知识自动获取，即：小规模的数据处理，数据精度要求 较高的情况。 扩张矩阵算法可以直接生成规则：决策树算法则需要先生成决策树，再由根节 点到各个叶节点归纳出规则。下面由例子来说明决策树和扩张矩阵生成规则的区别。表 2 1 为打高尔夫球天气形势的例子，其中9 个正类、5 个负类，构造的决策树为图2 1 ； 在2 4 中定义2 和定义3 生成的为扩张矩阵。 第2 章扩张矩阵及模糊扩张矩阵 表2 ，l 打高尔夫球天气形势的例子 属性 编号 o u t l o o k t e m o e r a t u r eh u m i d i t vw i n d y 分类 1 s u n n y h o t 埘曲 f a l s en 2 s u n n y h o t h i g h t m en 3o v e r c a s th o t h i g h f a l s ep 4r a i nm i l d h i g h 蹦s ep 5r a i nc 0 0 1n o r m a lf a l s ep 6r a i n c o n ln o r m a lt r u en 7o v e r c a s tc o o ln o r m a lt 】m ep 8 s u n n y m i l d h i g h f a l s en 9 s u n n y c 0 0 ln o r m a lf a l s ep 1 0 r a i nm i l d n o r m a lf a l s ep 1 1 s u n n y m i l d n o r m a lt h ep 1 2o v e r c a s tm i l d h i g h t n e p 1 3o v e r c a s t h o t n o r m a lf a l s ep 1 4 r a i n m i l d h i g l l 1 h en 圈2 1 决策树 下面从执行过程和计算复杂性两方面来进行比较。 首先从理论上比较，即从执行过程来比较： ( 1 ) 决策树 从示例中抽取分类知识进行预测的过程主要包括四个阶段： 步骤1 数据预处理，将数据集中的连续型变量转化为离散型变量。清晰决策树算 法的数据预处理过程为对数据进行离散化处理；模糊决策树算法的数据预处理过程为对 数据进行模糊化处理。 步骤2 训练。利用i d 3 或f u z z y i d 3 算法 3 2 - 3 4 1 从训练示例中抽取分类知识产生决 河北大学工学硕士学位论文 策僻。 步骤3 产生规则。将每一条从根节点出发到叶子节点的路径转化为规则。 步骤4 进行推理和匹配。将训练例子与规则一一推理，得到分类的训练准确率； 然后将所有测试例子与规则匹配，得到分类的测试准确率。根据待定示例的属性特 征，按照某种匹配算法，选取与之适应的规则，判定其类别，进行分类。 ( 2 ) 扩张矩阵 扩张矩阵对于清晰示例或模糊示例的学习起着重要的作用，对于清晰示例直接用0 、 l 表示，对于模糊示例采用相似性度量的方法。利用扩张矩阵去寻找最优特征子集，从 而构成规则或模糊规则，扩张矩阵启发式算法进行预测的过程主要步骤如下： 步骤1 数据初始化。f s 为整个特征空间，s 为搜索到的特征子集，p 是给出的正 类，是给出的负类，e m ( p , i v ) 是p 关于所生成的连接扩张矩阵。 步骤2 数据预处理。利用k o n h o n e n sf e a t u r e m a p s 算法确定每一个属性的模糊中 心”，采用三角隶属函数计算隶属度，根据隶属度确定属性的模糊值。 步骤3 建立正例集p e 在反例集背景下的扩张矩阵e m ( p e i n e 3 。 步骤4 在e m ( p e i n e ) e p 找一列，要求 ，的元素最多，即包含最多的非死元素， 此列设为第j 例，f + - - f u 饼】；当存在 y 的元素个数相同的多列时，那么就选择其中 0 5 ) 的相应的语言描述变量的向量；d r p ) 是与蚴剀一对应的隶属度向 量。肘f 司是把各个肘r j ( e s e ( x ) ) 放在一起的连接矩阵，同理，d 阎是隶属度连接矩阵。 例如上面提到的打高尔夫球天气形势的例子( 表2 1 ) 就表示带有模糊术语的示例，表 2 2 和表2 3 分别表示正例和负例经过模糊化的隶属度值。 例如：从表2 1 、表2 2 中分别取第一行e l + ，则m ( e j + j _ ( s u n n y ，h o t ，h i g h ，f a l s e ) ， d ( e f + ) = ( 0 9 ，1 0 ，o 8 ，0 6 ) 。 定义2 7 1 模糊扩张矩阵e m 白+ 夕表示一个正倒对所有负例的矩阵，即为： 戈j y 旷( ，) ) 一肼旷) ) ， 。 。 ，= l2 ，n 蝴妒均j 都d 万劢j ， ， 半 茗 ，【 i l f 、j + 8 l me w 研 黔 河北大学工学硕士学位论文 阵为 例如：从表2 2 中取第一行e l + 与表2 3 中所有的负例集合n e ，生成的模糊扩张矩 e m ( e + ) k = o 10 41 00 4 0 70 70 80 1 1 o0 8o 80 4 o 61 0o 70 1 o ，10 51 o0 4 0 10 51 00 4 定义3 “死元素”：在模糊扩张矩阵e m ( e + j 旭= ) 中，如果其中的一个元素刁y ，则 x 。就叫做“死元素”；同理，若元素而”则x j 叫做“非死元素”。模糊扩张矩阵抽取 的条规则就是相应的一条由非死元素组成的路径。( 其中，是死元素的闽值) 嗣m 表示死元素。 例如：对于上例而言，死元素阈值y - - - o 4 ，则而y 的元素就用“。”表示。 e m ( e + ) k = 2 5 清晰扩张矩阵与模糊扩张矩阵的区分 扩张矩阵是研究示例学习的有力工具，然而传统的扩张矩阵理论是基于精确示例的 学习，没有考虑到实际应用领域中的模糊数据所引起的问题，当扩张矩阵理论应用于有 熏叠问题的示例时，原有算法将造成大量的时间和空间开销，已无法解决重叠区域的规 则生成问题。对于一个实际应用来说，各属性值间的重叠是普遍的客观存在的，规则学 习本身不能产生一个判别界面、不能清晰的区别概率语义层次及对不确定程度的具体描 述。所以，它们面向对象不同，解决的具体问题不同。模糊扩张矩阵较清晰扩张矩阵而 言相对比较复杂。 ( i ) 模糊扩张矩阵对清晰示例或模糊示例的学习起着重要的作用，对于清晰示例直 加瞄叮加加 7 8 o 5 5 十n 吼l o 0 一o 石 $ o l 0 第2 章扩张矩阵及模糊扩张矩阵 接用0 、l 表示，对于模糊示例采用相似性度量的方法。利用扩张矩阵去寻找最优特征 子集，然后进行规则或模糊规则提取。 清晰扩张矩阵处理的是符号型的数据，它的分类结果是分明的，它不能处理分类过 程中潜在的不确定性。当属性的取值有微小的变化时，有可能导致分类结果明显不合适 的突变。一般不具有稳健性，数据信息的不精确或缺少可能完全阻止例子的分类。 模糊扩张矩阵的归纳学习与清晰扩张矩阵归纳学习相比较，由于合理地处理了不确 定信息、噪音数据等问题，从而有较强的分类能力及稳健性，使知识的表示方式更为自 然，为决策者提供了丰富的决策信息。 ( 2 ) 清晰扩张矩阵，是从e m ( p 捌 中找一列，要求 ) ，的元素最多，即包含最 多的非死元素，此列设为第，例，f 卜凡惦j ；当存在 y 的元素个数相同的列有多列时， 那么就选择其e p y 的元素和最小的一列；寻找规则，直到e m ( p e l 酬= 西，则停止。 模糊扩张矩阵是在e m ( e + 1 到中找一个“非死元素”，并且相应连接此“非死元素” 的路径的信息熵e n t r o p y ( n e w p a t h ) 最小；由不同列的“非死元素”组成信息熵最小的路 径，就是要抽取的规则；如果e m ( p e i n e ) = # ，则停止，输出规则集r u l e _ s e t 年i i 不能被 规则覆盖的余下正例p e 。 可见，由清晰扩张矩阵抽取的规则，能够完全区分正例和负例；而由模糊扩张矩阵 抽取的模糊规则，只能某种程度的覆盖正例排除负例，前者能够清晰的区分正例和负例， 后者却不能清晰的区分正例和负例，这是因为示例属性特征值带有模糊术语，各个示例 之间有重叠。就要涉及到参数值的选取，不同的参数值就会生成不同的规则，影响最终 的分类结果。 ( 3 ) 选取初始示例不同，生成的结果就不同。在精确度一定的条件下，由模糊扩 张矩阵抽取的规则，有时，生成规则数目少且生成规则长度较短；有时则相反，即：规 则数目多且生成规则长度较长。这是因为生成扩张矩阵的初始示例每次选取不同，初始 值采用任意选取的方法，每次选取的初值都不同，这就要求实验多次，选取效果好的， 从而增加了工作强度。对于清晰扩张矩阵的初始示例的选取( 如a e l ) 是采用在正例中 相似元素最多而且所得到的代价值最高的作为第一粒种子。这样经过选取所得到的规则 减少了复杂度，但是也存在着缺点，例如当所得到的示例代价值相同时如何选择等问题， 这也是需要考虑的。可见第一个示例的选取比较重要，寻找性能好的第一个示例，再生 河北大学工学硕士学位论史 成扩张矩阵，这是我们今后研究的方向。 26 数据模糊化 从上述的例子( 表2 1 ) 可以看到，属性h u m i d i t y 的属性值有n o r m a l 和h i g h 。但 是人的感官的感觉程度是不一致的，比如同样的湿度( h u m i d i t y ) ，可能有人感觉“适 中”，有人觉得“较低”，有人就会觉得“很高”。又比如“天气状况”，其中“晴见多云”， 很难用“晴”或者“阴”来确定地描述。因此经典逻辑中“非此即彼”的概念必须得到 修正。为了解决上述问题，x z w a n g 提出了模糊扩张矩阵的方法，它是在传统算法基碓 上的模糊版本，模糊思想的引入能处理与人的思维和感觉有关的不确定性，因而应用更 为广“泛。 表2 2 经过数据模糊化的正例集 编号 o u f l o o k t e m p e r a t u r e h u m i d i t yw i n d y s u n n yo v e r c a s tr a i n h o tm n dc o o l h i g h n o r m a lt m ef a l s e l0 9o 1 o o1 o 0 0 0 oo 8o 20 ，4o 6 20 0o 7o 3o 8o 2 0 o o 10 9 o2 o 8 30 oo 1o 9o 7o 30 00 5o 50 50 5 4 0 0o703o 00 30 70 70 30 4o 6 5o o o 3 o 7o 00 o1 o0 01 0o 1o 9 61 0 0 0 o o1 00 00 o0 60 4o 7 o 3 了 0 90 1 0 o 0 o0 30 70 01 0o 9o1 8o7o 3o o1 oo oo o1 oo oo 2o 8 9090lo o0 20 80 0o 1o 91 o0 o 定义1 设某概念a 可表示为n 个模糊词，当给出该概念a 的值x 时，可根据各模糊词的 隶属函数肛。( z ) ，i = 1 , 2 ，n ，计算出概念a 的各个隶属度。( x ) ，i = 1 , 2 ，n ，则概 念a 的模糊分布为 盼，坂) ，其中心= 戌。 上述定义，将某概念的值用多个模糊词表示，比经典逻辑更为精确。如“晴见多云” 可以描述成s u n n y 为0 7 ，o v e r c a s t 为0 3 ，r a i n 为0 。或根据具体情况用其它描述来表示。 第2 章扩张矩阵及模糊扩张矩阵 模糊扩张矩阵结合了扩张矩阵的可理解性和模糊集合的表示能力，用来处理模糊性 和不确定的信息。模糊扩张矩阵算法可以看作是清晰版本的推广，而清晰的数据库亦可 看作是模糊数据的特例，因此，将模糊扩张矩阵算法运用于清晰数据也是完全可以的。 表2 2 是经过数据模糊化的正例集，表2 3 是经过数据模糊化的负例集。 表2 3 经过数据模糊化的负例集 编号 o u t l o o k t e m p e r a t u r e h u m i d i t y w i n d y s u n n yo v e r c a s tr a i n h o t m i l dc o o l h i g h n o r m a lt 札ef a l s e 10802 o o0 6 0 4 o 0 o0 1 0 o o l0 20 2o 7 ol 0 30 7o 0o 2o 80 3o 7 3o01 oo o0 oo 2o 8o 2o 8o o1 o 40 2o 6o 20 o1 0o 0o - 3o 7o f 30 7 51 o00 0 o 0 50 5o 00 o1 o0 01 0 河北大学工学硕士学位论文 第3 章模糊扩张矩阵的生成和参数优化 31 模糊规则产生算法的描述和执行 近年来，人们越来越重视扩张矩阵在示例学习中的应用，比较而言，扩张矩阵这种 表示方法容易操作且易于实现。基于扩张矩阵的示例学习目的就是产生覆盖正例同时排 除所有负例的规则，而且，生成的规则能够对未知示例进行正确的分类。关于扩张矩阵 的概念、定义在2 4 节中已经介绍，这里就不在重复。 31 1 模糊扩张矩阵启发式算法的描述 模糊扩张矩阵抽取规则就是寻找路径，即等价于在e l ( p e ，n e ) 中找一条由非死元素 组成的路径，该路径涉及最少数目的列( 属性) 。在e m ( p e ，n e ) 中先找到一个含有最多数 目的非死元素的列，然后在e m ( p e ，n e ) 中删去该非死元素所在的行，再在余下部分的矩 阵中寻找含有最多数目的非死元素的列，递归进行，直到矩阵变空为止。这样，所 得到的列( 特征) 可能较少，得到的规则长度较短。 f 面给出模糊扩张矩阵的启发式算法描述m ： 步骤1 初始化：f 卜磊p 为正例集合，n e 为负例集合，p a t h 为由模糊扩张矩 阵抽取的一条路径，规则集r u l e _ s e t = 办设0 5 凸基l ，0 肛0 5 ，o 珲o 5 ，当扩张矩 阵生成的p a t h 所覆盖正例集c p e ，c p e p e ，c p e = 选取e + 均为n e w p a t h 覆盖正 例的程度dg + c p e ) 。 步骤2 从正例集p e 中任意选取一个示例种子e + ，与所有负例n e 生成模糊扩张 矩阵e m ( e + ) ，p a t h = 磊n e w p a t h = ，p e i = p e ，c p e = 西。 步骤3 在e m ( e + i n e ) 中找一个“非死元素1 ，并且相应连接此“非死元素”的路径 的信息墒e n t r o p y ( n e w p a t h ) 最小。 i f p a t h 包含了e m ( e + i r , r e ) 中所有的“非死元素” t h e n 计算c p e ；p e = p e - c p e ；转步骤4 ； e l s e f o r ( c i 为e m ( e + ) 的一个“非死元素”而且p m t t 中没有用到的) ， 16 第3 章模糊扩张矩阵的生成和参数位化 n e w p a t i - p a t hu c f ) ，计算e n t r o p y ( n e w p a 删。 e n d f o r 步骤4 p w 烈7 h = p a 丁日u ( 非死元素g ) ； 分别计算e n t r o p y ( p a t h ) ，e n t r o p y ( n e w p a t h ) 和d n ( n e w p a t h ) i fe n t r o p y ( n e w p a t h ) e n t r o p y ( p a t h ) t h e np a 丁h = 心w m 7 h ，n e w p a t h = ，标记c i 为使用过且与c f 同一列的 元素也做标记，转步骤2 ； e l s e 计算c p e ，p e = p e c p e 。 步骤5 如果e m ( p e i n e ) = 驴，则停止，并返回f 否则转步骤3 。 步骤6 i fd n ( n e w p a t h ) f l , 输出n e w p a t h 对应的规则l ，n e w p a t h 和 r u l e _ s e t = r u l e _ s e tu l ， e l s ei f p e l # p e t h e n 转步骤1 。 步骤7 输出r u l e _ s e t 和雎( 不能被规则覆盖的正例) 。 算法特点：本算法具有两个优点。 生成模糊扩张矩阵，从中抽取出模糊规则。由模糊扩张矩阵的定义2 可知，当正 例t j 负例的属性值相同时，那么此属性区分正负例能力就弱，算法采用隶属度相减的方 法，结果所得的差值较小，此属性被选为生成规则的最优特征子集的可能性较小；但是， 当 三例与负例的属性值不相同时，则此属性区分正负示例的能力就强，从而选取区分能 力强的属性，达到选取最优属性生成规则。 选取信息熵最小的路径。在p a t h 的扩展过程中e n t r o p y ( n e w p a t h ) 的值越小，引 起的模糊混乱程度较低，形成的路径( 规则) 越好，覆盖正例较强，排除负例能力较高， 路径信息熵的计算方法： 设训练例子集p 含有p 个正例和n 个反例，则一个规则覆盖正例集眦的概率为： p = p a z h 覆盖e 的程度e ep e 】 覆盖负例集n e 的概率为： n = p a 掰覆盖e 的程度ie e ) 因而产生路径模糊信息熵为： 河北大学工学硕士学位论文 e n r r o p y ( p a t h ) 一考b s ：焘一考l o g ：p pp焘p 十九 十n 十n十n 根据上面的定义，应该从扩张矩阵中搜索这样一条较优的路径：能够覆盖尽可能多 的h 例、尽可能少的负例，使它能够最大限度地区分开正负例，对示例能够更好的分类。 本文将信息熵作为扩张矩阵的路径搜索评价标准，即将信息熵作为是否扩展p a t h ( 向 p a t h 中加入新的列，合并成新路径) 的个标准。从上面的启发式算法可以看出，在 p a t t t 的扩展过程中，e n t r o p y ( n e w p a t t l ) 值越小，形成的路径( 规则) 越好。因为 e n t r o p y ( n e w p a t h ) 的值越小，越倾向于覆盖较多的正例和很少的负例，越能最大限度地 区分正负铡。 3 12 模糊规则产生的执行过程 基于2 4 节的定义，由模糊扩张矩阵生成模糊规则的执行过程如下： 步骤1 数据预处理 末要进行数据的模糊化。将数据集按一定比例分成训练集和测试集，本系统中扩张 矩阵的模糊化过程依y u f e i y u a n m i c h a e lj s h a w 提出的算法3 3 1 确定每一个属性的模糊 中心，并由此中心采用三角隶属函数计算隶属度，根据隶属度确定属性的模糊值( 如图 3 1 ) ，从而模糊化训练集及测试集( 如：生成表1 2 ，1 3 ) ； m e m b e r s l p 1 0 o 5 o o 图3 1 模糊示例集的隶属函数 步骤2 根据上面提到的模糊扩张矩阵启发式算法，建立正例集尸e 在负例集背景 f 的模糊扩张矩阵e m ( p e i n e ) ； 步骤3 得到规则集。从模糊扩张矩阵中搜索到路径集即规则集； 步骤4 进行推理和匹配。将训练例子与规则一一推理，得到分类的训练准确率， 然后将所有测试例子与规则一一匹配，得到分类的测试准确率。 第3 章模糊扩张矩阵的生成和参数优化 3 2 优化参数的定义 在模糊环境下，模糊熵是一种重要的启发信息，但由于生成的是模糊规则，它有一 个与不确定性有关的真实度，这种真实度影响着规则的性能( 训练精度，测试精度等) ， 故不确定性对模糊扩张矩阵抽取规则而言或许是一种更重要的启发信息。其抽取规则的 癌发式算法是基于不确定性的减少，因此，要涉及到参数闽值的选择，即涉及到研究参 数瞳、肛y 对模糊扩张矩阵生成规则的影响，以及对最终分类精度的影响。参数甜表示 由模糊扩张矩阵得到的路径及与之相对应规则覆盖正例的程度；表示由模糊扩张矩阵 得剑的路径及与之相对应规则覆盖负例的平均程度；y 表示模糊扩张矩阵的“死元素” 的标准，能够达