吳曉雪，李 艷

(1.河北大學 數(shù)學與信息科學學院,河北 保定 071002;2.北京師范大學 (珠海) 應用數(shù)學與交叉科學研究中心,廣東 珠海 519000)

傳統(tǒng)粗糙集[1-2]基于等價關系通過上下近似刻畫不精確概念,只能處理符號值屬性。很多后續(xù)研究引入不同的二元關系,如鄰域關系[3-7]、模糊關系[8]、容差關系[9]、優(yōu)勢關系[10]等,建立了相應的粗糙集模型,能夠處理更多的數(shù)據(jù)類型。其中,鄰域關系通過引入鄰域半徑直接處理連續(xù)值屬性。Hu等人將鄰域關系引入粗糙集,提出了鄰域粗糙集模型[3]；Wang等人提出了一種鄰域分辨指數(shù)來表示鄰域關系的分辨信息,引入信息熵的相關變體,設計了特征選擇算法[4]；Sun等人提出了一種新的基于勒貝格和鄰域粗糙集熵測度的屬性約簡方法,以有效地處理連續(xù)性數(shù)值問題[5]；Chen等人構造了一種基于變精度模糊鄰域粗糙集的多標簽屬性約簡方法,可處理多種類型的數(shù)據(jù)且能夠容忍噪聲影響[6]；Hu等人在鄰域關系中引入不同的權值,設計了一種貪婪搜索算法來選擇相關性較高的屬性子集[7]。

在實際應用中,數(shù)據(jù)通常隨時間的推移而變化。增量方法在數(shù)據(jù)對象和屬性發(fā)生任何變化時,可通過對已有信息的重用有效減少計算耗費,快速更新約簡。目前相關工作主要針對對象集(即樣本集)、屬性集、屬性值的變化[11-13]這3個方面進行研究。在鄰域關系粗糙集中,Hu等人提出了一種基于矩陣的鄰域多粒度粗糙近似表示方法和相應的動態(tài)約簡更新策略[14];Wang等人在有序信息系統(tǒng)中提出了一種優(yōu)勢特征矩陣獲取策略,避免了原始屬性之間的重復比較,從而在對象集和屬性集同時變化時高效地更新約簡[15]。對具有混合類型特征的動態(tài)數(shù)據(jù),Shu等人提出了一種基于鄰域熵的增量特征選擇算法,添加和刪除多個對象時可快速更新約簡[16]。

然而,現(xiàn)有增量方法一般使用全部的變化樣本參與增量計算,未考慮對象所攜帶的分布信息(樣本在特征空間所處的區(qū)域),其潛在假設是認為這些變化的樣本對更新約簡的影響是均等的,導致增量算法的耗費仍然會較大。實際上,數(shù)據(jù)集中各樣本對分類的重要程度往往是不同的,不確定性建模相關研究表明,樣本的不確定性大小會對分類性能產(chǎn)生重要影響[17-18]。而屬性約簡本質(zhì)是在保持數(shù)據(jù)分類能力的基礎上盡可能去除冗余屬性,因此，不同樣本對屬性約簡貢獻程度也會不同。

基于這個認識,很多工作通過樣本選擇來降低約簡的計算復雜度。如楊習貝等人在啟發(fā)式屬性約簡中使用K均值聚類算法對樣本進行選擇[19];Wang則提出了一種基于樣本抽取和優(yōu)先級的屬性約簡方法[20];Wang等人將樣本選擇的方法引入基于分辨矩陣的屬性約簡中,減少了參與約簡的樣本數(shù)量,在保證分類能力前提下明顯降低了算法的時間和空間耗費[21]。這些工作都認為處于邊界區(qū)域的樣本對屬性約簡有重要的影響，而邊界樣本往往具有較大的不確定性,因此，可考慮使用不確定性大小來體現(xiàn)樣本對約簡結(jié)果的重要程度。但是，這些研究只是在靜態(tài)的信息系統(tǒng)中進行屬性約簡,尚未考慮添加的樣本對動態(tài)信息系統(tǒng)約簡更新的影響。當樣本集發(fā)生變化時,增量算法只需要在原有約簡基礎上進行更新計算,不同于原始的約簡過程。本研究的主要思路是進一步考慮動態(tài)信息系統(tǒng)中所添加的樣本對約簡增量更新的影響,提出在增量算法之前加入一個樣本篩選的過程,從而只選擇貢獻程度較大的樣本參與增量計算。在鄰域粗糙集屬性約簡的增量方法中,目前尚未發(fā)現(xiàn)有結(jié)合樣本選擇的研究,本文在現(xiàn)有工作基礎上,基于不確定性度量對樣本進行刻畫和劃分,結(jié)合樣本選擇建立新的增量方法,進一步降低現(xiàn)有算法的計算代價。

