基于GA-PSO的粗糙集屬性約簡算法*

戴上平，劉素軍，鄭素菲

(華中師范大學計算機學院，湖北 武漢 430079)

1 引言

粗糙集理論[1]是一種新的數(shù)學理論，用于處理不準確和不完整的數(shù)據(jù)。它已被廣泛應用在人工智能、知識和數(shù)據(jù)發(fā)現(xiàn)、模式識別和分類、數(shù)據(jù)分析和其他不精確推理的方面。其通過知識約簡導出問題的決策或分類規(guī)則來保持穩(wěn)定的分類能力。在該理論中屬性約簡是一個核心問題，它是指信息系統(tǒng)在保持能力或知識的歸類決定沒有改變的同時，刪除不重要的或不相關的屬性。

遺傳算法GA(Genetic-Algorithm)具有隱含并行性、魯棒性、可擴展性等優(yōu)點，擅長全局搜索，除了適應度計算外，幾乎所有的遺傳操作都建立在全局統(tǒng)計處理的基礎上。這樣使得全局的重復計算量大且易“早熟”。遺傳算法在屬性約簡過程中采用不同的編碼方法，會產生不同的問題，從而導致沒有根據(jù)的積木假設，最終使得屬性約簡時GA過早收斂難以達到全局最優(yōu)。粒子群優(yōu)化PSO(Particle-Swarm-Optimization)算法是一種通過用無質量無體積的粒子作為個體，同時為每個粒子提供簡單行為規(guī)則使整個粒子群呈現(xiàn)出一定特性，以解決復雜的優(yōu)化問題的進化計算技術。

在粗糙集屬性約簡[2]中，GA與PSO在進化過程中均能保留和利用位置的信息，但除此之外，PSO算法還能利用速度(即位置的變化過程)信息，使得PSO比GA收斂于最優(yōu)解的速度更快。粒子群約簡算法過程中，粒子群在迭代時容易陷入到局部極值點中，導致得不到全局最優(yōu)解，使得最后的約簡結果不是最小相對屬性集。針對遺傳約簡與粒子群約簡的不足，本文提出了一種新的約簡算法，即：基于GA-PSO的粗糙集屬性約簡算法。

2 粗糙集基本知識與GA、PSO的引入

2.1 常用粗糙集基本定義

定義1設S=(U,A,V,F)為一個信息系統(tǒng)，又稱知識表示系統(tǒng)。其中，U={U1,U2,…,U|U|}為論域對象空間，U是有限非空集合，稱為；A={ɑ1,ɑ2,…,ɑ|A|}為屬性的有限非空集合；V=∪Vɑ，其中ɑ∈A，Vɑ為屬性ɑ的值域；F：U×A→V為信息函數(shù)，對于?ɑ∈A、?x∈U，F(xiàn)(x,ɑ)∈Vɑ，它指定了U中每一對象的屬性值。若A中的屬性又可分為兩個不相交的子集，即條件屬性集C和決策屬性集D，即：A=C∪D,C∩D=?，則S稱為決策表。

定義2給定一個知識表示系統(tǒng)S=(U,A,V,F)，P?A，X?U，x?U，集合X關于I的下近似、上近似、負區(qū)及邊界區(qū)分別為：

negP(X)=∪{x∈U:I(x)∩X≠?}

定義3設知識表達系統(tǒng)S=(U,A,V,F)，A=C∪D,C∩D=?，條件屬性C對決策屬性D的支持度(決策屬性D對條件屬性C的依賴度)定義為：

(1)

式(1)稱D在K程度上依賴于C，其中|·|指集合包含的元素個數(shù)，一般取0≤K≤1。當屬性集中的屬性值決定著屬性的所有屬性值時，本文把K取值為1；當屬性集中的屬性值決定著屬性中的部分屬性值時，K的取值范圍小于1。

定義4若S=(U,A,V,F)是一個知識表達系統(tǒng)，當B為C的一個(相對于決策屬性D的)相對約簡時，應滿足條件：B?C，若KB=KC，且不存在R?B，使得KR=KB，此時約簡結果可能有多個。相對約簡的集合記為redD(C)，所有C屬性約簡的交集記為Core(C)(又稱C的核)，且有CoreD(C)=∩redD(C)。最小約簡指含有最少屬性的約簡。

2.2 遺傳算法

2.2.1 染色體編碼

遺傳算法[3]的解集是從經過基因編碼的一定數(shù)目個體組成的一個種群開始，該種群中的各個體以染色體為載體，采用固定大小的二進制串表示其基因值。長度為15的染色體可用Y=110100101011001來表達。

2.2.2 選擇操作

從種群中選擇出質量優(yōu)的個體使之作為父代再生優(yōu)化同時淘汰劣質個體的操作稱為選擇操作。輪盤賭方法選擇算子是傳統(tǒng)的遺傳屬性約簡中的選擇運算，在該操作中，各個體的選擇概率和其適應度值成比例，其適應度值比例越大，該染色體代表的種群個體被選擇交配的機會也越大。

2.2.3 交叉操作

