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

鮑迪 張楠 童向榮 岳曉冬

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

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

中圖分類號(hào)：?TP181

文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

定義2 [30] 給定兩個(gè)區(qū)間值λ1=[lki，uki]和λ2=[lkj，ukj]，區(qū)間值的交、并運(yùn)算定義如下：

λ1∩λ2=

0，???? （uki

[max（lki，lkj），min（uki，ukj）]， 其他? ??（1）

λ1∪λ2=[min（lki，lkj），max（uki，ukj）]

（2）

區(qū)間值交、并運(yùn)算的介紹，為描述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ū)間長(zhǎng)度。αkij值越大，對(duì)象xi和xj關(guān)于屬性ak的相似度越高。

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

TRαP={（xi，xj） | （xi，xj）∈U×U，αkij>α，ak∈P}

（4）

α-相容關(guān)系具有以下性質(zhì)：

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

性質(zhì)2 [12] 設(shè)區(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下定義對(duì)象xi的α-相容類為：

SαP（xi）={xj | xj∈U，（xi，xj）∈TRαP}

（5）

所有SαP（xi）（xi∈U）的集合形成對(duì)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]，對(duì)象xi的相容類為SαP（xi），定義X關(guān)于屬性子集P的上、下近似分別為：

aprαP （X）={xi | xi∈U，SαP（xi）∩X≠}

（6）

aprαP （X）={xi | xi∈U，SαP（xi）X}

（7）

X關(guān)于P的正域、邊界域和負(fù)域分別定義為：

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）對(duì) 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的相容類中所有對(duì)象的決策值唯一。

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

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

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

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

根據(jù)表1計(jì)算布爾相似矩陣 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關(guān)于C的正域?yàn)镻OS0.6C（D）={x1，x3，x5}。

定義9 [14] 設(shè)區(qū)間值決策表DT=（U，C∪D，V， f），PC，若P是DT的一個(gè)約簡(jiǎn)，則需滿足以下兩個(gè)條件：

1）POSαP（D）=POSαC（D）;

2）P′P，滿足POSαP′（D）≠POSαP（D）。

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

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

通過例1計(jì)算正域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}中無冗余屬性，因此{(lán)a1，a3}是一個(gè)約簡(jiǎn)。

定義10 [14] 設(shè)區(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是可去屬性。在屬性約簡(jiǎn)過程中，內(nèi)部重要度用于計(jì)算核屬性或刪除屬性集中的冗余屬性。

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

sigouter（a，P，D）= | POSαP∪{a}（D）-POSαP（D） |

（14）

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

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

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

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

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

步驟1? 令Red←;

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

步驟3? 若POSαRed（D）≠POSαC（D），重復(fù)：

步驟3.1 ?對(duì)所有屬性aj∈C-Red，計(jì)算sigouter（aj，Red，D）;

步驟3.2 ?選取ak=arg max{sigouter（aj，Red，D）}，令Red←Red∪{ak};

步驟4? 對(duì)b∈Red，計(jì)算siginner（b，Red，D），若siginner（b，Red，D）=0，令Red←Red-;

步驟5? 返回Red。

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

2 單增量屬性約簡(jiǎn)

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

2.1 單增量的正域更新機(jī)制

屬性約簡(jiǎn)過程中，若使用非增量方法更新正域，會(huì)導(dǎo)致正域的計(jì)算效率低。為了提高正域的計(jì)算效率，可采用增量方法更新正域，下面介紹單個(gè)對(duì)象增加后的正域更新機(jī)制。

定理1? 設(shè)區(qū)間值決策表DT=（U，C∪D，V， f），任意屬性子集PC，增加對(duì)象x后更新論域?yàn)閁′=U∪{x}，POSαP（D）為論域U在屬性子集P下的初始正域，Sα（P，U′）（x）為論域U′中對(duì)象x的相容類，[x]D為x所在決策類中的對(duì)象集合，論域U′在屬性子集P下更新正域?yàn)椋?/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）中所有對(duì)象的決策屬性值相同;反之，則表示相容類Sα（P，U′）（y）中對(duì)象的決策屬性值存在差異。

證明

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

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，對(duì)于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所示，新增對(duì)象x如表2所示，更新論域U′=U∪{x}，令相似率閾值α=0.6，計(jì)算區(qū)間值決策表DT′=（U′，C∪D，V， f）的正域POS0.6（C，U′）（D）。

由例1計(jì)算初始正域POS0.6C（D）={x1，x3，x5}。計(jì)算對(duì)象x關(guān)于論域U′的相容類S0.6（C，U′）（x）={x5，x}，對(duì)象x5關(guān)于論域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ū)間值決策表的正域單增量屬性約簡(jiǎn)算法

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

