（计算机软件与理论专业论文）基于rough集机器学习的研究与实现.pdf

基于r o u g h 集机器学习的研究与实现 计算机软件与理论专业 硕士生：王蕾晴 指导教师：汤庸教授 摘要 机器学习是人工智能领域中前沿课题，其基本特征之一就是能够有效处理不 确定数据信息。一类重要的机器学习类型就是导师指导下的学习过程。本文借鉴 r o u g l l 集基本思想，研究基于不确定数据前提下的有指导机器学习过程中的基本 技术和方法。首先，建立了基于决策系统的有指导机器学习模型，其中将决策属 性理解为导师属性，将条件属性理解为学习者属性。其次，在模型所建立的框架 内，提出学习系统质量的基本概念，以此为基础对各种学习方法进行统一分析与 评估；第三，研究了学习过程中可能出现的各种情形，探讨导师知识不完备、学 习者知识缺失以及两者皆有缺失三种情况下的机器学习过程中基本情况和问题， 提出了不同的处理( 完备化) 方案，并研究处理过程前后学习质量的变化，而这 实际上是完成了一种动态学习；最后，设计了一个模拟实验的原型系统，采用关 系类的二进制数表示方式，实现了本文的研究工作。实验结果表明了本文工作的 合理性和有效性。 关键字：基于决策表的有指导学习系统，系统学习质量，不完备学习，动态 学习过程，模拟实验原型系统 t h er e s e a r c ha n d i m p l e m e n t a t i o no nm a c h i n el e a r n i n gt e c h n i q u e b a s e do i lr o u g hs e tm e t h o d s c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：w a n gl e i q i n g s u p e r v i s o r ：p r o f e s s o rt a n gy o n g a b s t r a c t m a c h i n el e a r n i n gi so n eo ft h ei m p o r t a n tr e s e a r c h e si nm f i e l d t h ea b i l i t yo f p r o c e s s i n gu n c e r t a i nd a t ai so n eo ft h ee s s e n t i a lf e a t u r e so fm a c h i n el e a r n i n gs t l l d y b a s e do nr o u g hs e tt h e o r y , i nt h i sa r t i c l e , w ed i s c u s st h et e c h n i q u e sa n dm e t h o d si n s u p e r v i s e dl e a r n i n gw h i c hp r o c e s s i n gu n c e r t a i nd a t a i nt h eb e g i n n i n g , w eb u i l d 叩a m o d e lo fs u p e r v i s e dl e a r n i n gb a s e do nd e c i s i o ns y s t e m t h ed e c i s i o na t t r i b u t e sa r e t r e a t e da st h et e a c h e r sa t t r i b u t e s ，a n dc o n d i t i o na t t r i b u t e sa st h es t u d e n t s o n e s s e c o n d l y , w eb r i n gt h ec o n c e p to fl e a r n i n gq u a l i t yf o r w a r di n s i d et h ef r a m e w o r k o f o u rm o d e l a l lt h ea n a l y s i sa n da s s e s s m e n t sf o ra l lt h el e a r n i n gm e t h o da r el e a n i n go n t h i s f o l l o w i n gt h a t ，t h ec h a n g eo ft h el e a r n i n gq u a l i t ya n dp r o c e s s i n gi nt h es i t u a t i o n o ft h et e a c h e r sk n o w l e d g ei si n c o m p l e t eo rt h es t u d e n t s k n o w l e d g ei si n c o m p l e t eo r b o t hi n c o m p l e t ei sm a i n l yd i s c u s s e d t h ev a r i o u sm e t h o d st oc o m p l e t et h eu n k n o w n k n o w l e d g e a r eb r o u g h tu p hf a c tt h i sp r o c e s si sak i n do fd y n a m i cl e a r n i n g , a tl a s t , w ed e s i g nap r o t o t y p es y s t e m ，u s i n gb i n a r yn u m e r i c a la l g o r i t h m ，r e a l i z et h et h e o r yw e d i s c u s s e di nt h i sa r t i c l e t h ee x p e r i m e n tr e s u l t si n d i c a t et h er a t i o n a l i t ya n de f f i c i e n c y o f o u r w o r k k e y w o r d ：s u p e r v i s e dl e a r n i n gs y s t e mb a s e do nd e c i s i o ns y s t e m ，l e a r n i n g q u a l i t y , i n c o m p l e t el e a r n i n g , p r o c e s s o fd y n a m i cl e a r h i n g , p r o t o t y p es y s t e m 1 1 1 1 1 问题研究的背景 第1 章前言 粗集( r o u g hs e t s ) 理论是波兰数学家p a w l a k 于1 9 8 2 年提出的【1 1 。其主要 特点是直接由数据构成决策表进行推理，不需要任何附加或额外的条件。其他的 方法，像概率论常常需要前提假设，模糊集理论则需要隶属函数假设f 2 l 。目前，粗 集理论已经广泛应用于机器学习、决策支持、知识发现、专家系统、模式识别等 领域。r o u g h 集理论将知识定义为不可区分关系的一个簇集，不可区分关系是 r o u g h 集理论最基本的概念，在此基础上引入了成员关系，上近似和下近似等概 念刻划不精确性与模糊性r o u g h 集理论认为知识即是将对象进行分类的能力 基于r o u g h 集理论的知识获取，主要是通过对原始决策表的约简，在保持决策表 决策属性和条件属性之间的依赖关系不发生变化的前提下对决策表进行约简。 粗集理论是基于信息或数据的不一致性这一客观世界常常出现的现象，给 出所需概念的近似描述( 上近似和下近似) 。对应于这些近似描述，给出相应的 必然和可能的决策规则。 机器学习是人工智能的最重要的分支之一，被公认是人工智能发展的重要 领域之一。机器学习的研究在人工智能的发现中起着举足轻重的作用。 机器学习是继专家系统之后人工智能应用的又一重要研究领域，也是人工 智能和神经计算的核心研究课题之一。从特殊的训练样例中归纳出一般函数是机 器学习的中心问题。机器学习的种类繁多，包括机械学习、基于解释的学习、基 于事例的学习、基于概念的学习、类比学习和基于训练神经网络的学习等。从有 无导师的角度可粗略分为三大类：有导师的学习( s u p e r v i s e dl e a r n i n g ) 、无导师的 学习( u n s u p e r v i s e dl e a r n i n g ) 和加强学习( r e i n f o r c e m e n tl c a r n i n g ) 。对机器学习的讨 论和机器学习研究的进展，必将促使人工智能和整个科学技术的进一步发展。 基于r o u g h 集机器学习的研究与实现 1 2 问题的提出 学习就是从未知到已知的过程，机器学习关注的是如何根据经验自动提高自 身处理性熊的计算机程序，也被定义为系统自我改进的过程，学习算法已被证明 在很多应用领域具有实用价值【3 , 4 l ，特别是：1 在某些人们还不具备足够的知识来 开发高效算法的领域，比如从图像库中识别出入脸。2 需要从大量数据中挖掘其 中有价值的可能规律的领域，例如从财务数据库中找出信用贷款的普遍规则。3 计算机程序必须动态适应环境的领域，比如适应个人阅读兴趣的变化【。 目前应用较多的机器学习算法有概念学习、决策树、人工神经元网络、贝叶 斯、遗传算法、基于实例学习、规则学习、基于解释学习、增强学习等。但作为 种理论基础，当前还没有一种是被公认可被接受。突出的数据处理能力使得 r o u g h 集方法可应用到机器学习中，作为研究其中某些问题的理论基础。尽管国 内外学者在机器学习和r o u g h 集理论方面的研究已经非常之多，但对于不完备 学习训练系统对学习质量和过程的影响以及动态学习如何影响学习质量进行研 究的为数不多。 然而信息不完备普遍存在的现象，这时，根据数据所提供的信息，我们无法 确切地将数据集截然划分为不同的类别，这样就不能用传统的示例学习算法进行 机器学习【5 l a 因此，本文将运用r o u g h 集方法，借鉴有导师的基于实例学习思想，通过 比较有导师学习训练系统完备前后学习质量和学习过程的变化，探讨导师知识不 完备、学习者知识缺失以及两者属性皆有缺失情况下的机器学习。 1 3 国内外研究及现状 1 3 1r o u g h 集理论研究及现状 波兰数学家z p a w l a k 借鉴g f r e g e 的边界线区域思想，于1 9 8 2 年提出 r o u g h 集概念。由于最初关于r o u g h 集理论的研究大部分是用波兰语发表，因此 2 第1 章前言 当时仅局限在东欧一些国家的学者研究，还没有引起国际计算机学界和数学界的 重视，直到2 0 世纪8 0 年代末才逐渐引起各国学者的关注。经过许多计算机科学 家和数学家的不懈研究，r o u g h 集已经从理论上日趋完善，形成了理论体系。由 于r o u g h 集方法在机器学习与专家系统 6 1 、数据挖掘 7 , 8 1 、决策支持与分析【8 ，9 ，堋、 人工智能【1 e l 、和知识发现【1 3 】等方面的广泛应用，研究逐渐趋热。 z p a w l a k 在1 9 9 1 年发表的专著【1 3 1 和1 9 9 2 年r s l o w i n s k i 主编的关于r o u g h 集应用及其与相关方法比较研究的论文集【1 4 蚓的出版，标志着r o u g h 集理论及其 应用的研究进入活跃时期。 1 9 9 2 年，在波兰召开了第一届关于r o u g h 集理论的国际学术会议k i e k r z , 会 议主要讨论了集合近似定义的基本思想及其应用，而r o u g h 集环境下机器学习 的基础研究是这次会议的四个重要专题之一。1 9 9 3 年第二届国际粗糙集与知识 发现( r s d 9 3 ) 研讨会在加拿大b a n f f 召开，其主题是r o u g h 集、f u z z y 集与知 识发现。与会学者提出了基于扩展的r o u g h 集理论的知识发现方法与系统。1 9 9 5 年，a c mc o m u n i c a t i o n 将r o u g h 集理论列为新浮现的计算机科学的研究课题。 1 9 9 8 年，国际信息科学杂志( i n f o r m a t i o ns c i e n e e s ) 出了一期r o u g h 集理论的研究 专辑。1 9 9 9 年9 - 1 1 日“第7 届r o u g h 集、f u z z y 集、数据挖掘和粒度软计算 的国际学术研讨会”( t h es e v e n t hi n t e r n a t i o n a lw o r k s h o po nr o u g hs e t s ， f u z z y s e t s ，d a t am i n i n ga n d g r a n u l a r - s o f tc o m p u t i n g ( r s f d g r c 9 9 ) ) 在日本召 开。会议阐述了当前r o u g h 集，f u z z y 集的研究现状和发展趋势，指出了r o u g h 集理论将着重在软计算、数据库、a i 和近似推理等理论和应用方面发展的方向。 目前，许多关于人工智能、模糊理论、信息管理与知识发现等国际学术会议都将 r o u g h 集理论列为重要的议题之一吲。 1 3 2 机器学习研究及现状 人工智能自1 9 5 6 年诞生之后取得了重大进展，先后经历了博弈时期、自然 语言理解、知识工程等阶段，目前的研究热点是机器学习【1 7 ，埘。 自从1 9 8 0 年在卡内基梅隆大学召开第一届机器学术研讨会以来，机器学习 的研究工作很快发展成为中心课题之一。1 9 8 9 年，c a r b o n e l l 指出机器学习的四个 研究方向：基于符号的归纳机器学习、连接机器学习、分析机器学习与遗传机器 基于r o u g h 集机器学习的研究与实现 学习。1 9 9 7 年，d i e t t c r i c h 【6 】提出了另外四个新的研究方向：增强机器学习 ( r e i n f o r c e m e n tl e a m i r 【曲、海量数据的有导师师学习算法( m e t h o d sf o rs c a l i n gu p s u p e r v i s e dl e a r n i n ga l g o r i t h m ) 、分类器的集成( e n s e m b l e so fc l a s s i f i e r s ) 与学习复 杂统计模型( l e a r n i n gc o m p l e xs t o c h a s t i cm o d e l s ) 。在理论上，可以将其进一步归纳 为三类不同的学习理论：海量数据的符号机器学习理论、统计机器学习理论与基 于适应性的机器学习理论【堋。而2 0 世纪9 0 年代初期出现的支持向量机( s v m ) ， 是在统计学习理论的基础上发展起来的新代学习算法。随着在理论方面的不断 深入，在实践中的不断拓广，该算法在文本分类、手写识别、图像分类、生物信 息学等领域中获得了较好的应用，目前已成为机器学习和数据挖掘领域的标准工 具嗍。 当今科技界关于机器学习的核心科研课题研究是如何让计算机获取知识， 机器学习领域的研究工作主要围绕以下三个方面进行：( 1 ) 面向任务的研究：研 究和分析改进一组预定任务的执行性能的学习系统。( 2 ) 认知模型：研究人类 学习过程并进行计算机模拟。( 3 ) 理论分析：从理论上探索各种可能的学习方法 和独立于应用领域的算法。 1 3 3 基于r o u g h 集理论的机器学习的研究现状 粗集理论的方法，特别是决策表规则提取和属性约简都可以应用于机器学 习的研究当中【1 2 ”】。利用r o u g h 集的理论对机器学习归结为知识表达和分类问题 例。把机器学习中的学习和推理过程的处理归结为粗集理论中知识表达、提取有 用特征、化筒表达、推理决策规则的过程。 目前的研究主要几种在：利用粗集理论改善规则提取算法【2 1 ，笠，洲。这一 部分的研究推动了粗集理论在机器学习中的应用，丰富了机器学习可利用的规则 提取方法，提高学习效率。例外的研究方向集中在动态学习的研究1 。但是对于 不完备学习系统的研究并不多见，对于这部分机器学习的研究理论尚不能够系统 f 1 o 硐。 4 第1 章前言 1 4 本文内容安排 本文后面章节的安排大致如下： 第二章，介绍机器学习、r o u g h 集理论的相关基础知识，以及算法实现上拟 引入基于g r a n u l e ( 粒度) 的二进制数方法。 第三章，讨论基于r o u g h 集方法的机器学习，包括导师知识不完备对学习 质量和过程的影响、学习者自身知识缺失对学习质量和过程的影响以及两者属性 皆有缺失对学习质量和学习过程的影响。 第四章，本章以第三章的讨论为基础，进行二进制数算法设计及实验验证。 第五章，对本论文内容进行总结和进一步的展望。 5 基于r o u g h 集机器学习的研究与实现 第2 章相关基础知识和技术方法 由于本文运用r o u g h 集方法研究有导师学习训练系统的学习质量和过程，所 以有必要在此对机器学习中有导师的实例学习以及r o u g h 集理论基础知识进行 相关的介绍。 2 1 机器学习基础知识 2 1 1 什么是机器学习 学习是人类获取智慧的根本途径，学习和解决问题是人类最重要的两个智能 行为。机器学习是让计算机模拟和实现人类的学习的过程，目的是获取知识。机 器学习也是让计算机获取智能的最主要的手段。机器学习具有快速、可复制、自 主性差、机械、学习方法单一等特点。在对一些数理化的知识的学习上，机器也 比人的速度要快得多，由于计算机程序易于复制，计算机的学习不会终止，可以 将其所具有的知识一直保留。但是，机器学习也存在目前来说还不能克服的缺陷， 即计算机只能根据有限的学习方法进行机械学习，不具有人类学习所特有的“灵 感思维”f 1 2 8 i 。 传统意义下的机器学习可描述为：令w 是一个问题空间，( x ，y ) w ，称 为样本或对象，其中，x 是一个n 维矢量，y 是一个类别域中的一个值，这称为 有导师的机器学习( s u p e r v i s el e a r n i n g ) 。如果样本不包含y ，则称为无导师的学 习( u n s u p e r v i s el e a r n i n g ) 。 机器学习是用计算机模拟人类学习的- - f l 科学，目前比较成熟的算法有归纳 学习算法、神经网络、遗传算法等，支持向量机是现在机器学习研究中较热门的 学习算法。 2 1 2 分类学习 分类学习是机器学习众多的分支中最主要的分支，主要研究如何从大量数 据中抽取规则( 知识) ，主要研究存在先验分类的机器学习。分类是指分析数据 6 第2 章相关基础知识和技术方法 库的一组对象，找出其共同属性。然后根据分类模型，把它们划分为不同的类别。 分类数据首先根据训练数据建立分类模型，然后根据这些分类描述分类数据库中 的测试数据或产生更恰当的描述。分类学习主要指有导师的学习。例如，股市升 降分析中，我们选定某支感兴趣的股票，想通过已往的历史数据中发现，哪些股 票对此股的升降有影响，有导师指的是我们感兴趣的那支股票以往的升降情况已 知。 2 1 3 聚类学习 聚类是指数据库中的数据可以划分为一系列有意义的子集，即类。在同一 类别中，个体之间的距离较小，而不同类别上的个体之间的距离偏大。聚类分析 通常称为“无监督学习”，因为聚类的学习不依赖于先验的分类。 2 。2r o u g h 集基本概念 2 2 1 知识分类 知识是对信息经过加工处理而形成，本文所指知识即是将对象进行分类的能 力f 1 2 l 。假定集合u 表示所砑究的对象全体，其中的对象具有必要的信息或知识， 则称u 为论域。u 上的知识可理解为在等价关系集r 下对数据集u 的分类。如 果论域u 中某两个对象具有相同的信息，则它们属于同一概念族，存在不分明 关系，是不可区分的【3 , 1 8 , 2 9 。 定义2 - 1 论域u 上的任何子集x ( x u ) 称为u 上的一个概念或范畴，约 定d 也是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。u 上 的划分族集( u ，r ) 构成关于u 的知识库( k n o w l e d g eb a s e ) 。 定义2 - 2 设u 为论域，r 为u 上的等价关系族，p c - r 且玛叼，则p 中所有 等价关系的交集n p 称为p 上的不可区分关系，记作d ( p ) ，即 i n d ( p ) = ( x ，y ) l ( x ，y ) u 2 ，v b g p ( b ( x ) = b ( y ) ) 由不可区分关系的定义可知，不可区分关系也是等价关系，且有： 矾d p ) = n 咧 b ) ) 7 基于r o u g h 集机器学习的研究与实现 定义2 - 3 设u 为论域，r 为u 上的等价关系族，p r 且p 妒，则不可区分 关系i n d ( p ) 的所有等价类集合u k r d ( p ) 称为u 的p 基本知识，相应等价类称为 知识p 的基本概念或基本范畴。 2 2 2r o u g h 集基本概念 r o u g h 集理论的关键概念是论域u 的不可区分关系。论域u 上的对象集合x 可由不可区分关系t n d ( p 1 确定的知识来划分，这时有三种可能性： ( 1 ) c 矾d ( p ) ，且c _ c x ，即x 定包含概念c ，称x 是c 可定义的。 ( 2 ) c i n d ( p ) ，c c x 且c n x 9 ，即x 包含概念c 的一部分，称x 是c 部分可定义的。 ( 3 ) c i n d ( p 1 ，且c n x = 刀；即x 一定不包含概念c ，称x 是c 不可定 义。 定义2 - 4 给定知识库k = ( u ，r ) ，x _ c u ，定义 r _ ( 均= x l x ui e i x r c _ x 尺+ ( z ) = x l x u 且 x h n x | 0 砜僻) = r 鹪一r 一僻) p o $ r 皤) = r p n e g ( 石) = u r 一( x ) 分别称嘲为x 的r 下近似集，r 一( z ) 为x 的r 上近似集，魄g ) 为x 的r 边界域，p o s a x )x 的r 正域，n e g 。( x ) 为x 的r 负域。其中f x 】r 表示包含 元素x u 的r 等价类。 r 固或p n ( z ) 是根据知识r 判断必定属于x 的元素组成的集合：r c r ) 是根据知识r 判断可能属于x 的元素组成的集合；6 皤) 是那些根据知识r 不 能明确判断是否属于x 的元素组成的集合；n e g 。( 工) 是根据知识r 判断一定不 属于x 的元素组成的集合。各部分的关系如图2 1 所示。 8 第2 章相关基础知识和技术方法 ， 0 o弋 、誓矗耋 弋 骘j x 、 、 - j 者对导师非 知识区完全不可识别；k = l ，表示学 - - - j 者对导师非知识区完全可识别；0 i s 2 ，则知识区t + 边界域f 瓴) f 减少； 若i s l i ( i s 2 i ，则i 锄，( ) i 增加；若l s i l = l s 2 i ，则l 帆( ) i 不变。 所以知识区，的正域p n g ) 增加，边界域i 厶魄叮) 变化情况 视l 眠( ) i 而定。从而学习质量q 增加，影响学习过程。 学习者对导师的非知识区的识别率k 幻。即：非知识区t o 的s 下近似瓴) 彩 时。对于所有的非知识区t o 都用+ 值替代。知识区r 的正域p 。仃) 都将 增加。从而使得学习质量q 增加，影响学习过程。 结论1 单纯的用+ 值替代导师非知识区属性方法来完备化导师属性后，学 习系统的学习质量是大于和等于完备化前的。 2 单纯用一值来替代0 值。 单纯的用一值来替代0 值得方法与单纯的用+ 值替代方法一致，其实只需将上 述分析过程中的+ 号与一号调换位置即可得到结论。因此得到的结论也同结论1 类 似。 结论2 单纯的用值替代导师非知识区属性方法来完备化导师属性后，学 习系统的学习质量是大于和等于完备化前的。 ，6 第3 章基于r o u g h 集理论的机器学习 3 用+ 和一值来替代0 值。 学习者对导师的非知识区的识别率k - - o 。即：非知识区t o 的s 下近似( 瓦) = g 时。 ( 1 ) 如果矗c _ b n ，伍) 眠旺) ，这时无论用+ 或一值代替属性t 中0 值进行 完备化，知识区丁的边界域锄。口) 不变，i t 域p o s s ( t ) 不变，从而 学习质量q 不变，也不影响学习过程。 ( 2 ) 如果瓦_ b n s 亿) ，且砌。仉) - 钿s c 【) 。用+ 值代替非知识区t 1 中。 值，用一值代替非知识区1 2 中o 值，t 1 u t 2 = 1 d ，t 1 n t 2 = 乃，t 1 、 t 2 非空。完备化后，如果互中元素t e p o s s ( l ) ，则学习质量q 增加， 影响学习过程。只是知识区t 边界域6 ( ) 减少的例子为p o s s ( ) 中 增加的例子，n 边界域帆( r ) 增加。由于帆( ) 增加的例子是 b n , ) 中例子，所以最终边界域砌，仃) 减少。否则，学习质量q 不 变，也不影响学习过程。 ( 3 ) 如果矗6 一( ) r b n , 以) 一6 ( ) 。用+ 值代替非知识区t l 中0 值， 用一值代替非知识区1 2 中0 值，t 1 t _ f r 2 = t o ，t 1 n t 2 = 彩，t 1 、t 2 非空。得到的结论同上。 ( 4 ) 如果瓦c b n 。伍) 且写旺锄。伍) ，帆伍) n 帆以) - d 。不妨设t l 、 t 2 和t 3 是t 0 的三个划分，互c _ b n 。( l ) 五c 钿。但) ，瓦帆旺) ， 五正6 ( l ) ，互c 砌。( t ) 且乃c b n 。( ) 如果用+ 值代替非知识区 t 1 中0 值，用一值代替非知识区t 2 中0 值，用+ 或一值代替非知识区 t 3 中0 值。则知识区t + 和t 一正域舯( 瓦) 、p o s s 伍) 增加，边界域 帆亿) 中例子个数变化情况同第i 或i i 类，与学习者知识分类情况 有关。此时学习质量q 增加，影响学习过程。如果用一值代替非知识 区t l 中o 值，用+ 值代替非知识区t 2 中0 值，用+ 或一值代替非知识 1 7 基于r o u g h 集机器学习的研究与实现 区t 3 中0 值，则知识区t + 和t 一正域p d q ) 、p 。) 都不变，边 界域6 伍) 和拥，( ) 都增加，所以此时知识区r i e j 或p o s s ( t + ) 不 变，边界域6 n s 口+ ) 增加，从而学习质量q 不变，但影响学习过程。 学习者对导师的非知识区的识别率k o 。即：非知识区t o 的s 下近似瓴) ，g 时。 ( 1 ) 如果帆瓴) ；g ，有： ( i ) 若l s 一儡) i _ 1 ，用+ ( 或一) 值代替属性t 中0 值，p d 伍) ( 或 p o s s ( ) ) 增加，s 一亿) ( 或s 一( ) ) 增加相同的元素，所以知识区 t + ( 或t - ) 边界域锄，( t ) ( 或锄。旺) ) 不变，从而知识区丁的正域 p o s s ( 7 ) 增加，边界域6 ( ) 不变。所以学习质量q 增加，影响学习 过程。 ( i i ) 若i s 一( 瓦) i 1 ，用+ 、一值分别代替属性t 中0 值，知识区t + 和t - 的正域p 8 ( 乏) 、p o s s ( ) 不变，边界域矗伍) 和6 _ b 诬) 增加， 所以知识区r 的正域p n 仃) 不变，边界域锄，仃+ ) 增加。学习质量q 不变，但影响学习过程。 ( 2 ) 如果拥。瓴) ，g 。不妨设t 1 、t 2 、t 3 和t 4 是t o 的四个划分， 五锄s ) ，五旺魄促) ，五c _ b n 。伍) ，瓦岱拥，佤) ，乃c 帆伍) 且互c 帆( t ) ，t 4 2 ( 瓦) 。有： ( i ) 当t 1 、t 2 非空时： 第1 种完备化方式：用+ 值代替t 1 中属性t 的所有0 值，一 值代替1 2 中属性t 的所有0 值，+ 值或一值代替t 3 、t 4 中属性 t 的0 值。此时，知识区t _ 和t + 的正域p 鸭( r ) 、p o s s ( l ) 都 第3 章基于r o u l g h 集理论的机器学习 增加，边界域魄旺) 、b n 。仉) 都减少。所以知识区丁的正域 p o s s 口) 增加，边界域6 _ b 仃+ ) 减少- 从而学习质量q 增加，影 响学习过程。 第2 种完备化方式：用一值代替t 1 中属性t 的所有0 值，+ 值代替1 2 中属性t 的所有0 值，+ 值或一值代替1 3 中属性t 的 0 值。此时，知识区t - 和t 斗的边界域锄。( ) 、6 ( t ) 都增加， 但由于熟，缳) 增加的元素是拥。( 乏) 中元素，熟s e ) 增加的元素 是帆以) 中元素，所以知识区r 的边界域帆口) 不变。t _ 和 t + 的正域胂( ) 、p o s s ) 变化情况根据t 4 中属性t 的0 值 由+ 值还是一值代替而定，若由+ 值代替，则t + 的正域p o s s 伍) 增 加，t - , - f 域p o s s ( ) 不变。若由一值代替，则l 正域p d 旺) 增 加，t + 的正域眇。 ) 不变。所以知识区z 的正域增加，从而 学习质量q 增加，影响学习过程。 第3 种完备化方式：t 1 中属性t 的0 值有的用+ 值代替，有 的用一值代替，t 2 中属性t 的0 值也是有的用+ 值代替，有的用 一值代替。此时同情况第2 种完备化方式，学习质量q 增加，影 响学习过程。 ( i i )当t 1 = 刀，t 2 非空时。t 2 的属性t 中0 值有的用+ 值代替， 有的用一值代替，则边界域6 ( ) 不变，帆伍) 增加。由于6 ( l ) 增加的元素是锄。( t ) 中元素，所以知识区r 的边界域b b f ) 也不 变。t - 和t + 的正域p s 缳) 、p o s s 位) 变化情况根据t 4 中属性t 的0 值由+ 值还是一值代替而定，若c a + 值代替，则t + 的正域p o s s 伍) 增加，l 正域p n 旺) 不变。若由一值代替，则t - e 域p o s s ( ) 增 基于r o u g h 集机器学习的研究与实现 加，t + 的正域彤( ) 不变。所以知识区丁j e 域p o s s ( t ) 增加， 从而学习质量q 增加，影响学习过程。 ( i i ) 当t 1 非空，t 2 = o 时，情况同上。学习质量q 增加，影响学习 过程。 ( 4 ) 分析完备化后出现冗余规则对学习质量和学习过程的影响。 s 一( t o ) = 乃时，完备化后，冗余样例只可能出现在边界域6 口) 中。此时， 完备化后，p o s s ( 7 1 可能增加，也可能不变。出现冗余样例后，对其进行删除后， 学习质量q - k 景夯列中，p 0 5 s 仃) 增加或者不变，u 减少。学习质量q 提高或 者不变，学习过程显然发生变化。 最瓴) 一a 时，完备化后，s ( 瓦) 中的样例转化为正域p o s ，口) 中的样例， 这时p d 仃+ ) 增加，冗余的样例不可能出现在p o s s ( t ) 中。可能出现在虮仃) 中。对冗余样例进行删除后，p o s 5 ( 7 ) 增加，u 减少。学习质量q 提高或者不变， 学习过程显然发生变化。 结论3 用+ 和一值分别代替导师非知识区的一部分属性，对导师属性进行完 备化后学习系统的学习质量是大于和等于完备化前的。 根据以上分析所得结论1 ，2 ，3 可知，知识系统完备化后的学习质量大于 或等于原系统学习质量得到如下命题： 定理3 - 3 存在导师非知识区的系统学习质量小于或等于完备化后的系统学 习质量。 3 2 3 对于导师完备化理论的补充 上一节中主要讨论了导师的知识区为两种取值时不同的完备化对学习质量 第3 章基于r o u g h 集理论的机器学习 和学习过程的影响。但是对于导师分类大于2 时，这样的分析显然不能满足要求。 案。 因此在此基础上，也可以对导师知识有缺失的完备化提出其他的完备化方 ( 1 ) 均值补偿法。对于导师的属性，我们可以选择在样例中出现频率最高的 导师属性进行补偿。 ( 2 ) 可以参考3 3 2 介绍的根据r o u g h 集理论中不可分辨关系对包含不完整 信息的知识表达系统进行补齐。 3 3 学习者自身知识不完备对学习质量和学习过程的影响 3 3 1 对于学习者属性完备化对学习系统的影响分析 上一节讨论了导师知识不完备对于学习质量和学习过程的影响。 在机器学习中，当学习者自身知识不完备时，即学习者属性缺失，不能对 相应的实例特征进行识别时，这种情况对学习者的学习能力会产生怎样的影响? 学习者是否能学习导师的知识? 定义3 - 8 训练系统学习者知识完备化指将学习者确定知识区的可能取值 赋给学习者非知识区s 。 在表3 2 学习训练系统中，学习者确定知识区的值为0 、1 或2 ，非知识区 驴的值用表示，则用0 、1 或2 值代替值的过程称为不完备学习训练系统学习 者知识完备化。 定理3 - 4 在完备化后不产生冗余样例的情况下，存在学习者非知识区的系 统学习质量小于完备化后的系统学习质量。 证明：设导师能分类的属性t 值用+ 和一表示，对应知识区表示为t + 和t 一， 则导师知识区r - t u t _ 。 对学习训练系统进行完备化，此时s = a ，所以t 的正域 2 l 基于r o u g h 集机器学习的研究与实现 p o s s 仃) = 【p o s s q ) up o s s 伍) 卜 【p o s s 以) up 呱幔) 】n s + = p o s s 伍) u p o s 。( t ) 。 先证明完备化后学习系统不可能产生与学习者确定知识区决策规则矛盾的 规则。用反证法。假设完备化前学习者确定知识区产生决策规则：a x b y t + ，x 、 y 为确定值。完备化后产生与之矛盾的规则：a x b y - - , t 一，此处x 、y 在完备化前 的取值情况只能为：x = ，y = y ；或x = x ，y = ，即形成规则a 幸b y t - ，或a x b t - 。 但完备化前，a b y 、a x b 和a x b y 对于学习者知识而言是同一概念，即对于学习 者属性具有相同的描述，但又对导师属性产生不同的描述t + 和t l ，这与决策规 则的产生原理是矛盾的。所以完备化后学习系统不可能产生与学习者确定知识区 决策规则矛盾的规则。 因此完备化后学习训练系统只存在以下情形： 幻产生与学习者确定知识区决策规则相符的规则。 b 1 产生新的规则。 以上两种情形都会导致p o s 。 ) 或p o s ，旺) 增加，即知识区t 的正域 p o s s 口) 增加，所以学习质量增加，影响学习过程。 由于不可能产生与学习者确定知识区决策规则矛盾的规则，所以知识区t 的正域p 。仃) 不会减少，即学习质量不会减少。 综上所述，知识系统完备化后的学习质量大于原系统学习质量，原命题得 证。 定理3 5 完备化后学习系统正域中不出现冗余样例，完备化后的学习质量 大于完备化前。 如果完备化的过程中产生了冗余的样例? 会对学习系统的学习质量和过程 造成怎样的影响? ( 1 ) 如果冗余的样例出现在边界域中，无论p o s s 口) 域不变还是提高，u 减小，都将提高学习质量q a 因为g _ 竺帮a ( 2 ) 冗余的样例如果出现在正域中，会使p o s s 口) 和u 同时减小。很难判 第3 章基于r o u l g h 集理论的机器学习 断，学习质量是否增加或者降低。 3 3 2 学习者空缺属性完备化策略。 本节内容基于参考文献1 1 2 】中对于空缺值的处理方法的分类。 在学生属性有缺失的系统中，完备化的策略有很多种。途径主要有： ( 1 ) 将空缺值的属性值作为一种特殊的属性值来处理。 ( 2 ) 利用统计学原理计算空缺值在属性中的分布，按照某种方法对空缺的属 性值进行估计值补充。 均值补偿法。对于非数值的属性，用该属性在其他所有实例中的取值次 数最多的属性值来补充；对于数值的属性，就如该方法的名字，取所有 实例中的取值的平均值来替代。 条件组合补偿法。就是根据包含不完备信息的知识表达系统中，空缺的 属性值由该属性在其决策相同的实例中的所有取值，分别来补充空缺的 属性值。条件组合补偿法需要多种补偿方案的尝试。 ( 3 ) 根据r o u g h 集理论中不可分辨关系对包含不完整信息的知识表达系统进 行补齐。 简介扩充可辨别矩阵的概念。 学习系统s t u ，a ，v ，f ，a 一瓴l i 一1 ，m ) 是属性集合，a ；( x j ) 使样本 毛在在属性a t 上的取值。扩充可辨别矩阵定义为： m o ，) 一瓴i 唯4 吼“) 一q o j ) a a k “) 一， a k ) 一+ ) 其中m ( i ，) 表示扩充可辨别矩阵中的第i 行第j 列的元素，其中，i , j = l ，n ；表示空 缺属性，a a 。“) 表示对于所有的吼 ) 。 定义几个集合。对象而的空缺属性集为m a s l ，无差别集 毽；系统s 的空缺对象集合s m a s t 一( 吒f 吒“) 一，后一1 ，m ) 毽一( j l m ( i ，) - o , i j ，j 一1 ，露) 基于r o u g h 集机器学习的研究与实现 s + = ( i l m a s i ，l o ，f - 1 , ，弗) 计算m r 的递推算法。s o 为初始系统