国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

區(qū)間值決策表的正域增量式屬性約簡算法

2019-10-23 12:23鮑迪張楠童向榮岳曉冬
計算機應用 2019年8期
關鍵詞:粗糙集

鮑迪 張楠 童向榮 岳曉冬

摘 要:實際應用中存在大量動態(tài)增加的區(qū)間型數(shù)據(jù),若采用傳統(tǒng)的非增量正域?qū)傩约s簡方法進行約簡,則需要對更新后的區(qū)間值數(shù)據(jù)集的正域約簡進行重新計算,導致屬性約簡的計算效率大大降低。針對上述問題,提出區(qū)間值決策表的正域增量屬性約簡方法。首先,給出區(qū)間值決策表正域約簡的相關概念;然后,討論并證明單增量和組增量的正域更新機制,提出區(qū)間值決策表的正域單增量和組增量屬性約簡算法;最后,通過8組UCI數(shù)據(jù)集進行實驗。當8組數(shù)據(jù)集的數(shù)據(jù)量由60%增加至100%時,傳統(tǒng)非增量屬性約簡算法在8組數(shù)據(jù)集中的約簡耗時分別為36.59s、72.35s、69.83s、154.29s、80.66s、1498.11s、4124.14s和809.65s,單增量屬性約簡算法的約簡耗時分別為19.05s、46.54s、26.98s、26.12s、34.02s、1270.87s、1598.78s和408.65s,組增量屬性約簡算法的約簡耗時分別為6.39s、15.66s、3.44s、15.06s、8.02s、167.12s、180.88s和61.04s。實驗結(jié)果表明,提出的區(qū)間值決策表的正域增量式屬性約簡算法具有高效性。

關鍵詞:粗糙集;區(qū)間值決策表;相容關系;正域;增量式屬性約簡

中圖分類號:?TP181

文獻標志碼:A

Incremental attribute reduction algorithm of positive region in interval-valued decision tables

BAO Di1,2, ZHANG Nan1,2*, TONG Xiangrong1,2, YUE Xiaodong3

1.Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes (Yantai University), Yantai Shandong 264005, China?;

2.School of Computer and Control Engineering, Yantai University, Yantai Shandong 264005, China?;

3.School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China

Abstract:??There are a large number of dynamically-increasing interval data in practical applications. If the classic non-incremental attribute reduction of positive region is used for reduction, it is necessary to recalculate the positive region reduction of the updated interval-valued datasets, which greatly reduces the computational efficiency of attribute reduction. In order to solve the problem, incremental attribute reduction methods of positive region in interval-valued decision tables were proposed. Firstly, the related concepts of positive region reduction in interval-valued decision tables were defined. Then, the single and group incremental mechanisms of positive region were discussed and proved, and the single and group incremental attribute reduction algorithms of positive region in interval-valued decision tables were proposed. Finally, 8 UCI datasets were used to carry out experiments. When the incremental size of 8 datasets increases from 60% to 100%, the reduction time of classic non-incremental attribute reduction algorithm in the 8 datasets is 36.59s, 72.35s, 69.83s, 154.29s, 80.66s, 1498.11s, 4124.14s and 809.65s, the reduction time of single incremental attribute reduction algorithm is 19.05s, 46.54s, 26.98s, 26.12s, 34.02s, 1270.87s, 1598.78s and 408.65s, the reduction time of group incremental attribute reduction algorithm is 6.39s, 15.66s, 3.44s, 15.06s, 8.02s, 167.12s, 180.88s and 61.04s. Experimental results show that the proposed incremental attribute reduction algorithm of positive region in interval-valued decision tables is efficient.

Key words:?rough set; interval-valued decision table; tolerance relation; positive region; incremental attribute reduction

0 引言

粗糙集理論中,屬性約簡[1-4]是重要研究內(nèi)容之一。屬性約簡的主要目標是移除冗余屬性,提高數(shù)據(jù)處理效率。目前,諸多學者通過深入研究給出了一系列求解約簡的方法。苗奪謙等[5]引入互信息用于選擇對決策重要的條件屬性,并基于互信息給出了啟發(fā)式的屬性約簡方法;Xu等[6]在不協(xié)調(diào)序信息系統(tǒng)下給出了計算分布約簡的矩陣方法;Min等[7]基于信息增益設計了測試代價敏感的約簡算法;Hu等[8]首次以正域定義屬性重要度啟發(fā)式求解約簡;Qian等[9]定義了局部粗糙集的理論框架,給出目標概念的局部約簡方法;Jia等[10]將代價敏感和最優(yōu)化問題引入決策粗糙集,進而求得最小代價約簡。

目前,區(qū)間型數(shù)據(jù)廣泛存在于工程測量、醫(yī)學等領域。在決策表中,若條件屬性值為區(qū)間值,則該決策表稱為區(qū)間值決策表。針對區(qū)間值決策表,眾多學者進行了屬性約簡研究。Leung等[11]定義了基于錯誤分類率的相容關系,分析了區(qū)間值決策表下的規(guī)則獲取;張楠等[12]針對分類結(jié)果冗余度大和錯分率高的問題,在區(qū)間值決策表中定義了α極大相容類,給出了廣義決策保持約簡;劉鵬惠等[13]定義了區(qū)間值決策表下的變精度相容關系,給出了決策屬性約簡與相對約簡的方法;徐菲菲等[14]以電力數(shù)據(jù)為背景,基于互信息和依賴度提出了區(qū)間值約簡算法,并給出了多決策表下的全局約簡方法,增強了算法的實用性;Dai等[15]分析了基于區(qū)間值相似度的擴展條件熵,討論了區(qū)間值決策表的不確定性度量問題。

現(xiàn)實應用中的數(shù)據(jù)集通常動態(tài)增加到數(shù)據(jù)庫,為及時從數(shù)據(jù)中獲得知識,相關學者給出了不同的增量更新方法[16-19]。在決策表中,數(shù)據(jù)動態(tài)變化有三種類型:對象集的動態(tài)增加、屬性集的動態(tài)增加和屬性值的動態(tài)改變。Hu等[20]針對單個對象的動態(tài)變化定義了正、負基本集,根據(jù)正、負基本集的改變更新約簡;Xu等[21]運用0-1整數(shù)運算,提出一種屬性約簡的增量式算法;楊明[22]改進了差別矩陣定義,避免了差別函數(shù)的計算,在動態(tài)更新核屬性的基礎上增量更新約簡;Liang等[23]分析了對象集增加后信息熵的變化規(guī)律,給出了高效處理海量數(shù)據(jù)的組增量方法;Shu等[24]在對象集動態(tài)變化的不完備決策表中提出了基于正域的增量式算法;Yu等[25]在區(qū)間值信息系統(tǒng)下定義了區(qū)間相似度,分析了近似集隨對象集變化的增量更新方法;Wang等[26]討論了信息熵的屬性增量機制,從屬性的角度分析了數(shù)據(jù)集融合;Liu等[27]在概率粗糙集模型下分析了近似集的更新策略,采用增量方法計算近似集;Cheng[28]針對屬性集的動態(tài)改變,基于邊界域和截集變化更新模糊算子;Chen等[29]分析了屬性值域與知識粒的變化關系,給出了增量更新近似集的原理和相應算法。

