[摘 要] 在簡單遺傳算法的基礎(chǔ)上，提出了一種基于種間競爭的分類規(guī)則挖掘算法。通過改進適應(yīng)度函數(shù)、雙群體結(jié)構(gòu)和遺傳算子等方法，將其應(yīng)用于收入分類的數(shù)據(jù)挖掘研究中，能夠高效地得到性能好的規(guī)則。

[關(guān)鍵詞] 遺傳算法 分類規(guī)則 種間競爭

一、引言

遺傳算法(Genetic Algorithm， GA)是由美國J.Holland教授于1975年在其論文“自然系統(tǒng)和人工系統(tǒng)的適配”中提出，并已得到了廣泛的應(yīng)用，不過它仍然存在過早收斂和局部最優(yōu)等問題。本文在引入“種間競爭”的思想的同時對其進行改進，在一定程度上解決了其“早熟”的問題?；诜N間競爭的基本遺傳算法的計算步驟大部分與單種群基本遺傳算法一致，不同的是在產(chǎn)生初始群體時，不是產(chǎn)生1個群體，而是2個群體。在遺傳操作后插入群體之間的信息交換，即種間競爭。

二、種間競爭算法的改進

1.改進思想

(1)初始種群:個體按照適應(yīng)值降序排列，將前三分之一放入群體1而剩余的三分之二放入群體2。群體1比群體2優(yōu)秀，這樣就能較快地在群體1中挖掘到優(yōu)秀的個體。

(2)群間比較和交換方法:相隔幾代相互替換個體一次，本文是用群體2中較優(yōu)秀的個體去交換1中較差的個體，這樣既保持了群體1的多樣性又保持了其優(yōu)秀性。

(3)自適應(yīng)變異算子：變異概率（Pm）能夠控制新基因?qū)肴后w的比例。Srinivas等提出變異概率自適應(yīng)改變的方法:當(dāng)種群各個個體適應(yīng)度差別小并趨于收斂時，增大Pm參數(shù)值；當(dāng)種群適應(yīng)度較為發(fā)散時，降低Pm參數(shù)，使個體趨于收斂。

(4)適應(yīng)度函數(shù)：本文采用適應(yīng)度函數(shù) F=W1*Conf+W2*Sup（0w2，且W1+W2=1），即：F= W1*Conf+ (1-W1)*Sup。一般W1取0.7，這樣得到的規(guī)則正確性高，而且也不會產(chǎn)生大量的細(xì)節(jié)規(guī)則。

2.改進算法描述

Step1：求個體適應(yīng)值并降序排列并生成兩個初始群體。

Step2：兩個群體獨立執(zhí)行遺傳算子產(chǎn)生后代。

Step3：種間競爭：競爭頻率C，群間比較個數(shù)R。

Step3.1：若進化代數(shù)能整除C進入種間競爭。

Step3.2：排序：群體1升序，群體2降序。

Step3.3：群間比較：群體1中最差的R個體同群體2中最好的R個體進行比較，再將其中優(yōu)秀的個體都放到群體1中。

Step3.4:當(dāng)比較個數(shù)大于等于R或群體1中當(dāng)前個體適應(yīng)值已經(jīng)優(yōu)于群體2中的，則執(zhí)行Step4，否則循環(huán)執(zhí)行Step3.2～Step3.4。

Step4:兩群體分別進入下一代的基本遺傳操作。待算法完成后從群體1中簡化并打印分類規(guī)則。

三、改進算法在收入分類規(guī)則挖掘中的應(yīng)用

1.系統(tǒng)運行環(huán)境和測試用的數(shù)據(jù)

算法用Microsoft Visual C++ 6.0開發(fā)實現(xiàn)，并使用了UCI(University of California， Irvine)機器學(xué)習(xí)數(shù)據(jù)庫中的收入統(tǒng)計(adult)數(shù)據(jù)集進行實驗。此數(shù)據(jù)集用于統(tǒng)計收入“>50K”和“<=50K”的人口模式。

2.數(shù)據(jù)預(yù)處理

分別對數(shù)據(jù)進行了空值、簡化屬性、離散化等預(yù)處理。并隨機地將數(shù)據(jù)集分為訓(xùn)練集和測試集，訓(xùn)練集占三分之二，共32561條實例，測試集占三分之一，共16281條實例。

3.算法參數(shù)

種群大小為100，最大進化代數(shù)為50，交叉概率PC為0.5，適應(yīng)度函數(shù)權(quán)值W1為0.7，競爭頻率C為3，替換個數(shù)R為5。

4.實驗結(jié)果

算法運行30次，在測試集上準(zhǔn)確率最高的規(guī)則集如下。分別列出規(guī)則、訓(xùn)練集上的適應(yīng)度和測試集上的適應(yīng)度。

IF(marital-status=Never-married) THEN class=”<=50k” 0.952 0.951

IF(workclass=private)and (native-country=United-States) THEN class=”<=50k” 0.846 0.839

IF(workclass=private)and(sex=male) THEN class=”<=50k” 0.827 0.812

IF(marital-status=Married-civ-spouse)and(native-country=United-States) THEN class=”>50K”0.712 0.707

如果一條規(guī)則在測試集上的適應(yīng)度與訓(xùn)練集上適應(yīng)度相差不超過0.1，就認(rèn)為這條規(guī)則能夠很好地推廣到測試集上。列出的規(guī)則集大部分能很好地推廣到測試集上。關(guān)于“<=50K”的模式適應(yīng)度較高，而關(guān)于“>50K”的模式適應(yīng)度較低，通過觀察數(shù)據(jù)集可以看出，類“>50K”的實例在數(shù)據(jù)集中所占的比例較低，只占總數(shù)據(jù)集的23.93%。

四、結(jié)束語

本文在簡單遺傳算法的基礎(chǔ)上，引入并改進了基于種間競爭的分類規(guī)則挖掘算法。從而避免了種群內(nèi)部的“封閉競爭”，提高了全局和局部搜索能力和進化速度。但算法引入了一些新的參數(shù)，如何優(yōu)化設(shè)置這些參數(shù)還要做進一步的研究。

參考文獻:

[1]John H．Holland ，adaptation in natural and artificial systems[m]， University of Michigan press， 1975

[2]陳建能:基于種間競爭的遺傳算法的改進.福建農(nóng)林大學(xué)學(xué)報，2003， 32(1):127～129

[3]M Srinivas， L Patnaik， Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm IEEE Trans. On Systems， Man， and Cybernetics， 24， pp 656～666， 1994

[4]王小平 曹立明:遺傳算法－理論、應(yīng)用與軟件實現(xiàn). 西安:西安交通大學(xué)出版社，2002，74～76