基于非隨機初始種群遺傳算法的學習分類器系統

薛愈潔

摘 要： 學習分類器系統能夠通過簡單位串規則的學習有效地引導個體在一個環境中的行為。通過分析基于遺傳算法的學習分類器系統的實現原理，提出一種以規則為基礎的分類系統，借助訓練數據集來實現類別的精確描述，并以數據挖掘中的基準數據鳶尾花卉數據集作為應用對象，實現學習分類器中的消息與分類器系統匹配、桶隊列算法信用分配以及基于遺傳算法的規則發現。仿真結果表明，通過學習分類器系統優化后，鳶尾花分類的精度好于單個算法的精度。

關鍵詞： 學習分類器； 遺傳算法； 桶隊列算法； 鳶尾花分類

中圖分類號：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 引言

分類規則是數據挖掘領域中的重要研究內容，其主要思想是通過分析訓練集數據，產生關于類別的精確描述[1-2]。此類別描述通常由分類規則組成，可以對未來的做出進行分析與分類預測，有著廣泛的應用前景。

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

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

本文通過分析基于遺傳算法的學習分類器系統的體系機構，以規則為基礎，給出一種基于非隨機初始種群遺傳算法的分類規則數據挖掘算法，通過訓練數據集來實現類別的精確描述，采用數據挖掘中的基準數據鳶尾花卉數據集作為應用對象，實現學習分類器中的消息與分類器系統匹配、桶隊列算法信用分配以及基于遺傳算法的規則發現等關鍵技術，提高了分類規則挖掘的效率和準確性。

1 學習分類系統

1.1 基本原理

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

1.2 規則及信息系統

規則及信息系統是一種特殊的產生式系統，其中的消息是長度確定的字符串，字符串中的字符一般用二進制：

：={0，1}m

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

一個分類器（classifier）是一條特殊的產生式規則：

：=：

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

：={0，1，#}

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

2 基于遺傳算法的學習分類器系統

2.1 規則生成與系統更新

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

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

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

第三步：R1取代規則庫中性能最差（規則強度最?。┑囊巹t。

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

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

2.2 工作過程

基于遺傳算法的學習分類系統（Learning classifier system based on genetic algorithm，LCS）流程如下。

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

Step2：環境消息與分類器規則庫中分類器的狀態部分進行匹配，匹配成功的分類器組成匹配分類器集合。

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

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

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

Step6：當執行子系統和桶隊列信用分配子系統運行一定的時間間隔后，啟動遺傳算法的規則發現子系統。對分類器規則庫進行遺傳操作，選擇優良的分類器作為父輩個體，運用交叉和變異操作產生新的分類器子個體，加入到分類器規則庫中。

Step7：返回至Step1。

3 實驗結果及分析

3.1 實驗準備

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

3.2 實驗結果及分析

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

表1 C5.0規則的精度

[類型 C5.0規則集精度 訓練集 測試集 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 優化后C5.0規則的精度

[類型 C5.0規則集精度 訓練集 測試集 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% ]

優化以后，規則具有與C5.0相同的形式。規則集中屬性左右邊界的值都會發生改變，值的改變導致了分類準確度的提高，表2是優化后的規則在訓練集和測試集上的精度。

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

4 總結

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

參考文獻（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] 鄧桂騫，趙躍龍，劉霖等.一種優化的貝葉斯分類算法[J].計算

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

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

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

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

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

[6] 于光帥，于憲偉.一種改進的自適應遺傳算法[J].數學的實踐

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

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

算機應用研究，2001.18（11）：13-15

[8] 廖萍.遺傳算法學習分類器系統的研究與應用[D].華東師范

大學碩士學位論文，2013.

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

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