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

鄧安生,趙梓旭

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

1 引言

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

在鄰域信息粒化方式中,通常是借助給定的半徑來約束樣本之間的相似性,最終確定鄰域關系。在這個過程中可以看出半徑的大小對最終的粒化結果起到十分重要的作用,若半徑選取的過大,很有可能會導致不同標簽的樣本落在同一個鄰域,引起信息粒化的不精確,不足以提供令人滿意的判別性能。針對該現象,Liu[9]和Wang[10]等人提出監(jiān)督鄰域粒化策略,在鄰域粒化過程中利用了樣本的標簽,使用兩個鄰域半徑確定鄰域關系。該策略可以在一定程度上減緩給定半徑不合適時,導致粒化不精確的問題。然而,數據集中的每個樣本都是不同的,所需粒化方式也理應是不同的,值得注意的是,該策略視數據集中的所有樣本都是相同的,忽略了樣本的特殊性;其次當樣本量非常巨大時,每個數據集都要通過實驗確定鄰域半徑會十分消耗時間。鑒于此,提出一種動態(tài)鄰域粒化機制,具體首先根據樣本分布初步計算鄰域半徑,降低因樣本分布不均勻導致的負面影響;然后依據屬性和標簽的關系對第一步計算出的鄰域半徑進行縮減,以期能提高粒化的精準率,為每個樣本設計一個獨有的鄰域半徑;在此基礎上給出上下近似算子,進而實現動態(tài)鄰域粗糙集模型。

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

2 基礎知識

2.1 鄰域關系

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

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

(1)

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

(2)

2.2 鄰域粗糙集

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

(3)

(4)

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

(5)

(6)

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

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

(7)

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

3 動態(tài)鄰域粒化機制和屬性約簡

3.1 動態(tài)鄰域粒化機制

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

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

(8)

(9)

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

(10)

圖1 分布半徑選取圖

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

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

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

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

(11)

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

(12)

v=(ATA)-1ATY

(13)

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

(14)

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

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

(15)

在實驗中,設置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)鄰域關系及其粗糙集

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

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

(16)

根據鄰域關系DN,容易得到樣本xi的近鄰為

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

(17)

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

(18)

(19)

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

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

(20)

3.3 屬性約簡

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

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

(21)

(22)

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

(23)

其中|Q∩W|/|V|表示被淘汰樣本中未變化的比例,也就是一致性樣本的比例。其中當B=?時,多準則屬性評估函數退化為依賴度評估函數。公式(23)同時兼顧考慮了已被淘汰的樣本,故稱為一種多準則的屬性評估。動態(tài)鄰域粒化方式下的屬性約簡如算法1所示。

算法1:動態(tài)鄰域粒化方式下的屬性約簡算法

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

輸出:約簡后屬性集BR

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

2)計算每個屬性a的關聯度ω(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)跳轉至3)

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

4 實驗與結果分析

4.1 實驗設置

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

表1 UCI數據集的描述

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

4.2 動態(tài)鄰域粒化機制精確度分析

把12個UCI數據集按屬性數量分成10個相等的子數據集,把第一個數據子集作為測試集1,前兩個數據子集累加作為測試集2,以此類推得到10個測試子集,在10個測試子集上分別計算在分布鄰域粒化機制下,和在其基礎上縮減半徑的動態(tài)鄰域粒化機制下的鄰域近似質量。在圖3中,隨著屬性數量的逐漸增多,12個數據集的鄰域近似質量并沒有呈現出單調性變化,這是由于在兩種粒化機制下鄰域內樣本隨著屬性增多是非單調的。通過觀察圖3發(fā)現,動態(tài)鄰域較于縮減半徑前的分布鄰域相比有更高的粒化精確度,提高了信息粒化一致性的比率。

4.3 約簡長度對比

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

表2 約簡長度的對比

4.4 分類準確率對比

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

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

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

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

4.5 Kappa值對比

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

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

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

5 結語

在鄰域粗糙集的背景下,針對已有的鄰域關系采取固定鄰域半徑粒化策略導致粒化不精確的問題,提出一個動態(tài)鄰域粒化的策略,并且定義了動態(tài)鄰域關系,構建相應的粗糙集模型。與此同時,針對下近似單調性問題,通過融合動態(tài)鄰域至樣本淘汰的屬性約簡算法中得以解決,并改進了其屬性評估方法。實驗結果表明,相較于傳統(tǒng)鄰域關系和其他新型的鄰域關系,采用動態(tài)鄰域關系,計算約簡結果,可在不同數據集上都獲得一個較優(yōu)的約簡結果,并且所得到的約簡在分類準確率上也優(yōu)于對比算法。