粗糙集理论与方法读书笔记智能信息处理是当前信息科学理论和应用研究中的一个热点领 域。由于计算机科学与技术的发展，特别是计算机网络的发展，每日 每时为人们提供了大量的信息，信息量的不断增长，对信息分析工具 的要求也越来越高，人们希望自动地从数据中获取其潜在的知识。 特 别是近20年间，知识发现（规则提取、数据挖掘、机器学习）受到 人工智能学界的广泛重视，知识发现的各种不同方法应运而生。1粗糙集概述粗糙集（RoughSet，有时也称Rough集、粗集）理论是 Pawlak 教授于1982年提出的一种能够定量分析处理不精确、不一致、不完 整信息与知识的数学工具粗糙集理论最初的原型来源于比较简单的 信息模型，它的基本思想是通过关系数据库分类归纳形成概念和规 则，通过等价关系的分类以及分类对于目标的近似实现知识发现。由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种 重要的智能信息处理技术，该理论已经在机器学习与知识发现、 数据 挖掘、决策支持与分析等方面得到广泛应用。目前，有三个有关粗糙 集的系列国际会议，即：RSCTC RSFDGr（和RSKT中国学者在这方 面也取得了很大的成果，从 2001年开始每年召开中国粗糙集与软计 算学术会议；RSFDGRC20O3EEE GrC2005、RSKT2006 IFKT2008、 RSKT2008 IEEE GrC2008等一系列国际学术会议在中国召开。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算 子，即上近似算子和下近似算子（又称上、下近似集）。经典Pawlak 模型中的不分明关系是一种等价关系， 要求很高， 限制了粗糙集模型 的应用。因此，如何推广定义近似算子成为了粗糙集理论研究的一个 重点。目前，常见的关于推广粗糙集理论的研究方法有两种，即：构 造化方法和公理化方法。构造化方法是以论域上的二元关系、划分、 覆盖、邻域系统、 布尔子代数等作为基本要素，进而定义粗糙近似算 子，从而导出粗糙集代数系统。 公理化方法的基本要素是一对满足某 些公理的一元集合算子， 近似算子的某些公理能保证有一些特殊类型 的二元关系的存在； 反过来 , 由二元关系通过构造性方法导出的近似 算子一定满足某些公理。事实上，有两种形式来描述粗糙集，一个是从集合的观点来进 行，一个是从算子的观点来进行。那么，从不同观点采用不同的研究 方法就得到粗糙集的各种扩展模型。 扩展模型的研究以及基于其上的 应用研究已经成为新的研究热点。粗糙集理论与其他处理不确定和不精确问题理论的最显著的区 别是它无需提供问题所需处理的数据集合之外的任何先验信息 , 所 以对问题的不确定性的描述或处理可以说是比较客观的 , 由于这个 理论未能包含处理不精确或不确定原始数据的机制 , 所以这个理论 与概率论 , 模糊数学和证据理论等其他处理不确定或不精确问题的 理论有很强的互补性。 因此，研究粗糙集理论和其他理论的关系也是 粗糙集理论研究的重点之一。如果我们将研究对象看成是现象，那么我们可以将这些现象分 类。现象被分为确定现象与不确定现象。 不确定现象有分为随机现象， 模糊现象和信息不全的粗糙现象。如下所示：确定现象现象随机现象，01律，多种可能性满足分布规律。不确定现象 模糊现象，律属度 ? （0 ，1），不是非此即彼。粗糙现象， 研究那些因为信息不充分而导致的不确定性 相对于前两种现象的处理， 粗糙现象是基于不完全的信息或知识去处 理不分明的现象， 因此需要基于观测或者测量到的部分信息对数据进 行分类，这就需要与概率统计和模糊数学不同的处理手段， 这就是粗 糙集理论。直观地讲，粗糙集是基于一系列既不知道多了还是少了， 也不知道有用还是没用的不确定、 不完整乃至于部分信息相互矛盾的 数据或者描述来对数据进行分析、 推测未知信息。 下面我们对粗糙集 的基本特征、以及数学符号进行简述。2 粗糙集的特点 粗糙集的特点是利用不精确、不确定、部分真实的信息来得到 易于处理、鲁棒性强、成本低廉的决策方案。因此更适合于解决某些 现实系统，比如，中医诊断，统计报表的综合处理等。粗糙集的另一 个重要特点就是它只依赖于数据本身， 不需要样本之外的先验知识或 者附加信息， 因此挑选出来的决策属性可以避免主观性， 有英雄不问 出身的意味。用粗糙集来处理的数据类型包括确定性的、 非确定性的、 不精确的、不完整的、多变量的、数值的、非数值的。粗糙集使用上、 下近似来刻画不确定性， 使得边界有了清晰的数学意义并且降低了算 法设计的随意性。粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比较客观的，由于这个理论未能包含处理不精确或不确定原始数据的机制，所以这个理论与概率论，模糊数学和证据理论等其他处理不确定或不精确问题的 理论有很强的互补性。因此，研究粗糙集理论和其他理论的关系也是 粗糙集理论研究的重点之一。基于粗糙集理论的应用研究主要集中在属性约简、规则获取、 基于粗糙集的计算智能算法研究等方面。由于属性约简是一个 NP-Hard问题，许多学者进行了系统的研究。基于粗糙集的约简理论 发展为数据挖掘提供了许多有效的新方法。 比如，针对不同的信息系 统（协调的和不协调的、完备的和不完备的），结合信息论、概念格、 群体智能算法技术等都有了相应的研究成果。基于粗糙集理论的应用 也涌现在各行各业。许多学者将粗糙集理论应用到了工业控制、医学卫生及生物科学、交通运输、农业科学、环境科学与环境保护管理、 安全科学、社会科学、航空、航天和军事等领域。2.粗糙集的基本概念从经典的角度来看，每个概念都包含其内涵和外延。为了给出 概念内涵和外延的具体描述，我们考虑一个简单的知识表达系统， 即 信息表。信息表就是一组对象的集合，对象通过一组属性来描述。2.1定义粗糙集要涉及论域u （这与模糊系统相似），还要涉及属性集合 R cUd （这被认为是知识，或者知识库）。当然，也要有属性值域V , 以及从u R到V的信息函数f。因此，一个信息系统S可以表示为一个 四元组S U,R,V, f。在不混淆的情况下，简记为S (U,R)，也称为 知识库。等价关系(通常用来代替分类)是不可或缺的概念，根据等价 关系可以划论域中样本为等价类。而每个等价类被称为同一个对象。 但是，等价关系又是建立在不可分辨概念之上的，为了便于描述这里的等价关系，我们首先介绍不可分辨性。设B R为一个非空子集，如果Xi,Xj U ，均有 f(x,r) f(Xj,r), r B成立，那么，我们称Xi和为关于属性子集b不可分 辨。B不可分辨关系，简记为Ind(B),是一种等价关系(易验证它满 足等价关系的数学公理)，于是Ind (B)可以将论域U中的元素分成若干 等价类，每一个等价类称为知识库的知识颗粒。全体等价类组成的集 合记为U / Ind (B)，称之为基本集合。若集合X可以表示成某些基本集 的并时，则称X是B精确集，否则称为B粗糙集。粗糙集中的“粗糙”主要体现在边界域的存在，而边界又是由下、上近似来刻画的。对于任意X U，X关于现有知识R的下、上近 似分别定义为：R_(X) x U,xr X，R (x) x U,xr X 。x的确定域Pos X R X，是指论域U中那些在现有知识R之下能够 确定地归入集合X的元素的集合。反之，Neg X U R X被称为否 定域。边界域是某种意义上论域的不确定域，即在现有知识R之下u中 那些既不能肯定在x中，又不能肯定归入X U X中的元素的集合，记为BndR X 。样本子集X的不确定性程度可以用粗糙度aR X来刻画，粗糙度 的定义为：Card R X3r X Card R X式中Card表示集合的基数（集合中元素的个数）。显然，0 aR X 1， 如果aR X 1，则称集合X关于R是确定的；如果aR X 1，则称集 合X关于R是粗糙的，aR X可认为是在等价关系R下逼近集合X的 精度。为了使得上述概念具体化，下面我们举一个例子说明如何理解 和计算以上相应的概念和对应量。例.针对一下医学信息表我们来理解前面所提到的概念。表1某医疗信息表属 性对象 条件属性C决策属性D头疼r1肌肉疼2体温3流感x是是正常否是是高是为是是很高是X4否是正常否为否否高否否是很高是依据此表，如果取属性子集R头疼,肌肉疼 ri,r2 , X Xi,X2X。那 么我们下面给出x的上近似集、下近似集、确定域、边界域、粗糙度。解：计算论域U的所有R基本集：U/l nd Rx(,x2, x3 , Xt,x6 , x5令RiXi,X2,X3R2X4,x6 R3X5确定样本子集X与基本集的关系XR1花必；XR2； XR3X5计算R X、RX、PosX 和 BndX :R XR1R3X1,X2X3,X5；RXR3X5Pos XRXX5；BndXRXRXX1,X2,X3计算近似精确度aR ZCardRX1/40.25CardRX与粗糙度类似，在给出了两个知识集(特征属性)的相对肯定域 的概念Po(Q)之后，我们也可以一个量来刻画两个知识集的依赖度。 设K (U , R)为一个知识库，P, Q R为两个知识集。令 k rp(Q) Card (PoSp(Q)/Card (U )，称为知识q依赖于知识p的依赖度。 特别，当k 1时称为完全依赖；0 k 1时，部分依赖；k 0时，Q完 全独立于知识P。2.2近似空间语言L(A)的所有可定义集正好构造成一个代数(U / E(A)，即:Def (U , L (A)(U/E(A).。序对aPr=(u,E(A)称为一个Pawlak近似空间，简称近似空间。所 以，也可以将语言L(A)的所有可定义集记为Def(U丄(A) Def(apr)。通过U/E(A)，可以构造一个 代数，即(U/E(A)，它包含空集 和等 价关系E(A)构成的等价类及其并，并且在交、并和补运算上是封闭的。 那么，Pawlak近似空间也唯一确定了一个拓扑空间(U, (u/e(a)。 2.3上下近似针对不可定义集，显然不可能构造一个公式来精确描述，只能 通过上下界逼近的方式来刻画，这就是粗糙集理论中的上下近似算 子。定义2设E(A)是信息表M上的等价关系，X U，上下近似算子aprE(A)，aPrE(A)(下文我们采用缩写形式apr，apr )定义为：OpT(X) Y|Y (U/E(A),yx Y|Y Def(U,L(A),XY;apr(X) Ly|Y(U/E(A),Y XY|Y Def(U,L(A),YX.上近似apr(X)是包含X的最小可定义集，下近似 迴(X)是包含在 X中的最大可定义集。根据定义2,可定义集显然有相同的上下近似。刚才我们在可定 义的基础上构造了一对近似算子。也就是说，只有当对象不可定义时， 才会用上下近似的方法来描述。考虑子集X U，论域空间将被分成三个区域：(1) 集合X的正域：POS(X)迴(X);(2) 集合 X 的负域：NEG(X) POS(X) U 議(X);(3) 集合 X 的边界域：BND(X)硕(X