動態(tài)鄰域粒化方式下的屬性約簡研究

鄧安生,趙梓旭

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧 大連116026)

1 引言

粗糙集[1]是Pawlak提出的一種刻畫不確定性的建模方法,但僅能用于處理符號型數(shù)據(jù),對于數(shù)值型數(shù)據(jù)[15]而言,經(jīng)典Pawlak粗糙集不能直接處理。為了彌補這一空缺,出現(xiàn)了許多粗糙集拓展模型[2-4,12]。其中基于鄰域關(guān)系[14]的粗糙集拓展模型能有效的處理數(shù)值型數(shù)據(jù)。最近,鄰域粗糙集在粒度計算[5,6]領(lǐng)域獲得了大量的關(guān)注,相關(guān)的理論研究和方法被廣泛應(yīng)用于屬性約簡和特征選擇[7,8,11,15]。

在鄰域信息粒化方式中,通常是借助給定的半徑來約束樣本之間的相似性,最終確定鄰域關(guān)系。在這個過程中可以看出半徑的大小對最終的?；Y(jié)果起到十分重要的作用,若半徑選取的過大,很有可能會導(dǎo)致不同標(biāo)簽的樣本落在同一個鄰域,引起信息?；牟痪_,不足以提供令人滿意的判別性能。針對該現(xiàn)象,Liu[9]和Wang[10]等人提出監(jiān)督鄰域?；呗?在鄰域?；^程中利用了樣本的標(biāo)簽,使用兩個鄰域半徑確定鄰域關(guān)系。該策略可以在一定程度上減緩給定半徑不合適時,導(dǎo)致?；痪_的問題。然而,數(shù)據(jù)集中的每個樣本都是不同的,所需?；绞揭怖響?yīng)是不同的,值得注意的是,該策略視數(shù)據(jù)集中的所有樣本都是相同的,忽略了樣本的特殊性;其次當(dāng)樣本量非常巨大時,每個數(shù)據(jù)集都要通過實驗確定鄰域半徑會十分消耗時間。鑒于此,提出一種動態(tài)鄰域?；瘷C制,具體首先根據(jù)樣本分布初步計算鄰域半徑,降低因樣本分布不均勻?qū)е碌呢?fù)面影響;然后依據(jù)屬性和標(biāo)簽的關(guān)系對第一步計算出的鄰域半徑進(jìn)行縮減,以期能提高?；木珳?zhǔn)率,為每個樣本設(shè)計一個獨有的鄰域半徑;在此基礎(chǔ)上給出上下近似算子,進(jìn)而實現(xiàn)動態(tài)鄰域粗糙集模型。

目前在基于粗糙集的屬性約簡方法中,都建立在粗糙集的上近似和下近似隨著屬性增加呈現(xiàn)單調(diào)性的前提下。若鄰域半徑是動態(tài)變化的,則上、下近似不再有單調(diào)性的特點。眾所周知,下近似的單調(diào)性更有利于設(shè)置屬性約簡的迭代停止條件。因此,針對上文提出的動態(tài)鄰域?；呗?引入Zhang[13]等人提出的‘樣本淘汰’(Sample Elimination)屬性約簡的方法作為本研究的屬性約簡策略,該策略在每次迭代選擇屬性時,僅考慮未被已選屬性正確分類的樣本,而那些已被正確分類的樣本則會被淘汰,保證了下近似的單調(diào)性,并在此基礎(chǔ)上提出一種多準(zhǔn)則屬性評估函數(shù),緩解在約簡的過程中產(chǎn)生的不一致的問題。

2 基礎(chǔ)知識

2.1 鄰域關(guān)系

給定一個決策系統(tǒng)DS=〈U,AT,d〉,其中U代表樣本集合,AT代表條件屬性集合,d代表決策屬性集合。對于任意xi∈U且任意b∈AT,b(xi)表示在條件屬性b下xi的取值,d(xi)表示在決策屬性d下xi的取值,也就是通常意義的標(biāo)簽。U/IND(d)={X1,X2,…,XN}表示在決策屬性d上誘導(dǎo)出的論域上的劃分,?Xi∈U/IND(d),Xi表示第i個決策類且1≤i≤N。

定義1:給定一個決策系統(tǒng)DS,?b∈AT,鄰域半徑δ>0,在條件屬性集B下的δ鄰域關(guān)系定義為

(1)

