论文研究-基于决策依赖度的粗糙集约简模型研究.pdf

所需积分/C币:7 2019-09-20 19:44:58 636KB .PDF

论文研究-基于决策依赖度的粗糙集约简模型研究.pdf,  为寻求高效的粗糙集约简模型,基于可分辨关系提出决策分辨约简、依赖性和依赖度等概念.与以往粗糙集约简模型相比,为提高约简精确性,提出性能为O(|P||U|)的等价类划分方法和性能为O(|P||U|)的属性重要性度量方法.同时给出了相关定理和等价命题,论证了传统决策约简模型和决策分辨约简模型的一致性.并基于属性重要性给出性能为O(|C|2
第2期 东鑫影,等:基于决策依赖度的粗糙集约简模型研究 507 但值得注意的是基数排序无需进行关键字的两两比较,本文基于静态链式基数排序,提出一种新的等价 类划分方法,该方法可有效降低系统的论域,使论域大小由|U降低为|UC.该等价类划分方法共分为两 个阶段,包括: Radsort全域按D+C有序和 ResEt全域抽取 221 Radsort(,PUD)全域有序 该方法借助于“分配”和“收集”这两种操作对所有属性进行排序,其中首先将对象按D有序,然后将 所有对象按P有序,最终将U中对象按D+P有序(P≤C).即对v;∈D∪P,依属性顺序逆序进行基 数排序(即若0至m-2列为条件属性,m-1列为决策属性则i可以从m-1取至0),如此排序可以确 保所有对象按D+P有序 由于其采用完善的D+P排序方法,因此适用于协调和不协调决策信息系统.对于协调决策信息系统 可直接将论域对象按P有序,而对于不协调决策信息系统,结合 ResEt全域抽取不会遗漏原系统的任何可 用信息,利于与后续的动态属性约简模型相结合该排序方法较为简单、直观和有效 Algorithm 1 RadSort Algorithm Input:决策信息系统S=(U.PUD) 15:if属性a;不符合要求then Output:按D+P有序的决策信息系统S 1: for Vd∈Ddo 17. else 2:对U个头指针h初始化 18:对U个头指针H初始化 for vx;∈Udo for vx;∈Udo 4: 对所有对象进行排序; 20 对所有对象进行排序 5:映射调整取值d 映射调整取值a 利用头、尾指针建立子表 利用头、尾指针建立子表 n end for for Whil do for Whli do 9:顺序链接非空子表; 顺序链接非空子表; 10 获取子表尾对象准备下次链接; 取子表尾对象准备下次链接; 11: end for end for 12:尾结点的地址为0 尾结点的地址为0; 13: end for 29: end if 1: for Va;∈Pdo 30: end for 易见步骤1~13的时间复杂度为O(DU),步骤14~30的时间复杂度为O(PU1),从而, Radsort的 时间复杂度为ODU)+O(P|U)=O(PU(现实中|D通常为1或远小于P) 222 Reset(U,P∪D)全域抽取 Reset负责求取U/P(PsC).其在对象按D+P有序的前提下,顺序将符合要求的各等价类的首元 素归入U′,以形成新的静态链.同时利用D数组完成对UD中各决策类大小的统计,以利于后续求取系统 的|M声和各属性重要性信息 在下述 Reset全域抽取方法中,对于同一U/尸条件等价类中各对象决策属性取值不同的情况,步骤 4将等价类中除首个对象外一并归入U+,由后文相关定义和定理(如决策对象差异矩阵的定义,依赖度的求 解)易知,本部分对象在本文后续约简处理中不起到仟何作用,因此可以不归入U 由于现实中大部分系统都涉及到动态属性约简问题,在动态添加属性后原有条件属性相同而决策属性不 同的对象集合U+,会在补充的属性信息影响下发生变化,因此该部分信息对动态约简等相关处理较为重要 在动态约简情况下可将本文的约简、核和全域抽取后的U∪U+作为后续动态属性约简模型131的 输入处理信息,以获得动态处理后的属性约简和核属性集. Reset的步骤2~16的时间复杂度为O(PU+O(DU=O(PU),步骤19的时间复杂度为 O(U/D),步骤20~26的时间复杂度为O(DU/P1).从而, Red set的时间复杂度为O(PU+O(U/)+ O(DIJU/PD=O(PUD 总体上,等价类划分方法的时间复杂度为O(PU 508 系统工程理论与实践 第36卷 Algorithm 2 RedSet algorithm Input:排序后的决策信息系统S 13:移至当前条件等价类的尾对象m; Output: U.U+ 将当前条件等价类除首个对象外一并归入 1:将静态链表中的第一个对象x1归入U′,s指向 15: end if 2: for Vx;,xy+1∈Udo 16: end for 3 for Va;∈Pdo 17:将U′中最后一个对象的地址设为0; ifr;和r+1的az属性取值不同then 18:数组初始化:t=0 将新条件等价类的首个对象x+1归入U,19调用 RadSorti(UV,D)函数;/依决策属性排序 作为s的后继对象 20 for vx,x+1∈U″(U)为上述6中形成的新链表 s=t;//s当前归入后的最后一个 查找下一个等价类 21:ifr;和m+1属于同一个决策类then else 22 D1++; 顺序查找下一个属性; 23 else 10 end if 24: t十+; 11: end for 25: end if 12:ifx;和x+1条件属性相同&&决策属性不同26: end for nen 3可分辨关系与分辨约简 定义4属性集的可分辨关系. 设决策信息系统S=(U,C∪),设PsC且P≠,定义由属性子集P导出的二元关系 DSp={(x,x)(x:,x;)∈U×U,k∈P,f(x;)≠f()} 称DISP为由属性集P推导出的可分辨关系 定义5属性集的可分辨对象单元集 若(x,x)∈D1SP,则称m;和是P可分辨的,即依据属性集P可将x和x区分开,并将(x1,m) 称为可分辨对象单元.将由属性集P推导出的可分辨关系对应的集合称为属性集P的可分辨对象单元集, 用DⅠSP(U)表示 定义6属性的可分辨对象单元集 设决策信息系统S-(U,CUD),设ak∈C,将由属性ak导出的二元关系 D5{}-{(x;,x)(x;,x)∈UXU,f(x1)≠(x 称为由属性ak∈C导出的可分辨关系,简记为DⅠS{a}将由属性ak∈C推导出的可分辨关系对应的集 合称为属性ak的可分辨对象单元集,用DSa(U)表示,代表由属性ak可分辨的对象单元的集合 定义7决策约简集 设S=(U,C∪D)为决策信息系统,若存在P≤C且P≠0,使 RpC RcCRD(即 irlap c indc c indD),则称P为决策协调集1.若P为决策协调集,且P的任何真子集均不是决策协调集,则称P为协 调决策信息系统的决策约简集16 定义8决策分辨约简集. 设S=(U,C∪D)为决策信息系统,若存在P≤C且P≠0,使DISP∩DISD=DISc∩DISD,则 称P为决策一致分辨集.若P为决策一致分辨集,且对于YQ<P,满足DIS∩DISn≠DISc∩DI5n, 则称P为决策信息系统S的决策分辨约简集 定义9决策对象差异矩阵. 设决策信息系统S=(U,CUD),其中U=n,|C|=m,将S的决策对象差异矩阵M定义为一个具 有n2行,m列的矩阵,其k列(k=1,2,…,m)的元素定义为 M={(x,x)(x;,x)∈U×U,(x1,x;)∈DSn,ak∈C,(x;)≠f(x) 第2期 东鑫影,等:基于决策依赖度的粗糙集约简模型研究 509 若PsC且P≠0,则将M称为决策信息系统S′=(U,P∪D)的决策对象差异矩阵 定义10决策分辨核心集 决策信息系统S=(UC∪D),设决策信息系统S存在丌个决策分辨约简集,Pk(k=1,2,……,),定义 决策信息系统的决策分辨核心集为 CORE= Pk 1<k<r 定理1设决策信息系统S=(U,C∪D),若存在PsC且P≠0,则以下命题等价: 1)S为协调决策信息系统; 2)DISC2 DISD 3)indc c indd; 证明2)÷3) 易知DSc2DISD等价于U×U-DISD2U×U-DISc,即等价于对V(x,x)∈U×U,若 (x:,x)∈U×U-DSC,则(x,x)∈UxU-D)1S 由定义4,定义5可知(x;,x)∈U×U-DISC,则x和x;是C不可分辨即lnC)=ximC) 同理(x2,x)∈U×U-DISD,则m;和x是D不可分辨,即[ tiande(D)={ iand( d) 由此可知,U×U- DISP=U×U-DⅠSc等价于V(x;,x;)∈UxU,若;]mndc)=[x;]nd(o),则 m(D)=[nd(D),即等价于 indc c idd 因此2)3)成立,同理易证1)÷2) 定理2设决策信息系统S=(U,CUD),若存在P三C且P≠0,则DISn具有如下性质 (1)若P2sPcC,则DISP2SDSP1DISc (2)DISP=∪ DISa ak∈P 定理2证明与文献[7]中定理1证明类似不再详述 定理3设决策信息系统S-(UC∪D),若存在P≤C且P≠0,则|M-|DSP∩DISD 证明由定义9易知ak∈Pmk*= DISa∩DISD且|Mp=|um,因此结合定理2性质2)可知 M|=|DⅠ SPDISD 4基于可分辨关系的依赖性和依赖度 4.1基于可分辨关系的依赖性 定义11基于可分辨关系的依赖性 设决策信息系统S=(U,CUD),其中R1,PC且P1,P2≠0 1)属性集P2决策依赖于属性集丑当且仅当DSP2∩ DISD CDISP∩DISD,其中P2决策依赖于 P1,记作P1→F 2)属性集P1与P决策等价当且仅当B1→P且P→B,其中P决策等价于P1记作P1≡P2,易 见B=P2当且仅当DISP2∩DISp=DIS∩DISD 定理4设决策信息系统S=(UCUD),若存在P1,PC且P1,P2≠0.则以下命题等价 1)1→P2; 2)1∪P=P1; 证明1)÷2 由依赖性定义11可知P1→P等价于DISn2∩ DISD C DISp1∩DISD,从而有(DISn1 U DIST2)∩ DISD= DISP UDISD,由定理2性质(2)可知DISP1UP2=DISP1 UDISP2,则可知 DISP,uP2∩DISD DⅠSP∪DISD,因此PUP2≡P1 定理5设决策信息系统S=(U,C∪D),若存在P,P2sC且P1,P≠⑩,使得P2≌P1,则必有 P1→P2. 证明由定理2性质1)可知,若P2∈P1则有DIS2CDIS1,从而由依赖性定义11可知P1→P2 510 系统工程理论与实践 第36卷 定理6设决策信息系统S=(U,C∪D,若存在B,P2≌C且B1,P2≠0,基于可分辨关系的依赖性 具有如下性质: 1)B1→P2 2)71UP2→B 3)B→P2且P→P,则P→P3; 4)B→P2且B1cP0,则P0→P2; 且乃3<P2,则→P3; 6)n1→P3且P2CB,则BUP2→P 7)B→P且BCP,则B1∪B3→P2 8)B1→P2UB3则1→P2且B1→B3; 9)B→P2且P∪P3CP,则B∪P3→P4; 10)P1P且B1→P2,则P1=P2 证明1)由依赖性定义11易证. 2)山定理2性质1)可知若sPJP则有 DISP C DISP,UP2,则DSn∩ DISp C Disp,up2∩ DISD故P1UP2→P1 3)由P→P2可知DSP2∩DSDD/Sn∩DSD,且由P→P3易知D/S3∩D)/S DISP2∩DISD,则DISP3 DISD C DISp1∩DISD,故有P1→P3 4)由R1→P可知DSP2∩DISD≌DSP∩D/SD,由定理2性质1)可知若PCPo有DIS1S DISP,则有DISP2∩ DISD C DiSp∩DISn,故P→P2 5)由P1→P可知DISP2∩DISn∈DISP1∩DISn,由定理2性质1)可知若PcP2有DISP2 DⅠSP2,则DISP2∩ DISD C DISp1^DISD,故1>乃3 6)由B1→B可知DⅠSP3∩ DISD C DIS∩DISp,由P2→P3可知DⅠSP3∩ DISD C DISp2∩ DISD,由定理2性质2)可知DISP1 U DISP2=DSP1uP2,则DISP3∩ DISD C DISp,UP2∩DISD,故有 P∪P2→13 7)由B1→P可知DISP2DⅠSD≌DISP∩DISD,由P3→P4可知DISP2∩ DISp C DISp∩DISD 由定理2性质2)可知DSP2 UDISP2=D/SB2UP,DISP∪DSP3= DISPUP,则有DISP2UP1∩ DISD C DISP,uP3∩DISD,故B1JB3→P2UP4 8)由B1→P∪P3可知DISP2UP2∩ DISD C DISp∩DISn,由定理2性质2)可知DISP2JP2= DISP2∪DISP3,则有DISP2∩ DISD C DISp1∩DISD且DISP2∩ DISD C DISp1∩DISD,故有P1>I 且P→P3 9)由B1→B2可知DISn2DⅠSDsDⅠSP∩DⅠSD,由P2UB3→P4可知DISP2 DISD C DISp2UP3∩ DISD,由定理2性质2)可知DISn2B3=DISP2∪DⅠSP3,故有DISP∩ DISD C( DISP, UDISE3) nDIS 由定理2性质2)可知DISP1 U DISE3=DⅠSPUP3则有B1P3→P1 10)若PsP2,则由定理2性质1)可知 DISP C DIS2;若P→P,则由定义11可知D/Sn2∩ DISp∈DISn∩DIS,故有DISP1∩DISD=DISP2∩DISD,即P1=P 42基于可分辨关系的依赖度 定义12基于可分辨关系的决策依赖度(决策替代度) 设决策信息系统S=(U,CUD),若存在P1,P2C,B1≠0且B→P:当 DISP2∩DISD kP2(1)=1 DⅠSP1∩DISD 时,称属性集P是k度(0≤k≤1)决策依赖于B,或者称P可以由P以1-k度决策替代,记作P→P 1)当k-0时,称属性集P2不决策依赖于P,或者称属性集P1可由P2完全决策替代 2)当0<k<1时,称属性集P2部分决策依赖于P,或者称属性集P可由P2鄯分决策替代 3)当k=1时,称属性集P2完全决策依赖于P1,或者称属性集P,P2不存在决策替代关系 定理7设决策信息系统S=(U,C∪D),若存在B,PsC,B1≠0且B1→P,则决策依赖度 kP2(P)=0当且仅当M声1|=|A 第2期 东鑫影,等:基于决策依赖度的粗糙集约简模型研究 511 证明由定理3易知kP2(P)=1 IMP 故k=0当且仅当M点=h2 定理8设决策信息系统S=(U,C∪D),若存在P1,PsC,B≠0且P1→P,则决策依赖度 kP2(P1)=1当且仅当DⅠSP2∩DⅠSD=0或M2=0. 证明由定义12和定理3易证,不再详述 定理9设决策信息系统S=(U,C∪D),若存在P,PC,B≠且→P,则丨MP,|与决策依 赖度kP2(P1)成反比关系,与决策替代度成正比关系 证明由定义12和定理3易证,不再详述 通过上述分析可见利用h2(P)=1-M可以很好地反映P,P2间的决策替代和决策依赖关系 43决策依赖度求解分析 algorithm 3 DccDep- Deg Algorithm Input:当前决策信息系统S-(U’,D∪P) ifx;和xt决策属性全部相等then Output:MI 17: s0++: 1: for Vr;,t∈U′do s2++ 3:1++; 20 1+=80*Dx] 4: for va∈Pdo 改变如0值以考察下个U/(D+P)等价类; if属性a;不符合要求then s2++ 考察下一个属性 end if else dIs ifx;和xt的条件属性az不同ther s1+=50*D[x 改变标记向量并转6进行判断; P+=s2*(o-L)-sl; 改变80,81和s2取值,以考察下个U/P等 考察下一个属性; 价类; end if cnd if 13 end if 29: end for end for 30: return MpI 15:if条件属性全部相等then DecDep_Deg负责求取当前集合P的kr(C)由于kr(C)=1-M中分母Me为定值而和 kP(C)成反比,故可直接以M来衡量P的决策依赖度大小,直接求取|M#· DecDep_ Deg在求取|M/#l 的过程中利用了定义9的思想,而没有真正生成决策对象差异矩阵这个中间结果,因而将复杂度有效控制在 ( PlU/CD) 其中步骤2中D{代表当前(x;所在)决策类中未考察的对象数;步骤3中L代表当前统计的对象 数;步骤17中s0代表决策和条件属性值均相同的对象数.步骤18屮s2代表条件属性值相同的对象数.步 骤25中的80*Dr]代表x;所在的(U/(D+P)等价类中已经考察的对象所无法分辨的后续对象数,s1 代表当前等价类无法分辨的后续对象数.步骤26中s2*(o-L)-s1代表当前U/(D+P)等价类可以分 辨的后续对象数,即当前等价类的分辨能力 DecDep_Deg中步骤4~29的时问复杂度为O(P+O(D)=O(P),由于U为形成的新链表,所以 总体来看 DecAp Dcg的时间复杂度为O(P|U/C|) 5决策信息系统求核分析 定义13基于决策依赖度的属性重要性. 设决策信息系统S=(U,CUD),若存在P≌C,P≠0,则属性集P关于条件属性集C的属性集重要 性可以定义为Tp(C)=kC-P(C) 512 类似地对于属性ak∈C,其关于条件属性集C的属性重要性可以定义为mk(C)=k-10 系统工程理论与实践 第 卷 定理10设决簧形式青景K:=(,C∪D,D,(x,x;)∈U×U,ak∈C,则以下命题等价 1)ak∈CO点B 2)3(x;,x1)∈mk,对于va∈C-{ak},(x,x)gmt M|≠|Mt-{ak}l 证明定理10证明与文献[17定理7证明类似,不再详述 如下设计的是系统的求核方法步骤3中。-a即属性ak关于属性集C的属性重要性的相关信 息如果步骤4中条件成立那么则有(C)-k-(0(C)B>0成立代表属性a不可 或缺并无法山其他属性决策替代,则a为核属性归入CORE.如果条件不成立,则7ak(C)为0,属性az可 由其他属性决策替代,a;为非核属性 Algorithm 4 CoreSet algorithm Input:当前决策信息系统S Output:核集CORE 1: for Va2∈Cdo 2:调用 Radsort i(U,C-a;∪D)令对象按1+C-a有序; 3:调用 Dec Dep_Deg(U’,C-a1UD)统计重要性相关信息|M-a 4ifM刮≠Me- I then 归入核集CORE; end if 7: end for CoreSet算法中步骤2的时间复杂度为O(C-aUC),步骤3的时间复杂度为O(C-aUC1).所 以,总体来看算法4的时问复杂度为O(C2U/C) 6决策信息系统约简模型 61相关约简定理 定理11设决簧信息系统S=(U,CUD),则决策分辨约简集必然存在 证明定理11证明与文献[1刁定理4证明类似,不再详述 定理12设决簧信息系统S=(U,C∪D),则决策系统S的决策协调集和决策一致分辨集是一致的 定理13设决策信息系统S=(U,C∪D,决策约简集和决策分辨约简集是-一致的 证明定理12,定理13证明与文献[17定理5证明类似,不再详述 定理14设决策信息系统S=(U,CUD),若存在P≤C且P≠0.则以下命题等价 1)P为决策一致分辨集 2)DISP∩DISD3DSc∩Ds 证明2)→1) 由定理2中性质1)易知若PsC则DISP≤DISc,由于已知DISp∩DISD2DISc∩DISD,因 此DISp∩DISD=DISc∩DⅠSD.由定义8可知P为决策一致分辨集 1)→2). 由定义8可知,若P为决策一致分辨集则满足DISP∩DISD=DISc∩DISD,则可知DISp∩DIS≤ DISc∩DSD且DISP∩DISD2DISc∩DISD 由定义11可知P≡C当且仅DSP∩D/SD= DIScnDISp,故由定义8可知3)2),1) 定理15设决策信息系统S=(U,CUD),若存在PCC且P≠0.则以下命题等价: 第2期 东鑫影,等:基于决策依赖度的粗糙集约简模型研究 513 1)P为决策分辨约简集 2)DSP∩DSn2 DISc n Dlsp,且对于vQcP,DSQ∩DlSD≠DlSc∩DSD 3)P=C,且对于vQcP,Q=C不成立 证明由定义和定理14易证不再详 6.2基于决策依赖度的属性重要性的约简模型 模型的主体算法采用自底向上的方法,以条件属性集合C的核CORE*作为求解约简RED的基础,其 中,步骤9~24采用基于决策依赖度的属性重要性ra;(C-COBE)作为启发式信息,依据启发式信息来选 择,考察和添加属性以得到约简配ED.具体算法如下 Algorithm 5 Dec Dep_Red Algorithm Input:决策信息系统S={UC∪D) 数 Output: RED 13:调用 DecDep_Deg(PUD)函数,求取P= 1:预处理数据表并以静态链表形式存储 C-CORE-az的M芦|; 2:初始化RED和CORE cn 3:调用 RadSort(l,C∪D)函数,全域按D+C有15:fora;∈C- COrE do 序 查找当前具有最小|M芦的属性 4:调用 Reset(U,CUD)函数,全域抽取以得到U〃17:将其归入系统的约简集合BED 和D数组 调用 Radsort(U,RED∪D)函数 5:调用 DecDep_Deg(U,CUD)函数求取|M 19 调用 DecDep_Deg(U, REDUD)求取 6:调用求核方法( preSet(,CUD)求取CORE RED 7:调用 RadSort(U,CORE∪D)函数 20: if IM&== MREDI then 8:调用 DecDep_Deg(U,COBE∪D)函数求取 21 结束查找 CORE end if g: if MCORE|≠Me|then 23 end for 10: RED= CORE 24: end if 11: for a2∈C- core do 25: return RED 1 调用 RadSort(U,C-COE-aUD)凶 若主算法步骤9~24中条件不成立,则代表当前系统的核属性集合CORF就是约简;反之,则说明 CORE不是约简 由于在步骤6中已经求取的重要性信息仅能代表属性a2在条件属性集合C中的重要性,因此考虑到属 性之间的相关性和分辨能力的影响,在步骤12中将当前链表按D+C-CORE-a;有序,在步骤13中重 新求取属性集合C-COBE-a的重要性信息M梦,而没有利用原有信息,如此可以考察任一非核属性a 在所有非核属性中的重要性 步骤9~24中求取约简RED是以核属性COBE为基础,所以在条件|MoFE≠|M成立情况下, 有 CORE C RED.此后求取约简需进行属性的添加直至条件M==MRED成立,因此步骤9~24符 合定理15命题2) 由约简结束时|C|==MED成立,亦可知属性集C可由RED完全决策替代,即RED≡C且 VQ CREL.Q≡C不成立,因此符合定理15命题3) 若条件|AoR|≠|M料不成立COE即为约简,易见此时亦符合定理15 63约简模型时间复杂度分析 主算法的步骤3的时间复杂度为O(C|U),步骤4的时间复杂度为O(C|),步骤5的时间复杂度为 O(C|U/C|),步骤6求核过程的时间复杂度为OC|U/C),步骤7的时间复杂度为O( COREJJU/C),步 骤8的时间复杂度为O(CORE|U/C 步骤12,13的时间复杂度为O(C-CORF-|1C1),从而步骤11~14的时间复杂度为O(C CORERU/C).步骤18,19的时间复杂度为O(CORE+a1|UC),从而步骤15~23的时间复杂度为 O(C-COF酬 COREU/C).因此,步骤9~24的时间复杂度为Max{O(C-CORE2U/C|).O(C 514 系统工程理论与实践 第36卷 COREICOREIJUCDI 所以,模型的时间复杂度可以被确定为Max{O(CU/),O(CP2U/CD} 7仿真实例分析 下面以示例 parily5+518说明约简模型的执行流程,示例 parity5+5表1属性重要性相关信息 包括100个对象和11个属性(其中∞0至g为条件属性,a0为决策属"C1M2-,|m、(C)核属性 性).如下详细说明在约简的各主要步骤的处理结果 247 在将全域按门+C有序,并执行至步骤4实现全域抽取后,得出|U=a12472非0 100,同时得到全域分为2个决策类其中D0=45,D(]=55.而后顺a22469非0 序执行步骤5利用 DecDep_ Deg函数求取属性集合C的|为2475.a271非0 此后执行步骤6求取核属性,表1罗刎出各条件属性的属性重要性相关信α42475 息根据a和1(C)并结合定理10可知核集为{a1,a2,a3a5,a7}.52472非0 此后执行步骤7和8,由于调用 DecDep_Deg函数得出核集 core a62475 的OBE|为24175,结果与(相等因此步骤9~24中(MoE≠a72473非0 82475 是否是否是否否 MC)不成立,即CORE即为约简,算法不再继续执行.本文算法所求的 a9 0 核和约简均为{1,m2,03,05,07} 由于利用文献[1】〗中的模型不能求取核属性因此只能直接求取约简属性,其结果为{a0a1203a4a5a6a7 asa9}.同时利用ROSE( Rough Set data explorer,由波兰 Poznan科技大学开发)中 Reduction”的“(ore” 和“ Discernibility matrix”功能求解核属性结果和约简结果,得出的结果均为{a1a2a3a5ar}.因此本文约简 模型所得岀的结果为精确约简,尢冗余属性;而文献[2所得结果中αoα4ααsαφ为冗余属性. 8实验分析 本文选取了10个UCI数据集1,所有数据集的最后一个属性为决策属性.鉴于粗糙集理论对系统中 的离散属性比较有效,而对连续属性处理能力有限,故首先利用ROSE提供的“ Discretization”方法,对部分 数据集进行了连续属性离散化处理. 选择在PC(IbmR52,52MB内存, Intell.86GHz, WindowXp)环境下对三个约简方法进行实验测试, 以分析各约简方法的精确性和有效性.表2中对比给出了各模型的约简结果和执行时间,其中模型A为文 献[12中提出的方法,模型B为本文提出的约简模型,同时提供了利用ROSE( Rcduction下的“(or”和 ¨ Discernibility Matriⅸx”功能)求解得岀的精确结果‘包括各数据集的核属性和所有约简),并将模型Δ和模 型B的结果与之相对比各约简结果中加粗鄙分代表所得结果中包含的冗余属性 表2测试结果 决策表 属性 约简结果(加粗代表冗余属性) 执行时间(S 数 算法A 算法B ROSE 算法A算法B balance-scale aoa1a2a3 a0a1 a2a3 aoa a3 0.0050.005 breast -cancer U0124U5C678 10 0O1C24a56C708 0a1024U56Q7 0.0050.005 aoC1a2a3a4a5a6a7 023U45 corral 00010203 a0a2a3a405 0.0050.005 aoa a3 diabetes C0U120304506a7 U10203045C607 U10263045067 00150.015 parity 5+5 11 a001a2a3040506a70aag a1a203a5a7 a1a2035 0.0050.005 001203U8C1001201 vote C012a38a1011C12015a0a1a2a3a8a1012C1 0.0160.016 a0a1a2a56a8a9101213014415 vote-irvine 17a0a1a2a3a8a9a10a11012a14a001a203a9a10a12a15共10个约简,约简长度7~130.0160.015 solar ao C102 03a4 a5a8 a9 a10 0C1a203a4a5a8a9010 c01a234a58a9C10 0.0050.005 threeof9 10 CC12a3a456a708 C01a20304aC6a70s C0C1a23a4U50678 0.0160.015 tic-tac-toe-buggy 10 02(34566a8 a0a1a23a4a5a6a7共7个约简、约简长度7~80.0150.016 通过对比约简结果和运行时间,可以看出针对这10个数据集的求解,在运行时间上两个模型相差无几 模型B可以求出所有数据集的核属性集,并且能够求解出其中9个数据集的精确约简结果:模型A不能求

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源