交叉操作是把兩個父代個體的部分結構加以替換重組而生成新的個體。交叉運算根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合。在使用單點交叉操作中，從個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新的染色體個體。該處用到的雙親染色體由輪盤賭方法隨機選出，參照依據(jù)是每個染色體適應度值。

2.2.4 變異操作

變異操作是對群體中的個體串的某些基因座上的基因值作變動。其目的是保證遺傳操作具有局部搜索能力的同時又要維持群體的多樣性，進而保證在加速向最優(yōu)解收斂的同時又能防止出現(xiàn)未成熟收斂。常用的變異運算是根據(jù)變異概率Pm隨機選擇染色體的個體，實現(xiàn)在某些位置進行0，1翻轉。

2.3 粒子群算法

粒子群算法的數(shù)學思想為：在D維搜索空間中，有一個群體由m個粒子組成，第i個粒子(i=1,2,…,m)的位置表示為Xi=(χi1,χi2,…,χid)，速度表示為Vi=(υi1,υi2,…,υid)。第i個粒子搜索到的最優(yōu)位置為Pbesti=(ρbesti1,ρbesti2,…,ρbestid)，整個粒子搜索到的最優(yōu)位置記為Gbest=(gbesti1,gbesti2,…,gbestid)。綜上定義，粒子群算法的進化方程描述為：

(2)

(3)

其中，i= 1,2,…,m;d= 1,2,…,D;t為當前迭代次數(shù);慣性權重ω取非負常數(shù);τ1、τ2為加速因子,取非負常數(shù)，用來調節(jié)粒子向全局最優(yōu)粒子和個體最優(yōu)粒子方向飛行的步長;γ1、γ2為[0,1]內兩個相互獨立的均勻分布的隨機函數(shù)。

3 GA-PSO屬性約簡算法

3.1 編碼方法

ωk=KCore(C)∪ck-KCore(C)

(4)

(5)

屬性ck的對應位lk取0或1由公式(6)決定：

(6)

即將屬性編碼為粒子。

3.2 粒子適應度函數(shù)

適應值函數(shù)的形式決定著群體的進化行為，也是對粒子的適應性進行評價的唯一確定指標。為控制粒子朝著約簡的方向發(fā)展，保證所得到的粒子是一個約簡。本文定義適應度函數(shù)與平均適應度函數(shù)如下：

Fitness(P)=k1*(KP/KC)+k2*(1-KP)

(7)

(8)

其中，k1的大小決定著待約簡粒子適應值的大小，與之成正比。種群中優(yōu)良粒子保留下來的概率越大，其對應的取值也越大。而函數(shù)屬性數(shù)目的大小或者約簡屬性數(shù)目的大小由k2判定，其值越大，它的適應度值也越大。式(9)決定k1與k2的大小。當KP/KC的值為“1”時，得到的屬性集是一個約簡。

(9)

3.3 遺傳操作與粒子更新

(10)

(11)

(12)

權重因子τ1、τ2和隨機數(shù)γ1、γ2決定變異的程度與方向，式(12)使得變異有了學習能力。

3.4 局部最優(yōu)與全局最優(yōu)

局部最優(yōu)是個體極值，即粒子在迭代更新過程中自身所找到的最優(yōu)解。全局最優(yōu)則是全局極值，即整個種群在進化迭代中所找到的最優(yōu)解也就是適應度值最好的一個位置。在GA-PSO算法中，局部最優(yōu)需要與粒子新的適應度值進行比較，由式(13)決定。全局最優(yōu)為種群中最優(yōu)質粒子，按式(14) 與每個粒子的局部最優(yōu)進行比較求得。

Pbesti=max(Pbesti,Fitness(i))

(13)

Gbest=max(Pbesti,Gbest)

(14)

3.5 GA-PSO約簡算法執(zhí)行過程

輸入：一個決策表S=(U,A,V,F)，A=C∪D，C是條件屬性集，D是決策屬性集。

輸出：此決策表最小相對屬性約簡。

步驟1由式(1)計算出決策屬性D關于條件屬性C的支持度KC(D)；

步驟2令Core(C) =?，逐個去掉一個屬性c∈C，若KC-c≠Kc，則Core(C)=Core(C)∪{c}。若KCore(D) =Kc(D)，則Core(C)即為最小相對約簡。否則，轉步驟3。

步驟3初始化粒子。除去核屬性，由式(4)計算其余各屬性權重，并把求得的權重按照公式(5)映射到[0,1]，根據(jù)公式(6)初始化各粒子，設置最大迭代次數(shù)T=80。

步驟4更新粒子群。由式(7)計算第i個粒子在t時刻的適應值Fitness(i)，由式(8)計算當前種群的平均適應度AF。由式(11)和式(12)更新粒子位置，由式(13)更新局部最優(yōu)值，由式(14)更新全局最優(yōu)粒子，取種群中粒子最優(yōu)適應度為全局最優(yōu)粒子。

步驟5將種群中每個粒子的適應度值與當前種群的AF值進行比較，適應度大于AF的粒子給予保留，適應度小于AF的粒子，用上面提到的均勻交叉法交叉、變異操作到變異算子。

步驟6判斷是否滿足終止條件，若達到最大迭代次數(shù)或所求得的結果不再發(fā)生變化，則終止迭代，否則轉步驟4。

