第10章--粗糙集理论-数据挖掘:概念与技术-教学1课件.ppt
《第10章--粗糙集理论-数据挖掘:概念与技术-教学1课件.ppt》由会员分享,可在线阅读,更多相关《第10章--粗糙集理论-数据挖掘:概念与技术-教学1课件.ppt(109页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第10章 粗糙集理论 参考书:1 20042 2008n 粗 糙 集 理 论 是 由 波 兰 华 沙 理 工 大 学Pawlak 教 授 于20世 纪80年 代 初 提 出 的 一 种 研 究 不 完 整、不 确 定 知 识 和 数 据 的 表 达、学 习、归 纳 的 理 论 方 法,它 是 一 种 刻 画 不 完 整 性 和 不 确 定性 的 数 学 工 具,能 有 效 地 分 析 不 精 确、不 一 致、不 完 整 等各 种 不 完 备 的 信 息,还 可 以 对 数 据 进 行 分 析 和 推 理,从 中发现隐含的知识,揭示潜在的规律。n 粗 糙 集 在 机 器 学 习、决 策 支 持
2、系 统、机 器 发 现、归 纳 推 理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。n 粗 糙 集 理 论 逐 渐 应 用 于 数 据 挖 掘 领 域 中,并 在 对 大 型 数 据 库 中不 完 整 数 据 进 行 分 析 和 学 习 方 面 取 得 了 显 著 的 成 果,使 得 粗 糙集 理 论 及 数 据 挖 掘 的 研 究 成 为 热 点 领 域。最 近 几 年,粗 糙 集 理论 越 来 越 受 到 众 多 研 究 人 员 的 重 视,它 的 应 用 研 究 得 到 了 很 大的发展。n 粗糙集方法仅利用数据本身提供的信息,无须任何先验知识。数据规则精确的数学方法10.1粗
3、糙集基本概念 粗糙集理论是在经典集合论基础上发展而来的。利用不确定性、不完整的经验知识进行推理。知识库1.知识的分类表达形式集合理论为描述世界中各种事件提供了一个十分有用的基础,千差万别的事物都可以用集合论的方法加以描述。知识表达系统采用集合表达。知识分类 利用事件不同的属性的知识描述,对事物可以产生不同的分类。定义,知识表达系统(知识库)M 可以形式化表达为四元组:M=(U,A,V,f),其中U 为对象非空有限集合,称为论域;A 为属性的非空有限集合,A=A1,A2,Am;V=Vi,Vi是属性Ai的值域;f:UAV 是一个信息函数,它为每个对象的每个属性赋予一个信息值,即aA,xU,f(x,
4、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
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:大积木
6、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 等价类。一
7、个知识库就是一个关系系统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黄色 圆
8、形 小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
9、,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 下近似集:
10、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
11、 上的一族等价关系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)
12、=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对
13、于集合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
14、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
15、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
16、 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在属
17、性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约简的含
18、义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
19、 d)两个约简a,b 和b,d,核为b。求解f(D)可以得到所有的约简和核NP 问题,即m 个属性其时间复杂度为O(2m)。10.3决策表 决 策 表 包 含 了 某 一 领 域 的 大 量 数 据,是 领 域 的 样 本数 据 库。它 记 录 了 大 量 样 本 的 属 性 值 和 决 策 情 况,是 领域知识的载体。知 识 获 取 的 目 的 就 是 要 通 过 分 析 这 个 实 例 库 来 得 到该 领 域 中 有 用 的、规 律 性 知 识。决 策 表 在 决 策 应 用 中 有十 分 重 要 的 地 位,可 用 于 表 达 绝 大 多 数 决 策 问 题。对 于决策表,最重要的是决
20、策规则的生成。数据库决策表规则在信息表(知识库)上指定条件属性集合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,求POS
21、C(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知识
22、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小
23、 汽油 白色 低 好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
24、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
25、所 谓 属 性 约 简,就 是 在 保 持 知 识 库 分 类 能 力 不 变 的条件下,删除其中不相关或不重要的属性。n 一个属性集合可能有多个约简。n 属 性 约 简 的 目 标 就 是 要 从 条 件 属 性 集 合 中 发 现 部 分必 要 的 条 件 属 性,使 得 根 据 这 部 分 条 件 属 性 形 成 的相 对 于 决 策 属 性 的 分 类 和 所 有 条 件 属 性 所 形 成 的 相对 于 决 策 属 性 的 分 类 一 致,即 和 所 有 条 件 属 性 相 对于决策属性D 有相同的分类能力。设T=(U,C D)是决策表,如果有:POSC(D)=U则决策表T 是协调的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 10 粗糙 理论 数据 挖掘 概念 技术 教学 课件
限制150内