上述研究主要針對完備決策表或不完備決策表討論增量更新方法,由于實際應用中存在大量的區(qū)間型數(shù)據(jù),而針對區(qū)間值決策表的增量式屬性約簡研究未見報道,因此,本文提出區(qū)間值決策表正域?qū)傩约s簡的增量方法,該增量方法可以在不重新計算的情況下獲得更新后區(qū)間值決策表的正域約簡,提高約簡的計算效率。本文首先介紹了區(qū)間值決策表的相關概念,然后分析了對象集動態(tài)變化時正域的單增量和組增量更新機制,提出了區(qū)間值決策表的正域單增量和組增量屬性約簡算法,最后通過實驗驗證了增量算法的高效性。

1 預備知識

本章將介紹區(qū)間值決策表和上、下近似等相關概念,給出區(qū)間值決策表的傳統(tǒng)正域非增量屬性約簡算法。

1.1 區(qū)間值決策表的上、下近似

定義1 [12] 區(qū)間值信息表是四元組IT=(U,A,V, f),其中:U={x1,x2,…,xn}為有限對象集,稱為論域;A為有限屬性集;V= ∪ ?ak∈A Vak為區(qū)間的集合,Vak為屬性ak∈A的值域; f是U×A→V的映射,表示xi∈U在ak∈A上存在對應的區(qū)間屬性值。

若有限屬性集A=C∪D,其中:條件屬性集C={a1,a2,…,am},決策屬性集D=syggg00;V=VC∪VD,VC是條件屬性值集,VD是決策屬性值集,其中決策屬性值為單值,則DT=(U,C∪D,V, f)稱為區(qū)間值決策表。

論域U關于決策屬性集D的不可分辨關系IND(D)={(xi,xj)∈U×U | d∈D,d(xi)=d(xj)},其中d(x)是對象x關于決策屬性d∈D的屬性值。不可分辨關系IND(D)對U的劃分U/IND(D)={D1,D2,…,Dr}(1

定義2 [30] 給定兩個區(qū)間值λ1=[lki,uki]和λ2=[lkj,ukj],區(qū)間值的交、并運算定義如下:

λ1∩λ2=

0,???? (uki

[max(lki,lkj),min(uki,ukj)], 其他? ??(1)

λ1∪λ2=[min(lki,lkj),max(uki,ukj)]

(2)

區(qū)間值交、并運算的介紹,為描述Jaccard相似率提供了方便,下面給出區(qū)間值Jaccard相似率的定義。

定義3? 給定區(qū)間值決策表DT=(U,C∪D,V, f),xi,xj∈U,ak∈C,令ak(xi)=[lki,uki],ak(xj)=[lkj,ukj],則區(qū)間值ak(xi)和ak(xj)的Jaccard相似率[30]:

αkij= ?| [lki,uki]∩[lkj,ukj] | ??| [lki,uki]∪[lkj,ukj] |

(3)

其中: | · | 表示閉區(qū)間長度。αkij值越大,對象xi和xj關于屬性ak的相似度越高。

定義4 [13] 設區(qū)間值決策表DT=(U,C∪D,V, f),PC,相似率閾值α∈[0,1],定義關于屬性子集P的α-相容關系為:

TRαP={(xi,xj) | (xi,xj)∈U×U,αkij>α,ak∈P}

(4)

α-相容關系具有以下性質(zhì):

性質(zhì)1 [12] 設區(qū)間值決策表DT=(U,C∪D,V, f), PC, α∈[0,1],則TRαP滿足自反性和對稱性。

性質(zhì)2 [12] 設區(qū)間值決策表DT=(U,C∪D,V, f), PC, α∈[0,1],則TRαP= ∩ ?ak∈P TRα{ak}。

定義5 [13] 區(qū)間值決策表DT=(U,C∪D,V, f), PC, α∈[0,1], 在屬性子集P下定義對象xi的α-相容類為:

SαP(xi)={xj | xj∈U,(xi,xj)∈TRαP}

(5)

所有SαP(xi)(xi∈U)的集合形成對U的覆蓋SαP(U)={SαP(x1),SαP(x2),…,SαP(x|U|)}。

基于上述概念,給出區(qū)間值決策表上、下近似的定義。

定義6 [14] 區(qū)間值決策表DT=(U,C∪D,V, f),XU,PC,α∈[0,1],對象xi的相容類為SαP(xi),定義X關于屬性子集P的上、下近似分別為:

aprαP (X)={xi | xi∈U,SαP(xi)∩X≠}

(6)

aprαP (X)={xi | xi∈U,SαP(xi)X}

(7)

X關于P的正域、邊界域和負域分別定義為:

POSαP(X)=aprαP (X)

(8)

BNDαP(X)=aprαP (X)-aprαP (X)

(9)

NEGαP(X)=U-(POSαP(X)∪BNDαP(X))

(10)

定義7 [14] 區(qū)間值決策表 α,α,α∈[0,1],U/IND(D)={D1,D2,…,Dr}

DT=(U,C∪D,V, f), PC,α∈[0,1], IND(D)對 U/IND(D)={D1,D2,…,Dr} U的劃分U/IND(D)={D1,D2,…,Dr}(1

aprαP (D)={aprαP (D1),aprαP (D2),…,aprαP (Dr)}

(11)

aprαP (D)={aprαP (D1),aprαP (D2),…,aprαP (Dr)}

(12)

定義正域POSαP(D)= ∪ ?r i=1 aprαP (Di)。為便于后續(xù)章節(jié)討論,正域可定義為POSαP(D)={xi∈U | ?| SαP(xi)/IND(D) | =1}, 其中 | SαP(xi)/IND(D) | =1表示xi的相容類中所有對象的決策值唯一。

定義8 [11] 設區(qū)間值決策表DT=(U,C∪D,V, f), U={x1,x2,…,xn},相似率閾值α∈[0,1],對PC,論域U和屬性集P確定的布爾相似矩陣 M αP定義為:

M αP=? r11 r12 … r1n ? rn1 rn2 … rnn

若對ak∈P,對象xi和xj在屬性ak上的相似率αkij>α(i, j∈[1,n]),則rij=1,表示對象xi和xj相似;否則rij=0,表示對象xi和xj不相似。

例1? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,U={x1,x2,x3,x4,x5,x6}為論域,C={a1,a2,a3,a4}為條件屬性集,D=syggg00為決策屬性集。令相似率閾值α=0.6,計算正域POSαC(D)。其中區(qū)間值ak(xi)=[lki,uki]為條件屬性值,單值d(xi)為決策屬性值,例如:a1(x3)=[0.75,3.02],d(x3)=1。

根據(jù)表1計算布爾相似矩陣 M 0.6C如下:

M 0.6C=? 1 0 0 0 0 00 1 0 1 0 10 0 1 0 0 00 1 0 1 0 10 0 0 0 1 00 1 0 1 0 1

由布爾相似矩陣可得相容類集合:S0.6C(U)={S0.6C(x1),S0.6C(x2),S0.6C(x3),S0.6C(x4),S0.6C(x5),S0.6C(x6)},其中S0.6C(x1)={x1}, S0.6C(x2)=S0.6C(x4)=S0.6C(x6)={x2,x4,x6}, S0.6C(x3)={x3}, S0.6C(x5)={x5}。

由于: | S0.6C(x1)/IND(D) | =1, | S0.6C(x2)/IND(D) | ≠1, | S0.6C(x3)/IND(D) | =1, | S0.6C(x4)/IND(D) | ≠1, | S0.6C(x5)/IND(D) | =1, | S0.6C(x6)/IND(D) | ≠1。根據(jù)定義7,D關于C的正域為POS0.6C(D)={x1,x3,x5}。

定義9 [14] 設區(qū)間值決策表DT=(U,C∪D,V, f),PC,若P是DT的一個約簡,則需滿足以下兩個條件:

1)POSαP(D)=POSαC(D);

2)P′P,滿足POSαP′(D)≠POSαP(D)。

條件1)保證了約簡前后區(qū)間值決策表的正域相同,條件2)保證了無冗余屬性存在于約簡結(jié)果。

