高斯核模糊粗糙集中基于粒子群算法的屬性約簡(jiǎn)

劉東君， 陳紅梅

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院 四川 成都 611756)

0 引言

在數(shù)據(jù)挖掘中，數(shù)據(jù)中冗余和不必要的屬性會(huì)影響算法執(zhí)行的效率，并可能造成過(guò)擬合.屬性約簡(jiǎn)是一種有效處理冗余屬性、相關(guān)屬性和不必要屬性的方法，它在保持?jǐn)?shù)據(jù)集分類能力不變的情況下，盡可能去除其中無(wú)關(guān)的、冗余的信息.Pawlak提出的粗糙集理論(rough set theory)[1]及其在屬性約簡(jiǎn)中的應(yīng)用得到了廣泛的研究[2-4].但是由于經(jīng)典粗糙集在處理數(shù)值數(shù)據(jù)中需要對(duì)數(shù)據(jù)進(jìn)行離散化處理，從而導(dǎo)致信息的損失，Dubois和Prade提出的模糊粗糙集理論[5]可解決該問(wèn)題.在模糊粗糙集理論中能直接對(duì)連續(xù)屬性值進(jìn)行分析，不會(huì)因?yàn)殡x散化而造成信息的損失.Jensen和Shen提出了模糊粗糙集理論的屬性約簡(jiǎn)算法[6]，Hu等將核函數(shù)應(yīng)用于模糊粗糙集，提出了核模糊粗糙集模型[7]，并在此基礎(chǔ)上提出了高斯核模糊粗糙集及相關(guān)屬性約簡(jiǎn)算法[8].

在粗糙集和模糊粗糙集屬性約簡(jiǎn)中，為了提高約簡(jiǎn)精度和降低計(jì)算約簡(jiǎn)或最小約簡(jiǎn)所需時(shí)間，演化算法在粗糙集中的應(yīng)用被廣泛研究，如基于粒子群算法(particle swarm optimization，PSO)的粗糙集屬性約簡(jiǎn)算法[9]、基于免疫遺傳算法的粗糙集屬性約簡(jiǎn)算法[10]、基于果蠅算法的粗糙集屬性約簡(jiǎn)算法[11]、魚(yú)群算法與粗糙集相結(jié)合的屬性約簡(jiǎn)算法[12]、基于環(huán)粒子群算法的模糊粗糙集約簡(jiǎn)算法[13]、八哥群算法與模糊粗糙集屬性約簡(jiǎn)的結(jié)合[14]等.可以看到，粗糙集與演化算法結(jié)合的算法已經(jīng)得到了廣泛的研究，但是模糊粗糙集與演化算法結(jié)合的研究還相對(duì)較少，尤其是在新興的模糊粗糙集模型如Hu等提出的核模糊粗糙集模型[7]上還未見(jiàn)相關(guān)報(bào)道.高斯核由于帶有可變參數(shù)的獨(dú)特性質(zhì)，通過(guò)與粒子群算法相結(jié)合，可根據(jù)參數(shù)的不同獲取不同約簡(jiǎn)率的屬性約簡(jiǎn)來(lái)提高分類的性能.實(shí)驗(yàn)表明本文提出的算法具有良好的約簡(jiǎn)性能，并且能夠獲取優(yōu)化的屬性約簡(jiǎn)以提高分類性能.

1 基本概念

1.1 模糊粗糙集相關(guān)理論

本節(jié)將介紹核模糊粗糙集相關(guān)的基本概念.Pawlak在粗糙集理論中定義了決策信息系統(tǒng)，用它來(lái)描述一個(gè)數(shù)據(jù)集.

定義2[5]設(shè)R為論域U上的一個(gè)模糊等價(jià)關(guān)系，那么模糊粗糙集的上、下近似定義為

定義3[16]設(shè)U是一個(gè)非空論域(不要求是有限的)，R是U上的任意模糊關(guān)系，對(duì)任意的A∈F(U)，模糊粗糙集的近似算子定義為

Hu等人通過(guò)把核函數(shù)引入模糊粗糙集，建立了基于核的模糊粗糙集模型[7]，并進(jìn)一步給出了一種常用核函數(shù)高斯核的模糊粗糙集模型[8].

定義4[17]設(shè)U是一個(gè)有限論域，如果實(shí)值函數(shù)k:U×U→R滿足條件：對(duì)?x,y∈U，有k(x,y)=k(y,x)，且半正定，那么把k稱為核.

