一种快速的动态属性约简矩阵算法

D0I:10.13374才.issn1001663.2013.02.017 第35卷第2期 北京科技大学学报 Vol.35 No.2 2013年2月 Journal of University of Science and Technology Beijing Feb.2013 一种快速的动态属性约简矩阵算法 钱文彬12)四，杨炳儒12)，徐章艳3)，李慧12) 1)北京科技大学计算机与通信工程学院，北京1000832)材料领域知识工程北京市重点实验室，北京100083 3)广西师范大学计算机科学与信息工程学院，桂林541004 通信作者，E-mail:qianwenbin1(027@126.com 摘要针对实际决策表中对象动态变化的情况，首先引入简化决策表概念，别除决策表中大量重复的对象，并构造了 基于正区域的简化矩阵，有效地缩小了算法的搜索空间：然后从理论上阐述了基于简化矩阵的属性约简和基于矩阵的属 性约简的一致性，并仅需扫描一遍简化矩阵便可求解出属性约简：最后在原属性约简的基础上，提出一种快速的动态属 性约简矩阵算法.通过算例分析和实验对比验证了算法的有效性和可行性. 关键词粗糙集理论：属性约简：矩阵算法；决策表 分类号TP301.6 Efficient algorithm for dynamic attribute reduction based on a matrix QIAN Wen--bim,2)凶，YANG Bing-l,2）,XU Zhang-yan.3,LlHu,2) 1)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Beijing Key Laboratory of Knowledge Engineering for Materials Science,Beijing 100083,China 3)School of Computer Science and Information Engineering,Guangxi Normal University,Guilin 541004,China Corresponding author,E-mail:gianwenbin1027@126.com ABSTRACT Objects in actual decision tables are often changed dynamically.Aiming at this problem,the concept of a simplified decision table is introduced firstly,and a large number of repeated objects are deleted.A simplified matrix based on the positive region is constructed,which can reduce the searching space.What's more,it is theoretically analyzed that the definition of attribute reduction based on the simplified matrix is equal to that based on the un- simplified matrix.The proposed method scans only once the simplified matrix and it can be effectively utilized to the old attribute reduction.On this condition,an efficient algorithm for dynamic attribute reduction based on a matrix was designed.Finally,an example and its experimental comparison were employed to illustrate the efficiency and feasibility of the proposed algorithm. KEY WORDS rough set theory;attribute reduction;matrix algorithm;decision tables 粗糙集理论)作为一种不确定性、不完全和不方法、差别矩阵方法和矩阵方法.对于前两种技术 精确数据的数学工具，已经在知识发现、数据挖掘、 目前研究较为成熟，而利用矩阵方法的研究相对较 模式分类、生物信息学等领域取得成功应用2-，'设 少.Guan等12)提出信息系统下的矩阵方法，将 计高效的属性约简是粗糙集理论研究的核心问题之 信息系统下的等价关系利用矩阵的形式进行重新描 一，近年来，许多学者根据不同的需求，设计了不同述，并在此基础上设计了约简算法：但在整个过程 的属性约简算法，算法的计算效率取得显著进步.目 中矩阵仅是一种表示形式，并不能用来参与具体的 前常见的模型主要有基于正区域的属性约简6-、 计算，尤其不能刻画和评定论域集合与对象的等价 基于差别矩阵的属性约简8-9)和基于信息熵的属 类之间的关系. 性约简10-1川.这些模型主要使用的方法是启发式 现有大多数算法都集中在静态决策表的研究， 收稿日期：2011-12-12 基金项目：国家重点基础研究发展计划资助项目(2009CB522701):国家自然科学基金资助项目(61175048)：科技部创新方法专项 项目(2010IM020900):材料领域知识工程北京市重点实验室2012年度阶梯计划项目(No.Z121101002812005)资助

DOI ：10．13374／j ．issn1001－053x．2013．02．017