例2? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,U={x1,x2,x3,x4,x5,x6}為論域,C={a1,a2,a3,a4}為條件屬性集,D=syggg00為決策屬性集,計算區(qū)間值決策表DT的一個約簡。

通過例1計算正域POS0.6C(D)={x1,x3,x5},由于POS0.6{a1,a3}(D)=POS0.6C(D),POS0.6{a1}(D)≠POS0.6C(D),POS0.6{a3}(D)≠POS0.6C(D),根據(jù)定義9,屬性子集{a1,a3}與屬性集C保持的正域相同,且屬性子集{a1,a3}中無冗余屬性,因此{a1,a3}是一個約簡。

定義10 [14] 設區(qū)間值決策表DT=(U,C∪D,V, f), PC,α∈[0,1],a∈P,定義屬性a在屬性子集P中的內(nèi)部重要度為:

siginner(a,P,D)= | POSαP(D)-POSαP-{a}(D) |

(13)

若siginner(a,P,D)>0,則a是核屬性;若siginner(a,P,D)=0,則a是可去屬性。在屬性約簡過程中,內(nèi)部重要度用于計算核屬性或刪除屬性集中的冗余屬性。

定義11 [14] 設區(qū)間值決策表DT=(U,C∪D,V, f), PC,α∈[0,1],a∈C-P,定義屬性a相對于屬性子集P的外部重要度為:

sigouter(a,P,D)= | POSαP∪{a}(D)-POSαP(D) |

(14)

1.2 區(qū)間值決策表的正域非增量屬性約簡算法

本節(jié)根據(jù)文獻[14]給出區(qū)間值決策表的傳統(tǒng)正域非增量屬性約簡算法,對于對象集動態(tài)增加的區(qū)間值決策表,該算法要重新計算約簡結(jié)果。區(qū)間值決策表的傳統(tǒng)正域非增量屬性約簡算法(Classic non-incremental Attribute Reduction algorithm based on positive region in interval-valued decision tables,CAR)具體描述如下:

算法1? 區(qū)間值決策表的傳統(tǒng)正域非增量屬性約簡算法(CAR)。

輸入? 區(qū)間值決策表DT=(U,C∪D,V, f)。

輸出? 約簡結(jié)果Red。

步驟1? 令Red←;

步驟2? 對所有屬性ai∈C,計算siginner(ai,C,D),若siginner(ai,C,D)>0,令Red←Red∪{ai};

步驟3? 若POSαRed(D)≠POSαC(D),重復:

步驟3.1 ?對所有屬性aj∈C-Red,計算sigouter(aj,Red,D);

步驟3.2 ?選取ak=arg max{sigouter(aj,Red,D)},令Red←Red∪{ak};

步驟4? 對b∈Red,計算siginner(b,Red,D),若siginner(b,Red,D)=0,令Red←Red-;

步驟5? 返回Red。

算法1計算正域的時間復雜度是O( | C | ?| U | 2),計算核屬性的時間復雜度是O( | C | 2 | U | 2),選擇屬性添加到核屬性集的時間復雜度是O( | C | 3 | U | 2),刪除冗余屬性的時間復雜度是O( | C | 2 | U | 2),所以算法1整體的時間復雜度是O( | C | 3 | U | 2)。

2 單增量屬性約簡

針對對象集動態(tài)變化的區(qū)間值決策表,2.1節(jié)分析了單個對象增加后決策類和相容類的變化規(guī)律,給出了單增量的正域更新機制;2.2節(jié)討論了增加單個對象與初始約簡結(jié)果的變化關系,給出了不同的約簡更新策略,提出了區(qū)間值決策表的正域單增量屬性約簡算法。

2.1 單增量的正域更新機制

屬性約簡過程中,若使用非增量方法更新正域,會導致正域的計算效率低。為了提高正域的計算效率,可采用增量方法更新正域,下面介紹單個對象增加后的正域更新機制。

定理1? 設區(qū)間值決策表DT=(U,C∪D,V, f),任意屬性子集PC,增加對象x后更新論域為U′=U∪{x},POSαP(D)為論域U在屬性子集P下的初始正域,Sα(P,U′)(x)為論域U′中對象x的相容類,[x]D為x所在決策類中的對象集合,論域U′在屬性子集P下更新正域為:

POSα(P,U′)(D)=POSαP(D)∪{y∈{x} | ?| Sα(P,U′)(y)/IND(D) | =1}-{y∈Sα(P,U′)(x) | ?| Sα(P,U′)(y)/IND(D) | ≠1}。

若 | Sα(P,U′)(y)/IND(D) | =1,則表示相容類Sα(P,U′)(y)中所有對象的決策屬性值相同;反之,則表示相容類Sα(P,U′)(y)中對象的決策屬性值存在差異。

證明

對象x增加到區(qū)間值決策表后分以下四種情況進行討論:

