装订线第6章 基于粗糙集（Rough Set）理论的数据挖掘技术粗糙集理论是由波兰华沙理工大学数学家Z.Pawlak于1982年提出的一种数据分析理论，该理论在分类意义下定义了模糊性和不确定性两个概念。是一种处理不完整数据、不精确知识的表达、学习、归纳等的一种新型数学工具。粗集理论的重要特点是：不需要任何附加信息或先验知识，直接从所需处理的数据本身所提供的信息出发找出问题的内在规律。目前，大多数数据挖掘工具软件（如：AQ系统、IDS系统等）都是基于集合论开发的，其中粗糙集（RS）理论使用最广，也最有发展前途。由于RS是研究不精确和不确定知识的一种数据工具，如，知识的含糊性，主要包括：术语的模糊性，如高矮；数据的不确定性，如噪声；知识自身的不确定性，如规则的前后件间的依赖关系不完全可靠等。所以，它同其它不确定问题理论，如，概率统计理论中的概率分布、模糊理论不能处理不完整数据且需提供隶属函数这种先验知识、D-S证据理论中的基本概率赋值等相比，更具实用性。粗集理论的主要思想：是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前，RS理论已成功地应用于机器学习、过程控制、模式识别、数据挖掘、预测、故障诊断、决策分析和人工神经网络等领域，成为其它不确定理论的一种补充，有着不可替代的优越性。1. 粗糙集理论的基本概念（1） 知识和知识库设为论域，任何子集，称为中的一个概念或范畴。规定空集也是一个概念。中的一个概念族称为关于的抽象知识，简称知识。这里，主要对上能形成划分的那些知识感兴趣。一个划分F定义为：F，其中， （显然，一个划分就是一条知识）上的一族划分称为关于的一个知识库（knowledge base）。设是上的一个等价关系，表示R的所有等价类构成的集合，即。表示包含元素的R等价类。【例如】考虑一组儿童的集合，A=（张，9），（王，9），（李，9），（赵，9），（刘，7），（洪，7），（梁，7），（黄，5），（陈，5），（段，8）。则具有“相同年龄”关系的等价类如下： =（张，9），（王，9），（李，9），（赵，9） =（刘，7），（洪，7），（梁，7） =（黄，5），（陈，5） =（段，8）即一个知识库就是一个关系系统，R是上的一族等价关系。若等价关系族，且，则也是一个等价关系（即P中所有等价关系的交集），称为P上的不可区分关系（indiscernibility）,记为ind(P)，且有 （1）则表示与等价关系族P相关的知识，称为K中关于的P基本知识（P基本集）。为简单起见，用代替。不可分辩关系概念是RS理论的基础，它揭示出论域知识的颗粒状结构。的等价类称为知识P的基本概念或基本范畴。特别的，如果，则称为K中关于的初等知识。的等价类为知识R的初等概念或初等范畴。当为一知识库，定义为K中所有等价关系的族，记作 （说明K是由所有基本知识组成的集合）【例如】一玩具积木的知识表达系统论域，如果根据某一属性描述这些积木情况，就可按颜色、形状和体积分类。换言之，可以定义三个等价关系（即属性）：颜色、形状、体积。按分：-红；-蓝；-黄按分：-圆；-方；-三角型按分：-大；-小。由此得三个等价类： 这三个等价类均是由知识库中的初等概念（初等范畴）构成的。它的基本范畴是初等范畴的交集构成的，如 -红色三角形 -蓝色方形 -黄色三角形上面是的基本范畴。 -红色大三角形这是的基本范畴。 -红色或蓝色，为的范畴。注：（1）有些范畴在这个知识库是无法得到的，如 -说明知识库中不存在蓝色圆形，为空范畴。 -说明知识库中不存在红色方形，为空范畴。 （2）上例容易求出、和 = = = = （3）若一个知识系统，给定一个等价关系簇，且有下列等价类： 试求：， 自己思考定义： 设和为两个知识库，若，即，则称和（P和Q）是等价的，记作（）。（说明和有同样的基本范畴）设和为两个知识库，当时，称知识P（知识库）比知识Q（知识库）更精细，或Q比P更粗糙。当P比Q更精细时，也称P为Q的特化，Q为P的推广。这就意味着，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。（2）不精确范畴、近似与粗糙集 令，为上的一个等价关系。当能表达成某些基本范畴的并时，则称是可定义的；否则不可定义的。可定义集是论域的子集，它可在知识库中精确地定义。而的不可定义集不能在这个知识库中定义。的可定义集也称为精确集，而的不可定义集也称为的非精确集或的粗糙集。当存在等价关系且为精确集时，集合称为中的精确集；当对于任何，都是粗糙集，则称为中的粗糙集。定义：设给定知识库，对于每个子集和一个等价关系，定义两个子集： 分别称为的下近似（lower approximation）和上近似（upper approximation）。上下近似也可用下面的等式表达： -由根据知识判断肯定属于的U中元素组成 -由根据知识判断可能属于的U中元素组成集合称为的边界域；称为的正域；称为的负域。显然，【示例】应用近似集合的概念，根据粗集的定义，来研究或分析一些人的受教育程度与就业的关系问题。受教育程度与就业的情况如下表所示。受教育者受教育程度就业情况王高中无马高中有李小学无刘大学有赵研究生有解：由受教育程度与就业情况知识表达数据表知，研究对象：受教育的人：U=王，马，李，刘，赵受教育程度：高中，小学，大学，研究生四种，即等价关系，其中=王，马，=李，=刘，=赵就业情况：有，无两种。设X为定义有工作的人为一种分类子集，则有工作的人的子集=马，刘，赵则根据粗集的定义，有 刘，赵 刘，赵，王，马 李 王，马所以，根据粗集中、的意义，可得受教育程度与就业的情况表达如下：根据， 规则1： if （大学）or（研究生） then （一定有工作）根据， 规则2： if （高中、大学）or（研究生） then （可能有工作）根据，规则3：if （高中） then （可能有、也可能无工作）根据，规则4：if （小学）then （无工作）定理1：（1）为可定义集当且仅当 （2）为粗糙集当且仅当定理2：（1） （2）， （3）； （4）； （5）； （6）()=；()= （7）；定义：当且仅当 当且仅当这里，表示根据，肯定地属于；表示根据，可能属于。分别称和为下和上成员关系。说明成员关系依赖于我们的知识，即一个对象是否属于一个集合依赖于我们的知识，并且这不是绝对特性。由此可以看出，集合（范畴）的不精确性是由于边界的存在而引起的。集合的边界域越大，其精确性则越低。一般而言，两个集合X和Y之间的相似程度定义为 当X和Y不相交时，S（X，Y）=0；当X和Y完全相同时，S（X，Y）=1。由此，可类似给出X关于R粗糙度。定义精度：由等价关系定义集合的近似精度为 -反映对了解集合的知识的完全程度。其中，表示集合的基数。 -为的粗糙度。对于空集，定义粗糙度。2. 知识约简知识约简是粗糙集理论的核心内容之一。众所周知，知识库中的知识（属性）并不是同等重要的，甚至其中某些知识是冗余的。所谓知识约简，是指在保持知识库分类能力不变的条件下，删除其中不相关或不重要的知识。知识约简中有两个基本概念：约简（reduct）和核(core)。定义：令R为一族等价关系，如果 则称为R中不必要的；否则为必要的。如果每一个都为R中必要的，则称R为独立的；否则称R为依赖的。定理：如果R是独立的，则P也是独立的定义：设，如果Q是独立的，且，则称Q为P的一个约简。显然P可以有多种约简。P中所有必要关系组成的集合称为P的核，记作core(P)。核与约简的关系为定理：core(P)=red(P)，其中red(P)表示P的所有约简。由此看出，核这个概念的用处有两个方面：l 核可以作为所有约简的计算基础，因为核包含在所有约简之中，并且计算可以直接进行；l 核可解释为在知识约简时它是不能消去的知识特征集合。【示例】 设是一个知识库，其中，且 则得关系的等价类为 （注：是通过计算获得的）故由计算： （注：是通过计算获得的）说明关系为R中必要的。 对于关系，有 故是R中不必要的。同理，也是R中不必要的，即有 但 且有 ，所以，为独立的且为R的一个约简。同理，也是独立的且为R的一个约简。则一个核core(R)=.3. 知识的相对约简、相对核概念令P和Q为U中的等价关系，Q的P正域记为，即 所以，Q的P正域是U中所有根据分类的信息可以准确地划分到关系Q的等价类中去的对象集合。令P和Q为等价关系族，如果 则称为P中Q不必要的；否则为必要的。为简单起见，用代替。 如果P中的每个都为Q必要的，则称P为Q独立的（或P相对于Q独立）。设，S为P的Q约简当且仅当S是P的Q独立子族且。P的Q约简简称为相对约简。P中所有Q必要的原始关系构成的集合称为P的Q的核。简称相对核，记为.定理：，其中是所有P的Q约简构成的集合。【示例】 设是一个知识库，其中，且 则由P导出的分类为 假设等价关系Q有下列等价类： 则Q的P正域为： 又 所以 故是P中Q必要的。 同理得，为P中Q不必要的；为P中Q必要的。这样，P的Q核为，即，它也是P的Q约简。4. 知识表达系统知识表达在智能数据处理中占有十分重要的地位