基于遺傳算法的分類方法討論

摘要:討論在分類器系統中結合遺傳算法，使用遺傳算法分別對使用一種分類方法和多種分類方法的分類器進行優化。對只使用一種分類方法的分類器，使用遺傳算法進行優化后，可以得到更高的精度;對于使用多種分類方法的分類器，經過優化后，分類結果精度更高，且具有更好的可理解性。

關鍵詞:遺傳算法，分類器，分類優化，集成學習

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2009)33-9615-02

Discuss the Method of Classification with Genetic Algorithm

WANG Xin-Xin

(Software College， MinJiang University， FuZhou 350011， China)

Abstract: In the classifier system， applied genetic algorithm(GA) to optimized the classifier system which is use a single classify method or multiple classify methods. For the first classifier system， GA make the better precision; and for the other one， GA can make the classifier system to be more precise and apprehensive.

Key words: genetic algorithm(GA); classifier system; classify optimization; ensemble learning

分類問題是集成學習的基本研究問題，即對一個分類器輸入一個實例的特征集，然后對這些特征進行判斷，對這個樣本進行歸類并輸出。在醫療診斷、語音識別、數據挖掘、人像識別等領域都有廣泛的應用。

J.H.Holland于1975年出版了《Adaptation in Natural and Artificial Systems》[1]，標志著遺傳算法的正式產生。遺傳算法是一種概率搜索算法，利用編碼技術作用于被稱為是染色體的二進制數串，其基本思想是模擬這些串組成的群體的進化過程。遺傳算法通過有組織的然而是隨機的信息交換來重新組合那些適應性好的串，在每一代中，利用上一代串結構中適應性好的位和串來生成一個新的串的群體。這是一類隨機算法，但不是簡單地隨機走動，而是利用已有的信息來搜尋那些有希望改善質量的串，這個過程類似于自然進化。[2]

1 遺傳算法的特點

與其他傳統的優化算法相比，遺傳算法在搜索的過程中采用群體搜索方式，有利于達到全局最優。依據個體相對優劣的適應度指標進行搜索，即使所定義的適應函數存在不連續、不規則或有噪聲等情況，也可進行處理。通過在遺產算法中使用雜交算子，可將算法的注意力更多地集中到搜索空間中期望值高的那部分;同時，為了避免局部最優，在遺傳算法中引入變異，這樣既可在當前附近找到更好的解得同時保持群體多樣性，有利于群體的繼續優化。[2]

但是，由于進化的過程具有隨機性，遺傳算法搜索的結果具有一定的不穩定性，因此，與傳統的優化算法相比，遺傳算法的優化效率相對較低。[3]

2 基于遺傳算法的分類優化方法

文獻[4]中提出了一種基于遺傳算法的分類優化方法。該方法針對兩種分類器進行優化。一種分類器采用一種分類方法，使用遺傳算法對分類結果進行優化。另一種是在分類器中使用幾種不同的分類方法，使用遺傳算法作為綜合方法對分類結果進行綜合優化。在一套訓練集上使用一種方法，由此產生一個唯一的模型，不同的方法在同一套訓練集上產生的模型也不一定相同。有些方法在某一類任務上的性能很好，但是在另外一類任務上的性能則較差，它們的預測結果有可能是錯的，因此使用遺傳算法可以將多種分類方法結合起來提高精度。

2.1 數據和算法集的定義

數據集合L={xn，yn}，n=1，…，N}，其中，xi是輸入屬性，yi是輸出屬性，N是例子數目。設有M個學習算法，分別用A1，A2，…，AM表示。A(R，S)，其中A是算法，R是算法空間，S是算法搜索的空間。算法對數據集合進行學習，得到不同的學習結果，利用遺傳算法對這些結果進行結合，得到一個綜合結果。

2.2 基于遺傳算法的組合方法框架

在L0層中，每個算法對輸入的訓練集數據進行訓練，各自生成一套對分類問題的表示，利用規則產生器對將L0層中關于分類問題的表達轉換為規則，然后作為L1層的輸入。在L1層中使用遺傳算法對規則集進行綜合，生成最終分類器。這種方法綜合各分類器的優點，其結果精度高于各單個分類器，用規則集表示其結果。