1)Sα(P,U′)(x)={x}且[x]D={x}。顯然 | Sα(P,U′)(x)/IND(D) | =1,由正域定義可知,POSα(P,U′)(D)={y∈U | ?| Sα(P,U′)(y)/IND(D) | =1}∪{y∈{x} | ?| Sα(P,U′)(y)/IND(D) | =1},由于Sα(P,U′)(x)={x}且[x]D={x},所以{y∈U | ?| Sα(P,U′)(y)/IND(D) | =1}={y∈U | ?| SαP(y)/IND(D) | =1},因此,更新正域POSα(P,U′)(D)=POSαP(D)∪{x}。

2)Sα(P,U′)(x)={x}且[x]D≠{x}。顯然 | Sα(P,U′)(x)/IND(D) | =1,POSα(P,U′)(D)={y∈U | ?| Sα(P,U′)(y)/IND(D) | =1}∪{y∈{x} | ?| Sα(P,U′)(y)/IND(D) | =1},由于Sα(P,U′)(x)={x}且[x]D≠{x},所以{y∈U | ?| Sα(P,U′)(y)/IND(D) | =1}={y∈U | ?| SαP(y)/IND(D) | =1},因此,更新正域POSα(P,U′)(D)=POSαP(D)∪{x}。

3)Sα(P,U′)(x)≠{x}且[x]D={x}。顯然 | Sα(P,U′)(x)/IND(D) | ≠1,對于y∈Sα(P,U′)(x)滿足 | Sα(P,U′)(y)/IND(D) | ≠1,由正域定義知,POSα(P,U′)(D)={y∈U | ?| SαP(y)/IND(D) | =1}-{y∈Sα(P,U′)(x) | ?| Sα(P,U′)(y)/IND(D) | ≠1}∪,因此,更新正域POSα(P,U′)(D)=POSαP(D)-{y∈Sα(P,U′)(x) | ?| Sα(P,U′)(y)/IND(D) | ≠1}。

4)Sα(P,U′)(x)≠{x}且[x]D≠{x}。更新正域POSα(P,U′)(D)=POSαP(D)-{y∈Sα(P,U′)(x) | ?| Sα(P,U′)(y)/IND(D) | ≠1},證明與上類似,不再贅述。

綜上,更新后的正域POSα(P,U′)(D)=POSαP(D)∪{y∈{x} | ?| Sα(P,U′)(y)/IND(D) | =1}-{y∈Sα(P,U′)(x) | ?| Sα(P,U′)(y)/IND(D) | ≠1}。

例3? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,新增對象x如表2所示,更新論域U′=U∪{x},令相似率閾值α=0.6,計算區(qū)間值決策表DT′=(U′,C∪D,V, f)的正域POS0.6(C,U′)(D)。

由例1計算初始正域POS0.6C(D)={x1,x3,x5}。計算對象x關于論域U′的相容類S0.6(C,U′)(x)={x5,x},對象x5關于論域U′的相容類S0.6(C,U′)(x5)={x5,x}。由于 | S0.6(C,U′)(x)/IND(D) | ≠1并且 | S0.6(C,U′)(x5)/IND(D) | ≠1,根據(jù)定理1更新正域:POS0.6(C,U′)(D)=POS0.6C(D)∪-{x5}={x1,x3,x5}-{x5}={x1,x3}。

2.2 區(qū)間值決策表的正域單增量屬性約簡算法

屬性約簡是保持決策表分類能力不變的條件下,移除冗余屬性,獲得最小屬性子集。當單個對象增加到區(qū)間值決策表,決策表的分類能力可能發(fā)生變化,因此需要更新初始約簡結(jié)果。下面討論單個對象增加后初始約簡結(jié)果的變化情況。

給定區(qū)間值決策表DT=(U,C∪D,V, f),相似率閾值α∈[0,1],初始約簡結(jié)果B,新增對象x,更新后的區(qū)間值決策表DT′=(U′,C∪D,V, f),其中U′=U∪{x}。對象x關于B和C的相容類存在以下三種情況:

1) | Sα(C,U′)(x)/IND(D) | =1且 | Sα(B,U′)(x)/IND(D) | =1;

2) | Sα(C,U′)(x)/IND(D) | =1且 | Sα(B,U′)(x)/IND(D) | ≠1;

3) | Sα(C,U′)(x)/IND(D) | ≠1且 | Sα(B,U′)(x)/IND(D) | ≠1。

只有滿足1)時,區(qū)間值決策表DT′的約簡結(jié)果依然是初始約簡結(jié)果。

定理2? 若滿足 | Sα(C,U′)(x)/IND(D) | =1且 | Sα(B,U′)(x)/IND(D) | =1,則初始約簡結(jié)果B是區(qū)間值決策表DT′的約簡結(jié)果。

證明

根據(jù)正域定義,由于 | Sα(C,U′)(x)/IND(D) | =1,故POSα(C,U′)(D)=POSαC(D)∪{x},由于 | Sα(B,U′)(x)/IND(D) | =1,故POSα(B,U′)(D)=POSαB(D)∪{x}。又因為B是初始約簡結(jié)果,POSαB(D)=POSαC(D),所以POSα(C,U′)(D)=POSα(B,U′)(D)。由定義9可知,對于B′B,有POSαB′(D)≠POSαB(D),POSαB′(D)POSαB(D),POSα(B′,U′)(D)POSαB′(D)∪{x},POSα(B′,U′)(D)POSαB(D)∪{x}=POSα(B,U′)(D),故POSα(B′,U′)(D)≠POSα(B,U′)(D)。因此,初始約簡結(jié)果B是區(qū)間值決策表DT′的約簡結(jié)果。

證畢。

基于以上分析,下面給出區(qū)間值決策表的正域單增量屬性約簡算法(a Single Incremental Attribute Reduction algorithm based on positive region in interval-valued decision tables, SIAR)。

算法2? 區(qū)間值決策表的正域單增量屬性約簡算法(SIAR)。

輸入? 區(qū)間值決策表DT=(U,C∪D,V, f),初始約簡結(jié)果B0,初始正域POSαC(D),新增對象x。

輸出? 論域U′上的約簡結(jié)果Red。

步驟1? 令B←B0,U′←U∪{x}。

步驟2? 計算相容類Sα(C,U′)(x)。

步驟3? 計算相容類Sα(B,U′)(x)。

步驟4 ?若滿足 | Sα(C,U′)(x)/IND(D) | =1且 | Sα(B,U′)(x)/ IND(D) | =1, 令Red←B,返回約簡結(jié)果Red;否則,轉(zhuǎn)至步驟5。

步驟5? 若POSα(B,U′)(D)≠POSα(C,U′)(D),重復:

步驟5.1? 對所有屬性ak∈C-B,計算sigouterU′(ak,B,D);

步驟5.2? 選取ai=arg max{sigouterU′(ai,B,D)},令B←B∪{ai}。

