遺傳算法下的粗糙集屬性約簡算法及其有效性分析

鄭文彬 , 胡敏杰*， 何秋紅

(1.閩南師范大學 計算機學院, 福建 漳州 363000;2.閩南師范大學 福建省粒計算及其應用重點實驗室， 福建 漳州 363000)

0 引 言

粗糙集理論屬于數(shù)據(jù)挖掘方法中的高效方法，也是全新強有力對不確定性信息數(shù)學工具處理的方法。不確定性信息處理指的是對于不完整、模糊及不精準信息和組合信息實現(xiàn)處理，其被廣泛應用到機器學習、人工智能、故障診斷、模式識別及數(shù)據(jù)分析挖掘中。使用粗糙集約簡，能夠選擇條件屬性集，將條件屬性和決策不相關(guān)刪除，使用條件屬性約簡集替代原本屬性集。對數(shù)據(jù)量較大、屬性維度較高的信息系統(tǒng)，在人們可接受時間及具有有效資源背景下，根據(jù)遍歷及枚舉的方法無法得到最小屬性約簡，人們一般只能夠得到屬性近似約簡，粗糙集屬性約簡算法為目前高效方法，所以使屬性約簡算法效率提高，對粗糙集屬性約簡來說尤為重要。

1 粗糙集的基本理論

粗糙集理論指的是對不確定性處理的數(shù)學工具，也是全新軟計算方法。目前，粗糙集備受人們的重視，其有效性已經(jīng)被證實，屬于現(xiàn)代國際中人工智能理論和應用領(lǐng)域中的研究熱點。在多種實際系統(tǒng)中都具有不同程度的不確定性因素，收集數(shù)據(jù)常常具有不完整、不確定及噪聲，所以需要對其進行處理。粗糙集理論使知識理解劃分成為數(shù)據(jù)，每個被劃分的集合就是概念。粗糙集理論思想就是使用已知知識庫，使不確定及不精準知識使用已知知識庫刻畫，此理論和其他處理不精準及不確定問題理論的主要區(qū)別就是其不需要提供問題需要的數(shù)據(jù)集合之外信息，所以在處理問題不確定描述過程中較為客觀，因為此理論沒有處理不確定及不精準原始數(shù)據(jù)的機制，那么此理論及概率論等處理具有一定的互補性[1]。粗糙集理論的主要定義為：

1)決策表。決策表S指的是四元組S≤U,R,V,F>，其中的U指的是非空有限對象集，稱之為論域;R=C∪D的屬性集合，C指的是條件屬性集，D指的是結(jié)果屬性集，V指的是屬性值集合。F指的是信息函數(shù)，屬于U中每個對象x的屬性值。

2)不可分辨關(guān)系。在決策表S中，對每個屬性自己定義成為不可分辨關(guān)系，也就是：

IND(B)= {(x,y)∣(x,y)∈U2,

?b∈B(b(x)=b(y))}

3)正域。假設(shè)U屬于論域，P與Q指的是U中的兩個等價關(guān)系簇。

4)下近似集。對于每個概念中的X與不可分辨關(guān)系，包括在X中的最大可定義集都是以B進行確定的[2]。

2 遺傳算法分析

遺傳算法是將達爾文所提出的生物進化論和孟德爾提出的遺傳學理論，對自然界生物從低級到高級進行模擬的高級凈化過程，將初始種群作為起點，使用適者生存自然法則對個體進行選擇，并且使用變異、交叉等策略產(chǎn)生下一代種群，逐漸進化到滿足期望條件。遺傳算法將凈化思想作為基礎(chǔ)，常用來對復雜優(yōu)化問題進行解決。在遺傳算法不斷完善及發(fā)展的過程中，算法效率在不斷的提高。并且遺傳算法自身具備開放性，能夠使其和其他算法相互融合，以此提高算法的效率[3]。

2.1 種群和個體

種群為遺傳算法中求解問題解空間子集，種群中全部元素都屬于個體，其在迭代過程中在不斷的發(fā)生變化，但是種群個體數(shù)量不會發(fā)生變化。

2.2 編碼

編碼指的是將需要優(yōu)化的問題朝著遺傳算法容易處理的方式進行轉(zhuǎn)變，遺傳算法性能和編碼方式具有一定的聯(lián)系，所以選擇合適求解問題編碼方式是算法設(shè)計的主要內(nèi)容，常見編碼方式包括樹型編碼、二進制編碼、自適應編碼及實數(shù)編碼。

