（计算机应用技术专业论文）不确定性条件下的知识获取方法的研究.pdf

重庆邮电大学硕士论文摘要 摘要 在信息不断膨胀的今天，人们需要从大量数据中获取有效的知识，这使得 智能信息处理成为了众多学者所面临的课题。在处理现实问题时，很难得到完 全确定的数据，因此对不确定性条件下的知识获取方法的研究，是机器学习研 究中的一项重要课题。 粒计算( g r a n u l a rc o m p u t i n g ，简称g r c ) 是一种新的智能信息处理理论。 现已成为国际上人工智能研究的主要方法之一。对于粒计算的研究，很大程度 上是因为它模拟了人脑认识和解决问题的过程。采用粒计算思想的很多理论已 经被广泛地应用于机器学习、数据挖掘等领域，并被证明是有效的求解问题的 方法。粗糙集理论，作为粒计算理论的子集，是一种处理模糊和不确定知识的 软计算工具。它能有效地分析和处理不精确、不一致、不完整等各种不完备信 息，并从中发现隐含的知识，揭示潜在的规律。近年来在机器学习、数据挖掘 等多个领域得到广泛应用。 本文通过研究决策表中样本和其产生的决策规则的不确定性，提出了一种 不确定性条件下基于粒计算的自主式知识学习模型( s l m g r c ) 。该方法运用粒 计算思想，在决策表样本空间的不同层次对其进行分解，再从分解得到的样本 粒子中获取规则，对于不确定性数据，我们借助王国胤教授等人提出的不确定 性度量方法，采用决策表局部最小确定性作为控制规则生成的阈值。通过仿真 实验，证明验证了s l m g r c 算法的有效性。 关键词：粒计算，粗糙集，不确定信息处理，知识获取 重庆邮电大学硕士论文 摘要 a b s t r a c t i nt h ei 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 oa c q u i r eu s e f u lk n o w l e d g ef o r m m a s s i v ed a t a t h i sg r o w i n gn e e dh a sm a d ei 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 ga r e s e a r c hh o t s p o t w h e nd e a l i n gw 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 n c o m p l e t e ，c e r t a i nd a t a t h e r e f o r e ，t h e r 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 m u n c e r t a i ni n f o r m a t i o nh a sb e c o m ea ni m p o r t a n ti s s u ef o rd i s c u s s i o n g r a n u l a rc o m p u t i n g ( g r c ) i sa ne m e r g i n gt h e o r yb a s e do nt h eu s eo fg r a n u l e s i n p 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 t h er e s e a r c ho ng r a n u l a r c o m p u t i n g ，t oag r e a te x t e n t ，s i m u l a t e st h ep r o c e s si nw h i c hf i u m a nb r a i n u 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 m a n yt h e o r i e se m p l o y i n gt h ei d e ao fg r ch a v e b e e nw i d e l ya p p l i e di nm a c h i n el e a m i n g ，d a t am i n i n ga n do t h e rf i e l d s ，w h i c hh a v e b e e np r o v e da se f f i c i e n tw a y sf o rp r o b l e ms o l v i n g r o u g hs e tt h e o r y , a sas u b s e to f g r a n u l a rc o m p u t i n gt h e o r y , i sat o o lf o rd e a l i n gw i t hf u z z ya n du n c e r t a i nd a t a i ti s e f f i c i e n tt oa n a l y z e ，p r o c e s sa n da c q u i r ep o t e n t i a l k n o w l e d g ef r o mi m p r e c i s e ， i n c o n s i s t e n ta n di n c o m p l e t ed a t a r o u g hs e tt h e o r yh a sb e e ns t u d i e da n da p p l i e di n m a c h i n el e a r n i n g ，d a t am i n i n ga n dm a n yo t h e rf i e l d s i nt h i sp a p er ，am e t h o dt od e c o m p o s ed e c i s i o nt a b l e si sp r o p o s e d a c c o r d i n gt o t h i sm e t h o d ，d e c i s i o nt a b l e sa r ed i v i d e di n t og r a n u l e sa td i f f e r e n th i e r a r c h i e s b a s e d o nt h e s eg r a n u l e s ，r u l e sa r eg e n e r a t e d p r o f g y w a n g sm e t h o df o rm e a s u r i n gt h e u n c e r t a i n t yo fd e c i s i o nt a b l e sa r ea d o p t e dt op r o c e s su n c e r t a i ni n f o r m a t i o n ，t h e m i n i m u ml o c a lc e r t a i n t yi su s e da sat h r e s h o l dt oc o n t r o lt h ep r o c e s so fr u l e g e n e r a t i o n t h es i m u l a t i o ne x p e r i m e n tr e s u l t sp r o v et h a tt h i sm o d e li sa l le f f i c i e n t w a y f o rr u l eg e n e r a t i o nu n d e ru n c e r t a i nc o n d i t i o n s k e yw 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 ，u n c e r t a i ni n f o r m a t i o np 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 i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得重废壑电盔堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：1 去金签字日期：谚口年月f 日 学位论文版权使用授权书 本学位论文作者完全了解重废邮鱼太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人授权 重送邮鱼太堂 可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：廿念导师签名：巧以自眇 签字日期：。6 年6 月? 日签字日期：缈年莎月7 日 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 在信息不断膨胀的今天，人们需要从大量数据中获取有效的知识，这使得智 能信息处理成为了众多学者所面临的课题。智能信息处理研究和工程应用中所需 要解决的核心问题之一，是对不确定性条件下的知识获取方法的研究。 粒计算( g r a n u l a rc o m p u t i n g ，简称g r c ) 是一种新的智能信息处理理论。它 能有效地分析和处理模糊、不精确、不一致、部分真值的问题，现已成为国际上 人工智能研究的主要方法之一。r o u g h 集理论以确定的上、下近似关系来表达和 处理近似集合的不确定特性，并在此基础上发展了一套不确定知识的获取、处理 方法，在不确定信息处理领域取得了较大的成功。 本文所研究和讨论的主要问题，是如何在不确定性条件下运用粒计算和粗糙 集理论，有效地从大量数据中获取知识。结合我们的解决方案【3 引，可以得到较好 的结果。 1 2 知识获取及其发展状况 知识获取是从数据集中识别和挖掘有效的、新颖的、潜在有用的以及最终可 以理解的数据和规则，需要有一个具有智能化的过程来实现知识的获取。知识获 取主要包括三个方面：数据准备、数据挖掘以及结果的解释与分析。知识获取的 方法有许多，其主要的研究成果9 t2 1 , 2 3 2 7 】包括以下几个方面： 统计方法是从事物的外在数量上的表现去推断该事物可能的规律性，其处理 过程主要包括三个阶段：搜索数据，分析数据以及进行推理。常见的统计方 法有回归分析、判别分析、聚类分析以及探索性分析。 f u z z y 集理论是表示和处理不确定性数据的重要方法，不仅可以处理不完全 数据、噪声或不精确数据，而且开发数据的不确定性模型方面也非常有用， 能够提供比传统更灵巧、更平滑的方法。 r o u g h 集理论【2 】自从1 9 8 2 由z p a w l a k 教授提出以来，是一种知识获取的方 法，已经应用到很多领域，能有效地分析和处理不精确、不一致、不完整等 信息，并从中发现隐含的知识，揭示潜在的规律，也是一种关于粒计算的具 体理论，使我们对粒计算有更深入的了解。 支持向量机( s v m ) 建立在计算学习理论的结构风险最小化原则之上的，其主 重庆邮电大学硕士论文第一章绪论 要思想是针对两类分类问题，在高维空间中收寻一个超平面作为两类附分 割，以保证最小的分类错误率，其主要优点是可以处理线性不可分的情况。 张钹、张铃教授提出的商空间理论，以集合作为描述粒的基本单元，将问题 不断的细分或合成，直至获取问题的解。商空间理论以及被应用到小波分析 和生物信息处理等领域。 粒计算作为一种新兴的知识获取研究领域，最大的优点是能够在不同甘勺层次 或粒度下获取知识，由于还处于探索阶段，很多地方还不成熟，值得作进一 步研究。 1 3 论文背景以及工作内容 在处理现实问题时，很难得到完全确定的数据，因此，对不确定性条件下的 知识获取方法的研究，是机器学习研究中的一项重要课题。在粗糙集理论研究中， 对不确定性数据的处理已经有许多研究成果：s k o w r o n 教授等人提出的一种通过 投影得到缺省决策规则的算法i ，可以从不确定性数据中提取规则，但该算法需 要人为确定域值来控制规则的生成；王国胤教授等人针对该问题给出了一种决策 表信息系统的不确定性度量方法i l ”，并且基于这种方法提出了一种不依赖领域先 验知识的自主式知识学习模型。 粒计算是一种基于粒子的问题求解和信息处理方法，其基本思想存在于许多 领域，如经典集合论及其扩展( f u z z y 集、r o u g h 集、v a g u e 集等) 、区间分析、 证据理论、神经网络、决策树、机器学习、数据挖掘、语义网络、聚类分析等。 1 9 7 9 年f u z z y 集创始人l a z a d e h 教授在世界上首次提出了模糊信息粒化问题。 从那以后，信息粒化开始得到人们越来越多的关注。在运用粒计算理论进行知识 获取的研究方面，已经有了一些研究成果。文献【39 ，”j 中的r g a g c 算法，通过对 样本空间进行不同层次的分解，再从每一层的粒子中获取规则，与许多经典决策 树算法相比，该算法不需要考虑属性选择问题，同时结合商空间的同态原则来控 制规则粒的生成过程，相应地提高算法的执行效率。但是r g a g c 算法只能处理 确定性的信息。 本文通过研究决策表中样本和其产生的决策规则的不确定性，提出了一种对 样本空间进行不同层次粒化的方法，利用这种方法结合王国胤等人提出的不确 定度量方法，提出了一种不确定性条件下基于粒计算的自主式知识学习模型 ( s l m g r c ) 。仿真实验表明，s l m g r c 生成的规则集较小，同时保证了对未知 样本较高的识别率。 本论文工作得到国家自然科学基金( 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 ) 2 重庆邮电大学硕士论文第一章绪论 以及重庆市自然科学基金( n o 2 0 0 5 b a 2 0 0 3 ) 资助，是这些项目整体研究工作中 的一部分。这些项目旨在从理论上系统研究基于粗糙集的智能数据分析技术，建 立一套完善的智能数据分析模型理论，建立基于r o u g h 集和粒计算机制的表示、 度量、和处理不确定性信恩和知识的理论系统；在r o u g h 集理论研究基础上， 对r o u g h 集中的核心约简技术进行重点突破与改进，研究最优约简的理论框架 与基于动态系统演化的实现方案：在算法开发基础上，形成一整套关于粗糙集的 算法库，开发相应的软件平台和应用系统。 1 4 论文组织与结构 本论文的组织结构如下： 第一章介绍了知识获取及其发展状况，以及本文的研究背景和研究工作； 第二章中，为了便于后面的叙述，我们先对粗糙集、粒计算理论中的一些基 本概念进行了简单介绍； 第三章提出了一种对样本空间的粒化模型，以及运用这个模型从数据集中获 取知识的方法。 第四章讨论了s l m g r c 算法的实现，并通过与缺省规则算法的对比实验来验 证s l m g r c 算法的有效性。 第五章对本文进行了总结。 重庆邮电大学硕士论文 第二章理论基础 2 1 引言 第二章理论基础 为了方便后面章节的讨论，这一章我们对粗糙集和粒计算的有关概念进行 简单的介绍。 2 2 粗糙集理论基础 粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析和 处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭 示潜在的规律。粗糙集理论的研究已经经历了近2 0 年的时间，无论是在系统理 论、计算模型的建立和应用系统的研制开发上，都已取得了很多成果，也建立 了一套较为完善的粗糙集理论体系。 2 2 1 粗糙集与近似 在粗糙集中，“知识”被认为是一种将现实或抽象的对象进行分类的能力。 定义2 1 给定我们感兴趣的对象论域【，对于任何子集x u ，称之为u 中 的概念或范畴。为了规范起见，我们认为空集也是一个概念，并且u 中任何概 念族称为关于u 的抽象知识，简称知识。我们通常用等价关系代替分类。 定义2 2 设u 是一个论域，月是u 上的一个等价关系。洲尺表示u 上由r 导出的所有等价类。卜1 。表示包含元素x 的尺的等价类，x u 。一个知识库就 是一个关系系统k = u ，p ，u 其中是论域，p 是u 上等价关系族。如果q p 且q 中，则iq ( q 的所有等价关系的交) 也是一种等价关系，称为p 上不分 明关系，且记为i n d ( p 1 。 不分明关系的概念是r o u g h 集理论的基石，它揭示出论域知识的颗粒状结 构。 定义2 3 令x u ，当x 能够用属性予集r 确切地描述( 即属性子集r 所 确定的u 上的不分明关系的并) 时，称x 是可定义的，否则称z 是不可定义的。 r 可定义集也称作精确集，r 不可定义集也称为非精确集或r 粗糙集( 在不发 生混淆的情况下也简称为粗糙集) 。 定义2 4 假设给定知识库k = ( u ，r ) ，对于每个子集x e u 和一个等价关系 r i n d ( k ) ，我们可以根据r 的基本集合的描述来划分集合，为了衡量基于 重庆邮电大学硕士论文 第二章理论基础 尺的基本集合的描述y ，精确地说明x 中对象的隶属度情况，我们便用下近似 集与上近似集这两个概念，它们分别定义如下： 下近似集：足( x ) = u r l ( u 1 1 n d ( r ) a y t x ) ， 上近似集：r - ( x ) = u r i ( r u i ，d ( 月) r n x 中) 。 也可以表示为： 足( x ) = x i ( x e u i x 。z ) ， r 一( ) = 扛l ( x u 【x k n x d ) a 定义2 5 集合巩( x ) = r 一( x ) 一足( ) 称为x 的尺边界域，集合 p o s r ( ) = r ( x ) 称为x 的尺正域，集合n e g r ( x ) = u 一足( x ) 称为x 的r 负 域。 r 一( ) 是根据知识r ，u 中所有一定能够归入x 的元素的集合，即所有包 含于x 的，：的并。r 一( x ) 是根据知识r ，u 中一定能和可能能够归入x 的元素 的集合，即所有与x 的交不为零的的并。b n 。( x ) 是根据知识r ，u 中即不 能肯定归入集合x ，又不能肯定归入集合的元素构成的集合。p o s 。( x ) 是 根据知识r ，u 中所有一定能归入集合x 的元素构成的集合。n e g 。( x ) 是根 据知识r ，u 中所有不能确定一定归入集合x 的元素的集合。图2 1 为粗糙集 概念的示意图。 l、 3 z 。一： 、 l ， 图2 1 粗糙集概念示意图 b n r o x 、 x 足( ) r 一( x ) 重庆邮电大学硕士论文第二章理论基础 2 2 2 知识表达系统，决策表 知识表达是智能信息系统的关键。所谓知识获取，就是要从大量的原始数 据信息中分析发现有用的规律信息，即是将知识从一种原来的表达方式( 原始 数据表达形式) 转换为一种新的目标表达形式( 人类或者计算机便于处理的形 式，如逻辑规则等) 。基于r o u g h 集理论的知识发现，主要是借助于信息表这 样一种有效的数据表知识表达方式。 定义2 6 信息表系统s = ( u ，r ，v ，f ) ，其中，u 是对象的集合，也称为论域， 尺：c u d 是属性集合，子集c = f qj i = l 。，m 和d = f d ) 分别称为条件属性和 决策属性集，u = x ix 2 ，x n ) 是论域，a i ( x ，) 是样本x 声属性q 上的取值，对 于每一个r e r ，咋是其所有可能的取值，v = u 。一，f ：u r 一矿是一个信 息函数，它指定u 中每一个对象x 的属性值。 定义2 7 给定信息表s = ( u ，r ，矿，f ) ，u i i n d ( c ) 和( ，i i n d ( d ) 分别为论域 u 在属性集c 和d 上形成的划分，条件类定义为：巨( u i i n d ( c ) ) ，其中 i = l ，2 ，m ，m 为条件类的个数；决策类定义为：z u i i n d ( d ) ) ，其e e ，= l 2 ，n ，以为决策类的个数。 定义2 8 在信息表s = ( u ，尺，v ，f ) 中，若某个条件类的每个样本都有相同的 决策值，则称这个条件类中的任一样本为确定性记录；若某个条件类的样本有 不同的决策值，则称这个条件类中的任一样本为不确定性记录。 定义2 9 对任意一个信息表s = ( u ，r ，矿，f ) ，如果它的所有条件类都是一致 的，则称s 为确定信息表，否则称s 为不确定信息表。 2 2 3 约简与核 在r o u g h 集应用中，我们经常要在保持知识库中初等范畴的情况下消去冗 余范畴，进行知识简化。完成知识简化的基本工作是利用约简和核这两个基本 概念来进行的。 令r 为一等价关系族，且r r ，如果i n d ( r ) = i n d ( r 一 r ) ，称r 为r 中 可省略的，否则r 为r 中不可省略的。 定义2 1 0 对于属性子集p r ，若存在q = p 一，q p ，使得 h v d ( q ) = i n d ( p ) ，且q 为最小子集，则称q 为尸的约简，用r e d ( p ) 表示。 一个属性集合p 可能有多种约简。 定义2 “尸中所用约简属性集中都包含的不可省略的集合，即约简 r e d ( p ) 的交集称为p 的核，记作c o r e ( p ) 。它是表示知识必不可缺少的重要 6 重庆邮电大学硕士论文 第二章理论基础 属性集。 可以看出，核这个概念的用处有两个方面：首先它可以作为所有约简的计 算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次可以解 释为在知识化简时它是不能消去的知识特征部分的集合。因此，核属性的计算 往往是信息约简过程的出发点和关键1 3 ”。计算约简的复杂性随信息表的增大呈 指数增长，是一个典型的n p 完全问题，当然实际中没有必要求出所有的约简。 2 2 4 规则集 定义2 1 2 令s = ( u ，r ，v ，f ) 表示一个决策表，且b c 。由s 产生的一个规 则集为表示为： f = 彳；，正；，l ，： ， 其中： 眉= 口号d 皓c ，d e d ，( i = 1 ，l ，) ，表示，中规则的数目，在名中，如果某些规则中的某个属性值被约简掉 那么在这些规则中被约简掉的属性表示为“”。 2 3 可辨识矩阵 可辨识矩阵是由波兰华沙大学著名的数学家s k o w r o n 教授提出的。根据可 辨识矩阵的定义，当两个样本( 实例) 的决策属性取值相同时，它们所对应的 可辨识矩阵元素的取值为o ：当两个样本的决策属性不同且可以通过某些条件 属性的取值不同加以区分时，它们所对应的可辨识矩阵元素的取值为这两个样 本属性值不同的条件属性集合，即可以区分这两个样本的条件属性集合；当两 个样本发生冲突时，即所有条件属性取值相同而决策属性的取值不同时，则它 们所对应的可辨识矩阵中的元素取值为空集。 定义2 1 3 令信息表系统s = ( u ，r ，矿，厂) ，其中，u 是对象的集合，也称为 论域，r = c u d 是属性集合，子集c = q i i = 1 ，2 ，朋) 和d = d 分别称为条 件属性和决策属性集，u = x 。，z ：，矗 是论域，q ( x ，) 是样本x 声属性q 上的 取值。c 。( f ，) 表示可辨识矩阵第f 行- ，列的元素，则可辨识矩阵c 。定义为： c 。( t ，) = 0 qi q c n 吼_ ) ：d d i ；! d d ； ，i x =i 工1 其中f ，j = l 2 ，h 重庆邮电大学硕士论文 第二章理论基础 显然，可辨识矩阵是一个依主对角线对称的矩阵，在考虑可辨识矩阵的时 候只需要考虑其上三角( 或下三角) 部分就可以了。 可辨识矩阵元素中是否包含空集元素可以作为判定信息表系统中是否包含 不一致( 冲突) 信息的依据。 2 4 粒计算理论基础 人脑对问题的认知可以用三个基本概念来描述，即粒化( g r a n u l a t i o n ) 、重 组( o r g a n i z a t i o n ) 和因果推理( c a u s a t i o n ) i i , ”】，“粒化是把整体分解为部分， 重组是把部分合并为整体，而因果推理指的是促使这种分解与合并的原因以及 它们会导致的结果”。对于粒计算的研究，很大程度上是因为它模拟了人脑认识 和解决问题的过程。粒计算的主要模型有包括：集合论和区间分析、模糊集、 粗糙集、商空间理论、概率论等等。对于这些模型已有了许多研究和应用，特 别值得注意的是，它们大多是独立发展起来的，彼此之间并没有多少相互影响， 但它们最终都统一于粒计算这个框架之下，这也从另一方面表明粒计算本身是 一种基础的问题求解方法。 2 4 1 粒计算的基本问题 粒计算中存在许多基本问题，如空间的粒化、粒的描述、粒子之间的关系 和使用粒的计算。空间的粒化是指将对象空间分解为许多子空间，或是基于有 用的信息和知识将空间中的个体聚集成不同的类，这些类我们称为粒，粒中的 元素可以对应概念的实例。因为概念生成的目的之一是对具有某些概念的粒的 表示、特征化、描述和解释，而知识发现和数据挖掘的一个重要方面就是在颗 粒之间建立关联和因果等联系，因此可以把粒计算机制与概念生成、知识发现 和数据挖掘联系起来。 虽然目前对什么粒计算还没有明确的定义，也还没有一个统一的模型来统 一诸多粒计算的具体模型。但是人们对粒计算基本问题都有一个大致的想法， 即粒计算可以从两大方面来进行研究：粒子的构造和使用粒子的计算。前者处 理粒子的形成、表示和解释，后者处理在问题求解中粒子的运用。同时粒计算 的研究可以从两个同等重要的层面展开：语义和算法。 通俗地讲，粒计算的语义研究侧重“为什么”这类问题，侧重于对粒的解 释，如为什么两个对象会在同一个粒之中? 不同粒子之间存在怎样的关系? 一 般来讲，每个粒中的元素满足不可分辨关系、相似性、邻近性或者功能性， 同时信息粒化也基于这些关系。由于对论域不同的分类标准( 等价、相容、泛 重庆邮电大学硕士论文 第二章理论基础 序、异同等关系) 可能会形成不同的粒空间，并具有不同的粒子结构，所以有 必要研究这些关系的语义解释，如相似性( c l o s e n e s s ) 、关联性( a s s o c i a t i o n ) 、依赖 性( d e p e n d e n c y ) 。粒子结构的不同对论域的任一子集的近似集和对这些基本粒的 操作会有所不同，并导致算法的时间、空间复杂度有很大差别，因此进行信息 粒化时要结合实际需要。 粒计算的算法研究关注“如何”这类问题，即如何进行粒化和如何进行基 于粒的计算。很有必要研究粒计算的方法学和工具( 如近似、推理等机制) 。对 粒子的分解与合并机制的研究，是构建任何粒度体系结构的本质要求。 2 4 2 粒的概念和层次结构 直观地讲，粒的大小描述了其特异性，粒中元素越多，它就越抽象越通用： 反之则越抽象。 信息粒化的层次取决于所要求解的问题。信息粒可视为概念的构造块，用 来观察和描述问题并同外界交互，从而决定了粒度的层次。在此，我们把信息 粒视为一种执行有效计算的机制，在问题求解中选择最有用的粒度层次。 粒计算的研究包含一系列重大的方法学和算法上的问题。在粒计算中，信 息粒在粒度的不同水平出现，通常把最相似的粒聚集为一层。信息粒度表明不 同粒化模型的使用在某个特定的粒度层次上是相关的。如系统建模分为三层， 最底层处理最细的粒度数字，它使用不同的方程式、回归模型或神经网络 等数值模型；中间层处理较大的信息粒( 包含许多个体元素) ；最上层是基于符 号的处理，它基于概念( 有限状态机、p e t r i 网、连接图等) 。 众多的粒计算模型引发了一个更基本的问题：如何评估这些构造模型呢? 一般来讲，任何评估标准都和信息粒的粒度有关，评估和模型测试应该和所设 计模型相符合，即评估使用的信息粒在特异性( 粒大小) 上和所评估模型构建 的信息粒相比应相同或更小。 不同的粒度世界很少不和外界交互而独立存在。可以设想在不同的粒世界 中存在不同的a g e n t s ，每个a g e n t 对应不同的粒计算环境，a g e n t 之间相互发 生作用( 协作和竞争) 。这样，各个粒度世界之间的通信变为这些a g e n t 之间的 通信。 2 4 3 粒计算中存在的问题 粒计算中存在的下述待解决的典型重要问题，有待进一步探索解决： ( 1 ) 信息粒的解析表示理论和方法，即用形式化的数学理论工具来描述和表 9 重庆邮电大学硕士论文 第二章理论基础 达粒计算的处理对象信息粒。 ( 2 ) 研究信息粒的粒度描述方法。这对我们洞察信息粒化的本质至关重要。 ( 3 ) 考虑不同粒化方法的融合来更好地求解复杂问题。如商空间理论和 r o u g h 集都是基于等价关系的，将商空间理论和r o u g h 集方法结合，将 微观和宏观的粒计算统起来，构成一个更加系统的粒计算理论和方 法。 ( 4 ) 考虑采用非等价关系粒化形成粒，并讨论此时粒化结构之间的关系。如 扩展r o u g h 集理论产生的粒度和f u z z y 集、经典r o u g h 集和商空间理论 的关系。 ( 5 ) 层次化的粒度结构和规则的关系，在不一致分类问题中的表达和解释。 ( 6 ) 扩充不同的粒计算模型算法。 ( 7 ) 粒的分解和合成技术( 静态和动态) 的研究。 ( 8 ) 除了商空间理论外，现有的许多研究都没考虑到空间拓扑结构对粒化的 影响，在这方面的研究会得到许多有价值的成果。 ( 9 ) 不同粒度水平和不同粒计算框架下系统间的通信机制( 编码和解码) 。 2 5 信息系统的粒化 定义2 1 4 令信息系统s = ( u ，r ，v ，厂) ，其中r = c u d 是属性集合， u = 五，x 2 ，矗) 是论域，也称为样本空间，对于任意r r ，v ，称( ，v ) 为 信息系统s 上的一个原子公式，简称公式。 显然，如果和妒是s 上的公式，则_ 1 妒、妒 妒、v 妒、妒寸妒也是s 上的 公式。 定义2 1 5 如果样本x 满足s 上的公式，则有：x i _ 。，或简写为x l = ， 集合m s ( 庐) = x v l x 是公式在s 上的含义，也称为公式在s 上的解释 空间，m s ( 矿) 可以简写为m ( ) 。 ( ) 是所有满足公式妒的样本的集合。 如果砂和妒是s 上的公式，则下列性质显然成立： ( 1 ) m ( 一声) = u m ( ) ( 2 ) m ( 妒妒) = m ( 庐) n 埘( p ) ( 3 ) 所( 矿v 妒) = 所( 矿) u 所( 妒) ( 4 ) 州( 妒弓妒) = 一川( 庐) u 肌( 妒) 根据前述定义，我们提出了信息系统s 中的，粒子和粒化的定义。 定义2 1 6 令信息系统s = ( u ，尺，v ，f ) ，其中r = c u d 是属性集合，对任意 公式= ( q ) l ( ) ，其中，i = 1 ，l ，l c i ，c t , l ，c le c ，、，l ，飞6 v ， 0 重庆邮电大学硕士论文 第二章理论基础 肌( ) = x u i x 卜 是矿在s 上的解释空间，称m ( 妒) 为由公式妒在s 上划分的 一个粒子，简称粒子；称i 为公式西的长度。 定义2 1 7 令为信息系统s 上的公式，其长度为i ，称粒子集合： 甲：= 研( 硝) ) ，l ， 川( 蟛) ) ，l ， m ( 硝) ) ， 为对s 的第i 层分解，其中，_ ，= i , l ，h ，以是s 上所有长度为i 的公式的个 数。 定义2 1 8 对决策表s = ，其中r = c u d ，和妒是s 上的公式， 如果任意一条满足公式的样本x ，都一定满足公式妒，那么称j 伊为s 上的 一条规则。规则的可信度因子定义为： 爿s ( j p ) = k 丛吊；1 生。 很明显，根据定义2 1 6 ，在任意层次上对s 的分解，都会包含论域u 中的 所有样本。因为在任意层次上，决策表中的任何一个样本都至少满足一个公式。 每一条公式所划分的粒子中的样本，从这条公式的角度来看，是不可分辨 的。而属于同一层次的粒子，都是由长度相同的公式所划分的，由此可以认为， 信息系统s 上，隶属于同一层次的粒子，拥有相同的粒度。因此，通过这样的 划分，我们得到了一种层次化的粒化信息系统的方法。 在下一章中我们将详细描述这个粒化模型。 2 6 不确定性度量 王国胤教授等人给出了一种决策表信息系统的不确定性度量方法【i o , n l ，基 于这种方法，我们可以在没有领域先验知识时，对不确定性信息进行处理。下 面给出这种不确定性度量方法的定义。 定义2 1 9 给定决策表s = ，r = c u d ，c 和d 分别为决策表 的条件属性和决策属性，u l i n d ( c ) 和u 1 1 n d ( d ) 分别为论域u 在属性集c 和 d 上形成的划分：条件分类定义为：e u i i n d ( c ) ，i = 1 , l ，m ，m 为条件分 类的个数；决策分类定义为：x ，u i i n d ( d ) ，= 1 , l ，n ，”为决策分类的个 数。 对于决策表s = ，r = c u d ，c 和d 分别为决策表的条件属性 和决策属性，分类巨u i i n d ( c ) ( i = 1 , l ，m ) 为条件分类，x j u 1 1 n d ( d ) ( ，= l ，l ，”) 为决策分类，则对于任意条件分类巨对应有集合正，满足： 7 ：= m a ) ( e n x j l x j u i 刷d ( d ) 。 重庆邮电大学硕士论文 第二章理论基础 因此对于各条件分类集合巨，l ，e ，l ，e 都分别存在对应的五，l ，l ，l ，瓦。 定义2 2 0 给定决策表s = ，e l ，l ，e ，l ，已是所有的条件分类， 那么决策表整体确定性定义为： | 7 ：| 胪钎； 决策表整体不确定性定义为： | 7 ：l 。1 一雌划一订。 定义2 2 1 给定决策表s = ，r = c w d ，c 和d 分别为决策表 的条件属性和决策属性，分类e u l i n d ( c ) ( i = 1 ，l ，m ) 为条件分类， u i i n d ( d ) ( ，= 1 ，l ，h ) 为决策分类，任意条件分类ee u i ， ，d ( c ) 对于 决策属性分类的确定性程度定义为： r ( 剐= m a x l e , r 、x j l i e , i l x j u i n d ( d ) l ； k ( 巨) ，l ，r ( 邑) 是条件分类对决策分类的确定性程度，则决策表局部最小 确定性定义为： q = m i n x ( e , ) ，l ，r ( e ) ： 决策表局部最大不确定性定义为：吼。= 1 一q 。 定理2 1 由决策表s 得到的规则集f ，在决策表能够充分反映领域样本数 据的情况下，对从决策表中获取的规则知识进行测试的最大可能正确率叩等于 决策表整体确定性雎，即有： 吲 栌旷钎 其中m 为决策表条件分类数。 定理2 2 对决策表s = ，其中r = c w d ，我们取决策表局部最 小确定性为阈值来控制规则集f 的生成，用，对样本数据集进行测试，理论上 可以得到对样本数据集测试的最大正确率。 定理2 2 的证明【1 0 1 ： 首先根据条件属性集c 计算决策表s 的条件分类：啄。) u i z n d ( c ) ， k = l ，l ， u l m d ( c ) i 。 重庆邮电大学硕士论文 第二章理论基础 对于任意气日对应存在，c ) = m a x 铱，c ) n z ke u i n d ( d ) ，且对任意 条件分类气川，存在u i i n d ( d ) ，并满足： e l k , c ) n _ = m a x c ) n 墨i 置u i i n d ( d ) = 墨 ) 。 因此1 c ) n i i 啄q j _ i 碌q i i e , 。q i 是规则d ( 铱q ，c ) - ，d e s ( _ ，d ) 的可信度因子，其中，d e s ( 气，c ) ，c ) 为用条件属性集c 来表示条件分类铱q 的 公式，d e s ( ，d ) 为用决策属性集d 来表示决策分类的公式。 由此可知： ，m ，l = r ( ) 。 又因为： 铲m i n 盯( 铴) ，l ，k ( q ) ，l ，r ( 眺肛) ) ， 所以陬。，i i e , 删i - o c 因此，我们可以得到规则d e s ( 纠，c ) 哼d 船( 乃，d ) 墨托) f 1 臣) i ，其中， l 碌c ) l 1 功l 是该规则的可信度因子。 如果用这条规则测试乓托l 中的数据，可得到正确结果的样本集合为 ) = m a x 气qx , i x , u i i n d ( d ) 。 瓢r 叩：犁。 2 7 小结 r o u g h 集理论主要应用在对不完整、不精确信息的表达与处理上，它从新 重庆邮电大学硕士论文第二章理论基础 的视角出发对知识进行了定义，把知识看作是关于论域的划分，并引入代数学 中的等价关系来讨论知识，能有效地分析和处理不精确、不一致、不完整等各 种信息，并从中发现隐含的知识，揭示潜在的规律，已经被广泛应用到很多领 域。本章第一部分主要描述r o u g h 集理论的一些基本概念。 粒计算作为一种新颖的描述或解决问题的方法，已经被应用很多领域。它 将复杂问题划分为一系列更容易管理和更小的子问题，使人们更好地领悟问题 的本质并提供一种更好的解决方案，避免陷入不必要的细节中去。本章第二部 分描述了粒计算理论的理论基础、思想方法及其存在的问题等等。 在本章的第三部分中，我们讨论了在决策表信息系统中，粒子的定义以及 表示，并提出了一种层次化分解决策表信息系统的方法，这一部分内容将在第 三章中进行更加详细的论述。 对于不确定性信息系统，在没有领域先验知识条件下的主动式学习是机器 学习领域中的一个难题，又是决定系统性能的关键之一，我们在第四部分中给 出了一种度量其不确定性，以及处理不确定性决策表的方法。 重庆邮电大学硕士论文第三章信息系统的粒化及知识获取模型 3 1 引言 第三章信息系统的粒化及知识获取模型 粒计算思想是一种基于不同粒度层次看待客观世界的方法论。以粒计算的 观点来看，人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 中的问题求解是指将整体分解 为局部直至最基本的、能直接求解的局部问题，随后将各局部问题的解合并， 从而得到整体问题的一个解。人类的问题求解本质上来讲也是采用的粒计算思 想。同时采用粒计算观点处理问题具有简化问题、减小计算代价等优点 3 2 决策表信息系统的粒化模型 粒计算的思想无处不在，信息粒子存在于现实世界中，是对现实的抽象。 粒子由一系列元素组成，这些元素之间满足不可分辨关系和某种程度上的相似 性。人类在解决和处理大量复杂问题时，往往凭借自己以往的经验、感觉或者 专业背景知识，按问题各自的特征和性能将复杂信息分成若干简单的部分( 粒 子) 。这种处理过程，就称为信息粒化( i n f o r m a t i o ng r a n u l a t i o n ) 。信息粒化旨 在建立基于外部世界的有效的并以用户为中心的概念，同时简化我们对物理世 界和虚拟世界的认识。 信息粒化在本质上是分层次的。只有从不同层次、不同角度来分析问题， 才可以得到对问题更好的解决。信息粒化的层次依赖于我们要处理的任务和决 策生成的需要。比如人们根据不同的需要将时间粒化为年、月、日、小时、分、 秒。同样的，人们在描述待求解的问题时，为了简化问题，一般不是用精确的 数字( 小粒子) ，而是选择用形式化语言、规贝j j ( i f t h e n ) 等( 大粒子) 来描述问 题。在图像、信号处理和系统建模中，信息粒化的观点更为普遍。在地理信息 系统中需要对世界地理做描述时，如果只是做比较粗的了解，那就使用大的信 息粒，如大陆、国家和大洋。这是我们在从一个比较高的抽象层次处理问题。 如果需要了解更多的信息，那就使用较小的粒，如地区、省、海。如果还需要 进一步了解细节信息，那可以使用更细的粒，如城镇、湖泊、森林等。 一个决策表信息系统是由满足条件的样本所组成。用粒计算的思想来考察 一个决策表，可以把每一个样本看成是一个小粒子。根据定义2 1 6 和定义2 1 7 ， 利用不同长度的公式，可以在不同层次上将这个决策表划分为粒度不同的粒子。 同样长度的公式所形成的粒子处于相同的层次中。所有这些层次中的粒子构成 重庆邮电大学硕士论文第三章信息系统的粒化及知识获取模型 了描述这个信息系统的粒空间。 这样形成的粒空间是一个多层次、立体的结构。在解决不同问题的时候， 可以到最合适的层上寻找答案。在一定程度上简化了问题求解过程的同时，保 证解决方案的准确度。 3 2 1 粒化过程 为了描述的方便，我们将通过一个例子来讲解决策表信息系统的粒化过程。 表3 1 是这个例子中使用的决策表。该决策表有条件属性c l 、c 2 、c 3