其中disB(xi,xj)表示在條件屬性集B下兩個樣本之間的距離,為了簡便起見,距離度量函數(shù)使用歐氏距離。

(2)

2.2 鄰域粗糙集

定義3:給定一個決策系統(tǒng)DS,?b∈AT,d關(guān)于B的上近似和下近似可以定義為

(3)

(4)

其中,?Xi∈U/IND(d)。關(guān)于決策類Xi的上近似和下近似定義為

(5)

(6)

定義3中給出的上、下近似描述了目標(biāo)概念的粗糙程度。為了反映出目標(biāo)的確定程度,給出如下所示的依賴度(也稱作近似質(zhì)量)的概念。

定義4 給定一個決策系統(tǒng)DS,?b∈AT,d關(guān)于B的依賴度定義如下

(7)

其中,|X|表示集合X的基數(shù),U表示樣本集。顯然,0≤γB(d,U)≤1成立。γB表示根據(jù)條件屬性B,確定屬于某一個決策類別的樣本在樣本集U中的比例。γB的值越接近1,表示確定性程度越高,反之值越接近0,表示確定性程度越低。

3 動態(tài)鄰域?；瘷C制和屬性約簡

3.1 動態(tài)鄰域?；瘷C制

在傳統(tǒng)的鄰域模型中,鄰域半徑通常由實驗分析給出且固定不變,這種粒化方式對有的樣本粒化過粗,而對有的樣本?；^細(xì),整體來看粒化效果并不好,所以需要對每個樣本找到它適合的?；绞?也就是適合它的半徑。首先根據(jù)不同的數(shù)據(jù)分布初步為每個樣本選擇半徑(下文簡稱為‘分布半徑’)。具體的定義如下所示。

定義5:給定一個決策系統(tǒng)DS,NB(xi)表示距離xi的樣本從小到大排序的集合

(8)

(9)

定義6:給定一個決策系統(tǒng)DS,?B∈AT,則樣本xi的分布半徑定義為

(10)

圖1 分布半徑選取圖

圖2 屬性a1、a2下的樣本圖

相比于傳統(tǒng)鄰域粗糙集固定半徑的?；瘷C制,分布半徑可以針對每個樣本的特點選擇一個鄰域半徑,然而,仍不可避免出現(xiàn)粒化不精確的問題。如圖2所示在屬性a1、a2下樣本的分布情況,假設(shè)這兩個屬性是約簡后的最佳屬性,然而觀察在兩類分界處的樣本xi和yi,其鄰域內(nèi)仍包含不同類別的樣本點,這可能會在屬性評估時降低對這兩個屬性的分?jǐn)?shù),導(dǎo)致無法選出該屬性。

針對這一問題,本研究對鄰域半徑進(jìn)行縮減操作,減少鄰域內(nèi)異類樣本,以期能提高這類樣本的粒化精確度。考慮到不同屬性與標(biāo)簽存在不同的關(guān)聯(lián)度,最佳屬性在一定程度上會與標(biāo)簽有更高的關(guān)聯(lián)度,遂以此為思想來計算縮減比例,進(jìn)一步提高粒化精確度。具體先計算每個屬性與標(biāo)簽的關(guān)聯(lián)度,然后根據(jù)關(guān)聯(lián)程度決定鄰域半徑的縮減比例,具體定義如下。

定義7:給定一個決策系統(tǒng)DS,?B∈AT,?xi∈U,a(xi)表示樣本xi在屬性a下的取值,d(xi)表示樣本xi在決策屬性d下的取值,構(gòu)建矩陣A如下所示

(11)

決策向量可表示為Y=(d(x1),d(x2),…,d(xn))T,條件屬性與決策屬性的相似度可以用向量表示為v=(v(a1),v(a2),…,v(an))T。則問題轉(zhuǎn)換為

(12)

v=(ATA)-1ATY

(13)

|v(a)|表示v(a)的值,反應(yīng)屬性a與決策屬性d的關(guān)聯(lián)程度。|v(a)|的值越大,說明屬性a與決策屬性d的關(guān)聯(lián)程度越大。接著為每個屬性a計算關(guān)聯(lián)度

(14)

其中ω(a)≥0并且∑ai∈ATω(ai)=|AT|。

定義8:給定一個決策系統(tǒng)DS,?B∈AT,屬性關(guān)聯(lián)度向量表示為ω=(ω(a1),ω(a2),…,ω(am)),其中m表示特征的總數(shù),則在條件屬性B下,最終的動態(tài)鄰域半徑定義為

