邻域多粒度粗糙集知识更新增量算法

徐 怡,孙伟康,王 泉

1(安徽大学 计算智能与信号处理教育部重点实验室,合肥 230039)

2(安徽大学 计算机科学与技术学院,合肥 230601)

E-mail:xuyi1023@126.com

1 引 言

粗糙集理论[1,2]作为处理不确定性和不完备数据的一种数学工具,最初由Pawlak Z在1982年提出.粗糙集作为一种新的软计算方法,在知识发现、数据挖掘、机器学习等领域得到了广泛的应用[3-7].经典的粗糙集模型是基于等价关系构成划分的,以上下近似的形式来刻画不确定性.从粒计算的观点来看，在现有的粗糙集模型中，一个集合所描述的一般概念总是通过单粒度下的上、下近似来表征，即，该概念是由对论域的单一关系(如等价关系、容差关系和反身关系)来描述的.在许多情况下，我们常常需要根据用户的需求或问题解决的目标，通过多种二元关系来同时描述一个目标概念.因此，Qian等人[8]引入了多粒度粗糙集理论(MGRS)，将粗糙集理论更广泛地应用于实际应用中.自多粒度粗糙集的概念被提出之后,粗糙集领域研究中一个重要论题便是MGRS,很多基于多粒度粗糙集的拓展模型被提出.例如 Yang等[9]采用容差关系、相似关系和限制容差关系分别构建了乐观/悲观多粒度粗糙集,将多粒度粗糙集方法引入到不完备信息系统中.Liu等[10]将多粒度粗糙集与覆盖近似空间相结合,提出基于覆盖近似空间的四种多粒度粗糙集模型(MGCRS).Feng等[11]结合可变精度粗糙集和三支决策理论模型,提出可变精度多粒度决策理论模糊粗糙集.

在实际应用中,由于数据的不断变化,信息系统也在不断地改变.如何在动态变化的信息系统中获取有用的知识已越来越受到关注.目前,有以下三个方面是信息系统动态变化的来源：对象的变化、属性的变化和属性值的变化.例如,医院中有数据表会记录住院病人是否有感染流感,该数据表中会记录住院人数、病人的体温、是否发烧以及是否咳嗽等,并且确认是否患有流感.跟随时间的推移,又会有新的患者住院,此时,原信息系统的对象就发生了变化；如果因为某些原因患者需要检查新的身体指标,这即是属性发生了变化；像体温这样的指标还会波动,这即是属性值发生了变化.目前,在动态信息系统的增量知识获取方面已经取得了许多重要的研究成果：

1)属性的变化.例如Liu等[12]针对属性变化情况下的动态更新问题,基于概率粗糙集模型提出了两种增量更新算法.Li等[13]将优势矩阵引入优势粗糙集模型中并给出更新优势粗糙集上下近似的增量算法.2)属性值的变化.例如Zeng等[14]在混合信息系统中给出两种增量算法用于更新模糊粗糙集近似集.Wang等[15]基于信息熵提出属性值动态变化下的属性约简算法.当属性值变化时,Li等[16]提出一种维护优势粗糙集近似集的增量方法.3)对象的变化.例如Luo等[17]引入矩阵方法,用以处理对象动态变化下更新上下近似问题.Shu等[18]在动态不完备系统中提出一种增量算法用于属性约简.Hu等[19]基于对象的变化提出一种增量式算法用于在双重论域中更新近似集.在多粒度环境中,Yang等[20]根据乐观和悲观多粒度定义,提出了一种快速算法用于粒结构变化情况下动态更新近似集问题.Hu等[21]在Yang的基础上引入了矩阵方法,用以处理在粒结构动态变化情况下更新多粒度粗糙集近似的问题.同时,Hu等[22]提出了基于属性值细化或粗化的动态更新多粒度粗糙集近似机制以及相应的算法.在本文中,我们关注的是第三种情况,即在对象集变化下的知识更新.