本研究的主要工作為:第一,在鄰域關系粗糙集模型的增量約簡方法中考慮分布在不同區(qū)域的樣本對更新約簡的影響；第二,結(jié)合不確定性和分類器結(jié)果對樣本的重要性進行類型劃分,更準確地刻畫樣本對約簡結(jié)果的貢獻程度大??；第三,針對不同類型的樣本提出不同的更新策略,建立相應的約簡更新算法。本文為連續(xù)值信息系統(tǒng)提供了新的增量方法,可以在保持分類性能不變的情況下,進一步提高約簡的效率,同時對豐富不確定性理論也有著重要的意義。

1 鄰域關系粗糙集中的基本概念

定義1稱NIS=(U,A,V,f,ε)是一個鄰域信息系統(tǒng)[22],其中，U={x1,x2,…,xn}是非空的對象集,稱為論域;A={a1,a2,…,am}是非空的屬性集;V是所有屬性值的集合,即V=∪a∈AVa;f:U×A→V是信息函數(shù);ε是鄰域閾值參數(shù),以此來確定鄰域的大小。

若A=C∪D,其中C為條件屬性集合,D為決策屬性集合,則稱NDS=(U,C∪D,V,f,ε)為鄰域決策信息系統(tǒng)。

定義2[22]設鄰域決策信息系統(tǒng)為NDS=(U,C∪D,V,f,ε),xi∈U,B?C。在特征空間B中,xi的鄰域εB(xi)定義為

εB(xi)={xj|xj∈U,ΔB(xi,xj)≤ε)}。

(1)

其中，Δ是距離函數(shù)，使用鄰域便于處理連續(xù)值屬性。

(2)

(3)

定義4[22]基于定義3中的上下近似,論域U被劃分為3個區(qū)域,分別為正域POSB(X)、邊界域BNDB(X)和負域NEGB(X),定義為

(4)

(5)

(6)

定義5[22]給定鄰域決策信息系統(tǒng)NDS，對于?B?C,若滿足以下條件,則稱屬性集B為屬性集C的屬性約簡，

POSB(D)=POSC(D)，

(7)

?a∈B,滿足POSB-{a}(D)≠POSC(D)。

(8)

2 基于鄰域關系粗糙集和樣本不確定性的增量屬性約簡方法

2.1 樣本不確定性與屬性約簡之間關系的初步分析

決策系統(tǒng)中處于邊界域的樣本攜帶較大不確定性(不一致度),一般會降低決策系統(tǒng)分類能力。已有研究也表明數(shù)據(jù)本身的不確定性會顯著影響分類器的泛化性能[23-24]。而屬性約簡本質(zhì)是在保持數(shù)據(jù)本身的分類能力的前提下最大程度去除冗余屬性,因此,我們認為在一個信息系統(tǒng)中增加不確定性大的樣本對約簡結(jié)果也會有重要的影響。本節(jié)通過在人工數(shù)據(jù)集上的實驗對此做初步驗證。

前期研究發(fā)現(xiàn)數(shù)據(jù)的樣本不一致度、邊界復雜性和分類器輸出不確定性有著很強的相關性[25]。因此，可采用模糊k近鄰分類器(FKNN)的輸出不確定性衡量樣本的不確定性大小(見定義10)。樣本的輸出向量中每個分量為該樣本屬于每個類的隸屬程度，易知,隸屬于每個類的程度越接近,不確定性越大,越不容易分辨該樣本的類別(即易被分錯)，這樣的樣本大多數(shù)處于類別的邊界區(qū)域。在動態(tài)決策系統(tǒng)中,若這種不確定性大的樣本被加入或刪除,原決策表的分類能力容易發(fā)生變化。因此，在約簡的更新計算中,不能忽略變化的對象集中不確定性大的樣本。相反,樣本的輸出不確定性越小,說明該樣本越容易通過其他樣本確定其所屬類別,當此類樣本發(fā)生變化時,對分類性能影響較小。另一方面,易被分錯的樣本一般處于樣本分布比較復雜的區(qū)域,或者是噪音樣本,其對約簡更新也可能有重要的影響。

