（电路与系统专业论文）粗糙集约简算法在知识发现中的研究与应用.pdf

摘要 摘要 、娅文的主要工作是了解知识发现的体系结构，学习粗糙集理论的基本概念，研 究基于粗糙集理论的约简算法在知识发现领域中进行数据约简和离散化两个方面 存在的问题，开发用于粗糙集理论算法研究的实验平台。 本文通过在数据约简方面的研究，提出了对利用属性频率函数的启发式约简算 法的改进算法h o r a f a s v d m 算法，以及这个算法的增量版本 h o r a f a i a 算法。同时根据实验讨论了该类算法对于无核数据集所存在的需要 大量时间求约简的问题，在这个问题的探讨中，本文结合上述利用属性频率函数 的启发式约简算法提出了一个可以实现算法自适应的模型h o r a f a - - a 。 在离散化方面，将属性频率函数引入到n s 算法中，提出了相应的约简算法， 同时为了解决启发式约简算法在n s 算法中存在的问题提出了新的概念候选核 和基于候选核的b c c 算法。 最后介绍在这次研究工作中根据一些知识发现的原型系统开发的用于粗糙集 算法研究的平台r s d m e s 系统。 关键词：知识发现粗糙集约季多氢化 a b s t r a c t a b s t r a c t t h ew o r ko ft h i sp r e s e n tp a p e rm a i n l yi n c l u d e st h ei n v e s t i g a t i o no ft h es t r u c t u r eo f k d d s y s t e m ，t h es t u d yo f t h eb a s i cc o n c e p t so f r o u g hs e tt h e o r y ，t h er e s e a r c ho f t h e q u e s t i o n si nt h eh e u r i s t i cr e d u c tf i n d i n ga l g o r i t h m sb a s e dt h er o u g hs e tt h e o r yu s e di n t h ed a t ar e d u c t i o na n dt h ed i s c r e t i z a t i o ni nt h ef i e l do fk d d ，a n dt h ed e v e l o p m e n to f t h es y s t e mw h i c hi su s e dt os t u d yt h ea l g o r i t h m so f t h e r o u g h s e t t h r o u g ht h es t u d yi n t h ed a t ar e d u c t i o n ，t h i s p a p e rp r e s e n t s an e wr e d u c t i o n a l g o r i t h mn a m e dh o r a f a - - s v d ma n da ni n c r e m e n t a la l g o r i t h mo ft h eh e u r i s t i c o p t i m a lr e d u c tf i n d i n ga l g o r i t h mo ft h ef r e q u e n c i e sf u n c t i o nn a m e dh o r a f a - - i a a c c o r d i n g t ot h er e s u l t so ft h ee x p e r i m e n t ，t h e p a p e r d i s c u s s e st h eq u e s t i o nt h a ti tt a k e s t o om u c ht i m ei nt h ef i n d i n gr e d u c tw h e nt h i sk i n do ft h ea l g o r i t h mi su s e di nt h ed a t a s e tw i t h o u tc o r e a na d a p t i v em o d e lh o r a f a - - ai sc o n s t r u c t e dw i t l lt h eh e u r i s t i c o p t i m a l r e d u c tf i n d i n g a l g o r i t h mp r e s e n t e di nt h ep a p e r i nt h ef i e l do f d i s c r e t i z a t i o n ，f r e q u e n c i e sf u n c t i o ni si m p o r t e dt ot h en sa l g o r i t h m a n dt h en e wr e d u c tf i n d i n ga l g o r i t h ma r es h o w n an e w c o n c e p t c a n d i d a t ec o r e a n dan e w a l g o r i t h mb a s e do n i ta r ep r e s e n t e dt os o l v et h eq u e s t i o ni nt h en s a l g o r i t h m w i t ht h eh e u r i s t i cr e d u c tf i n d i n ga l g o r i t h m a tl a s t ，t h r o g l lt h es t u d yo fs o m e p r o t o t y p es y s t e m so f k d d ，t h i sp a p e r i n t r o d u c e s a ne x p e r i m e n ts y s t e n l _ r s d m e sb u i l ti nt h er e s e a r c hw o r k ，w h i c hi su s e dt os t u d y t h ea l g o r i t h mo f r o u g hs e t k e y w o r d ：k d dr o u g h s e tr e d u c t i o nd i s c r e t i z a t i o n 第一章绪论 第一章绪论 1 1 研究工作的背景 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 及其核心技术 数据挖掘( d a t a m i n i n g ，d m ) 技术是在应用的推动下，融合了人工智能，数据 库技术的一个新兴的跨学科的研究领域，具有较为广泛的应用前景1 6 , 3 4 1 。 粗糙集( r o u g hs e t ，r s ) 理论是波兰华沙大学的数学家p a w l a kz 教授于1 9 8 2 年提出来的一种处理模糊和不精确知识的数学工具【1 9 , 2 0 , 3 4 - 3 6 , 3 q 4 们。八十年代末，随 着理论的不断完善和数据挖掘的兴起，粗糙集合理论引起了世界各国学者的注意。 而约简既是知识发现中数据削减中重要的一步，又是粗糙集中非常重要的一 个研究课题1 3 ”。 本节首先介绍知识发现和数据挖掘的发展和研究状况，然后再简单的介绍目 前粗糙集理论的情况。 1 1 1知识发现和数据挖掘的发展及研究状况 ( 一) 知识发现和数据挖掘的起源 j o h n n a i s b e t t 在大趋势一书中曾这样感叹：“w ea r e d r o w n i n g i n i n f o r m a t i o n ， b u ts t a r v i n gf o rk n o w l e d g e ”。这句话是对知识发现和数据挖掘起源最好的表述。 在八十年代，人们就估算全世界的数据总量2 0 个月就会翻一番，进入九十 年代后，数据量会增长的更快。在这样的数据增长速度下，“信息爆炸”和哮据过 剩”( d a t a g l u t ) 成为了当今数字化社会面临的巨大挑战。 一目前人们用到的主要是数据库的存储功能，传统的数据分析手段有其自身的 局限性，只能以简单的统计方法进行数据分析，这样获得的数据仅仅是表层信息， 因此缺乏挖掘数据背后隐藏知识的手段。人们迫切感到需要新的技术和工具以便 智能的、自动的对大量的数据进行分析，从数据中抽取有价值的信息和知识。 进入九十年代后，数据库技术的一个新领域数据仓库( d a t aw a r e h o u s e ) 【1 3 】以及人工智能领域中的一个分支机器学习( m a c h i n el e a r n i n g ) 的研究取得 了很大进展。在这两门学科的相互融合下，数据库中的知识发现( k n o w l e d g e d i s c o v e r y i nd a t a b a s e ，k d d ) 及其核心技术数据采掘( d a t a m i n i n g ，d m ) 就 这样应运而生了。数据库技术的日益成熟和数据仓库的发展为知识发现和数据挖 掘提供了发挥的平台，而机器学习又为数据挖掘提供了大量的方法。因此，知识 发现和数据挖掘是应用需求推动下跨学科发展的产物口。 ( 二) 知识发现和数据挖掘的发展概况 粗糙集约简算法在知识发现中的研究与应用 目前，知识发现不仅被许多研究人员看作是数据库系统和机器学习方面一个 重要的研究课题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。 1 9 8 9 年8 月在美国底特律的第1 1 届国际人工智能联合会议的专题讨论会上 召开了第一届k d d 的w o r k s h o p ，1 9 9 1 、1 9 9 3 和1 9 9 4 年又接着举行k d d 专题讨 论会。从1 9 9 5 年开始，每年都举办一次k d d 国际会议。从1 9 9 7 年开始，k d d 也拥有自己的专门杂志( ( k n o w l e d g ed i s c o v e r y a n dd a t am i n i n g ) ) 。1 9 9 5 年以来， 国外在知识发现和数据挖掘方面的论文非常多，已形成了热门研究方向【3 6 】。 ( 三) 知识发现和数据挖掘的概念 知识发现这个术语出现在1 9 8 9 年8 月美国底特律召开的第1 l 届国际人工智 能联合会议的专题讨论会上，至今有多种定义，公认的是1 9 9 6 年，f a y y a d 、 p i a t e t s k y - s h a p i r o r 和s m y t h 提出来的1 6 j ： k n o w l e d g ed i s c o v e r yi nd a t a b a s e si st h en o n t r i v i a lp r o c e s so fi d e n f i f y i n gv a l i d ， n o v e l ，p o t e n t i a l l y u s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n s i nd a t a 数据库中的知识发现是从数据( 集) 中识别出有效的、瓶颖的、潜在有用的， 以及最终可理解的模式的高级( 非平凡) 过程。 数据挖掘是进入九十年代后才提出来的，技术上的定义为从大量的、不完全 的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先 不知道的、但又是潜在有用的信息和知识的过程。 知识发现和数据挖掘由于是新兴的、来自各种不同领域的交叉性学科，因此 有很多不同的术语名称，本文在不易混淆的情况下将不区别地使用它们。 ( 四) 数据挖掘的任务 数据挖掘作为知识发现的核心部分，它被研究得最多。根据发现知识的不同， 数据挖掘任务归纳为以下几类1 3 3 j ： ( 1 ) 特征规则从与学习任务相关的数据中提取出关于这些数据的特征式， 这些特征式表达了该数据集的总体特征。例如从病状中提取疾病的特征规则。 ( 2 ) 区分规则发现或提取要学习数据的某些特征或属性，使之与要进行对 比的数据能够区分开来。例如，通过对某些疾病与其它疾病的症状比较，提取出 该疾病相对于其它疾病的区分规则，利用这些规则可以区分出该种疾病。 ( 3 ) 分类规则用一个分类函数或分类模型( 也常称为分类器) 把数据库中 的数据项映射到某个预定义的类。分类和回归都可用于预测，它们的区别是，分 类的输出是离散的类别值，而回归的输出则是连续值。分类器的构造方法有统计 方法、机器学习方法、神经网络方法等，本文提到的粗糙集是一种新兴的方法。 ( 4 ) 关联规则关联规则是反映一个事件和其他事件之间依赖或关联的知 识，表达成x j y 形式的规则，解释为满足x 的数据库元组很可能会满足y 。它 被广泛的应用于交易数据分析，是目前在数据挖掘中研究的比较成熟的一类问题。 - r l ， 第一章绪论 ( 5 ) 聚类通过搜索并识别一个有限的种类集合或簇集合，从而描述数 据。也就是识别出一组聚类规则，将数据分成若干类，即实现“物以类聚”。 ( 6 ) 预测主要有两方面的任务，一方面是通过对数据的分析处理，估 计一组数据中某些丢失数据的可能值或一个数据集合中某些属性值的分布情况； 另一方面，根据时间序列型数据，由历史和当前的数据去推测未来的数据。 ( 7 ) 变化和偏差分析探测数据现状、历史记录或标准之间的显著变化和偏 离，偏差包含了潜在的知识。如分类中的反常实例，数据聚类外的离群值等。 所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升， 从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 ( 五) 数据挖掘的方法和技术 目前存在很多数据挖掘方法或算法，有必要对这些方法进行分门别类，下面 对数据挖掘中主要的技术进行分类介绍【1 6 】。 1 分类算法分类算法这具有相当多的成员。这里只讨论常见的几种算法， 即决策树，a q ，b a y e s ，s v m ，神经网络等。粗糙集方法将在后面详细介绍。 ( 1 ) 决策树：最有影响和最早的决策树方法是q u i n l a l l 的i d 3 方法，它对越 大的数据库效果越好，i d 3 及后续版本c 4 5 ，c 5 是使用最为广泛的决策树方法1 2 ”。 此外还有采用基于最小距离的g i n ii n d e x 标准的c a r t 算法，以及f 统计，c s e p ， i m p u r i t y ，m d l 等算法。而在超大规模数据集中还有采用预排序技术和m d l 剪 枝的s l i q 算法，引入了并行方式的s p r i n t 算法等。 ( 2 ) a q ：它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。比较 典型的有m i c h a l s k i 的a q l l 方法。洪家荣在a q l l 的基础上增加了渐近学 - 3 ，构 造学习和近似推理等功能，形成了a q l 5 算法，这是一个比较成熟的覆盖算法。 其后，洪家荣还提出了改进的a e l ，a e 9 算法。 值得一提的是，a q 算法和粗糙集理论有许多共同之处0 0 ，a q 中覆盖正例的 复合对应于粗糙集理论的下近似或者说是正区域。粗糙集中区分函数的化简结果， 等同于a q 的最大复合。但是，粗糙集有坚实的理论基础和对概念进行近似的能 力，因而应用范围更广。 ( 3 ) b a y e s ：b a y e s 方法是利用贝叶斯公式将先验信息与样本信息综合，得 到后验信息。在数据挖掘中主要有两种方法，即n a i v e - b a y e s 方法和b a y e s 网络。 n a i v e b a y e s 方法直接利用b a y e s 公式进行预测，此方法简单易行并且具有较好的 精度。b a y e s 网络是一个带有概率注释的有向无环图，适合用来分析大量变量之 间的相互关系。 ( 4 ) s v m ： s v m 是v a p n i k 根据统计学习理论提出的一种新的学习方法， 近年来得到了国际学术界的重视。s v m 的最大特点是根据v a p n i k 结构风险最小 化准则，尽量提高学习机的泛化能力，即由有限的训练集样本得到的小的误差能 粗糙集约简算法在知识发现中的研究与应用 够保证对独立的测试集仍保持小的误差。另外由于s v m 算法是一个凸优化问题， 因此局部最优解一定是全局最优解。而且s v m 的复杂度和实例集的维数无关。 ( 5 ) 神经网络：神经网络是一种很好的函数逼近工具，近年来许多学者提 出了从神经网络中提取规则的方法，主要可以分为三类方法：分解法、学习法以 及这两种的折衷方法。分解抽取方法的最大特点是对神经元网络内部的单个节点 ( 隐含和输出) 所表示的概念进行解释，典型的分解算法有s u b s e t 及其改进 m o f n 、k t 和r u l e x 。学习抽取法的基本思想是将训练后的神经元网络看成一 个黑箱，把规则抽取过程看成一个学习过程，主要方法有t r e p a n 和r l 算法。 2 聚类在统计方法中，聚类称聚类分析( c l u s t e r i n ga n a l y s i s ) ，它是多元 数据分析的三大方法之一( 其它两种是回归分析和判别分析) 。它主要研究基于几 何距离的聚类，如欧式距离、明考斯基距离等。聚类方法主要分为平面聚类和层 次聚类。平面聚类方法通过优化一个评估函数把数据集分割成多个部分，最著名 的是k m e a n s 算法；分层聚类在不同层次上对数据进行分割，具有明显的层次性。 传统的统计聚类分析方法还包括系统聚类法、分解法、加入法、动态聚类法、有 序样品聚类、有重叠聚类和模糊聚类等。 3 关联规则的算法 关联规则的经典算法是a p r i o r i 算法【2 j ，a p r i o r i 算法 通过多次迭代来找出所有的频繁项目集，在第k 次迭代过程中找出所有的频繁k 项目集l k 。此后还有利用h a s h 表的d h p 算法，基于兴趣度规则的处理算法等对 a p r i o r i 算法进行改进。 ( 六) 知识发现和数据挖掘的应用和研究状况 知识发现和数据挖掘的兴起不到十年的时间，它仍然处在早期阶段，还有很 多的研究难题和面临的挑战，如数据的巨量性、动态性、噪声性、缺值和稀疏性， 发现模式的可理解性、兴趣或价值性，应用系统的集成，用户的交互操作，知识 的更新管理，复杂数据库的处理等等。 除了研究外，目前也出现了许多知识发现和数据挖掘的产品和应用系统。如 加拿大s i m o nf r a s e r 大学开发的多任务知识发现系统_ d b m i n e r 【l o l ，它的前身 是d b l e a r n ，该系统把关系数据库和数据挖掘集成在一起，以面向属性的多级概 念为基础发现各种知识。m m 公司a l m a d e n 研究中心开发的多任务k d d 系统一 _ q u e s t ”，该系统的目的是为新一代决策支持系统的应用开发提供高效的数据 开采基本构件。目前，在两个大型数据库系统o r a c l e 和s q ls e v e r 的最新版本中 也加入了数据挖掘的组件。可见k d d 和d m 已经得到了业界的极大的关注。 1 1 2 粗糙集的发展和研究状况 ( - - ) 粗糙集的发展概况 第一章绪论5 粗糙集尽管是出现在八十年代的一个理论，而且同时也开发了一些应用系 统，但是由于最初的研究大多是以波兰文字发表的，所以该项研究当时并未引起 国际计算机学界的重视，研究局限于东欧国家。 1 9 9 1 年，p a w l a k 发表了专著( ( r o u g h s e t ：t h e o r e t i c a la s p a c t so f r e a s o n i n ga b o u t d a t a ) ) 【l ，奠定了粗糙集理论的基础，从而掀起了粗糙集的研究高潮。1 9 9 2 年， 在波兰召开了第一届国际粗糙集研讨会，这次会议着重讨论了集合近似的基本思 想及其应用，其中粗糙集环境下机器学习的基础研究是这次会议的四个专题之一。 1 9 9 3 年在加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会议积极推动 了国际上对粗糙集应用的研究。由于这次会议正值知识发现成为热门研究话题， 一些著名的知识发现学者参加了这了次会议，并且介绍了许多应用扩展粗糙集理 论的数据挖掘的方法与系统。1 9 9 6 年在日本东京召开的第五届国际粗糙集研讨会 以及今年在我国举行的研讨会推动了亚洲地区和我国对粗糙集理论与应用的研 究。现在，美国、加拿大、波兰、日本都有粗糙集研究的专门机构【3 ”。 ( 二) 粗糙集的应用和研究状况 由于粗糙集理论可以支持知识发现的多个步骤，如数据预处理、数据缩减、 规则生成等，因此基于粗糙集理论的k d d 系统被认为具有独特的优势 3 6 】。 近几年来，粗糙集合理论已应用于机器学习、知识发现、决策支持与分析、 专家系统、智能控制、模式识别等领域。目前国际上已经开发出了一些基于粗糙 集理论的k d d 系统。如r e g i n a 大学利用粗糙集理论开发的知识发现系统k d d r ，该系统目前被广泛的应用于医疗诊断、电信业等领域f 3 ”。还有美国k a n s a s 大学开发的l e r s ( l e a r n i n g f r o me x a m p l e sb a s e do nr s ) 系统，该系统被应用于 医疗诊断、社区规划、全球气象研究等方面【8 j 。 国外目前在粗糙集领域的研究主要集中在约简的优化算法、粗糙集理论和模 糊理论，粗糙集理论同神经网络理论等其他人工智能技术的结合、粗糙逻辑等课 题上。本文对于约简算法的研究正是粗糙集领域中一个非常重要的课题。 我国在粗糙集领域的研究起步较晚，但我国在这个领域的发展速度很快，目 前中科院、清华大学等研究所和高校已加入到这个领域中，并取得了一定的成果。 1 2 研究工作的内容 本次课题主要有以下几个方面的研究工作： 1 了解知识发现的体系结构，学习粗糙集理论的基本概念，研究粗糙集理论 进行数据约简的算法。 2 通过在区分矩阵和属性频率函数的研究和实验分析，在h o r a f a 算法的 基础上，利用区分矩阵项合并后的统计信息，提出了h o r a f a s v d m 算法，通 粗糙集约简算法在知识发现中的研究与应用 过实验证明这个算法能够明显的减少在大多数数据集中获得约简的时间。 3 在h o r a f a - - s v d m 算法的基础上，提出了h o r a f a 算法的增量算法 h o r a f a m 算法，该算法可以在增量数据集中发现最小或次优约简。 4 通过实验发现导致无核数据集在h o r a f a 算法中需要大量时间的原因是 由于合并无法减少区分矩阵项的数量。针对这个问题提出了一个自适应模型 h o r a f a - - a 模型，该模型通过对原数据集采样，考察区分矩阵项的合并情况， 然后根据具体情况选择相关的合适算法。 5 研究基于粗糙集的连续值属性离散化的n s 算法，将频率函数引入n s 算 法，形成为了b f f 算法，为解决在n s 算法中启发式约简算法会造成某些属性不 能离散化的问题，提出了候选核的概念，同时提出了基于这个概念的b c c 算法。 6 根据目前的一些知识发现的系统模型，在m l c + + 和r s l 的基础上开发 了用于粗糙集算法研究的一个知识发现的原型系统r s d m e s 系统。 1 3 论文的组织结构 本文章节及内容的安排如下： 第一章绪论 概述知识发现和数据挖掘领域的发展和研究情况；介绍粗糙集理论的发展和 目前应用和研究的概况：介绍本次工作及论文的安排； 第二章集合理论和粗糙集基础 介绍集合理论和粗糙集理论的基本概念；介绍粗糙集理论的扩展模型： 第三章约简算法的研究 介绍区分矩阵等重要的概念：介绍对于利用属性频率函数启发的约简算法的 研究情况，在这个算法的基础上提出了改进算法h o r a f a s v d m 算法，同 时给出了这个算法的增量算法h o r a f a - - i a 算法；最后介绍一个针对无核数据 集的，融合h o r a f a 系列算法的自适应模型h o r a f a a 模型： 第四章连续值属性离散化 介绍连续值属性离散化，概述了这方面目前的研究情况：介绍基于粗糙集理 论的n s 离散化算法：介绍将属性频率函数引入到这个算法中形成的约简算法， 以及为了解决启发式约简算法对离散化算法的影响而提出的新概念候选集和 建立在这个算法基础上的算法b c c 算法： 第五章粗糙集数据挖掘实验系统- r s d m e s 介绍在粗糙集算法研究中开发的实验系统r s d m e s 系统； 第六章结束语 对本次工作的总结及以后工作的展望。 第二章集合理论和粗糙集基础 第二章集合理论和粗糙集基础 自1 9 世纪末德国数学家康托为集合论做奠基以来，集合论在一百多年的时间 里，已经成为了数学中不可缺少的基本的描述工具，集合也成为了数学中的基本 概念之- - 3 引。 知识理论的基础概念是分类和范畴，实际上范畴是特征子集对对象的描述，是 给定知识库中可获得的知识。某些范畴在一个知识中是可以定义的，但在另外一 个知识库中却不可定义，粗糙集正是利用近似定义对这些无法定义的范畴进行处 理。 为了更好的理解粗糙集理论的基本概念，这一章首先介绍集合的概念，然后在 集合理论的基础上给出粗糙集的基本概念，最后再介绍一些粗糙集的扩展模型。 2 1 集合理论基础 集合理论是描述离散世界中各种事物的一个很有用的基础，千差万别的事物都 可以用集合理论羽方法加以描述和解释。本节将对集合理论的基本概念和知识的 概念给予介绍【3 9 i 。 2 1 1 基本概念 ( 一) 基本概念和定义 所有的事物都可以在一定的目的下进行分类组合，例如将所有苹果中，红色的 苹果可以看成一个集合，其中的每一个苹果可以看作是这个集合中的一个元素。 因此可得到集合和元素的概念。 定义2 1 ( 集合) ：研究对象按照某一目的或特点进行的组合。 定义2 2 ( 元素) ：集合中的每一个研究对象。 一般用大写的字母表示集合，小写的字母表示元素，如a e a ，表示a 为集合a 中的元素。 集合论中还包括了各种关系。集合之间除了包含与被包含关系外，还有交、并、 差、补运算，分别记为0 量日、4 广忸、a w b 、4 一b 和爿表示。 定义2 3 ( 基数) ：对于一个有限集合4 ，爿中元素的个数即为基数。 基数也是集合论中经常用到的一个概念，用c a r d 臼) 或阻i 表示。 ( 二) 集合关系 在集合理论中，关系是指： 粗糙集约简算法在知识发现中的研究与应用 定义2 4 ( 关系) ；两个不同和相同集合中有序对元素的集合。 对于两个集合4 和b ，其二值关系r 定义为c a r t e s i o n 积a x b 的一个子集，即： 匙，b 。其逆关系定义为从集合b 到集合a 的关系，即如果关系r c a b = ， 6 ) ：a e a ，b e b ) ，逆关系可定义为月“互a b 。如果关系只是集合4 和b 的关系， s 是b 和c 的关系，则关系r 和s 的合成表达式为r o s 。 集合的关系具有以下五种性质： ( 1 ) 反射性：对于每个a e a ，如果0 ，口) e r ，则关系r c a 一是反射的。 ( 2 ) 对于每个a e a ，如果尺是爿上的二值关系，但关系a r a 非真，则r 是 非反射的； ( 3 ) 对称性：如果0 ，6 ) e r ，当( 6 ，e r ，关系尺是对称的； ( 4 ) 如果，b ) e r ，且a ，b 不相同，若( 6 ，回g r ，则关系尺是反对称的； ( 5 ) 传递性：若 ，6 ) e r ，( 6 ，c ) r ，则当 ，c ) e r ，关系r 是传递的。 根据上面这些性质，可以得到两个非常重要的概念等价关系和等价类。 定义2 5 ( 等价关系) ：如果集合a 的关系满足反射性、对称性和传递性，则a 的关系尺称为等价关系。 定义2 6 ( 等价类) ：等价关系的集合称为等价类。 等价关系同样也是粗糙集理论中非常重要的一种关系。 2 1 2 知识的概念 在人工智能领域，知识被认为是基于对研究对象分类的能力。 定义2 7 ( 论域) ：在问题研究中，所有的研究对象称为论域。 例如数据库中所有的记录都可以认为是研究对象，所以整个数据库中的记录可 以认为是论域，论域记为u 。在集合论中，通常不是处理一个单独的分类而是处 理u 上的一些分类族。在这里，用c 豫表示根据关系月，u 中的对象构成的所有 等价类族，因此引出了不可分辩的概念。 定义2 8 ( 不可分辩关系) ：设属性集p e r ，对象卫咫以对于每个口尸，当 且仅当，= ，( l 口) 时，x 和】，是不可分辨的，即： i n d ( p ) = ( 墨l ，) u ：v a e p ，( l 口) = ，( l 回)( 2 1 ) 卅i n d ( p ) 定义为与等价关系相关的知识，称为基本知识。为了简洁表示，在这 里将u i n d ( p ) 记为u r ，的等价类称为知识p 的基本概念或基本范畴。如果 q c p ，i n a ( q ) 的等价类就称为知识p 的初等范畴。 例2 1 ：表2 1 是一个关于苹果情况的表，从表可知： 第二章集合理论和粗糙集基础 表2 1 知识示例 u 颜色( c )大小( s )熟否( m ) e 1红大是 e 2红中是 e 3红小否 e 4青大是 e 5青 由 否 e 6 青小否 e 7青小否 苹果的集合u 可以按颜色c ( e l ，9 2 ，p 3 为红色，9 4 ，p 5 ，e 6 ，e 7 为青色) 、 大小s ( e l ，e 4 为大的，9 2 ，e 5 为中等的，p 3 ，8 6 ，p 7 为小的) 、熟否m ( e l ，e 2 ， p 4 ，p 5 为熟的，p 3 ，e 6 ，8 7 为未熟) 进行分类，根据这三个等价关系，可得到下 列三个等价类族： u c = e 1 ，e 2 ，p 3 ， e 4 ，p 5 ，b 6 ，p 7 ) ) u s = “e l ，e 4 ， e 2 ，e 5 1 ， p 3 ，p 6 ，p 7 ) ) u m = e 1 ，e 2 ，p 4 ， 9 3 ，p 5 ，p 6 ，e 7 ) ) 这些等价类族就是由知识库世= u ， c ，s ，m ) 中的初等范畴构成的，根据 这些初等范畴的交集可以构成基本范畴，如： p 1 ，e 2 ，p 3 ) n e l ，e 2 ，e 4 ，e s = e l ，e 2 是基于fc ，m 的初等范畴得到的基本范畴，即：红的熟了的苹果。 由上面的概念可知，知识实际上是一族等价关系，是区分论域中不同对象的能 力，它将论域分割成一系列的等价类，每个等价类中各个体之间是不可辨识的。 一个等价类就是所谓的“知识颗粒”( k n o w l e d g eg r a n u l e ) ，粗糙集的含糊性 ( v a g u e n e s s ) 很大程度上都是由知识的颗粒性引起的。如由表2 1 可得： u c ，s ，m ) = 8 1 ， e 2 1 ， e 3 ， e 4 ， p 5 ) ， e 6 ，e 7 1 1 ，其中 p 6 ， e 7 ， e l i 等就是“知识颗粒”。 2 2 粗糙集理论基础 本节将介绍粗糙集中最基本的概念，如近似、粗糙程度度量、约简与核等。 2 2 1 基本概念 粗糙集把客观世界或对象世界抽象为一个信息系统，也称属性一值系统。 定义2 9 ( 信息系统i n f o r m a t i o ns y s t e m ) ：一个信息系统s 是一个四元组 ! !塑撞堡丝煎篡壁垄塑塑蕉堡主笪堑窒墨堡旦 s 2 ( 2 - 2 ) 其中，u 就是一组论域，设u 有f 个对象，则u 可表示为：u = 仕l ，x 2 ， h 。a 是有限个属性的有限集合，设有m 个属性，则其可表示为：爿= m ，晚， a 。 。a 又可进一步划分为两个不相交的集合：条件属性集c 和决策属性集d ，c 和d 满足a = c u d 且c n d = ，d 一般只有一个属性。v 是属性的值域集，肛= n ，圪，) ，其中m 是属性4 i 的值域。，是信息函数( i n f o r m a t i o n f u n c t i o n ) ， ，：u x a 寸y ，( 而，a j ) 巧。 在表2 1 中，u = p 1 ，p 2 ，9 3 ，8 4 ，p 5 ，p 6 ，e 7 ) ，a = c u d = 颜色( c ) ，大 小( s ) ) u 熟否( m ) ) ，矿e = 红，青 ，v x , j 、= 大，中，小 ，矿* i = 是，否 ， 矿= 矿臻色，v x 4 、，矿熟吾 。 粗糙集理论将用于分类的知识嵌入到集合内，作为集合的一个组成部分。根据 现有的知识判断，一个对象a 是否属于集合x 有三种情况：对象a 肯定属于m 对象口肯定不属于集合五对象口可能属于也可能不属于集合j 乙由此出现了 粗糙集中最重要的两个概念：下近似( l o w e ra p p r o x i m a t i o n ) 和上近似( u p p e r a p p r o x i m a t i o n ) 。 定义2 1 0 a ( 下近似) ：对信息系统s ，设x g u 是一组对象，对于一个等价关 系r ，即r g c 是一组条件属性。相对于矗的下近似是： r ( 2 缸u 僵： x h c _ x ( 2 3 a ) 定义2 1 0 b ( 上近似) ：对信息系统s ，x 相对于r 的下近似是： r e 的= 缸u r ：b kn x ；a o )( 2 3 b ) 基c 的是根据知识r ，u 中所有一定能归入z 的元素的集合，即所有包含于x 的b k 的并。rc 的是根据知识r ，u 中一定和可能归入z 的元素的集合，即所有与 x 的交不为零的w r 的并。 由上近似和下近似，可以得到正域( p o s i 廿v er e g i o n ) 、负域( n e g a t i v er e g i o n ) 和边界域( b o u n d a r yr e g i o n ) 的概念。 定义2 1 l a ( 正域) ：集合z 相对于r 的正区域就是x 的下近似，即 p o s e d ) = 显( 的( 2 4 a ) 定义2 1 l b ( 负域) ：集合x 相对于r 的负区域是： n e 嘞( 勘= u r ( 2 - - 4 b ) 定义2 1 l e ( 边界域) ：集合z 相对于r 的边界域是： b n d n ( x ) 2 r 的一r ( 的( 2 4 c ) 边界域中的元素是可能属于也可能不属于x 的元素组成的集合，如果边界域为 空，则称集合x 是关于r 的精确集( e x a c ts e t ) ；反之，称集合z 是关于r 的粗糙 集( r o u g h s e t ) 。 例2 2 ：从例2 1 的分析有，选择r = s c ，有：u s = 蜀，岛) ，其中s i = p 1 ， 第二章集合理论和粗糙集基础 e 4 ，2 e 2 ，e 5 ，s 3 = e 3 ，8 6 ，e 7 ) 。d = m ，u m = ，) ，蝎= e 1 ，e 2 p 4 ) ，m z = e 3 ，p 5 ，e 6 ，e 7 。 对于蝎有：因为s l c m ，昆n m l o ，岛n m = 0 ，因此有： 基( 饥) = s i = e l ，e 4 ，r ( 4 ) = s l u & = p 1 ，p 2 ，p 4 ，p 5 ) 对于m 2 有：因为s ln 尬= o ，& n m l 0 ，岛c m = 0 ，因此有： 星( 朋j ) = & = p 3 ，p 6 ，p 7 ) ，r ( 以) = u & = p 2 ，p 3 ，p 5 ，p 6 ，p 7 ) p o s r ( d ) = 基( 蚴) t 基( 尬) = p 1 ，8 4 ，p 3 ，e 6 ，e 7 1 n e g r ( m 1 ) = p 3 ，p 6 ，e 7 ) ，n e g r ( m e ) = e l ，e 4 1 b n d r ( m i ) = r ( m ) 一基( 蚴) = e 2 ，e 5 1 b n d r ( m 2 ) = r ( 尬) 一基( 必) = e 2 ，e 5 由此可以获得这样的知识，如果苹果是大的，一定是熟的，如果苹果是小的， 一定是不熟的，中等大小的苹果可能是熟的，也可能是不熟的。 2 2 2 精度表示的概念 一个集合的粗糙程度与集合边界中元素的多少有关，边界域中元素越多表明集 合的粗糙程度越大。在粗糙集申，主要有两种方法表示粗糙程度，一种是用近似 程度的精度来表示数字特征，一种是用分类来表示拓扑特征。 定义2 1 2 ( 近似精度) ：近似精度出( 的定义为： 蟊= c a r d ( r ) c a r d ( 基)( 2 5 ) 玉用来反映对于集合z 的知识了解的完全程度。显然，对于每一个r 且y o u ， 有0 d r ( x ) 1 ；当出= 1 ，x 的r 边界域为空，集合x 为r 可定义的；当d r ( x ) 1 ，则集合x 有非空边界域，则集合为r 不可定义的。 妇还可以由另外一种形式r 粗糙度( r r o u g h n e s s ) 来定义集合x 的不 确定程度，即： p r ( 的= 1 一办( 的( 2 6 ) 如在例2 2 中，d r ( m i ) = 2 4 = o 5 ，d r ( m 2 ) = 3 5 = 0 6 。 可以看到，与概率论和模糊集合论不同，不精确性的数值不是先设定好的，而 是通过表达知识不精确性的概念近似计算得到的，近似精度是反映对象分类能力 的结果。 除了用近似精度外，还可以根据上、下近似的定义来表示粗糙集的拓扑特征， 即可以定义如下四种不同的粗糙集： 当基( a 且r ( 两u ，则称x 为r 粗糙可定义( r o u g h l y r d e f i n a b l e ) 。 当基s = 乃且r u ，则称z 为r 内不可定义( i n t e r n a l l y r u n d e f i n a b l e ) 。 当基g 且r = u ，则称x 为月外不可定义( e x t e m a l l yr ! !塑蕉塞丝笪蔓堡查翅返蕉堡的盟窒墨查旦 u n d e f i n a b l e ) 。 当r = o 且r = u ，则称z 为r 全不可定义( t o t a l l y r u n d e f i n a b l e ) 。 近似精度和拓扑特征都可以表示粗糙集，二者之间既有联系又有区别。显然， 当集合为内不可定义时，其近似精度为0 ；当集合为外不可定义或全不可定义时， 它的补集的近似精度为0 。然而近似精度仅表示了结合边界域的大小，没有说明边 界的结构，粗糙集的拓扑特征只提供了边界域的结构而没有提供大小信息，因此 二者不可相互替代。 2 2 3 约简与核 在信息系统中，常常需要在保持初等范畴的情况下消去冗余基本范畴，进行知 识简化，在粗糙集理论中，主要是利用两个基本概念约简( r e d u c t i o n ) 和核 ( c o r e ) 。首先需要做如下定义： 定义2 1 4 ( 省略和不可省略) ：设一等价关系为属性集合r c _ c ，属性，r ，当 i n d ( r ) = i n d ( r 一 ， ) ，称r 为r 中可省略的，否则r 为r 中不可省略的。 定义2 1 5 ( 独立) ：当对于任一r r ，若r 不可省略，则r 为独立的。 属性是可省略的就意味这属性去掉后不影响分类的结果，由此可以计算属性与 集合间的依赖程度。 定义2 1 6 ( 依赖) ；设一等价关系为屙l 生集合r c _ c ，对于属性d 以依赖度7 r ( d ) 依赖于s 中a 的子集尸，若： = t “d ) - | ( p o s k d ) i i p o s a ( d ) l( 2 - 7 ) 定义2 1 7 ( 属性重要性) ：设属性a e c ，则d 的属性重要度定义为： s g f ( 口，c ，d ) = t r ( d ) 一你一( d )( 2 8 ) s g f ( 口，c ，d ) 表明从c 中去除口后对分类决策的影响程度，有了这些概念后， 就可以定义核( c o r e ) 和约简( r e d u c t i o n ) 的概念。 定义2 1 8 ( 约简) ：属性子集r c _ c ，若： ( 1 ) p o s r ( d ) = p o s c ( d ) ； ( 2 ) 对于r 的任意真子集r 有( 1 ) 不真。 则r 称为c 的一个约简，记为r e d ( d ) ，简记为r e d 。 定义2 1 9 ( 核) ：c 中所有不可省略属性的集合称为c 的核，即： c o r e ( d ) = n r e d ( d ) ( 2 9 )