为了解决多粒度粗糙集不能处理连续数值型数据的问题,Lin等人[23]将多粒度粗糙集模型扩展到邻域多粒度粗糙集(NMGRS),定义了两类邻域多粒度粗糙集,分别称为1型多粒度粗糙集和2型多粒度粗糙集,在这两类邻域多粒度粗糙集的基础上,分别在乐观和悲观条件下给出上近似和下近似的定义.在实际应用中,随着时间的推移,论域也会产生变化,从而导致在一定粒度下近似集划分产生变化,当非增量算法更新集合的上下近似时,需要再次对整个论域进行遍历,但是当有较大数据量时,非增量算法就会消耗大量的时间.因此,在邻域多粒度粗糙集模型的基础上,本文针对该信息系统中论域发生变化的情况,提出了用矩阵增量的方法进行知识更新.本文首先给出了矩阵增量更新相关的定理.然后,在给定的更新策略的基础上,提出了一种增量算法来更新邻域多粒度粗糙集的正域、负域和边界域.最后,通过对比实验验证了本文算法的有效性.

2 基本概念

下面介绍本文主要涉及到的相关概念[23-25].

2.1 邻域粗糙集

信息系统S=(U,AT,V,f)为一个四元组,U={xi|i∈{1,2,…,n}}为有限对象集合,AT为有限属性集合,V为属性的值域,V=∪a∈ATVa,f为属性到属性值域上的映射,即f(x,a)∈Va,∀a∈AT,x∈U.

对于∀A⊆AT,IND(A)={(xi,xj)∈U×U|∀a∈A,f(xi,a)=f(xj,a)}表示为一个等价关系.xi关于IND(A)的等价类记为[xi]A.对于信息系统S=(U,AT,V,f),若属性集AT构成邻域关系,那么,称该信息系统为邻域信息系统,记为NIS=(U,AT,V,f).

定义1[25].给定邻域信息系统NIS=(U,AT,V,f),U={xi|i∈{1,2,…,n}},对于∀A⊆AT,对象xi在属性集A下的邻域δA(xi)定义为：

δA(xi)={xj|xj∈U,ΔA(xi,xj)≤δ,j∈{1,2,…,n}}

(1)

其中ΔA(xi,xj)为属性集A的度量函数,本文采用欧氏距离作为度量函数,δ≥0为给定的阈值.

定义2[25].给定邻域信息系统NIS=(U,AT,V,f),U={xi|i∈{1,2,…,n}},X⊆U,δA(xi)为对象xi在属性集A下的邻域,对于∀A⊆AT,X的下近似集和上近似集分别定义为:

(2)

(3)

基于下近似集和上近似集的基本定义,论域可被分为三个域,分别为正域POSA(X),边界域BNDA(X)和负域NEGA(X),其中

2.2 邻域多粒度粗糙集

由于经典多粒度粗糙集(MGRS)无法处理连续数值型数据,Lin等[23]利用邻域关系代替等价关系,提出邻域多粒度粗糙集(NMGRS)模型.下面简单介绍邻域多粒度粗糙集中的一些基本概念.

定义3[23].给定邻域信息系统NIS=(U,AT,V,f),U={xi|i∈{1,2,…,n}},A1,A2,…,Am⊆AT为m个粒度.对于∀X⊆U,目标概念X的乐观邻域多粒度粗糙集下近似和上近似定义为:

(4)

(5)

其中δAm(xi)表示对象xi在粒度Am下的邻域,具体计算见定义1.

定义4[23].给定邻域信息系统NIS=(U,AT,V,f),U={xi|i∈{1,2,…,n}},A1,A2,…,Am⊆AT为m个粒度.对于∀X⊆U,X的悲观邻域多粒度粗糙集下近似和上近似分别定义如下:

(6)

(7)

其中δAm(xi)表示对象xi在粒度Am下的邻域,具体计算见定义1.

2.3 基于矩阵方法的邻域多粒度粗糙集

矩阵计算工具以其强大的计算能力在粒计算和粗糙集理论中得到了广泛的应用.在用矩阵描述粗糙集理论时,我们可以发现由于领域的动态变化,在知识更新过程中存在一些冗余计算.通过矩阵运算可以提高算法的执行效率,这也为我们研究增量更新算法提供了可靠的依据.

