作者简介:罗来鹏(1973—),华东交通大学副教授.研究方向:粗糙集与粒计算.E-mail:luolp789@163.com
中文责编:英 子; 英文责编:木 柯
School of Sciences, East China Jiaotong University, Nanchang 330013, Jiangxi Province, P.R.China
artificial intelligence; rough set; granular computing; attribute reduction; optimal approximation set; incremental updating; similarity degree
DOI: 10.3724/SP.J.1249.2021.03324
粗糙集理论[1-2]是建立在集合论基础上,用来分析和处理不精确、不协调、不完备信息的数学理论,是当前3大粒计算模型之一,已被成功应用于人工智能与机器学习等领域.目标概念在近似空间上的近似表示与计算,是粗糙集理论研究与应用的基础.当目标概念无法用近似空间上基本知识粒完全定义时,一直以来都是借用拓扑中的内核和闭包概念,采用其上近似集和下近似集作为近似边界来刻画,因此,目标概念在近似空间上往往存在边界域的不确定性,进而造成系统及规则知识的不确定性.为深入挖掘及有效利用边界域信息,ZIARKO[3- 4]提出变精度近似并建立变精度粗糙集模型和概率粗糙集模型,所得约简规则提高了容错性,且能将小样本数据得到的结论用到大数据中.但是,这两个模型在实际应用中存在如何优化参数阈值的问题,参数值直接影响近似集计算和属性约简结果[5].同时,这种近似的思路仍然是从基本知识粒即等价类角度来定义目标概念的近似,并未从系统角度来看待目标概念的近似,且当目标概念是粗糙时,其近似表示仍是用它的下(上)近似集,而非一个具体的可定义的集合.为此,张清华等[6-7]以相似度为度量标准提出目标概念的最优近似,即在近似空间上所有可定义的集合中找一个与目标概念相似度最高的集合作为目标概念的近似.基于此,LUO等[8]给出了粗糙集最优近似的代数定义、计算和基于最优近似的分布约简,讨论了在相同近似空间下目标概念的最优近似与其上(下)近似之间,以及基于最优近似的分布约简与基于上(下)近似分布约简之间的关系,发现基于最优近似所建立的分布约简更能反映数据本身特性,也更能体现粗糙集应用中不需要先验知识的优势.
然而,实际应用中数据库中的数据往往是动态变化的,因此,粗糙集的动态知识发现是目前粗糙集研究的重点.当前研究主要集中在论域变化、属性集变化和属性值域变化等方面.YU等[9]针对属性集变化的区间值信息系统设计了两种动态近似计算算法; LI等[10]针对基于优势关系的动态信息系统讨论了基于对象集的变化时近似集的增量式更新方法. CHENG等[11]在模糊粗糙集中,提出了两种概念近似增量更新的动态方法.HU等[12]在多粒度粗糙集中,针对单个粒结构随时间演化,提出基于矩阵的动态近似更新方法.JING等[13]通过引入知识粒度增量机制,讨论了多个对象发生变化时,更新约简的两种增量方法. ZHANG等[14]研究了基于知识粒度的增量属性约简方法.WEI等[15]通过压缩决策表,讨论了对象集变化时动态数据的属性约简.GE等[16]讨论了基于冲突区域的增量机制,提出在新增对象情况下属性约简的更新计算方法.HU等[17-18]就多种模型,如优势关系粗糙集模型、集值粗糙集模型以及不完备系统等,讨论了近似更新等.
但是,当前关于粗糙集动态知识获取的研究更多地局限在基于不同模型目标概念的上、下近似,随着粗糙集最优近似集的提出,基于粗糙集的最优近似动态更新计算成为新的研究方向,但目前尚未见文献报道.为此,本研究针对对象集增加的情况,探讨了决策系统中各决策类的最优近似的动态变化规律,为建立基于最优近似的动态分布约简提供参考.
定义1[1-2] 设U是有限论域, R是U上的等价关系,由此导出近似空间为(U, R), 等价关系R决定论域U上的一种划分称为近似空间(U, R)上的基本知识基,表示为U/R={X1,X2,…,Xm}.其中,, 特别地,若x∈Xi(i=1,2,…,m), 则可用[x]R表示Xi, 即[x]R=Xi.
定义2[1-2] 设(U, R)为近似空间, 且U/R={X1, X2, …, Xm}, 对于的目标概念, 则分别称为X在近似空间(U, R)上的下近似集和上近似集, BNR(X)={xk|xk∈R^-(X)-R(X)}和NEGR(X)=分别称为X在近似空间(U, R)上的边界域和负域.
定义3[1-2] 设(U,R)为近似空间, 若, 则称X在近似空间(U, R)上是可被定义的精确集; 否则,为粗糙集,并用表示.
定义4 设(U, R)为近似空间, U/R={X1, X2, …, Xm}, XU, 则称BNR'(X)=为X的边界类. 其中, |·|为集合基数(下文相同).
定义5 设(U, R)为近似空间, XU, 在(U, R)上,若存在可定义的精确集Xopt, 使得对于任意可定义的精确集Y, 有S(X, Xopt)≥S(X, Y), 则称Xopt为X在近似空间(U, R)上的最优近似集. 其中, S为U上的集合相似度.对于X,YU, 取S(X,Y)=.
定义6 设(U, R)为近似空间, U/R={X1, X2, …, Xm}, 的边界域类BNR'(X)={X(1), X(2), …, X(k)}, 令(|X(j)∩X|)/(|X(j)-X|)=λj(j≤k), 则称(λ1, λ2, …, λk)为X在(U, R)上关于BNR'(X)的分布向量, λj(j≤k)为对应边界类的分布值.
定理1[8] 设(U, R)为近似空间, , BNR'(X)={X(1), X(2), …, X(k)}. 令, , 则X在近似空间(U, R)上的最优近似集为Xopt=.
由定理1可知,计算目标概念的最优近似集的关键是需要获取两个参数值,即目标概念中正域所占的比值和目标概念在其边界类上的分布向量.
更新计算一直都是信息处理研究的重点和难点.在粗糙集动态知识更新内容中,对象增加是普遍情况.考虑到增加多个对象的更新操作可看成是对增加单个对象更新的递推,并且对象删除处理方法具有一定的类似性,接下来将讨论单个对象增加的情况下,决策系统中决策类的最优近似更新原理,并设计相应的算法.
设决策系统S=(U, C∪d, V, f), 条件属性集C在论域U上导出的划分为U/C={X1, X2, …, Xm}, 决策属性集d在U上导出的划分为U/d={Y1, Y2, …, Yn}, V为属性值域,并用VC表示属性集C的值域, f为信息函数.并令(j≤n), Yj关于(U, C)在其BNC'(Yj)上的分布向量 Dj=(λ(1)j, λ(2)j, …, λ(qj)j)(j≤n), gYj(λi)=(j≤n). 为描述方便,当新增对象x后,决策系统S改记为S'=(U',C∪d,V', f), 相应的Xi改记为Xi'(i≤m), Yj改记为Yj'(j≤n), λj改记为λj', Dj改记为 Dj'=(λj'(1), λj'(2), …, λj'(qj) )(j≤n), V改记为V', 并用λ(x)j表示Yj'在新增对象x加入的条件类后所对应的分布值,新增条件类表示为xC, 新增决策类表示为xd. 此时,显然有U'=U∪x,V'=V或VV'.
接下来针对对象集新增一个对象并引起值域发生不同变化的情况,讨论决策类最优近似更新.
定理2 若Vd'=Vd, VC'≠VC, 且存在Yj∈U/d, 使得Yj'=Yj∪x, 则对于任意Yk'(k≠j), 有.
【证】因为Vd'=Vd, VC'≠VC, 所以f(x, d)∈Vd, f(x, C)?VC, 又因为Yj'=Yj∪x,所以U'/C={X1', X2', …, Xm', xC}, U'/d={Y1',Y2',…,Yj',…,Yn'}. 其中, Xi'=Xi(i≤m), Yk'=Yk(k≠j, k≤n). 此时,任意Yk'(k≠j)与Yk具有相同边界分布且正域不变,所以(Yk')opt=Ykopt. 而对于Yj'=Yj∪x, 由于, 所以λj'=.又因对于任意i(i≤m),有(|Xi'∩Yj'|)/(|Xi'-Yj'|)=(|Xi∩Yj|)/(|Xi-Yj|), 即Yj和Yj'关于(U, C)在其边界类上的分布值相同,所以(Yj')opt=(Yj∪x)opt=.
定理3 若Vd'=Vd, VC'=VC, 且存在Yj∈U/d, 使得Yj'=Yj∪x, 存在Xi∈U/C, Xi'=Xi∪x, 则对于任意Yk'(k≠j), 有:
1)若Yk∩Xi=, 则(Yk')opt=Ykopt;
2)若;
3)若Xi∈BNC'(Yk), 则当(|Xi∩Yk|)/(|Xi-Yk|+1)≥λk'时,(Yk')opt=Ykopt∪x; 当λk'≥(|Xi∩Yk|)/(|Xi-Yk|)时,(Yk')opt=Ykopt; 当(|Xi∩Yk|)/(|Xi-Yk|)≥λk'>(|Xi∩Yk|)/(|Xi-Yk|+1)时,(Yk')opt=Ykopt-Xi. 其中, λk'=(|C(Yk)|)/(|Yk|).
【证】由于Vd'=Vd, VC'=VC, 且Yj'=Yj∪x, Xi'=Xi∪x, 即U'/C={X1', X2', …, Xi∪x, …, Xm'}, U'/d={Y1', Y2', …, Yj∪x, …, Yn'}. 其中, Xp'=Xp(p≠i, p≤m), Yt'=Yt(t≠j, t≤n). 因此,有:
1)对于任意k≠j, 若Yk∩Xi=, 则Yk'∩Xi'=, 所以Yk'(k≠j)与Yk具有相同边界分布且正域不变,所以(Yk')opt=Ykopt.
2)若(k≠j, k≤n), 因为, 所以, 且类Xi'=Xi∪{x}变成BNC'(Yk')中的新元素.此时, , 而新增的边界类Xi∪{x}的分布值λ(x)k=(|(Xi∪{x})∩Yk'|)/(|(Xi∪{x})-Yk'|)=(|Xi∩Yk|)/(|{x}|)=|Xi∩Yk|=|Xi|≥1≥λk', 因此,Yk'的最优近似集(Yk')opt=.
3)若Xi∈BNC'(Yk), 则Yk和Yk'的正域不变,即. 此时,Yk和Yk'在边界域分布中唯有Xi所对应的Xi'分布值发生改变,且值为
因此,若λ(x)k≥λk', Xi增加x后归属的最优近似保持不变,其他分布也未改变,则有(Yk')opt=Ykopt∪{x}. 类似地,当λk'>(|Xi∩Yk|)/(|Xi-Yk|),(Yk')opt=Ykopt; 当(|Xi∩Yk|)/(|Xi-Yk|)≥λk'>(|Xi∩Yk|)/(|Xi-Yk|+1)时,(Yk')opt=(Yk)opt-Xi.
定理4 若Vd'=Vd, VC'=VC, 且存在Yj∈U/d使得Yj'=Yj∪x, 存在Xi∈U/C使得Xi'=Xi∪x, 则
1)若.
2)若, 则当1/(|Xi|)≥λj'时,(Yj')opt=; 当1/(|Xi|)<λj'时,.其中, λj'=.
3)若Xi∈BNC'(Yj), 则当λ(x)j≥λj'时,(Yj')opt=; 当λ(x)j<λj'时,. 其中, λj'=
【证】
1)因为, 且Xi'=Xi∪x, Yj'=Yj∪x, 所以. 又因Yj与Yj'的边界类及分布值不变,所以
2)若, 则Xi'∈BNC(Yj'), Yj'比Yj仅新增一个边界类Xi', 并且, 而λ(x)j=(|{x}|)/(|Xi|)=1/(|Xi|), Yj与Yj'的其他的边界类和它们对应的分布值不变,所以当1/(|Xi|)≥λj'时,; 当1/(|Xi|)<λj'时,.
3)若Xi∈BNC'(Yj), 则, λj'=, Yj'在其所有边界类中唯有在Xi'上的分布值发生改变, λ(x)j=(|Xi'∩Yj'|)/(|Xi'-Yj'|)=(|Xi∩Yj|+1)/(|Xi-Yj|). 所以,若λ(x)j≥λj', 则; 若λ(x)j<λj', 则.
定理5 若Vd'≠Vd, VC'≠VC, 则(Yj')opt=Yjopt(j≤n), xoptd=xC.
【证】若Vd'≠Vd且VC'≠VC, 则U'/C={X1', X2', …, Xm', xC}, U'/d={Y1', Y2', …, Yn', xd}, 且Xi'=Xi(i≤m), Yj'=Yj(j≤n). 此时显然有(Yj')opt=Yoptj(j≤n), xoptd=xC.
定理6 若Vd'≠Vd, VC'=VC, 且存在Xi∈U/C使得Xi'=Xi∪x, 对于任意Yj'(j≤n), 则有:
1)xoptd=Xi'=Xi∪x.
2)若
3)若Xi∈BNC'(Yj), 则当λ(x)j≥λj时,(Yj')opt=Yjopt∪{x}; 当λ(x)j<λj时,(Yj')opt=Yjopt-Xi. 其中, λ(x)j=(|Xi∩Yj|)/(|Xi-Yj|+1).
4)若, 则(Yj')opt=Yjopt.
【证】若Vd'≠Vd, VC'=VC, 且存在Xi∈U/C使得Xi'=Xi∪x, 此时有U/C={X1', X2', …, Xi∪x, …, Xm'}, U'/d={Y1', Y2', …, Yn', xd}, 且Xp'=Xp(p≠i, p≤m), Yj'=Yj(j≤n),则
1)xoptd=Xi'=Xi∪x显然成立;
2)若, 则类Xi'=Xi∪{x}变成BNC'(Yj')中的新元素,此时λj'=
3)若Xi∈BNC'(Yj), 则, Yj在边界类的分布中唯有Xi所对应的值发生了改变, λ(x)j=(|(Xi∪{x})∩Yj'|)/(|(Xi∪{x})-Yj'|)=(|Xi∩Yj|)/(|Xi-Yj|+1). 因此,若λ(x)j≥λj', 则(Yj')opt=Yjopt∪{x}; 若λ(x)j<λj', 则(Yj')opt=Yjopt-Xi.
4)若, 此时显然(Yj')opt=Yjopt.
综上可见,新增一个对象后,决策系统中决策类最优近似更新的计算,只需分析变化的条件类对决策类正域、边界域和负域的改变情况.显然,与非增量计算相比,增量更新计算可极大地简化求解过程; 同时,因新增对象所引起的属性值域的变化不尽相同,决策类更新的时间复杂度也未必一样.
设决策系统S=(U, C∪d, V, f), 条件属性集C在论域U上导出的划分为U/C={X1, X2, …, Xm}, 决策属性集d在U上导出的划分为U/d={Y1, Y2, …, Yn},并令, 则当新增对象x后, Xi(i≤m)变为Xi',Yj(j≤n)变为Yj', λj变为λj'. 最优近似集更新算法步骤为:
步骤1 获取相关变量的初始值.计算、 BNC'(Yj)、 gYj(λi)和Yjopt(j≤n).
步骤2 对新增数据类别进行判定,并计算决策类最优近似的更新结果.
1)若Vd'≠Vd且VC'≠VC,即令Xk'=Xk(k≤m), Yk'=Yk(k≤n), 则(Yj')opt=Yjopt(j≤n), xoptd=xC.
2)若Vd'≠Vd VC'=VC, 即令Xi'=Xi∪x, Xk'=Xk(k≠i), Yk'=Yk(k≤n), 则对于Yj'(j≤n), 有:③ 若Xi∈BNC'(Yj), 则当λj'(x)≥λj时, 有(Yj')opt=Yoptj∪{x}; 当λj'(x)<λj时, 有(Yj')opt=Yjopt-Xi. 其中, λj'(x)=(|Xi∩Yj|)/(|Xi-Yj|+1), λj=, 则(Yj')opt=Yoptj.
3)若Vd'=Vd且VC'≠VC, 即令Xk'=Xk(k≤m), Yk'=Yk(k≠j), Yj'=Yj∪x, 则(Yk')opt=.
4)若Vd'=Vd且VC'=VC, 即令Yj'=Yj∪x, Xi'=Xi∪x, Xk'=Xk(k≠i), Yk'=Yk(k≠j), 对于任意Yk', 有:.当1/(|Xi|)≥λj'时,{x}; 当1/(|Xi|)<λj'时, 其中,,则(Yk')opt=. 其中, λk'=. 其中, ③ 若Xi∈BNC'(Yk), 则当(|Xi∩Yk|)/(|Xi-Yk|+1)≥λk'时,(Yk')opt=Ykopt∪x(k≠j); 当λk'>(|Xi∩Yk|)/(|Xi-Yk|)时,(Yk')opt=Ykopt(k≠j); 当(|Xi∩Yk|)/(|Xi-Yk|)≥λk'>(|Xi∩Yk|)/(|Xi-Yk|+1)时,(Yk')opt=Ykopt-Xi(k≠j), 其中, ; 当λ(x)j≥λj'时,时,. 其中, λj'=
从UCI公用数据集(http://archive.ics.uci.edu/ml/index.php)选择数据集Zoo、Hayes-roth、Lymphography、Monk's problems和Balance-scale,采用SQL server 2008中的SQL进行编程,测试不同条件下最优近似更新计算的运行时间.实验测试所用的计算机配置为:内存为8 Gbyte, CPU为Intel Core(TM)i7-8550U,1.80 GHz,操作系统为Windows 10.表1为5个数据集的参数描述.
图1为在5个数据集上新增不同类别的单个对象时,最优近似更新计算的运行时间对比.其中,每种情况下的运行时间取相同类别数据5次运行时间的平均值.由图1可见,满足条件Vd'≠Vd且VC'≠VC的增量数据运行时间最短,满足条件Vd'=Vd且VC'=VC的增量数据运行时间最长,原因是在Vd'≠Vd且VC'≠VC条件下进行增量数据更新时,决策类最优近似不变,新增决策类的最优近似为新增条件类,整个过程中不需要新增计算; 而满足条件Vd'=Vd且VC'=VC的增量数据,仅当决策类与新产生的条件类相交为空集时才不用计算,最优近似保持不变,而相交为非空集时,需根据不同情况进行不同的计算,新产生的决策类也有类似过程,因此,总体来说所需时间最长.新增其他两类数据的过程有些类似,但是在讨论决策类分布变化时都会比满足Vd'=Vd且VC'=VC时的运行时间要少,所以运行时间也是在上述两类之间.
图2为新增单个对象,并在不同数据集上进行增量更新与非增量更新时,求解最优近似算法的运行时间结果.运行时间取5次随机新增一个对象时的运行时间的平均值.由图2可见,利用增量更新与非增量更新方法,在不同数据集上计算最优近似的耗时并不一样,增量更新方法所需时间较少,优势明显.当数据集决策类增加且数据集中的对象数较多时,增量更新方法的耗时也会增长,但并不明显,而非增量算法的耗时却呈快速增长.可见,增量更新算法的时间效率要优于非增量更新,究其原因主要是在动态环境下,当对象增加时,采用非增量更新方法计算最优近似集需要比较每个决策类与每个条件类,造成较多重复计算,而对于增量更新方法,只需关注变化的条件类对决策类正域以及边界类分布值的影响,减少了比较次数,提高了效率.尤其是当数据集较大时,增量更新方法具有较好的时间性能,其计算最优近似集的时间效率明显优于非增量方法计算.
针对决策系统动态变化情况下,决策类的最优近似更新问题,本研究就单个对象增加引起值域发生改变的4种不同情况,讨论了决策类的最优近似的变化机制,并给出4种不同变化情形下的最优近似更新求解方法.仿真实验结果表明,所提增量式更新算法能够快速地对最优近似结果进行快速更新,具有很高的计算性能.
深圳大学学报理工版
JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING
(1984年创刊 双月刊)
主 管 深圳大学
主 办 深圳大学
编辑出版 深圳大学学报理工版编辑部
主 编 李清泉
国内发行 深圳市邮电局
国外发行 中国国际图书贸易集团有限公司(北京399信箱)
地 址 北京东黄城根北街16号
邮 编 100717
电 话 0755-26732266
0755-26538306
Email journal@szu.edu.cn
标准刊号 ISSN 1000-2618
CN 44-1401/N