高斯核被定義為kG(x,y)=exp(-‖x-y‖2/2σ2)，用高斯核所計(jì)算的模糊關(guān)系是Tcos-模糊等價(jià)關(guān)系[18]，這里‖·‖是x和y之間的歐氏距離.

基于該種依賴度定義，Hu提出了FS-GKA約簡(jiǎn)算法[8].本文將基于高斯核模糊粗糙集模型及其依賴度定義，構(gòu)建與粒子群相結(jié)合的屬性約簡(jiǎn)算法.

1.2 粒子群算法相關(guān)理論

pi(t+1)=pi(t)+vi(t+1)，

vi(t+1)=ω(t)·v(t)+c1·rand( )·(pbesti-pi(t))+c2·rand( )·(gbest-pi(t)).

2 基于粒子群算法的高斯核模糊粗糙集屬性約簡(jiǎn)

在高斯核模糊粗糙集的約簡(jiǎn)計(jì)算中，和傳統(tǒng)粒子群算法中每個(gè)維度坐標(biāo)都是連續(xù)的不同，由于每個(gè)屬性只有選擇和不選擇兩種可能，所以這時(shí)候粒子的每個(gè)屬性都是2值的，以{0,1}來(lái)表示.給定決策信息系統(tǒng)DIS=〈U,C∪D,V,f〉，對(duì)條件屬性集C={c1,c2,…,cn}，用一個(gè)n維粒子p=(x1,x2,…,xn)表示對(duì)條件屬性的選擇，其中xi∈{0,1}，規(guī)定0表示不選擇該屬性，1表示選擇該屬性，把粒子的速度記為v=(y1,y2,…,yn)，yi∈R，對(duì)粒子進(jìn)行更新時(shí)，若xi+yi≥0.5，則記為1，若xi+yi<0.5，則記為0.

粒子的適應(yīng)度函數(shù)f(p)選擇為f(p)=α·γp(D)+β·(|C|-|p|)/|C|，其中：α+β=1，α,β∈[0,1]；|C|為數(shù)據(jù)集屬性的個(gè)數(shù)；|p|為當(dāng)前粒子所選擇的屬性個(gè)數(shù).

通過(guò)下面的分析將會(huì)看到，把粒子群算法與高斯核模糊粗糙集模型結(jié)合，選擇不同的σ參數(shù)將會(huì)使最終所得到的約簡(jiǎn)的屬性個(gè)數(shù)發(fā)生變化.

定理1若U被決策屬性劃分為{d1,d2,…,dI}，對(duì)任意di,若x∈di，即di(x)=1，那么

若取高斯核函數(shù)，則

當(dāng)x∈di時(shí)，若y∈di，即di(x)=di(y)，這時(shí)di(y)=1，所以一定有Rn(x,y)≤di(y)，可得?Tcos(Rn(x,y),di(y))=1，即

?Tcos(Rn(x,y),di(y)).

當(dāng)y?di時(shí)，di(y)=0，于是可得

由定理1和正域的定義可以得出

下面給出粒子群算法與高斯核模糊粗糙集相結(jié)合的屬性約簡(jiǎn)算法.

算法1基于粒子群算法的高斯核模糊粗糙集屬性約簡(jiǎn)算法(PSO-GKFRA).

輸入：決策信息系統(tǒng)DIS=〈U,C∪D,V,f〉，最大迭代次數(shù)N，參數(shù)σ，ωmax，ωmin，c1，c2，α，β；

輸出：模糊粗糙集屬性約簡(jiǎn)Red.

1. 隨機(jī)初始化粒子S={p1,p2,…,pt}

2. n←0

3. While n

4. for each piin S

5. f(pi)←α·γpi(D)+β·(|C|-|pi|)/|C|

6. if f(pi)>f(pbesti) then

7. pbesti←pi

8. end if

9. if f(pi)>f(gbest) then

10. gbest←pi

11. end if

12. end for each

13. for each piin S

14. vi(n+1)=ω(n)·v(n)+c1·rand( )·(pbesti-pi(n))+c2·rand( )·(gbest-pi(n))

15. pi(n+1)←pi(n)+vi(n+1)

16. end for each

17. n←n+1

18. End While

19. Red←gbest

20. 輸出Red

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

在本節(jié)中，將使用本文提出的屬性約簡(jiǎn)算法，在4個(gè)公有數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以測(cè)試算法性能.

3.1 實(shí)驗(yàn)方案