本小节主要介绍矩阵方法计算邻域多粒度粗糙集正域、负域、边界域的有关定义和定理.

定义5[24].给定邻域信息系统NIS=(U,AT,V,f),U={xi|i∈{1,2,…,n}},对于∀X⊆U,X的布尔列矩阵FU(X)=[f1,f2,…,fn]T定义如下:

(8)

其中“T”表示转置.

(9)

其中ΔAk(xi,xj)为粒度Ak的度量函数,δ≥0为给定的阈值.

(10)

GAk=MAk·FU(X)

(11)

其中“·”表示矩阵间的点乘运算.

HAk(X)=GAk/·ΛAk

(12)

其中 “/·” 表示矩阵元素之间的点除运算.

(13)

(14)

(15)

(16)

其中“∨”表示 “或” 运算,“∧”表示“与”运算.

证明:

3) 负域证明类似.

(17)

其中“∨”表示“或”运算，“∧”表示“与”运算.

证明:本条定理的证明与定理1的类似.

在上文定理的基础上，下面给出更新乐观和悲观邻域多粒度粗糙集的正域、边界域、负域的非增量算法.

算法1.更新邻域多粒度粗糙集的非增量算法

输入:(1)邻域信息系统NIS=(U,AT,V,f),论域U={xi|

i∈{1,2,…,n}},A1,A2,…,Am⊆AT.

(2)目标概念X,邻域阈值δ;

输出:正域、边界域、负域;

Step 1.for 1≤i≤ndo

ifxi∈Xthenfi=1;

elsefi=0;

Step 2.for 1≤i≤ndo

for 1≤j≤ndo

if ΔAk(xi,xj)≤δthen

mij=1;

elsemij=0;

end

end

Step 3.for 1≤i≤ndo

for 1≤j≤ndo

end

end

Step 4.计算GAk=MAk·FU(X);

Step 5.计算HAk(X)=GAk/·ΛAk;

算法1计算布尔列矩阵的时间复杂度为O(n);计算邻域关系矩阵,其时间复杂度为O(n2); 计算对角矩阵以及中介矩阵时,其时间复杂度为O(n2); 所以算法1的时间复杂度为O(n2).

3 基于矩阵运算增量更新近似集

3.1 对象增加时增量更新近似集算法

当信息系统发生动态变化时,静态算法的时间复杂度较高.为了提高算法的执行效率,降低算法的时间复杂度,在这一节中，我们将以上一节的内容为基础，以论域中对象的增加为前提，讨论如何用矩阵方法更新邻域多粒度粗糙集的正域、负域与边界域.

(18)

接下来,通过一个例子来说明目标概念列矩阵增量更新的过程.

表1 邻域信息系统

Table 1 Neighborhood information system

UA1A2A3x11.180.200.17x20.760.360.74x30.420.250.28x41.090.410.39x50.520.630.52x60.800.760.58

例1.给定邻域信息系统NIS=(U,AT,V,f),如表1所示.

U={x1,x2,x3,x4,x5,x6},AT={A1,A2,A3}构成NIS的粒度空间,设X={x1,x4,x5,x6},邻域阈值δ=0.15,新增对象x7∉X,具体如表2所示.

表2 增加对象后的邻域信息系统

Table 2 Neighborhood information system when object is added

UA1A2A3x11.180.200.17x20.760.360.74x30.420.250.28x41.090.410.39x50.520.630.52x60.800.760.58x71.100.190.36

(19)

证明:与定理3类似.

下面通过一个实例展示邻域关系矩阵的计算过程.

例2.(接例1)通过定义6,可得到粒度A1,A2和A3的邻域关系矩阵分别为:

以MA1为例,新增对象x7后,根据定理4有

当1≤i,j≤6时:

(m11)′=m11=1,(m12)′=m12=0,…,(m16)′=m16=0;

(m21)′=m21=0,(m22)′=m22=1,…,(m26)′=m26=1;