4 實驗結果及分析

為了驗證本文算法(記為GA-PSO屬性約簡)的有效性和正確性，本文用UCI機器學習數(shù)據(jù)庫中的標準數(shù)據(jù)集作為測試數(shù)據(jù)，從UCI數(shù)據(jù)庫中分別選取具有低、中、高維特征的Iris、Zoo、Sogbeanbarge三個數(shù)據(jù)集作為算例進行計算，并同文獻[5]的基于遺傳算法的粗糙集屬性約簡算法(記為GA屬性約簡)與文獻[6]的基于粒子群優(yōu)化算法的粗糙集屬性約簡(記為PSO屬性約簡)在屬性約簡過程中適應度值和計算平均時間開銷兩方面進行比較。

對本文提出的GA-PSO算法，參數(shù)值分別取變異概率Pm=0.2，交叉概率Pc=0.75，m=25，在Windows7、內存為2 GB的PC機上運行10次;GA約簡算法與粒子群約簡算法參數(shù)設置參照參考文獻[5,6]，最大迭代次數(shù)均設置為80。三組實驗均在同一臺PC機上運行，求得最小相對屬性約簡集與平均運行時間。三種算法的屬性約簡結果如表1所示，為了更好地呈現(xiàn)出進化過程，圖1給出了具體進化過程中的適應度值曲線；為了觀察收斂速度，圖2給出了三種算法進行相同迭代次數(shù)的約簡實驗10次的運行時間曲線圖。

Table 1 Results of attribute reduction

Figure 1 Fitness value curve of Zoo evolution圖1 Zoo進化過程適應度值變化曲線

Figure 2 Numbers of experiments vs run time about Zoo reduction圖2 Zoo約簡實驗不同次數(shù)運行時間曲線

由實驗結果可以看出，GA-PSO約簡算法與遺傳算法相比，運行時間短且能得到最小相對屬性集；與粒子群算法相比，雖然運行時間相對較長，但是，其約簡是以犧牲時間為代價獲得最小相對屬性集，進而證實本文提出的算法是有效的。本算法在保證運行速度相對快的前提下，能得到最小相對屬性集。

5 結束語

近年來粗糙集理論以其獨特的優(yōu)勢引起了廣泛的關注，并成功應用于臨床醫(yī)療診斷、量子粒子群[7]、預測控制、機器學習和數(shù)據(jù)挖掘[8]等諸多領域。粗糙集理論與人工智能算法相結合也是其應用范圍之一。但是，粗糙集理論中求解最小約簡是NP-hard 問題。本文提出了一種基于GA-PSO的粗糙集屬性約簡算法，在跨越局部搜索障礙的同時又保證了最小相對屬性約簡。實驗表明，該算法在決策表屬性約簡中的有效性和實用性。本算法雖然求得了最小相對屬性約簡集，但是以犧牲時間為代價，如何高效地對決策表進行屬性約簡是今后進一步研究的方向。

[1] Pawak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):314-356.

[2] Dai Jian-hua,Li Yuan-xiang.An algorithm for reduction of attributes in decision system based on rough set[J].Mini-Micro System,2003,3(3):523-526.(in Chinese)

[3] Xiao Hou-guo,Sang Lin.Rough set attribute reduction algorithm based on GA and its application[J].Computer Engineering and Applications,2008,44(15):228-230.(in Chinese)

[4] Walczak W,Massart D L.Tutorial,rough sets theory[J].Chemo Metrics and Intelligent Laboratory Systems,1999,47:1-16.

[5] Yan Yan,Yang Hui-zhong. Rough set attribute reduction algorithm based on GA [J].Computer Engineering and Applications,2007,43(31):156-158.(in Chinese)

[6] Dai Jian-hua,Chen Wei-dong,Gu Hong-ying,et al.Particle swarm algorithm for minimal attribute reduction of decision data tables[C]∥Proc of Multi-Symposiums on Computer and Computational Sciences,2006:572-575.

[7] Wang Jia-yang,Xie Ying.Minimal attribute reduction algorithm based on quantum particle swarm optimization[J].Computer Engineering,2009,35(12):148-150.(in Chinese)

[8] Huang Xiao-fang.Algorithm of decision tree in data mining and its application[J].O.I.Automation,2005,24(2):35-36.(in Chinese)

附中文參考文獻：

[2] 代建華,李元香.一種基于粗糙集的決策系統(tǒng)屬性約簡算法[J].小型微型計算機系統(tǒng),2003,3(3):523-526.

[3] 肖厚國,桑琳.基于遺傳算法的粗糙集屬性約簡及其應用[J].計算機工程與應用,2008,44(15):228-230.

[5] 顏艷,楊慧中.基于遺傳算法的粗糙集屬性約簡算法[J].計算機工程與應用,2007,43(31):156-158.

[7] 王加陽,謝穎.基于量子粒子群優(yōu)化的最小屬性約簡算法[J].計算機工程,2009,35(12):148-150.

[8] 黃曉芳.數(shù)據(jù)挖掘中決策樹算法及其應用[J].兵工自動化,2005,24(2):35-36.