250 北京科技大学学报 第35卷 而有关动态决策表的属性约简算法研究的相关报道 决策表的矩阵定义为Mc=[rginxn,其元素定义 相对较少.已有学者利用启发式方法和差别矩阵 如下： 方法设计了决策表的动态约简算法，但未见到利用 r= 03ck∈C,f(x,ck)卡f(x,ck): 矩阵方法设计动态属性约简算法的研究成果13-16). 在工程应用领域中决策表（决策系统）的数据信息 1Vck EC,f(i,ck)=f(j,Ck) 大多都是动态变化的，使用静态的约简算法不能满 定义512☑1在决策表S=(U,CD,V,f)中，设 足实时性的需求.动态约简算法可在决策表发生变 Mc=[rglnxn为矩阵，3RCC,属性集R所对应 化时，无需重新计算决策表的属性约简，只需利用 的矩阵为MR=r]nxn,若R是基于矩阵的属性 原决策表的属性约简，针对变化的数据进行动态属 约简，当且仅当满足如下条件： 性约简，从而可有效提高约简算法的效率 (1)MR =Mc; 针对决策表中对象的动态变化的情况，利用矩 (2)对于Vck∈R,使得MR-{ck}卡Mc. 阵操作简洁且易于理解的优点.文中首先引入简化 定义651在决策表S=(U,C,D,V,f)中， 决策表的概念，对决策表进行简化，剔除决策表中 记U/C={lc,lc,…,znm]c},记U”= 大量重复的对象，并给出了基于正区域模型下简化 {x,x2,…,xm},设POSc(D)=4lcUz2lcU 矩阵的构造；然后从理论上详细分析了基于简化矩 …Ulc,其中{2…，}≤U且 阵的属性约简定义与基于矩阵的属性约简定义是一 .1c/D1=1(s=1,2,…,:记Uos= 致的，并将决策表中对象的变化情况映射到简化矩 {,2…,},Ueg=U-Upos’则称S= 阵中元素的动态变化，这样仅需扫描一遍简化矩阵 (U”,C,D,Vf)为简化的决策表. 中元素的动态变化情况便可求解属性约简；最后在 定义7在决策表S=(U,C,D,V,f)中，设 有效利用原属性约简的基础上，提出了一种快速的 S=(U',C,D,V,f)为简化决策表，简化的矩阵定 动态属性约简矩阵算法.新算法能有效地利用原决 义为：M'c=r,]nxn,其元素的定义如下： 策表的有用信息，使得算法的计算效率得到了有效 地提高，并通过算例分析和实验对比说明了算法是 0,ck∈C,f(,ck)≠f(a,ck)Af(x,D)卡 有效且可行的. f(x5,D)Ax,d)∈Upos; 0,ck∈C,f(z,ck)≠f(,ck)∧(r∈UnegA 1相关知识 r= ∈Usi 定义1决策表S=(UA,V,f),其中U= 0,ck∈C,f(x,c)卡f(x,ck)A(r∈ {c1,x2,·,xn}表示对象的非空有限集合，若A由 条件属性集C和决策属性集D组成，即CUD=A Uneg∈Upos) 且CnD=o,V=yVa,Va是属性a的 L,else. aECUD 值域，f:U×CUD→V是一个信息函数，即 a∈CUD,x∈U,有f(x,a)∈Va;每一个属性子 定义8在简化决策表S=(U',C,D,V,f) 集BC(CUD)决定一个等价关系IND(B)=aE 中，设M%=r9]nxn为简化矩阵，3R'CC,R'所 B,f(x,a)=f(y,a),简记为U/B. 对应的矩阵为MR=r]nx,若R是基于简化 矩阵的属性约简，当且仅当满足如下条件： 定义2在决策表S=(U,C,D,V,f)中，若 存在x,x;∈U,i卡j,对于ck∈C,使得 (1)MR=M6: f(xck)=f(x,ck)入f(,D)卡f(Ej,D),则称 (2)对于Vck∈R',使得M-{e}卡M6 x,5是不相容的，否则x,工是相容的.包含不相 定义g12设两矩阵为M=Tilnxn和 容对象的决策表称为不相容决策表，否则称之为相 M=[r号lnxn,则MnM2=rig Arilnxn,M1- 容决策表. M2=ri -riglnxn. 性质112在决策表S=(U,C,D,V,f)中，条 定义3在决策表S=(U,C,D,V,f)中，设 件属性集C={c1,c2,…,cs},对于c∈C所对应 U/D={D1,D2,·,Dk}表示决策属性D对论域 的划分，U/P={P,P,·,Pm}表示由条件属性 的矩阵为Me,}=rfonxn,则有Mc=沿Me小 集P(PSC)对论域U的划分，称POSP(D)=2一致性分析 D,品DP(D)为P关于D的正区域 性质2设Mc=r]nxn是决策表S= 定义4131在决策表S=(U,C,D,V,f)中，设 (U,C,D,Vf)的矩阵，M6=r9nxn是简化决

第2期 钱文彬等：一种快速的动态属性约简矩阵算法 251· 策表S=(U,C,D,V,f)的矩阵，则Mc=rglnxn 3动态属性约简算法 和M6=r号lnxn中具有的0”元素相同. 证明：对于x∈U,∈U,若x∈U',x)∈ 根据性质2可知，由矩阵Mc和简化矩阵M% U'且r=0,则存在x∈[xc,x')∈clc且 具有相同的“0”元素，根据定理1可知基于简化 r=0.若xc/D=1且izlc/D=1时，则 矩阵的属性约简等价于基于矩阵的属性约简.且简 ∈Uos∈U6s,由定义6可知，存在ck∈C,使 化矩阵去除重复元素，有效地缩小了算法的搜索空 得f(,ck)≠f(x,ck)f(,D)≠f(,D),再由定 间，并且根据性质3，将决策表中对象的变化情况 义7可知r=r;若Ilc/D=1和xc/D=1 映射到简化矩阵中元素的动态变化，仅需扫描一遍 不同时满足时，则说明对于x,x∈'，至少有一个 简化矩阵中的元素便可求解属性约简，为此可设置 存在Uheg中，从而由定义7可知r=r,对于 标志位count记录矩阵中0”元素的个数，当count ∈U',)∈U',若x∈U,∈U且T=0,则存 越大时其对应的属性就越重要，在有效利用原属性 在ec,∈rc且r%=0,若EUpos∈ 约简的基础上，本文给出一种快速的动态属性约简 Uos时，由定义7可知，f(x,ck)卡f(x,c),再由定 矩阵算法， 义4可知r=:若，至少有一个存在Ucg 算法：快速的动态属性约简矩阵算法 中时，即假如设∈Ueg'若f(x,ck)≠f(c,ck 输入：简化决策表S=(U”,C,D,V,f),原属 则由定义4可知r)=r;如果存在f(x,ck)= 性约简Red(C),新增对象zo,Vck∈C,矩阵Me! f(xj,ck小，由于x∈Uheg且∈【rc,故一定有 中“0”元素个数count,矩阵M6中“0”元素个数 x,∈[xc使得f(x,ck)卡f(x,c),从而使得 count. f(x,c)卡f(,ck小，则由定义4可知r对=r. 输出：更新后的属性约简Red(C) 综上所述，命题成立，证毕 Step1 if((3xj∈Uheg A YCk∈CAf(xo,ck)= 定理1设R为决策表S=(U,C,D,V,f) f(xj,Ck)》 的矩阵的属性约简，设R为简化决策表S= 则Red(C)保持不变； (U,C,D,V,f)的简化矩阵的属性约简，则R和R Step2if(3zj∈Upos A VCk∈CAf(xo,ck)= 中所求结果是一致的，即有R=R成立 f(xj,ck)A f(xo,D)=f(xj,D)) 证明：在决策表S=(U,C,D,V,)的矩阵 则Red(C)保持不变； Mc中，若存在ck∈R,根据定义5可知，则存在 Step3if(3xj∈Upos A VCk∈CAf(zo,ck)= 一个r∈Mc,使得r=0,满足MR=Mc且 f(xj,ck)A f(xo,D)f(zj,D)) MR-{c}卡Mc,根据性质2可知，在简化决策表 Step3.1 if(Vzi EUpos A f(i,D)=f(rj,D)) S=(U,C,D,V,f)的简化矩阵M化中，存在一个 则根据定义7，更新对象x与x所对应的矩 对应的r∈M6,必有T=r)成立，故可知 阵元素r;并更新M化.count; rY=0,使得M=M6且MR-e}≠M6,根 if(3ck∈C-Red(C)Af(r,ck)≠f(c,ck) 据定义8可知ck∈R',则可证R二R.在决策表 S=(U,C,D,V,f)的矩阵M6中，若存在ck∈R, 则更新对象x:与x)在ck上所对应的矩阵 根据定义8可知，则存在一个r'∈M化，使得 Me}:并更新count的值： rry=0,满足M=M6且M?-fes}≠Mc,根 选择属性满足G一4 Me)count))(偌 据性质2可知，在简化决策表S=(U',C,D,V,f) 存在多个，则任选其一)： 的简化矩阵M化中，存在一个对应的r)∈Mc,必 Red(C)=Red(C)U{ci}; 有T=r成立，故可知r=0,使得Mr=Mc 根据定义8，对Red(C)中可能存在的冗余属 且MR-ck}卡Mc,根据定义5可知ck∈R,由此 性反向剔除： 可证RCR综上所述，命题成立，证毕 A 性质3在简化决策表S=(U,C,D,V,f), else 对VceC,设条件属性ck对应的矩阵为M{e}= Red(C)保持不变； rnxm,则Me}=r号nxn中0”元素个数 Step3.2iVar:∈Uheg) 越多，区分能力越大 删除对象)在矩阵S,中所对应的行，并更 证明：由定义7和性质2可知命题成立，证毕 新M6.count;