…

(m61)′=m61=0,(m62)′=m62=1,…,(m66)′=m66=1.

此外,ΔA1(x1,x7)≤0.15⟹(m17)′=(m71)′=1;

ΔA1(x2,x7)>0.15⟹(m27)′=(m72)′=0;

ΔA1(x3,x7)>0.15⟹(m37)′=(m73)′=0;

ΔA1(x4,x7)≤0.15⟹(m47)′=(m74)′=1;

ΔA1(x5,x7)>0.15⟹(m57)′=(m75)′=0;

ΔA1(x6,x7)>0.15⟹(m67)′=(m76)′=0;

ΔA1(x7,x7)≤0.15⟹(m77)′=1;

因此，更新后粒度A1的邻域关系矩阵为:

(20)

例3.(接例2)根据定义7可知粒度A1,A2和A3的对角矩阵分别为:ΛA1=diag[2,2,2,2,2,2],ΛA2=diag[2,3,3,2,2,2],ΛA3=diag[2,1,3,3,3,2].针以ΛA1为例,新增对象x7后,由定理7可知,当1≤i,j≤6时,

(21)

其中“·” 表示矩阵间的点乘运算.

例4.(接例3)根据定义8已知粒度A1,A2和A3的中介矩阵分别为:GA1=[2,1,1,2,1,1]T,GA2=[1,1,1,1,2,2]T,GA3=[1,0,2,2,3,2]T.新增对象x7后,以粒度A1为例,当1≤i≤6时,

例5.(接例4)根据定义9～定义10以及定理1～定理2计算论域新增对象时,乐观与悲观情况下的正域矩阵、边界域矩阵以及负域矩阵:

因此,根据定义5可得:

下面给出邻域多粒度粗糙集中,在对象增加时基于矩阵运算更新正域、负域、边界域的算法描述.

算法2.对象增加时更新邻域多粒度粗糙集知识的增量算法

输入:(1)邻域信息系统NIS=(U,AT,V,f),论域U={xi|i∈{1,2,…,n}},A1,A2,…,Am⊆AT,X⊆U.

(2)概念X的布尔列矩阵为FU(X),邻域关系矩阵为MAk,对角矩阵为ΛAk，中介矩阵为GAk.

(3)增加的对象集ΔU={xn+1,xn+2,…,xn+n′},邻域阈值为δ.

输出:更新后的正域、边界域、负域;

Begin:初始化FU∪ΔU(X)←FU(X),M′Ak←MAk,

Step 1.forn+1≤i≤n+n′ do

ifxi∈X′ thenf′i=1

elsef′i=0;

end

Step 2.forn+1≤i≤n+n′ do

for 1≤j≤n+n′ do

if ΔAk(xi,xj)≤δthen

end

end

Step 3.for 1≤i≤ndo

end

forn+1≤i≤n+n′ do

end

Step 4.计算HAk(X)=GAk/·ΛAk;

在算法2中，更新目标概念X的布尔列矩阵的时间复杂度为O(n′);更新邻域关系矩阵的时间复杂度为O(n·n′); 更新对角矩阵和中介矩阵的复杂度为O(n·n′).因此,算法2的总体时间复杂度为O(n·n′).因为n′≪n,可以看出算法2比算法1效率更高.

3.2 对象减少时增量更新近似集算法

在这一节中，我们将讨论如何使用矩阵方法在论域中对象数目减少时更新正域、边界域和负域.具体的定理描述和过程如下.

(22)

与定理3类似,在删除对象集ΔU后,新矩阵中的元素可以从原始矩阵中的元素映射得到.下面给出了一个例子来说明更新过程.

表3 删除对象后的邻域信息系统

Table 3 Neighborhood information system when object is removed

UA1A2A3x11.180.200.17x20.760.360.74x30.420.250.28x41.090.410.39x60.800.760.58

基于布尔列矩阵更新思想,下面给出邻域关系矩阵的更新方法.

(23)

证明:证明过程与定理3证明过程类似.