接下來針對分布在不同區(qū)域的樣本對屬性約簡的影響進行初步的實驗分析。采用人工生成高斯分布的數(shù)據(jù)集,包含300個20維的樣本,類別為3類,鄰域半徑設為0.1。基于HANDI算法[4]計算得原始約簡集為{1,4,8},其中，數(shù)字為屬性的序號。通過在數(shù)據(jù)集上添加若干不同區(qū)域的樣本構成動態(tài)信息系統(tǒng),重新計算約簡觀察不同樣本對約簡的影響。圖1中實心三角代表的樣本是在原始數(shù)據(jù)集中新增加的樣本,樣本的3種顏色代表它們的標簽類別。

根據(jù)加入樣本所處區(qū)域和FKNN的分類結(jié)果，分3種情況來討論。圖1A中新加入的樣本分布在靠近同類類簇中心的密集區(qū)域，或者處于同類簇稀疏區(qū)域但遠離其他異類簇,出現(xiàn)概率大,該區(qū)域的樣本往往不確定性小且被正確分類,稱為第1類樣本。加入后在新的數(shù)據(jù)集上重新計算約簡,發(fā)現(xiàn)結(jié)果保持原始約簡{1,4,8}不變,說明此類樣本對約簡更新的貢獻較小,若需要進一步降低計算耗費,此類樣本可以不參與約簡的更新。圖1B中新添加的樣本分布在類邊界區(qū)域或者分布在異類樣本的密集區(qū)域(可能為異常點或噪音),該區(qū)域的樣本特點是不確定小但容易被錯誤分類,稱為第2類樣本。加入后重新計算約簡,結(jié)果更新為{1,4,5,8}，說明處于該區(qū)域的樣本對約簡更新有一定的影響,為保持分類能力應參與約簡的更新過程,但此類樣本出現(xiàn)的概率一般很小。圖1C中新加入的樣本分布在類邊界區(qū)域,且不確定性較大,稱為第3類樣本。加入樣本后約簡結(jié)果更新為{1,3,8,10}，說明處于該區(qū)域的樣本對約簡更新有較大的影響,貢獻程度較大,應參與約簡的更新。

圖1 不同區(qū)域樣本對屬性約簡的影響結(jié)果

在隨機生成的數(shù)據(jù)集上進行反復實驗,從加入單樣本和多樣本兩個方面,進行了600輪約簡的更新計算,對添加樣本前后約簡的對比發(fā)現(xiàn)，在3種情況下均有類似結(jié)果,即第1類樣本對約簡影響最小,第2類和3類樣本影響較大,但第2類樣本出現(xiàn)的概率最小,總體影響低于第3類(不確定性大的樣本)。在這3類樣本中,一般第1類樣本出現(xiàn)的可能性最高,占的比重最大,如果在約簡更新中忽略此類樣本的影響,則應該能夠明顯降低更新代價。

2.2 相關概念和更新策略

2.2.1 相關概念 根據(jù)2.1節(jié)的分析和初步驗證,本文在文獻[4]中非增量算法的基礎上,建立基于不確定性和鄰域關系粗糙集的增量屬性約簡方法。

定義6在鄰域決策信息系統(tǒng)NDS=(U,C∪D,V,f,ε)中,樣本間的相似關系可以用矩陣來表示,相似矩陣表示為RB=(rij)n×n。

(9)

其中：xi和xj是U中的兩個樣本，記xl=[xl1,xl2,…，xls]T,l=i,j；B?C；ε是鄰域半徑,是控制樣本相似性的閾值。

使用鄰域分辨指數(shù)表示鄰域關系的分辨信息,并引入條件分辨指數(shù)等變體用于計算分辨信息的變化。它們與香農(nóng)熵及其變體有相似的性質(zhì)。