步驟6? 對b∈B,計算siginnerU′(b,B,D)= | POSα(B,U′)(D)-POSα(B-,U′)(D) | ,若siginnerU′(b,B,D)=0,令B←B-。

步驟7? Red←B,返回Red。

當對象增加到區(qū)間值決策表,根據(jù)定理1更新正域,更新正域的時間復雜度是O( | U | ?| C | +∑ |SαC(x)| t=1 ?| SαC(xt) | ),為表示簡潔,令Φ1=∑ |SαC(x)| t=1 ?| SαC(xt) | 。分別計算相容類Sα(C,U′)(x)和Sα(B,U′)(x)的時間復雜度是O( | U′ | ?| C | )和O( | U′ | ?| B | ),計算外部屬性重要度的時間復雜度是O( | C-B | ( | U | ?| B | +Φ1)),選取屬性添加到初始約簡的時間復雜度是O( | C-B | ( | U | ?| B | +Φ1)),刪除冗余屬性時間復雜度是O( | B | ( | U | ?| B | +Φ1))。所以算法2整體的時間復雜度是O( | U | ?| C | 2+ | C | Φ1)。

例4? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,新增對象x如表2所示,更新論域U′=U∪{x},令相似率閾值α=0.6,計算區(qū)間值決策表DT′=(U′,C∪D,V, f)的一個約簡。

由例2得初始約簡結(jié)果B={a1,a3},由例3得正域POS0.6(C,U′)(D)={x1,x3}。計算對象x在條件屬性集C下的相容類S0.6(C,U′)(x)={x5,x},對象x在條件屬性集B下的相容類S0.6(B,U′)(x)={x1,x5,x},由于 | S0.6(C,U′)(x)/IND(D) | ≠1且 | S0.6(B,U′)(x)/IND(D) | ≠1,故應更新初始約簡結(jié)果。通過計算得POS0.6(B,U′)(D)≠POS0.6(C,U′)(D),從剩余屬性集{a2,a4}中選擇外部重要度最大的屬性a4,POS0.6(B∪{a4},U′)(D)=POS0.6(C,U′)(D),因此B=B∪{a4}={a1,a3,a4}。由于siginner(a3,B,D)=0,所以a3為冗余屬性,刪除冗余屬性后的約簡結(jié)果Red={a1,a4}。

3 組增量屬性約簡

現(xiàn)實應用中,數(shù)據(jù)庫中的數(shù)據(jù)通常批量增加,傳統(tǒng)的非增量和單增量屬性約簡算法已不能滿足高效處理數(shù)據(jù)的要求。針對對象集動態(tài)增加的區(qū)間值決策表,本章將分析組增量的正域更新機制,提出區(qū)間值決策表的正域組增量屬性約簡算法。

3.1 組增量的正域更新機制

對象集的動態(tài)增加可能導致正域發(fā)生改變,下面給出組增量的正域更新機制。

定理3? 設區(qū)間值決策表DT=(U,C∪D,V, f),論域U={x1,x2,…,xn},任意條件屬性子集PC,TRαP對U的分類U/TRαP={SαP(x1),SαP(x2),…,SαP(xn)},IND(D)對U的劃分U/IND(D)={D1,D2,…,Dm},U在P下的初始正域為POSαP(D)。新增對象集U1={y1,y2,…,ys},TRαP對U1的分類 U1/TRαP={SαP(y1),SαP(y2),…,SαP(ys)},IND(D)對U1的劃分U1/IND(D)={T1,T2,…,Tm′}。論域Ua=U∪U1,Ua在屬性子集P下更新正域為:POSα(P,Ua)(D)=POSαP(D)∪POSα(P,U1)(D)-{xi∈X∧xi∈U | ?| Sα(P,Ua)′(xi)/IND(D) | ≠1}-{yj∈X∧yj∈U1 | ?| Sα(P,Ua)′(yj)/IND(D) | ≠1}。

其中,Sα(P,Ua)′(xi)和Sα(P,Ua)′(yj)表示變化的相容類,Sα(P,Ua)′(xi)=SαP(xi)∪{yj | yj∈U1,(xi,yj)∈TRαP},Sα(P,Ua)′(yj)=SαP(yj)∪{xi | xi∈U,(xi,yj)∈TRαP},X表示P在Ua上形成的具有相容關系的對象集合,X={xi∈POSαP(D),yj∈POSα(P,U1)(D) | (xi,yj)∈TRαP}。

證明

為表示簡潔,令SαP′(xi)=Sα(P,Ua)′(xi), SαP′(yj)=Sα(P,Ua)′(yj)。 假設在分類U/TRαP和U1/TRαP中, 存在一些對象在屬性集P下形成相容關系, 相容關系TRαP對論域Ua的分類Ua/TRαP={SαP′(x1), SαP′(x2), …, SαP′(xu), SαP(xu+1),? SαP(xu+2), …, SαP(xn), SαP′(y1), SαP′(y2), …, SαP′(yu′), SαP(yu′+1), SαP(yu′+2), …, SαP(ys)},其中u∈[1, l],l為論域U中發(fā)生變化的相容類個數(shù), u′∈[1, h], h為論域U1中發(fā)生變化的相容類個數(shù)。SαP′(xi)和SαP′(yj)表示變化的相容類,其中i∈[1,u], j∈[1,u′],對于yj∈U1,若yj∈SαP(xi),則SαP′(xi)=SαP(xi)∪{yj},由相容關系的對稱性可得SαP′(yj)=SαP(yj)∪{xi}。SαP(xe)和SαP(yw)表示未改變的相容類,SαP(xe)={xf | xf∈U,(xe,xf)∈TRαP},SαP(yw)={yq | yq∈U1,(yw,yq)∈TRαP},其中e∈[u+1,n],w∈[u′+1,s]。IND(D)對Ua的劃分Ua/IND(D)={D′1,D′2,…,D′v,Dv+1,…,Dm,Tv+1,…,Tm′},其中,D′z=Dz∪Tz(z=1,2,…,v),表示決策類Dz∈U/IND(D)與決策類Tz∈U1/IND(D)有相同的決策屬性值。則正域更新為:

POSα(P,Ua)(D)= ∪ ?v z=1 POSα(P,Ua)(D′z)∪

∪ ?m z=v+1 POSα(P,Ua)(Dz)∪ ∪ ?m′ z=v+1 POSα(P,Ua)(Tz)

其中: ∪ ?v z=1 POSα(P,Ua)(D′z)={xk∈U | SαP(xk)D′z} ∪{yr∈U1 | SαP(yr)D′z} (k∈[1,n],r∈[1,s])-{xi | SαP′(xi)D′z}-{yj | SαP′(yj)D′z} (i∈[1,u], j∈[1,u′])。 同理可得: ∪ ?m z=v+1 POSα(P,Ua)(Dz) = {xk∈U | SαP(xk)Dz} - {xi | SαP′(xi)Dz} (k∈[1,n],i∈[1,u]), ∪ ?m′ z=v+1 POSα(P,Ua)(Tz)={yr∈U1 | SαP(yr)Tz}-{yj | SαP′(yj)Tz}(r∈[1,s], j∈[1,u′])。

