基于Skowron分明矩阵的有效属性约简算法

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 ma￾trix 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 provid￾ed.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 discerni￾bility 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 il￾lustrate 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:

不可取的 . 对于决策表 1 而言, 其分明矩阵的元素为 : {{abc}, {abd}, {bcd}, {bcd}, {bd }, {acd}, {cd}, {abc},{abcd}}.在该分明矩阵中, 各属性的频率 分别为:a∶5 ;b∶7 ;c∶7 ;d∶7 .这种频率的计算是 建立在分明矩阵上, 也就是要求出分明矩阵, 才能计 算出相应频率.但是, 这样的计算复杂性不好, 其计 算分明矩阵的代价太大.有一种计算属性频率的方 法不用去求分明矩阵 :若求出 U/{a}后, 也可以求 出属性 a 的频率 .对于决策表 1 有 U/D ={{X1, X4}, {X2}, {X3}, {X5}}, 且该决策表的所有对象都 在正区域内, 故它能产生的非空元素有 C 2 5 -1 =9, 因为{X1, X4}不能产生差别元素 .U/{a}={{X1, X5}, {X2, X3, X4}}.{X1, X5}是不能产生带有属性 a 的差别元素共 1 个, {X2, X3, X4}是不能产生带有 属性 a 的差别元素共 3 个, 故产生带有属性 a 的差 别元素共 9 -4 =5 个 .利用这种思想设计如下的启 以函数. 表 1 决策表 1 Table 1 Decision table 1 U a b c d D X1 1 1 1 1 0 X2 2 2 2 1 1 X3 2 3 1 2 3 X4 2 3 2 3 0 X5 1 2 3 2 2 定义 9 在决策表 S =( U, C, D, V , f ) 中, S′=( U′, C, D, V, f ) 为其简化决策表, X = X pos ∪ X neg U′=U′pos ∪ U′neg , 其中 X pos U′pos, X neg U′neg, 记 X po s/D ={D1, D2, …, Dt}, 定义函 数 f ( X ) 如下 : f( X) = Xpos ( X pos -1) 2 - ∑ t i =1 Di ( Di -1) 2 + X neg ( X neg -1) 2 + X pos X neg . 当 X =U′时, f ( U′) 表示了简化分明矩阵产生的非 空元素个数 .其中 U′neg ( U′neg -1) 2 表示 U′neg 中 对象产生的非空元素个数, U′pos U′neg 表示由 U′pos 和 U′neg 中 对 象 产 生 的 非 空 元 素 个 数, U′pos ( U′pos -1) 2 - ∑ t i =1 Di ( Di -1) 2 表示 由 U′pos中对象产生的非空元素个数, 这可以由简化分 明矩阵的定义得出 .显然 f ( X ) 就是表示由对象集 X 产生的简化分明矩阵的非空元素的个数. 定理 3 在决策表 S =( U, C, D, V , f ) 中, S′=( U′, C, D, V , f ) 为其简化决策表, M′= ( mi′j′) 是简化分明矩阵, a ∈ C, 记 U′/{a }= {A1, A2, …, Ak}, 则函数 G( a) =f ( U′) - ∑ k i =1 f ( Ai) 表示简化分明矩阵中条件属性 a 出现的频率 . 证明 对于 Ai ∈ U′/{a}, 由 f ( A i) 的定义 知 :f( Ai) 表示由对象集 Ai 产生的简化分明矩阵 的非空元素的个数 .另一方面由于 Ai ∈ U′/{a}, 故对于 Ai 中任意两对象产生的非空元素不可能出 现条件属性a .f ( U′) 表示简化分明矩阵中所有包 含条件属性 a 的非空元素的次数.由分析知 ∑ k i =1 f ( Ai) 表示简化分明矩阵中所有不包含条件属性 a 的非 空元素的次数.故 G( a )表示简化分明矩阵中条件 属性 a 出现的频率 . 定理 4 [ 10] 在决策表 S =( U , C, D, V, f ) 中, B C, a ∈ ( C -B ), 记 U/ B ={B 1, B 2, …, Bl}, 则有 U/( B ∪{a}) = ∪ B i ∈ U/B B i/{a}. 定义10 在简化决策表 S′=( U′, C, D, V , f) 中, B C, a ∈ ( C -B ) , 记 U′/B ={B 1, B2, …, B l}, 由定理 3 可设 B i/{a}={Bi 1, B i2, …, Bit}, 定义函数如下 : HB ( a) = ∑ l i =1 f( Bi) - ∑ l i =1 ∑ t j =1 f ( Bij) . 特别地, 当 B 为空集时, 显然有 H ( a) = G( a ) .由定理 3 的证明过程知, ∑ l i =1 f ( Bi) 表示简 化分明矩阵中所有不包含条件属性集 B 的非空元 素的个数, 而 ∑ l i =1 ∑ t j =1 f ( Bij ) 表示简化分明矩阵中 所有不包含条件属性集 B ∪ {a}的非空元素的个 数 .因此 HB ( a)表示简化分明矩阵中去掉包含条件 属性集 B 的非空元素后, 条件属性 a 出现的频率. 这与通常用分明矩阵的条件属性的频率作为启发信 息设计的属性约简算法是一样的, 只不过计算 HB( a )的时间复杂度和空间复杂度要好一些 . 算法 2 计算 HB( a) 的算法. 输入 :U′/B ={B1, B2, …, Bl}, Ma, ma, mD, MD , S 1= ∑ l i =1 f( Bi) ; 输出 :U′/ ( B ∪ {a}) , S 2 = ∑ l i =1 ∑ t j =1 f ( Bij ), HB( a ) =S 1 -S 2 . ( 1) S 2 =0 ; 第 3 期 秦奕青等:基于 Skowron 分明矩阵的有效属性约简算法 · 401 ·

。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 卷