第10章--粗糙集理论-数据挖掘：概念与技术-教学1课件.ppt

第10章 粗糙集理论 参考书：1 20042 2008n 粗 糙 集 理 论 是 由 波 兰 华 沙 理 工 大 学Pawlak 教 授 于20世 纪80年 代 初 提 出 的 一 种 研 究 不 完 整、不 确 定 知 识 和 数 据 的 表 达、学 习、归 纳 的 理 论 方 法，它 是 一 种 刻 画 不 完 整 性 和 不 确 定性 的 数 学 工 具，能 有 效 地 分 析 不 精 确、不 一 致、不 完 整 等各 种 不 完 备 的 信 息，还 可 以 对 数 据 进 行 分 析 和 推 理，从 中发现隐含的知识，揭示潜在的规律。n 粗 糙 集 在 机 器 学 习、决 策 支 持 系 统、机 器 发 现、归 纳 推 理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。n 粗 糙 集 理 论 逐 渐 应 用 于 数 据 挖 掘 领 域 中，并 在 对 大 型 数 据 库 中不 完 整 数 据 进 行 分 析 和 学 习 方 面 取 得 了 显 著 的 成 果，使 得 粗 糙集 理 论 及 数 据 挖 掘 的 研 究 成 为 热 点 领 域。最 近 几 年，粗 糙 集 理论 越 来 越 受 到 众 多 研 究 人 员 的 重 视，它 的 应 用 研 究 得 到 了 很 大的发展。n 粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。数据规则精确的数学方法10.1粗糙集基本概念 粗糙集理论是在经典集合论基础上发展而来的。利用不确定性、不完整的经验知识进行推理。知识库1.知识的分类表达形式集合理论为描述世界中各种事件提供了一个十分有用的基础，千差万别的事物都可以用集合论的方法加以描述。知识表达系统采用集合表达。知识分类 利用事件不同的属性的知识描述，对事物可以产生不同的分类。定义，知识表达系统（知识库）M 可以形式化表达为四元组：M=(U,A,V,f)，其中U 为对象非空有限集合，称为论域；A 为属性的非空有限集合，A=A1,A2,Am；V=Vi，Vi是属性Ai的值域；f：UAV 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即aA，xU，f(x,a)Va。知识表达系统称为（或信息表），其数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。一个信息表 U 颜色R1形状R2大小R31红色 圆形 小2蓝色 方形 大3红色 三角形 小4蓝色 三角形 小5黄色 圆形 小6黄色 方形 小7红色 三角形 大8蓝色 三角形 大下面的表是一个信息表的例子，是一个玩具积木的集合。其中：U=1,2,3,4,5,6,7,8，A=颜色,形状,大小，V颜色=红色,蓝色,黄色，V形状=圆形,方形,三角形，V大小=大,小。按颜色分类：1，3，7：红色积木2，4：蓝色积木5，6，8：黄色积木按形状分类：1，5：圆形积木2，6：方形积木3，4，7，8：三角形积木按大小分类：2，7，8：大积木1，3，4，5，6：小积木换言之，定义了三个等价关系(即属性)：颜色R1、形状R2和大小R3，通过这样的分类，可以得到以下三个等价类：U/R1=1,3,7，2,4，5,6,8U/R2=1,5，2,6，3,4,7,8U/R3=2,7,8，1,3,4,5,6这些等价类是知识库K=(U,R1,R2,R3)中的初等概念。所以：基于R1的初等概念有：1,3,7：红色积木2,4：蓝色积木5,6,8：黄色积木基于R2的初等概念有：1,5：圆形积木2,6：方形积木3,4,7,8：三角形积木基于R3的初等概念有：2,7,8：大积木1,3,4,5,6：小积木U 颜色R1形状R2大小R31红色 圆形 小2蓝色 方形 大3红色 三角形 小4蓝色 三角形 小5黄色 圆形 小6黄色 方形 小7红色 三角形 大8蓝色 三角形 大2.不可分辨关系 n 在粗糙集理论中，“知识”被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。n 假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，如果两个对象(或对象集合)具有相同的属性和属性值，则它们之间具有不可分辨关系。n 定义 设U 是一个论域，R 是U 上的等价关系，U/R 表示U 上由R 导出的所有等价类。表示包含元素xU 的R 等价类。一个知识库就是一个关系系统K，其中U 是论域，P 是U 上的一个等价类簇。如果 且，则（Q 的所有等价类的交也是一个等价关系）称Q 为不可分辨关系,记作IND(Q)。IND(Q)=(x,y)|所有的a Q，f(x,a)=f(y,a)其中，x、y 为知识库中的记录或对象，Q 是属性对应的等价类。简记为U/QU/Q=xQ|x Ux元素的等价类U/R1,R3=1,3,2,7,4,5,6,8U/R2,R3=1,5,2,3,4,7,8,6U/R1,R2,R3=1,2,3,4,5,6,7,8不可分辨关系U 颜色R1形状R2大小R31红色 圆形 小2蓝色 方形 大3红色 三角形 小4蓝色 三角形 小5黄色 圆形 小6黄色 方形 小7红色 三角形 大8蓝色 三角形 大关系R 的粒（初等概念），其他知识都是由粒构成的。10.1.2集合近似与粗糙概念n 给定论域U，一簇等价关系R 将U 划分为互不相交的基本等价类U/R。n 当能表达成某些基本等价类（初等概念）的并集时，称为可定义的；否则称为不可定义的。R 可定义集能在这个知识库中被精确地定义，所以又称为R 精确集。n R 不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为R 粗糙集（Rough set）。1.集合的近似与粗糙集U R1 12 23 34 15 26 47 28 1初等概念：U/R=1,4,8,2,5,7,3,6集合X=2,3,5,7 是R 精确集。集合Y=1,7 是R 粗糙集。不能由任何分类得到。2,5,7 3信息粒知识库的等价性设K=(U,P)和K=(U,Q)为两个知识库，当：U/P=U/Q则两个知识库K 和K 是等价的。若U/P U/Q，则称知识P 比知识Q 更精细。含义是什么？n 粗糙集的上近似集（UpperApproximation）和下近似集（LowerApproximation）来近似地定义粗糙集。n 粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。2.上、下近似集定义设集合X U，R 是一个等价关系，并且有：U/R=y1,y2,yn，则：l 集合X 的R 下近似集：R_(X)=yiU|IND(R):yiXl 集合X 的R 上近似集：R(X)=yiU|IND(R):yiXlX 的R 边界域：BNR=R(X)-R_(X)lX 的R 正域：POSR(X)=R_(X)l 为X 的R 负域：NEGR=U-R(X)R(X)R(X)下近似、正域：表示X 划入U/R 的初等范畴的情况。或者用U/R 的初等范畴表示X 的情况。yesyes/nono x1,x6 x3,x4 x2,x5,x7R_(X)R(X)X=x|Walk=yes=x1,x4,x6U集合U/RR:属性子集R_()R()所有分类都是相对R 而言的，U/R 或R 就是一种知识。IND(R)n 例如，设论域，U 上的一族等价关系R=R1,R2,R1和R2是两个等价关系。根据这两个等价关系可以将论域U 进行划分：n 和 U/R1中的，代表 的等价类。n 论域U 被R 划分的基本等价类为:n 集合 是U 上的一个子集。则X 无法用基本等价类U/R 的并集精确表示，所以X 是U 上的一个粗糙集合。故有:n X 的下近似集为:；n X 的上近似集为:；n X 的负区域:。集合X=2,3,5,7 是R 精确集。集合Y=1,7 是粗糙集。如何计算？U a1 12 23 34 15 26 47 28 1U/R=1,4,8,2,5,7,3,6R(X)=yiU|IND(R):yiX=y2y3=2,3,5,7R_(X)=yiU|IND(R):yiX=y2y3=2,3,5,7NEGR(X)=，所以X 是精确的。IND(R)y1 y2 y3 y4R(Y)=yiU|IND(R):yiY=y1y2=1,4,8,2,5,7R_(X)=yiU|IND(R):yiX=NEGR(X)，所以X 是粗糙的。R=a定理：（1）R_(X)X R(X)（2）R(X Y)=R(X)R(Y)（3）R_(XY)=R_(X)R_(Y)（4）X Y R_(X)R_(Y)例如，设某知识库K=(U,R),其中U=x1,x2,.,x8,一个等价关系R 定义分类对象的等价类如下:y1=x1,x4,x8,y2=x2,x5,x7,y3=x3,y4=x6对于集合X1=x1,x4,x5,则:dR(X1)=0/6=0，rR(X1)=1。表示根据R 的基本集合描述集合X1的近似精度为0，粗糙度为1。对于集合X2=x3,x5,则:dR(X2)=1/4，rR(X2)=3/4。表示根据R 的基本集合描述集合X2的近似精度为0.25，粗糙度为75%。10.2.1.知识的简化定义，给定知识库K=(U,R)，定义一个等价关系R，有属性r R，若存在：IND(R)=IND(R-r)称属性r 为R 中可省略的。对于任一r R，若R 不可省略，则称R 是独立的。10.2 知识库的简化表示删除属性r，不影响记录之间的区分（分辨）。U a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 16 4 2 37 4 3 28 2 3 2一个知识表除掉属性b：U/R=1,2,3,4,5,6,7,8U/R-b)=1,2,3,4,5,6,7,8U/R 等于U/R-b)，属性b 是可省略的定义，对于属性子集P R，若存在Q=P-r，且IND(Q)=IND(P)，且Q 为最小子集，则Q 称为P 的简化，用red(P)表示。一个属性集合P 可能有多种简化。P 中所有简化属性集中都包含的不可省略关系的集合，即简化集red(P)的交称为P 的核。记作core(P)。core(P)=red(P)U a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 16 4 2 37 4 3 28 2 3 2一个知识表除掉属性a：U b c1 1 22 3 13 1 34 3 35 2 16 2 37 3 28 3 2U/R=1,2,3,4,5,6,7,8U/R-a)=1,2,3,4,5,6,7,8U/R 不等于U/R-a),属性a是不可省略的U a c1 1 22 2 13 3 34 1 35 1 16 4 37 4 28 2 2除掉属性b：U/R=1,2,3,4,5,6,7,8U/R-b)=1,2,3,4,5,6,7,8U/R 等于U/R-b),属性b是可省略的U a b1 1 12 2 33 3 14 1 35 1 26 4 27 4 38 2 3除掉属性c：U/R=1,2,3,4,5,6,7,8U/R-c)=1,2,8,3,4,5,6,7U/R 等于U/R-c),属性c 是不可省略的则：redR=a,c，core(R)=a,c。n 核的概念具有两方面的意义:（1）因 为 核 包 含 于 所 有 约 简 之 中，所 以 核 可 以 作 为 所有约简的计算基础。（2）核在知识约简中是不能消去的特征集合。可以直接由分辨矩阵来求取系统的核集Pc。不失一般性,假定系统T 对于属性集P 是可分辨的。则系统的核集由以下定理确定。分辨矩阵定义：设U=x1,x2,xn，分辨矩阵D=dijdij=当i=j 时ak当ij，且xi和xj在属性ak上不相同时分辨函数f(D)=所有非空项的合取求出最简合取范式，得到所有属性约简，U a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 16 4 2 37 4 3 28 2 3 2D=1 2 3 4 5 6 7 8 abc ac bc bc abc ab ab abc ac ab abc ac c ab abc ab abc abc bc ab ac ac ac abc abc bc abc a利用分辨矩阵求核：f(D)=(abc)(ac)(bc)(abc)=ac。core(R)=a,c。一个属性约简核是分辨矩阵中所有单个元素组成的集合。12345678约简的含义U a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 16 4 2 37 4 3 28 2 3 2U a c1 1 22 2 13 3 34 1 35 1 16 4 37 4 28 2 2等价例如，一个信息表如下：U a b c d1 0 1 2 02 1 2 0 23 1 0 1 04 2 1 0 15 1 1 0 2分辨矩阵：1 2 3 4 512 abcd3 abc bcd4 acd abd abcd5 acd b bcd adf(D)=(abc d)(abc)(ac d)(ac d)(bc d)(abd)b(abc d)(bc d)(ad)=(a b)(b d)两个约简a,b 和b,d，核为b。求解f(D)可以得到所有的约简和核NP 问题，即m 个属性其时间复杂度为O(2m)。10.3决策表 决 策 表 包 含 了 某 一 领 域 的 大 量 数 据，是 领 域 的 样 本数 据 库。它 记 录 了 大 量 样 本 的 属 性 值 和 决 策 情 况，是 领域知识的载体。知 识 获 取 的 目 的 就 是 要 通 过 分 析 这 个 实 例 库 来 得 到该 领 域 中 有 用 的、规 律 性 知 识。决 策 表 在 决 策 应 用 中 有十 分 重 要 的 地 位，可 用 于 表 达 绝 大 多 数 决 策 问 题。对 于决策表，最重要的是决策规则的生成。数据库决策表规则在信息表（知识库）上指定条件属性集合C 和结论（决策）属性集合D，这样就构成了决策表。利用粗糙集理论进行数据挖掘的过程决策表决策表规则属性约简值约简10.3.1 知识的相对简化一个分类相对另一个分类的正域。定义，给定决策表T=(U,R)，等价关系R 的子集C和D，定义D 的C 正域POSC(D)为：POSC(D)=C(X)，X U/DU 的所有D 分类（U/D）划入到U 的C 分类（U/C）的情况。U a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 16 4 2 37 4 3 28 2 3 2一个决策表：设C=a,b，D=c，求POSC(D)=?U/D=1,7,8,2,5,3,4,6U/C=1,2,8,3,4,5,6,7C_(1,7,8)=1,7C_(2,5)=5C_(3,4,6)=3,4,6POSC(D)=1,7 5 3,4,6=1,3,4,5,6,7 POSC(D)的含义是什么？U 对于属性集合D 有一个分类U/D。U 对于属性集合C 有一个分类U/C。POSC(D)表示这两种分类之间的关系。表示U/D 的分类在U/C 中的不确定性。如果POSC(D)=U，表示两种分类是一致的。U/CU/DPOSC(D)U/C、U/D 均为知识，知识之间通过POSC(D)关联，构成一种知识体系结构。知识5 知识6知识7知识8知识2知识3知识4知识1知识体系结构粒计算的研究方向之一定义C D 依赖性度量：设(U,C D)是一个决策表。10.3.2 知识的依赖性和属性的重要性k可以看成D 和C 之间依赖性的量度，也可解释为对对象的分类的能力。当k=1 时，则U 的全部记录都可以通过知识C 划入U/D的初始概念。当k1 时，只有属于正域的记录可以通过知识C 划入U/D 的初始概念。一个汽车决策表：U条件属性 决策属性类型a 机型b 颜色c 速度d 加速e1中 柴油 灰色 中 差2小 汽油 白色 高 极好3大 柴油 黑色 高 好4中 汽油 黑色 中 极好5中 柴油 灰色 低 好6大 混合 黑色 高 好7大 汽油 白色 高 极好8小 汽油 白色 低 好U/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8C_(1)=，C_(2,7)=7，C_(3,6)=3,6C_(4)=4，C_(5,8)=，POSC(D)=7 3,6 4=3,4,6,7k=|POSC(D)|/|U|=4/8=0.5。两者之间的依赖度为50。也就是说，由类型、机型和颜色可以50来确定速度和加速属性。定义，属性a的重要性度量：Ia(S)=rR(S)-rR-a(S)，其中S 为属性a的分类结果设(U,C D)是一个决策表。一个决策表如下，求属性a、b、c 的重要性？U条件属性 决策属性a b c d e1 2 2 1 0 02 1 1 3 0 13 3 1 2 1 14 2 2 2 1 05 2 1 1 1 26 3 3 2 1 17 3 2 3 0 18 1 2 3 1 2U/a,b,c=1,2,3,4,5,6,7,8，U/d,e=1,2,7,3,6,4,5,8，POSC(D)=1,2,3,4,5,6,7,8，POSC-a(D)=1,2,3,4,5,6,7,8POSC-b(D)=3,4,6,7，POSC-c(D)=2,3,5,6,7,8，Ia(D)=8/8-8/8=0；Ib(D)=8/8-4/8=0.5；Ic(D)=8/8-6/8=0.125。属性a最不重要，可以删除，属性b最重要。10.3.3 属性约简、核集的求取 n 所 谓 属 性 约 简，就 是 在 保 持 知 识 库 分 类 能 力 不 变 的条件下，删除其中不相关或不重要的属性。n 一个属性集合可能有多个约简。n 属 性 约 简 的 目 标 就 是 要 从 条 件 属 性 集 合 中 发 现 部 分必 要 的 条 件 属 性，使 得 根 据 这 部 分 条 件 属 性 形 成 的相 对 于 决 策 属 性 的 分 类 和 所 有 条 件 属 性 所 形 成 的 相对 于 决 策 属 性 的 分 类 一 致，即 和 所 有 条 件 属 性 相 对于决策属性D 有相同的分类能力。设T=(U,C D)是决策表，如果有：POSC(D)=U则决策表T 是协调的或一致的；否则称T 为不协调的决策表。对于不协调的决策表，不能由条件属性导出结论属性之间的关系，应将其分解为完全协调和完全不协调的两个决策表。1.协调的决策表U条件属性 结论属性头疼 肌肉疼 体温 流感1是 是 正常 否2是 是 高 是3是 是 很高 是4否 是 正常 否5否 否 高 否6否 是 很高 是设C=头疼,肌肉疼,体温，D=流感U/流感=1,4,5,2,3,6U/头疼,肌肉疼,体温=1,2,3,4,5,6POSC(D)=C(1,4,5)C(2,3,6)=1,4,5 2,3,6=1,2,3,4,5,6 U该决策表是协调的。定义，设T=(U,C D)是决策表，如果去掉条件属性c，得到的表T1=(U,C c,D)与表T 相比，有：POSC-c(D)=POSC(D)则称条件属性c 是关于D 可省的，否则称条件属性c 是关于D 不可省的。决策表T决策表T1删除条件属性c 并合并记录2.条件属性的可省略性n 定义，如果决策表T 中每个条件属性都是关于D 不可省的，则称条件属性集C 是关于D 独立的，否则称C 是关于D 依赖的。n 定义，决策表T=(U,C D)中条件属性集C 的一个子集B 是关于D 独立的，并且POSB(D)=POSC(D)，则称B 是C 的一个D 属性约简。U a b c d e1 1 0 2 2 02 0 1 1 1 23 2 0 0 1 14 1 1 0 2 25 1 0 2 0 16 2 2 0 1 17 2 1 1 1 28 0 1 1 0 1一个决策表：C=a,b,c，D=d,eU/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8POSC(D)=3,4,6,7rC(D)=4/81，不是协调的。DesC(1)=1,0,2 DesD(1)=2,0DesC(5)=1,0,2 DesD(5)=0,1DesC(2)=0,1,1 DesD(2)=1,2DesC(8)=0,1,1 DesD(8)=0,1矛盾矛盾分解为如下两个表：U a b c d e3 2 0 0 1 14 1 1 0 2 26 2 2 0 1 17 2 1 1 1 2完全协调的决策表U a b c d e1 1 0 2 2 02 0 1 1 1 25 1 0 2 0 18 0 1 1 0 1完全不协调的决策表DesC(x)表示元素x的条件属性值。DesD(x)表示元素x的决策属性值。U a b c d e3 2 0 0 1 14 1 1 0 2 26 2 2 0 1 17 2 1 1 1 2完全协调的决策表U/C=3,4,6,7，U/D=3,6,4,7POSC(D)=3,4,6,7，rC(D)=4/4=1，数据是协调的。U/(C-a)=3,4,6,7，POSC-a(D)=3,4,6,7,rC-a=1，是协调的。U/(C-b)=3,6,4,7，POSC-b(D)=3,4,6,7,rC-b=1，是协调的。U/(C-c)=3,4,6,7，POSC-c(D)=3,4,6,7,rC-c=1，是协调的。U/(C-a,b)=3,4,6,7，POSC-a,b(D)=7,rC-a,b=1/4，是不协调的。U/(C-b,c)=3,6,7,4，POSC-b,c(D)=4,rC-b,c=1/4，是不协调的。U/(C-a,c)=36,4,7，POSC-a,c(D)=3,6,rC-a,c=2/4，是不协调的。所以a,b、a,c、b,c 都是不可省略的，则：redC(D)=a,b,a,c,b,c。10.4 常用的属性约简算法 对于决策表中的每一个条件属性a进行如下过程，直到条件属性集合不再发生变化为止。如果删除该属性a 使得POSC-a(D)=POSC(D)，则说明该属性是相对决策属性D 不必要的，从 决策表中删除该属性所在的列并将重复的行进行合并；否则，说明该属性是相对决策属性d 必要的，不能删除。10.4.1 一般属性约简算法算法描述:10.4.2 基于可辨识矩阵属性约简算法 n 分辨矩阵（也称分明矩阵）是由波兰数学家Skowron.A教授提出的。n 定义，设相容决策表T=，U=x1,x2,xn，C=ci|i=1,2,m 和D=d 分别为条件属性集和决策属性集。分辨矩阵定义为：dij 当d(xi)=d(xj)ck|ck(xi)ck(xj)当d(xi)d(xj)和信息表求分辨矩阵有什么不同？U条件属性 结论属性a b c1 1 1 22 2 3 13 3 1 34 1 3 35 1 2 1一个决策表求分辨矩阵：1 2 3 4 51 ab a b b2 ab a3 ab4 b5n 由上述定义可以看出，分辨矩阵是一个对称矩阵。当两个样本的决策属性取同时，对象值为；当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同的条件属性集合。n 一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，所有的蕴含式包含的属性就是决策表的所有约简集合。算法分辨矩阵属性约简算法 输入：相容决策表DT=；输出：约简的属性集。步骤：（1）计算决策表的分辨矩阵；/根据分辨矩阵的定义求元素（2）对于可辨识矩阵中所有取值为非空集合的对象，建立相应的析取逻辑表达式。（3）将所有的析取逻辑表达式进行合取运算，得一个最简合取范式T。（4）将合取范式T 转换为析取范式的形式。（5）输出属性约简结果。基于分辨矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化。一个气象决策表U条件属性 结论属性天气a 温度b 湿度 c 有风否d e1 1 1 1 0 N2 1 1 1 1 N3 2 1 1 0 P4 3 2 1 0 P5 3 3 2 0 P6 3 3 2 1 N7 2 3 2 1 P8 1 2 1 0 N9 1 3 2 0 P10 3 2 2 0 P11 1 2 2 1 P12 2 2 1 1 P13 2 1 2 0 P14 3 2 1 1 NU/C=1,2,3,4,5,6,7,8,9,10,11,12,13,14U/D=1,2,6,8,14,3,4,5,7,9,10,11,12,13POSC(D)=1,2,3,4,5,6,7,8,9,10,11,12,13,14=U，是协调的。1 2 3 4 5 6 7 8 9 10 11 12 13 141 a ab abc abcd bc abc bcd abd ac2 ad abd abcd abc bcd abcd bc ab acd3 abcd ab abd4 bcd ab d5 d ac bcd6 a ad bd ab abd abd7 abcd abc8 bc ac cd cd abc9 abcd10 cd11 ac12 ad13 abcd14分辩矩阵：d1,3=a,d2,3=add1,4=abf(D)=d1,3d2,3a1,4=(abd)(ac d)两个约简为a,b,d 和a,c,d，核为a,d。约简结果1：a,b,dU条件属性 结论属性天气a 温度b 有风否d e1 1 1 0 N2 1 1 1 N3 2 1 0 P4 3 2 0 P5 3 3 0 P6 3 3 1 N7 2 3 1 P8 1 2 0 N9 1 3 0 P10 3 2 0 P11 1 2 1 P12 2 2 1 P13 2 1 0 P14 3 2 1 N约简结果2：a,c,dU条件属性 结论属性天气a 湿度 c 有风否d e1 1 1 0 N2 1 1 1 N3 2 1 0 P4 3 1 0 P5 3 2 0 P6 3 2 1 N7 2 2 1 P8 1 1 0 N9 1 2 0 P10 3 2 0 P11 1 2 1 P12 2 1 1 P13 2 2 0 P14 3 1 1 N利用分辨矩阵求核在分辨矩阵中，所有单项属性构成决策表的核。1 2 3 4 5 6 7 8 9 10 11 12 13 141 a ab abc abcd bc abc bcd abd ac2 ad abd abcd abc bcd abcd bc ab acd3 abcd ab abd4 bcd ab d5 d ac bcd6 a ad bd ab abd abd7 abcd abc8 bc ac cd cd abc9 abcd10 cd11 ac12 ad13 abcd14上例的分辩矩阵：其中单项属性为a和d，则核为a,d设决策表中元素个数为n，求核的算法时间复杂度为O(n2)。10.4.3 归纳属性约简算法 算法描述：步骤1：求核COREC(D)；步骤2：求最小属性约简minC(D);（1）令X=COREC(D)，L=D-X=a1,a2,a3am，T(L)表示L 的幂集，Ti(L)为L 的i（1im）阶幂字集；（2）如果DOSX(D)=DOSC(D)，则minC(D)=X，转(10)；（3）i=1，Flag=0；（4）Y=Ti(L)；（5）任意取y Y，A=X y，计算POSA(D)=POSC(D)？若相等，则如果Flag=0，则Z=A，Flag=1；否则，如|U|Z|U|A|，则Z=A；（6）Y=Y-y;（7）如果Y0，转(5)；（8）如果Flag=1,则minC(D)=Z，转（10）;（9）i=i+1,如果im，则转（4）；（10）结束10.4.4 基于属性重要性的属性约简输入：决策表S=。输出：条件属性C 相对于决策属性D 的一个相对约简。（1）计算C 相对于D 的核COREC(D)；（2）令B=COREC(D)，如果，转到（5）（3）对于C-B 中的任一属性a，计算属性重要度sig(a,B)=(|POSB a(D)|-|POSB(D)|)/|U|求得最大重要性的属性a（若同时存在多个属性满足最大值，则从中选取一个与B 的属性值组合数最少的属性作为a），令B B a；（4）如果POSB(D)POSC(D)，转到（3），否则转到（5）；（5）输出，算法结束。算法描述：例如，一个决策表如下：U条件属性 决策属性a b c e d1 0 0 0 0 02 1 0 1 1 03 0 1 1 0 14 0 0 1 0 1求得COREC(D)=c令B=c，POSB(D)=1POSC(D)。R=C B=a,b,e，则：Sig(a,B)=3/4Sig(b,B)=1/4Sig(e,B)=3/4可选的属性有a和e，所以B=a,c 或e,c 有POSa,c(D)=POSC(D)和POSc,e(D)=POSC(D)输出B=a,c 或c,e 即为所给决策表的约简。10.4.5 基于信息增益的属性约简输入：决策表S=。输出：条件属性C 相对于决策属性D 的一个相对约简。（1）计算C 相对于D 的核COREC(D)；（2）令B=COREC(D)，如果POSB(D)=POSC(D)，转到（5）；（3）任意属性aC B，计算属性信息增益G(C,a)=E(C)-E(C,a)，求得G(C,a 最大的属性a（若同时存在多个属性满足最大值，则从中选取一个与B 的属性值组合数最少的属性作为a），令B=B a；（4）如果POSB(D)POSC(D)，转到第3步，否则转到第5步；（5）输出，算法结束。算法描述：例如，一个天气信息的决策表 论域U OutLook(a)Temperature(b)Humidity(c)Windy(e)决策属性(d)1 Sunny Hot High False N2 Sunny Hot High True N3 Overcast Hot High False P4 Rain Mild High False P5 Rain Cool Normal False P6 Rain Cool Normal True N7 Overcast Cool Normal True P8 Sunny Mild High False N9 Sunny Cool Normal False P10 Rain Mild Normal False P11 Sunny Mild Normal True P12 Overcast Mild High True P13 Overcast Hot Normal False P14 Rain Mild High True N经过数据预处理之后的决策表 U条件属性集 决策属性集a b c e d1 1 1 1 0 12 1 1 1 1 13 2 1 1 0 24 3 2 1 0 25 3 3 2 0 26 3 3 2 1 17 2 3 2 1 28 1 2 1 0 19 1 3 2 0 210 3 2 2 0 211 1 2 2 1 212 2 2 1 1 213 2 1 2 0 214 3 2 1 1 1该决策表的相对D 核是：CORE=a，e。开始进入算法核心处理流程令B=a,e，计算：POSB(D)=3,4,5,6,7,10,12,13,14POSC(D)=1,2,3,4,5,6,7,8,9,10,11,12,13,14两者不相等。求得条件属性集合中除了核值属性的剩下部分的属性为：C B=b,c，分别从该集合中选取属性，计算属性信息增益如下：G(C,b=0.8954314 G(C,c)=0.234103 于是，根据算法，优先选取信息增益度量值最大的那个属性，便是对决策属性的分类改变影响最大的条件属性，换句话说，这个条件属性对决策属性是重要的。在这里，我们选取c，将c 加入到核值属性集合中，进行测试。此时：B=B c=a,c,e。计算此时B 的相对正域，POSB(D)=1,2,3,4,5,6,7,8,9,10,11,12,13,14=POSC(D)输出B=a,c,e 即为决策表的一个相对约简。10.5值约简产生决策规则 属性约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类产生的影响也不同。例如，判断人的体形（瘦、中、胖）时，体重是主要属性。但若体重属性值为75Kg 时，此人的体形要结合其身高、性别等属性才能确定。如果体重属性值为160Kg 时，几乎肯定其体形为胖，这时身高、性别已不重要。U重量 性别 身高 体形1 160女180胖2 160男200胖3 if 重量=160 then 体形为胖n 命题设 是决策表上的一条决策规则,属性值v 是一可被约去当且仅当,其中 和 均为决策表上的逻辑公式。该命题说明一条决策规则的条件属性值可被约去当且仅当约去后仍然保持规则的一致性。例如，有一个决策表如下（没有多余的条件属性）：U a b c d e1 1 0 2 1 12 2 1 0 2 03 2 1 2 0 24 1 2 2 1 15 1 2 0 0 2产生如下决策规则：（1）a1b0c2d1e1（2）a2b1c0 d1e0（3）a2b1c2 d0e2（4）a1b2c2 d1e1（5）a1b2c0 d0e2求决策规则的核（1）a1b0c2d1e1有a1c2 d1e1，a1b0 d1e1，b0c2 d1e1，核为空。U a c d e1 1 2 1 12 2 0 2 03 2 2 0 24 1 2 1 15 1 0 0 2U a b d e1 1 0 1 12 2 1 2 03 2 1 0 24 1 2 1 15 1 2 0 2U b c d e1 0 2 1 12 1 0 2 03 1 2 0 24 2 2 1 15 2 0 0 2（2）a2b1c0 d1e0U a b d e1 1 0 1 12 2 1 2 03 2 1 0 24 1 2 1 15 1 2 0 2a2b0 d1e0，b1c1 d1e0，a2b1 d1e0，核为c0U b c d e1 0 2 1 12 1 0 2 03 1 2 0 24 2 2 1 15 2 0 0 2U a c d e1 1 2 1 12 2 0 2 03 2 2 0 24 1 2 1 15 1 0 0 2U a b c d e1 1 12 0 2 03 2 0 24 2 1 15 0 0 2得到仅包含决策规则的核值得到决策规则：c0 d2d0 d0e2c2 d0e2d1e1 命题：设dX是一条消去所有过剩条件属性值的决策规则，条件属性集C 的等价类xC中任何最少属性a的等价类xa的交集 相应决策类xD中，则由此而得到的最小条件属性a组成的相应于dX的新决策规则dX是dX的一个决策规则约简。U a b c d e1 1 0 2 1 12 2 1 0 2 03 2 1 2 0 24 1 2 2 1 15 1 2 0 0 2对于第一条：决策类1d,e=1,4;1a=1,4,5,1b=1,4,5,1c=1,3,4显然：1a 1d,e，1c 1d,e，但1b 1d,e，1a 1b=1,4 1d,e所以得到两条约简的决策规则：1：b0 d1e1 1：a1c2 d1e1U a b c d e1-0-1 11 1-2 1 12 2-0 1 02-1 0 1 03 2-2 0 23-1 2 0 24 1-2 1 14-2 2 1 15 1-0 0 25-2 0 0 2得到所有约简的决策规则：决策规则的最小化消去所有过剩规则：U a b c d e1-0-1 11 1-2 1 12 2-0 1 02-1 0 1 03 2-2 0 23-1 2 0 24-2 2 1 15 1-0 0 25-2 0 0 210.6 粗糙集在数据挖掘中的应用 n 基于粗糙集理论的数据挖掘方法，首先对原始数据（原始决策表）进行离散化，然后可以通过两种方法对离散化的决策表进行属性约简，最后进行属性值的约简。n 以一个医疗数据记录决策表为例子，给出属性约简求核和属性值约简的过程。n 例如，以下一个决策表给出了一个医疗数据记录表，通过测量人的体温、咳嗽、头痛、周身痛等症状来确定是否患了流感。U条件属性 决策属性体温 咳嗽 头痛 周身痛 流感1正常 无 无 有 无2正常 无 有 无 无3偏高 无 有 无 有4高 有 有 无 有5高 有 无 无 有6偏高 有 有 无 有一个医疗记录表l 体