基于非隨機初始種群遺傳算法的學(xué)習(xí)分類器系統(tǒng)

薛愈潔

摘 要： 學(xué)習(xí)分類器系統(tǒng)能夠通過簡單位串規(guī)則的學(xué)習(xí)有效地引導(dǎo)個體在一個環(huán)境中的行為。通過分析基于遺傳算法的學(xué)習(xí)分類器系統(tǒng)的實現(xiàn)原理，提出一種以規(guī)則為基礎(chǔ)的分類系統(tǒng)，借助訓(xùn)練數(shù)據(jù)集來實現(xiàn)類別的精確描述，并以數(shù)據(jù)挖掘中的基準數(shù)據(jù)鳶尾花卉數(shù)據(jù)集作為應(yīng)用對象，實現(xiàn)學(xué)習(xí)分類器中的消息與分類器系統(tǒng)匹配、桶隊列算法信用分配以及基于遺傳算法的規(guī)則發(fā)現(xiàn)。仿真結(jié)果表明，通過學(xué)習(xí)分類器系統(tǒng)優(yōu)化后，鳶尾花分類的精度好于單個算法的精度。

關(guān)鍵詞： 學(xué)習(xí)分類器； 遺傳算法； 桶隊列算法； 鳶尾花分類

中圖分類號：TP301 文獻標志碼：A 文章編號：1006-8228（2018）03-60-03

The learning classifier system based on non-random initial population genetic algorithm

Xue Yujie

（School of Computer Engineering， Taiyuan University， Taiyuan， Shanxi 030001， China）

Abstract： Learning classifier system can guide the individual behavior in a random environment with simple string of rule learning. A classification system based on the rules is proposed by analyzing the architecture of learning classifier system based on genetic algorithm with training data set to improve the accurate of the classification. And the matching of message and classifier in the learning classifier system， the credit allocation in bucket-brigade algorithm and the rule discovery based on genetic algorithm are implemented by using the benchmark data in iris flower dataset. The simulation results show that the accuracy of classification is better than the precision of a single algorithm after learning classifier system optimization.

Key words： learning classifier； genetic algorithm； bucket-brigade algorithm； classification of iris flower

0 引言

分類規(guī)則是數(shù)據(jù)挖掘領(lǐng)域中的重要研究內(nèi)容，其主要思想是通過分析訓(xùn)練集數(shù)據(jù)，產(chǎn)生關(guān)于類別的精確描述[1-2]。此類別描述通常由分類規(guī)則組成，可以對未來的做出進行分析與分類預(yù)測，有著廣泛的應(yīng)用前景。

分類規(guī)則的數(shù)據(jù)挖掘[3]，主要方法有：決策樹法、貝葉斯法、人工神經(jīng)網(wǎng)絡(luò)法、遺傳算法和粗糙集方法等，在實際應(yīng)用中，數(shù)據(jù)集的特征往往復(fù)雜多樣，需要根據(jù)實際情況采取不同的方法進行處理。

遺傳算法（GA）是一種尋找最優(yōu)解的計算方法[4-5]，通過模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程，得到問題的最優(yōu)結(jié)果。借用生物遺傳學(xué)的觀點，通過自然選擇、交叉、變異等操作，一代代不斷地繁殖進化，最后收斂到一批最適應(yīng)環(huán)境的個體上，從而求得最優(yōu)分類規(guī)則[6]。

本文通過分析基于遺傳算法的學(xué)習(xí)分類器系統(tǒng)的體系機構(gòu)，以規(guī)則為基礎(chǔ)，給出一種基于非隨機初始種群遺傳算法的分類規(guī)則數(shù)據(jù)挖掘算法，通過訓(xùn)練數(shù)據(jù)集來實現(xiàn)類別的精確描述，采用數(shù)據(jù)挖掘中的基準數(shù)據(jù)鳶尾花卉數(shù)據(jù)集作為應(yīng)用對象，實現(xiàn)學(xué)習(xí)分類器中的消息與分類器系統(tǒng)匹配、桶隊列算法信用分配以及基于遺傳算法的規(guī)則發(fā)現(xiàn)等關(guān)鍵技術(shù)，提高了分類規(guī)則挖掘的效率和準確性。

1 學(xué)習(xí)分類系統(tǒng)

1.1 基本原理

