《粗糙集理论与方法》读书笔记

《粗糙集理论与方法》读书笔记智能信息处理是当前信息科学理论和应用研究中的一个热点领域。由于计算机科学与技术的发展，特别是计算机网络的发展，每日每时为人们提供了大量的信息，信息量的不断增长，对信息分析工具的要求也越来越高，人们希望自动地从数据中获取其潜在的知识。特别是近20年间，知识发现（规则提取、数据挖掘、机器学习）受到人工智能学界的广泛重视，知识发现的各种不同方法应运而生。1粗糙集概述粗糙集（RoughSet，有时也称Rough集、粗集）理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具粗糙集理论最初的原型来源于比较简单的信息模型，它的基本思想是通过关系数据库分类归纳形成概念和规则，通过等价关系的分类以及分类对于目标的近似实现知识发现。由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种重要的智能信息处理技术，该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用。目前，有三个有关粗糙集的系列国际会议，即：RSCTC、RSFDGrC和RSKT。中国学者在这方面也取得了很大的成果，从2001年开始每年召开中国粗糙集与软计算学术会议；RSFDGRC2003、IEEEGrC2005、RSKT2006、IFKT2008、RSKT2008、IEEEGrC2008等一系列国际学术会议在中国召开。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子（又称上、下近似集）。经典Pawlak模型中的不分明关系是一种等价关系，要求很高，限制了粗糙集模型的应用。因此，如何推广定义近似算子成为了粗糙集理论研究的一个重点。目前，常见的关于推广粗糙集理论的研究方法有两种，即：构造化方法和公理化方法。构造化方法是以论域上的二元关系、划分、覆盖、邻域系统、布尔子代数等作为基本要素，进而定义粗糙近似算子，从而导出粗糙集代数系统。公理化方法的基本要素是一对满足某些公理的一元集合算子，近似算子的某些公理能保证有一些特殊类型的二元关系的存在；反过来,由二元关系通过构造性方法导出的近似算子一定满足某些公理。事实上，有两种形式来描述粗糙集，一个是从集合的观点来进行，一个是从算子的观点来进行。那么，从不同观点采用不同的研究方法就得到粗糙集的各种扩展模型。扩展模型的研究以及基于其上的应用研究已经成为新的研究热点。粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的,由于这个理论未能包含处理不精确或不确定原始数据的机制,所以这个理论与概率论,模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。因此，研究粗糙集理论和其他理论的关系也是粗糙集理论研究的重点之一。如果我们将研究对象看成是现象，那么我们可以将这些现象分类。现象被分为确定现象与不确定现象。不确定现象有分为随机现象，模糊现象和信息不全的粗糙现象。如下所示：确定现象随机现象，0－1律，多种可能性满足分布规律。现象不确定现象模糊现象，律属度Î(0，1），不是非此即彼。粗糙现象，研究那些因为信息不充分而导致的不确定性相对于前两种现象的处理，粗糙现象是基于不完全的信息或知识去处理不分明的现象，因此需要基于观测或者测量到的部分信息对数据进行分类，这就需要与概率统计和模糊数学不同的处理手段，这就是粗糙集理论。直观地讲，粗糙集是基于一系列既不知道多了还是少了，也不知道有用还是没用的不确定、不完整乃至于部分信息相互矛盾的数据或者描述来对数据进行分析、推测未知信息。下面我们对粗糙集的基本特征、以及数学符号进行简述。2粗糙集的特点粗糙集的特点是利用不精确、不确定、部分真实的信息来得到易于处理、鲁棒性强、成本低廉的决策方案。因此更适合于解决某些现实系统，比如，中医诊断，统计报表的综合处理等。粗糙集的另一个重要特点就是它只依赖于数据本身，不需要样本之外的先验知识或者附加信息，因此挑选出来的决策属性可以避免主观性，有英雄不问出身的意味。用粗糙集来处理的数据类型包括确定性的、非确定性的、不精确的、不完整的、多变量的、数值的、非数值的。粗糙集使用上、下近似来刻画不确定性，使得边界有了清晰的数学意义并且降低了算法设计的随意性。粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的,由于这个理论未能包含处理不精确或不确定原始数据的机制,所以这个理论与概率论,模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。因此，研究粗糙集理论和其他理论的关系也是粗糙集理论研究的重点之一。基于粗糙集理论的应用研究主要集中在属性约简、规则获取、基于粗糙集的计算智能算法研究等方面。由于属性约简是一个NP-Hard问题，许多学者进行了系统的研究。基于粗糙集的约简理论发展为数据挖掘提供了许多有效的新方法。比如，针对不同的信息系统（协调的和不协调的、完备的和不完备的），结合信息论、概念格、群体智能算法技术等都有了相应的研究成果。基于粗糙集理论的应用也涌现在各行各业。许多学者将粗糙集理论应用到了工业控制、医学卫生及生物科学、交通运输、农业科学、环境科学与环境保护管理、安全科学、社会科学、航空、航天和军事等领域。2．粗糙集的基本概念从经典的角度来看，每个概念都包含其内涵和外延。为了给出概念内涵和外延的具体描述，我们考虑一个简单的知识表达系统，即信息表。信息表就是一组对象的集合，对象通过一组属性来描述。2.1定义粗糙集要涉及论域U（这与模糊系统相似），还要涉及属性集合RCD（这被认为是知识，或者知识库）。当然，也要有属性值域V，以及从UR到V的信息函数f。因此，一个信息系统S可以表示为一个四元组,,,SURVf。在不混淆的情况下，简记为(,)SUR，也称为知识库。等价关系（通常用来代替分类）是不可或缺的概念，根据等价关系可以划论域中样本为等价类。而每个等价类被称为同一个对象。但是，等价关系又是建立在不可分辨概念之上的，为了便于描述这里的等价关系，我们首先介绍不可分辨性。设BR为一个非空子集，如果,ijxxU，均有(,)(,),ijfxrfxrrB成立，那么，我们称ijxx和关于属性子集B不可分辨。B不可分辨关系，简记为()IndB，是一种等价关系（易验证它满足等价关系的数学公理），于是()IndB可以将论域U中的元素分成若干等价类，每一个等价类称为知识库的知识颗粒。全体等价类组成的集合记为/()UIndB，称之为基本集合。若集合X可以表示成某些基本集的并时，则称X是B精确集，否则称为B粗糙集。粗糙集中的“粗糙”主要体现在边界域的存在，而边界又是由下、上近似来刻画的。对于任意XU，X关于现有知识R的下、上近似分别定义为：_(){,[]}RRXxUxX，(){,[]}RRxxUxX。X的确定域PosXRX，是指论域U中那些在现有知识R之下能够确定地归入集合X的元素的集合。反之，NegXURX被称为否定域。边界域是某种意义上论域的不确定域，即在现有知识R之下U中那些既不能肯定在X中，又不能肯定归入\XUX中的元素的集合，记为RBndX。样本子集X的不确定性程度可以用粗糙度RaX来刻画，粗糙度的定义为：RCardRXaXCardRX式中Card表示集合的基数（集合中元素的个数）。显然，01RaX，如果1RaX，则称集合X关于R是确定的；如果1RaX，则称集合X关于R是粗糙的，RaX可认为是在等价关系R下逼近集合X的精度。为了使得上述概念具体化，下面我们举一个例子说明如何理解和计算以上相应的概念和对应量。例.针对一下医学信息表我们来理解前面所提到的概念。表1某医疗信息表属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感1x是是正常否2x是是高是3x是是很高是4x否是正常否5x否否高否6x否是很高是依据此表，如果取属性子集12,,Rrr头疼肌肉疼，123,,Xxxx。那么我们下面给出X的上近似集、下近似集、确定域、边界域、粗糙度。解：①计算论域U的所有R基本集：123465/,,,,,UIndRxxxxxx令112324635,,,RxxxRxxRx②确定样本子集X与基本集的关系112235{,}{}XRxxXRXRx；；③计算RX、RX、PosXBndX和：131235355123{,,}{}{}{,,}RXRRxxxxRXRxPosXRXxBndXRXRXxxx；；④计算近似精确度：1/40.25RCardRXaZCardRX与粗糙度类似，在给出了两个知识集（特征属性）的相对肯定域的概念()PPosQ之后，我们也可以一个量来刻画两个知识集的依赖度。设(,)KUR为一个知识库，,PQR为两个知识集。令()(())/()PPkrQCardPosQCardU，称为知识Q依赖于知识P的依赖度。特别，当1k时称为完全依赖；01k时，部分依赖；0k时，Q完全独立于知识P。2.2近似空间语言()AL的所有可定义集正好构造成一个代数(/())UEA，即：(,())(/()).DefUAUEAL。序对(,())aprUEA=称为一个Pawlak近似空间，简称近似空间。所以，也可以将语言()AL的所有可定义集记为(,())()DefUADefaprL。通过/()UEA，可以构造一个代数，即(/())UEA，它包含空集和等价关系()EA构成的等价类及其并，并且在交、并和补运算上是封闭的。那么，Pawlak近似空间也唯一确定了一个拓扑空间(,(/()))UUEA。2.3上下近似针对不可定义集，显然不可能构造一个公式来精确描述，只能通过上下界逼近的方式来刻画，这就是粗糙集理论中的上下近似算子。定义2设()EA是信息表M上的等价关系，XU，上下近似算子,()()apraprEAEA（下文我们采用缩写形式,aprapr）定义为：(){|(/()),}{|(,(),};(){|(/()),}{|(,(),}.aprXYYUEAYXYYDefUAXYaprXYYUEAYXYYDefUAYXUIIUULL上近似()aprX是包含X的最小可定义集，下近似()aprX是包含在X中的最大可定义集。根据定义2，可定义集显然有相同的上下近似。刚才我们在可定义的基础上构造了一对近似算子。也就是说，只有当对象不可定义时，才会用上下近似的方法来描述。考虑子集XU，论域空间将被分成三个区域：(1)集合X的正域：()();POSXaprX(2)集合X的负域：()(~)();NEGXPOSXUaprX(3)集合X的边界域：()()().BNDXaprXaprX。如果()BNDX是空集，则称集合X关于关系()EA是清晰的(crisp)；反之，如果()BNDX不是空集，则称集合X为关于关系()EA粗糙的(rough)。3.理论研究方法经典粗糙集理论的基本思想是基于等价关系的粒化与近似的数据分析方法。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子（又称上、下近似集）。目前，主要有两种研究方法来定义近似算子：构造化方法和公理化方法。构造化方法的主要思路就是通过直接使用二元关系的概念来定义粗糙集的近似算子，从而导出粗糙集代数系统(2,,,~,,)Uaprapr。构造化方法所研究的问题往往来源于实际，所建立的模型有很强的应用价值，其主要缺点是不易深刻体现近似算子的公理（代数）性质。所以，也有许多学者从公理化的角度来研究粗糙集。公理化方