通過合并化簡可得正域:POSα(P,Ua)(D)=POSαP(D)∪POSα(P,U1)(D)-{xi∈X∧xi∈U | ?| Sα(P,Ua)′(xi)/IND(D) | ≠1}-{yj∈X∧yj∈U1 | ?| Sα(P,Ua)′(yj)/IND(D) | ≠1}。

證畢。

例5? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,新增對象集U1={y1,y2,y3}如表3所示。更新論域Ua=U∪U1,令相似率閾值α=0.6,計算論域Ua在屬性集C下的正域POS0.6(C,Ua)(D)。

由例1得初始正域POS0.6C(D)={x1,x3,x5},計算U1在C下的正域POS0.6(C,U1)(D)={y1,y2,y3}。對象集增加后x5和y1的相容類發(fā)生改變,S0.6(C,Ua)′(x5)=S0.6C(x5)∪{y1}={x5,y1},S0.6(C,Ua)′(y1)=S0.6(C,U1)(y1)∪{x5}={y1,x5},由于 | S0.6(C,Ua)′(x5)/IND(D) | ≠1且 | S0.6(C,Ua)′(y1)/IND(D) | ≠1,根據(jù)定理3,正域更新為POS0.6(C,Ua)(D)={x1,x3,x5}∪{y1,y2,y3}-{x5}-{y1}={x1,x3,y2,y3}。

3.2 區(qū)間值決策表的正域組增量屬性約簡算法

單增量約簡方法每次只更新一個對象增加后的約簡結(jié)果,而組增量約簡方法將新增對象集視為一個整體,然后更新初始約簡結(jié)果。下面給出區(qū)間值決策表的正域組增量屬性約簡算法(Group Incremental Attribute Reduction algorithm based on positive region in interval-valued decision tables,GIAR)。

算法3? 區(qū)間值決策表的正域組增量屬性約簡算法(GIAR)。

輸入? 區(qū)間值決策表DT=(U,C∪D,V, f),初始約簡結(jié)果B0,初始正域POSαC(D),新增對象集U1。

輸出? 論域Ua上的約簡結(jié)果Red。

步驟1? 令B←B0,Ua←U∪U1。

步驟2 ?分別計算Ua在屬性集B和C上的正域POSα(B,Ua)(D)和POSα(C,Ua)(D)。若POSα(B,Ua)(D)=POSα(C,Ua)(D),

轉(zhuǎn)至步驟4;否則,轉(zhuǎn)至步驟3。

步驟3? 若POSα(B,Ua)(D)≠POSα(C,Ua)(D),重復:

步驟3.1 ?對所有屬性ak∈C-B,計算sigouterUa(ak,B,D);

步驟3.2 ?選取ai=arg max{sigouterUa(ak,B,D)},令B←B∪{ai}。

步驟4 ?對b∈B,計算siginnerUa(b,B,D)= | POSα(B,Ua)(D)-POSα(B-,Ua)(D) | ,若siginnerUa(b,B,D)=0,令B←B-。

步驟5? Red←B,返回Red。

對于對象集增加的區(qū)間值決策表,根據(jù)定理3更新正域,更新正域的時間復雜度是O( | U1 | ?| U | ?| C | +∑ |X| l=1 ?| SαC(xl) | ),其中X表示C在U和U1上形成的具有相容關系的對象集合。為表示簡潔,令Φ2=∑ |X| l=1 ?| SαC(xl) | 。計算外部屬性重要度的時間復雜度是O( | C-B | ( | U | ?| U1 | ?| C | +Φ2)),選取屬性添加到初始約簡的時間復雜度為O( | C-B | ( | U | ?| U1 | ?| C | +Φ2)),刪除冗余屬性的時間復雜度是O( | B | ( | U | ?| U1 | ?| C | +Φ2))。所以算法3整體的時間復雜度是O( | C | ( | U | ?| U1 | ?| C | +Φ2))。

例6? 區(qū)間值決策表DT=(U,C∪D,V, f)如表1所示,論域U={x1,x2,x3,x4,x5,x6}。新增對象集如表3所示,論域U1={y1,y2,y3}。計算U1增加到DT后的一個約簡。

由例1得初始正域POS0.6C(D)={x1,x3,x5},由例2得初始約簡結(jié)果B={a1,a3}。

對象集增加后論域更新為Ua=U∪U1,計算論域Ua在屬性子集B下的正域POSα(B,Ua)(D)={x3,y2,y3},論域Ua在屬性集C下的正域POSα(C,Ua)(D)={x1,x3,y2,y3}。由于POSα(B,Ua)(D)≠POSα(C,Ua)(D),從剩余屬性集{a2,a4}中選擇外部重要度最大的屬性a4,滿足POSα(B∪{a4},Ua)(D)=POSα(C,Ua)(D),因此B=B∪{a4}={a1,a3,a4}。通過計算a3為冗余屬性,刪除冗余屬性后的約簡結(jié)果Red={a1,a4}。

4 實驗結(jié)果及分析

實驗選取區(qū)間值決策表中基于信息熵的屬性約簡算法[31]與本文所提算法進行比較,為方便表示,將文獻[31]中的算法記為CEAR。本章實驗分為兩部分:第一部分比較單增量算法SIAR、組增量算法GIAR、非增量算法CAR與算法CEAR的約簡結(jié)果;第二部分比較算法SIAR、GIAR、CAR與CEAR的約簡效率。

實驗環(huán)境:操作系統(tǒng)Windows 7;處理器Intel Corei5-6500;內(nèi)存8.00GB;程序運行環(huán)境python3.6;采用PyCharm編碼。實驗選取8組UCI數(shù)據(jù)集,數(shù)據(jù)集描述如表4所示。實驗使用WEKA3.6對數(shù)據(jù)進行預處理,對于屬性缺失值,取該屬性下比重最大的屬性值,使用等頻分割方法[32]處理連續(xù)型的數(shù)據(jù),用整數(shù)代替名詞性數(shù)據(jù)。由于實驗數(shù)據(jù)采用區(qū)間型數(shù)據(jù),文獻[32]已給出單值數(shù)據(jù)轉(zhuǎn)化為區(qū)間型數(shù)據(jù)的方法,閾值ω用于調(diào)節(jié)區(qū)間值長度,取ω=2.4。

4.1 約簡結(jié)果比較

