基于Skowron分明矩阵的有效属性约简算法.pdf_大学文库

D01:10.13374.isml00103x.2009.B.048 第31卷第3期北京科技大学学报 Vol.31 No.3 2009年3月 Journal of University of Science and Technology Beijing Mar.2009 基于Skowron分明矩阵的有效属性约简算法秦奕青1,2) 杨炳儒徐章艳2到 1)北京信息科技大学计算机学院，北京1001922)北京科技大学信息工程学院，北京100083 3)广西师范大学计算机系，桂林541004 摘要为降低基于Skow ron分明矩阵属性约简算法的复杂度，提出了简化分明矩阵及其相应属性约简的定义，并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上，定义了一个函数，该函数能度量条件属性在简化分明矩阵中出现的频率.并给出了计算该函数的快速算法，其时间和空间复杂度均为O(U/C.用该函数设计了一个有效的基于原分明矩阵属性约简算法，算法的时间复杂度降为O川C|U川)十O斗U/C人，空间复杂度降为O (小U川)：并用实例证明了算法的有效性. 关键词粗糙集；分明矩阵：属性约简：复杂度分类号TP301.6 Efficient algorithm of attribute reduction based on Skowron s discernibility ma- trix QIN Yi-qing.YANGBingru.XU Zhang-yan2 1)Colege of Computer Beijing Information Science and Technology University.Beijng 100192.China 2)School of Information Engincering.University of Science and Techmlogy Beijng.Beijing 100083.China 3)Department of Computer.Guangxi Normal University.Guilin 541004.China ABSTRACT To cut down the time and space complexity and improve the efficiency of the attribute reduction algorithm based on Skowron's discernibility matrix,the definitions of a simplified discernibility matrix and corresponding attribute reduction were provid- ed.It is proved that attribute reduction based on the simplified disceribility matrix is equivalent to that based on the old one.By the foundation of a simplified decision table,a function w hich can measure the frequency of a condition attribute in the simplified discerni- bility matrix w a defined.An algorithm for the above function w as designed.Its time and space complexity are (U/Cl).Then an efficient algorithm of attribute reduction based on Skow mon s discernibility matrix was designed with the new function.Its time complexity is cut dow n to o(cllUl)+(l cl21 U/Cl),and space complexity to o(l Ul )Finally,an example was used to il- lustrate the effectiveness of the new algorithm. KEY WORDS rough set:discernibility matrix:attibute reduction:complexity 粗糙集理论是由Pawlak习于1982年提出的，明矩阵的属性约简响：王国胤等提出的基于信息目前被广泛应用于人工智能、模式识别、数据挖掘和熵的属性约简.文献8指出这三种属性约简定智能决策等领域：它是一种新的处理不精确、不完全义在不协调决策表中彼此相互不等价.因此，有许与不相容知识的数学理论.在粗糙集理中，属性约多学者致力于各种不同属性约简算法的设计与简（也称知识约简）是粗糙集理论的重要研究内容之分析. 一，目前己出现了多种属性约简定义及其相应的算由于基于Skow ron分明矩阵的属性约简定义法.最常见的有：Paw lak提出的基于正区域的属性直观且易于理解同时用分明矩阵能快速地求出核约简F习：Skow ron和Hu等提出的基于Skow ron分属性故这种属性约简引起了许多学者的关注，并成收稿日期：200803-26 基金项目：国家自然科学基金资助项目(No.60675030):北京市教委科技发展计划面上项目(NaKM200910772013) 作者简介：秦奕青(1969一），女，别教授，博士，E-mail:q-cmil@iaom.cm杨炳儒(1943一)，男，教授，博士生导师

基于 Skowron 分明矩阵的有效属性约简算法秦奕青1, 2) 杨炳儒2) 徐章艳2, 3) 1) 北京信息科技大学计算机学院, 北京 100192 2) 北京科技大学信息工程学院, 北京 100083 3) 广西师范大学计算机系, 桂林 541004 摘要为降低基于 Skow ron 分明矩阵属性约简算法的复杂度, 提出了简化分明矩阵及其相应属性约简的定义, 并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上, 定义了一个函数, 该函数能度量条件属性在简化分明矩阵中出现的频率, 并给出了计算该函数的快速算法, 其时间和空间复杂度均为 O( U/ C ) .用该函数设计了一个有效的基于原分明矩阵属性约简算法, 算法的时间复杂度降为 O( C U ) +O( C 2 U/ C ), 空间复杂度降为 O ( U ) ;并用实例证明了算法的有效性. 关键词粗糙集;分明矩阵;属性约简;复杂度分类号 TP301.6 Efficient algorithm of attribute reduction based on Skowrons discernibility matrix QIN Yi-qing 1, 2 , YANG Bing-ru 2 , XU Zhang-yan 2, 3 1) College of Computer, Beijing Inf ormation Science and Technology University, Beijing 100192, China 2) School of Information Engineering, Universit y of Science and Tech nology Beijing, Beijing 100083, China 3) Department of C omput er, Guangxi Normal University, Guilin 541004, China ABSTRACT To cut down the time and space complexity and improv e the efficiency of the attribute reduction alg orithm based on Skowron' s discernibility matrix , the definitions of a simplified discernibility matrix and corresponding a ttribute reduction were provided.It is proved that attribute reduction based on the simplified discernibility matrix is equivalent to that based on the old o ne.By the foundation of a simplified decision table, a function w hich can measure the frequency of a condition attribute in the simplified discernibility matrix w as defined.An alg orithm fo r the above function w as designed.Its time and space complexity are O ( U/ C ) .Then an efficient alg orithm of a ttribute reductio n based on Skow ro n' s discernibility matrix was designed with the new function .Its time complex ity is cut dow n to O ( C U ) +O( C 2 U/ C ), and space complexity to O( U ) .Finally , an example was used to illustrate the effectiveness of the new algo rithm . KEY WORDS rough set ;discernibility matrix;attribute reduction;complexity 收稿日期:2008-03-26 基金项目:国家自然科学基金资助项目( No .60675030) ;北京市教委科技发展计划面上项目( No.KM200910772013) 作者简介:秦奕青( 1969—) , 女, 副教授, 博士, E-mail:qyq -email@sina.com .cn;杨炳儒( 1943—) , 男, 教授, 博士生导师粗糙集理论是由 Paw lak [ 1-2] 于 1982 年提出的, 目前被广泛应用于人工智能、模式识别、数据挖掘和智能决策等领域 ;它是一种新的处理不精确、不完全与不相容知识的数学理论.在粗糙集理中, 属性约简(也称知识约简)是粗糙集理论的重要研究内容之一, 目前已出现了多种属性约简定义及其相应的算法.最常见的有:Paw lak 提出的基于正区域的属性约简[ 1-2] ;Skow ron 和 Hu 等提出的基于 Skow ro n 分明矩阵的属性约简[ 3-6] ;王国胤等提出的基于信息熵的属性约简[ 7] .文献[ 8] 指出这三种属性约简定义在不协调决策表中彼此相互不等价 .因此, 有许多学者致力于各种不同属性约简算法的设计与分析. 由于基于 Skow ron 分明矩阵的属性约简定义直观且易于理解, 同时用分明矩阵能快速地求出核属性, 故这种属性约简引起了许多学者的关注, 并成第 31 卷第 3 期 2009 年 3 月北京科技大学学报 Journal of University of Science and Technology Beijing Vol .31 No.3 Mar.2009 DOI :10.13374/j .issn1001 -053x.2009.03.048