(15)

在實驗中,設(shè)置0.1δt≤δD≤0.9δt,也就是說,若δD≤0.1δt,動態(tài)鄰域半徑為最小值δD=0.1δt,若δD≥0.9δt,動態(tài)鄰域半徑為最大值δD=0.9δt。

3.2 動態(tài)鄰域關(guān)系及其粗糙集

定義9:給定一個決策系統(tǒng)DS,?B∈AT,對于一個動態(tài)鄰域半徑δD,動態(tài)鄰域關(guān)系可以定義為

DNB={(xi,xj)∈U×U：disB(xi,xj)≤δD}

(16)

根據(jù)鄰域關(guān)系DN,容易得到樣本xi的近鄰為

DNB(xi)={xj∈U：(xi,xj)∈DNB}

(17)

定義10:給定一個決策系統(tǒng)DS,?B∈AT,?Xi∈U/IND(d),d關(guān)于B的動態(tài)鄰域上下近似可以定義為

(18)

(19)

其中V、W∈U,是樣本全集的子集。

定義11:給定一個決策系統(tǒng)DS,?B∈AT,V∈U,在動態(tài)鄰域關(guān)系下,d關(guān)于B的依賴度定義如下

(20)

3.3 屬性約簡

觀察動態(tài)鄰域粗糙集的上下近似發(fā)現(xiàn),下近似并沒有隨著屬性的增加而單調(diào)變化,這是因為鄰域半徑的動態(tài)變化,樣本鄰域中粒子個數(shù)并不隨著屬性的增加而具有單調(diào)性。為了方便設(shè)置屬性約簡的迭代停止條件,需要設(shè)計的屬性約簡策略讓下近似具有單調(diào)性。通過研究樣本淘汰(Sample Elimination)的約簡策略,發(fā)現(xiàn)該方法在屬性約簡的過程中僅計算部分樣本,若結(jié)合粗糙集理論,然后重新定義屬性約簡的過程中上下近似的定義,可以保證下近似的單調(diào)性,具體方法如下所示。

定義12:給定一個決策系統(tǒng)DS,B0=?,并且Bi=Bi-1∪{a},a∈AT-Bi-1,i=1,2…,|AT|。V∈U,?Xp∈U/IND(d)。屬性集B的擴(kuò)張模擬了屬性約簡的過程中屬性的增加,上下近似計算公式定義為:

(21)

(22)

該策略保證了下近似的單調(diào)性,然而,觀察算法發(fā)現(xiàn)這種迭代算法嚴(yán)重忽略了那些被淘汰的樣本,被淘汰的樣本可能在新屬性加入時再次變的不確定,筆者稱這類樣本為不一致樣本。在屬性約簡的過程中完全忽略那些淘汰樣本的確定性變化會導(dǎo)致最終得到的約簡屬性集并不是一個最優(yōu)的約簡屬性集。綜上考慮,筆者提出了一個多準(zhǔn)則的屬性評估方法,把已確定的樣本也納入屬性選擇的考慮范圍之內(nèi)而不破壞下近似單調(diào)性的特點。具體定義如下所示。

(23)

其中|Q∩W|/|V|表示被淘汰樣本中未變化的比例,也就是一致性樣本的比例。其中當(dāng)B=?時,多準(zhǔn)則屬性評估函數(shù)退化為依賴度評估函數(shù)。公式(23)同時兼顧考慮了已被淘汰的樣本,故稱為一種多準(zhǔn)則的屬性評估。動態(tài)鄰域?；绞较碌膶傩约s簡如算法1所示。

算法1:動態(tài)鄰域?；绞较碌膶傩约s簡算法

輸入:決策系統(tǒng)DS

輸出:約簡后屬性集BR

1)初始化樣本子集V=U,屬性子集Sk=AT,約簡后屬性集BR=?

2)計算每個屬性a的關(guān)聯(lián)度ω(a)

3)FOR each aiin Sk：

4)BR=BR∪{ai},Pai=?

5) FOR each xiinV:

6)計算動態(tài)鄰域半徑δD

7)IF DNB(xi)中的樣本是一致的:

8)Pai=Pai∪{xi}

9) End IF

10) End FOR

11)End FOR

12)選擇屬性ai滿足ai=maxφai(d,V)

13)V=V-Pai,Sk=Sk-{a0},BR=BR∪{ai}

