数据挖掘原理与SPSS Clementine应用宝典第11章粗糙集理论

数据挖掘原理与数据挖掘原理与SPSS Clementine应用宝典应用宝典 元昌安元昌安 主编主编 邓松李文敬刘海涛编著邓松李文敬刘海涛编著 电子工业出版社电子工业出版社 本章包括本章包括：粗糙集的基本概念粗糙集的基本概念 知识表达知识表达 粗糙集在数据预处理中的应用粗糙集在数据预处理中的应用v粗糙集理论是由波兰华沙理工大学粗糙集理论是由波兰华沙理工大学PawlakPawlak教教授于授于2020世纪世纪8080年代初提出的一种研究不完整、年代初提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理不确定知识和数据的表达、学习、归纳的理论方法，它是一种刻画不完整性和不确定性论方法，它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致的数学工具，能有效地分析不精确、不一致(inconslsteniinconslsteni)、不完整不完整(incomPleteincomPlete)等各等各种不完备的信息，还可以对数据进行分析和种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规推理，从中发现隐含的知识，揭示潜在的规律。律。v粗糙集在机器学习、决策支持系统、机器发现、归粗糙集在机器学习、决策支持系统、机器发现、归纳推理、数据库中的知识发现、模式识别等领域都纳推理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。得到了广泛的应用。v粗糙集应用于数据挖掘领域，能提高对大型数据库粗糙集应用于数据挖掘领域，能提高对大型数据库中的不完整数据进行分析和学习的能力，具有广泛中的不完整数据进行分析和学习的能力，具有广泛的应用前景和实用价值。的应用前景和实用价值。v粗糙集方法仅利用数据本身提供的信息，无须任何粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。先验知识。v粗糙集是一个强大的数据分析工具，它能表达和处粗糙集是一个强大的数据分析工具，它能表达和处理不完备信息；能在保留关键信息的前提下对数据理不完备信息；能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估进行化简并求得知识的最小表达式；能识别并评估数据之间的依赖关系，揭示出概念的简单模式；能数据之间的依赖关系，揭示出概念的简单模式；能从经验数据中获取易于证实的规则知识。从经验数据中获取易于证实的规则知识。v粗糙集的研究对象是由一个多值属性粗糙集的研究对象是由一个多值属性(特征、症状、特征、症状、特性等特性等)集合描述的一个对象集合描述的一个对象(观察、病历等观察、病历等)集合，集合，对于每个对象及其属性都有一个值作为其描述符号，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符是表达决策问题的对象、属性和描述符是表达决策问题的3 3个基本要个基本要素。素。v粗糙集理论逐渐应用于数据挖掘领域中，并在对大粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据库中不完整数据进行分析和学习方面取得了型数据库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙集理论及数据挖掘的研究成显著的成果，使得粗糙集理论及数据挖掘的研究成为热点领域。最近几年，粗糙集理论越来越受到众为热点领域。最近几年，粗糙集理论越来越受到众多研究人员的重视，它的应用研究得到了很大的发多研究人员的重视，它的应用研究得到了很大的发展。展。v 知识是人类通过实践对客观世界的运动规律的知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有抽象和认识，是人类实践经验的总结和提炼，具有抽象和普遍的特性。普遍的特性。v 从认知科学的观点来看，知识来源于人类对客从认知科学的观点来看，知识来源于人类对客观事物的分类能力，概念是事物类别的描述或者符观事物的分类能力，概念是事物类别的描述或者符号，知识则是概念之间的关系和联系。任何一个物号，知识则是概念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用物种的不种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。同属性知识描述来产生对物种的不同分类。v集合上的等价关系和集合上的划分是一一对应，相集合上的等价关系和集合上的划分是一一对应，相互唯一决定的。从数学意义上讲，集合上的等价关互唯一决定的。从数学意义上讲，集合上的等价关系和集合的划分是等价的概念，即划分就是分类。系和集合的划分是等价的概念，即划分就是分类。v定义定义11-1 11-1 设讨论的对象组成的有限集合，称为设讨论的对象组成的有限集合，称为论域论域(Universe)Universe)，对于论域中由等价关系划分出来对于论域中由等价关系划分出来的任意子集，都可以称为论域的任意子集，都可以称为论域U U中的一个概念中的一个概念(concept)concept)或范畴或范畴(category)category)。为规范起见，认为为规范起见，认为空集必也是一个概念。论域空集必也是一个概念。论域U U中的任意概念族称为中的任意概念族称为关于论域的抽象知识，它代表了对论域中个体的分关于论域的抽象知识，它代表了对论域中个体的分类，简称为知识。类，简称为知识。v定义定义11-2 11-2 K=(U,R)K=(U,R)其中其中K K为知识库，为知识库，U U为全体对象为全体对象的集合称为论域，的集合称为论域，R R为论域为论域U U上的等价关系上的等价关系(等价关等价关系与分类的概念等同系与分类的概念等同)，它是一种属性或多种属性，它是一种属性或多种属性的集合。可以根据不同的的集合。可以根据不同的R R对对U U进行不同形式的分类。进行不同形式的分类。知识库也被称作近似空间。知识库也被称作近似空间。Uv定义定义11-3 11-3 K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)是两个知识库，若是两个知识库，若IND(P)=IND(Q)IND(P)=IND(Q)，则称则称K K和和M(M(或或Q Q和和P)P)是等价的，是等价的，记作记作 (或者或者)。因此，当。因此，当K K和和M M是同样的基本是同样的基本范畴集时，知识库范畴集时，知识库K K和和M M中的知识都能使我们确切地中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着表达关于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于可以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事实。论域的完全相同的事实。v对于两个知识库对于两个知识库K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)，当当 时，称知识库时，称知识库P P比知识库比知识库Q Q更精细，或者说更精细，或者说Q Q比比P P更粗更粗糙。当糙。当P P比比Q Q更精细时，我们称更精细时，我们称P P为为Q Q的特化，的特化，Q Q为为P P的的推广。由以上可知，推广是将某些范畴组合在一起，推广。由以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。而特化则是将范畴分割成更小的单元。KMPQIND(P)IND(Q)v在粗糙集理论中，在粗糙集理论中，“知识知识”被认为是一种分类的能被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它力。不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。假定关于论域的某揭示出论域知识的颗粒状结构。假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，种知识，并使用属性和属性值来描述论域中的对象，如果两个对象如果两个对象(或对象集合或对象集合)具有相同的属性和属性具有相同的属性和属性值，则它们之间具有不可分辨关系。值，则它们之间具有不可分辨关系。v定义定义11-411-4设R是非空集合U上的二元系，如果它是自反的、对称的和可传递的，则称R为U上的等价关系。若，则称x与y有关系，记为 ；若 ，则称x与y没有关系，记为 。等价关系的一个重要特点是用它可以构成U的一个划分。划分即是分类，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。xRy(x,y)R(x,y)R_x Ryv定义定义11-511-5设U是一个论域，R是U上的等价关系，U/R表示U上由R导出的所有等价类。v 表示包含元素xU的R等价类。一个知识库就是一个关系系统K=U,P，其中U是论域，P是U上的一个等价类簇。如果 且 ，则 (Q的所有等价类的交也是一个等价关系)，称Q为不可分辨关系,记作IND(Q)。RxQPQQv给定论域给定论域U U，一族等价关系一族等价关系R R将将U U划分为互不相交的划分为互不相交的基本等价类基本等价类U/RU/R。令令 XgUXgU为为R R上的一个等价关系。上的一个等价关系。v当能表达成某些基本等价类的并集时，称为可定义当能表达成某些基本等价类的并集时，称为可定义的；否则称为不可定义的。的；否则称为不可定义的。R R可定义集能在这个知可定义集能在这个知识库中被精确地定义，所以又称为识库中被精确地定义，所以又称为R R精确集。精确集。vR R不可定义集不能在这个知识库中被精确定义，只不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为能通过集合逼近的方式来刻画，因此也称为R R粗糙粗糙集集(RoughsetRoughset)。v两个精确集，两个精确集，v即粗糙集的上近似集即粗糙集的上近似集(UpperApproximationUpperApproximation)和下和下近似集近似集(LowerApproximationLowerApproximation)来近似地定义粗糙来近似地定义粗糙集。集。v粗糙集理论引入上近似和下近似等概念来刻画知识粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。的不确定性和模糊性。v定义11-6设集合 ，R是一个等价关系，称 v 为集合X的R下近似集；v称 为集合X的R上近似集；v称集合 为X的R边界域；v称 为X的R正域；v称 为X的R负域。X URRX=x|x U|,xX且RRX=x|xU|,xX且()RBNXRXRXRPOS(X)=RXRNEG(X)=U-RXv例例11-1 11-1 设论域 ，U上的一族等价关系R=R1,R2,R1和R2是两个等价关系。根据这两个等价关系可以将论域U进行划分：v 和 。U/R1中的 ，代表 的等价类。v论域U被R划分的基本等价类为:v集合 是U上的一个子集。则X无法用基本等价类U/R的并集精确表示，所以X是U上的一个粗糙集合。故有:vX的下近似集为:；vX的上近似集为:；vX的负区域:。12345678U=e,e,e,e,e,e,e,e 212345678U/R=e,e,e,e,e,e,e,e1234e,e,e,e 11 Re12345678U/R=e,e,e,e,e,e,e,e 23678X=e,e,e,e,e 678Pos(X)=R(X)=e,e,e 12345678R(X)=e,e,e,e,e,e,e,e R5NEG (X)=e 112345678U/R=e,e,e,e,e,e,e,e v知识表达在智能数据处理中占有十分重要的地位。知识表达在智能数据处理中占有十分重要的地位。在智能系统中，经常会碰到要处理的对象可能是用在智能系统中，经常会碰到要处理的对象可能是用语言方式表达，也可能使用数据表达；可能是精确语言方式表达，也可能使用数据表达；可能是精确的数据，可能会有一些缺省的信息或者相互矛盾的的数据，可能会有一些缺省的信息或者相互矛盾的信息。信息。v为了处理这些数据，我们需要进行知识的表达，即为了处理这些数据，我们需要进行知识的表达，即知识表达系统。决策表是特殊的知识表达系统。知识表达系统。决策表是特殊的知识表达系统。v定义定义11-711-7一个知识表达系统一个知识表达系统S S可以定义为，其中可以定义为，其中U U为对象的集合，称为论域；为对象的集合，称为论域；=R R为属性集合；子集为属性集合；子集C C和和D D分别称为条件属性和决策属性；分别称为条件属性和决策属性；为属性值的集为属性值的集合；表示了属性的属性值范围；是一个信息函数，合；表示了属性的属性值范围；是一个信息函数，它指定了它指定了U U中每一对象中每一对象x x的属性值。的属性值。v知识表达系统的数据以知识表达系统的数据以关系表关系表的形式表示，关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达的信息是通过指定对象的各属性值来表达。v例例11-211-2：表11.1是一个轿车信息决策表，条件属性集为e1,e2,e3,e4分别代表价格、油耗、速度和安全性，决策属性为d，表示质量。表表11.1 轿车信息决策表轿车信息决策表车型车型U Ue1e1e2e2e3e3e4e4d d1 1高低快好高2 2低高中差低3 3中中慢一般低4 4中高慢一般中5 5低高中差低6高低快好高v决策表包含了某一领域的大量数据，是领域的样本决策表包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，数据库。它记录了大量样本的属性值和决策情况，是领域知识的载体。是领域知识的载体。v知识获取的目的就是要通过分析这个实例库来得到知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。决策表在决策应用该领域中有用的、规律性知识。决策表在决策应用中有十分重要的地位，可用于表达绝大多数决策问中有十分重要的地位，可用于表达绝大多数决策问题。对于决策表，最重要的是决策规则的生成。题。对于决策表，最重要的是决策规则的生成。v定义定义11-811-8 设U=U1，U2，U3，Un 是一个论域,U(i=1,2,，n)是研究对象。P是属性集,P=C+D,C 为条件属性集,D 为决策属性集,T=(U,P,C,D)是决策表。决策表中每一行就是一条决策规则:dx|C-dx|D,dx|B 表示个体x关于属性集B 的值。v定义定义11-911-9 若决策表T 中任意的dxdy,由dx|C=dy|C,可得dx|D=dy|D,则称决策规则dx 是一致的,否则,称决策规则dx 是不一致的。如果T 中每条决策规则都是一致的,则称决策表T 是一致的,否则称决策表T是不一致的。v定义定义11-1011-10 设T=(U,P,C,D)是决策表,如果去掉条件属性Pi，得到的表T1=(U,P-Pi,C-Pi,D)与表T 相比,有PosC(D)=Pos(D)，则称属性Pi是关于D可省的,否则称属性Pi 是关于D 不可省的,是D 关于B 的正区域，其中 。PosB(D)=YU/IND(D)B(Y)B(Y)=X U/IND(B):X Yv定义定义11-1111-11 如果决策表中每个条件属性都是关于D 不可省的,则称条件属性集C 是关于D独立的，否则称C 是关于D 依赖的。v定义定义11-1211-12 决策表T=(U,P,C,D)中条件属性集C 的一个子集B 是关于D 独立的,并且PosB(D)=PosC(D),则称B 是C 的一个D约简。v所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。v一个属性集合可能有多个约简。v属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属性D有相同的分类能力。v属性集合P的所有约简的交集定义为P的核(Core)，记作core(P)，核是表达知识必不可少的重要属性集。v核的概念具有两方面的意义:v(l)因为核包含于所有约简之中，所以核可以作为所有约简的计算基础。v(2)核在知识约简中是不能消去的特征集合。v直接由分辨矩阵来求取系统的核集Pc。不失一般性,假定系统T 对于属性集P 是可分辨的。则系统的核集由以下定理1确定。v定理定理11-111-1P 中任一属性P Pc,充要条件为:D(P)中至少存在一个元素 ,满足 。其中，元素都是属性集P的一个子集，元素Dij定义如下：v 其中i,j=1,2,3,，m。（1）v （2）ijD (P)ijkD (P)=P ijDijij1ij2ij3ijnD=d,d,d,d ijk,d=1,2,3,.,ikjkkikjkUUknP UUv命题命题11-111-1从信息系统的决策表中将属性集P中逐一移去,每移去一个属性即刻检查其决策表,如果不出现新的不一致,则属性是可被约去的；否则属性不能约去。v命题命题11-211-2 全体不可约去属性集称为核集。v属性集合的约简和核的关系如下:v式中red(P)表示P的所有约简。core(P)含有P的全部约简中共同的等价关系，是属性集合P中不可缺少的重要属性集。core(P)=red(P)v属性约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类产生的影响也不同。v例如，判断人的体形(瘦、中、胖)时，体重是主要属性。但若体重属性值为75Kg时，此人的体形要结合其身高、性别等属性才能确定。如果体重属性值为160Kg时，几乎肯定其体形为胖，这时身高、性别已不重要。v命题11-3设 是决策表上的一条决策规则,属性值v 是一可被约去当且仅当 ,其中 和 均为决策表上的逻辑公式8。()(-v)v决策表包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，是领域知识的载体。v知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。v从决策表分析得到的规律性知识，通常采用决策规则的形式记录下来。下面给出决策规则的形式化描述。v定义定义11-1311-13定义公式如下：v(1)(a,v)(或写为av，aA，vVa，表示属性a的取值为v)是公式且是原子公式。v(2)如果A和B都是公式，那么 ,AB都是公式。v(3)只有按定义(1)和(2)所组成的式子是公式。v对于决策表 是决策表，A=CD属性集合，子集 和 分别为条件属性集和决策属性集，有关决策规则的定义如下：T=(U,P,C,D)A,A B,A B,(A)iC=c|i=1,2,njD=d|j=1,2,mv定义定义11-1411-14公式 称为P基本公式，这里 ，P，。v定义定义11-1511-1511公式 称为Q基本公式，这里 ，。v定义定义11-1611-1611公式AB为决策规则，如果A是P基本公式且B是Q基本公式，则AB是基本决策规则。1122nn(c,v)(c,v)(c,v)iicvV12nc,c,c PC1122mm(d,v)(d,v)(d,v)jjdvV12md,d,d Q,QDv可辨识矩阵（也称分明矩阵）是由波兰数学家Skowron.A教授提出的。v定义定义11-1711-17设相容决策表T=，A=CD，和D=d分别为条件属性集和决策属性集，是论域，是样本 在属性上的取值。表示可辨识矩阵中第i行j列的对象，则可辨识矩阵定义为：其中，iCc|i=1,2,m12U=x,nxxijc(x)jxDM(i,j)kkjijDijc|cC()(x),d(x)d(x)M(i,j)=0 ,d(x)d(x)kikcxc,1,2,i jnv由上述定义可以看出，可辨识矩阵是一个对称矩阵。当两个样本的决策属性取同时，对象值为0；当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同的条件属性集合。v一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，所有的蕴含式包含的属性就是决策表的所有约简集合。v算法算法11-111-1可辨识矩阵属性约简算法可辨识矩阵属性约简算法 v输入输入：相容决策表DT=，A=CD是属性集合；v输出输出：约简的属性集。v步骤：步骤：vStep1计算决策表的可辨识矩阵 ；/根据分辨矩阵的定义求元素vStep 2对于可辨识矩阵中所有取值为非空集合的对象 ，建立相应的析取逻辑表达式,v ,；DMijMijTijTiijcMicvStep 3将所有的析取逻辑表达式 进行合取运算，得一个合取范式T，即 ；vStep 4将合取范式L转换为析取范式的形式，得 ；vStep 5输出属性约简结果。v基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化 0TijMijTijTTiiTv信息熵是信息论的核心内容，它最早应用于通信领域。由于信息熵可以刻画信息划分粒度的大小，也被广泛应用于信息不确定性的度量。v设U为一个论域,可以认为U上任一属性集合(知识、等价关系簇)是定义在U上的子集组成的R代数上的一个随机变量,其概率分布可通过如下方法来确定。v定义定义11-1811-18设P,Q在U上导出的划分分别为X,Yv则P,Q在U的子集组成的代数上的概率分布为12,nXX XX12,mYY YY1212:()()()nnXXXXpp Xp Xp X1212:()()()mmYYYYpp Yp Yp Y其中，；v定义定义11-1911-19知识P的熵H(P)定义为 。(),1,2,iiXp XinU(),1,2,jjYp YjmU1()()log()niiiH Pp Xp X v定义定义11-2011-20决策信息系统S=(U,A=CD,V,F),C、D为U上的一个等价关系集合，C、D在U上导出的划分分别为:v则D相对于C的条件信息熵H(D|C)为：v其中，12U/IND(C)=,nXXX12U/IND(D)=,mY YYU/C/ii=11H(D|C)=-p(X)(|)log(|)U Djijijp YXp YX(|)jijiiYXp YXXv定理定理11-211-2在信息系统S=(U,A=CD,V,F)中，若H(D|B)=H(D|(B-b)则称b为B中相对于D是可省的（不必要的）；否则b为B中相对于D是不可省的。对 ,若其任一元素D都是必要的，则称B相对于D是独立的。v定义定义11-2111-21在决策信息系统S（U,A=CD,V,F）中，若 ,H(D|B)=H(D|C)且B相对与D是独立的，则称B是C关于D的属性约简。v推论推论11-111-1如果一个属性a不能为属性子集R的分类增加任何信息，即 ，就可以将这个属性约简。bBC BCBCH(D|R a)=H(D|R)v算法算法11-211-2信息熵的求核算法信息熵的求核算法v输入输入：相容决策表T=，A=CD是属性集合；子集 和D=d分别为条件属性集和决策属性集；v输出输出：信息熵定义下的核属性 ；v步骤：步骤：vBeginBegin (1)；v(2)对于条件属性集C中的所有属性r,如果H(D|C)H(D|C-r),则 ；End EndiCc|i=1,2,mDCO RE(C)DCORE(C)=DDCORE(C)=CORE(C)rCEBARKCC算法是一种比较典型的基于信息熵的属性约简算法。该算法是建立在决策属性集相对于条件属性集的条件熵的基础上的，以H(D|Ba)作为启发式信息，以H(D|B)=H(D|C)作为算法的终止条件。CEBARKCC算法以决策表核属性集为起点，逐次选择使H(D|Ba)最小的非核条件属性a添加到核属性集中，直到满足终止条件H(D|B)=H(D|C)v算法算法11-311-3CEBARKCCCEBARKCC算法算法v输入：输入：相容决策表T=，A=CD是属性集合；子集v 和D=d分别为条件属性集和决策属性集；v输出：输出：该决策表的一个相对约简B。v步骤：步骤：vStep1计算决策表S中决策属性集D相对条件属性集C的条件熵H(D|C)；vStep 2计算条件属性集C中相对于决策属性集D的核属性Co；vStep 3令B=C0iCc|i=1,2,m a 如果|B|!=0,则计算条件熵H(D|B),转d)；v b 对每个属性 ,计算决策属性集D相对条件属性集的条件熵 ；v c 选择使 c(若同时有多个属性达到则从中选取一个与B的属性值组合数最少的属性),；vd IF H(D|B)H(D|C)Then b)0icCC(|)iH D Bc(|)iH D Bc0CC iBBcv定义定义11-2211-22设S=(U,A=CD,V,F)是一个决策信息系统，其中C是条件属性集合，D是决策属性集合，且 ,则对于任意属性aC-R的重要度的定义为：v =,v其中 。RCSGF(a,R,D)=K(R a,D)-K(R,D)H(D|R)-H(D|Ra)RK(R,D)=POS(D)/()CPOS Dv算法算法11-411-4信息熵的属性约简改进算法信息熵的属性约简改进算法v输入：输入：相容决策表T=，A=CD是属性集合；v子集 和D=d分别为条件属性集和决策属性集；v输出：输出：决策表T的一个相对约简P。v步骤：步骤：vStep1计算决策表T中决策属性集D相对条件属性集C的条件熵H(D|C)；vStep 2计算条件属性集C中相对于决策属性集D的核属性Co；Step 3 计算条件信息熵H(D|P)，转Step 6；iCc|i=1,2,mvStep 4 对i=1.n,biB中的每个属性计算条件熵H(D|Pbi)，求vSGF（bi,P,D）=H(D|P)-H(D|Pbi)得到属性bi的重要度SGF（bi,P,D）；vStep 5选择使SGF（bi,P,D）最大的属性bi（若同时有多个属性达到最小值，则从中选取一个与P的属性值组合数最少的属性），把bi从B中删除，并把bi增加到P的尾部；同时从B中删除使SGF的值为零的属性bi；vStep 6如果H(D|P)H(D|C)Then Step 4 Step 7从P的尾部开始，从后向前判别每个属性的a是否可约。如果 ，则从a开始向前的属性都是核属性，不可约，算法终止；否则，如果H(D|P-a)=H(D|C)，则a是可约简的，把a从A中删除。Cacore(D)v例11-4：根据表11.5决策表所示，根据算法11-4进行信息熵的属性约简计算。表表11.5决策表决策表vU a b c d e fU a b c d e fve1 1 0 1 1 2 1ve2 0 0 1 1 1 0ve3 1 1 0 1 2 0ve4 0 1 0 1 1 1ve5 1 2 2 1 2 0ve6 2 1 0 1 0 1vStep1求出H(D|C)=0；vStep2利用求核算法求出 ；情形一：Step3求出H(D|P)=1;转Step 6,if H(D|P)H(D|C)Then Step4Step4SGF(a,P,D)=H(D)-H(D|a)=0.2075;SGF(b,P,D)=H(D)-H(D|b)=0.2075;SGF(c,P,D)=H(D)-H(D|c)0.2075;SGF(d,P,D)=H(D)-H(D|d)=0;SGF(e,P,D)=H(D)-H(D|e)=0.2705;P=a,B=b,c,e;Step5 选择属性a同时删除不必要的属性d。00C=;P=C;B=a,b,c,d,e情形二：Step3 H(D|P)=0.7925;转Step 6,if H(D|P)H(D|C)Then Step4Step4 SGF(b,P,D)=H(D|a)-H(D|a,b)=0.7925;SGF(c,P,D)=H(D|a)-H(D|a,c)=0.7925;SGF(e,P,D)=H(D|a)-H(D|a,e)=0；P=a,b,B=c;Step5 选择属性b的同时删除不必要的属性e。H（D|P）=H（D|C）=0Step6 P中没有可删除属性。则相对约简集为P=a,b。v基于粗糙集理论的数据预处理方法，首先对原始数据（原始决策表）进行离散化，然后可以通过两种方法对离散化的决策表进行属性约简，最后进行属性值的约简。我们以一个医疗数据记录决策表为例子，给出属性约简求核和属性值约简的过程。v本节介绍属性约简的两种方法：分辨矩阵求核约简方法、直接求核集方法。v方法一，分辨矩阵求核约简方法方法一，分辨矩阵求核约简方法：设D是一个m*m阶矩阵，其中每一个元素Dij都是P的一个子集，元素Dij定义如下：vDij=dij1,dij2,dij3,dijn v 其中i,j=1,2,3,，m。(1)(2)v说明：U,U表示决策表中第i行和第j行两个属性的值；k表示决策表的研究对象的个数，分辨矩阵D是一个对角线为0的对称矩阵。ijk,d=1,2,3,.,ikjkkikjkUUknP UUv方法二，直接求核集方法方法二，直接求核集方法：用命题11-1、命题11-2直接求核集。例例11-311-3以下决策表11.2给出了一个医疗数据记录表，通过测量人的体温、咳嗽、头痛、周身痛等症状来确定是否患了流感。表表11.2医疗记录表医疗记录表v U U 体温体温 咳嗽咳嗽 头痛头痛 周身痛周身痛 流感流感v1 正常 无 无 有 无v2 正常 无 有 无 无v3 偏高 无 有 无 有v4 高 有 有 无 有v5 高 有 无 无 有v6 偏高 有 有 无 有v其中属性及属性值的含义为：v体温a，正常0，偏高1，高2；咳嗽b，无0，有1；头痛c,无0，有1；周身痛d，无1，有1；流感e，无0，有1。v表表11.3医疗决策表医疗决策表vU a b c d eU a b c d ev1 0 0 0 1 0v2 0 0 1 0 0v3 1 0 1 0 1v4 2 1 1 0 1v5 2 1 0 0 1v6 1 1 1 0 1v其中：条件属性集为a,b,c,d，决策属性集为e。根据粗糙集理论对表11.3医疗决策表进行数据预处理，处理过程分两个步骤进行，一是对决策表条件属性集进行约简求核；二是对条件属性值进行约简。v下面讨论属性约简求核的两种方法：分辨矩阵直接求核约简法和用命题11-1、命题11-2求核约简法。v首先，用分辨矩阵直接求核集。用以下举例说明分辨矩阵求核约简的方法，如表11.3医疗决策表所示是一个知识系统，U=U1,U2,，Un是论域，C=a,b,c,d 是条件属性集，D=e 是决策属性集，。则其相应的分辨矩阵为：vD=acacbabcababeabceabeaeabcdeabdeabcdeacdecdv从上述分辨矩阵中可以得出：由于D=e是决策集，不需要约简，约简的是条件集合C，根据定理11-1直接求出该知识系统的核集为 a,b,c。该约简求核集的方法便于计算机上实现。v其次，用方法二直接求核集集。还是以决策表11.3作为知识系统的例子，求核集的步骤为：v（1）去掉属性a,对比每一行属性值，第4、6行发生冲突，则属性a不可约；v（2）去掉属性b,对比每一行属性值，第4、6行发生冲突，则属性b不可约；v（3）去掉属性c,对比每一行属性值，第4、5行发生冲突，则属性c不可约；v（4）去掉属性d,对比每一行属性值，没有发生冲突，则属性d可约；v若还有条件属性，则依次类推。经过约简后得到的核集为a,b,c。v比较两种求核集的方法，对于数据量大，采用分辨矩阵来求核集，方便计算机来实现；第二种方法简单易行，方便人工处理。v 属性值约简是在核集基础上进行的，经约简后的核集用表11.4医疗核集决策表表示如下：表表11.4医疗核集决策表医疗核集决策表 U a b c eU a b c e1 0 0 0 01 0 0 0 02 0 0 1 02 0 0 1 03 1 0 1 13 1 0 1 14 2 1 1 14 2 1 1 15 2 1 0 15 2 1 0 16 1 1 1 16 1 1 1 1根据命题11-3计算决策规则中条件属性的核值,并确定出一个最小决策算法，用逻辑语义表示。v对于决策规则1，1a=1,2,1b=1,2,3,1c=1,5,1e=1,2v其中：1a 1b=1,21,2,3=1,2 1e，则c0（表示c属性值为0）可约；v1a 1c=1,2 1,5=1 1e,则b0（表示b属性值为0）可约；v1b 1c=1,2,31,5=1 1e,则a0（表示a属性值为0）可约；v对于决策规则2，2a=1,2,2b=1,2,3,2c=2,3,4,6,2e=1,2v其中：2a 2b=1,2 1,2,3=1,2 2,则c1是可约的；v 2a 2c=1,2 2,3,4,6=2 2,则b0是可约的；v 2b 2c=1,2,3 2,3,4,6=2,3 2,则a0不可约；v其逻辑语义表示为：a0b0Va0c1e0v同理，决策规则3推出：a1不可约，b0可约,c1不可约，其逻辑语义为：a1b0Va1c1Vb0c1e1v决策规则4推出：a1,b1,c1均可约；v决策规则5推出：a2,b1,c0均可约；v决策规则6推出：a1,b1,c1均可约。v经过上述属性和属性值的约简，得到了最小决策算法，它 的 逻 辑 语 义 为：a0b0Va0c1-e0和a1b0Va1c1Vb0c1-e1。相应的自然语言的语义是体温正常且不咳嗽或者体温正常且头痛的不患流感；体温偏高且不咳嗽或者体温偏高且头痛或者不咳嗽且头痛的患流感。v数据表示方法越明显，冗余数据越少，神经网络就越容易学习；神经网络的神经元节点个数越多，权值的个数越多，则它的训练时间就越长，而且神经网络的泛化能力就越差。v通过粗糙集对数据进行约简，用约简后的数据集作为BP神经网络的设计依据及训练数据。这样得到的训练数据表示清晰，从而使得两种方法进行互补，既能利用粗糙集约简数据，减少BP神经网络训练时间，又能利用BP神经网络降低噪声影响。v一方面提高了数据的代表性，减少了噪声的干扰，使训练出来的神经网络不容易出现过配现象；另一方面减少了训练数据，使训练时间得以减少，提高了效率。v算法算法11-511-5粗神经网络算法粗神经网络算法 v输入：输入：输入离散型决策表；v输出：输出：输出决策结果。v步骤：步骤：vStep1:确定问题:首先要对待解决的问题做出详细的调研，明确目标，然后考虑如何引入粗糙集从而更好地解决该问题。vStep2:采集数据，对原始数据进行收集。vStep3:数据处理:把要处理的数据建立成一张决策表，即一张二维表格，每一行描述一个对象，每一列描述对象的一种属性。在这一部分中，如果无法得到完备的数据表，就有必要将信息表进行完备化操作;如果初始数据是连续值，还要经过连续属性离散化操作。vStep4:根据粗糙集理论对数据进行属性约简，去掉数据表中的冗余条件属性，同时消去重复的样本并处理矛盾的样本。属性约简有多种方法，我们可以利用属性重要度消去不重要的属性。vStep5:根据训练数据样本设计神经网络。即根据约简结果确定神经网络的输入层单元数和隐含层节点数。vStep6:用约简后形成的学习样本对神经网络进行学习，得到神经网络的权值。然后将测试样本输入网络进行测试。vStep7:输出最终结果。开始数据采集训练集预处理约简集神经网络设计神经网络训练测试集输入离散决策表粗神经网络输出结果图11-1粗神经网络算法流程粗神经网络算法流程图如图11-1所示v粗糙集在机器学习、决策支持系统、机器发现、归纳推理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。它的算法简单、易于操作，应用粗糙集的属性约简可以有效地去除冗余的属性，对于每个属性的值域出现冗余，同样可以应用粗糙集方法中的属性值约简删除某些属性的多余值，从而使条件属性的个数和取值得到约简。v本章首先简单介绍粗集理论的发展过程及其在各领域中的应用。v然后介绍粗糙集理论的基本概念，主要包括知识表达系统、决策表、可辨识矩阵属性约简、属性值约简、信息熵的属性约简的基本概念及其相关算法，最后通过例子介绍粗糙集理论在数据挖掘及数据预处理中的具体应用。v1 高晓康.粗糙集理论研究及其在工程和医学诊断中的应用.同济大学工学博士学位论文2007,24-26.v2黄丽萍.基于粗糙集的属性约简与规则提取.厦门大学硕士学位论文，2007,13-14.v3张静.基于粗集理论的数据挖掘方法及应用研究.大连理工大学硕士论文,2007,17-19.v4 唐建国,谭明术.粗糙集理论中的求核与约简J.控制与决策,2003,18(4):449-452.v5 陈晓红,陈岚.基于粗糙集理论的知识约简及应用实例J.大学数学,2003,19(4):68-73.v6 瞿彬彬.基于粗糙集理论的决策信息系统知识获取研究.华中科技大学博士论文，2006，2006,26-28.v v7韩祯祥,张琦,文福拴.粗糙集理论及其应用综述J.控制理论与应用,1999,16(2):1532157.v8 曾黄麟.粗糙集理论及其应用(修订版)M.重庆:重庆大学出版社,1998.v9 谢祥云,吴明芬.Pawlak 粗代数理论研究综述J.计算机科学,2002,29(5):76-79.v10徐泽柱，王林.基于粗糙集理论和BP神经网络的数据挖掘算法.计算机工程与应用，2004，(31):169一175.v11 张文修,吴伟志,梁吉业等.Rough Set理论与方法.北京:科学出版社，2001.1-223v12王国胤.Rough Set理论与知识获取.西安:西安交通大学出版社，2001.1-226 谢谢