給定區(qū)間值決策表DT=（U，C∪D，V， f），相似率閾值α∈[0，1]，初始約簡(jiǎn)結(jié)果B，新增對(duì)象x，更新后的區(qū)間值決策表DT′=（U′，C∪D，V， f），其中U′=U∪{x}。對(duì)象x關(guān)于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）時(shí)，區(qū)間值決策表DT′的約簡(jiǎn)結(jié)果依然是初始約簡(jiǎn)結(jié)果。

定理2? 若滿足 | Sα（C，U′）（x）/IND（D） | =1且 | Sα（B，U′）（x）/IND（D） | =1，則初始約簡(jiǎn)結(jié)果B是區(qū)間值決策表DT′的約簡(jiǎn)結(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}。又因?yàn)锽是初始約簡(jiǎn)結(jié)果，POSαB（D）=POSαC（D），所以POSα（C，U′）（D）=POSα（B，U′）（D）。由定義9可知，對(duì)于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ǎn)結(jié)果B是區(qū)間值決策表DT′的約簡(jiǎn)結(jié)果。

證畢。

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

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

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

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

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

步驟2? 計(jì)算相容類Sα（C，U′）（x）。

步驟3? 計(jì)算相容類Sα（B，U′）（x）。

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

步驟5? 若POSα（B，U′）（D）≠POSα（C，U′）（D），重復(fù)：

步驟5.1? 對(duì)所有屬性ak∈C-B，計(jì)算sigouterU′（ak，B，D）;

步驟5.2? 選取ai=arg max{sigouterU′（ai，B，D）}，令B←B∪{ai}。

步驟6? 對(duì)b∈B，計(jì)算siginnerU′（b，B，D）= | POSα（B，U′）（D）-POSα（B-，U′）（D） | ，若siginnerU′（b，B，D）=0，令B←B-。

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

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

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

由例2得初始約簡(jiǎn)結(jié)果B={a1，a3}，由例3得正域POS0.6（C，U′）（D）={x1，x3}。計(jì)算對(duì)象x在條件屬性集C下的相容類S0.6（C，U′）（x）={x5，x}，對(duì)象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，故應(yīng)更新初始約簡(jiǎn)結(jié)果。通過計(jì)算得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ǎn)結(jié)果Red={a1，a4}。

3 組增量屬性約簡(jiǎn)

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

3.1 組增量的正域更新機(jī)制

對(duì)象集的動(dòng)態(tài)增加可能導(dǎo)致正域發(fā)生改變，下面給出組增量的正域更新機(jī)制。

定理3? 設(shè)區(qū)間值決策表DT=（U，C∪D，V， f），論域U={x1，x2，…，xn}，任意條件屬性子集PC，TRαP對(duì)U的分類U/TRαP={SαP（x1），SαP（x2），…，SαP（xn）}，IND（D）對(duì)U的劃分U/IND（D）={D1，D2，…，Dm}，U在P下的初始正域?yàn)镻OSαP（D）。新增對(duì)象集U1={y1，y2，…，ys}，TRαP對(duì)U1的分類 U1/TRαP={SαP（y1），SαP（y2），…，SαP（ys）}，IND（D）對(duì)U1的劃分U1/IND（D）={T1，T2，…，Tm′}。論域Ua=U∪U1，Ua在屬性子集P下更新正域?yàn)椋篜OSα（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上形成的具有相容關(guān)系的對(duì)象集合，X={xi∈POSαP（D），yj∈POSα（P，U1）（D） | （xi，yj）∈TRαP}。

證明

為表示簡(jiǎn)潔，令SαP′（xi）=Sα（P，Ua）′（xi）， SαP′（yj）=Sα（P，Ua）′（yj）。 假設(shè)在分類U/TRαP和U1/TRαP中， 存在一些對(duì)象在屬性集P下形成相容關(guān)系， 相容關(guān)系TRαP對(duì)論域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ā)生變化的相容類個(gè)數(shù)， u′∈[1， h]， h為論域U1中發(fā)生變化的相容類個(gè)數(shù)。SαP′（xi）和SαP′（yj）表示變化的相容類，其中i∈[1，u]， j∈[1，u′]，對(duì)于yj∈U1，若yj∈SαP（xi），則SαP′（xi）=SαP（xi）∪{yj}，由相容關(guān)系的對(duì)稱性可得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）對(duì)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′]）。

通過合并化簡(jiǎn)可得正域：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所示，新增對(duì)象集U1={y1，y2，y3}如表3所示。更新論域Ua=U∪U1，令相似率閾值α=0.6，計(jì)算論域Ua在屬性集C下的正域POS0.6（C，Ua）（D）。