2.3 選擇

選擇指的是以個體適應度值的優(yōu)劣程度對種群個體進行選擇，也就是以一定概率Pr從上一代種群中實現(xiàn)個體選擇，之后進行操作。一般選擇方法包括隨機便利、輪盤賭和排序選擇等。遺傳算法中最早的選擇策略就是輪盤賭，此方法使種群中全部個體適應度的和作為輪盤，每個個體和輪盤中的某個區(qū)域進行對應，個體適應度越高，那么占比就會越高[4]。

2.4 適應度函數(shù)

適應度指的是種群個體對于環(huán)境適應程度，此指標主要是對種群中個體優(yōu)劣程度進行描述。適應度函數(shù)主要指的是個體在進化計算過程中的最優(yōu)解程度，遺傳算法在搜索過程中不利用外部信息評價，以此導致適應度成為種群個體評價的主要標準，所以選擇適應度函數(shù)和設(shè)計對遺傳算法具有一定的影響。

2.5 交叉

交叉操作指的是以一定概率Pc從種群種選擇種群個體構(gòu)成配對，之后將其基因串某部分實現(xiàn)交叉，以此產(chǎn)生全新種群個體過程。交叉操作不僅保持原本種群優(yōu)良個體特點，并且還使算法能夠?qū)θ禄蚩臻g進行搜索，使全新種群個體具備多樣性。二進制編碼大部分都是利用單點交叉策略。

假設(shè)每個個體都具有八位二進制表達，其中的兩個個體分別為F1=11100111，F(xiàn)2=10011010，假如交叉位置為3，那么個體低三位交換，得到全新個體：R1=11100010，R2=10011111。在進行個體交叉操作的過程中，對每次個體交叉操作概率進行控制[5]。

3 基于遺傳算法的粗糙集屬性約簡算法

3.1 遺傳約簡算法

在決策問題的過程中，尋找最小相對約簡具有重要的作用，結(jié)合遺傳算法和粗糙集，效果良好。

3.1.1 編碼方式

因為遺傳算法無法對空間解數(shù)據(jù)進行直接處理，所以利用編碼使其轉(zhuǎn)變成為遺傳空間基因型串結(jié)構(gòu)數(shù)據(jù)。利用固定長度二進制符號對群體個體進行表示，等位基因通過二值符號集{0,1}構(gòu)成。初始群體個體基因使用均勻發(fā)布隨機數(shù)表示，比如100111001000011100就為個體，此個體染色體長度為n=18，其中的每位都與條件屬性相互對應。如果取值為1,那么其指的是選擇某個對應條件屬性，如果取值為0，那么就表示不對相應條件屬性進行表示[6]。

3.1.2 個體適應度評價

將適應度函數(shù)定義成為：

式中： card(x)----染色體中1的數(shù)量，也就是染色體中條件屬性的數(shù)量;

n----染色體長度，也就是條件屬性數(shù)量;

k----決策屬性對于染色體條件屬性的依賴度。此函數(shù)能夠?qū)θ旧w控制最小約簡方向：k越大，表示決策屬性D對于屬性C依賴程度就會越強;在k為1的時候，決策信息通過條件信息進行確定。

利用card對染色體中條件屬性長度進行控制，以此所創(chuàng)建的適應度函數(shù)不僅能夠保證決策屬性對于整體條件屬性依賴度不改變，還能夠?qū)ふ揖哂袟l件屬性小的約簡。

3.1.3 選擇操作

利用適應度比例選擇方法，從目前群體中選擇優(yōu)良個體，將其到下一代群體中進行復制。具體流程為：

1)對群體中全部個體適應度總和進行計算；

2)對個體相對適應度大小進行計算，也就是個體到下一代群體遺傳的概率；

3)利用賭盤操作模擬對個體被選中數(shù)量進行確定[7]。

3.1.4 交叉操作

使用單點交叉算子進行執(zhí)行。對群體個體實現(xiàn)兩兩隨機配對，對每對相互配對個體隨機實現(xiàn)交叉點的設(shè)置，對每對配對個體根據(jù)假設(shè)的交叉概率Pc在交叉點中相互交換個體部分染色體，以此產(chǎn)生全新個體。

3.1.5 變異操作

利用變異算法使個體基因根據(jù)編譯概率指定變異點，使每個指定變異點中的屬性不變異，對其基因值進行取反運算，以此產(chǎn)生全新個體。