例7.(接例6)根据定义6,已知粒度A1,A2和A3的邻域关系矩阵分别为:

当i=5时

故粒度A1更新后的邻域关系矩阵为

同理,粒度A2,A3对应更新后的邻域关系矩阵分别为:

(24)

接下来，通过一个实例说明邻域对角矩阵的更新过程.

例8.(接例7) 由定义7可知，粒度A1,A2和A3的对角矩阵分别为:ΛA1=diag[2,2,2,2,2,2],ΛA2=diag[2,3,3,2,2,2],ΛA3=diag[2,1,3,3,3,2].以对角矩阵ΛA1为例,假设论域中减少了对象x5.根据定理9,当1≤i<5时,

(25)

其中“·”表示矩阵间的点乘运算.

例9.(接例8) 根据定义8已知粒度A1,A2和A3的中介矩阵分别为:GA1=[2,1,1,2,1,1]T,GA2=[1,1,1,1,2,2]T,GA3=[1,0,2,2,3,2]T.删除对象x5后,以粒度A1为例.当1≤i<5时,

例10.(接例9) 根据定义9～定义10以及定理1～定理2计算论域对象减少时,乐观与悲观情况下的正域矩阵、边界域矩阵以及负域矩阵:

因此根据定义5可得:

定理7～定理10描述了对象从论域中删除时,基于矩阵方法的更新策略,并且通过例子进一步介绍了该增量方法的计算过程.下面给出具体的算法描述.

算法3.对象减少时更新邻域多粒度粗糙集知识的增量算法

输入:(1)邻域信息系统NIS=(U,AT,V,f),论域U={xi|i∈{1,2,…,n}},A1,A2,…,Am⊆AT,X⊆U.

(2)概念X的布尔列矩阵为FU(X),邻域关系矩阵为MAk,对角矩阵为ΛAk，中介矩阵为GAk.

(3)删除对象集ΔU={xt1,xt2,…,xtn′},邻域阈值δ;

输出:更新后的正域、边界域、负域;

Step 1.for 1≤i≤t1-1 do

for 1≤j≤t1-1 do

end

end

Step 2.fort1≤r≤n′ do

fort1≤i≤tn′-n′ do

f′i=fi+r-1;

fort1≤j≤tn′-n′ do

end

end

end

Step 3.for 1≤r≤n′ do

fortr-1-r+2≤i≤tr-r+1 do

end

end

Step 4.fortn′-n′+1≤i≤n-n′ do

f′i=fi+n′;

fortn′-n′+1≤j≤n-n′ do

end

end

Step 5.计算HAk(X)=GAk/·ΛAk;

在算法3中，更新目标概念X的布尔列矩阵的时间复杂度为O(n-n′);更新邻域关系矩阵的时间复杂度为O((n′)2);更新对角矩阵和中介矩阵的时间复杂度约为O((n′)2+(n-n′)).因此，算法3的总体时间复杂度为O((n′)2+(n-n′)).

4 实 验

为了进一步论证本文提出算法的有效性,在这一部分中，我们将使用仿真实验和具体的数据集来验证算法在动态更新邻域多粒度粗糙近似集的效率.在本实验中,每组对比实验中通过三种算法的计算均得到了相同的实验结果.在此前提下,实验测量以算法的执行时间作为依据,证明了在动态更新邻域多粒度粗糙近似集方面,增量算法的效率相比非增量算法更能体现优势.本文着重讨论了矩阵增量更新算法与非增量更新算法相比的优点,并没有对其他增量算法进行对比实验.

表4 数据集描述

Table 4 Descriptions of datasets

NO.Data setsObjectsGranular structuresClasses1Iris150432Glass Identification2141073User Knowledge Modeling403544Website Phishing13531035CMC14731036Segmentation2130197

实验分为两组,分别对应两种情况：对象的减少和对象的增加.在两组实验均选择了相同的6个UCI数据集[26],一个属性作为一个粒度.最后,分析了非增量算法和增量算法在不同数据集上的执行时间增长率的情况,进一步验证了本文提出的算法的有效性.实验环境操作系统为Windows 7,CPU为Intel(R)Core(TM)i3 550@3.20GHz,内存4G,使用编程语言java在Eclipse neon平台进行开发.数据集的详细说明如表4所示.

