（控制理论与控制工程专业论文）基于概念学习的模糊规则提取方法的研究.pdf

大连理工大学硕士学位论文 摘要 概念学习方法是归纳学习的核心问题，指学习已知类别的训练样本。随着规则提取 在专家系统、模式识别、图像处理、语音识别等领域的广泛应用，基于概念学习的规则 提取算法得到越来越多人的关注。 本文首先对两个经典的归纳学习算法：a q 算法和决策树算法进行了研究，指出了这 两个算法在理论研究和实际应用中的一些不足。本文在用归纳学习方法提取模糊规则领 域所作的一些工作： 1 提出了基于子集度和向量欧氏距离等的模糊蕴含算子n f i o ，创建了基于这个模 糊蕴含算子的规则提取算法r e n f i o ( r u l e se x t r a c t i o nb a s e do nn f i o ) 。r e n f i o 算法 将学习过程分为两步：第一步，对每一类样本取蕴含度大的简单概念作组合；第二步， 找出每类的最好描述，即与训练样本拟合得最好的规则。实验证明该蕴含算子比其它算 子对概念之间的蕴含关系描述更准确。r e n f i o 算法与其它规则提取算法相比有如下优 势：搜索概念速度更快；预测精度更高；描述规则更简单。 2 提出了用正样本和反样本提取模糊规则的模糊候选删除算法，在由属性构成的概 念空间中，找到一个能够覆盖所有正样本和排除所有反样本的最佳概念描述。如何利用 训练样本在训练样本的属性假设空间进行学习是概念学习的一个重要问题，覆盖算法 ( a q 系列) 和分治算法( 决策树) 是处理该问题的两个著名算法，而模糊候选删除算法与它 们相比有如下优势：只需遍历一遍训练集，即可针对多样本的数据集；对连续量数据分 类能力强；抗噪性强。通过i r i s 和w i n e 数据集的实验证明了模糊候选删除算法的有效性 和实用性。 3 给出了n f i o 算子的三个应用：属性约减、求单个样本的模糊描述、求误分类样 本的描述。通过三个数据集的实验可以证明，用n f i o 约减后得到的样本的属性，是对 分类贡献最大的属性，而且可以找到最好的分类属性。用n f i o 求出的单个样本的模糊 描述与第三章求得的基本一致，从而证明其有效性。误分类样本是模糊规则没有覆盖的 样本。求它们的描述可以补充模糊规则，提高规则对训练样本的覆盖度。 关键词：模糊蕴合算子；模糊候选删除；归纳学习；a f s 模糊逻辑；模糊规则提取 基于概念学习的模糊规则提取方法的研究 大连理工大学硕士学位论文 r e s e a r c ho nm e t h o d so ff u z z yr u l e s e x t r a c t i o nb a s e do nc o n c e p t l e a r n i n g a b s t r a c t c o n c e p tl e a r n i n gw h i c hl e a r n sk n o w l e d g ef r o ms i g n e dt r a i n i n gd a t ai st h ee s s e n t i a li s s u e o fi n d u c t i v e1 e a r n i n g w i t ht h ew i d e ri m p l i c a t i o no fr u l e se x t r a c t i o ni ne x p e r ts y s t e m ，p a t t e r n r e c o g n i t i o n , i m a g ep r o c e s s i n ga n ds o u n dr e c o g n i t i o n , r u l e se x t r a c t i o na l g o r i t h m sb a s e do n c o n c e p tl e a r n i n gh a v ei n t e r e s t e dm o r ea n dm o r ep e o p l e t l l i sp a p e rf i r s t l yo v e r v i e w st h et w oc l a s s i c a li n d u c t i v el e a r n i n ga l g o r i t h m s ：a qa l g o r i t h m a n dd e c i s i o nt r e ea l g o r i t h m s o m ei n s u m c i e n c i e so ft h e mi nb o t ht h e o r ya n dp r a c t i c ea r e i n d i c a t e d t h e nt h ew o r kw eh a v ed o n ei nt h ef i e l do fr u l e se x t r a c t i o nb yi n d u c t i v el e a r n i n g m e t h o d si si n t r o d u c e dp a r t i c u l a r l y 1 af u z z yi m p l i c a t i o no p e r a t o r ( c a l l e dn f i o ) b a s e do n s u bt h r e s h o l d v e c t o r s d i s t a n c ee ta la n daf u z z yr u l e se x t r a c t i o na l g o r i t h mb a s e do nn f i o ( c a l l e dr e n f l 0 ) a r ep u tf o r w a r d t h el e a r n i n gp r o c e s so ft h er u l e si sm a d ei n t ot w os t e p sb y i 也n f i o ：( 1 ) g e tt h ec o m b i n a t i o no f e a c hc l a s s sd e s c r i p t i o nw h i c h h a st h el a r g e ri m p l i c a t i o n ( 2 ) f i n dt h eb e s td e s c r i p t i o no fe a c hc l a s s ，a n dt h a ti sf i n d i n gt h eb e s tr u l e sc o v e rt h et r a i n i n g d a t a e x p e r i m e n t ss h o wt h a tn f i og i v e sab e t t e rd e s c r i p t i o no fi m p l i c a t i o nr e l a t i o n s h i p b e t w e e nc o n c e p t s c o m p a r e dt oo t h e r s ，t h ea d v a n t a g e so f 砌狲f i oa l g o r i t h ma r e ：s e a r c h c o n c e p t sq u i c k l y ；p r e c i s i o no fp r e d i c t i o nf o rn e ws a m p l e si sh i g h e r ；t h er u l e sa r ee a s i e r 2 t h i sp a p e ra l s og i v e sf u z z yc a n d i d a t e e l i m i n a t i o na l g o r i t h mt oe x t r a c tr u l e su s i n gb o t h p o s i t i v ea n dn e g a t i v ei n s t a n c e s i nt h ec o n c e p ts p a c ec o n s t r u c t e db yf e a t u r e s ，w ef i n dag o o d d e s c r i p t i o nn l a tc a l lc o v e rp o s i t i v ei n s t a n c e sa n de x c l u d en e g a t i v ei n s t a n c e s h o w t ol e a r ni n t h e f e a t u r eh y p o t h e s i ss p a c ei sa ni m p o r t a n ti s s u eo fc o n c e p tl e a r n i n g a qa l g o r i t h ma n d d e c i s i o na l g o r i t h ma r et w of a m o u sm e t h o d st h a tc a nd e a lw i t ht h ep r o b l e m c o m p a r e dt o t h e m ，f u z z yc a n d i d a t e e l i m i n a t i o na l g o r i t h mh a st h ef o l l o w i n ga d v a n t a g e s ：s e a r c hc o n c e p t s p a c ef o ro n l yo n c ea n ds ot h i sa l g o r i t h mc a nc o p ew i t hl a r g ed a t as e t ；h a sas t r o n g e ra b i l i t yo f c l a s s i f i c a t i o na st oc o n t i n u o u sd a t a ；i tc a l ld e a lw i t hn o i s yd a t a r e n f l 0a l g o r i t h m s e f f i c i e n c yi st e s t i f i e db vi r i sd a t a s e ta n dw i n ed a t a s e t 3 w ea l s og i v et h r e ea p p l i c a t i o n so f n f i o ：f e a t u r e se x t r a c t i o n ；o b t a i n i n ge a c hi n s t a n c e sd e s c r i p t i o n ；g a i n i n gw r o n gc l a s s i f i e d i n s t a n c e s d e s c r i p t i o n e x p e r i m e n t so nt h r e ed a t a s e t sh a v ep r o v e dt h a tt h ef e a t u r e se x t r a c t e d b vn f i oa r et h em o s tu s e f u lo n e sf o rc l a s s i f i c a t i o na n dab e s tf e a t u r ea l s oc a nb ef o u n d e a c h i n s t a n c e sd e s c r i p t i o nf o u n db vn f i oi sn e a r l yt h es a m ea st h eo n ei nc h a p t e rt h r e ea n dt h a t i l l u m i n a t e st h er i g h t n e s so ft h i sm e t h o d w r o n gc l a s s i f i e di n s t a n c e sa r et h eo n e sn o tc o v e r e d i i i 基于概念学习的模糊规则提取方法的研究 b yf u z z yr u l e s t h e i rd e s c r i p t i o nc a nc o m p l e m e n tt h ef u z z yr u l e sa n di m p r o v et h ea c c u r a c yo f t r a i n i n gd a t a k e yw o r d s ：f u z z yi m p l i c a t i o no p e r a t o r ；f u z z yc a n d i d a t e e l i m i n a t i o n ；i n d u c t i v el e a r n i n g ； a f sf u z z yl o g i c ；f u z z yr u l e s e x t r a c t i o n i v 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。、 作者签名：互圣豳亟 导师签名： 丑垃年彳月上日 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：翠幽劢 日期：迎星：圭：2 星 大连理工大学硕士学位论文 1 绪论 归纳学习( i n d u c t i v el e a r n i n g ) 是机器学习发展最核心、应用最广泛的一个分支【j 】， 也是模式识别理论与人工智能相衔接的关键之一。归纳学习旨在从大量的经验数据中归 纳、抽象出一般的规则和模式。由于其依赖于数据间的相似性，所以又称为经验学习或 基于相似性学习，是知识获取的重要手段，在专家系统、模式识别、图像处理、语音识 别等领域都有着重要的应用。由于归纳学习是以逻辑推理为基础，因而成为机器学习中 最成熟的分支之一。概念学习是归纳学习的主要方法，规则提取是归纳学习的一种重要 应用。概念可以理解为对一组具有某种共同性质而区别于其他对象的抽象表示【2 】。应用 比较多的归纳学习方法是规则学习方法、决策树学习方法及科学发现方法。很多学者用 这些方法提取实际数据的模糊规则，使得归纳学习方法得到了更深入的研究和应用。 本文通过学习经典的归纳学习算法，针对这些算法存在的问题，提出了新的基于归 纳学习的概念学习思想的算法。 1 1归纳学习方法的研究背景和意义 归纳学习是指给定关于某个概念的一系列己知的正例和反例，从中归纳出一个一般 的概念描述。归纳学习能够获得新的概念、新的规则以及新的理论。它的一般操作主要 是泛化( g e n e r a l i z a t i o n ) 和特化( s p e c i a l i z a t i o n ) 。所谓泛化，是指扩展一个假设的语义 信息，使之能够包含更多的正例，应用于更多的情况。与之相反，所谓特化，是指缩小 一个假设的语义信息，使之能够排除更多的反例，用于限制概念描述的应用范围。 归纳学习起源于1 9 世纪的哲学和心理学研究。2 0 世纪中叶，人工智能领域开始对 其进行研究。e b h u n t 是用计算机程序模拟人类归纳学习的先驱之一，他在1 9 6 2 年至 1 9 6 6 年间研制了从c l s 1 到c l s 9 的一系列概念学习系统。7 0 年代中期归纳学习的研 究逐步发展，研制出一批归纳学习系统，如i d 3 和a q l1 等。进入8 0 年代以后，归纳 学习成为机器学习研究的焦点之一。到目前为止，归纳学习已得到了广泛的应用：归纳 学习理论决策树分类理论在电力系统的电压控制的应用【3 】【4 1 ，构建可以确定低压限的 恰当值的决策树；电影介绍系统【5 】：构建决策树表示使用者的偏好，然后用分类决策树 预测一个新的事物的类别；临床数据分析6 】【7 】：用构造的决策树收集诊所的信息；市场 基于概念学习的模糊规则提取方法的研究 数据分析【8 】：用决策树得到决策规则；用a q 方法提取描述规则的文本识别应用中【9 1 ， 归纳学习用于属性提取；动态系统的模糊规则决策【l o 】；智能报警系纠1 1 】； 应用比较多的归纳学习方法是规则学习方法、决策树学习方法及科学发现方法。目 前归纳学习的研究在深度和广度上不断扩展。就广度而言，一方面不断有各种传统的或 者新提出的归纳学习修改算法出现，另一方面，不断有新的数学方法引入归纳学习。就 深度而言，已经有许多研究探讨基于各种不同模型的归纳学习的统一方法。 1 2 经典归纳学习方法 机器学习中用得最多的方法是归纳方法【12 1 。知识工程是基于知识的，而知识是通过 学习过程才可获得。一个典型的学习环境是可以被看作概念学习的模式分类问题【l3 1 。学 习过程来源于经验世界，只有通过人类对经验世界的感知，才能从中概括与归纳，并通 过选择形成公理，随后进行演绎推理。分类就是寻找一个分界面，最小化误分率4 1 。分 类规则描绘了知识表示的一个重要方法，这样人们在机器学习著作中提出了许多不同类 型的方法，来从正样本和反样本集中推导分类规则到一个概念上【1 5 , 1 6 , 1 7 , 1 8 】。 规则学习是从一些给定的正例集合反例集中通过训练归纳，产生识别正例和反例的 概念的方法，是归纳学习的一个重要分支。最早的规则学习算法是m i c h a l s k i 的准优算 法( q u a s i o p t i m a la l g o r i t h m ，简称a q 算法) 。在a q 算法中，每个例子被表述成选择子的 合取，算法将依据所给的例子，归纳出一个概念集合k = 毛，乞9o o 9 吒) ，在这个概念集合 中，所有概念覆盖的例子的并集包含正例集，并且不存在任何岛覆盖反例。我国的洪家 荣教授提出了扩张矩阵理论，扩张矩阵是研究规则学习的强有力的工具。利用扩张理论， 己经证明了一些归纳学习优化问题，例如最优覆盖、最简公式、最优示例学习问题都是 n p 难题，并且还出现了些扩张矩阵理论为基础的规则学习算法，如a e l 、a e 5 、a e 9 、 h c v 和f c v 等。 决策树是用于监督学习的一种常用方法，是应用最广的归纳推理算法之一。它是用 决策树的形式来表示所获取的概念。i d 3 算法是一个著名的决策树归纳算法，它是“分 割示例学习算法 的代表。它的例子用“属性值”对表示，每个例子表示类集合中 的某一个。i d 3 从根节点出发，递归地形成决策树，在每个节点，i d 3 都选择一个属性， 用它的值来扩展该节点，通常属性有几种取值就会产生几个分支，直到每个节点上的实 例都属于同一类为止。i d 3 偏向于深度较小的决策树。c 4 5 是i d 3 的改进版，非常流行， 被q u i n l a n 称为“人工智能的程序 ，它的最新功能是能够将决策树转换为相应的规则， 并解决了具有连续值属性的数据学习问题。 大连理工大学硕士学位论文 科学发现是用计算机来模拟人类发现物理、化学定律的方法。科学发现是一种无导 师的归纳学习方法，发现的目标通常不确定，代表性的科学发现系统有l a n g l e y 的 b a c o n ，l e n a t 的a m ，k o h e n 的f a h r e n h e i t ，m i c h a l s k i 的a b a c u s 以及递归函数法 等。其中l a n g l e y , s i m o n 和b r a d s h a w 等于1 9 7 6 至1 9 8 3 年研制了六个版本的b a c o n 系统。b a c o n 是科学发现的一种公式发现系统，通过一定的启发式来发现实例空间的 数据对应关系，并以公式的形式描述出来。 特征子集选择是归纳学习的一个重要研究内容，也是机器学习和模式识别中非常困 难而有意义的一个课题。f s s 问题是指从一个大的候选特征集合中选择一个较好的有代 表性的子集来一致地描述己知样本集。国内外学者对特征子集选择的问题上做了大量的 工作。我国学者陈彬证明了最小特征子集选择问题( o f s s 问题) 是n p 难题。因此寻 找一个较好特征子集选择的启发式算法是必然的。 归纳学习也需要考虑一定的问题。归纳学习企图从给定的有限的少数样本空间推导 出一个完整的、正确的描述。这样的样本空间所要考虑的主要问题包括两个，一个是样 本的质量，另一个是样本空间的概念的搜索方法。数据是归纳的素材，应该是无二义性 的，搜索数据集的目的在于选择合适的数据，以便证实或否定类描述。数据集的搜索方 法往往与类描述空间有关，常用的方法有：选择最有利于划分类描述的例子，以便尽 快缩小寻找归纳断言的范围。选择最有希望的类描述，再选择适当的数据来证实它。 选择否定某些类描述的数据。与样本空间有关的问题是对样本空间的要求和样本空间 的搜索方法。对空间的要求有两方面：空间包括归纳断言；空间的表示方法不仅应该适 合归纳推理，而且要与例子的表示一致。前者关系到能否学习到要求的归纳断言，后者 影响归纳学习过程的难易程度。 基于以上两个问题，本文提出了搜索概念空问的基于蕴含算子的模糊规则提取算法 和选择有效样本组成训练样本空间的模糊候选删除算法。并且，这个模糊蕴含算子可以 进行属性选择。以下进行简要介绍这两种算法。 1 3 模糊蕴含算子与蕴涵度 模糊数学是由美国加利福尼亚大学控制论专家l a z a d e h 教授提出的【1 9 】。模糊数 学解决了很多用精确数学难以解答的问题。z a d e h 教授用 0 ，1 区间内的数来描述事物 的模糊性，取代了原来的 0 ，1 ) 二值逻辑 3 1 。模糊数学诞生至今4 0 多年，它的应用触角 已涉及到自然科学，社会科学的各个领域，尤其在冶金、气象学、生物学、心理学、电 子学、计算机科学、控制论、物理学、信息论等学科领域【2 0 】。模糊数学在众多领域的广 泛应用说明它与人的主观意见有很多共同的地方。 基于概念学习的模糊规f i u 提取方法的研究 模糊蕴含是非常重要的二元模糊连接词，也是模糊逻辑推理的核心内容，现在研究 最多的模糊蕴含算子是基于t 模的r 蕴含算子和基于f 余模的s 蕴含算子。由于统一模 是，模和，余模的自然推广，可以构建基于统一模的天蕴含算子和s 蕴含算子。从文献 4 d 0 可明显看出，在模糊推理系统与模糊逻辑控制器中，最好的模糊蕴含算子的选择是 一个基本问题。 人们思维都是用语言进行的，在识别和判断事物时，使用条件语句，即如果彳则b 或如果z 是a 则y 是b 这样的形式，或更复杂一些的多重条件语句。在数理逻辑中，把 自然语言的如果彳则召抽象成为一个公式ajb ，这个式子称为蕴涵式。读作a 蕴涵b ， 虽然这一蕴涵式的含义是丰富的，但它在一般的数理逻辑中只能取两个值，即真或假值。 诚然，在现实生活中，由于蕴涵式中的命题变量么或曰的不确定性( 或叫模糊性) ， 所以，必然使a jb 也具有模糊性。例如： 如果a 是大则占是小 如果4 不够则b 要多 这里诸如a 是大，曰是小，a 不够，b 要多，都是一些不明确的，不确定的量，如 果还要用蕴涵式，显然，这样得到的“a 是大召是小 的值就不止一个，也就是说“彳 是大j b 是小这个式子有个真假程度的问题，这就是我们要讨沦的蕴涵度概念产生的 背景。 由于蕴涵度的概念是从实际中抽象出来的，有着强烈的实际背景，而且可以建立一 个蕴涵度空间。所以，我们可以利用蕴涵度概念来解决一些实际问题。 本文根据模糊蕴含算子的意义，定义了一个基于向量距离和真值度的模糊蕴含算 子，样本在两个概念上的隶属度代入模糊蕴含算子，得到两个概念间的蕴涵度。这个蕴 涵度表示了彳和丑两个概念的ajb 为真的程度。 1 4 模糊候选删除算法 候选删除算法是用正样本逐步一般化最特殊的假设【2 1 1 ，用反样本逐步特殊化最一般 的假设，最后得到某类样本的描述的上界和下界。候选删除法由m i c t h e l l ( 1 9 7 7 ，1 9 8 2 ) 提出，这一算法己经应用于质谱分析中的规则推理以及应用于学习搜索控制规则。它的 一个最大的实际限制是它要求训练数据是无噪声的。m i t c h e l l ( 1 9 7 9 ) 描述了该算法的一种 扩展，以处理可预见的有限数量的误分类样例，h i r s h ( 1 9 9 0 ，1 9 9 4 ) 提出一种良好的扩展 以处理具有实数值属性的训练样例中的有限噪声。h i s r h ( 1 9 9 0 ) 描述了一种递增变型空间 合并算法，它将候选取删除法扩展到能处理由不同类型的值约束表示的训练信息。来自 每个约束的信息由变型空间来表示，然后用交叠变型空间的办法合并这些约束。 大连理工大学硕士学位论文 模糊候选删除算法使用具有模糊值的样本，并且在寻找目标概念的上下界过程中， 可以发现噪声样本，从而具有良好的抗噪性。 i ， 1 5 论文的章节安排 第二章介绍了数据预处理方法的使用背景和常用方法，并给出常用的数据预处理方 法；介绍了a f s 模糊逻辑，由于本文的一些模糊定义是基于a f s 理论的。 第三章首先分析了模糊蕴含算子的发展过程，给出一些常用的模糊蕴含算子，并提 出了一个新的模糊蕴含算子：n f i o 。接着对它的有效性进行分析，提出了基于这个模 糊蕴含算子的规则提取算法，并用i r i s 数据，w i n e 数据，w d b c 数据和w b c d 数据试 验证实算法的有效性。 第四章首先介绍经典概念学习的两个方法：f i n d s 算法和候选删除算法，在此基础 上提出了模糊候选删除算法，并用i r i s 和w i n e 数据检验其有效性。 第五章探讨用n f i o 约减属性，用于单个样本规则提取和误分类样本的规则提取等 n f i o 算子的其他应用。 基于概念学习的模糊规则提取方法的研究 2 数据的预处理及a f s 理论框架 本文提出的模糊规则提取算法都是针对实际数据而言的，而实际数据库中的数据经 常会由于人为的原因而含有记录值错误、记录值丢失、记录值特殊等等的噪声。因此， 需要在使用提取规则算法之前，处理一下需要使用的数据，即对数据进行预处理。本章 将对数据预处理的背景、方法和应用作简单的介绍，后三章的算法都使用到了这些方法。 在执行模糊规则提取算法时，我们使用了隶属度这一概念。隶属度是样本属于某一 个概念的程度，隶属函数的定义将直接影响算法的应用结果。本文的隶属函数定义采用 a f s ( 模糊公理集) 定义的公式。a f s 是根据人的思维逻辑，基于z a d e h 的模糊集思想 定义的一种模糊逻辑。它比现有的模糊逻辑更接近人的思维逻辑。本章的第四节对a f s 做了简单介绍。 2 1数据预处理的背景 现实中的数据库很容易受到噪声数据、数据丢失、数据不一致等的影响【2 2 1 。如何对 数据进行预处理，才能提高数据的质量，进而提高挖掘出的规则的质量；如何对数据进 行预处理才能改善数据的有效性，使挖掘数据规则变得简单等问题成为研究的热点。数 据预处理方法解决了这一问题。数据预处理有很多方法，如：数据清理，数据整合，数 据转换，数据约减等。 数据预处理是很必要的。举个例子说：假如你是一家大型超市的经理，现在需要调 查这个月的销售情况。你可以查看数据库中的记录，例如：商品的类别，商品价格，商 品的销售量等数据属性。你当然希望调查的数据值都被记录下来，然而，经常事与愿违。 有一些数据没有被记录。而且，有时候数据记录者可能记录错误、特殊的值等。换句话 说，你的信息是不完整的、有噪声的、不一致的。这些都将影响数据分析的结果。因此， 数据预处理是很必要的。 2 2 相关工作 数据清理的工作是填补丢失数据、平滑噪声数据、解决数据不一致性等。干扰数据 可能造成挖掘过程的困扰，得出不可信的输出。尽管大多数挖掘方法都有自己处理不完 整数据或噪声数据的方法，它们大多是不具备鲁棒性的。因此，一个有效的预处理过程 就是在使用之前清理数据。 对于丢失的数据值，可以采用以下方法： ( 1 ) 忽略这个样本：当类标签丢失的情况下通常采用这个方法； ( 2 ) 人工手动填入丢失值：通常比较耗时，尤其当大的数据库有很多丢失值时： 大连理工大学硕士学位论文 ( 3 ) 用常量填补丢失值：例如用“u n k n o w n 填补所有丢失值，方法简单但不推荐； ( 4 ) 用属性的均值填补丢失值； ( 5 ) 用同一类的这个属性的均值填补丢失值； ( 6 ) 用出现次数最多的值填补丢失值。 对于噪声数据采用的方法有： ( 1 ) b i n n i n g 方法：对于排序后的数据根据临近值； ( 2 ) 聚类方法：本文采用的是聚类方法中的f c m 方法； ( 3 ) 将计算机和人的观察结合起来； ( 4 ) 回归方法：线形回归是找一条直线拟合两个变量。 数据整合是指将不同的数据库资源、不同的文件综合起来。因为在不同的数据库中 一些属性表示的是相同的概念，而名字不同，这样就可能导致不一致或是冗余。 在不同的数据库中分析数据，需要考虑属性的冗余。可以用相关性方法找出冗余属 性。 当你想要用基于距离的数据挖掘算法分析数据时，如神经网络，最近邻分类器，聚 类等，如果数据被归一化，得到的结果会更好些。这就是数据转换。方法包括： ( 1 ) s m o o t h i n g 方法：包括b i n n i n g 方法，聚类方法，回归方法； ( 2 ) 聚合方法：例如：将销售数据按年或月来统计； ( 3 ) 一般化数据方法：例如：将年龄分为年轻，中年，年长。本文在属性上定义的 大、中、小简单概念就是根据这个方法演化而来的； ( 4 ) 归一化：将数据从很大的范围转换到一个小的范围内，如 o ，1 】区间； ( 5 ) 构造属性方法。 数据约减是将数据量减小而不影响分析结果( 相同或几乎相同) 的方法。也就是， 在约减后的数据集上挖掘应该更有效，而产生的结果相同。包括以下的方法： ( 1 ) 数据立方体综合：构造一个数据立方体； ( 2 ) 维数约减：不相关的，弱相关的，冗余的属性或维可以去掉； ( 3 ) 数据压缩：小波转换，p c a 方法等。 2 3 预处理算法实现 数据预处理有很多方法，如：数据清理，数据整合，数据转换，数据约减等。而这 些方法又有很多不同的方法。本文采用数据整合，数据转换，数据约减等方法，针对无 数据丢失的数据。针对有数据丢失的数据，采取忽略这些数据的方法，即不用它们参与 算法。 基于概念学习的模糊规则提取方法的研究 、甜扩= 喜 1 i l l _ x j 一- v v i , i l i i i 坝册一 ，1 z c ，甩 c 2 t ， m = 尝，c 。2 2 ， v = 二一 1szsc ， ” 。 _ l ：；。( 甜驴) 脚 厶z 步骤三：如果i l 矿6 一y 6 + 1 | i ，则算法停止并输出划分矩阵帅聚类中心既否则 大连理工大学硕士学位论文 究提供了良好的条件。而且，也是最重要的是它不仅在许多领域获得了非常成功的应用， 而且以f c m 算法为基础，人们提出的基于其它原型的模糊聚类算法，形成了一大批f c m 类型的算法。 2 3 2 数据的属性约减方法 属性约减是针对海量数据属性求描述前处理数据的一种常用办法，比较常用的有 l d a ，p c a ，m m c 等【2 3 1 。本文对于多属性样本采用了l d a 属性约减算法。下面先介绍 l d a 算法。 l d a ( l i n e a rd i s c r i m i n a n ta n a l y s i s ) 线性判别分析，寻找一些向量，在概念空间中 能够最好区分类的，而不是最能描述每一类的样本。l d a 目的是最大化类间距度量，最 小化类内距度量。因此可以利用l d a 方法，把高维的不可分的样本投影到低维的利于分 类的子空间来进行分类识别。给定一个训练集墨样本总数为，共分为c 类，每类中的 样本数为，扛1 ，2 ，c ，cn ，= n ，类内离散度矩阵为刎： = 万1 缶c 丢n ( 为_ 西( 而一i ) r ( 2 3 ) 类间离散度矩阵为： & = 专荟，( i 一- ) ( i 一_ ) 7 ( 2 4 ) 上面两式中x 为所有属性的均值向量，丐为第i 类属性的均值向量，而是第i 类属性 中的第，个样本。 由上文讨论的f i s h e r 线性判别法得到判别函数： ，( 形) = 髓w r s 两, w ( 2 5 ) 当s w 是非奇异阵时，可以得到一个正交矩阵，并且它能够使投影后样本类间散度分 布矩阵的行列式的值与样本类内散布矩阵的行列式的值之比达到最大，即： 小一，叫甲x 矧 ( 2 6 ) 其中 wii = 1 ，2 ，p ) 是式( 2 9 ) 的广义特征向量，对应于式( 2 9 ) 的p 个晟大的广 义特征值 五ii = 1 ，2 ，p ) ，即 一9 一 基于概念学习的模糊规则提取方法的研究 s b w f = 旯f s w f ( 2 7 ) 由于类间离散度矩阵& 的秩不大于c - 1 ，所以p c - 1 ，即最多有c - 1 个广义非零特征值。 咙，就是所求的最佳的投影变换矩阵。 根据最大特征值( 或前门个最大特征值) 所对应的特征向量，特征向量中的元素个 数即为属性个数，选取特征向量中的元素值大于某个阀值a ( a e ( 0 ，1 ) ) 的所有属性作为新 的训练样本的属性。 注：用l d a 选择属性用的是原始数据，且属性与简单概念不同。 p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 主成分分析算法是要寻找一个子空间【2 4 】，它的基 向量是原始空间中最大变化量方向。本文也采用过p c a 算法作属性约减，但是由于样本 的分类是已知的，它的效果就不j t n l d a 算法的效果好。令f 哟从原，维空间到，维特征子 空间的线性转换，产 l 时， ( m 瓦劢与布尔代数不代数同构，所以该逻辑系统是布尔逻辑系统的推广。称这个新的 逻辑系统为a f s 模糊逻辑系统。 由于a f s 模糊逻辑系统中的模糊集的隶属函数，逻辑算子”人，v ，都是用原始数据 通过统一的算法获得的，所以具有更好的客观性和统一性。因为a f s 结构与计算机的 数据库在结构上很相似，所以a f s 模糊逻辑系统非常便于计算机操作。同时可应用代 数和拓扑研究作为分子格的a f s 代数( 研究了其上的简单的拓扑分子结构) ，也可应用 组合数学研究作为一类组合对象的a f s 结构。 2 4 3 关于隶属函数的定义 定义2 4 ( 连续情况) 口7 1 设x 为一集合，x _ c r o p ：n = e 0 ，o o ) 。虎x 上在l e b e s g u e 测度肝可积函数并且0 f x p d u o o 。s ( s c _ 2 x ) 是b o r e l 集。对任意彳s ，称r a 为s 上的 由碍出的测度，令 州) ：粤 j r 脚 ( 2 1 2 ) ( 离散情况) 设x 为一集合，s 是x 上的c l r 代数。p ：n 矿= e o ，o o ) ，m o e 竹) o 。 对任意的a e s ，称聊为s 上的f h p 导出的测度，令 所= 豳弦 易验证对于任意的p ，这里给出的m 是x 上的测度。事实上，对于x 上的每个简单 概念f 都可由原始数据和相关信息导出一个x 上的一个正值函数膨j b 矿= e o ，o o ) 并由 基于概念学习的模糊规则提取方法的研究 时出的测度获得概念f 的隶属函数。 设f 是x 上的简单概念，膨轴r + = o ，o 。) ，如果店满足下列条件，则店称为简单 概念c = 的隶属密度函数： ( 1 ) 店( x ) = o 郇，x ) 仨尺白x 凰 ( 2 ) o ，力r 户腭o ) 店，x ，y 刨r ( o 定义2 5 t 2 7 】设x 为论域，m 是x 上的一些简单概念构成的一个集合，s 是x 上的仃 代数。对于任意的口m ，m 口是由口的隶属密度函数阮导出的s 上的测度。f 胆4 ，e e x m , 如果满足a i e s , vi e l ，则如下定义f 脾4 f 的范数： m ( ，e ，q 4 ) = s u p ( 兀( q ) ) o ，1 ( 2 1 4 ) “ 口e 4 对于在半认知空间( m 互x $ 可测的模糊概念，仨4 ，e e m , 定义其表示模糊概念，4 ，的 z a d e h 模糊集的隶属函数如下：任意x x 姆，4 ( x ) = m ( ( 硝4 ) ( x ) - - m ( z 剧鱼( x m ) o ，1 ) ( 2 1 5 ) 这个隶属函数的定义符合人的思维逻辑，已经应用到模糊分类、模糊聚类、模糊粗 糙集的应用等方面，见文献 2 9 3 1 。 大连理工大学硕士学位论文 3 基于蕴含算子模糊规则提取算法( r e n f 10 ) 及其应用研究 规则提取是归纳学习或者说是机器学习研究的一个重要方向。本章主要探讨基于模 糊蕴含算子n f i o 的模糊规则提取算法( r e n f i o ) ，n f i o 是根据欧氏距离和子集度定义 的一个新的模糊蕴含算子。首先通过一个例子，分析比较n f i o 算子与其它常用蕴含算 子如g o d e l ，l u k a s i e w i c z ，m a m d a n i ，s h a r p 等的有效性。同时介绍用此算法处理i r i s 数据 集，w i n e 数据集，w d b c 数据集和w b c d 数据集的实验结果，并与其它算子在这些数 据上的结果相比较，然后对实验结果都作了详细的分析和讨论。 3 1蕴含算子技术的提出与发展 基于属性比较两个物体的问题是一个目前比较热的话题，已经出现在很多领域，例 如：自动分类、计算机科学、经济学、统计学、分类学等。很多学者根据两个物体的相 似程度和相异程度来比较它们。当物体的属性是模糊值时，b o u c h o n m e u n i e r 等人定义 了一个一般的比较事物的两组框架：相似度和不相似度【3 2 】。相似度有三类：可满足性度 量、包含性度量、相似性度量；不相似度包含特殊的类：距离。所有这些度量都基于以 下的集合操作：集合的交、集合的并、集合的不同。人们认为集合的交和集合的并采用 z a d e l 的最小t 模和最大t c o 模。而集合的不同的定义大多基于蕴含算子。 g o d e l ，l u k 嬲i e w i c z ，m a m d a n i ，s h a r p 等人提出了多种模糊蕴含算子，见文献【3 3 4 2 。 本章根据一些经典的模糊蕴含算子及a f s 模糊逻辑，提出了一种新的模糊蕴含算子 公式。 3 2 模糊蕴含算子介绍 在研究模糊数据( 即用数值表示属性值的数据) 时，数据属性是首要分析的项目之 一。不同的属性或不同属性的组合可以将一类数据与其他数据区分开来。因此，对不同 属性之间的联系的研究显得尤为重要。例如，人的身高和体重之间就有一定的蕴含关系。 给定的两个向量之间的相似度可以用很多方法来测量。 模糊蕴含关系是模糊推理的大前提，是构造模糊控制器的核心环节之一，很多学者 给出了模糊蕴含算子不同的定义方法。这些模糊蕴含算子的定义一般都有各自的背景， 满足不同的要求，多数取自多值逻辑，通过集合运算来定义的。一般采用下面的定义： 定义：模糊蕴含算子俺是 o ，1 】上的一个二元函数，如果正【0 ，1 2 一【0 ，1 】满足条 件： ( 1 ) j a ，b o ，1 使以口，6 ) = 1 基于概念学习的模糊规则提取方法的研究 ( 2 ) j c ，d o ，1 】使苁c ，坊- 0 称厂为模糊蕴含算子。 一个模糊系统的结构包括许多i f t h e n 规则，每一条规则可以表示成【4 3 】： 伍x i s at h e ny i s b 彳和b 是在论域帅v 中用隶属度函数表示的模糊变量( 如“老 ， “小 ，“高 等) ，脚玢别是他们的值。一个模糊规则可用从集合砸0 集合啪模糊关系r 表示，如 下： r ：u xv 一 o ，1 ：( 甜，1 ，) 一，( 以( “) ，盹( v ) ) ，v ( u ，v ) uxv 心和是彳和b 的隶属度，j 是用弘模定义的蕴含算子。 当规则的前件有不止一个输入时，隶属度。( x ) 用下式计算： 心( x 。) = t ( g a 。( 五) ，砌( 以) ) ，x 。= ( 墨( r ) 9 o 9 以( f ) ) 丁代表产模算子。 3 2 1常用的模糊蕴含算子 设以 ) 为样本x 属于模糊描勘的隶属度。符号“ ”表示取最小，符号“v 表 示取最大。一般的蕴含算子的定义是删：称函数g ： o ，1 】2 一【0 ，l 】为一个模糊蕴含算子， 若函数g 满足g ( o ，0 ) = g ( o ，1 ) = 甙l ，1 ) = 1 ，且g ( 1 ，0 ) = 0 。 迄今为止，蕴含算子的数目还在增加，但是却没有一个蕴含算子被证明对模糊推理 过程都有效。下面是一些常用的模糊蕴含算子3 3 - 4 2