（计算机应用技术专业论文）基于粒计算的知识获取方法研究.pdf

重庆邮电人学硕十论文摘要 摘要 粒计算( g r a n u l a r c o m p u t i n g ，简称g r c ) 是一种新的智能信息处理理 论。对于粒计算的研究，很大程度上是因为它模拟了人脑认识和解决问题 的过程。它主张从实际出发，从多粒度层上分析问题，寻求一种更经济和 消耗更低的解决办法。近年来，粒计算理论发展迅速，现已经被广泛地应 用于机器学习、数据挖掘等领域，并被证明是有效的求解问题的方法。 机器学习( 知识获取) 的目标是将大量数据中所隐含的知识发现出来， 也就是将知识从人们难于理解、操作和使用的数掘表达形式转化为便于人 们理解、操作和使用的符号表达形式。在信息不断膨胀的今天，人们需要 从大量数据中获取有效的知识，这使得机器学习成为了众多学者研究的热 点。然而在处理现实问题时，很难得到完全确定的数据，因此对不确定性 条件下的知识获取方法的研究，是一项重要研究课题。而且，由于现代信 息系统同趋复杂，精确求解常常很难实现，从问题的简化上考虑需要寻找 一种更加经济实效的方法。这些都是我们用粒计算进行知识获取过程中的 新挑战。 目前，粒计算理论中针对上述问题还缺乏有效的处理方法。为此，本 文提出了两种基于粒计算的知识获取算法：第一种为用户驱动粒计算学习 算法，它通过用户输入的先验知识作为阈值来驱动粒网络的构造，从而控 制知识获取过程：第二种为自主式粒计算学习算法。我们借助王国胤教授 等人提出的不确定性度量方法，采用决策表的最小确定性作为闽值，完成 自主式知识获取。 最后，我们通过仿真实验验证了算法的有效性。 关键词：粒计算，粗糙集，不确定信息处理，知识获取，自主式学习 重庆邮电人学硕十论文 a b s t r a c t a b s t r a c t g r a n u l a rc o m p u t i n g ( g r c ) i san e wt h e o r yb a s e do nt h ei d e ao fg r a n u l e s i np r o b l e ms o l v i n ga n di n f o r m a t i o np r o c e s s i n g i ts i m u l a t e st h ep r o c e s so f h u m a nb r a i n su n d e r s t a n d i n ga n ds o l v i n gp r o b l e m s i tl o o k sf o ra ne c o n o m i c a n dl o wc o s ts o l u t i o nb yc o n s i d e r i n gap r o b l e ma td i f f e r e n t l e v e l so f g r a n u l a r i t y i nr e c e n ty e a r s ，g r ch a sb e e nw i d e l ya p p l i e di nm a c h i n el e a r n i n g ， d a t am i n i n ga n ds o m eo t h e rf i e l d s i th a sb e e np r o v e da sa ne f f i c i e n tw a yf o r p r o b l e ms o l v i n g m a c h i n el e a r n i n g ( k n o w l e d g e a c q u i s i t i o n ) i s t oe x t r a c t i m p l i c i t ， p r e v i o u s l yu n k n o w n ，a n dp o t e n t i a l l yu s e f u li n f o r m a t i o nf r o ml a r g e - s c a l ed a t a i nt h i sp r o c e s s ，w ea r et r a n s f o r m i n gk n o w l e d g ef r o mad a t af o r m a t ，w h i c hi s n o tu n d e r s t a n d a b l ef o rh u m a n i n t oa n o t h e ru n d e r s t a n d a b i ea n de a s yt ob e u s e ds y m b o l i cf o r m a t i nt h ec u r r e n ti n f o r m a t i o ne x p l o s i o ne r a ，p e o p l en e e dt o a c q u i r e u s e f u l k n o w l e d g e f r o mm a s s i v e d a t a i n t e l l i g e n t i n f o r m a t i o n p r o c e s s i n gb e c o m e sah o tr e s e a r c hf i e l dd u et o t h i sd e m a n d w h e nd e a l i n g w i t hp r a c t i c a lp r o b l e m s ，i ti sv e r yd i f f i c u l tt oo b t a i nc o m p l e t ec e r t a i nd a t a t h e r e f o r e ，t h er e s e a r c ho fe x t r a c t i n gk n o w l e d g ef r o mu n c e r t a i ni n f o r m a t i o n s y s t e m sh a sb e c o m ea ni m p o r t a n ti s s u eo fa r t i f i c i a li n t e l l i g e n c e i na d d i t i o n ， c o n s i d e r i n gt h ec o m p l e x i t yo fp r o b l e ms o l v i n g ，w en e e dt of i n da na p p r o x i m a t e a n di n a c c u r a t es o l u t i o ni fi ti sh a r dt og e ta na c c u r a t es o l u t i o n t h e ya r ea l ln e w c h a l l e n g e sf o ru si ni n t e l l i g e n ti n f o r m a t i o np r o c e s s i n g a tp r e s e n t ，t h e r ea r ef e we f f e c t i v em e t h o d sf o rs o l v i n gt h ea b o v e p r o b l e m si ng r c i nt h i sp a p e r ，t w om e t h o d sa r ep r o p o s e df o rs o l v i n gt h e m a t f i r s t ，au s e r - d r i v e nk n o w l e d g ea c q u i s i t i o nm e t h o db a s e do ng r a n u l ec o m p u t i n g i sp r o p o s e d ，u s i n gat h r e s h o l dg i v e nb yu s e rt oc o n t r o lt h ep r o c e s s e so f g r a n u l e n e t w o r kc o n s t r u c t i o na n dk n o w l e d g e a c q u i s i t i o n s e c o n d l y ，a d a t a d r i v e nk n o w l e d g ea c q u i s i t i o nm e t h o db a s e do ng r a n u l ec o m p u t i n gi s p r o p o s e d b a s e do nt h em e a s u r i n gm e t h o df o rt h eu n c e r t a i n t yo fd e c i s i o n t a b l e sp r o p o s e db yp r o f gy w a n g w eu s et h em i n i m u ml o c a lc e r t a i n t ya sa t h r e s h o l dt oc o n t r o lt h el e a r n i n gp r o c e s s f i n a l l y ，o u rs i m u l a t i o ne x p e r i m e n tr e s u l t ss h o wt h ee f f i c i e n c yo ft h et w o 重庆邮电人学硕十论文 a b s t r a c t m e t h o d sp r o p o s e di nt h i sp a p e r k e y w o r d s ：g r a n u l a rc o m p u t i n g ，r o u g hs e t s ，u n c e r t a i n i n f o r m a t i o n p r o c e s s i n g ，k n o w l e d g ea c q u i s i t i o n ，d a t a d r i v i n gl e a r n i n g i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。掘我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废 邮鱼太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者硌谣闷 签字日期：支。口7 年6 月彩日 学位论文版权使用授权书 本学位论文作者完全了解重麽塑血盔堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重麽自鱼太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：孑友i 司 导师签名：钼j 缈 签字同期：立。7 年6 月g 目签字日期：咿4 7 年月字同 重庆邮电大学硕十论文第一章绪论 1 1 引言 第一章绪论 智能信息处理是当前信息科学理论和应用研究中的一个热点领域。在 过去几十年中，人们在专家系统、知识工程、人工神经网络、模糊集合等 众多领域不断实践和探索，取得了许多很好的成绩。粒计算( g r a n u l a r c o m p u t i n g ，简称g r c ) j 下是在此背景下提出的一种新的智能信息处理理 论，它覆盖了所有有关粒的理论、方法、技术和工具的研究。粒计算既是 模糊信息粒度、羊r 糙集、商空i 日j 、区问计算等诸多理论的超集，也是粒数 学的子集。由于粒计算能有效地分析和处理模糊、不精确、不一致的问题， 现已成为国际上人工智能研究的重要方法之一。同时，在机器学习、模式 识别、数据挖掘、知识发现、模糊和智能控制、语意w e b 服务等众多领域， 粒计算都有着广泛的应用前景。 1 2 粒计算理论发展状况 自从z a d e h19 7 9 年发表论文“f u z z ys e t sa n di n f o r m a t i o ng r a n u l a r i t y ” 以来【lj ，研究人员对信息粒度化的思想就产生了浓厚的兴趣。z a d e h 认为 很多领域都存在信息粒的概念，只是在不同领域中的表现形式不同。自动 机与系统论中的“分解与划分”，最优控制中的“不确定性”，区问分析罩的 “区间数运算”，以及d s 证据理论中的“证据”都与信息粒有密切的联系。 后来，h o b s s 在1 9 8 5 年直接用粒度( g r a n u l a r i t y ) 这个词作为论文题目在 美国l o s a n g e l e s 举行的国际人工智能联合会议上发表论文f 2 】，讨论了粒的 分解和合并，以及如何得到不同大小的粒，并提出了产生不同大小粒的模 型。 l i n 在1 9 8 8 年提出邻域系统并研究了邻域系统与关系数掘库之问的关 系pj 。1 9 9 6 年他在u c b e r k e l e y 大学z a d e h 的重点实验室做客座教授时， 向z a d e h 提出作“g r a n u l a rc o m p u t i n g ”课题的研究，当时z a d e h 称之为 “g r a n u l a rm a t h e m a t i c s ”，l i n 后来改称为“g r a n u l a rc o m p u t i n g ”，并且缩写 成g r c 。他发表了系列关于粒计算与邻域系统的论文 4 - t o 】，这些论文主 重庆邮电大学硕十论文第一章绪论 要是研究二元关系( 邻域系统、r o u g h 集和信任函数) 下的粒计算模型， 论述基于邻域系统的粒计算在粒结构、粒表示和粒应用等方面的问题，给 出了粒计算中的模糊集和r o u g h 集方法，并将粒计算方法引入数据挖掘和 机器发现领域。依据人们在解决问题时能从几个不同的粒度世界去分析和 观察同一个问题，并且很容易地从一个粒度世晃转到另一个粒度世界的模 型，张钹和张铃在1 9 9 0 年针对复杂问题求解，从仿生学的观点提出了问题 求解理论，建立了一种商结构的形式化体系，给出一套解决信息融合、启 发式搜索、路径规划和推理等问题的理论和算法，并已有一些相关研究和 应用以2 1 。1 9 9 7 年z a d e h 进一步指出 1 3 1 ，世上有三个基本概念构成人类认 识的基础：粒化、组织及因果关系。大体上来看，粒化是整体分解为部分； 组织是部分结合为整体；而因果关系则涉及原因与结果j 日j 的联系。物体的 粒化产生一系列的粒子，每个粒子即为一簇点( 物体) ，这些点难以区别， 或相似、或接近、或以某种功能结合在一起。一般来晚，粒化在本质上是 分层，时间可粒化为年、月、f 1 、小时、分、秒就是大家熟悉的例子。z a d e h 将模糊逻辑应用到信息粒化的过程，得到了模糊信息粒化理论，并指出 【13 】n o m e t h o d o l o g yo t h e rt h a nf u z z yl o g i cp r o v i d e sac o n c e p t u a lf r a m e w o r k a n da s s o c i a t e d t e c h n i q u e s f o r d e a l i n g w i t h p r o b l e m s i nw h i c h f u z z y i n f o r m a t i o ng r a n u l a t i o np l a y s ，o rc o u l dp l a y ，am a j o rr o l e ”这充分体现出模 糊信息粒化的重要性。在l i n 的研究基础上，y a o 结合邻域系统对粒计算进 行了详细地研究【1 4 一郇，发表了一系列研究成果【m 2 舶，并将它应用于知识挖 掘等领域，建立了概念之间的i f t h e n 规则与粒度集合之间的包含关系的 联系，并提出利用由所有划分构成的格求解一致分类问题，为数掘挖掘提 供了新的方法和视角。结合粗糙集理论，y a o 探讨了粒计算方法在机器学 习、数据分析、数据挖掘、规则提取、智能数据处理和粒逻辑等方面的应 用。y a o 给出了粒计算的三种观点【2 2 】： ( 1 ) 从哲学的角度看，粒计算是一种结构化的思想方法； ( 2 ) 从应用的角度看，粒计算是一个通用的结构化问题求解方法； ( 3 ) 从计算的角度看，粒计算是一个信息处理的典型范例方法。 这从更深层次的角度揭示了粒计算的本质。 总的来说粒计算是一种理论，一套方法学，一种技术，是在处理过程 中使用粒子来描述空间或求解问题的工具，它使得空b j 描述或问题求解更 加可行。粒计算可以说一把伞，它覆盖了凡是可以用到粒子进行研究的相 关领域。 随着粒计算研究的逐渐深入，近年来国际国内又有很多学者加入到了 2 重庆邮电人学硕十论文 第一章绪论 粒计算研究的领域。为了探讨r o u g h 集理论在各种环境下的应用，建立 r o u g h 集理论在各个专业领域中的应用前景，s k o w r o n l 2 27 1 以包含度概念来 研究粒近似空间上的r o u g h 下近似和r o u g h 上近似，发表了一系列关于信息 粒和粒计算的文章。刘清1 2 8 - 3 0 1 在研究r o u g h 逻辑的基础上，提出了粒一逻 辑的概念( g 一逻辑) ，构造了这种逻辑的近似推理系统，并将粒计算的方 法成功应用于医疗诊断专家系统。粒逻辑的提出，为经典逻辑的应用丌辟 了新途径，也为处理非规范知识提供了较好的理论工具。粒逻辑的运算涉 及整体到局部的分解和局部到整体的合并，以此提供了a l ( a r t i f i c a l i n t e l l i g e n c e ) 中问题求解的新思路。近几年来在掀起粒计算研究的热潮下， 商空间理论被人们广泛认识和推广，2 0 0 3 年张铃和张钹将z a d e h 的模糊概 念与商空间理论结合，提出模糊商空间理论，为粒计算提供了新的数学模 型和工具，并把这些理论和方法应用于数据挖掘等领域p 1 - 3 5 1 。2 0 0 2 年苗夺 谦等人【36 】对知识的粒度计算进行了探讨，引入属性的重要度以及在求最小 约简方面的应用，并提出了协调度的概念以及在构造决策树方面的应用。 王飞跃等人 3 7 1 对词计算和语言动力学进行了探讨，建立了以词计算为基 础，对问题进行动态描述、分析、综合，进而设计、控制和评估的语言动 力学系统。这是用粒计算研究复杂系统的一个重要而有意义的研究方向。 王国胤等人【3 8 - 4 4 1 提出了基于容差关系的粒计算模型，使用属性值上的容差 关系给出了不完备信息系统的粒表示、粒运算规则和粒分解算法，同时结 合粗糙集中的属性约简问题，提出了不完备信息系统在粒表示下属性必要 性的判定条件，并对粒计算方法在规则提取方面作了尝试性的应用研究。 郑征等人1 4 “47 】提出了一种新的粒计算模型一一相容粒度空问模型，该模型 基于这样的思想，即人类具有根据具体的任务特性把相关数据和知识泛化 或者特化成不同程度、不同大小的粒的能力，以及进一步根掘这些粒和粒 之间的关系进行问题求解的能力，并将相容粒度空间应用到图像纹理识别 中，取得良好效果。并在此基础上分析了相容粒度空问模型在数据挖掘中 的应用及其前景，给出了基于相容粒度空间模型的建模和问题求解的一般 方法。h 东波等人【4s j 从信息粒度的角度剖析聚类和分类技术，试图使用信 息粒度原理的框架来统一聚类和分类，指出从信息粒度的观点来看，聚类 是在一个统一的粒度下进行计算，而分类却是在不同的粒度下进行计算， 并根据粒度原理设计了一种新的分类算法，在大规模中文文本分类的应用 实践表明这种分类算法有较强的泛化能力。z h a n g y q 等人【4 9 。5 0 】对粒神经 网络进行了探讨，并在高效知识发现中得到很好的应用。李道国等人1 5 i 在粒计算的基本思想和理论基础上，研究了基于粒向量空间的人工神经网 重庆邮电人学硕十论文第一章绪论 络模型，在一定程度上提高了人工神经网络的时效性、知识表达的可理解 性。随着概念格理论【5 2 】研究的不断深入，杜伟林等人【5 3 1 根据概念格与粒度 划分在概念聚类的过程中都是基于不同层次的概念结构来进行分类表示， 而且粒度划分本身构成一个格结构的特点，研究了概念格与粒度划分格在 概念描述与概念层次转换之间的联系，通过对概念的分层递阶来进行概念 的泛化与例化，使概念在递阶方面忽略不必要的冗余，达到更高的效率。 粒计算方法的应用也越来越广泛，已经渗透到自然科学和社会科学的 很多领域。比如：图形图像处理，海量数据挖掘，复杂问题求解等等。粒 计算理论虽然已经得到大家的广泛认识，但罩面依然还有很多问题有待我 们继续研究和解决。 1 3 论文背景及工作内容 知识获取是一个从大量的数掘中挖掘我们所需要的知识的过程，它是 随着我们的数据库不断扩大，计算能力不断增强而出现的，它是一个知识 转化的过程。 粒计算是当前计算智能研究领域中模拟人类思维和解决复杂问题的 新方法。它覆盖了所有有关粒度的理论、方法和技术，是复杂问题求解、 海量数据挖掘、模糊信息处理的有力工具。y y y a o 和j t y a o 等学者在 基于粒计算的数据挖掘方面进行了一系列的研究，尝试用粒计算模型束解 决分类问题，并且提出了基于粒计算模型的多个知识获取算法及应用。但 是，目前基于粒计算模型的知识获取算法还不能很好的处理不一致、不完 备的情况。其外，在信息不断膨胀的今天，由于现代系统同趋复杂，精确 求解常常很难实现，从问题的简化上考虑也需要寻找一种更加灵活的方 法，这些都是基于粒计算的知识获取过程中的新挑战。 对不确定性条件下的知识获取方法的研究，是机器学习研究中的一项 重要课题，现在主要有两种处理方法。一种是传统的基于用户驱动的方法， 它通过人为输入的先验知识来帮助机器的学习。例如，在产生规则的时候 对于不确定规则的取舍往往根据产生规则的可信度来决定，这个取舍界限 的标准常常就是一个先验知识。然而，这种方法对专家知识倚赖较高，不 能自主地完成学习任务，智能化程度低。特别是对于庞大的、复杂的或者 是人类没有完全认知的领域，这种先验知识往往更是不准确的，或者是不 能得到的。另一种是近年来被广泛研究的自主式( 数掘驱动) 学习方法。 自主式学习是根据数据集自身的内部特性来控制机器学习过程。自主式学 重庆邮电人学硕十论文 第一章绪论 习方法不但能简化问题求解过程，而且可以克服对先验知识的依赖性，提 高对人类未知或者复杂系统的学习能力。王国胤教授等人针对该问题进行 了深入的研究，给出了一种决策表信息系统的不确定性度量方法，提出了 一种自主式学习模型，并把此模型推广到多个相关领域，提出了多种自主 式学习算法【5 4 巧7 1 ，大大的推动了自主式学习研究的发展。 本文中提出了两种基于粒计算的知识获取算法：用户驱动粒计算学习 算法，它通过用户输入的先验知识作为阂值来控制粒网络的构造，从而控 制知识获取过程；自主式粒计算学习算法，我们借助王国胤教授等人提出 的不确定性度量方法，采用决策表的最小确定性作为阈值，完成自主式知 识获取。 本论文工作得到国家自然科学基会( n o ，6 0 3 7 3 1 1 1 ，n o 6 0 5 7 3 0 6 8 ) 、教 育部新世纪优秀人才支持计划( n c e t ) 、重庆市教委科学技术研究项目 ( n o 0 4 0 5 0 5 ) 的资助，是这些项目整体研究工作中的一部分。这些项目 从理论上系统研究基于粗糙集的智能数据分析技术，建立一套完善的智能 数据分析模型理论，建立基于r o u g h 集理论的表示、度量、和处理不确定 性信息的理论和方法；在算法开发基础上，形成一整套关于粗糙集的算法 库，开发相应的软件平台和应用系统。通过研究粒计算的基础理论和算法， 试图用高效的粒计算方法处理数据挖掘等问题，为智能计算提供新的理论 工具和计算方法。 1 4 论文组织与结构 本论文的组织结构如下： 第一章介绍了粒计算理论的发展和现状，以及本论文的研究背景和工 作内容等。 第二章中为了便于后面的叙述，我们先对狙糙集理论中的基本概念以 及基于粗糙集理论的自主式学习方法进行简单介绍。 第三章介绍了粒计算基础理论，包括粒计算的基本问题、基本模型、 以及需要进一步研究的问题。 第四章介绍了粒计算知识获取模型，提出了两种基于粒计算的知识获 取算法，并通过仿真实验来证明算法的有效性。 第五章对本文进行总结。 2 1 引言 第二章r o u g h 集理论基础 r o u g h 集( 粗糙集) 理论由波兰逻辑学家z p a w l a k 教授于1 9 8 2 年提 出，是一种描述不完整性和不确定性的数学工具，能有效地分析和处理不 精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示 潜在的规律。现在，粗糙集理论的研究在系统理论、计算模型的建立和应 用系统的研制开发上，都已取得了很多成果，也建立了一套较为完善的粗 集理论体系。 本章主要是介绍粗集以及基于粗糙集的自主式知 t 学习模型，首先将 对粗集理论的有关的概念作一个简要的介绍。 2 2r o u g h 集理论的基本概念 知识理论的基础概念是分类和范畴，实际上范畴是特征子集对对象的 描述，是给定知识库中可获得的知识。某些范畴在一个知识库中是可定义 的，但在另一个知识库中却不可定义，粗粗糙集正是对这些无法定义的范 畴进行处理，使其能够近似定义。 2 2 1 粗糙集与近似 在粗糙集中，“知识”被认为是一种将现实或抽象的对象进行分类的能 力。 定义2 1 ：给定我们感兴趣的对象论域u ，对于任何子集x u ，称之 为u 中的概念或范畴。为了规范起见，我们认为空集也是一个概念，并且 u 中任何概念族称为关于【厂的抽象知识，简称知识。我们通常用等价关系 代替分类。 定义2 2 ：设u 是一个论域，r 是u 上的一个等价关系。叫r 表示u 上由r 导出的所有等价类。卜1 。表示包含元素x 的r 的等价类，x u 。一 个知识库就是一个关系系统k = u ，p 。其中u 是论域，j p 是上等价关 系族。如果q p 且q o ，则n q ( q 的所有等价关系的交) 也是一种等 重鏖塑坐里堕笙塞笙三童垦! ! 业堡堡垒垦型 价关系，且记为i n d ( q 1 。不分明关系的概念是粗糙集理论的基石，它揭示 出论域知识的颗粒状结构。 定义2 3 ：令x u ，当x 能够用属性子集r 确切地描述( 即属性子 集尺所确定的u 上的不分明关系的并) 时，称x 是可定义的，否则称x 是不可定义的。足可定义集也称作精确集，太不可定义集也称为非精确集 或r 粗糙集( 在不发生混淆的情况下也简称为粗糙集) 。定义2 4 ：假设给 定知识库k = ( u ，r 1 ，对于每个子集x u 和一个等价关系r i n d ( k ) ，我 们可以根据r 的基本集合的描述来划分集合量为了衡量基于月的基本集 合的描述n 精确地说明x 中对象的隶属度情况，我们使用下近似集与上 近似集这两个概念，它们分别定义如下，下近似集： 疋( x ) = u r u i i n d ( r ) ：l ：x ( 2 1 ) 上近似集： r 一( x ) = u l ：u i i n d ( r ) ：rc 7 x = 0 ( 2 2 ) 也可以表示为： 是( x ) = 工：f x k x ( 2 - 3 ) r 一( x ) = x u ： x k n x o ( 2 4 ) 定义2 5 ：集合b n r ( x ) = r 一( 彳) 一疋( 彳) 称为x 的r 边界域，集合 p o s 。( x ) = 足( x ) 称为x 的r 正域，集合n e g i 。( x ) = u 一是( x ) 称为的胄负 域。 足( x ) 是根据知识胄，u 中所有一定能够归入x 的元素的集合，即所 有包含于x 的f 的并。尺一( x ) 是根据知识r ，u 中一定能和可能能够归入x 的元素的集合，即所有与x 的交不为零的r 的并。砌。( x ) 是根掘知识r ， 【，中即不能肯定归入集合x ，又不能肯定归入集合x 的元素构成的集合。 2 2 2 决策表 粗糙集理论中应用决策表束描述论域中的对象。它是一张二维表格， 每一行描述一个对象，每一列描述对象的种属性。属性分为条件属性和 决策属性，论域中的对象根据条件属性的不同，被划分到具有不同决策属 性的决策类。 定义2 6 ：定义一个决策表信息系统( 简称决策表) s = ， 其中u 是对象的集合，也称为论域，r = c u d 是属性集合，子集c 和d 分 里鏖坚生厶堂堕堡塞笙三童垦! ! 韭生堡堡茎型 别称为条件属性集和决策属性集，d 庐，v = u ，。r 是属性值的集合，表 示属性r r 的属性值范围，即属性r 的值域，厂：u 尺寸矿是一个信息函数， 它指定u 中每一个对象x 的属性值。 定义2 7 ：设u 为一个论域，p 、q 为定义在u 上的两个等价关系簇， ii q 的p 萨域记为p o s e 倒，定义为：p o s p ( q ) = up ( 2 5 ) x d j i g 定义2 8 ：给定决策表s ，c 和d 分别为决策表的条件属性集和决策属 性，条件分类定义为：e u 1 1 n d ( c ) ，( f - 1 ，m ) ，m 为条件分类的个数； 决策分类定义为：x ，u i i n d ( d ) ，q = l ，珂) ，n 为决策分类的个数。 定义2 9 ：在决策表s = 中，r = c u d ，若对于u c 中同 一等价类的记录都有相同的决策值，则称这个等价类中的任一记录为确定 性记录；若对于u c 中同一等价类中的已录有不同的决策值，则称这个等 价类中的任一记录为不确定性记录。 定义2 1 0 ：在决策表s = 中，若所有的记录都是确定性记 录，则s 称为相容表( 一致表) ；否则s 称为不相容表( 不一致表) 。 2 2 3 约简与核 我们经常要在保持知识库中初等范畴的情况下消去冗余范畴，迸行知 识简化。完成知识简化的基本工作是利用约简和核这两个基本概念柬进行 的。 定义2 1 l ：令月为一等价关系族，且，r ，如果1 n d ( r ) = i n d ( r p ) ， 称r 为r 中可省略的，否则，为r 中不可省略的。 定义2 1 2 ：对于属性子集p r ，若存在q = p 一，q p ，使得 1 n d ( q ) = i n d ( p ) ，且q 为最小子集，则称q 为p 的约简，用r e d ( p ) 表示。 定义2 1 3 ：p 中所用约简属性集中都包含的不可省略的集合，即约简 r e d ( p ) 的交集称为p 的核，记作c o r e 例。它是表示知识必不可少的重要属 性集。 可以看出，核这个概念的用处有两个方面：首先它可以作为所有约简 的计算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其 次可以解释为在知识约简时它是不能消去的知识特征部分的集合。一个属 性集合尸可能有多种约简，计算约简的复杂性随决策表的增大呈指数增长， 是一个典型的n p 完全问题，实际中没有必要求出所有的约简。 2 2 4 属性重要性 在信息系统中，每个条件属性所占的地位不一定相同。一些条件属性 占的地位较高，而另外的条件属性占的地位较低。属性的重要性可以在辅 助知识的基础上事先假设，并用“权重”表示。在羊h 糙集方法中，不使用假 设的信息，只利用表中的数据进行衡量。因为信息系统的属性重要性是建 立在分类能力上的，为了衡量条件属性的重要性程度，我们可以从表中删 除一些属性，来考察信息系统的分类会产生怎样的变化：如果去掉某属性 会相应的改变分类，则说明该属性的重要性高：反之说明该属性的重要性 低。 定义2 1 4 ：通过分类质量唯来衡量分类能力，定义为： r r = l p o s r ( d ) l i u i ( 2 6 ) 属性a 的重要性为： g a i n = r r r r 山j ( 2 7 ) 2 2 5 规则集 定义2 1 5 ：令s = 表示一个决策表，且b c _ c ，山s 产生 的一个规则集为表示为f = 石；，石：，f ：) ，其中： 形= a - - - ) d i 。c a n dd e j d ( f - 1 ，) ( 2 8 ) ，表示f 中规则的数目，在z ；中，如果某些规则中的某个属性值被约简掉， 那么在这些规则中被约简掉的属性表示为“”。 2 3 基于r o u g h 集理论的自主式学习方法 在实际研究中，决策表的不确定性和决策规则的不确定性是大量存在 的。不确定性的存在，缘于很多因素，如选择的描述属性不充分、测量中 的差错以及记录过程中的失误等。因此，在规则知识获取的研究中，解决 决策表的不确定性问题很重要的。通常情况下，人们是依靠研究领域的先 验知识( 专家知识) 来控制机器学习过程。然而，这种方法对专家知识倚 赖较高，不能自主地完成学习任务，智能化程度低。特别是对于庞大的、 复杂的或者是人类没有完全认知的领域，这种专家先验知识往往更是不准 确的，或者不能得到的。 9 重鏖坚皇盔兰亟迨塞蔓三童坠! 韭堡堡迨垦型 2 3 1 自主式学习方法介绍 现在，有很多机器学习方法，如人工神经网络、模糊集、粗糙集、决 策树、遗传算法等，很多学者对数据挖掘技术进行了大量的研究，而很少 涉及到数据挖掘的本质问题：什么是机器学习、在机器学习过程中需要得 到些什么、我们在机器学习过程中需要做些什么和需要遵循什么规则等。 重庆邮电大学的王国胤教授等对这个问题作了较深入的研究，通过理论证 明和试验仿真结果，指出摆脱对先验知识的依赖是完全可能的 5 4 - 5 7 6 3 1 。他 在文献 6 3 中指出：所谓机器学习( 知识获取) ，其目标是将大量数据中所 隐含的知识发现出来，也就是将知识从人们难于理解、操作和使用的数据 表达形式转化为便于人们理解、操作和使用的决策规则形式的表达形式。 由此可以看出，机器学习过程，实质上是知识的一个形式转换过程，而不 是知识的产生过程，在机器学习过程中，仅有知识的形式转换，并没有新 的知识产生。如何解决对先验知识的倚赖性，实现机器对信息系统的智能 学习正是自主式学习研究的出发点。 a 自主式( 数据驱动) 的机器学习 从图2 1 可看出，数据挖掘过程是知识从数据形式向符号形式的转换 过程，因此在这个过程中没有新知识的产生，这好比我们将一本英文书翻 译为中文一样，在翻译过程中书所含有的知识量应保持不变，否则我们的 翻译就出了问题。 b 自主式学习过程 在学习过程中，知识的特性应该保持不变。这个观点为我们设计学习 算法提供了标准。但是，知识如何表达是人工智能中一个尚未解决的问题， 即我们并不知道知识的所有特性，究竟需要什么及多少特性去表现知识 呢? 因此，为了保证在学习过程中知识的特性不发生变化，我们应知道在 数据格式下知识包含了哪些特性，并用这些特性的不变性去控制学习的过 程，这是自主式学习的关键所在。于是自主式学习过程可归纳如下： s t e p l ：选择一个度量方法，它既能表示知识在数据格式的特性，也能 表示其在符号格式下的特性： s t e p 2 ：分别度量在数据格式下和符号格式下的特征值： s t e p 3 ：用这个特征值去控制学习的过程。 1 0 里压唑生厶堂堡主堡塞笙三童垦! ! 韭釜堡鲨堇壁 图2 1 机器学习过程中知识的转换框架幽 2 3 2 基于r o u g h 集理论的自主式学习算法 重庆邮电大学王国胤教授在文献 5 4 中给出了决策表整体不确定性和 决策表局部不确定性的度量方法，指出决策表的不确定性在机器学习的过 程中是不会改变的，以此为基础设计了一种以决策表局部最小不确定性为 闽值的决策表的自主式学习模型，尹德升等将这种不确定性度量方法应用 到决策树的预修剪中设计了决策树的自主式学习算法【55 1 ，王燕等提出了基 于概念格的自主式学习算法【57 1 。现以文献 5 4 】中所给出的自主学习模型为 例进行说明。 a 决策表不确定性情况分析 决策表中的不确定性情况一般来说可以分为三种： 第一种不确定性情况是能够从决策表中直接得到的。它就是指决策表 中包含冲突( 矛盾) 的样本，即两个样本的条件属性取值完全相同，而决 策( 分类) 属性的取值不同。这种不确定性情况是本文中着重处理的，该 不确定性的产生，主要有以下三种可能： 1 ，条件属性不充分，也就是说根据现有的条件属性不能对样本进行丁f 确的分类，必须增加额外的条件属性才能够正确区分样本。 2 ，样本属性值的测量或记录不正确，从而使本来可以区分的样本变得 不能区分了。 3 ，在得到决策表的预处理过程中产生了冲突( 如在离散化过程中可能 将一些本来可以区分的样本变得不能区分了) 。 玺压堕生丛竺堡主丝塞笙：童垦! ! 业基堡堡蔓型 第二种不确定性情况是指原本在决策表中没有冲突的样本，在对信息 表处理过程中引入的不确定性，如在条件属性上作投影等。 第三种不确定性情况不是从决策表中能够直接反映出来的，而是由于 决策表只包含了所有可能的样本( 或者样本全集，问题空| 日j ) 中的部分， 没有包括所有可能出现的样本情况，即待识样本和决策表中的样本冲突。 b 决策表不确定性度量 对于决策表s = ，r = c u d ，c 为条件属性集，d 为决策 属性集，分类e u i i n d ( c ) ( i - 1 ，m ) 为条件分类，x ，uj i n d ( d ) ， 0 = 1 ，n ) 为决策分类，则对于任意条件分类e ，对应有集合f ，满足： f = m a x e n x ，i x ，u i i n d ( d ) ( 2 9 ) 因此对于各条件分类集合蜀、墨、瓦都分别存在对应的五， f 、乙。 定义2 1 7 ：给定决策表s = ，e 、e ，、e 。是所有 的条件分类，那么决策表整体确定性定义为： 肛2 订( 2 1 0 ) 决策表整体不确定性为： 。1 一订 ( 2 定义2 1 8 ：给定决策表s - - - - ，r = c u d ，c 为条件属性集， d 为决策属性集，分类e u l i n d ( c ) ( i = 1 ，晰) 为条件分类， x u i i n d ( d ) q = l ，”) 为决策分类，则对任意条件分类e ，u 1 1 n d ( c ) ， 其对于决策属性分类的确定性程度定义为： r 。( 巨) = m a x le ，n x ji i 巨i ix ，u ii n d ( d ) = i fi 1e ( 2 1 2 ) 定义2 1 9 ：给定决策表s - - - - - ，j r 。( 巨) 一、盯。( e ) 、 r 一( 巴) 是条件分类对决策分类的确定性程度，则决策表局部最小确定性 定义为： 瓯= m i n j r 一( 毛) ，r 一( e ) ，茁一( e 。) ( 2 13 ) 决策表局部最大不确定性定义为： o r 。= 1 一口。( 2 1 4 ) 决策表整体不确定性反映了决策表的整体冲突情况，决策表局部最大 1 2 不确定性反映了决策表各条件分类中的最大冲突情况。通过上面的一些定 义，我们比较完全地度量了决策表的不确定性。 定理1 ：由决策表s 得到的规则集f ，在决策表能够充分反映领域样 本数据的情况下，对从决策表中获取的规则知识进行测试的最大可能诈确 率刁等于决策表整体确定性以。 即有r = 。= 等i ，其中m 为决策表条件分类数。 l u c 决策规则的不确定性度量 定义2 2 0 ：对于决策表s = ，r = c u d 是属性集合，子集c 和d 分别为条件属性集和决策属性集，决策规则4 专b 的可信度c f ( a j b ) 定义为： c f ( 4 斗b ) = i x n y i i x i ( 2 15 ) 其中，集合x 为条件属性值满足公式a 的样本的集合，集合y 为决 策属性值满足公式b 的样本的集合。如果c f ( a 寸b ) = 1 ，则称决策规则 4 一b 是一致的( 协调的) ；否则，决策规则a b 是不一致的( 不协调的) 。 定义2 2 l ：对于决策表s = ，生成规则集f ( 设f 有 条 规则) ，属于，的规则为z ，卜、，对应的可信度为啊、矿，、。矾， 则舰则集，的最小可信度为夕= m i n c f ，c f ，玩 。 在s k o w r o n 算法【6 4 l 中，规则集是由阈值控制生成的，对规则集中的任 意一条规则，其可信度要大于等于阈值，即有规则集的最小可信度大于等 于阈值。 d 决策表与规则集不确定性关系 规则集是通过对决策表的学习 ! 导到的，决策表的不确定性和规则集的 不确定性必然存在某种联系。但是由于控制规则生成的阈值是往往还是研 究人员通过其他方法得到的先验知识，从而隔离了决策表的不确定性和规 则集的不确定性之白j 的联系。因此我们考虑不加入先验知识，直接通过对 决策表的不确定性研究来得到闽值。决策表的局部最小确定性反映了决策 表各条件分类中的最大冲突情况，而规则集的最小可信度对应规则集中冲 突最大的规则，如果要求决策表每一个条件分类中都有数据都被测试出， 我们需要满足规则集的最小可信度大于等于决策表的局部最小确定性。由 定理l 知道，能够被正确识别的数据所在条件分类对决策分类的确定性程 度都大于等于决策表的局部最小确定性，因此，我们考虑用决策表的局部 最小确定性作为阈值来控制规