2.3 如何使用遺傳算法對規則進行優化

1) 編碼表示

GlodBerg在上個世紀80年代對遺傳算法進行歸納，在文獻[5]中總結了遺傳算法的基本框架。根據該算法，一個個體代表問題的一組解，每一個個體含有表達全部解的一組規則集。規則由條件和結論組成:“if (x1，y1) and (x2，y2)，…，and (xn，yn) then Cj”每一個規則用一個染色體表示。

2) 適應函數

適應函數由匹配值和不匹配值兩個參數組成，當分類器能對規則進行正確識別并與結果匹配，則增加匹配值;若不能，則增加不匹配值;如果條件無法識別，則這兩個參數都不變。

3) 選擇策略

利用遺傳算法來產生新的規則，采用限制交配策略，對于同類規則，可進行交配進化，而對于結論相同的規則，則只在其條件部分進行進化。對于結論相同的規則只在條件部分進行進化的目的是為了防止出現不收斂的情況。

4) 遺傳算子

選擇算子:選擇算子從群體中選擇優秀的個體，淘汰劣質的個體，將適應度高的候選解遺傳到下一代。在選擇的過程中以適應度為依據進行選擇，獨立于編碼方式。

雜交算子:雜交是按照一定的概率將兩個父代個體的部分結構加以交換重組，然后產生新的個體。在本文中，個體間同類規則的相同基因位進行交叉。

圖2對遺傳算法的交叉算子進行描述。

變異算子:變異算子使個體中某些基因發生突變，遺傳算法中的變異運算通過位的取反操作實現。在本文中，通過對屬性邊界值進行突變實現。圖3描述了變異算子。

5) 終止規則

遺傳算法循環執行計算適應值，選擇復制和應用雜交和變異算子幾個步驟，直到找到滿足條件的解。

3 優化結果討論

3.1 對使用一種分類方法的分類器進行優化

文獻[4]表明，遺傳算法優化后的精度優于使用單個算法的精度。對于屬性值十分接近的分類目標，使用單一屬性生成的規則進行區分是很難實現的，而只有采用屬性值的組合才能實現這類分類目標的區分。

3.2 對使用多種分類方法的分類器進行優化

在文獻[4]中，使用遺傳算法對基于C5.0和神經網絡的規則集進行優化。優化后，得到兩套規則集，基于C5.0的規則集邊界值發生改變，新的規則在精度上比原來更高。而基于神經網絡的規則集在形式上沒有發生改變。對兩種規則集進行比較，發現基于C5.0的規則集和基于神經網絡的規則集均具有較高的精度，但是從理解性的方面考慮，基于C5.0的規則集既有較好的可理解度。

4 小結

該文討論了一種基于遺傳算法的分類器優化方法，在分類技術中結合遺傳算法可以得到更好的分類效果，得到的分類結果更精確、易于理解。用分類技術處理原始數據集從而得到初步的規則集，而遺傳算法通過優化規則條件的部分邊界值提高了分類的精度。這種方法具有較好的魯棒性和可延展性，當給定的邊界值與其正確的位置相距很遠，也可通過遺傳算法對全局進行搜索得到解空間的最優解;如果在分類器中采用新的分類方法，可將分類的結果轉化為規則集作為遺傳算法輸入，這些新的規則集與已有的規則集一起進行演化，從而得到更好的結果。

參考文獻:

[1] Holland J H. Adaptation in Natural and Artificial Systems[M]. MIT Press，1992.

[2] 劉勇，康立山，陳毓屏.非數值并行算法遺傳算法[M].2冊.北京:科學出版社，1995.

[3] 孫瑞祥，屈梁生.進化計算的過去、現在與未來[C]//進化計算研究生論壇論文集.西安:西安交通大學，2001.

[4] 季文赟，周傲英，張亮，等.一種基于遺傳算法的優化分類器的方法[J].軟件學報，2002，13(2).

[5] Glodberg D. Genetic algorithm in search， optimization and machine learning [M].MA: Addsion-Wesley Publishing，1989.