定義7[4]給定鄰域決策信息系統(tǒng)NDS，B?C，ε是鄰域半徑,RB表示屬性集B的鄰域相似矩陣。屬性B的鄰域分辨指數(shù)定義為

(10)

鄰域分辨指數(shù)用來衡量特征子集區(qū)分能力的不確定性,通過計算鄰域關系的基數(shù)直接得到,復雜度比香農(nóng)熵小。

(11)

其中，0≤Hε(B1|B2)≤logn；|*|表示集合或關系*的基數(shù)。

鄰域分辨指數(shù)用于衡量關系或?qū)傩约膮^(qū)分能力，屬性集的條件分辨指數(shù)越小,屬性集的分辨能力越強,屬性集的重要度越大。根據(jù)以上定義,通過在已有約簡結(jié)果的基礎上,進行屬性集的增加或減少,可以改變鄰域分辨指數(shù)的大小,通過計算之間的差值來進行屬性集重要度的判定。

定義9[4]設鄰域決策信息系統(tǒng)NDS=(U,A,V,f,ε),B?C,a∈C-B,關于B和D,屬性a的重要度定義為

SIG(a,B,D)=Hε(D|B)-Hε(D|B∪{a})。

(12)

屬性的重要度SIG越大,則越重要。集合C是條件屬性集,B?C,若屬性集B是約簡集,則滿足如下性質(zhì):

Hε(D|B)≤Hε(D|C)，

Hε(D|B-{a})>Hε(D|B)，?a∈B。

使用模糊k近鄰(FKNN)計算不確定性,好處是模糊k近鄰引入了類別隸屬度的概念,樣本不只屬于某一類,而是以一定比例隸屬于多個類別,比k近鄰更加準確。

定義10給定鄰域決策信息系統(tǒng)NDS,設有n個決策類。對任意U中樣本x,使用模糊k近鄰(FKNN)分類器對此樣本的輸出向量[u1,u2,…,un]計算不確定性，

(13)

其中ui∈[0,1],ui為樣本x對第i類的隸屬程度。易知,Uncerni∈[0,log2n]。

2.2.2 樣本劃分和更新策略 首先,在原始數(shù)據(jù)集上事先訓練FKNN和SVM分類器,使用FKNN輸出結(jié)果計算樣本不確定性(定義10),并設定區(qū)分不確定性大小的閾值。使用SVM分類器確定樣本分類的正確與否,將加入的樣本可粗略分為以下3類。

1)不確定性小且被正確分類的樣本。該類型的樣本大部分分布在類內(nèi)樣本密集區(qū)域,少部分分布在同類稀疏區(qū)域但離其他異類較遠,該類型樣本對屬性約簡的貢獻度較小,對約簡集的更新沒有影響或影響較小。

2)不確定性小且被錯誤分類的樣本。該類型的樣本一般是邊界點,極少數(shù)情況是噪音,分布在邊界區(qū)域,但周圍異類樣本點較多,該類型樣本對屬性約簡的貢獻度高于第一類樣本,對約簡集的更新影響也較大。

3)不確定性大的樣本。該類型的樣本一般屬于邊界樣本,對屬性約簡的貢獻度大,不管是被正確還是錯誤分類,都對約簡集的更新有不可忽視的影響。

針對不同類別的樣本,采取不同的策略。

1)對于第1類樣本,即不確定性小于閾值且被正確分類的樣本,忽略其對約簡的影響,不參與屬性約簡的更新。此類樣本占數(shù)據(jù)集大多數(shù),出現(xiàn)概率大,因此，可假設在動態(tài)變化的對象集中也占最大比例。

2)對于第2類樣本,即不確定性小且被錯誤分類的樣本,為保持系統(tǒng)分類能力考慮其影響，此類樣本參與屬性約簡的更新。

3)對于第3類樣本,即不確定性大的樣本,不能忽略其對分類和約簡的貢獻,應參與屬性約簡的更新。

2.3 增量算法步驟

根據(jù)2.2節(jié)的更新策略,對于加入的樣本,提出了基于不確定性和鄰域關系粗糙集的增量屬性約簡方法(incremental attribute reduction method based on uncertainty and neighborhood relation rough set,簡稱為IAUNR),算法如下。