3.1.6 最優(yōu)保存

在得到全新個體以后，假如最壞個體適應值比上一代最好個體適應值要小，那么上一代最好個體替代最新最壞個體，此方法能夠保證算法收斂。

3.2 基于遺傳算法粗糙集屬性約簡算法

因為遺傳算法無法實現(xiàn)理解空間解數(shù)據(jù)直接處理，所以就要利用編碼使其轉(zhuǎn)變成為遺傳空間中基因型串結(jié)構(gòu)數(shù)據(jù)。文中利用固定長度二進制符號串表示群體個體，等位基因通過二值符號集構(gòu)成。初始群體中的個體基因值使用均值分布隨機數(shù)生成，比如1001100就是個體，其中的每位對應條件屬性。如果值為1，那么對相應條件屬性選擇；假如值為0，那么表示不對相應條件屬性選擇，以上個體相應屬性為{c1，c4，c5}[8]。

3.2.1 基于區(qū)分矩陣粗糙集約簡算法

因為二進制區(qū)分矩陣核和基于正區(qū)域核兩者定義不同，其不僅能夠在決策表中使用，也能夠應用到不相容決策表中。

對給定信息系統(tǒng)S=(U,A,V,F)定義成為區(qū)分矩陣M={Mij}，其中Mij表示為：

式中：d(xi)----U中全部和xi在關(guān)系中的等價元素相應決策屬性值創(chuàng)建的集合基數(shù)。

在簡化分區(qū)矩陣中使關(guān)系IND(C)值得出，求解方法復雜度為0(m*n*logn)，其中m指的是屬性集數(shù)量，n指的是U元素數(shù)量，但是并不理想。算法為：

1)輸入決策表S-(U,C,D,V,F,d),U={x1,x2,…,xn},C={c1,c2,…,cr}。

2)實現(xiàn)IND(C)的輸出。

3)對每個ci(i=1，2，…，r)得到f(xj)(j=1,2，…，n)的最小值和最大值，最大值為Mi，最小值為mi。

4)通過靜態(tài)鏈表對對象進行存儲，分別為x1，x2,…，xn，使表頭指針為x1。

5)For(i=1；i

7)如果Bi中的全部對象在決策屬性中的值相同，那么使Bi中的第一個對象融入到U中。

文中是遺傳算法和粗糙集結(jié)合實現(xiàn)約簡，免疫遺傳算法能夠結(jié)合生物免疫系統(tǒng)自適應識別及排除侵入機體抗原性異物功能，在遺傳算法中融入生物免疫系統(tǒng)記憶、學習、識別及多樣性的特點，免疫遺傳約簡算法的思路為：

1)主要步驟就是選擇適應度函數(shù)，之后創(chuàng)建適應度函數(shù)，表示為：

式中:r----染色體中的解；

n----染色體長度；

card(M)----M區(qū)分矩陣中的非空元素數(shù)量，滿足M。

適應度函數(shù)前部分中的驅(qū)使算法朝著屬性數(shù)最小方向進行搜索，后部分保證R為約簡[9]。

2)促進產(chǎn)生抗體。要想能夠促進抗體高適應度，就要抑制高濃度抗體?？贵w相似性利用抗體編碼歐幾里得距離進行表示，兩個抗體之間的歐幾里得距離表示為：

式中，d值在不斷的增加，那么兩者相似度就會越低。假如d為0，那么表示抗體一致。

3)選擇操作。使群體抗體利用輪盤賭選擇方式從目前抗體群中將優(yōu)良個體進行選擇，將其到下一代群體中進行復制。利用相似性矢量矩作為選擇概率，將其定義為：

式中:α、β----常數(shù)調(diào)節(jié)因子;

F(x)----適應度函數(shù)。

通過以上公式可以看出，此選擇概率不僅和抗體適應度具有密切的關(guān)系，還和抗體相似度具有密切的關(guān)系。此種抗體群體的選擇能夠避免出現(xiàn)抗體陷入局部最優(yōu)解問題，使抗體多樣性進行保證。

4)在算法中使用基本位變異算子及單點交叉算法，利用最優(yōu)保存策略對算法收斂進行保證。

①使用基數(shù)排序算法對矩陣進行簡化區(qū)分，假如決策屬性D和條件屬性C依賴度和屬性核進行確定，兩者相等，那么結(jié)束運算;如果不相等，進行以下操作。

