鄰域粗糙集的隨機(jī)集成屬性約簡(jiǎn)

沈 林

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

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

1 基本概念

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

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

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

(1)

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

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

(2)

1.2 基于依賴度的屬性約簡(jiǎn)

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

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

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

(3)

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

定義5[2]對(duì)于屬性集A?C， 當(dāng)rA(DS,β)=r(DS,β)時(shí)，則認(rèn)為屬性A是C的一個(gè)約簡(jiǎn).

1.3 基于辨識(shí)矩陣的變精度鄰域粗糙集屬性約簡(jiǎn)

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

(4)

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

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

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

(5)

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

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

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

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

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

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

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

2 基于隨機(jī)抽樣的集成屬性約簡(jiǎn)

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

圖1 本文算法的流程圖

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

(6)

其中ωCi表示屬性Ci的權(quán)重，ωSi表示屬性子集Si的權(quán)重.

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

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

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

3.1 各抽樣比例的空間占用和時(shí)間消耗

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

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

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

表3 3種算法的時(shí)間消耗

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

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

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

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

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

(7)

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

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

圖3 各抽樣比例的精度

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

3.3 不同算法的約簡(jiǎn)效果

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

表6 3種算法的屬性約簡(jiǎn)精度

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

4 結(jié)論

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