鄰域多粒度粗糙集知識更新增量算法

徐 怡,孫偉康,王 泉

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 結 論

由于數據集在實際應用中是不斷變化的,如屬性的變化、屬性值的變化以及論域的變化等.在任何類型的改變之后,需要重新計算原始近似集.本文從論域的角度出發,提出一種在矩陣方法基礎上來解決多粒度環境下領域動態變化的問題,與傳統的靜態方法相比,本文提出的增量方法不僅減少了計算量,而且提高了執行效率.最后,實驗也證明了本文提出的方法是有效的.增量技術是在動態環境中保持知識的一種有效方法,通過矩陣運算又可以提高增算法的執行效率.在下一步的工作中，我們將基于分塊的思想減少粒度矩陣的計算，并進一步研究簡化粒度矩陣構造的過程，從而提高算法的效率.