第3期秦奕青等：基于Skowron分明矩阵的有效属性约简算法 ·399。功地将这种属性约简引入其他的应用领域1.文献表示，简记为U/P.划分U/P中的任何元素 [56从基于分明矩阵属性约简的定义出发，以分 [xp={ylHa∈P,fx,a)=f(y,a}称为等明矩阵的元素为启发信息，设计了基于Skow ron分价类. 明矩阵的属性约简算法，其时间复杂度均为定义2在决策表S=(U,C,D,V,f)中， O(|C2|U2).在这类算法中，首先要求出决策表 HR二CUD,XU,记U/R={R1,R2,,R}, 的分明矩阵，而求决策表的分明矩阵的时间复杂度则称R-(X)=U{R:R:∈U/R,R:二X}为X关和空间复杂度均为O(|C|U2):故这种方法不仅于R的下近似集. 耗时，而且要消耗大量的空间，一旦数据量很大，计定义3四在决策表S=(U,C,D,V,f)中，算机的存储空间就会出现问题可.文献9，中设计设U/D={DL,D2,,Dk}表示由决策属性集D 的属性约简算法，其思路与文献5一6]中的思路相对论域U的划分，U/C={C,C2,:Cm}表示由同，只是用不同的启发式策略，其时间复杂度为条件属性集C对论域U的划分，其中C(i=L,2 oIC|U21Cl+lgU1))(注：原文的时间复杂 m)称为基本块，称POSc(D)=从wC-(D) 度分析有误其算法的第4步是循环，可是作者没有为C关于D的正区域. 计算循环的最坏次数).也就是说如果先求分明矩定义48,10设在决策表S=(U,C,D,V,f) 阵，再用分明矩阵的信息去设计属性约简算法，其时中，记U1C=[x1c,[xc,;【xmch,U= 间复杂度一般不大理想.为了设计更有效的算法， {x1,x2,;xm}.设POSc(D=[,]cU[x,]cU… 本文首先引入简化决策表的定义，并利用文献[10 中快速求划分U/C的算法，给出一个快速求简化 U[c其中{xi,x,xi}∈U'且I[x的c/ 决策表的算法，其时间复杂度为O(|C|U):然后 Dl=1(s=1,2,3以，记U={x,x,x, 提出了简化分明矩阵及其相应的属性约简定义，并 U=U-Ups.称S=(U,C,D,V,f)为简化证明新属性约简定义与基于原分明矩阵的属性约简决策表. 定义等价.在简化决策表的基础上，定义了一个函定义4在决策表S=(U,C,D,口，f) 数，该函数能度量条件属性在简化分明矩阵中出现中，设Skow ron分明矩阵M=(mi)mxm,其元素的频率，并给出了计算该函数的快速算法.该算法 mi,j如下：不用求出分明矩阵，其时间和空间复杂度均为 {ala∈C,f(xi,a)≠f(x,a), O(|U/C).用该函数设计了有效的基于原 1m访三 f(xi,D)≠f(x,D》 Skow ron分明矩阵的属性约简算法，算法的时间复 0,否则杂度降为O(1CIU)+o(IC2|U/C),空间复定义6到在决策表S=(U,C,D,V,f)中，杂度降为O(U).最后用一个实例说明了新算法设M=(m)nxn是分明矩阵，HB二C.若B满足：的有效性. 1)H0≠(m访∈M),有B∩m≠0， 1基于Skowron的简化分明矩阵 (2)b∈B,B-{b},不满足(1)，则称B是C相对于D的基于分明矩阵的属性约定义1四五元组S=(U,C,D,V,f)是一个简. 决策表.其中U={x1,x2,；x}表示对象的非空定义7在决策表S=(U,C,D,V,f)中，有限集，称为论域；C表示条件属性的非空有限集， S'=(U,C,D,V,f)为其简化决策表定义该简 D表示决策属性的非空有限集，C∩D=O:V= 化决策表的分明矩阵（简称简化分明矩阵）M'= ,n'a,Va是属性a的值域：fUX(CUD)→ (m),其元素定义如下： aE0D V,是一个信息函数，它对一个对象的每一个属性赋 {ala∈C,f川x,a)≠f川x,a),当x, 予一个信息值即Ha∈CUD,x∈U,有f(x,a)∈ x至多一个在Um中；f(x,a)≠ 'a.每一个属性子集P口CUD)决定了一个二元 m'= f,a),f(xi,D≠fx,D), 不可区分关系IND(P): 当xi,x都在Upa中} IND(P)={(x,y)∈UX U Ya∈P, 0,否则 f(x,a)=f(y,a)). 定义8在决策表S=(U,C,D,V,f)中，关系IND(P)构成了U的一个划分，用U/IND(P) S'=(U,CD,V,f)为其简化决策表，M=

功地将这种属性约简引入其他的应用领域 [ 5] .文献 [ 5-6] 从基于分明矩阵属性约简的定义出发, 以分明矩阵的元素为启发信息, 设计了基于 Skow ron 分明矩阵的属性约简算法, 其时间复杂度均为 O( C 2 U 2 ) .在这类算法中, 首先要求出决策表的分明矩阵, 而求决策表的分明矩阵的时间复杂度和空间复杂度均为 O( C U 2 ) ;故这种方法不仅耗时, 而且要消耗大量的空间, 一旦数据量很大, 计算机的存储空间就会出现问题[ 6] .文献[ 9] 中设计的属性约简算法, 其思路与文献[ 5-6] 中的思路相同, 只是用不同的启发式策略, 其时间复杂度为 O( C U 2 ( C +lg U ) )( 注:原文的时间复杂度分析有误, 其算法的第 4 步是循环, 可是作者没有计算循环的最坏次数) .也就是说, 如果先求分明矩阵, 再用分明矩阵的信息去设计属性约简算法, 其时间复杂度一般不大理想.为了设计更有效的算法, 本文首先引入简化决策表的定义, 并利用文献[ 10] 中快速求划分 U/C 的算法, 给出一个快速求简化决策表的算法, 其时间复杂度为O( C U ) ;然后提出了简化分明矩阵及其相应的属性约简定义, 并证明新属性约简定义与基于原分明矩阵的属性约简定义等价.在简化决策表的基础上, 定义了一个函数, 该函数能度量条件属性在简化分明矩阵中出现的频率, 并给出了计算该函数的快速算法.该算法不用求出分明矩阵, 其时间和空间复杂度均为 O( U/ C ) .用该函数设计了有效的基于原 Skow ron 分明矩阵的属性约简算法, 算法的时间复杂度降为 O( C U ) +O( C 2 U/C ) , 空间复杂度降为 O( U ) .最后用一个实例说明了新算法的有效性 . 1 基于 Skowron 的简化分明矩阵定义 1 [ 1] 五元组 S =( U, C, D, V, f )是一个决策表.其中 U ={x 1, x 2, …, xn}表示对象的非空有限集, 称为论域 ;C 表示条件属性的非空有限集, D 表示决策属性的非空有限集, C ∩ D = ;V = ∪ a∈ C∪ D Va , Va 是属性 a 的值域 ;f ∶U ×( C ∪ D) ※ V, 是一个信息函数, 它对一个对象的每一个属性赋予一个信息值, 即 a ∈ C ∪D, x ∈ U , 有f ( x, a) ∈ Va .每一个属性子集 P ( C ∪ D) 决定了一个二元不可区分关系 IND( P ) : IND( P ) ={( x , y) ∈ U ×U a ∈ P, f ( x , a) =f ( y , a)}. 关系 IND( P)构成了 U 的一个划分, 用 U/ IND(P ) 表示, 简记为 U/P .划分 U/ P 中的任何元素 [ x] P ={y a ∈ P , f ( x , a ) =f ( y, a )}称为等价类. 定义 2 [ 1] 在决策表 S =( U, C, D, V , f ) 中, R C ∪ D, X U , 记 U/ R ={R 1, R2, …, R l}, 则称 R -( X ) =∪ {Ri R i ∈ U/ R , Ri X}为 X 关于R 的下近似集. 定义 3 [ 1] 在决策表 S =( U, C, D, V , f ) 中, 设 U/D ={D1, D2, …, Dk}表示由决策属性集 D 对论域U 的划分, U/C ={C1, C2, …, Cm }表示由条件属性集 C 对论域U 的划分, 其中 Ci( i =1, 2, …, m)称为基本块, 称 POSC ( D) = ∪ D i ∈ U/ D C -( Di) 为 C 关于D 的正区域 . 定义 4 [ 8, 10] 设在决策表 S =( U, C, D, V, f ) 中, 记 U/C ={[ x′1] C, [ x′2] C, …, [ x′m] C}, U′= {x′1, x′2, …, x′m}.设 POSC ( D) =[ x′i 1 ] C ∪[ x′i 2 ] C ∪ … ∪[ x′i t ] C, 其中{x′i 1 , x′i 2 , …, x′i t} U′且 [ x′i s ] C/ D =1( s =1, 2, …, t), 记 U′pos ={x′i 1 , x′i 2 , …, x′i t}, Uneg =U -Upos .称 S′=( U′, C, D, V , f ) 为简化决策表 . 定义 5 [ 3-4] 在决策表 S =( U, C, D, V, f ) 中, 设 Skow ron 分明矩阵 M =( mij ) n ×n, 其元素 mi , j如下 : mij = {a a ∈ C, f ( xi , a) ≠f ( x j , a), f ( x i , D) ≠f ( xj , D)} , 否则定义 6 [ 3] 在决策表 S =( U, C, D, V , f ) 中, 设 M =( mij) n ×n是分明矩阵, B C .若 B 满足: ( 1) ≠( mij ∈ M ), 有 B ∩ mij ≠ , ( 2) b ∈ B , B -{b}, 不满足( 1) , 则称 B 是 C 相对于D 的基于分明矩阵的属性约简 . 定义 7 在决策表 S =( U, C, D, V , f ) 中, S′=( U′, C, D, V , f ) 为其简化决策表, 定义该简化决策表的分明矩阵(简称简化分明矩阵) M′= ( mi′j′), 其元素定义如下 : mi′j′= {a a ∈ C, f( x i′, a) ≠f( x j′, a) , 当 xi′, xj′至多一个在U′po s中;f ( xi′, a ) ≠ f ( xj′, a), f ( x i′, D) ≠f ( xj′, D), 当 x i′, xj′都在U′pos中} , 否则定义 8 在决策表 S =( U, C, D, V , f ) 中, S′=( U′, C, D, V , f) 为其简化决策表, M′= 第 3 期秦奕青等:基于 Skowron 分明矩阵的有效属性约简算法 · 399 ·

。400 北京科技大学学报第31卷 (m出)是简化分明矩阵，HB二C,若B满足： 2求简化决策表的快速算法 (1)H0≠(m∈M),有B∩m≠0， (2)Hb∈B,B一{b},不满足(1)，用文献[8.10中的算法来计算简化决策表，其则称B是C相对于D的基于简化分明矩阵的属性时间复杂度为O(|CIU). 约简. 算法1求简化决策表. 定理1在决策表S=(U,C,D,V,f)中，输入：决策表S=(U,C,D,',f),U={x1, M=(m)xm是分明矩阵，M'=(mH)是简化分明 x2,…;xm},C={c1,C2,…,c}; 矩阵，则二者具有相同的非空元素. 输出：Us,Ug,mi,MmD,Mo(i=L,2, 证明对于V0≠(m∈M),则存在xi,x∈ r). U使得xi∈[xlc,x∈[Jc若[xc/D|= (1)对每一个G(i=1,2,；r)和D统计， I[c/D=I时，则有xi,x∈U·由简化决策 f(xi,G)和f(,D(j=1,2,…n)的最大值和最表的定义知有：f(x,D)=f(xi,D)≠f(x,D)= 小值，分别记为M:和m:以及MD和mD; f(x,D).由简化分明矩阵的定义知m=m (2)以静态链表依次存储对象x1,x2,,xm: 令表头指针指向x1; 若[xc/D=1和[c/Dl=1中至少有一个不 (3)for(i=1:r+1:i++) 成立，则x,x至多有一个在U中，由简化分明矩 ①第i趟“分配”：建立M一m十1空对列，令阵的定义知m'=m.即VO≠(m∈M),总存 frontk和endk(k=0,l,2,；Mi-m:)分别为第k 在m∈M使得m)=m前：个对列的头指针和尾指针，将链表中的对象x∈U 对于H0≠(m∈M),则存在xi,灯∈U使按链表中的次序分配到第f(x,G)一m:个对列得xi∈[xc,∈[xc.当xi,x∈U时，由简中去：化分明矩阵的定义知有f(x,D=f(xi,D)≠f ②第i趟“收集”：表头指针指向第一个非空对 (x,D)=f升x,D).由M的定义知m=m.当列的头指针，修改每一个非空对列的尾指针，令其指 xi,至多有一个在Up中时，无妨设xi∈Ug,若向下一个非空对列的对头对象，这样将M一m十1 f川x,D)=fx,D)≠f川x,D)=fx,D),由分个对列重新组成一个链表：明矩阵的定义知m=m;若f(x,D)= (4)设由第(3)步得到链表中的对象序列为x1, fx,D),由于x∈U且x∈[xc,故一定3xH x2,…;xm ∈c使得f(x,D)≠f(x,D),从而有f1, 1=1;B,={x1}: D)卡f(,D,由分明矩阵的定义知mml=m for (j=2;K n;j) 若任一G∈C(i=L,2,r)均有f(x,c= 即H0≠(m∈M),总存在mi∈M使得m= f(x广，c),则B,=B,U火}：否则{t=1十1；B,= mi'i. {}: 综上所述，命题成立. (5)Ue=0:Uig=0 定理1说明简化分明矩阵与分明矩阵具有相同 for(i=1;Kt+1;i++) 的非空元素.由简化分明矩阵的定义知，简化分明若B;中所有对象在决策属性上取值均相同，则矩阵的元素个数比分明矩阵的元素个数要少一些，取出B:中的第一个对象并入U:否则将B:中的但是它们具有同样的非空元素，这说明简化分明矩第一个对象并入U 阵去掉了许多重复的元素，因此简化分明矩阵要比分明矩阵简洁.另一方面，根据属性约简的定义可 3有效的属性约简算法知：属性约简只与分明矩阵的非空元素有关因而可在文献[3子6,9]中，首先要求出分明矩阵，然后得出如下的定理. 再用分明矩阵的元素设计启发信息以完成属性约简定理2在决策表S=(U,C,D,V,f)中，基算法的设计；但是求出分明矩阵是一个既耗时间又于Skow ron分明矩阵的属性约简与基于简化分明耗空间的方法.正如文献6所说，一旦决策表的数矩阵的属性约简等价. 据变为海量数据时，计算机的存储空间就有问题. 定理2说明基于Skow ron分明矩阵的属性约简因此用这种方法去设计算法，只能处理数据量不太可建立在简化分明矩阵上. 大的决策表：对于大型决策表而言，这种设计方法是

( mi′j′)是简化分明矩阵, B C, 若 B 满足: ( 1) ≠( mi′j′∈ M′) , 有 B ∩ mi′j′≠ , ( 2) b ∈ B , B -{b}, 不满足( 1), 则称 B 是 C 相对于D 的基于简化分明矩阵的属性约简 . 定理 1 在决策表 S =( U, C, D, V , f ) 中, M =( mij) n ×n是分明矩阵, M′=( mi′j′)是简化分明矩阵, 则二者具有相同的非空元素 . 证明对于 ≠( mij ∈ M ), 则存在 x′i , x′j ∈ U′使得 x′i ∈[ x i] C, x′j ∈ [ xj ] C .若 [ xi] C/D = [ xj] C/D =1 时, 则有 x′i , x′j ∈ U′pos .由简化决策表的定义知有:f ( xi , D) =f ( x′i , D) ≠f ( x′j , D) = f ( xj , D) .由简化分明矩阵的定义知 mi′j′=mij ; 若 [ x i] C/D =1和 [ xj] C/D =1 中至少有一个不成立, 则 x′i , x′j 至多有一个在U′pos中, 由简化分明矩阵的定义知mi′j′=mij .即 ≠( mij ∈ M ), 总存在mi′j′∈ M′使得mi′j′=mij . 对于 ≠( mi′j′∈ M′), 则存在 x i , xj ∈ U 使得x′i ∈[ x i] C , x′j ∈[ x j] C .当 x′i , x′j ∈ U′pos时, 由简化分明矩阵的定义知有 f ( x′i , D) =f ( x i , D) ≠f ( x j , D) =f( x′j , D) .由 M 的定义知mij =mi′j′.当 x′i , x′j 至多有一个在U′pos中时, 无妨设 x′i ∈ U′neg , 若 f ( xi , D) =f ( x′i , D) ≠f( x′j , D) =f ( xj , D) , 由分明矩阵的定义知 mij = mi′j′;若 f ( xi , D) = f ( xj , D), 由于x′i ∈ U′neg且 x′i ∈[ x i] C , 故一定 x i1 ∈[ xi] C 使得f ( x i1, D) ≠f ( x i , D), 从而有 f ( xi 1, D) ≠f ( xj , D), 由分明矩阵的定义知mm1j =mi′j′. 即 ≠( mi′j′∈ M′), 总存在 mij ∈ M 使得 mij = mi′j′. 综上所述, 命题成立 . 定理 1 说明简化分明矩阵与分明矩阵具有相同的非空元素 .由简化分明矩阵的定义知, 简化分明矩阵的元素个数比分明矩阵的元素个数要少一些, 但是它们具有同样的非空元素, 这说明简化分明矩阵去掉了许多重复的元素, 因此简化分明矩阵要比分明矩阵简洁.另一方面, 根据属性约简的定义可知:属性约简只与分明矩阵的非空元素有关, 因而可得出如下的定理 . 定理 2 在决策表 S =( U, C, D, V, f )中, 基于Skow ro n 分明矩阵的属性约简与基于简化分明矩阵的属性约简等价 . 定理 2 说明基于Skow ron 分明矩阵的属性约简可建立在简化分明矩阵上 . 2 求简化决策表的快速算法用文献[ 8, 10] 中的算法来计算简化决策表, 其时间复杂度为 O( C U ) . 算法 1 求简化决策表. 输入 :决策表 S =( U, C, D, V , f ), U ={x1, x 2, …, x n}, C ={c1, c2, …, cr}; 输出:U′pos, U′neg , mi , Mi, mD, MD ( i =1, 2, …, r) . (1) 对每一个 ci ( i =1, 2, …, r) 和 D 统计, f ( x j , ci)和 f ( xj , D)( j =1, 2, …, n )的最大值和最小值, 分别记为 Mi 和 mi 以及MD 和mD ; ( 2) 以静态链表依次存储对象 x1, x 2, …, x n ; 令表头指针指向 x 1 ; ( 3) fo r ( i =1 ;i <r +1 ;i ++) ①第 i 趟“分配” :建立 Mi -mi +1 空对列, 令 front k 和endk ( k =0, 1, 2, …, Mi -mi ) 分别为第 k 个对列的头指针和尾指针, 将链表中的对象 x ∈ U 按链表中的次序分配到第 f ( x , ci ) -mi 个对列中去; ②第 i 趟“收集” :表头指针指向第一个非空对列的头指针, 修改每一个非空对列的尾指针, 令其指向下一个非空对列的对头对象, 这样将 Mi -mi +1 个对列重新组成一个链表; ( 4) 设由第( 3)步得到链表中的对象序列为 x′1, x′2, …, x′n ; t =1 ;Bt ={x′1}; fo r ( j =2 ;j <n +1 ;j ++) 若任一 ci ∈ C( i =1, 2, …, r) 均有 f ( x′j , ci) = f ( x′j-1, ci), 则 Bt =Bt ∪{x′j};否则{t =t +1 ;Bt = {x′j}}; ( 5) U′pos = ;U′neg = fo r ( i =1 ;i <t +1 ;i ++) 若 B i 中所有对象在决策属性上取值均相同, 则取出 B i 中的第一个对象并入U′pos ;否则将 Bi 中的第一个对象并入U′neg . 3 有效的属性约简算法在文献[ 3-6, 9] 中, 首先要求出分明矩阵, 然后再用分明矩阵的元素设计启发信息以完成属性约简算法的设计;但是求出分明矩阵是一个既耗时间又耗空间的方法 .正如文献[ 6] 所说, 一旦决策表的数据变为海量数据时, 计算机的存储空间就有问题. 因此用这种方法去设计算法, 只能处理数据量不太大的决策表 ;对于大型决策表而言, 这种设计方法是 · 400 · 北京科技大学学报第 31 卷

第3期秦奕青等：基于Skowron分明矩阵的有效属性约简算法 ·401。不可取的定理3在决策表S=(U,C,D,V,f)中，对于决策表1而言，其分明矩阵的元素为： S=(U,C,D,V,f)为其简化决策表，M= abc),{abd),bed),(bed),bd,acd),cd), (m)是简化分明矩阵，Ha∈C,记U'/{a}= {abc},{abcd}}.在该分明矩阵中，各属性的频率分别为：a5;b7:c7:d7.这种频率的计算是 (,4&y4则函数Ga=U)-空建立在分明矩阵上，也就是要求出分明矩阵才能计表示简化分明矩阵中条件属性α出现的频率. 算出相应频率.但是，这样的计算复杂性不好，其计证明对于HA:∈U'/{a},由f(A)的定义算分明矩阵的代价太大.有一种计算属性频率的方知：f川A)表示由对象集A,产生的简化分明矩阵法不用去求分明矩阵：若求出U/{a}后，也可以求的非空元素的个数.另一方面由于A:∈U'/{a以，出属性a的频率.对于决策表1有U/D={XL, 故对于A:中任意两对象产生的非空元素不可能出 X4),{X2},{X3},{X5},且该决策表的所有对象都现条件属性a.f(U)表示简化分明矩阵中所有包在正区域内，故它能产生的非空元素有C一1=9，因为{X1,X4)不能产生差别元素.U/{a}={X1, 含条件属性a的非控元素的次数.由分析知习f) X5},{X2,X3,X4}.{X1,X5}是不能产生带有属性表示简化分明矩阵中所有不包含条件属性α的非 a的差别元素共1个，{X2,X3,X4}是不能产生带有空元素的次数.故G(a)表示简化分明矩阵中条件属性a的差别元素共3个，故产生带有属性a的差属性a出现的频率. 别元素共9一4=5个.利用这种思想设计如下的启定理41g在决策表S=(U,C,D,V,f)中，以函数. HB三C,Ha∈(C-B),记U/B={B1,B2,；表1决策表1 B,则有UBU{a)=B/a. Table 1 Decision table 1 定义10在简化决策表S'=(U',C,D,V,f) 中，HB三C,Ha∈(C-B),记U'/B={B1,B2 XI 0 ,B},由定理3可设B/{a}={B1,B2, X2 Ba,定义函数如下：七 3 X4 3 Ha(a)= f(B) =1j=1 X5 特别地，当B为空集时，显然有Ho(a)= 定义9在决策表S=(U,C,D,V,f)中， G(a).由定理3的证明过程知， 2f(B)表示简 S'=(U,C,D,V,f)为其简化决策表HX= 化分明矩阵中所有不包含条件属性集B的非空元 XpU Xneg∈U'=U poU Uirg,其中Xm∈Ua, X∈U记Xm/D={D1,D2,,Dh,定义函素的个数，而空1B:)表示情化分明矩阵中数f(X)如下：所有不包含条件属性集BU{a}的非空元素的个 rw=x.l--空Dg-+ 数.因此(a)表示简化分明矩阵中去掉包含条件 2 2 属性集B的非空元素后，条件属性a出现的频率. X(X.-业+1X1. 这与通常用分明矩阵的条件属性的频率作为启发信 2 息设计的属性约简算法是一样的，只不过计算当X=U'时，f(U)表示了简化分明矩阵产生的非 Hs(a)的时间复杂度和空间复杂度要好一些. 空元素个数.其中U-山表示U中算法2计算Hs(a)的算法对象产生的非空元素个数，|U川U|表示由输入：U/B={B1,B2,；B1},Ma,ma,mD, U和U'中对象产生的非空元素个数， MD,S= Lu--业-名gl-表示由 2 2 输出：U'1(BU{a,S2= U中对象产生的非空元素个数，这可以由简化分 f(Bg). 明矩阵的定义得出.显然∫(X)就是表示由对象集 HB(a)=S1-S2. X产生的简化分明矩阵的非空元素的个数. (1)S2=0:

。402 北京科技大学学报第31卷 (2)对B={x1,x2,}∈U/B,以静态 (2)R=0:计算f(U'): 链表依次存储对象x1,x2,;,;令表头指针指向 (3)对Ha∈C-R,计算HR(c:令Hr(b)= X1; 巴匙RH(c以若这样的b不止一个，则任选一个： ①建立Ma一ma十1空对列，令front[]和 R=RU(b); end(k=0,1,2,;Ma-ma)分别为第k个对 (4)若U'/R=0则算法终止，输出属性约简列的头指针和尾指针，将链表中的对象x∈B:按链 R,否则转步聚(3)：表中的次序分配到第f(x,a)一ma个对列中去；算法3的复杂度分析如下.第(1)步求出的是 ②对由第①步得到每一非空对列作如下处理：原决策表的简化决策表，其时间复杂度为 (a)S=0: o(小C|U川)：第(2)步的时间复杂度为O1U'I): (b)将非空对列中属于Um的对象放入集合第(3)步的最坏时间复杂度为O(C一|R川UI), k1,属于U的对象放入k2,计算第(3)和第(4)步总的最坏时间复杂度为 S=|kl×(1kl-1)/2+1k2l×(1k21-1)/ 0(CIU'1)+0(IC1-1)1U'1)+…+ 2+|kl×|k2l: 0(1U'1)=01C21U'1)=01C2|U1cl).故 (c)用算法1第(3)步的方法求出k1/D={K1, 算法3最坏的时间复杂度为O(1C|IU丨)十 K2,,K,计算S=S一之lK④K-业，若 o(C1U/Cl),空间复杂度为o|Ul). 2 S=0则删除该对列，否则输出该对列，并计算S2= 4实例 S2+S: 以文献10]中的决策表2为例（表2），说明新 ③输出HB(a)=S1一S2. 算法的高效性.对决策表1的15个对象U,用算法算法说明及其复杂度分析如下.在算法2中， 1计算U/{a,b,c,d},过程如下(c1=a,c2=b, 当S=0,删除该对列.这是因为S=0时，即 c3=c,c4=d)(见文献10). f(X)=0,由f(X)的定义可知只有两种情况：第一表2决策表2 种是X只有一个对象，此时X没有必要保留：第二 Table 2 Decision Table 2 种是X有多个对象，但它们均属于U,且它们的 U b d D 决策属性值均相等，由简化分明矩阵的定义可知，它 XI 0 们不可能产生简化分明矩阵的非空元素，故X没有 X2 1 必要保留. X3 0 算法2第①步的时间复杂度为O(B:I);设 X4 0 B/八a}={B1,Bi2,B},则第(b)步的时间复杂 X5 度也为O(Bl)(j=1,2,,t小，第(c步的时间复杂度为O(|k1)≤O(Bl),得第②步总的时间复杂度为O(|B1l)+O(|B2l)++O(BI)= O(|B).由此得到第(2)步总的时间复杂度为 X9 o(B)+o(B21)+.+o(Bl)o(U). X10 所以算法2最坏的时间复杂度为O(UI).同理 X11 可得最坏的空间复杂度为O(|U1). X12 3 在算法2的基础上，可以设计如下有效的基于 X13 4 2 分明矩阵的属性约简算法. X14 2 算法3基于分明矩阵的有效属性约简算法： X15 2 输入：决策表S=(U,C,D,V,f),U={x1, x2,,xn},C={C1,c2,5Cr}; 由算法3的第(1)步：Ma=4,ma=1;M6=3, 输出：属性约简R. mb=1;Me=4,me=1;Ma=3,m4=1:MD=3. (1)由算法1求出：Ups,Ung,M,m(i=L, mD=0;Um={X1,X2,X8,X4};Umg={X6,X7, 2,,r)和MD,mD; X13}.故得到的简化决策表如表3所示

( 2) 对 Bi ={x 1, x 2, …, xj}∈ U′/B , 以静态链表依次存储对象 x 1, x 2, …, xj ;令表头指针指向 x 1 ; ①建立 Ma -ma +1 空对列, 令 front[ k ] 和 end[ k] ( k =0, 1, 2, …, Ma -ma ) 分别为第 k 个对列的头指针和尾指针, 将链表中的对象 x ∈ Bi 按链表中的次序分配到第 f ( x , a) -ma 个对列中去 ; ②对由第 ①步得到每一非空对列作如下处理: ( a) S =0 ; ( b) 将非空对列中属于 U′po s的对象放入集合 k 1, 属于 U′neg的对象放入 k2, 计算 S = k 1 ×( k 1 -1) /2 + k 2 ×( k 2 -1)/ 2 + k 1 × k2 ; ( c) 用算法 1 第( 3)步的方法求出 k1/D ={K 1, K 2, …, Ks}, 计算 S =S - ∑ s i =1 Ki ( Ki -1) 2 , 若 S =0 则删除该对列, 否则输出该对列, 并计算 S2 = S 2 +S ; ③输出 HB( a ) =S 1 -S 2 . 算法说明及其复杂度分析如下 .在算法 2 中, 当 S =0, 删除该对列 .这是因为 S =0 时, 即 f ( X ) =0, 由 f ( X )的定义可知只有两种情况:第一种是 X 只有一个对象, 此时 X 没有必要保留;第二种是 X 有多个对象, 但它们均属于 U′pos, 且它们的决策属性值均相等, 由简化分明矩阵的定义可知, 它们不可能产生简化分明矩阵的非空元素, 故 X 没有必要保留 . 算法 2 第 ①步的时间复杂度为 O ( Bi ) ;设 Bi/{a}={B i1, Bi 2, …, B it}, 则第( b) 步的时间复杂度也为 O( B ij )( j =1, 2, …, t), 第( c) 步的时间复杂度为 O( k 1 ) ≤O( Bij ) , 得第 ②步总的时间复杂度为 O ( Bi 1 ) +O ( Bi 2 ) +…+O( Bit ) = O( Bi ) .由此得到第( 2) 步总的时间复杂度为 O( B 1 ) +O( B 2 ) +…+O( Bl ) ≤O( U′ ) . 所以算法 2 最坏的时间复杂度为 O( U′ ) .同理可得最坏的空间复杂度为 O( U′ ) . 在算法 2 的基础上, 可以设计如下有效的基于分明矩阵的属性约简算法 . 算法 3 基于分明矩阵的有效属性约简算法: 输入:决策表 S =( U , C, D, V , f ) , U ={x 1, x 2, …, xn}, C ={c1, c2, …, cr}; 输出 :属性约简 R . ( 1) 由算法 1 求出 :U′pos, U′neg , Mi , mi( i =1, 2, …, r)和 MD, mD ; ( 2) R = ;计算 f ( U′) ; ( 3) 对 ci ∈ C -R , 计算 HR( ci) ;令 HR( b) = max c i ∈ C -R HR( ci), 若这样的 b 不止一个, 则任选一个; R =R ∪{b}; ( 4) 若 U′/ R = 则算法终止, 输出属性约简 R , 否则转步聚( 3) ; 算法 3 的复杂度分析如下 .第( 1)步求出的是原决策表的简化决策表, 其时间复杂度为 O( C U ) ;第( 2)步的时间复杂度为 O( U′ ) ; 第( 3)步的最坏时间复杂度为 O(( C - R ) U′ ), 第( 3 ) 和第 ( 4 ) 步总的最坏时间复杂度为 O(( C U′ ) +O (( C -1) U′ ) + … + O( U′ ) =O( C 2 U′ ) =O( C 2 U/C ) .故算法 3 最坏的时间复杂度为 O ( C U ) + O( C 2 U/ C ), 空间复杂度为 O( U ) . 4 实例以文献[ 10] 中的决策表 2 为例(表 2) , 说明新算法的高效性.对决策表 1 的 15 个对象 U, 用算法 1 计算 U/{a, b, c, d}, 过程如下( c1 =a, c2 =b, c3 =c, c4 =d ) (见文献[ 10] ) . 表 2 决策表 2 Table 2 Decision Table 2 U a b c d D X1 1 1 1 1 0 X2 2 2 2 1 1 X3 1 1 1 1 0 X4 2 3 2 3 0 X5 2 2 2 1 1 X6 3 1 2 1 0 X7 1 2 3 2 2 X8 2 3 1 2 3 X9 3 1 2 1 1 X10 1 2 3 2 2 X11 3 1 2 1 1 X12 2 3 1 2 3 X13 4 3 4 2 1 X14 1 2 3 2 3 X15 4 3 4 2 2 由算法 3 的第( 1)步 :Ma =4, ma =1 ;Mb =3, mb =1 ;Mc =4, mc =1 ;Md =3, md =1 ;MD =3, mD =0 ;U′pos ={X1, X2, X8, X4};U′neg ={X6, X7, X13}.故得到的简化决策表如表 3 所示. · 402 · 北京科技大学学报第 31 卷

第3期秦奕青等：基于Skowron分明矩阵的有效属性约简算法 403。表3决策表2的简化决策表 S2=4:U/{a}={XL,X7),{X2,X8,X4}. Table3 Sim plified table of Decision tabe 2 同理可得： U D H0(b)=S1-S2=20-5=15;S2=5: 0 U'/{b}={X1,X6,{X2,X7},{X8.X4,X13}. X2 2 2 2 H6(c)=S1-S2=20-4=16:S2=4: X8 2 1 2 3 U'/{c}={X1,X8,{X2,X4X6}. X4 2 3 2 3 0 Hd)=S1-S2=20-6=14:S2=6: X6 3 2 0 U'/{d}={XL,X2,X6,{X8,X7,X13}. X7 3 由算法3的第(3)步得到可供选择的属性有a X13 和c,在这里选择a.这时R=RU{a}={a}. 由算法3的第(2)步：Us/D={X1,X4}, 由算法的第(4)步知U/R≠0，故算法转第 {X2,{X8},f(U')=4×3/2-2×1/2+4X3+ (3)步. 3×2/2=20. 对Hr∈C-R={b,c,d},现计算H{a(r), 由第(3)步，计算Ho(a).下面以计算Ho(a) 以计算H(a(b)为例说明. 为例说明：这时输入：U/{a}={X1,X7},{X2,X8, 输入：U'/0={X1,X2,X8,X4,X6,X7, X4},M6=3,ma=1,MD=3,mD=0,S1=4. X13}},Ma=4,ma=1;MD=3,mD=0:S1= 由算法2的过程可得： f(U')=20. H{a(b)=S1-S2=4-1=3:S2=1: 由算法2的第(1)步得：S2=0. U'/{a,b}={X8,X4. 由算法2的第(2)步得： Ha(c)=3;S2=1;U'/{a,c}={X2,X4}. →X1→X2→X8→X4→X6→X7-→X13. H{a(d)=4:S2=0:U'/{a,d}=0. 由算法2的第①步得：由算法的第(3)步知选择属性d.这时R= font0→X1→X7←-emd01; RU{d}={a,d}.由于U'/{a,d}=0,故由第 front[]→X2→X8→X4←end]; (4)步知算法终止，输出属性约简R={a,d}. font2]→X6-end2]； 5结论 font3]→X13-end3). 对于front0→X1→X7end0,由算法2(a) 在现有基于分明矩阵的属性约简算法中，通常得到S=0;由(b)得到k1={X1},k2={X7},故有要先求出分明矩阵，这一过程是一个既耗时又耗空 S=1×(1-1)/2+1×(1-1)/2+1X1=1;由(c) 间的过程由此设计出的属约简算法，其时间复杂度得S=S-1×(1-1)/2=L,S2=S2+S=0+1=1. 也较高.为了降低该类属性约简算法的时间和空间对于front[l]→X2→X8→X4←-end],由(a) 复杂度，首先引入简化决策表的定义，然后给出简化得到S=0:由(b)得到k1={X1,X8,X4},k2=0, 分明矩阵的定义，证明简化分明矩阵与原分明矩阵故有S=3X(3-1)/2+0X(0-1)/2+1×0=3:由具有相同的非空元素，故简化分明矩阵去掉了原分 (c)得S=S-1×(1-1)/2-1×(1-1)/2- 明矩阵中大量的重复元素.为计算分明矩阵中条件 1×(1-1)/2=3,S2=S2+S=1+3=4. 属性出现的频率设计了一个新的求条件属性的频对于font[2]→X6end2],由算法2(a)得到率的函数，并设计了一种快速求该函数值的算法 S=0:由(b)得到k1=0,k2={X6},故有S=0:由该算法不用求出分明矩阵，其时间和空间复杂度均 (c步得S=S一0=0：由于S=0,故删除该对列. 为O(U/C).在此基础上，设计了一种有效的基对于font[2→X13-end2,由(a)得到S= 于Skow ron分明矩阵的属性约简算法.该算法的时 0:由(b)步得到k1=0,k2={X13},故有S=0:由间复杂度为o(小C|Ul)+O小C2|U/C|),空间 (c步得S=S一0=0：由于S=0,故删除该对列. 复杂度为O(|U引).该复杂度比相应属性约简算法由算法2得到：Ho(a)=S1-S2=20-4=16: 的复杂度要好