輸出 新的約簡集red(U∪UX)。

樣本的篩選過程:在NDS中的約簡集redU上計算UX的不確定性大小和樣本分類正確與否,將其分為3種類型;若新增樣本UX全部屬于第1種類型,則直接加入原數(shù)據(jù)集中,不進行約簡的更新,轉(zhuǎn)到步驟20);否則,將屬于其他兩類的樣本保留,記為數(shù)據(jù)集X,用于約簡的更新,轉(zhuǎn)到步驟1)。

初始化:B=A-redU,start=1；

1) 計算H(U∪X)(D|C)和H(U∪X)(D|red)。判斷H(D|red)和H(D|C)的大小關系,若H(D|red)-H(D|C)≤δ,則轉(zhuǎn)至步驟20)，否則轉(zhuǎn)至步驟2)。

2)while start

3) for eachai∈B

5) 計算重要度

SIG(ai,red(U∪X),D)=

Hε(D|red(U∪X))-

Hε(D|red(U∪X))∪{ai});

6) end for

7) 找出最大SIG(akred(U∪X),D)對應的屬性ak

8) if SIG(ak,red(U∪X),D)>δ

9) red(U∪X)←red(U∪X)∪{ak};

10)B←B-red(U∪X)；

11) else

12) start=0;

13) end if

14) end while

∥檢查是否有冗余屬性

15) for eachai∈red(U∪X)

16) ifHε(D|red)-

Hε(D|red(U∪X)-{ai})≥δ

17) red(U∪X)←red(U∪X)-{ai}；

18) end

19) end

20) return red(U∪X)=red(U∪X)。

算法時間復雜度分析:IAUNR算法在其非增量算法的約簡集red的基礎上進一步考慮約簡更新,并使用貢獻度較大的樣本集進行約簡的更新。對于N維的樣本集,計算鄰域相似關系的時間復雜度為ΔN=C-red,最壞的時間復雜度為(ΔN+ΔN2)/2。

3 實驗結(jié)果與分析

為驗證此增量算法的有效性,使用UCI數(shù)據(jù)庫[26]中的11個數(shù)據(jù)集來評估算法,如表1所示。本節(jié)包含了5組實驗結(jié)果,分別為：①所提出增量算法IAUNR與非增量算法[4]的約簡時間比較;②IAUNR與現(xiàn)有4種增量算法的約簡時間比較;③IAUNR與非增量算法以及4種對比算法在分類精度上的比較;④5種增量方法約簡率的比較;⑤不確定性閾值對結(jié)果的影響分析。實驗中的所有算法在Matlab 2016b中執(zhí)行,并在Intel Core i5-10210U CPU和16GB RAM的硬件環(huán)境中運行。

表1 實驗數(shù)據(jù)集

參數(shù)鄰域半徑ε和δ的設置參見文獻[4]，ε通過調(diào)整參數(shù)的值從0到1,步長為0.05,為每一個數(shù)據(jù)集選擇一個最優(yōu)的特征子集;參數(shù)δ用于終止算法主循環(huán),需提前設置,通常來說,隨著參數(shù)δ值的減小,約簡數(shù)目應隨之增多,本文設置δ為0.001。在后面3.2節(jié)與現(xiàn)有相關增量方法的比較中,有關鄰域的實驗參數(shù)設置也按照以上方法。分類精度基于10次10倍交叉驗證,對訓練集進行屬性約簡,在約簡后的數(shù)據(jù)上訓練分類器得到精度,取每次精度的平均值作為最終結(jié)果。

3.1 與非增量算法的約簡時間比較

為了構造數(shù)據(jù)集對象增加的動態(tài)性,根據(jù)原始數(shù)據(jù)集中3類樣本的分布隨機產(chǎn)生符合該數(shù)據(jù)集分布的樣本集,每次生成該數(shù)據(jù)集總數(shù)的10%添加至原始數(shù)據(jù)集,進行了5次增量實驗,并在不同的數(shù)據(jù)集上與非增量算法進行比較。本文所提出的增量算法是基于鄰域分辨指數(shù)的啟發(fā)式算法(HANDI)。圖2展示了非增量算法和增量算法在9個數(shù)據(jù)集上的時間消耗的對比。由于Wpbc和wine數(shù)據(jù)集、 electrical和Segmentation數(shù)據(jù)集的增長趨勢相似,篇幅限制,省略了Wpbc和electrical數(shù)據(jù)集的折線圖。

