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

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

關(guān)鍵詞:遺傳算法，分類器，分類優(yōu)化，集成學習

中圖分類號: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

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

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

1 遺傳算法的特點

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

但是，由于進化的過程具有隨機性，遺傳算法搜索的結(jié)果具有一定的不穩(wěn)定性，因此，與傳統(tǒng)的優(yōu)化算法相比，遺傳算法的優(yōu)化效率相對較低。[3]

2 基于遺傳算法的分類優(yōu)化方法

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

2.1 數(shù)據(jù)和算法集的定義

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

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

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

2.3 如何使用遺傳算法對規(guī)則進行優(yōu)化

1) 編碼表示

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

2) 適應(yīng)函數(shù)

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

3) 選擇策略

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

4) 遺傳算子

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

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

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

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

5) 終止規(guī)則

遺傳算法循環(huán)執(zhí)行計算適應(yīng)值，選擇復(fù)制和應(yīng)用雜交和變異算子幾個步驟，直到找到滿足條件的解。

3 優(yōu)化結(jié)果討論

3.1 對使用一種分類方法的分類器進行優(yōu)化

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

3.2 對使用多種分類方法的分類器進行優(yōu)化

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

4 小結(jié)

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

參考文獻:

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

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

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

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

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