.252 北京科技大学学报 第35卷 对ck∈C,删除对象：与西在矩阵Mc} 表1决策表 中所对应的行，并更新Me}.count的值： Table 1 Decision table itf3cs∈RedC)AMe}.count=Me.count） 数据集，U 条件属性 决策属性.) Red(C)=x: b c d 22 1 2 0 else 22 2 2 1 2 0 Red(C)保持不变： x3 21 1 Step3.3 Upos=Upos) 2 1 2 2 0 Uneg=UhegU 5 1 2 1 26 2 2 2 1 0 Step4 i,∈U6osA3ck∈f(o,ck)≠ 7 0 f(xj,ck)) r8 1 2 1 则对于∈U,增加对象x0与x;所对应的 r9 2 矩阵元素r6,以及在ck上所对应的矩阵M{}i更 E10 2 0 新M.count和对应的Mc}count: 首先根据定义6可得简化决策表S”= ir(3ck∈C-Red(C)Af(xo,ck)≠f(a,ck) (U,C,D,V,f),则U'={1,r3.rx.其 中Uos={r1,3,46.小.Ucg={.然后，根 选择属性满足G=2nM.cou()若存 据定义7可得简化矩阵M6如下： 在多个，则任选其一)： 101100 Red(C)=Red(C)U{ci}; 010010 根据定义8，对Red(C)中可能存在的冗余属 M&= 1011 00 性反向剔除： 101100 } else L010010 Red(C)保持不变； 同样根据定义7可知，对于rk∈C,决策表中 Upos Upos U{o}: 每个属性所对应的简化矩阵M,如下： Step5输出属性约简Red(C),算法终止. 101100 算法复杂度分析：当新对象0加入决策表 010011 时，算法Stepl的最坏时间复杂度为O(CU): Mid)= 101 1 00 算法Step2的最坏时间复杂度为O(ICUpos):算 1 0 00 法Step3.1的最坏时间复杂度为O(ICUs)+ 0 O(Cl川Ug:算法Step3.2的最坏时间复杂 度为O(IClUpos)+O(IRed(C)2U6sU'I):算 法Step4的最坏时间复杂度为O(ICIU'I)+ O(RCd(C)IUoU):因此，算法的时间复杂度为 max{O(Red(C)21UslU').O(ICU'I}.易知，算 法的空间复杂度为O(CII心U').在文献[13]中 算法的时间复杂度和空间复杂度分别为O(CU3) 和O(C2U2),在文献14④中算法的时间复杂度和 空间复杂度均为O(1C2U1),因此算法的计算效率 优于文献[13-14的算法.且新算法剔除了决策表中 Mic)= 的重复对象，有效地降低了算法的复杂度. 0 4算例分析及实验比较 4.1算例分析 0 下面以表1中的决策表S=(U,C,D,V,f)为 Mid)= 10 0 例进行说明分析，其中为a.b,c,d条件属性，D为 11 决策属性，共有10个对象