從圖2可以看出，所提出的增量算法IAUNR在所使用的數(shù)據(jù)集上都明顯降低了非增量算法(HANDI)所消耗的時間,并且隨著增量數(shù)目的增多,差距越來越明顯。隨著樣本增多,IAUNR的時間增長趨勢比HANDI算法緩慢的多。不難理解,出現(xiàn)這個結(jié)果的原因是非增量算法在每次新增樣本集時,都要重新計算約簡集,而IAUNR充分利用了已有的約簡信息，不必重新從頭計算;另一個原因是IAUNR算法考慮了不同區(qū)域樣本對屬性約簡更新的貢獻程度,只選用貢獻程度大的樣本進行屬性約簡的更新,大大減少了樣本的規(guī)模,提高了約簡的效率。其中，wine、Credit、Segmentation、Wdbc、biodeg在增加越來越多的樣本時,時間耗費比較穩(wěn)定,說明加入樣本集之前的約簡形成的分類結(jié)果已達到了一個較高精度,加入的樣本集對現(xiàn)有的約簡結(jié)果影響不大,故約簡結(jié)果沒有發(fā)生變化,需要的計算量很小,僅需運行2.3節(jié)中算法的步驟1)。其他數(shù)據(jù)集隨增量次數(shù)的增多時間變化較大,取決于每次所增加的樣本對影響約簡更新的程度大小。

圖2 非增量算法和增量算法約簡時間比較

3.2 與現(xiàn)有增量方法的約簡時間比較

為了驗證本文所提增量算法的性能,選擇了4種相關增量算法進行比較,分別是一種分組增量特征選擇方法(GIARC)[27]、基于知識粒度的增量屬性約簡方法(IARC)[28]、基于鄰域?；瘲l件熵的增量式屬性約簡算法(IARNGCE)[29]、以及文獻[28]和[30]中鄰域關系知識粒度增量約簡算法的變體(NIARC)。GIARC和IARC算法是針對等價關系的增量方法,在使用之前,首先要用k均值聚類方法對數(shù)據(jù)進行離散化處理;NIARC算法是在IARC算法的基礎上引入鄰域的概念,用于處理連續(xù)性數(shù)值。以上增量算法中新增的樣本與3.1節(jié)中新增的樣本相同,進行了5次增量實驗,實驗結(jié)果取5次增量實驗時間消耗的平均值。由于數(shù)據(jù)集規(guī)模的大小不同,時間消耗存在較大差異,故將11個數(shù)據(jù)集分為3組進行結(jié)果對比(見圖3)。

圖3 IAUNR與現(xiàn)有增量方法的約簡時間比較

結(jié)果表明,本文所提的IAUNR算法在大部分數(shù)據(jù)集上的時間消耗較小,在4個數(shù)據(jù)集上所用時間最少,在7個數(shù)據(jù)集上接近最優(yōu),僅次于最少時間。IARC算法在7個數(shù)據(jù)集上的時間消耗最少,因為IARC是基于等價關系的, 只需對新增的樣本進行等價類的計算, 運行速度快, 但不能直接處理連續(xù)值數(shù)據(jù),同時， 離散化會丟失信息, 導致分類精度受到影響(見3.3節(jié)中分類精度的對比結(jié)果)。 其他3個算法的時間消耗相對較大, GIARC雖然是基于等價關系的增量算法,不需要考慮整個論域,但仍需要對增加的全部樣本進行處理,且計算較IARC復雜;IARNGCE算法采用分層的方法進行計算,不需要計算加入的樣本與其他全部樣本的距離,但仍需要考慮全部變化的樣本;NIARC算法是在IARC算法的基礎上引入鄰域的概念,也需對新增的全部樣本進行處理。而IAUNR算法只選用貢獻度較大的樣本進行屬性約簡的更新,而在一般情況下,貢獻度比較大的樣本處于邊界區(qū)域或者是異常點,出現(xiàn)的幾率小，大部分新增樣本在增量計算中被忽略,這樣就極大地減少了時間的消耗。注意到在較大數(shù)據(jù)集如Segmentation、electrical上,IAUNR的時間消耗也是較少的,只有在Musk數(shù)據(jù)集上IARNGCE和IARC接近,獲得了最快的約簡更新,可能的原因是所生成的新增樣本對該算法屬性約簡的影響較小,不需要大量的計算。總體來說，IAUNR算法在屬性約簡更新上的時間消耗有著優(yōu)越性。