為了說(shuō)明本文所提出的算法的正確性和有效性，實(shí)驗(yàn)采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中的常用數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)和對(duì)比，數(shù)據(jù)集見(jiàn)表1，表中給出了所選數(shù)據(jù)集樣本數(shù)、屬性個(gè)數(shù)、數(shù)值型屬性個(gè)數(shù)以及類別數(shù).

表1 數(shù)據(jù)集信息

本實(shí)驗(yàn)粒子群算法中ωmin設(shè)置為0.2，ωmax設(shè)置為0.6，預(yù)設(shè)迭代次數(shù)N設(shè)置為50，c1和c2均設(shè)置為0.6，α設(shè)為0.8，β設(shè)為0.2，粒子數(shù)設(shè)置為所選數(shù)據(jù)集屬性數(shù)的一半，詳細(xì)數(shù)目見(jiàn)表1的最后一列.

在不同σ值下，屬性約簡(jiǎn)后的數(shù)據(jù)集屬性數(shù)將會(huì)產(chǎn)生改變，表2、3給出了本文所提的PSO-GKFRA算法在不同σ下通過(guò)本文算法進(jìn)行約簡(jiǎn)后的屬性個(gè)數(shù)以及該情況下的分類精度.由于粒子群算法最終約簡(jiǎn)結(jié)果會(huì)受到初始粒子隨機(jī)選擇的影響，所以實(shí)驗(yàn)中每一個(gè)σ進(jìn)行5組實(shí)驗(yàn)，表2、3中數(shù)據(jù)均為5次實(shí)驗(yàn)的平均值.此外還采用Hu所提出的FS-GKA算法[8]以及經(jīng)典粗糙集屬性約簡(jiǎn)算法RS進(jìn)行比較，比較所采用的約簡(jiǎn)結(jié)果為文獻(xiàn)[8]中給出的約簡(jiǎn)結(jié)果，分類所采用的算法為weka中的J48算法，采用十折交叉驗(yàn)證進(jìn)行分類精度測(cè)定.

3.2 實(shí)驗(yàn)結(jié)果分析

根據(jù)以上實(shí)驗(yàn)結(jié)果，從以下3個(gè)方面進(jìn)行分析.

表2 約簡(jiǎn)屬性個(gè)數(shù)比較

注：PSO-GKFRA算法的屬性個(gè)數(shù)為5次實(shí)驗(yàn)的平均值.

表3 分類精度比較

注：1) 表中加粗的數(shù)值為當(dāng)前數(shù)據(jù)集的最高分類精度； 2) PSO-GKFRA算法的分類精度為5次實(shí)驗(yàn)的平均值.

1)σ的變化對(duì)約簡(jiǎn)屬性數(shù)目的影響

通過(guò)對(duì)表2的分析可以得出，隨著σ值的增加，應(yīng)用本文算法進(jìn)行屬性約簡(jiǎn)所得到的約簡(jiǎn)結(jié)果的屬性個(gè)數(shù)在sonar、iono、wine三個(gè)只包含數(shù)值型數(shù)據(jù)集上有明顯增加，而在僅包含6個(gè)數(shù)值型屬性的credit下沒(méi)有表現(xiàn)出明顯的約簡(jiǎn)后屬性個(gè)數(shù)的變化.σ在[0.1,1]變化時(shí)，sonar、iono、wine這三個(gè)數(shù)據(jù)集約簡(jiǎn)后，屬性個(gè)數(shù)與原始屬性個(gè)數(shù)之比分別在區(qū)間[7.4/60,40.8/60]=[12.3%,68%]、[6.2/34,24.2/34]=[18.2%,71.2%]、[4.6/13,10.6/13]=[35.4%,81.5%]進(jìn)行變動(dòng)，并且最小約簡(jiǎn)屬性個(gè)數(shù)均為個(gè)位數(shù).由此可以看出，在相同的σ值下，對(duì)屬性越多的數(shù)據(jù)集，本文算法屬性的約簡(jiǎn)率越高,具體見(jiàn)圖1.

圖1 iono數(shù)據(jù)集上粒子全局最優(yōu)點(diǎn)適應(yīng)度與迭代次數(shù)關(guān)系Fig.1 The relationship between global best fitness and iteration times of data set iono

圖2 σ=0.15時(shí)PSO-GKFRA算法在迭代次數(shù)為10、25、50下與FS-GKA的約簡(jiǎn)時(shí)間比較Fig.2 The running time of FS-GKA and PSO-GKFRA when iteration times=10,25,50,σ=0.15

2) 本文所提算法約簡(jiǎn)的有效性