②通過隨機產(chǎn)生m個長度n二進制串代表個體構(gòu)成初始抗體群，對核中的屬性相應值為1，否則值為0，對初始抗體群中的個體適應度進行計算。

③以上一步所計算的適應度，刺激適應度比較大的個體，對抗體濃度進行計算，刪除大濃度個體。

④對選擇個體概率進行計算，利用輪盤賭方法對個體進行選擇。

⑤根據(jù)交叉及變異概率產(chǎn)生全新個體，變異的時候保證核屬性相應基因位不出現(xiàn)變異。

⑥使用最優(yōu)保存策略取出父代個體中高適應度個體，將其到下一代個體中進行復制。

⑦如果使用十代最優(yōu)個體適應度不提高，那么計算終止。如果提高，轉(zhuǎn)到③繼續(xù)計算。

文中使用的算法在對等價關(guān)系進行計算的過程中使用基數(shù)排序思想，使等價關(guān)系計算時間復雜度表示為O(m*n)，空間復雜度表示為O(n)。在運算算法的過程中融合決策屬性對于條件屬性依賴度，并且和抗體濃度相互結(jié)合，對凈化過程個體多樣性進行維持，使搜索能力得到提高，避免出現(xiàn)局部最優(yōu)。

3.2.2 算法可行性分析

文中所提出的基于遺傳算法的粗糙集屬性約簡算法設(shè)計過程中，使用Sigmoid函數(shù)使連續(xù)優(yōu)化問題算法和粗糙屬性約簡問題相互聯(lián)系，以此對文中算法可操作性進行驗證。之后所分析的最優(yōu)更新操作都能夠提高文中算法約簡效果，并且使用適應度函數(shù)能夠?qū)ΨN群中接近約簡、屬性數(shù)較少粒子保存進行保證，所以通過多次迭代之后還能夠?qū)ふ易钚〖s簡，以對文中算法有效性進行保證[10]。

4 算法實驗

為了對文中算法有效性及可行性進行分析，列舉簡單實例對算法運算步驟進行說明，之后利用大數(shù)據(jù)約簡對算法有效性進行驗證。

其中的實例對象集合為U={U1，U2,…,U10}，條件屬性集表示為C={a，b，c，d，e}，決策屬性表示為{D}。

利用可辨識矩陣方法對屬性約簡結(jié)果進行該計算，將其作為對比信息，以下為屬性約簡步驟。假如粒子維數(shù)表示為5，種群數(shù)目表示為3，最大迭代次數(shù)表示為T=10。

首先，以屬性集C={a，b，c，d，e}對屬性依賴度值進行計算；之后，通過初始化粒子群和屬性，將其使用二進制方式進行表示：P1=10101，P2=00100，P3=00111。以粒子適應度值計算，設(shè)置全局最優(yōu)粒子為P1=10101。

決策信息系統(tǒng)實例見表1。

表1 決策信息系統(tǒng)實例

最后，實現(xiàn)遺傳算法循環(huán)迭代，因為迭代計算過程復雜，計算步驟結(jié)果描述見表2。

表2 計算步驟結(jié)果的描述

因為全局最優(yōu)粒子gbest連續(xù)四次迭代都沒有出現(xiàn)變化，所以運算終止，全局最優(yōu)位置為00110，也就是此決策表中的最小相對約簡屬性表示為cd。文中所設(shè)計的算法和相關(guān)研究學者算法對比表明，此算法能夠有效節(jié)約運算時間。

5 結(jié) 語

粗糙集理論屬于全新處理不確定性、含糊性問題的數(shù)學工具，其主要優(yōu)勢就是不需要相關(guān)數(shù)據(jù)預備及其他信息，所以粗糙集理論因為自身的優(yōu)勢備受人們重視，其和遺傳算法相互結(jié)合成為研究的重點內(nèi)容。屬性約簡為粗糙集理論中的主要研究內(nèi)容，但是尋找決策表最小約簡為較難的問題。文中所提出的基于遺傳算法粗糙集約簡方法，不僅能夠提高算法的局部搜索能力，還能夠保證此算法全局尋優(yōu)特點。實驗結(jié)果表明，此算法不僅能夠?qū)崿F(xiàn)決策表約簡，在對大規(guī)模數(shù)據(jù)計算的時候節(jié)約時間。在今后工作過程中，要對遺傳約簡算法繼續(xù)進行完善。