3.3 分類精度比較

本節(jié)使用約簡后數(shù)據(jù)集上的分類精度體現(xiàn)和評估屬性約簡的質(zhì)量。對3.1節(jié)和3.2節(jié)中涉及的6個算法,可以基于某種分類器通過10倍交叉驗證計算得到對應的分類精度，這里選擇了SVM作為分類算法。一種非增量算法和5種增量算法的約簡后精度結(jié)果詳見表2。其中,每一列代表相應算法在各數(shù)據(jù)集上進行5次增量約簡后的平均分類精度,用均值±標準差的形式來表示,最后一行是各算法的總體平均精度。最優(yōu)精度加黑進行標注。

從表2可以看出,在11個數(shù)據(jù)集上以及6種算法中,IAUNR的平均精度是最高的,在8個數(shù)據(jù)集上均達到最優(yōu)分類精度,另外在biodeg和Sonar兩個數(shù)據(jù)集上表現(xiàn)次優(yōu),略低于最高精度。其次是NIARC算法,平均精度比IAUNR低約1%,但僅在1個數(shù)據(jù)集上取得最高精度。然后是IARNGCE算法,在2個數(shù)據(jù)集上達到最高精度,平均精度比IAUNR約低2%。GIARC和IARC算法的約簡后分類精度在6種算法中表現(xiàn)最差,原因是這兩個算法是基于等價關系的增量方法,對所增加的樣本集進行了離散化處理,破壞了原有樣本集屬性取值的連續(xù)性,所以精度明顯低于其他算法。與非增量HANDI算法相比,5種增量算法中除去GIARC和IARC,其他3種算法均取得了更高的約簡后精度。IAUNR在9個數(shù)據(jù)集上優(yōu)于HANDI算法的精度,這表明IAUNR算法在極大減少時間消耗的基礎上,還保持了良好的分類性能。

表2 約簡后的6種算法精度比較

結(jié)合3.2節(jié)和3.3節(jié)的實驗結(jié)果，本文所提的IAUNR增量算法在11個數(shù)據(jù)集上取得了最好的分類精度,約簡更新的時間僅高于基于等價關系的增量算法IARC,但顯然能比IARC生成更好的屬性約簡。

3.4 約簡中屬性數(shù)目的比較

約簡中所含屬性數(shù)量可以反映約簡算法去除冗余信息的能力。表3顯示了6種算法經(jīng)過5次增量實驗的平均約簡數(shù)目。非增量算法HANDI的結(jié)果是在每次變化后的數(shù)據(jù)集上重新計算的,可視為其他算法的一個基準。

表3 約簡中屬性數(shù)目比較

可以看出,6種算法去除了數(shù)據(jù)集中的大部分屬性,且在5種增量算法中,IAUNR的平均約簡數(shù)目(6.85)是最少的,其次是NIARC算法(8.73),再次是IARNGCE算法(8.91)。與非增量HANDI算法相比,IAUNR約簡中平均屬性數(shù)目只多了0.41,在3個數(shù)據(jù)集上達到最少,1個數(shù)據(jù)集上屬性數(shù)目相等。可見IAUNR算法在保持了分類精度優(yōu)勢的同時,還有著很強的約簡能力。GIARC和IARC的約簡中屬性數(shù)目較多的原因是對數(shù)據(jù)集進行了離散化處理,為保持原始分類能力需要包含更多的屬性。IARNGCE和NIARC也表現(xiàn)出了較好的約簡能力,但提取的屬性數(shù)目仍然明顯多于IAUNR,可能的原因包括其自身算法的分類能力低于IAUNR算法,而且這兩個算法沒有加入檢查冗余屬性的操作。