從表3中可以看出，本文所提算法在σ取不同值時(shí)數(shù)據(jù)集sonar上的通過(guò)J48進(jìn)行分類的精度均優(yōu)于FS-GKA以及RS算法，且在所有σ值下均高于sonar、credit、iono的原始分類精度.此外在數(shù)據(jù)集credit上σ為0.1、0.5，iono上σ為0.15、0.5時(shí)的分類精度均高于FS-GKA以及RS算法，在數(shù)據(jù)集wine上分類精度均低于FS-GKA以及RS算法，但是最高分類精度也高于原始分類精度.由此可以看出，本文算法大部分?jǐn)?shù)據(jù)集下分類精度都優(yōu)于FS-GKA和RS算法，且相對(duì)于原始數(shù)據(jù)集都能進(jìn)行有效約簡(jiǎn).隨著σ的變化，σ在0.1或0.15時(shí)在所有數(shù)據(jù)集上取得了3次最優(yōu)分類精度，結(jié)合σ越小，約簡(jiǎn)后屬性越少的變化情況，說(shuō)明了本文算法在約簡(jiǎn)屬性的同時(shí)，能夠保持或增加數(shù)據(jù)集的分類精度，說(shuō)明了算法的有效性，并且給出了σ的一個(gè)較為合適的范圍[0.1,0.15]，具體見(jiàn)圖2.

3) 算法的約簡(jiǎn)效率

圖1中(a)和(b)子圖為在數(shù)據(jù)集iono上算法執(zhí)行迭代過(guò)程.圖1中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為粒子的適應(yīng)度，每一條線表示一次實(shí)驗(yàn)中全局最優(yōu)點(diǎn)適應(yīng)度隨迭代次數(shù)變化的過(guò)程，每一個(gè)σ都進(jìn)行了5次實(shí)驗(yàn).圖1(a)為本文算法在σ=0.1時(shí)對(duì)數(shù)據(jù)集iono上的計(jì)算收斂過(guò)程，圖1(b)為σ=1時(shí)在數(shù)據(jù)集iono上的計(jì)算收斂過(guò)程.從圖中可以看出，在σ=0.1和σ=1時(shí)，粒子均有一個(gè)較快的收斂過(guò)程，普遍在25次迭代以前就能達(dá)到最優(yōu)適應(yīng)度，而且實(shí)驗(yàn)選擇的粒子數(shù)只為數(shù)據(jù)集屬性數(shù)目的一半，說(shuō)明該算法收斂速度較快，粒子選擇較少，有較好的計(jì)算效率.此外，在兩種情況下最優(yōu)解與最差解的依賴度差距都在0.005左右，說(shuō)明該算法有較強(qiáng)的魯棒性，受初始粒子選擇影響小.通過(guò)圖2可以看到，本文算法在credit、sonar、iono下迭代次數(shù)為25、50次的運(yùn)行時(shí)間均高于FS-GKA算法，這是由于FS-GKA算法選擇出的屬性相對(duì)較少，約簡(jiǎn)率均大于67%，所以依賴度的計(jì)算次數(shù)就會(huì)比較少，消耗時(shí)間比較少.而對(duì)于本文算法，粒子群算法收斂的次數(shù)相對(duì)固定，所以不管選擇屬性多少，時(shí)間都會(huì)比較接近，所以在選擇屬性較少的情況下沒(méi)有優(yōu)勢(shì).在數(shù)據(jù)集wine上可以看出，本文算法在25次迭代時(shí)的時(shí)間低于FS-GKA算法，此時(shí)算法已基本收斂，因此效率高于FS-GKA算法，此時(shí)該算法約簡(jiǎn)率為54%.所以，本文算法在FS-GKA算法約簡(jiǎn)率較低時(shí)能夠取得一定時(shí)間上的優(yōu)勢(shì).

4 總結(jié)

本文所提出的基于粒子群算法的高斯核模糊粗糙集屬性約簡(jiǎn)算法在數(shù)值型數(shù)據(jù)集上，通過(guò)改變高斯核中的σ參數(shù)可以有效控制約簡(jiǎn)后的屬性個(gè)數(shù)，體現(xiàn)了模糊粗糙集能夠直接處理數(shù)值型數(shù)據(jù)的特性.通過(guò)與其他算法進(jìn)行比較，證明約簡(jiǎn)結(jié)果具有較好的分類精度，粒子的快速收斂說(shuō)明算法有較快的約簡(jiǎn)速度，本文所提屬性約簡(jiǎn)算法是有效的.