《数据挖掘与知识发现.docx》由会员分享，可在线阅读，更多相关《数据挖掘与知识发现.docx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 基于粗糙集（Rough Set）理论的数据挖掘技术粗糙集理论是由波兰华沙理工大学数学家Z.Pawlak于1982年提出的一种数据分 析理论，该理论在分类意义下定义了模糊性和不确定性两个概念。是一种处理不完 整数据、不精确知识的表达、学习、归纳等的一-种新型数学工具。粗集理论的重要特点是：不需要任何附加信息或先验知识，直接从所需处理的 数据本身所提供的信息出发找出问题的内在规律。目前，大多数数据挖掘工具软件（如：AQ系统、IDS系统等）都是基于集合论 开发的，其中粗糙集（RS）理论使用最广，也最布开展前途。由于RS是研究不精确和不确定知识的一种数据工具，如，知识的含糊性，主要 包括：术语
2、的模糊性，如高矮；数据的不确定性，如噪声；知识自身的不确 定性，如规那么的前后件间的依赖关系不完全可靠等。所以，它同其它不确定问题理 论，如，概率统计理论中的概率分布、模糊理论不能处理不完整数据且需提供隶属 函数这种先验知识、D-S证据理论中的基本概率赋值等相比，更具实用性。粗集理论的主要思想：是在保持分类能力不变的前提下，通过知识约简，导出 问题的决策或分类规那么。目前，RS理论已成功地应用于机器学习、过程控制、模式识别、数据挖掘、预 测、故障诊断、决策分析和人工神经网络等领域，成为其它不确定理论的一种补充, 有着不可替代的优越性。核可解释为在知识约简时它是不能消去的知识特征集合。【例如】设
3、K = （U,R）是一个知识库，其中=区，/），R = R”&,&， 且U / R、=xpx4,x5,x2,x8),j;3,x6,x7)U/R2 =x1,x3,x5),x6,x2,x4,j:7,x8)U/% =“,% ,“ 2,与，/，工3，匕那么得关系加4（R）的等价类为U /加d(R) = 再,5 , %2 ,“8 ，巧，匕，%，%7 （注：u/h（r）是通过计算（u/与 nu/Qnu/6获得的）故由计算:u /ind(R-Rx) = x1,x5,x2,x7,x8Jx3,x4,x6)丰 U/indg(注：U/ind(R-/?,)是通过计算U/R2CU/R.获得的)说明关系叫为R中必要的。对
4、于关系R?,有U/ind(R - 7?2) = Xj ,x5, x2,x8, x3, x4, x6, x7 = ind(R)故R?是R中不必要的。同理，&也是R中不必要的，即有U /ind(R - &) = 司,毛,x2,x8),(x3,x4 ,x6 ,x7) = ind(R) 但U/R-R2,Ry = U/R = x1,x4,x5),x2,x8),x3,x6,x7 wU/加d(R)且有U /山d( K, & ) h U /加d(K), U1加d(，& )工 U / 以(R2)所以，R-R?为独立的且为R的一个约简。同理，叫,R-J也是独立的且为R的一 个约简。那么一个核core(R);叫,与
5、。叫,& = RJ .知识的相对约简、相对核概念令P和Q为U中的等价关系，Q的P正域记为R，Sp(Q),即PosP(Q) = U PXXeU/Q _所以，Q的P正域是U中所有根据分类U/P的信息可以准确地划分到关系Q的等 价类中去的对象集合。令P和Q为等价关系族，RwP,如果尸%,/(p)(力以(Q) = P%d(p.用的d(Q)那么称R为P中Q不必要的；否那么为必要的。为简单起见，用Rz%(Q)代替P3MP)a(Q)。如果P中的每个R都为Q必要的，那么称P为Q独立的(或P相对于Q独立)。设S q P ,S为P的Q约简当且仅当S是P的Q独立子族且Poss(Q) = R?Sp(Q)。P的Q约简简
6、称为相对约简。P中所有Q必要的原始关系构成的集合称为P的Q的核。简称相对核，记为 coreQ(P).定理：ceQ(P) = OedQ(P),其中&/q(P)是所有P的Q约简构成的集合。【例如】设K = (U,P)是一个知识库，其中。=和，4，P = R1,R2，R3，且UIR、=xpx3,x4,x5,x6,x7),x2,x8)|U i R? =区，七,工25,12，16，工7，工8U/% =%1，工5，尢6，加工8)，13，3那么由P导出的分类为U / 历d(P) = 否,匕，(犬3，匕)，工2，工8 ，工6 ，与假设等价关系Q有以下等价类:。/(? = 口，与，4，*3，匕，工2，工7 ，那
7、么Q的P正域为:Posp(Q) = (x) ,x51 u xX4 U 6 U A：7 = xi,x3,x4,x5,x6,x1又 U/(P-R) =0/?2，& = 和为，%3，匕，%2，力7，力8 ，4所以 R，SPT%)(Q) = xpx5Ux3,x4Ux6 = xpx3,x4,x5,x6 PoSp(Q)故但凡P中Q必要的。同理得，鱼为P中Q不必要的；&为P中Q必要的。这样，P的Q核为R1,R-J，即co%q(P) = R1,&,它也是P的Q约简。3 .知识表达系统知识表达在智能数据处理中占有十分重要的地位。形式上，一个知识表达系统可定义为四元组S = (U,AVJ),其中，U：对象的非空有
8、限集合，称为论域；A：属性的非空有限集合；V=U匕，匕是属性。的值域； aeA/:UxAf V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即V.r U, Vq A J(x,a) g Va知识表达系统也称为信息系统。通常用S = (U, A)来代替S = (C/,AV,/)o知识表达系统的数据以关系表的形式表示。关系表的行对应要研究的对象，列 对应对象的属性，对象的信息是通过指定对象的各属性值来表达。显然，一个属性对应一个等价关系，一个表可以看作是定义了一族等价关系， 即知识库。【例如】，一个关于某些病人的知识表达系统，那么U = ei . es,G，%,，A=头痛，肌肉痛，体温病人潮
9、肌肉痛体温是是正常%是是高%是是很高/否是正常%否否高否是很高令PqA,定义属性集P的不可分关系加d(P)为indP = (x9y)eUxUX/a g P,f(x,a) = f(y9a)如果(x, y) g incl(P),那么称x和y是P不可区分的。容易证明，,不可分关系山。(P)是U上的等价关系。假设取属性集P=头痛，肌肉痛,那么有。/尸=，,02,%，回，为即P的基本集为，/勺，匕，% 假设取 X= 6,64,6,那么PX = PoSp(X) = eA,eb PX = e,e2,ei,e4,e6N%(X) = U - PX = % ； Bnp(X) = ene2,e3而U- A) = ,
10、% ,G，0，% ，U或A-头痛) = ,/,g,6,/，仁工。/山d(A)U/加 d(A-肌肉痛)= q,图/4匕,%， =Ud(A)U /ind(A - 体温) = , 6，6 ，/，/,/ w U / 山d( A) 所以，经约简知，属性集头痛、肌肉痛、体温有一个约简头痛，体温且co砥A)=(头痛,体温。4 .决策表决策表是一类特殊而重要的知识表达系统。多数决策问题都可以用决策表形式来 表达，这一工具在决策应用中起着重要的作用。设S = (U,AK/)为一知识表达系统，4 = cuncno =。，c称为条件属性集, D称为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。【例如】
11、一个关于某些病人的决策表如下，其中(7 = ,/，4，c=头痛，肌肉痛，体温, D=流感。令孰二头痛，C2二肌肉痛，。3=体温，那么u/CJ = ee2,e3, /,仁，/，。，41)/C2 = e,e2,e3,e4,e6,e8,e5,e7)条件属性决策属性 沆感/C3 = e1,e4,e2,e5,e7,e3,6,e8)病人邮肌肉痛体温&是是正常否u/GC = 化，出勺，怙，/，/,生勺是是高是U/C、,。3 二 1 ,卜2 ，3 ,，,%,， 分 ,/是是很高是否是正常否U /。2, G = 1，64 ，2 ，%，67 ，,3, 66, 08 )%否否高否U / C = , g,6, ej
12、%，。)，&，/绘否是很高是%否否高是U / D = e2,e?t,e(),e1,el,e4,e5,e8%否是很高否因为 Posc(D) = eJ e2 U e3 U e4) = (el9e2,e39e4且有 PosC_C(D) = eie2,e4工 Posc(D)PoSctjh(D) = el,e2,e3,e4= PoscDPoSCTG）（O）=。，PoSc（D）PoSctg，C2“（）= 41 Posc（D）&Sc-gc”（Q）=。h Posc（D）所以C的D约简（相对约简）为C-C2 = G，C3，C的D核（相对核）也为G，G。在决策表中，不同的属性可能具有不同的重要性。为了找出某些属性
13、（或属性集） 的重要性（significance）,我们的方法是：从表中去掉一些属性，现来考察没有该属 性后分类会怎样变化。假设去掉该属性相应分类变化较大，那么说明该属性的强度大， 即重要性高；反之重要性低。对属性的重要性问题，我们也可用依赖度定义来说明：定义 令C和D分别为条件属性和决策属性，那么k = yc(D) =k = yc(D) =Posc(D)U称为D依赖于C的依赖度。如，上例中k = yc（D）=P：；* =。= 05,说明D部I。I 8分依赖于C,依赖度为0.5。定义属性子集C，C关于D的重要性为be（C）= /c（O）-，dc（D）特别地，当C=。时，属性acC关于D的重要性
14、为crcD（）= rc（）-rc-M（D）如，上例中，有（头痛）=4/8-3/8=1/8肌肉痛）=4/8-4/8=0% （体温）=4/8-0=4/8由此知，在决策表中，体温最重要；其次是头痛; 肌肉痛是不重要的。在决策表中，最重要的是决策规那么的产生。设S = （U,AVJ）是一个决策表，A = CUD,CnD =。令X,和匕分别代表U/C 与U/D中的各个等价类，des（Xj）,des（）分别表示对等价类X,和匕的描述，即等价 类X,和匕对各属性值的特定取值。决策规那么定义如下：% :f desQj）, - D 。Y C X 规那么确实定因子（Xj,匕）=,0 4（Xj,匕） /;uX, =
15、U l 7 I7 IJ77.7,1=1（显然，一个划分就是一条知识）U上的一族划分称为关于U的一个知识库（knowledge base）o设R是U上的一个等价关系，U/R表示R的所有等价类构成的集合，即 U/R = xRxeU.幻犬表示包含元素xwU的R等价类。【例如】考虑一组儿童的集合，A=（张，9）,（王，9）,（李，9）,（赵，9）, （刘，7）,（洪，7）,（梁，7）,（黄，5）,（陈，5）,（段，8） 0那么具有“相同年龄” 关系R的等价类如下：匹二（张，9）,（王，9）,（李，9）,（赵，9） 72=（刘，7）,（洪，7）,（梁，7） 乃3=（黄，5）,（陈，5） % = （段，8
16、） 即A/R = 勺，42，43，町一个知识库就是一个关系系统K = （SR）, R是U上的一族等价关系。假设等价关系族P = R,且P#，那么CP也是一个等价关系（即P中所有等价关系的交集),称CP为P上的不可区分关系(indiscernibility)，记为ind(P),且有 国i=nm。那么U/加d(P)表示与等价关系族P相关的知识，称为K中关于U的P基本知识(P 基本集)。为简单起见，用U/P代替U/0(P)。不可分辩关系概念是RS理论的基 础，它揭示出论域知识的颗粒状结构。山或P)的等价类源称为知识P的基本概念或基本范畴。特别的，如果QeR,那么称。为K中关于U的Q初等知识。Q的等价
17、类为知识R的。初等概念或初等范畴。当K = (U,R)为一知识库，加或K)定义为K中所有等价关系的族，记作ind(K) = 山d(P)|尸三阳(说明K是由所有基本知识组成的集合)【例如】一玩具积木的知识表达系统由此得三个等价类:积木 颜色形状论域=用,，/，如果根据某一属性描述这些积体枳X】红圆小x2-&方大 木情况，就可按颜色、形状和体积分类。换言之，可以定义X,红三角型小 三个等价关系(即属性)：颜色与、形状凡、体积尺。4蓝三角坦小X,黄回小、按分：芭,当,与一红；灰,匕一蓝；八,工6，%黄X，黄方小J红三角型按凡分：冷一圆；工2，工6一方；七，匕，匕，工8 一三角型*8黄三角型大按分：X
18、2-%,冬一大;再，了3，“4，均，工6一小。U/R1 =x1,x3,x7,a:2,x4,5,x6,x8)U/R2 =xi,x5,x2,x6,x3,x4,x7,x8)U/R3 =工2，七，/，%，工3，工4，/，4) 这三个等价类均是由知识库k =(u,m，R2，R3)中的初等概念(初等范畴)构成的。它的基本范畴是初等范畴的交集构成的，如(jf1,x3,x7Aj:3,x4,x7,x8) = x3,x7)红色三角形(x2,x4)n(x2,x6J = x2蓝色方形(x5,x6,x8) A(x3,x4,x7,x8) = /黄色三角形上面是R1,RJ的基本范畴。xj,x3,x7nx3,x4,x7,x8
19、nx2,x7,x8 = x7红色大三角形这是RR?,&的基本范畴。，工3，七1)工2，E = 内，M3，与，工2，匕-红色或蓝色，为RJ的范畴。注：(1)有些范畴在这个知识库是无法得到的，如看,匕口区,看=。说明知识库中不存在蓝色圆形，为空范畴。芭,当,看6=。-说明知识库中不存在红色方形，为空范畴。(2)上例容易求出 U/R1,4、/%,&、/0,&)和U/R = U/R”R2，RJU -二。/凡0/穴2=再，占，巧，7，七，“5，%，/。/a,& =。/叫。/=区，巧，出，5)，“，展，/，4U/犬2，火3=/穴2-0/&=再，&，%2，*3，相，与，/，(工6U/R=U/g 7。/&门。
20、/&=再，上，出，会用匕,/(3)假设一个知识系统，u = U，w，,4，给定一个等价关系簇R = 凡,Rz,R.J， 且有以下等价类：U/R =斗,X4，匕，%2，/，匕，*6,u IR? =x,x5,x3,x6,x4,x2,x7,x8)U! Ry = x2,x7,x8|,xpx5),A-4,x3,x6)试求：UIR, U/R-R, U/R-R2, U/R-R3自己思考定义：设K = (U,P)和K = (U,Q)为两个知识库，假设ind(P)=山d(Q),即U/P = SQ , 那么称K和K (P和Q)是等价的，记作KnK (P二Q)。(说明K和K有同样的基 本范畴)设K = (U,P)和
21、K = (U,Q)为两个知识库，当加d(P) u加d(Q)时，称知识P (知 识库K)比知识Q (知识库K)更精细，或Q比P更粗糙。当P比Q更精细时， 也称P为Q的特化，Q为P的推广。这就意味着，推广是将某些范畴组合在一起， 而特化那么是将范畴分割成更小的单元。(2)不精确范畴、近似与粗糙集令XqU, R为U上的一个等价关系。当X能表达成某些R基本范畴的并时， 那么称X是R可定义的；否那么不可定义的。R可定义集是论域的子集，它可在知识库中精确地定义。而R的不可定义集不能 在这个知识库中定义。R的可定义集也称为精确集，而A的不可定义集也称为A的 非精确集或尺的粗糙集。当存在等价关系R ind(K
22、)且X为R精确集时，集合X q U称为K中的精确集; 当对于任何X都是R粗糙集，那么X称为K中的粗糙集。定义：设给定知识库K = (U,R),对于每个子集XqU和一个等价关系 Rwind(K),定义两个子集:RX=JYeU/RYXRX=JYeU/RYCX/f分别称为 X 的 R 下近似(lower approximation)和 R 上近似(upper approximation )o上下近似也可用下面的等式表达:RX=xeUxR q X -由根据知识R判断肯定属于X的U中元素组成RX=xeUxR n X w 0由根据知识R判断可能属于X的U中元素组成集合B?(X) = AX-RX称为X的R边
23、界域；PoSr(X) = RX称为X的R正域；Negr(X) = U - R X称为X的R负域。显然，RX = PosR(X)jBnR(X)【例如】应用近似集合的概念，根据粗集的定义，来研究或分析一些人的受教育程度与就业的关系问题。受教育程度与就业的情况如下表所示。受教育者受教育程度就业情况王局中无马高中有李小学无刘大学有赵研究生有解：由受教育程度与就业情况知识表达数据表知，研究对象:受教育的人：U=王，马，李，文IJ,赵受教育程度：高中，小学，大学，研究生四种，即等价关系R = LLX，%, 其中y产王,马,匕=李，匕=刘），匕=赵）就业情况：有，无两种。设x为定义有工作的人为一种分类子集，
24、那么有工作的人的子集x二马，刘，赵 那么根据粗集的定义，有poSr（x）= r（x）= xul =刘，赵A（x）= xU%U% =刘,赵,王,马NEGr（X） = U-R（X） = Y2 =李B%（X） = R（X）- R（X） = X = 王，马所以，根据粗集中R（x）、R（X）、NEGr（X）、3曲（X）的意义，可得受教育程度与 就业的情况表达如下：根据R（X）, 规那么1： if （大学）or （研究生）then （一定有工作）根据R（X）, 规那么2： if （高中、大学）or （研究生）then （可能有工作）根据8r（X）,规那么3： if （高中）then （可能有、也可能无工作
25、）根据NEGr（X）,规那么4： if （小学）hen （无工作）定理1： （1） X为R可定义集当且仅当HX = RXX为R粗糙集当且仅当HX wRx定理 2： （1） RX qX qRXRgRge，RU = RU =U（2） R(XJY) = RXIJRY ； R(X CY) = R X C RYXqYnRXq/?y； XqYnRXqRy(5)R(xuy)3 RxuRy； R(xny)qAxnRyR (X)= RX ； R(X)二RX(6) R(RX) = R(RX) = RX； R(RX) = R(RX) = RX定义：xg X当且仅当xsRX -R-XEr X当且仅当XE RX这里，6
26、表示根据R, X肯定地属于X； EK表示根据R, X可能属于X。分别称E一 R-R和日为下和上成员关系。说明成员关系依赖于我们的知识，即一个对象是否属于一 个集合依赖于我们的知识，并且这不是绝对特性。由此可以看出，集合（范畴）的不精确性是由于边界的存在而引起的。集合的 边界域越大，其精确性那么越低。一般而言，两个集合X和Y之间的相似程度定义为s（x,y）二s（x,y）二XCYIXUYI当X和Y不相交时，S （X, Y） =0；当X和Y完全相同时，S （X, Y） =1。由此,可类似给出X关于R粗糙度。定义精度：由等价关系R定义集合X的近似精度为RXrRX |RX|%（x）= -=-一 一反映对
27、了解集合X的知识的完全程|RXURX| |RX|度。其中，Xw。，|X|表示集合X的基数。pX) = 1-%(X)为X的R粗糙度。对于空集，定义粗糙度0f(。) = 1。2.知识约简知识约简是粗糙集理论的核心内容之一。众所周知，知识库中的知识(属性)并 不是同等重要的，甚至其中某些知识是冗余的。所谓知识约简，是指在保持知识库分类能力不变的条件下，删除其中不相关或 不重要的知识。知识约简中有两个基本概念：约简(reduct)和核(core)。定义：令R为一族等价关系，RwR，如果加d(R) = id(R-R)那么称R为R中不必要的；否那么为必要的。如果每一个RgR都为R中必要的，那么称R为独立的；否那么称R为依赖的。定理：如果R是独立的，PcR,那么P也是独立的定义：设QqP，如果Q是独立的，且而/(Q) = id(P),那么称Q为P的一个约简。显然P可以有多种约简。P中所有必要关系组成的集合称为P的核，记作core(P)。核与约简的关系为定理：core(P尸Cred(P),其中red (P)表示P的所有约简。由此看出，核这个概念的用处有两个方面：核可以作为所有约简的计算基础，因为核包含在所有约简之中，并且计算可以直接进行;