3.5 IAUNR算法中不確定性閾值對增量算法的影響

在IAUNR算法中,不確定性閾值對3類樣本的劃分有著直接的影響,而且主要影響的是不確定性大的樣本(第3類)。根據(jù)第2節(jié)可知,不確定性閾值變大,則第3類樣本減少,參與更新計算的樣本減少會降低時間耗費,但可能會引起精度的降低。由于一般情況下,大多數(shù)樣本屬于第1類樣本,尤其是當原始約簡結(jié)果已經(jīng)具有較高的精度時,不確定性區(qū)間在較小范圍內(nèi)的變動，對屬性約簡的更新影響不大。但是，當現(xiàn)有的信息系統(tǒng)比較復雜時,即第2種和第3種類型樣本集的數(shù)量本身比較多時,那么不確定性大且被正確分類的樣本數(shù)較多,此時選擇比較準確的不確定性閾值是非常重要的,理想的閾值既可以使得參與更新的樣本集規(guī)模盡可能達到最小,大大減少計算量,又可以有效地更新屬性約簡,使其分類能力達到最大。

本文在選用模糊k近鄰(FKNN)計算不確定性時,使用的是k個近鄰中每類樣本占k值的比例,是一個由離散值計算出的結(jié)果,得到的也是離散的不確定性值,即閾值可在有限個離散值中選取。

為簡單討論不同閾值對結(jié)果的影響,本節(jié)采用隨機生成3個高斯分布的樣本集,分別有200、250、200個樣本,原始屬性有20個,類別數(shù)分別有3、3、4類。分別加入隨機產(chǎn)生的100、50、100個樣本到原數(shù)據(jù)集中。本實驗主要研究不確定性閾值對增量算法的影響,不考慮其他參數(shù),故統(tǒng)一設置鄰域半徑為0.1,FKNN中k取3。首先，根據(jù)定義10計算全部情況的不確定性大小,對一個樣本的3-近鄰共有3種分布[0,0,3]，[0,1,2]，[1,1,1],可對應不同不確定性大小分別約等于0、0.918 3、1.585 0。取[0,1,2]所對應的0.918 3作為不確定性閾值,然后將閾值增大,取[1,1,1]所對應的1.585 0作為對比。實驗結(jié)果如表4，其中,原屬性約簡結(jié)果指增量前的屬性結(jié)果。

表4的實驗結(jié)果表明,當不確定性閾值增大時,由于參與更新計算的樣本減少,因此，所消耗的時間有所減少,但同時可能會因為信息丟失導致分類精度有所下降。通過上述實驗結(jié)果可知,本文在11個采用的數(shù)據(jù)集上根據(jù)二分類問題選取的不確定性閾值是傾向于保留更多樣本,減少精度損失。當然閾值的選擇與類別數(shù)有密切的關系,類別數(shù)越多,可選擇的不確定性離散值也越多。

表4 不同不確定性閾值的比較

4 結(jié)語

增量方法是應對當今大數(shù)據(jù)快速變化的一個重要方法,鄰域粗糙集框架下研究連續(xù)值屬性也具有重要意義?？紤]不同區(qū)域樣本對屬性約簡貢獻程度不同的問題,本文提出了基于不確定性和鄰域關系粗糙集的增量屬性約簡方法,使用不確定性和分類器結(jié)果衡量樣本的貢獻大小,將其分為3種不同類型,并給予不同的更新策略。當樣本增加時,只選擇重要的樣本參與約簡的更新計算,提出了相應的增量屬性約簡算法,并通過大量實驗結(jié)果表明該算法的有效性。相比現(xiàn)有的增量方法,所提方法可處理連續(xù)值信息系統(tǒng),進一步降低了約簡更新的時間代價,同時保持了很好的分類精度。需要進一步討論的問題是，針對類別數(shù)量較多、具有復雜邊界數(shù)據(jù)集上的不確定閾值的選擇和優(yōu)化;另外,本文的增量方法是針對有監(jiān)督樣本增加的情形,接下來將進一步探究無監(jiān)督樣本加入時的增量屬性約簡問題。