由例1得初始正域POS0.6C（D）={x1，x3，x5}，計(jì)算U1在C下的正域POS0.6（C，U1）（D）={y1，y2，y3}。對(duì)象集增加后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ǎn)算法

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

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

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

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

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

步驟2 ?分別計(jì)算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），重復(fù)：

步驟3.1 ?對(duì)所有屬性ak∈C-B，計(jì)算sigouterUa（ak，B，D）;

步驟3.2 ?選取ai=arg max{sigouterUa（ak，B，D）}，令B←B∪{ai}。

步驟4 ?對(duì)b∈B，計(jì)算siginnerUa（b，B，D）= | POSα（B，Ua）（D）-POSα（B-，Ua）（D） | ，若siginnerUa（b，B，D）=0，令B←B-。

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

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

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

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

對(duì)象集增加后論域更新為Ua=U∪U1，計(jì)算論域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}。通過計(jì)算a3為冗余屬性，刪除冗余屬性后的約簡(jiǎn)結(jié)果Red={a1，a4}。

4 實(shí)驗(yàn)結(jié)果及分析

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

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

4.1 約簡(jiǎn)結(jié)果比較

本節(jié)通過實(shí)驗(yàn)比較單增量算法SIAR、組增量算法GIAR、非增量算法CAR與算法CEAR的約簡(jiǎn)結(jié)果。實(shí)驗(yàn)中，令閾值ω=2.4，相似率閾值α=0.8。對(duì)表4中每個(gè)UCI數(shù)據(jù)集，選取60%的對(duì)象作為基礎(chǔ)對(duì)象集，剩余40%作為新增對(duì)象集，當(dāng)新增對(duì)象集增加到基礎(chǔ)對(duì)象集后，分別利用算法SIAR、GIAR、CAR和CEAR計(jì)算約簡(jiǎn)結(jié)果。四種算法的約簡(jiǎn)結(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中實(shí)驗(yàn)結(jié)果表明，增量算法SIAR、GIAR與非增量算法CAR的約簡(jiǎn)結(jié)果可能不同，但三個(gè)算法的約簡(jiǎn)結(jié)果不僅保持了相同的正域，而且不存在冗余屬性，即算法SIAR、GIAR所得約簡(jiǎn)均為正確約簡(jiǎn)結(jié)果，存在差異的原因是啟發(fā)式約簡(jiǎn)算法執(zhí)行一次只能獲得一個(gè)約簡(jiǎn)結(jié)果。由表5可知，單增量算法SIAR和組增量算法GIAR的約簡(jiǎn)結(jié)果可能不同，例如：編號(hào)為7的數(shù)據(jù)集，單增量算法SIAR的約簡(jiǎn)結(jié)果為{1，2，3，5，6，7，8，9，12，13，14}，組增量算法GIAR的約簡(jiǎn)結(jié)果為{1，2，3，4，5，7，8，9，12，13，14}。導(dǎo)致約簡(jiǎn)結(jié)果不同的可能原因：一是由于約簡(jiǎn)過程中屬性的添加順序不同，導(dǎo)致刪除的冗余屬性不同。例如：若存在兩個(gè)屬性都為冗余屬性，則優(yōu)先刪除兩者中位于前面的屬性，因此所得約簡(jiǎn)結(jié)果不同。二是由于單增量算法SIAR和組增量算法GIAR更新約簡(jiǎn)結(jié)果的方式不同，算法SIAR執(zhí)行一次只能獲得單個(gè)對(duì)象增加后的約簡(jiǎn)結(jié)果，而算法GIAR將對(duì)象集視為整體更新約簡(jiǎn)結(jié)果。由表5中算法CAR、SIAR、GIAR、CEAR的約簡(jiǎn)長(zhǎng)度可以看出，增量算法SIAR和GIAR可以有效去掉冗余屬性，對(duì)于8組UCI數(shù)據(jù)集，增量算法SIAR、GIAR和非增量算法CAR所得約簡(jiǎn)結(jié)果的長(zhǎng)度相同。

4.2 約簡(jiǎn)效率比較

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

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

5 結(jié)語

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

參考文獻(xiàn)

[1]?PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

[2]?王國(guó)胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，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]?苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J].計(jì)算機(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)的知識(shí)約簡(jiǎn)[J].計(jì)算機(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)的決策屬性約簡(jiǎn)[J].計(jì)算機(jī)工程與應(yīng)用，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ū)間值全局近似約簡(jiǎn)[J].軟件學(xué)報(bào)，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ìn)差別矩陣的屬性約簡(jiǎn)增量式更新算法[J].計(jì)算機(jī)學(xué)報(bào)，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)的知識(shí)約簡(jiǎn)[J].小型微型計(jì)算機(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.