14)IF|Pai|/|V|≤θ：

15)輸出BR

16) End

17)ELSE:

18)跳轉(zhuǎn)至3)

其中θ是控制迭代算法停止的參數(shù),實驗設(shè)置θ=0.01。在算法中,首先計算每個屬性的關(guān)聯(lián)度,接著計算在每個屬性下每個樣本的動態(tài)鄰域,判斷鄰域中的樣本是否一致。最后使用提出的多準(zhǔn)則評估函數(shù)選擇滿足條件的屬性,直到算法停止。假設(shè)樣本的個數(shù)為|U|,屬性的個數(shù)為|AT|。上述算法中,需要對每個樣本計算它的近鄰且排序,時間復(fù)雜度為O(|AT|2*log|AT|)。每次迭代選擇樣本都要計算樣本的一致性,所以算法的整體時間復(fù)雜度為O(|AT|2*log|AT|*|U|2)。

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

4.1 實驗設(shè)置

為驗證動態(tài)鄰域?qū)傩约s簡(Dynamic Neighborhood Attribute Reduce,DNAR)算法的有效性,從UCI數(shù)據(jù)集中選取12個數(shù)據(jù)集,基本信息如表1所示。所有的實驗均在Windows 10 PC, Intel(R)Core(TM)i5-6500 CPU 3.20 GHz,16G RAM,Python3.8實驗平臺進(jìn)行。首先設(shè)置仿真實驗驗證動態(tài)鄰域?；瘷C制的有效性,接著用本研究提出的鄰域粗糙集屬性約簡算法與其他三個鄰域粗糙集屬性約簡算法SNRS[9](SupervisedNeighborhood Rough Set)、NNRS[16](k-Nearest Neighborhood Rough Set)、NRS(δ-Neighborhood Rough Set)比較三個指標(biāo)。第一個指標(biāo)是約簡后長度,第二個指標(biāo)是分類精度,即被分類器正確分類的樣本比例。第三個指標(biāo)是Kappa系數(shù),評價分類效果時平衡了隨機分類對分類結(jié)果的影響。實驗中參數(shù)采取對應(yīng)研究中使用的數(shù)值,其中NRS算法中的鄰域半徑設(shè)置為δ=0.1,0.2,…,1,取在所有鄰域半徑下表現(xiàn)的均值。

表1 UCI數(shù)據(jù)集的描述

實驗采用了十折交叉驗證的方法,即將原始數(shù)據(jù)集隨機的等分為10個部分,其中挑選9組用于訓(xùn)練,1組用于測試,該過程會將重復(fù)10次,保證每一組都會作為訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)進(jìn)行實驗,以避免模型的擬合性問題的出現(xiàn)對實驗結(jié)果產(chǎn)生偏差。另外在實驗前均對所有數(shù)據(jù)集進(jìn)行了標(biāo)準(zhǔn)化處理,以避免不同屬性的取值差異過大對結(jié)果產(chǎn)生影響。

4.2 動態(tài)鄰域?；瘷C制精確度分析

把12個UCI數(shù)據(jù)集按屬性數(shù)量分成10個相等的子數(shù)據(jù)集,把第一個數(shù)據(jù)子集作為測試集1,前兩個數(shù)據(jù)子集累加作為測試集2,以此類推得到10個測試子集,在10個測試子集上分別計算在分布鄰域?；瘷C制下,和在其基礎(chǔ)上縮減半徑的動態(tài)鄰域?；瘷C制下的鄰域近似質(zhì)量。在圖3中,隨著屬性數(shù)量的逐漸增多,12個數(shù)據(jù)集的鄰域近似質(zhì)量并沒有呈現(xiàn)出單調(diào)性變化,這是由于在兩種?；瘷C制下鄰域內(nèi)樣本隨著屬性增多是非單調(diào)的。通過觀察圖3發(fā)現(xiàn),動態(tài)鄰域較于縮減半徑前的分布鄰域相比有更高的?；_度,提高了信息?；恢滦缘谋嚷省?/p>

4.3 約簡長度對比

