沈 林

( 莆田學院 信息工程學院， 福建 莆田 351100 )

2008年，胡清華等通過引入鄰域關系，構建了鄰域粗糙集模型(neighborhood rough sets，NRS)[1]，解決了Pawlak的粗糙集理論(rough sets，RS)無法處理數(shù)值型數(shù)據(jù)的問題[2].此后，許多學者對鄰域粗糙集模型進行了研究[3-6].目前，NRS被廣泛應用于知識發(fā)現(xiàn)、規(guī)則提取等領域.屬性約簡是去除冗余屬性、獲得精簡知識的前提，對研究NRS具有重要作用.辨識矩陣是粗糙集屬性約簡的主要方法之一，但由于傳統(tǒng)辨識矩陣僅記錄樣本間的辨識信息，缺少決策分布的相關信息，因此難以應用于變精度鄰域粗糙集(variable precision neighborhood rough sets，VPNRS)的屬性約簡.文獻[7]提出了一種改進的辨識矩陣，解決了變精度鄰域粗糙集的屬性約簡問題，但該改進的辨識矩陣占用空間較大，限制了其在大規(guī)模數(shù)據(jù)上的應用.基于上述研究，本文提出一種基于隨機抽樣的屬性約簡算法，并通過對多個UCI數(shù)據(jù)集的實驗，驗證本文方法的可行性.

1 基本概念

1.1 鄰域粗糙集和變精度鄰域粗糙集模型

定義1[1]有決策系統(tǒng)DS=(U,C∪D,V,f)，U是非空樣本集，C是條件屬性，D是決策屬性，f是U×(C∪D)→V的映射函數(shù).樣本xi∈U的鄰域關系記為δA(xi)={xj|xj∈U,ΔA(xi,xj)≤δ}， 其中δ是鄰域半徑，屬性集A?C，ΔA(xi,xj)是樣本xi和xj的距離函數(shù).

定義2[1]對于給定的集合X?U， 屬性集A的上近似和下近似定義為：

(1)

上下近似是粗糙集中的重要的概念之一，是用于分析精確、模糊知識的重要工具.定義2要求處理的樣本必須是精確的，但因其抗噪音能力差，所以在實踐中往往會引入精度β(0≤β≤0.5)， 即將粗糙集變?yōu)樽兙揉徲虼植诩?變精度鄰域粗糙集的上下近似定義為：

定義3[1]當有非空樣本集X?U， 則X關于屬性A的β上、下近似可以描述為：

(2)

1.2 基于依賴度的屬性約簡

基于依賴度屬性約簡的基本思想是通過計算依賴度，尋找到可以保持正域不變的屬性約簡(下面記作Dependence算法).

定義4[2]決策系統(tǒng)的近似鄰域依賴為

r(DS)=|POS(DS)|/|U|.

(3)

其中POS(DS)= ∪CδYj，Yj?U/D是決策屬性D對樣本U的劃分，CδYj為決策類Yj在條件屬性C的δ鄰域關系下的下近似，POS(DS)是決策類下近似的并集.

定義5[2]對于屬性集A?C， 當rA(DS,β)=r(DS,β)時，則認為屬性A是C的一個約簡.

1.3 基于辨識矩陣的變精度鄰域粗糙集屬性約簡

因傳統(tǒng)的辨識矩陣不能直接應用于VPNRS，文獻[8]定義了一種新的辨識矩陣，如公式(4)所示：

(4)

該辨識矩陣的每行是一個樣本對，每列對應一個屬性， 數(shù)字0表示樣本對不是鄰域關系， 數(shù)字1表示樣本對是鄰域關系且決策屬性相同， 數(shù)字2表示樣本對是鄰域關系但決策屬性不同.在每一輪屬性選擇中，選擇數(shù)字值2與數(shù)字值1比值最低的屬性.由于該方法無需反復計算各樣本的鄰域和精度，因此降低了時間復雜度.為了避免對某個決策類過度擬合，文獻[7]的算法在約簡過程中還檢驗了下近似分布不變.

定義6[7]決策系統(tǒng)的下近似分布的定義為：

DP(DS,β)={Cβ δY1,Cβ δY2,…,Cβ δYn},

(5)

其中Cβ δYj為決策類Yj在條件屬性C的δ鄰域關系下的β下近似.

文獻[7]中的改進辨識矩陣算法(下面稱為BMLNRS算法)的具體流程如下：

a)按照式(3)計算樣本集的鄰域辨識矩陣.

b)計算全屬性C下的下近似分布.

c)找出精度最高的屬性{ai|min(|M(ij)ai=2|/(|M(ij)ai=1|+m))}，m是元素個數(shù)，并將該屬性放入已選屬性隊列，然后執(zhí)行步驟e).

d)將剩余屬性依次和已選屬性隊列做位與運算，將精度最高的屬性加入已選屬性隊列.若有多個剩余屬性可以得到最高精度，則選擇數(shù)值1最多的剩余屬性.

e)檢查下近似分布是否和b)一致，如果是則輸出已選屬性隊列并結束算法，如果不是則重復d)、e)步驟，直到滿足條件.

2 基于隨機抽樣的集成屬性約簡

為了解決BMLNRS算法空間占用過高的問題，本文通過隨機抽樣獲得多個不同的小規(guī)模樣本，然后利用BMLNRS算法分別進行約簡.在獲得多個有一定差異的屬性子集后，計算每個屬性子集的權重，并選取最好的n個屬性子集在之前抽取的小規(guī)模樣本上進行測試，以此選出精度最好的屬性子集.為了進一步減少空間占用，將文獻[7]中按字節(jié)存儲矩陣元素的方法，改為按二進制位存儲.整個算法如圖1所示.

圖1 本文算法的流程圖

