基于鄰域關(guān)系粗糙集和不確定性的增量屬性約簡方法

吳曉雪，李 艷

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

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

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

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

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

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

1 鄰域關(guān)系粗糙集中的基本概念

定義1稱NIS=(U,A,V,f,ε)是一個(gè)鄰域信息系統(tǒng)[22],其中，U={x1,x2,…,xn}是非空的對(duì)象集,稱為論域;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]設(shè)鄰域決策信息系統(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個(gè)區(qū)域,分別為正域POSB(X)、邊界域BNDB(X)和負(fù)域NEGB(X),定義為

(4)

(5)

(6)

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

POSB(D)=POSC(D)，

(7)

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

(8)

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

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

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

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

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

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

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

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

2.2 相關(guān)概念和更新策略

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

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

(9)

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

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

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

(10)

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

(11)

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

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

定義9[4]設(shè)鄰域決策信息系統(tǒng)NDS=(U,A,V,f,ε),B?C,a∈C-B,關(guān)于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)計(jì)算不確定性,好處是模糊k近鄰引入了類別隸屬度的概念,樣本不只屬于某一類,而是以一定比例隸屬于多個(gè)類別,比k近鄰更加準(zhǔn)確。

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

(13)

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

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

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

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

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

針對(duì)不同類別的樣本,采取不同的策略。

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

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

3)對(duì)于第3類樣本,即不確定性大的樣本,不能忽略其對(duì)分類和約簡的貢獻(xiàn),應(yīng)參與屬性約簡的更新。

2.3 增量算法步驟

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

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

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

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

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

2)while start

3) for eachai∈B

5) 計(jì)算重要度

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)對(duì)應(yīng)的屬性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)。

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

3 實(shí)驗(yàn)結(jié)果與分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.1 與非增量算法的約簡時(shí)間比較

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

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

圖2 非增量算法和增量算法約簡時(shí)間比較

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

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

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

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

3.3 分類精度比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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