（计算机软件与理论专业论文）基于粗集理论的数据挖掘中数据预处理的方法研究.pdf

摘要 出于经典的粗糙集理论不能处理原始数据资料中的遗漏信息以及含 有连续属性的数据，需要对这些数据进行补齐和连续属性离散化才能用 于知识获取。因此数据预处理在粗糙集理论应用中非常重要的一环，其 结果将直接影响到粗糙集理论应用的效率，准确度。所以有关基于粗集 理论的数据挖掘中数据预处理的方法研究具有非常重要的意义。 本文对基于粗集的数据预处理中数据补齐和连续属性离散化问题进 行讨论。 首先，对目前主要的离散化算法进行分析和评价，以中值序列分割 点集为基础，提出了一种连续、离散混合离散化改进算法，保证划分后决 策表相容性，获得合理的划分点。 其次，分析了当前主要数据补齐算法的特点和不足，并针对已有的 基于粗糙集理论的不完备系统补齐算法r 0 u s t i d a 的缺陷，提出了改进的 数据补齐算法，使更多的缺损数据得到填补，尽量避免可能导致的决策 规则矛盾问题。 关键字：粗集数据挖掘数据补齐离散化 a b s t r a c t d u et ot h ec l a s s i cr o u 曲s e t 也e o r yc a i ln o td e a lw i t l lt l l em i s s i n gd a t ao f o r i g i n a ld a t am 舢e r i a la sw e l la st l l ed a t ac o m a i n i n gt l l ec o m i n u o u sf e a t u r e ，i t c a nb eu s e dt og a i n ；m o w l e d g et or e i n f o r c et h o s ed a t aa n dd i s 删z et l l e c o n t i n u o u sf b a t u r e s 0 出妇p r e p r o c e s s i n gi nm er o u g hs e tm e o r yp r a c t i c ei sa v e r yu s e f mp r o c e s s ，i t sr e s u l tw i l ii n f l u e n c er o u 曲s e t 1 e o r y 口r a c t i c e s e 伍c i e n c y 趾da c c u r a c y s om er e s e a r c hf o rd a t ap r e p r o c e s s i n gm e m o di n t h ed a t am i n i n gt l l a ti sb a s e du p o nr o u g hs e tm e o r yh a sv e r yi m p o r t a n t m e a n l l 培 t m st l l e s i sd i s c u s s e sm ea u e s t i o no fd 咖r e i n r i r c ea n dc o m i n u o u s f e a t i i r ed i s c r c t i z a t i o nw h i c hi sb a s e du p o nd a t ap r e p r o c e s s i n go f r o u g hs e t f i r s t l y i ta n a l y z e sa i l dc o m m e n t st h ep r c s e mm a i nd i s c r c t i z a t i o n c a l c u l a d o n ，i tp u t sf on 】l ，a r dak i n do fc o n t i n u o u sa 1 1 dm i x e dd i s c r e t i z a t i o n 瑚【0 d i f i e dm e t l l o db a s e do nt h em e d i a ns e q u e n c ed i v i s i o np o i n ts e tt oe n s u r e d e c i s i o nt a b l ec o m p a t i b i l i t ya r i dt og a i nr e a s o n a b l ed i v i s i o np o i m s e c o n d l y ，i t a n a l y z e st l l ef e a t u r c s 锄ds h o n a g e so fp s e n tm a i n r e i n f o r c ec a l c l l l a t i o n ，a i m i n 窑a t 也el i m i t a t i o no fi n c o m p l e t cs y s t e m 砒i c r e i n f o r c ec a l c u l a t i o nr o u s n d a 。i td u t sf o n 趼dam o d i f i e dd a t ar e i i l f o r c e c a j c l l i a t i o nw h j c hc a l lf i l lu pm o r cm i s s i n gd a t aa n dt r i e st oa v o i dd e c i s i o n m l ec o n t r a d i c t i o nq u e s t i o nw h i c hm a yb ec a u s e d k e y _ r o r d s ：r o u g hs e t 。 d a t am i n j n g ，d a t ar e j n f o r c e d i s c r e t i z a t i o n 第一章绪论 1 1 研究的目的和意义 随着计算机、网络和通讯等信息技术的高速发展，信息处理在整个 社会规模上迅速产业化，在技术上表现为整个社会对大规模数据操作的 产业化。这使得人们所积累的数据越来越多，并且数据与信息系统中的 不确定性更加显著。海量杂乱的数据背后隐藏着许多重要的信息，人们 希望能够对其进行深入分析，以便更好地利用这些数据所隐藏的信息。 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但 无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发 展趋势“1 。缺乏挖掘数据背后隐藏知识的手段，导致了“数据爆炸但知 识贫乏的现象”。 所以，一种能自动分析数据，并提取出隐藏的、为人所理解的知识 的数据挖掘( d a t am i n i n g ，d m ) 0 3 算法是非常有用的。它的出现为自动 和智能地把海量数据转化为有用的知识提供了有力的手段。卜“1 。数据挖 掘技术从一开始就是面向应用的，它要对这些数据进行微观、中观乃至 宏观的统计、分析、综合和推理，以指导实际问题的求解，发现事件问 的相互关联，甚至利用已有的数据对未来的活动进行预测。进行数据挖 掘的方法有很多，粗糙集方法是主要方法之一。粗糙集理论是8 0 年代初 由波兰数学家z p a w l a k 教授提出的，用于研究不完整数据和不精确知识 的表达、学习归纳的数学分析理论“1 。其特点是算法简单，无需提供数 据之外的任何先验信息，可直接从给定问题的描述集合出发，通过不可 分辨关系和等价类确定给定问题的近似域，从而找出该问题的规律。由 于经典的粗糙集理论不能处理原始数据资料中的遗漏信息以及岔有连续 属性的数据，而我们现实中面对的数据大多含有连续属性，需要对这些 数据进行补齐和连续属性离散化后才能用于知识获取。因此数据预处理 在粗糙集理论应用中非常重要的一环，其结果将直接影响到粗糙集理论 应用的效率，准确度。所以有关粗糙集理论数据预处理的研究具有非常 重要的意义。 1 2 粗糙集理论的应用与发展 1 2 1 粗糙集理论的产生和发展 7 0 年代，波兰学者z p a w l a k 等人组成研究小组，针对从试验中得 到的以数据形式表达的不精确、不确定、不完整的信息和知识，进行分 类分析，为粗糙集理论产生奠定了基础。8 0 年代，z p a w l a k 针对g f r e g e 的边界线区域思想提出了r o u g hs e ，1 9 8 2 年，z p a w l a k 发表了经典 论文r o u g h s e t s ，宣布了粗糙集理论的诞生，他把那些无法确认的个体都 归于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差。 由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描 述，所以含糊元素的数目可以被计算出来，从而实现了g f r e g e 的边界 线区域思想。到了八十年代末，粗糙集理论引起了许多数学家、逻辑学 家和计算机研究人员的兴趣，他们在粗糙集理论和粗糙集理论的应用方 面作了大量的研究工作。1 9 9 1 年z p a w l a k 的专著和1 9 9 2 年应用专集“1 的出版，对这一段时期理论和实践工作的成果作了较好的总结，促进了 粗糙集理论在各个领域的应用。此后召开的与粗糙集理埝有关的国际会 议进一步推动了粗糙集理论的发展，越来越多的科技人员开始了解和从 事该领域的研究。目前，粗糙集理论已成为人工智能领域中一个较新的 学术热点，在机器学习、知识获取、决策分析、过程控制等许多领域得 到了广泛的应用。 1 2 2 粗集理论的特点 l 。粗糙集理论不需要先验知识。模糊集方法和概率统计方法是处理 不确定信息的常用方法，但这些方法需要一些数据的附加信息或先验信 息，如模糊隶属函数和概率分布等。粗糙集理论是一种新型的处理模糊 和不确定信息的数学工具，其基本思想“1 是在保持分类能力不变的前提 下，通过知识的约简导出概念分类规则，该方法的最大优点在于无需人 为的额外假设条件，而是完全由已知数据来如实地回答问题，从而开辟 了一条与传统智能信息处理方法所截然不同的新途径。 2 粗糙集理论可以对数据进行处理，去掉多余属性，提高发现效率， 降低错误率，他能表达和处理不完备信息。能在保留关键信息的前提下 对数据进行化简求得知识的最小表达式，能识别并评估数据之间的依赖 关系，揭示出概念简单的模式，能从经验中获得易于证实的规则知识。 3 从数据发现的角度看，粗糙集理论支持数据发现的多个步骤：数 据预处理、数据约简、规则生成等，具有其他方法不具有的优点。由于 粗糙集理论中的决策表可以被视为关系型数据库的关系表，因此粗糙集 方法的伸缩性较强，知识的可理解性和开放性较好。 4 粗糙集与证据理论、模糊集的区别，粗糙集理论能够分析隐藏在 数据中的事实而不需要关于数据的任何附加信息。即先验知识，从数据 中揭示出概念简单、易于操作的模式，这是和模糊理论。1 与证据理论的 主要区别，粗糙集理论以不可分辨关系为基础，侧重分类，模糊集基于 元素对集合隶属程度的不同，强调集合本身的含糊性，虽然粗糙集和模 糊集的特点不同，但他们之蒯有着密切的关系，有很强的互补性“俨“”， 粗糙集和证据理论也有一些互补之处“。 1 2 3 粗糙集理论的应用现状 粗糙集理论问世以来，无论是在理论或应用上都是一种迅速发展的 理论，不但出现了很多基于粗糙集理论的算法，许多国家和企业还开发 出许多的实验平台。 1 股票数据分析，文“”应用粗糙集方法分析了十年间股票的历史数 据，研究股票价格与经济指数之间的依赖关系。 2 美国肯萨斯大学开发了一套基于粗糙集理论的示例学习系统，由 示例的机器学习和知识获取两部分组成，它能从大量经验数据中抽取出 规则。其以被美国国家航空航天管理局采用，作为专家系统的开发工具。 3 模式识别，文“”应用粗糙集方法研究了手写字符识别问题，提取 出了特征属性。 4 地震预报，文“研究了地震前的地质和气象数据与里氏地震级别 的依赖关系。 5 决策分析“”。希腊工业发展银行e t e v a 应用r s 理论协助制定信贷 政策，是r s 多准则决策方法的一个成功范例。 6 文“”应用粗糙控制研究了“小车一倒立摆系统”这一经典控制问 题，取得了较好的结果。 7 医疗诊断，粗糙集方法根据以往的病例归纳出诊断规则，用来指 导新的病例。 8 人工神经网络，训练时间过长是制约人工神经网络实用化的因素 之一，文“应用粗糙集理论化简神经网络训练样本数据集，在保留重要 信息的前提下消除了多余的数据，使训练速度得到提高，文“”将粗糙集 理沧与人工神经网络结合起来，充分利用粗糙集理论处理不确定性的特 长，以增强人工神经网络的信息处理能力。 1 3 数据挖掘 1 - 3 1 数据挖掘的定义 近年来，随着数据应用的普及和大规模数据库的出现，数据挖掘引 起了信息产业界的极大关注，迫切需要将数据转换成有用的信息和知识。 数据挖掘( d m ) 通常系指从大量的原始数据中发现隐含的、未知的、 有用的知识的非平凡过程。”1 ”1 。简单的说，就是从数据到知识的过程。 数据挖掘的对象一数据，既可以是集中在主机上的数据库，也可以是分 布存放在互联网上的各种数据。这些数据一般可能有几千兆字节或更多， 故数据挖掘一般需要某些领域知识。 1 3 2 数据挖掘的特点 数据挖掘技术与传统的数据库查询技术存在显著不同1 。首先，传 统的数据库查询一般都具有严格的查询表达式，可以用s q l 语句描述， 而数据挖掘则常常表现出即时的、随机的特点，查询要求不确定，无法 用s q l 语言表达。其次，传统的数据库查询一般生成严格的结果集，但 数据挖掘过程往往基于统计规律，产生的规则并不要求对所有的数据项 总是成立的，而是达到事先约定的闽值就可以了。此外，通常情况下， 数据库查询只对数据库的原始字段进行，而数据挖掘可能在数据库的不 同层次上发掘知识规则。 1 3 3 粗糙集理论在数据挖掘中的应用 基于粗糙集理论的数据挖掘方法可以支持数据挖掘的多个步骤，如 数据预处理、数据约简与规则生成等。目前，粗糙集理论在数据挖掘中 的应用相当广泛，涉及的领域有医疗研究、商业风险预测、市场分析、 气象学、语音识别、工程设计等，在众多的数据挖掘系统中，粗糙集理 论的主要作用集中在以下几个方面： 1 数据约简 粗糙集理论可提供有效方法用于对信息系统中的数据进行约简，在 数据挖掘系统的预处理阶段，通过粗糙集理论删除数据中的冗余信息， 如冗余属性、对象以及属性值等，可大大提高数据挖掘系统的运算速度。 例如，文献。”使用粗糙集方法对信息系统进行属性及属性域的约简，然 后使用神经网络对约简后的数据进行分类，从而在网络分类精度没有明 显下降的前提下使网络的学习速度提高到约简前的4 7 2 倍。 2 规则提取 与其它方法相比，使用粗糙集理论生成规则是相对简单和直接的， 信息系统中的每一个对象既对应一条规则，粗糙集方法生成规则的一般 步骤为：首先，得到条件属性的一个约简，删去冗余属性；再者，删去 每条规则的冗余属性值；最后，对剩余规则进行合并。目前已经产生了 许多基于粗糙集理论的方法用于从信息系统中抽取规则嘶，。 3 增量算法 面对数据挖掘中的大规模、高维数据，寻找有效的增量算法是一个 研究热点。文献0 7 1 提出了一种基于粗糙集理论与泛化分布表的规则发现 算法，它能从大型数据库中增量地发现规则，而且能有效处理噪声数据 和不完整数据。 4 与其它方法的融合 粗糙集理论与其它方法如神经网络、遗传算法、模糊数学、决策树 等相结合可以发挥各自的优势，大大增强数据挖掘的效率。在文献“”中， 粗糙集理论应用于产生确定规则，神经网络用于产生非确定规则，粗糙 集理论的使用提高了系统的运算速度，同时神经网络则使产生的规则集 泛化能力提高。 1 3 4 未来的发展 尽管粗糙集理论作为一种主要的数据挖掘方法，已经得到了相当程 度的发展，但是仍有一些待深入研究的课题：比如，面对大规模、高维 数据，粗糙集理论如何设计比较通用的、高效率的、可扩展的挖掘算法； 面对时序数据、空间数据以及时序一空间数据，粗糙集理论如何动态地发 现知识、修改知识；如何与其它挖掘方法的有效结合来进行复杂系统数 4 据挖掘；如何更有效的利用领域知识、先验知识来提高挖掘的有效性及 准确性。 1 4 数据预处理 随着数据应用的普及以及大规模的数据库的不断发展壮大，人类积 累的数据量正在以指数级速度迅速增长。人们对数据库的应用已不能满 足于仅对数据库进行简单的查询和检索。而是充分发掘和利用数据背后 隐藏的丰富知识，提取带有结论性的有用信息，这就需要进行数据发现 和数据发掘。 由于目前数据挖掘具有数据内容涉及范围广、数据量大、数据属性 宽、数据来源和数据原始资料存储形式比较复杂等特点，数据如果没有 经过数据预处理阶段，直接用于数据挖掘算法，容易引起以下问题： 一方面数据在内存和存储器之间频繁的进行页面调度，导致数据挖 掘算法的性能急剧下降；另一方面低质量数据造成数据挖掘算法的运算 结果严重失真。 因此，对数据预处理进行研究具有很重要的现实意义，主要表现在 以下几个方面： 第一，任何数据挖掘的方法都离不开对数据的预处理。 第二，数据预处理是数据挖掘处理步骤中非常重要的一环，其结果 将直接影响到数据挖掘的效率、准确度以及最终模式的有效性。 第三，数据挖掘发展面对的基本难点问题，如数据量巨大和高维数、 用户交互与先验知识的利用、丢失数据的处理及模式的可理解性等，上 述问题的有效解决都有待于对数据挖掘预处理进行深入的研究和探索。 总而言之，数据预处理的目的就是在不损失数据信息的基础上，对 数据进行优化处理，提高数据质量，满足数据挖掘算法对数据的特定要 求，减少后续数据搜索的复杂度，提高数据挖掘的效率。 有关基于粗糙集理论的数据预处理： 从知识发现的角度来看，粗糙集理论支持数据挖掘的多个步骤：如 数据预处理、数据约简、规则生成等，能够有效的提高知识发现效率， 降低错误率。 粗糙集理论能够对在知识获取阶段造成的属性值缺损。1 进行填补， 现在比较成熟的方法主要有两种：一是间接处理方法，其特点是通过一 定的方法把不完备信息系统转化为完备信息系统，即数据补齐；二是直 接处理方法，其特点是对经典粗糙集理论中相关概念在不完备信息系统 下进行扩充。粗糙集理论给数据挖掘的应用带来好处的同时也带来了一 些需要解决的问题，例如因为粗糙集理论只能处理有关离散型数据的研 究，而一般的数据挖掘所面临的大多是一些连续型的数据，所以将粗糙 集理论引入数据挖掘就需要对连续型数据进行相关的离散”“化处理。连 续型属性的离散化问题处理就是在特定的连续属性的值域范围内设定若 干离散化划分点，将连续属性的值域范围划分成一些离散化区间，在用 不同的符号或整数值代表属于每个区间的属性值。目前，人们提出了很 多连续属性离散化算法，如等宽区间法，等频区间法，基于信息熵的二 元分割法，粗集方法。“，实函数离散化。“。另外，每个连续属性的离散 化过程并不是独立进行的，还要考虑其它属性的影响，从而有可能产生 不合理的或多余的划分点，影响数掘挖掘的效果，如何解决这个问题已 经成为一个新的研究发展方向。 1 5 本文的主要研究内容 粗糙集理论对于人工智能和认知科学是十分重要的，提出以来一直 得到模糊数学创始人z a d e h 的重视，并给予很高的评价，将之列入他新 提倡的软计算的基础理论之一。将粗糙集理论应用于数据挖掘领域，能 提高对大型数据库中的不完整数据进行分析和学习的能力，具有广泛的 应用前景和应用价值。 由于经典的粗糙集理论不能处理原始数据资料中的缺损信息以及含 有连续属性的数据，需要对这些数据进行缺损数据补齐和连续属性离散 化才能用于知识获取。因此数据预处理在粗糙集理论应用中非常重要的 一环，其结果将直接影响到粗糙集理论应用的效率，准确度。所以有关 粗糙集理论数据预处理的研究具有非常重要的意义。 本文主要是有关粗糙集理论数据预处理的研究，主要针对连续数据 离散化方面和有关缺损属性补齐的问题进行研究。首先，传统基于租糙 集理论的离散化方法大多仅仅从连续属性的角度上考虑离散化方法，这 样的处理方法虽然简单易行，但为后续处理步骤带来了隐患。主要没有 将连续属性和离散属性进行全局考虑，进而导致了条件属性中连续属性 的分类能力无法与其中的离散属性相比较，所以在后续的属性约简中， 没有统一的尺度加以评价，而仅仅是将条件属性分为连续属性和离散属 性分别进行考虑，这一不足之处显然不能满足产生有效规则的最终要求。 有鉴于此，对于连续属性离散化方法不能仅仅考虑连续属性，还应当同 时考虑离散属性。本文对传统粗糙集理论的离散化方法进行改进，以中 值序列分割点集为基础，提出了一种连续、离散混合离散化方法，对上 述不足之处进行改进。其次，本文分析了数据补齐方法r o u s t i d a 的优缺 点，该算法虽然考虑到粗糙集理论的不可分辨性，保证补齐后避免引入 决策冲突信息，但对于许多情形无能为力，可能在处理到一定的步骤后， 就无法进行下去，而缺损值并没有填补好，而且填补结果还是容易引入 决策冲突，本文针对该算法的缺点进行改进，使更多的缺损值得到填补， 减少引入的决策冲突。 本文的组织如下： 第一章是全文的绪论。 第二章重点介绍了经典粗糙集理论及其相关理论。 第三章本文对传统粗糙集理论的离散化方法进行改进，以中值序列 分割点集为基础，提出了一种连续、离散混合离散化的改进方法。 第四章分析了数据补齐方法r o u s t i d a 的优缺点，针对该算法的缺点 进行改进，提出改进算法。 第五章对全文工作进行了总结和展望。 第二章粗糙集基本理论 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主 要思想就是在保持分类能力不变的前提下，通过知识约简导出问题的决 策或分类规则。下面将阐述粗糙集理论的基础及其基本思想。 2 1 知识与分类 在信息系统中，人们首先碰到的就是对知识的理解和表达。一般认 为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特性，是属 于认识论范畴的概念。知识直接与真实或抽象世界有关的不同分类模式 联系在一起，任何一个物种都是由一些知识来描述的，利用物种不同的 属性知识描述，可以对物种产生不同的分类。 设u a 是我们感兴趣的对象组成的有限集合，称为论域。任何子 集x u 称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是 一个概念。u 中的任何概念簇称为关于u 的抽象知识，简称为知识。u 上 的一族划分称为关于u 的一个知识库，它构成了一个特定论域u 的分类。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合， x 。表示包含元素x u 的r 等价类。一个知识库就是一个关系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一个等价关系族。 若o p 至r ，则n p ( p 中所有等价关系的交集) 也是一个等价关系， 称为p 上的不可分辨( i n d i s c e r n i b i l i t y ) 。”关系，记为i ( p ) ，且 有 x ) _ n x 。 r p ( 公式2 1 ) 这样，u i n d ( p ) 表示与等价关系族p 相关的知识，称为关系系统 k 中关于u 的p 基本知识，i n d ( p ) 的等价类称为知识p 的基本概念或 基本范畴。事实上，p 基本范畴是拥有知识p 的论域的基本特性，即知 识的基本模块。 例如，给定一个玩具积木集合u = x l x 2 ，x 8 ，并假设这些 积木有不同的颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 大、 小) 。因此，这些积木都可以用颜色、形状、体积这些知识来描述。例如 一块积木可以是红色、小而圆的，或黄色、大而方的等。我们可以按颜 色、形状、体积对这些积木进行分类。 例如，表2 1 所示的决策表 表2 1 信息系统实例 决策表中的每一行称为一个对象( 实体、实例) ，我们将其标记为 u l ，u 2 ，u 3 ，u 8 每一个对象的属性集可以分为条件属性集和决策属 性集，条件属性集为 身高、头发、眼睛 ，决策属性集为 分类 ，考虑 条件属性身高和头发，对于u l 、u 2 、u 8 这三个对象，其条件属性身高的 值都是“矮”，条件属性头发的值也都是“金黄色”，因此，从条件属性 身高和头发的角度来看，这三个对象是不可分辨的。同样u 4 、u 5 、u 7 在 这两个属性上也是不可分辨的。由此可构成的不分明集为 ( u 1 ，u 2 ，u 8 ， u 4 ，u 5 ，u 7 ) ， u 3 ) ， u 6 ) 被称为基本集。任意有限个基本集的 并被称之为可定以集。 2 2 不精确范畴，近似与粗糙集 令x u ，r 为u 上的一个等价关系。当x 能表达成某些r 的基本范 畴的并时，称x 是r 可定义的；否则称x 为r 不可定义的。r 可定义集 也称为r 精确集，而r 不可定义集也称为r 的非精确集或r 的粗糙集。 例如，在表2 一l 所示的决策表中，集合 u l ，u 3 ，u 6 就是条件属性子 集为r = 头发) 不可定义的，是r 非精确集，因为根据条件属性子集，对 象u 1 、u 2 、u 6 、u 8 是不可分辨的，u 4 、u 5 、u 7 是不可分辨的，我们不 能根据条件属性子集r 来对所有对象是否属于集合 u 1 ，u 3 ，u 6 ) 作出精确 判定，是r 不可定义的。但是，如果条件属性子集为r = 头发，眼睛) ， 因为根据条件属性子集，对象u 1 、u 6 是不可分辨的，u 2 、u 8 是不可分 辨的，u 4 、u 5 是不可分辨的，我们能根据条件属性子集r 来对所有对象 是否属于集合 u l ，u 3 ，u 6 ) 作出精确判定，是r 可定义的。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上 近似集( u p p e ra p p r o x i i i l a t i o n ) 和下近似集( l o w e ra p p r o x i i i l a t i o n ) 来描 述。给定知识表达系统k _ ( u ，r ) ，对于每个子集x 呈u 和一个不可分辨 关系r ，定义两个子集： 9 星x = u y u 只l l ，x ) ( 公式2 2 ) 豆并= u ( ye u ，月i j ，nz 回 ( 公式2 3 ) 分别称它们为x 的r 下近似集和r 上近似集。 其中，u r = x l ( x 互u 八v x v y v b ( b ( x ) = b ( y ) ) ) 是不可分辨关系r 对u 的划分，也是论域u 的r 基本集的集合。 即当且仅当 x n x ，x 垦( x ) 即当且仅当 x n n x o ，x 敏 集合b ( x ) 2 _ x 一旦x 称为x 的r 边界域；p o s n ( x ) r 正域，n e g * ( x ) = u + _ x 称为x 的r 负域。显然有 砑= p c ( x ) u b r ( x ) r x 称为x 的 ( 公式2 4 ) r x 或p o s 。( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成 的集合；诫是那些根据知识r 判断可能属于x 的u 中元素组成的集合； b n h ( x ) 是那些根据知识r 既不能判断肯定属于x 又不能判断肯定不属于x 的u 中元素组成的集合；n e g 。( x ) 是那些根据知识r 判断肯定不属于x 的 u 中元素组成的集合。 例如，在表2 一l 所示的决策表中，对于属性子集r = 头发，眼睛) ， 集合x = u l ，u 3 ，u 6 ) 是r 可定义，下面分别计算集合x 的上近似集、下近 似集、正域、边界域。 首先计算论域u 的所有r 基本集为 u i n d ( r ) = u 1 ，u 6 ， u 2 ，u 8 ， u 3 ) ，( u 4 ，u 5 ， u 7 可得集合x 的上近似集、下近似集、正域、边界域分别为 r y = u 1 ，u 3 ，u 6 jr x = u 1 ，u 3 ，u 6 ) p o s r ( x ) = u 1 ，u 3 ，u 6 ) b n i l ( x ) = mn e g r ( x ) = u 2 ，u 4 ，u 5 ，u 7 ，u 8 j 当b n r ( x ) = 巾时，称集合x 是属性子集r 可定义的。 集合的不精确性是由于边界域的存在而引起的，集合的边界域越大， 其精确性越低。为了更准确地表达这一点，我们引入了精度概念。由等 价关系r 定义的集合x 的近似精度为： 嘣耻黝 ( 公式2 5 ) 其中x a ，如果x _ o ，可定义。( x ) = 1 ，i x i 表示集合x 的基数。 由此可见，集合x 的精度是一个区间 0 ，1 上的实数，它定义了集 合x 的可定义程度，即集合x 的确定度。精度用来反映我们对集合x 的 知识的了解程度。显然，当n 。( x ) = l 时，我们说集合x 是r 可定义的； 当q 。( x ) l 时，我们说集合x 是r 不可定义的。 1 0 当然，也可以用其它量度来定义集合x 的不精确程度，比如，用x 的r 粗糙度p 。( x ) 来定义： p ( x ) = 1 一口r ( r ) x 的r 粗糙度与精度恰恰相反， 程度。 ( 公式2 6 ) 它表示关于集合x ，知识r 的不完备 除了用数值( 近似程度的精度) 来表示粗糙集的特征外，也可以根 据上下近似集的定义来表达粗糙集的另一个有用的特征，即拓扑特征。 下面定义四种不同的重要粗糙集： 如果丛o 且豆_ u ， 如果鲋2 0 且r z u ， 如果丛a 且r z 2 u ， 如果蚪= o 且豆z = u ， 则称x 为r 粗糙可定义； 则称x 为r 内不可定义； 则称x 为r 外不可定义； 则称x 为r 全彳i 可定义； 这个划分的直观意义如下：如果集合x 为r 粗糙可定义，则我们可 以确定u 中某些元素属于x 或不属于x ；如果x 为r 内不可定义，意味 着我们可以确定u 中某些元素是否不属于x ，但不能确定u 中任一元素 是否属于x ：如果x 为r 外不可定义，我们可以确定u 中某些元素是否 属于x ，但不能确定u 中任一元素是否不属于x ：如果x 为r 全不可定义， 则我们不能确定u 中任一元素是否属于x 或不属于x 例如，在表2 一l 所示的决策表中，集合 u l ，u 3 ，u 6 就是条件属性子集 r = 头发) 粗糙可定义，因，l 勾_ x = i j l ，u 2 ，u 3 ，u 6 ，u 8 8 x = u 3 ，x 的精度和 粗糙度分别为n ，( x ) = 1 5 ，pn ( x ) = 4 5 粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域的 结构；而粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边 界域的结构。因此在粗糙集的实际应用中，我们需要将边界域的两种信 息结合起来，既要考虑精度因素，又要考虑到集合的拓扑结构。 粗糙集理论还对集合类关于近似空间的分类问题定义了上近似集和 下近似集。令f = x l ，x 2 ，x n 是u 的一个分类或划分，这个分 类独立于知识r ，子集x i 是划分f 的类f 的r 下近似集和上近似集分 别定义为： 星f = ( 笪1 ，星芦2 ，星晒 面= 面l ，戤2 ，砒) 1 1 有两个量度来描述近似分类的不精确性，第个量度为根据知识r ， f 的近似分类精度： 印i 口r ( f ) = 等一 陋i ( 公式2 7 ) 第二个量度为根据知识r ，f 的近似分类质量： 幽| h 旷卜苛 ( 公衄8 ) r 对f 近似分类的精度描述的是当使用知识r 对对象进行分类时， 在所有可能的决策中确定决策所占的百分比；r 对f 近似分类的质量表 示的是应用知识r 对对象进行分类时，能够确切地划入f 类的对象的百 分比。 将粗糙集的概念与普通集合论相比较，可以看出粗糙集的基本性质， 如元素的成员关系、集合的等价和包含等，都与不可区分关系所表示论 域的知识有关。因此，一个元素是否属于某一个集合，不是该元素的客 观性质，而取决于我们对它的了解程度：同样，集合的相等和包含也没 有绝对的意义，而取决于我们对所研究问题中集合的了解程度。 2 3 知识约简与知识的依赖性 知识约简是粗糙集理论的核心内容之一。所谓知识约简，就是在保 持知识库分类能力不变的条件下，删除其中不相关或不重要的知识。当 了解一个论域中的对象的时候，我们可以通过知道其属性值来对对象进 行处理。但是在现实情况中，有时我们不知道一个对象的所有属性值， 只能根据部分属性值来进行判定；有时我们需要确定一个论域中是否每 个属性的重要程度都是一样的，因为度量不同属性值的代价可能不同。 在专家系统中，也会遇到类似的权重问题，重要性高的属性在作决策时 被赋予大的权重。通常我们只能根据经验来选择权重，这依赖于人的先 验知识。根据上节中介绍的知识r 对集合簇f 近似分类的质量y ，( f ) 这 一概念，我们可以对论域样本属性的重要程度进行度量，而不依赖于人 的先验知识。 令r 为一个等价关系簇，p r ，如果i n d ( r ) = i n d ( r 一( p ) ，则称p 为 r 中不必要的；否则称p 为r 中必要的。如果每一个p r 都为r 中必要 的，则称r 为独立的，否则称r 为相关的。 设q 至p ，如果q 是独立的，且i n d ( q ) = i ( p ) ，则称o 为p 的一个 约简( 简式) 1 。显然，p 可以有多个约简( 简式) p 中所有必要等 价关系组成的集合称为p 的核，记作c o r e ( p ) 。 核与简式( 约简) 有如下关系： c o r e ( p ) = n r 即( p )( 公式2 9 ) 其中，r e d ( p ) 表示p 的所有简式( 约简) 。可以看出，核这个概念有 两方面的用处：首先它可以作为所有约简的计算基础，因为核包含在所 有的简式之中，并且计算可以直接进行；其次可解释为在知识约简时它 是不能消去的知识特征集合。 不可区分关系r ( a o ，c ，d 可以看作每一个属性a a ，b ，c 。d ) 的不 可区分关系r a 的重叠。这样，并不是所有的属性在“叠加”r a ，b ，c ，d ) 时都是必需的。一个约简是一个最小子集b 至a ，a = 慨b ，c ，d j ，使r b = r a 。 在本例中，约简是 a b ) ， b ，d 和 c ，d 。 在应用中，一个分类相对于另一个分类的关系十分重要。令p 和q 为u 中的等价关系，q 的p 正域记为p o s 。( q ) ，即 尸( 爆p ( g ) = u 蹦 e u 口 ( 公式2 1 0 ) q 的p 正域是u 中所有根据划分u p 的信息可以准确地分类到关系q 的等价类中去的对象集合。 令p 和q 为等价关系族，r p ，如果 尸0 岣( 一( 刷d ( q ) ) 2p 0 q d ( p 一) ( d ( 9 ) ( 公式2 1 1 ) 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。为简单起见， 也用p o s 。( q ) 代替p 0 s 。( i n d ( q ) ) 如果p 中的每个r 都为q 必要的， 则称p 为q 独立的。 设s 互p ，s 为p 的q 简式当且仅当s 是p 的q 独立的且 p c 嗨( q ) = p ( 心p ( q ) p 的q 简式简称为相对简式p 中所有q 必要的初等关系构成的集 合称为p 的q 核，简称为相对核，记为c o r e 。( p ) 。 相对核与相对约筒的关系如下： c o r e 口( p ) = n r e d q ( p )( 公式2 1 2 ) 其中r e d 。( p ) 是所有p 的q 简式构成的集合。 知识的依赖性可形式化地定义如下：令k = ( u ，r ) 是一个知识库， p ，q 互r 知识q 依赖于知识p ( 记作p 辛q ) 当且仅当i n d ( p ) 呈i n d ( q ) ； 知识p 与知识q 等价( 记作p 呈q ) 当且仅当p 寺q 且q = p ； 知识p 与知识q 独立( 记作p q ) 当且仅当p j q 与q 净p 均不成立。 当知识q 依赖于知识p 时，我们也说知识q 是由知识p 导出的。有 时知识的依赖性可能是部分的，这意味着用知识p 只能导出q 的部分知 识，部分可导出可以由知识的正域来定义： 令k = ( u ，r ) 为一知识库，且p ，q r ，当 七= ，p ( q ) = j p 傩p ( q ) i i u l ( 公式2 1 3 ) 我们称知识q 是k 度依赖于知议p 的，记作p 号。q 。 当k = l 时我们称q 完全依赖于p ；当o k 1 时称q 粗糙依赖于p ； 当k = 0 时称q 完全独立于p 系数h ( q ) 可以看作q 和p 间的依赖度。 部分依赖性p 号k q 的量度k 不能完全反映u q 中类之间的分布 情况，一些决策类可能完全由p 描述，但另一些可能仅仅由p 部分描述。 因此，我们需要使用一个系数r d ( x ) = l p x i lx l ，( x u q ) 来表明通过知 识p 能将u q 中每个类的多少个元素被正确划分。 这样，两个值b ( q ) 和h ( x ) ( x u q ) 给出了知识p 关于划分u q 的分类能力。 2 4 知识表达系统与决策表 知识表达在智能数据处理中占有十分重要的地位。知识表达系统的 基本成份是研究对象的集合，关于这些对象的知识可通过指定对象的基 本特征和它们的特征值来描述。 形式上，四元组s = ( u ，a ，v ，f ) 是一个知识表达系统，其中 u ：对象的非空有限集合，称为论域： a ：属性的非空有限集合； v = u v aa a ，v 属性值域，v a 是属性a 的值域； f ：u a v 是一个信息函数，它为每个对象的每个属性赋予一个信 息值，即v a a ，x u ，f ( x ，a ) v a 。 知识表达系统也称为信息系统。通常也用s = ( u ，a ) 来代替 s = ( u ，a ，v ，f ) 。 知识表达系统的数据以关系表的形式表示，关系表的行对应要研究 的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来 表达。容易看出，一个属性对应一个等价关系，一个表可以看作是定义 的一个等价关系簇，即知识库，知识约简可以转化为属性约简。 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用 决策表形式来表达。决策表可以根据知识表达系统定义如下： 设s = ( u ，a ，v ，f ) 是一知识表达系统，a = c u d ，且c n d o ，c 称为条件属性集，d 称为决策属性集，v 是属性的值域，f 对象属 性到值域的映射。具有条件属性和决策属性的知识表达系统称为决策表。 在决策表中，不同的属性可能具有不同的重要性。为了找出某些属 性( 或属性集) 的重要性，一般的方法是从表中去掉一些属性，再来考 1 4 察没有该属性后分类会怎样变化。若去掉该属性后相应的分类变化较大， 则说明该属性的重要性较高；反之，说明该属性的重要性较低。 令c 和d 分别为条件属性集和决策属性集，条件属性子集c c 关 于决策属性d 的重要性定义为 o r c d ( c ) = 毙( d ) 一比一c - ( d ) ( 公肯，1 4 1 这表示当我们从属性集c 中去掉属性子集c 对d 近似分类的质量 的影响。 在决策表中，最重要的是决策规则的产生。设s = ( u ， a ，v ，f ) 是一个决策表，a = c u d ，c n d = o ，其中c 为条件属性集，d 为决策属性集。 令x i 和y j 分别代表u c 与u d 中的各个等价类，d e s ( x i ) 表示对等价类 x i 的描述，即等价类x i 对于各条件属性值的特定取值；d e s ( y j ) 表示对 等价类y j 的描述，即等价类y j 对于各决策属性值的特定取值。决策规 则定义如下：r i j ：d e s ( x i ) 一d e s ( y j ) ，y j n x i o 。 规则的确定因子，“( x i ，y j ) = l y j n x i l i x i ，o 斗( x i ，y j ) 1 。 当“( x i ，y j ) = l 时，规则是确定的，当0 肛( x i ，y j ) 1 时，规则是不 确定的。 在产生决策规则之前，可先对决策表中的属性进行约简。 2 5 其它粗集模型 通过对前面粗糙集理论的介绍，我们对基本的粗糙集模型有了一定 的了解，下面我们再简单的介绍一下其它粗糙集模型。 1 粗信息分析，i v od u n t s c h 等人提出了粗信息分析领域，他们首 先描述了基本的粗集数据分析方法，并将统计概率、信息熵、代数格、 二进制转换等诸多领域的方法融入原始的粗糙集理论，他们的工作集中 于三个能利用传统粗集方法提高的领域，而这些方法也正在粗糙集基本 理论范畴内：数据的过滤：粗集规则的重要性检测；客观的描述粗集规 则的不确定性度量方法。 他们开发了一个非侵略性数据分析方法组件，这些组件虽然是基于 粗糙集理论的，但是并不局限于经典的粗集应用。 2 可变精度粗糙集模型 经典的粗糙集理论模型实际上是处理不精确或不完全信息的三值逻 辑的工具，即正区域、边界区域和负区域，缺乏处理模糊信息的能力， 不能处理概率事件。粗糙集理论的核心就是依据一定的等价关系将对象 分类，所描述的知识就是这种分类能力的大小。粗糙集理论的方法是在 可用信息不完全的情况下将对象归类于某一具体的类。通常分类是确定 的，但并未提供数理统计中所常用的，在给定错误率的条件下将尽可能 多的对象分类的方法，而实际上会经常遇到这类问题。 并且，原始粗糙集理论模型假设论域u 是已知的，所推出的理论仅 适用于此论域u 中的对象。实际应用中，满足此条件是非常困难的。例 如在天气预测上，可以从过去的资料中提取规则，根据当前的已知数据， 预测明天的天气。但若假设明天天气已知才能使用提取的规则，这是不 可能的。为解决这个矛盾，就必须寻求一种方法，能够从少量样本中提 出结论