在計算屬性子集的權重時，若在多組不同的屬性子集中，某屬性出現(xiàn)的次數(shù)多，則表示其分辨決策類的能力強.權重的計算公式如下：

(6)

其中ωCi表示屬性Ci的權重，ωSi表示屬性子集Si的權重.

3 實驗結果

所有實驗均在Windows7環(huán)境下完成.首先在Matlab下編寫代碼，以此獲得屬性約簡的子集，然后使用WEKA自帶的算法驗證精度.本文從UCI數(shù)據(jù)集中選擇5個大規(guī)模數(shù)據(jù)集來驗證本文算法的效果，所有數(shù)據(jù)集均為數(shù)值型數(shù)據(jù)，如表1所示.

表1 數(shù)據(jù)集參數(shù)

3.1 各抽樣比例的空間占用和時間消耗

不同抽樣比例對辨識矩陣空間占用的影響如表2所示.從表2可以看出，隨著抽樣比例的降低，辨識矩陣的占用空間迅速減少.在30%抽樣比例時，占用空間為全集的2%～3%；在10%抽樣比例時，占用空間只有全集的0.25%～0.35%.這說明，隨機小規(guī)模樣本子集可以顯著減少辨識矩陣的占用空間.

表2 各抽樣比例的空間占用

為了避免算法運行時間超過全集時的運行時間，將本文算法的運行時間與全集時的Dependence算法、BMLNRS算法進行比較，結果如表3所示.隨機抽取本文算法的15個樣本子集(按30%、20%、10%比例分別隨機抽取5次)進行運行.從表3可以看出，采用15組隨機子集進行屬性約簡，其運行總時間明顯少于BMLNRS算法和基于依賴度的算法.這說明，通過控制隨機抽樣的次數(shù)，可以使屬性約簡的時間消耗不超過全集下屬性約簡的時間.

表3 3種算法的時間消耗

3.2 各抽樣比例和鄰域半徑下的穩(wěn)定性

3.2.1各抽樣比例對約簡子集的屬性個數(shù)的影響 表4和表5給出了不同抽樣比例對約簡后屬性個數(shù)的影響.由表4可知，在0.5σ時，除Waveform外，其他數(shù)據(jù)集在各抽樣比例下其約簡后的屬性個數(shù)與全集基本相當，即并不隨抽樣比例的變化而發(fā)生顯著變化.但在0.3σ時(表5)，各數(shù)據(jù)集約簡后的屬性個數(shù)均隨抽樣比例的降低而減少.

表4 0.5σ鄰域半徑下約簡后的屬性個數(shù)

表5 0.3σ鄰域半徑下約簡后的屬性個數(shù)

3.2.2各抽樣比例約簡結果的相似度 為了進一步了解隨機抽樣和鄰域半徑對約簡后屬性子集的影響，將本文算法的15個隨機樣本子集分別按照0.3σ、0.4σ、0.5σ、0.6σ的鄰域半徑進行屬性約簡，并分別計算這些結果與全集約簡結果的相似度，然后將相似度按照樣本抽樣比例分組并求平均值，結果如圖2所示.相似度計算采用谷元距離度量法[8]：

(7)

公式中，DT的取值范圍為[0，1]，取值越大，說明兩個屬性子集的相似度越高；取值為0時表示完全不同，為1時表示完全相同.

從圖2可以看出，相似度的變化與抽樣比例、鄰域半徑的變化沒有相關性.其中，Waveform數(shù)據(jù)集的相似度低于其他數(shù)據(jù)集，這是因為Waveform數(shù)據(jù)集中有40個屬性，而每個抽樣比例僅隨機抽取5個樣本，所以相似度偏低.

圖3 各抽樣比例的精度

3.2.3各抽樣比例的約簡精度 按30%、20%、10%比例隨機抽樣(每個比例各抽樣5次)測試各抽樣比例對精度的影響.測試時，δ取0.5σ，β取0.5.約簡后，用3NN、SimpleCart、SMO、Bagging、JRip、RandomForest算法計算每組的平均精度，結果如圖3所示.由圖3可以看出，在30%和20%的抽樣比例下，除了Letter數(shù)據(jù)集，其他隨機子集的精度都略高于全集.在抽樣比例為10%時，隨機子集的精度普遍較低，其原因是在該抽樣比例下，樣本子集的信息量丟失較多.

3.3 不同算法的約簡效果

為了評價本文算法的分類精度，將本文算法得到的屬性子集的分類精度與Dependence算法、BMLNRS算法進行對比.BMLNRS算法和本文算法的δ取0.5σ，β取0.5，Dependence算法則采用分類精度最好的結果.用3NN、SimpleCart、SMO、Bagging、JRip、RandomForest算法計算每個屬性子集的精度并取平均值，結果如表6所示.

表6 3種算法的屬性約簡精度

從表6可以看出，本文算法的分類精度和BMLNRS算法基本相當.Dependence算法在EEG和Letter數(shù)據(jù)集上的精度優(yōu)于本文算法，這是由于在這兩個數(shù)據(jù)集上，Dependence算法約簡后的屬性個數(shù)多于本文算法，即保留的信息量多于本文算法.

4 結論

UCI數(shù)據(jù)集實驗證明，本文提出的基于多次隨機抽樣的集成屬性約簡算法的空間占用比BMLNRS算法可減少2～3個數(shù)量級，且其約簡精度和BMLNRS算法相當，所以本文方法在處理大規(guī)模數(shù)據(jù)時，具有更大的優(yōu)勢.本文在生成約簡子集時，僅考慮了一種屬性評價標準，該評價標準可能會更偏好個別屬性，因此今后將考慮綜合多種評價標準，以進一步提高本文方法的魯棒性.