本節(jié)通過實驗比較單增量算法SIAR、組增量算法GIAR、非增量算法CAR與算法CEAR的約簡結(jié)果。實驗中,令閾值ω=2.4,相似率閾值α=0.8。對表4中每個UCI數(shù)據(jù)集,選取60%的對象作為基礎對象集,剩余40%作為新增對象集,當新增對象集增加到基礎對象集后,分別利用算法SIAR、GIAR、CAR和CEAR計算約簡結(jié)果。四種算法的約簡結(jié)果比較如表5所示。

集合1={1,2,3,4,5,6,8,10,12,16,17,18,19},集合 2={2,3,4,5,6,7,8,10,12,16,17,18,19},集合3={1,2,3,4,5, 6,8,10,12,16,17,18,19},集合4={1,2,3,4,5,6,8,10,12,16,17,18,19},集合5={1,2,3,4,6,7,9,10,12,13,14,15,17,20,21,22},集合6={1,2,4,7,8,9,10,12,13,14,15,17,19,20,21,22},集合7={1,2,3,4,5,7,9,10,12,13,14,16,17,20,21,22},集合8={1,2,3,4,5,7,9,10,12,13,14,16,17,20,21,22},集合9={1,2,3,4,5,6,9,11,13,15,16,18},集合10={1,2,3,4,5,6,7,11,14,15,16,18},集合11={1,2,3,4,5,6,7,11,14,15,16,18},集合12={1,2,3,4,5,6,9,11,13,15,16,18},集合13={1,2,3,4,5,7,8,9,12,13,14},集合14={1,2,3,5,6,7,8,9,12,13,14},集合15={1,2,3,4,5,7,8,9,12,13,14},集合16={1,2,3,4,5,7,8,9,12,13,14}。

表5中實驗結(jié)果表明,增量算法SIAR、GIAR與非增量算法CAR的約簡結(jié)果可能不同,但三個算法的約簡結(jié)果不僅保持了相同的正域,而且不存在冗余屬性,即算法SIAR、GIAR所得約簡均為正確約簡結(jié)果,存在差異的原因是啟發(fā)式約簡算法執(zhí)行一次只能獲得一個約簡結(jié)果。由表5可知,單增量算法SIAR和組增量算法GIAR的約簡結(jié)果可能不同,例如:編號為7的數(shù)據(jù)集,單增量算法SIAR的約簡結(jié)果為{1,2,3,5,6,7,8,9,12,13,14},組增量算法GIAR的約簡結(jié)果為{1,2,3,4,5,7,8,9,12,13,14}。導致約簡結(jié)果不同的可能原因:一是由于約簡過程中屬性的添加順序不同,導致刪除的冗余屬性不同。例如:若存在兩個屬性都為冗余屬性,則優(yōu)先刪除兩者中位于前面的屬性,因此所得約簡結(jié)果不同。二是由于單增量算法SIAR和組增量算法GIAR更新約簡結(jié)果的方式不同,算法SIAR執(zhí)行一次只能獲得單個對象增加后的約簡結(jié)果,而算法GIAR將對象集視為整體更新約簡結(jié)果。由表5中算法CAR、SIAR、GIAR、CEAR的約簡長度可以看出,增量算法SIAR和GIAR可以有效去掉冗余屬性,對于8組UCI數(shù)據(jù)集,增量算法SIAR、GIAR和非增量算法CAR所得約簡結(jié)果的長度相同。

4.2 約簡效率比較

本節(jié)通過實驗比較算法CAR、SIAR、GIAR和CEAR的約簡效率,驗證組增量算法GIAR的高效性。對表4中每個UCI數(shù)據(jù)集,取60%的對象作為基礎對象集,剩余40%分為8等份,每份表示為xi(i=1,2,…,8),Xi= ∪ ?i j=1 xi(i=1,2,…,8)為實驗中每次新增的對象集,例如:第1次新增對象集X1=x1,第2次新增對象集X2=x1∪x2,以此類推,第8次新增對象集X8=x1∪x2∪…∪x8。令相似率閾值α=0.8,分別將X1,X2,…,X8增加到基礎對象集后,采用算法CAR、SIAR、GIAR和CEAR計算約簡。圖1給出了算法CAR、SIAR、GIAR和CEAR計算約簡的時間對比,其中x軸表示不同規(guī)模的新增對象集,數(shù)值1,2,…,8分別表示將對象集X1,X2,…,X8增加到基礎對象集,y軸表示計算約簡的時間耗費。

圖1中的實驗結(jié)果表明,當不同規(guī)模的對象集增加到基礎對象集后,組增量算法GIAR的約簡效率優(yōu)于單增量算法SIAR,單增量算法SIAR的約簡效率優(yōu)于非增量算法CAR。增量算法SIAR和GIAR比非增量算法CAR的約簡效率高,原因是對象集每次動態(tài)增加時,非增量算法CAR要重新計算約簡,而增量算法SIAR和GIAR在初始約簡的基礎上獲得更新后區(qū)間值決策表的約簡結(jié)果,因此提高了約簡效率。單增量算法SIAR和組增量算法GIAR相比,算法GIAR計算約簡的時間少于算法SIAR,原因是算法GIAR將新增對象集視為整體,更新一次可得約簡結(jié)果,而算法SIAR每次只增加一個對象,要重復更新求解約簡。算法CEAR與組增量算法GIAR相比,算法GIAR計算約簡的時間遠遠少于算法CEAR。而且在大多數(shù)的數(shù)據(jù)集中,隨著新增對象集規(guī)模不斷增大,算法GIAR的高效性更明顯。因此,實驗結(jié)果表明了算法GIAR的高效性。

5 結(jié)語

針對區(qū)間值決策表中對象集動態(tài)增加的情況,本文分析了單增量和組增量的正域更新機制,提出了區(qū)間值決策表的正域單增量和組增量屬性約簡算法。實驗選取8組UCI數(shù)據(jù)集,分別運用非增量、單增量和組增量的正域?qū)傩约s簡算法和算法CEAR計算約簡,實驗結(jié)果驗證了增量算法的高效性。本文主要針對對象集的動態(tài)增加分析了增量式屬性約簡,下一步將針對屬性集的動態(tài)增加和屬性值的動態(tài)改變進行增量式屬性約簡的研究。

參考文獻

[1]?PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356.

[2]?王國胤,姚一豫,于洪.粗糙集理論與應用研究綜述[J].計算機學報,2009,32(7):1229-1246. (WANG G Y, YAO Y Y, YU H. A survey on rough set theory and applications [J]. Chinese Journal of Computers, 2009, 32(7): 1229-1246.)