學(xué)習(xí)分類器系統(tǒng)[7-9]由屬于三層次結(jié)構(gòu)，第一層是規(guī)則庫及信息系統(tǒng)，是一種基于規(guī)則（即分類器）的形式特殊的產(chǎn)生式系統(tǒng)，直接與環(huán)境發(fā)生作用；第二層是信用分配系統(tǒng)，其主要作用是對分類器做性能測評，每條分類器根據(jù)其性能而得到一個規(guī)則強度；第三層是規(guī)則生成與更新系統(tǒng)，規(guī)則庫中可用規(guī)則數(shù)量龐大，而分類器庫中的規(guī)則數(shù)有限，通常采用遺傳算法對規(guī)則進行處理，不斷產(chǎn)生新的、性能好的規(guī)則代替規(guī)則中性能差的規(guī)則以提高系統(tǒng)的性能。

1.2 規(guī)則及信息系統(tǒng)

規(guī)則及信息系統(tǒng)是一種特殊的產(chǎn)生式系統(tǒng)，其中的消息是長度確定的字符串，字符串中的字符一般用二進制：

：={0，1}m

符號“：=”表示“定義成”，{0，1}m表示字符串message的長度為m，而字符取0或1。

一個分類器（classifier）是一條特殊的產(chǎn)生式規(guī)則：

：=：

它的語義是：如果分類器地條件滿足，分類器將向系統(tǒng)提供一條消息。

：={0，1，#}

符號“#”表示通配符，即“0”“1”都匹配“#”。如條件#01#與消息0010，1010，0011，1011都匹配。

2 基于遺傳算法的學(xué)習(xí)分類器系統(tǒng)

2.1 規(guī)則生成與系統(tǒng)更新

當規(guī)則和消息系統(tǒng)和環(huán)境進行一段時間的交互作用后，經(jīng)過信任分配，規(guī)則庫中的規(guī)則都有了能體現(xiàn)其性能的規(guī)則強度，此時使用遺傳算法來產(chǎn)生新的規(guī)則替代性能不好的規(guī)則，其中的主要過程如下。

第一步：根據(jù)規(guī)則強度的大小，按照概率值大小隨機選取兩條規(guī)則r1和r2，規(guī)則強度大的規(guī)則選中的可能性大，反之則小。

第二步：將選中的兩條規(guī)則進行交叉和變異，產(chǎn)生兩條新規(guī)則，R1和R2，隨機保留其中的一條規(guī)則，設(shè)為R1，新規(guī)則的強度取為規(guī)則庫的平均規(guī)則強度。

第三步：R1取代規(guī)則庫中性能最差（規(guī)則強度最?。┑囊?guī)則。

第四步：回到第一步，直到規(guī)則庫中一定比例（G）的規(guī)則被替換。

需要注意的是，由于分類器系統(tǒng)使用三個字符 0、1、#，因此當某一個字符發(fā)生變異時，它將以相同的概率變化為其他兩個字符中的一個。

2.2 工作過程

基于遺傳算法的學(xué)習(xí)分類系統(tǒng)（Learning classifier system based on genetic algorithm，LCS）流程如下。

Step1：檢測器對環(huán)境輸入進行位串編碼，形成環(huán)境消息，存儲于消息列表中。

Step2：環(huán)境消息與分類器規(guī)則庫中分類器的狀態(tài)部分進行匹配，匹配成功的分類器組成匹配分類器集合。

Step3：匹配的分類器根據(jù)自身強度值進行投標，中標的分類器稱為激活的分類器，激活的分類器允許將其動作部分作為新消息向外發(fā)送，所發(fā)送的新消息為外部消息或內(nèi)部消息。

Step4：清空消息列表。如果Step3中產(chǎn)生的是內(nèi)部消息，則將內(nèi)部消息放入消息列表中。內(nèi)部消息需再與分類器規(guī)則庫中的分類器進行匹配，激活下一個分類器，產(chǎn)生新的消息，由此構(gòu)成一個內(nèi)部消息鏈，直至最后形成外部消息。

Step5：運用桶隊列算法（Bucket brigade algorithm，簡稱BB算法）對激活的分類器進行回報的信用分配。如果激活的分類器產(chǎn)生的是外部消息，則該分類器直接得到環(huán)境回報；如果激活的分類器產(chǎn)生的是內(nèi)部消息，它將在下一個周期中，其他分類器匹配該內(nèi)部消息后才能得到回報。這兩種激活的分類器分別用“t時刻激活的分類器”和“t-1時刻激活的分類器”加以區(qū)分。

Step6：當執(zhí)行子系統(tǒng)和桶隊列信用分配子系統(tǒng)運行一定的時間間隔后，啟動遺傳算法的規(guī)則發(fā)現(xiàn)子系統(tǒng)。對分類器規(guī)則庫進行遺傳操作，選擇優(yōu)良的分類器作為父輩個體，運用交叉和變異操作產(chǎn)生新的分類器子個體，加入到分類器規(guī)則庫中。

