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

戴上平，劉素軍，鄭素菲

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

1 引言

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

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

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

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

2.1 常用粗糙集基本定義

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

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

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

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

(1)

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

定義4若S=(U,A,V,F)是一個知識表達系統，當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]的解集是從經過基因編碼的一定數目個體組成的一個種群開始，該種群中的各個體以染色體為載體，采用固定大小的二進制串表示其基因值。長度為15的染色體可用Y=110100101011001來表達。

2.2.2 選擇操作

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

2.2.3 交叉操作

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

2.2.4 變異操作

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

2.3 粒子群算法

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

(2)

(3)

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

3 GA-PSO屬性約簡算法

3.1 編碼方法

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

(4)

(5)

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

(6)

即將屬性編碼為粒子。

3.2 粒子適應度函數

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

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

(7)

(8)

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

(9)

3.3 遺傳操作與粒子更新

(10)

(11)

(12)

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

3.4 局部最優與全局最優

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

Pbesti=max(Pbesti,Fitness(i))

(13)

Gbest=max(Pbesti,Gbest)

(14)

3.5 GA-PSO約簡算法執行過程

輸入：一個決策表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]，根據公式(6)初始化各粒子，設置最大迭代次數T=80。

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

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

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

4 實驗結果及分析

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

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

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

5 結束語

近年來粗糙集理論以其獨特的優勢引起了廣泛的關注，并成功應用于臨床醫療診斷、量子粒子群[7]、預測控制、機器學習和數據挖掘[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] 代建華,李元香.一種基于粗糙集的決策系統屬性約簡算法[J].小型微型計算機系統,2003,3(3):523-526.

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

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

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

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