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

吳曉雪，李 艷

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)

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

(4)

(5)

(6)

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

POSB(D)=POSC(D)，

(7)

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

(8)

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

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

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

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

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

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

圖1 不同區域樣本對屬性約簡的影響結果

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

2.2 相關概念和更新策略

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

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

(9)

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

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

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

(10)

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

(11)

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

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

定義9[4]設鄰域決策信息系統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是約簡集,則滿足如下性質:

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

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

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

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

(13)

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

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

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

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

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

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

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

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

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

2.3 增量算法步驟

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

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

樣本的篩選過程:在NDS中的約簡集redU上計算UX的不確定性大小和樣本分類正確與否,將其分為3種類型;若新增樣本UX全部屬于第1種類型,則直接加入原數據集中,不進行約簡的更新,轉到步驟20);否則,將屬于其他兩類的樣本保留,記為數據集X,用于約簡的更新,轉到步驟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)≤δ,則轉至步驟20)，否則轉至步驟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 實驗結果與分析

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

表1 實驗數據集

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

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

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

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

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

3.2 與現有增量方法的約簡時間比較

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

圖3 IAUNR與現有增量方法的約簡時間比較

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

3.3 分類精度比較

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

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

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

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

3.4 約簡中屬性數目的比較

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

表3 約簡中屬性數目比較

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

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

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

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

為簡單討論不同閾值對結果的影響,本節采用隨機生成3個高斯分布的樣本集,分別有200、250、200個樣本,原始屬性有20個,類別數分別有3、3、4類。分別加入隨機產生的100、50、100個樣本到原數據集中。本實驗主要研究不確定性閾值對增量算法的影響,不考慮其他參數,故統一設置鄰域半徑為0.1,FKNN中k取3。首先，根據定義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作為對比。實驗結果如表4，其中,原屬性約簡結果指增量前的屬性結果。

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

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

4 結語

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