Step7：返回至Step1。

3 實驗結(jié)果及分析

3.1 實驗準備

選用Iris數(shù)據(jù)集作為處理對象，使用C5.0算法生成初始規(guī)則集。Iris數(shù)據(jù)集包含150個數(shù)據(jù)對象，分為三類，分別為：Iris setosa，Iris versicolour，Iris virginica。C5.0是決策樹模型中的算法，主要針對離散型屬性數(shù)據(jù)，C5.0是C4.5應(yīng)用于大數(shù)據(jù)集上的分類算法，主要在執(zhí)行效率和內(nèi)存使用方面進行了改進。

3.2 實驗結(jié)果及分析

由C5.0生成的規(guī)則集的精度如表1所示。

表1 C5.0規(guī)則的精度

[類型 C5.0規(guī)則集精度 訓(xùn)練集 測試集 Iris-Setosa 25/25 25/25 Iris-Versicolour 24/25 23/25 Iris-Virginica 25/25 24/25 Total 74/75 72/75 98.67% 96% ]

表2 優(yōu)化后C5.0規(guī)則的精度

[類型 C5.0規(guī)則集精度 訓(xùn)練集 測試集 Iris-Setosa 25/25 25/25 Iris-Versicolour 24/25 23/25 Iris-Virginica 25/25 25/25 Total 74/75 73/75 98.67% 97.33% ]

優(yōu)化以后，規(guī)則具有與C5.0相同的形式。規(guī)則集中屬性左右邊界的值都會發(fā)生改變，值的改變導(dǎo)致了分類準確度的提高，表2是優(yōu)化后的規(guī)則在訓(xùn)練集和測試集上的精度。

表1和表2的結(jié)果表明，遺傳算法優(yōu)化后的精度好于單個算法的精度。測試集的分類精度從96%提升到97.33%。需要注意的是，在測試數(shù)據(jù)中Iris—Versicolor類的兩個例子被誤分為Iris—Virginia類、其原因在于這兩個例子中的屬性值極為相似，因此，用基于單屬性來生成規(guī)則集（決策樹算法把每次把一個屬性作為分枝的標準）的算法是無法區(qū)分的，只有通過屬性值的組合才可以把它們進行區(qū)分。

4 總結(jié)

本文將分類技術(shù)與進化方法結(jié)合起來，把遺傳算法作為一種優(yōu)化技術(shù)應(yīng)用于多分類器上，實驗結(jié)果表明，這樣的結(jié)合可以得到較好的分類效果，即得到更精確或更易理解的結(jié)果。分類器系統(tǒng)從一個更高層次對規(guī)則集進行優(yōu)化，通過優(yōu)化規(guī)則的條件部分的邊界值來提高預(yù)測精度，具有全局最優(yōu)性和魯棒性，對于大規(guī)模的數(shù)據(jù)集極為適合。

參考文獻（References）：

[1] Wah Y B， Ibrahim I R. Using data mining predictive models

to classify credit card applicants[C]. International Conference on Advanced Information Management and Service. IEEE，2010：394-398

[2] Singh V， Midha N. A Survey on Classification Techniques

in Data Mining[J]. International Journal of Computer Science & Management Studies，2015.16.

[3] 鄧桂騫，趙躍龍，劉霖等.一種優(yōu)化的貝葉斯分類算法[J].計算

機測量與控制，2012.20（1）：199-201

[4] 金敏，魯華祥.一種遺傳算法與粒子群優(yōu)化的多子群分層混

合算法[J].控制理論與應(yīng)用，2013.30（10）：1231-1238

[5] 徐勝，馬小軍，錢海等.基于遺傳-模擬退火的蟻群算法求解

TSP問題[J].計算機測量與控制，2016.24（3）：143-144

[6] 于光帥，于憲偉.一種改進的自適應(yīng)遺傳算法[J].數(shù)學(xué)的實踐

與認識，2015.45（19）：259-264

[7] 邢乃寧，孫志揮.基于增量式遺傳算法的分類規(guī)則挖掘[J].計

算機應(yīng)用研究，2001.18（11）：13-15

[8] 廖萍.遺傳算法學(xué)習(xí)分類器系統(tǒng)的研究與應(yīng)用[D].華東師范

大學(xué)碩士學(xué)位論文，2013.

[9] 季文赟，周傲英，張亮等.一種基于遺傳算法的優(yōu)化分類器的

方法[J].軟件學(xué)報，2002.13（2）：245-249