第2期 钱文彬等：一种快速的动态属性约简矩阵算法 253. 根据定义8、定理1和性质3可得原决策表 01=T10=0,T03=T30=1; 的属性约简为Red(C)={a,c},并可知简化矩阵 T04=T40=0,T06=T60=0: M(、M{aMbM{e和Ma的count值分别 T09=T90=1,T08=0. 为17、15、9、11和9.下面通过增加不同的新对象 0分析属性约简的动态变化情况. T01=r10=1,T03=T30=1: (1)当决策表中增加的对象x0为[1,1,2,1,0 r04=T40=1.706=T60=1; 时，对于ck∈C,存在x8∈Uheg'使得 09=r90=1,T08=0. f(xo,ck)=(x8,ck),根据算法的Stepl可知，属 性约简Red(C)={a,c}保持不变. T01=T10=1,T03=T30=1: (2)当决策表中增加的对象x0为[1,1,1,2,1时， T04=T40=0,T06=T60=1: 对于k∈C,存在xg∈Upos'使得f(a0,ck)= T09=r90=1,T08=0. f(rg,cx)Af(xo,D)=f(ag,D),根据算法的Step2 T01=T10=1,T03=T30=1: 可知，属性约简Red(C)={a,c}保持不变 T04=T40=0,T06=T60=0: (3)当决策表中增加的对象xo为2,1,2,2,1时， T09=Tg0=1,T08=0. 对于ck∈C,存在x4∈Ups'使得f(xn,ck)= f(x4,ck)Af(xo,D)卡f(x4,D),根据算法的Step3 T01=T10=0,T03=T30=1; 可知，在矩阵M化中需更新的矩阵元素为 T04=T40=0,T06=T60=1: T09=T90=1,T08=0. T14=T41=0, T64=T46=0. 由于此时3d∈C-Red(C)∧f(xo,d≠f(xr,d), 属性约简更新为Red(C)={a,c,d},并根据定义8， 同理可知，在矩阵Mia)Mio)Mic)和M{a中 对Rd(C)中可能存在的冗余属性进行反向剔除， 矩阵元素分别更新为 未发现冗余属性，因此属性约简Red(C)={a,c,d}. 4.2实验比较 r14=T41=1, r14=T41=0, 为了进一步验证本文提出的算法与同类算法 T64=r46=1; T64=T46=0: 的性能，本文选用决策表1和UCI机器学习数据库 中的四个数据集.由于在一般情况下，数据集中的 T14=T41=0 T14=T41=1, 实例数远大于属性数，即C1《U,因此文献[14 T64=T46=1; T64=T46=0. 中的算法效率要好于文献[13)中的算法效率.为了 根据算法Step3.1可知，此时存在b∈C- 便于实验的性能比较，仅与文献[14中的属性约 Red(C)Af(zo,b)≠f(Eb),将属性作为候选属 简算法进行了实验比较，并将文献[14中的算法简 性放入Red(C):并根据定义8，对Red(C)中可 记为S_ARMA,将本文的算法简记为D ARMA.上 能存在的冗余属性进行反向剔除，并得出此时属 述算法采用C++编程实现，开发环境为Microsoft 性c是冗余的，为此属性约简更新为Red(C)= Visual Studio2005,在Windows XP下执行，硬件 {a,b}.删除矩阵M%中对象x4所对应的行矩 配置CPU Pentium3.0GHz,内存1GB.实验数 阵，同理可知在矩阵M{a)Mio)Mie)和Md 据集情况如表2所示.基准实例数是指从五个数据 中也需删除对象x4所对应的行矩阵，此时可得 集中随机抽取的实例数，将它们生成的矩阵和简化 M6、Mia)Mio)Mie)和Mad的count值分 矩阵分别作为算法S_ARMA和D_ARMA的输入， 别为17、12、11、12和10，根据算法Step3.2可 算法的性能比较如表3所示，其中T表示算法的 知，属性约简Red(C)保持不变，因此属性约简运行时间（单位：s),Red(C)表示算法得到的约简 Red(C)={a,b}. 结果 (4)当决策表中增加的对象x0为[2,2,1,1,1 从表3中可知，由于两个算法的输入矩阵都 时，对，∈Us,至少3ck∈C,使得 是基于正区域模型的构造，为此在这些数据集上两 f(zo,ck)≠f(z,ck),根据算法的Step4可知，在矩 个算法所求得的约简结果是一致的.同时从表中看 阵M%、Mia)Mio Mie)和Ma中分别需增加 出：对于规模较小的数据集，两个算法的性能差距 的矩阵元素如下： 并不明显：但对于维数较高、规模较大的数据集，本