表2展示了四種不同的方法在上述介紹的12個數(shù)據(jù)集上約簡長度的比較,且是經(jīng)過十折交叉驗證得到結(jié)果的均值,約簡長度越小,代表刪除的屬性越多。觀察表2得出以下結(jié)論:DNAR算法在所有數(shù)據(jù)集上都能約簡合適數(shù)量的屬性,而其他三個算法在部分?jǐn)?shù)據(jù)集上約簡后屬性數(shù)量過多過少,這反應(yīng)了DNAR算法能夠處理不同類型的數(shù)據(jù)集。例如,SNRS算法在5個數(shù)據(jù)集上約簡后的平均屬性個數(shù)都為1,NNRS算法在QSAR數(shù)據(jù)集上幾乎無法約簡,這說明對比算法依靠固定的鄰域半徑不能處理這些數(shù)據(jù)集。約簡長度對比實驗說明DNAR算法能處理不同分布的數(shù)據(jù)集且約簡合適的屬性長度。在3.3節(jié)的分類精度對比也證明了DNAR算法約簡后屬性的質(zhì)量比其他算法約簡后的屬性質(zhì)量要高。

表2 約簡長度的對比

4.4 分類準(zhǔn)確率對比

在本組實驗中,采用KNN分類器和SVM分類器,利用屬性約簡后的結(jié)果對測試數(shù)據(jù)集進(jìn)行分類,并且計算分類準(zhǔn)確率,最后求出分類準(zhǔn)確率的平均值和最大值。分類準(zhǔn)確率結(jié)果如表3和表4所示,在每個數(shù)據(jù)集上的效果最好的算法得出的準(zhǔn)確率用粗體標(biāo)出。從表3和表4中可以看出,無論是采用KNN分類器還是SVM分類器,利用DNAR算法所求得的約簡,其對應(yīng)的平均分類準(zhǔn)確率,在多數(shù)數(shù)據(jù)集上都優(yōu)于其他算法。結(jié)合3.2節(jié)的結(jié)果表明,DNAR算法能夠有效的刪除冗余屬性且保留最佳的屬性。

表3 在KNN分類器上分類精度的對比

表4 在SVM分類器上分類精度的對比

為了驗證2.3中提出的多準(zhǔn)則屬性評估方法的有效性,設(shè)計了一種在DNAR下未使用多準(zhǔn)則屬性評估而使用近似質(zhì)量評估屬性的算法DNAR*。實驗結(jié)果表明,加入多準(zhǔn)則屬性評估的DNAR算法在12個數(shù)據(jù)集下,分類準(zhǔn)確率都要高于DNAR*。注意到在SONAR數(shù)據(jù)集上,DNAR算法比DNAR*算法準(zhǔn)確率提高8%左右。這說明了本研究提出的多準(zhǔn)則屬性評估方法能有效的減少不一致的樣本。

4.5 Kappa值對比

為了進(jìn)一步了解DNAR算法的性能,在本小節(jié)中利用Kappa統(tǒng)計在KNN分類器和SVM分類器下進(jìn)行分析。Kappa的數(shù)值在-1到1之間,數(shù)值越大,說明預(yù)測的結(jié)果越理想,反之說明預(yù)測的結(jié)果不理想。實驗結(jié)果如表5,表6所示,最優(yōu)值用粗體標(biāo)出。

表5 在KNN分類器上Kappa值的對比

根據(jù)表5,表6中的實驗結(jié)果顯示,在KNN分類器下,其中10個數(shù)據(jù)集上都優(yōu)于其他算法,且在11個數(shù)據(jù)集上的值都高于0.8。在SVM分類器下,在10個數(shù)據(jù)集上都優(yōu)于其他算法,且也在11個數(shù)據(jù)集上的值高于0.8。總體來看,DNAR算法的Kappa系數(shù)平均取值也優(yōu)于其他算法。

5 結(jié)語

在鄰域粗糙集的背景下,針對已有的鄰域關(guān)系采取固定鄰域半徑?；呗詫?dǎo)致?；痪_的問題,提出一個動態(tài)鄰域?；牟呗?并且定義了動態(tài)鄰域關(guān)系,構(gòu)建相應(yīng)的粗糙集模型。與此同時,針對下近似單調(diào)性問題,通過融合動態(tài)鄰域至樣本淘汰的屬性約簡算法中得以解決,并改進(jìn)了其屬性評估方法。實驗結(jié)果表明,相較于傳統(tǒng)鄰域關(guān)系和其他新型的鄰域關(guān)系,采用動態(tài)鄰域關(guān)系,計算約簡結(jié)果,可在不同數(shù)據(jù)集上都獲得一個較優(yōu)的約簡結(jié)果,并且所得到的約簡在分類準(zhǔn)確率上也優(yōu)于對比算法。