薛愈潔

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ī)則組成，可以對(duì)未來的做出進(jìn)行分析與分類預(yù)測，有著廣泛的應(yīng)用前景。

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

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

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

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)，其主要作用是對(duì)分類器做性能測評(píng)，每條分類器根據(jù)其性能而得到一個(gè)規(guī)則強(qiáng)度；第三層是規(guī)則生成與更新系統(tǒng)，規(guī)則庫中可用規(guī)則數(shù)量龐大，而分類器庫中的規(guī)則數(shù)有限，通常采用遺傳算法對(duì)規(guī)則進(jìn)行處理，不斷產(chǎn)生新的、性能好的規(guī)則代替規(guī)則中性能差的規(guī)則以提高系統(tǒng)的性能。

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

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

：={0，1}m

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

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

：=：

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

：={0，1，#}

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

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

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

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

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

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

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

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

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

2.2 工作過程

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

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

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

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

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

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

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

Step7：返回至Step1。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)準(zhǔn)備

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

3.2 實(shí)驗(yàn)結(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ī)則集中屬性左右邊界的值都會(huì)發(fā)生改變，值的改變導(dǎo)致了分類準(zhǔn)確度的提高，表2是優(yōu)化后的規(guī)則在訓(xùn)練集和測試集上的精度。

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

4 總結(jié)

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

參考文獻(xiàn)（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].計(jì)算

機(jī)測量與控制，2012.20（1）：199-201

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

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

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

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

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

與認(rèn)識(shí)，2015.45（19）：259-264

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

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

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

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

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

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