4.1 对象增加时的效率对比

在本实验中，我们比较了非增量(算法1)和增量算法(算法2)的计算效率.对于表4中的每一个数据集，我们先做如下处理:首先将数据集分成10个不相交且大小相等的子集D1,D1,…,D10,这十个数据子集依次组合由可以产生10个增长率为10%的数据子集，分别为D1,D1∪D2，…,D1∪D2∪…∪D10.这10组数据子集分别作为10组对比数据.另外,需要注意的是增量更新近似集的算法在增量更新时需要输入初始数据值,所以在第一组数据子集D1中,增量算法的执行时间设置为0.

图1 对象增加时算法1和算法2的执行时间对比

图1展示了在不同数据规模中,由于对象的增加,在算法1和算法2中更新正域、边界域和负域所花费的时间.其中,纵坐标表示算法的执行时间,横坐标表示数据增长的比例.由图1可看出,在实验选取的6个数据集中,增量算法的执行时间都小于非增量算法.随着数据规模的增大,非增量算法的执行时间增长较快,而增量算法的时间增长较慢.例如在数据集Glass Identification中,数据规模增长到100%时,非增量算法的执行时间为0.238秒,而增量算法仅需0.031秒.

4.2 对象减少时的效率对比

在第二组实验中，我们比较了对象减少时非增量(算法1)和增量算法(算法3)的执行时间.对于每个数据集，我们先做如下处理:首先将数据集分成10个不相交且大小相等的子集D1,D1,…,D10.这十个数据子集依次组合由可以产生个增长率为10%的数据子集，分别为D1∪D2，D1∪D2∪D3，…,D1∪D2∪…∪D10,这9组数据子集分别作为9组对比数据,这样保证了每个据子集包含相同数量的数据子集D1.以验证在不同数据规模下,减少相同比例的对象时非增量算法和增量算法在更新正域、边界域、负域时的性能.

图2展示了在不同数据规模中,由于对象的减少,使用算法1和算法3更新正域、边界域和负域和所花费的时间.其中，纵坐标指算法的执行时间,横坐标是指数据减少的比例.由图2可看出,在实验选取的6个数据集中,增量算法的执行时间都小于非增量算法.随着数据规模的增大,非增量算法的执行时间增长较快,而增量算法的时间增长较慢.例如在数据集Glass Identification中,当数据规模增长到100%的时候,非增量算法的执行时间为0.199s,而增量算法仅需0.035s.

图2 对象减少时算法1和算法3的执行时间对比

图3 增量算法与非增量算法执行时间增长率对比

图3展示了数据量从初始值变化到100%时,非增量算法和增量算法在不同数据集中的执行时间增长率.从图中可以看出,随着数据量的变化,非增量算法的执行时间增长很快,而增量算法的执行时间增长缓慢.例如,从图3(a)可以看出,非增量算法的最大时间增长率是50%,而增量算法的时间增长率仅仅是11%，增量算法的时间增长率都低于非增量算法的时间增长率.因此,对于不同规模的数据,增量算法在处理大规模数据的情况下,其稳定性也优于非增量算法.

5 结 论

由于数据集在实际应用中是不断变化的,如属性的变化、属性值的变化以及论域的变化等.在任何类型的改变之后,需要重新计算原始近似集.本文从论域的角度出发,提出一种在矩阵方法基础上来解决多粒度环境下领域动态变化的问题,与传统的静态方法相比,本文提出的增量方法不仅减少了计算量,而且提高了执行效率.最后,实验也证明了本文提出的方法是有效的.增量技术是在动态环境中保持知识的一种有效方法,通过矩阵运算又可以提高增算法的执行效率.在下一步的工作中，我们将基于分块的思想减少粒度矩阵的计算，并进一步研究简化粒度矩阵构造的过程，从而提高算法的效率.