[3]?LI D, ZHANG B, LEUNG Y. On knowledge reduction in inconsistent decision information systems [J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2004, 12(5): 651-672.

[4]?QIAN Y, LIANG J, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory [J]. Artificial Intelligence, 2010, 174(9/10): 597-618.

[5]?苗奪謙,胡桂榮.知識約簡的一種啟發(fā)式算法[J].計算機研究與發(fā)展,1999,36(6):681-684. (MIAO D Q, HU G R. A heuristic algorithm for reduction of knowledge [J]. Journal of Computer Research and Development, 1999, 36(6): 681-684.)

[6]?XU W, LI Y, LIAO X. Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems [J]. Knowledge-Based Systems, 2012, 27: 78-91.

[7]?MIN F, HE H, QIAN Y, et al. Test-cost-sensitive attribute reduction [J]. Information Sciences, 2011, 181(22): 4928-4942.

[8]??HU X, CERCONE N. Learning in relational databases: a rough set approach [J]. International Journal of Computational Intelligence, 1995, 11(2): 323-338.

[9]?QIAN Y, LIANG X, WANG Q, et al. Local rough set: a solution to rough data analysis in big data [J]. International Journal of Approximate Reasoning, 2018, 97: 38-63.

[10]?JIA X, LIAO W, TANG Z, et al. Minimum cost attribute reduction in decision-theoretic rough set models [J]. Information Sciences, 2013, 219: 151-167.

[11]?LEUNG Y, FISCHER M M, WU W-Z, et al. A rough set approach for the discovery of classification rules in interval-valued information systems [J]. International Journal of Approximate Reasoning, 2008, 47(2): 233-246.

[12]?張楠,苗奪謙,岳曉冬.區(qū)間值信息系統(tǒng)的知識約簡[J].計算機研究與發(fā)展,2010,47(8):1362-1371. (ZHANG N, MIAO D Q, YUE X D. Approaches to knowledge reduction in interval-valued information systems [J]. Journal of Computer Research and Development, 2010, 47(8): 1362-1371.)

[13]?劉鵬惠,陳子春,秦克云.區(qū)間值信息系統(tǒng)的決策屬性約簡[J].計算機工程與應用,2009,45(28):148-151. (LIU P H, CHEN Z C, QIN K Y. Decision attribute reduction of interval-valued information system [J]. Computer Engineering and Applications, 2009, 45(28): 148-151.)

[14]?徐菲菲,雷景生,畢忠勤,等.大數(shù)據(jù)環(huán)境下多決策表的區(qū)間值全局近似約簡[J].軟件學報,2014,25(9):2119-2135. (XU F F, LEI J S, BI Z Q, et al. Approaches to approximate reduction with interval-valued multi-decision tables in big data [J]. Journal of Software, 2014, 25(9): 2119-2135.)

[15]?DAI J, WANG W, XU Q, et al. Uncertainty measurement for interval-valued decision systems based on extended conditional entropy [J]. Knowledge-Based Systems, 2012, 27: 443-450.

[16]?SHU W, QIAN W, XIE Y. Incremental approaches for feature selection from dynamic data with the variation of multiple objects [J]. Knowledge-Based Systems, 2019, 163: 320-331.

[17]?JING Y, LI T, FUJITA H, et al. An incremental attribute reduction method for dynamic data mining [J]. Information Sciences, 2018, 465: 202-218.

[18]?WEI W, WU X, LIANG J, et al. Discernibility matrix based incremental attribute reduction for dynamic data [J]. Knowledge-Based Systems, 2018, 140: 142-157.

[19]?XIE X, QIN X. A novel incremental attribute reduction approach for dynamic incomplete decision systems [J]. International Journal of Approximate Reasoning, 2018, 93: 443-462.

[20]?HU F, WANG G Y, HUANG H, et al. Incremental attribute reduction based on elementary sets [C]// Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, LNCS 3641. Berlin: Springer, 2005: 185-193.

[21]?XU Y, WANG L, ZHANG R. A dynamic attribute reduction algorithm based on 0-1 integer programming [J]. Knowledge-Based Systems, 2011, 24(8): 1341-1347.

[22]?楊明.一種基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機學報,2007,30(5):815-822. (YANG M. An incremental updating algorithm for attribute reduction based on improved discernibility matrix [J]. Chinese Journal of Computers, 2007, 30(5): 815-822.)

[23]?LIANG J, WANG F, DANG C, et al. A group incremental approach to feature selection applying rough set technique [J]. IEEE Transactions on Knowlede and Data Engineering, 2014, 26(2): 294-308.

[24]?SHU W, QIAN W. An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory [J]. Data and Knowledge Engineering, 2015, 100(Part A): 116-132.

[25]?YU J, XU W. Incremental knowledge discovering in interval-valued decision information system with the dynamic data [J]. International Journal of Machine Learning and Cybernetics, 2017, 8(3): 849-864.

[26]?WANG F, LIANG J, QIAN Y. Attribute reduction: a dimension incremental strategy [J]. Knowledge-Based Systems, 2013, 39: 95-108.

[27]?LIU D, LI T, ZHANG J. Incremental updating approximations in probabilistic rough sets under the variation of attributes [J]. Knowledge-Based Systems, 2015, 73: 81-96.

[28]?CHENG Y. The incremental method for fast computing the rough fuzzy approximations [J]. Data and Knowledge Engineering, 2011, 70(1): 84-100.

[29]?CHEN H, LI T, QIAO S, et al. A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values [J]. International Journal of Intelligent Systems, 2010, 25(10): 1005-1026.

[30]?張楠,許鑫,童向榮,等.不協(xié)調(diào)區(qū)間值決策系統(tǒng)的知識約簡[J].小型微型計算機系統(tǒng),2017,38(7):1585-1589. (ZHANG N, XU X, TONG X R, et al. Knowledge reduction in inconsistent interval-valued decision systems [J]. Journal of Chinese Computer Systems, 2017, 38(7): 1585-1589.)

[31]?DAI J-H, HU H, ZHENG G-J, et al. Attribute reduction in interval-valued information systems based on information entropies [J]. Frontiers of Information Technology and Electronic Engineering, 2016, 17(9): 919-928.

[32]?ZHANG X, MEI C, CHEN D, et al. Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems [J]. International Journal of Approximate Reasoning, 2014, 55(8): 1787-1804.

猜你喜歡
粗糙集
基于粗糙集指標約簡和云模型的供應鏈金融風險評價
基于屬性重要度規(guī)則提取算法的高校教學質(zhì)量評價研究
基于粗集決策規(guī)則性質(zhì)的研究
一種基于改進的層次分析法的教師教學質(zhì)量評價模型
一種改進的ROUSTIDA數(shù)據(jù)填補方法
不確定性數(shù)學方法的比較研究
一種基于數(shù)組的高效等價類劃分算法
模糊軟集合與軟粗糙集模型研究
“高職學生”視角下教師課堂教學質(zhì)量學生評價探析
基于知識依賴度約簡的知識發(fā)現(xiàn)研究