XCS及其在二進(jìn)制序列分類(lèi)問(wèn)題中的應(yīng)用

李鑫　陶華敏　羅輝舞　吳東婭

摘 要： XCS作為一種基于精度的學(xué)習(xí)分類(lèi)器系統(tǒng)，是近年來(lái)機(jī)器學(xué)習(xí)領(lǐng)域研究的熱點(diǎn)。介紹了XCS的基本結(jié)構(gòu)，研究了其在序列分類(lèi)問(wèn)題中的應(yīng)用，并以此為基礎(chǔ)構(gòu)建一個(gè)學(xué)習(xí)/測(cè)試系統(tǒng)，實(shí)現(xiàn)了對(duì)二進(jìn)制序列的學(xué)習(xí)和分類(lèi)，討論了相關(guān)參數(shù)對(duì)學(xué)習(xí)性能的影響，最后對(duì)XCS的應(yīng)用前景進(jìn)行了總結(jié)。

關(guān)鍵詞： XCS； 學(xué)習(xí)分類(lèi)器系統(tǒng)； 機(jī)器學(xué)習(xí)； 二進(jìn)制序列

中圖分類(lèi)號(hào)： TN957.52?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）05?0090?04

0 引 言

自計(jì)算機(jī)問(wèn)世以來(lái)，人們就一直在研究怎樣使其具備和人類(lèi)一樣強(qiáng)大的學(xué)習(xí)能力，并因此產(chǎn)生了多種機(jī)器學(xué)習(xí)算法。LCS（學(xué)習(xí)分類(lèi)器系統(tǒng)）作為一種基于規(guī)則的自主學(xué)習(xí)方法，在機(jī)器學(xué)習(xí)領(lǐng)域占有重要的地位[1]。

1978年，John Holland首次將遺傳算法和強(qiáng)化學(xué)習(xí)的思想結(jié)合起來(lái)，提出了LCS的概念[1]。但起初LCS規(guī)則集的更新方式相對(duì)復(fù)雜，且更新過(guò)程不穩(wěn)定。為提高LCS的學(xué)習(xí)性能，S.W. Wilson在1995年提出了XCS（拓展的學(xué)習(xí)分類(lèi)器系統(tǒng)）作為L(zhǎng)CS的改進(jìn)形式，XCS對(duì)LCS的結(jié)構(gòu)進(jìn)行了簡(jiǎn)化，系統(tǒng)內(nèi)部不再需要復(fù)雜的消息列表，并將適應(yīng)度取值從基于預(yù)測(cè)回報(bào)的強(qiáng)度改為基于預(yù)測(cè)回報(bào)的精度，因此XCS也常叫做基于精度的學(xué)習(xí)分類(lèi)器系統(tǒng)[2]。

序列分類(lèi)是機(jī)器學(xué)習(xí)領(lǐng)域的經(jīng)典問(wèn)題，通過(guò)對(duì)二進(jìn)制序列的學(xué)習(xí)與分類(lèi)，可以更直觀(guān)地理解XCS的工作特點(diǎn)和學(xué)習(xí)過(guò)程。本文首先介紹了XCS的基本結(jié)構(gòu)；然后討論了序列學(xué)習(xí)與分類(lèi)的問(wèn)題，構(gòu)建了二進(jìn)制序列分類(lèi)的實(shí)驗(yàn)環(huán)境并給出部分實(shí)驗(yàn)結(jié)果，分析了XCS的學(xué)習(xí)性能；最后對(duì)XCS的應(yīng)用前景進(jìn)行了總結(jié)。

1 XCS的基本結(jié)構(gòu)

圖1 XCS的基本組成

XCS的基本工作流程是：當(dāng)有外界環(huán)境輸入時(shí)，執(zhí)行部分會(huì)根據(jù)環(huán)境的狀態(tài)從種群[P]中選取與之相匹配的分類(lèi)器集合[M]，然后依據(jù)一定的準(zhǔn)則確定動(dòng)作集[A]并將動(dòng)作輸出，獲得環(huán)境反饋后強(qiáng)化部分將更新集合[A]中分類(lèi)器的參數(shù)，而后發(fā)現(xiàn)部分應(yīng)用遺傳算法在集合[A]中進(jìn)行分類(lèi)器的交叉和變異，依此循環(huán)往復(fù)，不斷更新種群[P]中的分類(lèi)器，直至獲得最優(yōu)的種群或達(dá)到規(guī)定的學(xué)習(xí)次數(shù)。為進(jìn)一步說(shuō)明XCS的學(xué)習(xí)機(jī)制，下面簡(jiǎn)要介紹各個(gè)部分的組成。

1.1 分類(lèi)器種群

1.4 發(fā)現(xiàn)部分

發(fā)現(xiàn)部分主要由覆蓋機(jī)制和遺傳算法兩部分組成。一般地，為保證匹配集[M]非空且不直接等于[A]，當(dāng)[M]中包含的動(dòng)作數(shù)小于設(shè)定的閾值[θmna]（一般為最大動(dòng)作數(shù)）時(shí)，覆蓋機(jī)制將被激活，用于產(chǎn)生狀態(tài)與環(huán)境狀態(tài)相匹配的新分類(lèi)器，新分類(lèi)器的動(dòng)作在當(dāng)前[M]不包含的動(dòng)作中隨機(jī)選取，其他參數(shù)的初始化采用默認(rèn)值。覆蓋機(jī)制一般發(fā)生在種群初始化為空的學(xué)習(xí)開(kāi)始階段[4]。

遺傳算法是XCS學(xué)習(xí)機(jī)制的核心之一，是分類(lèi)器種群[P]淘汰低準(zhǔn)確率分類(lèi)器、保留和遺傳高準(zhǔn)確率分類(lèi)器的主要途徑。和經(jīng)典的遺傳策略相一致，這里的遺傳算法采取了交叉和變異兩種遺傳算子，遺傳算子操作的對(duì)象的一般為分類(lèi)器的狀態(tài)或動(dòng)作。在強(qiáng)化部分更新[A]中的分類(lèi)器參數(shù)之后，遺傳操作將基于適應(yīng)度[F]選取父代分類(lèi)器，并以交叉概率[χ]和變異概率[μ]進(jìn)行分類(lèi)器的交叉和變異[5]。如果有子代分類(lèi)器產(chǎn)生，發(fā)現(xiàn)部分將檢查[P]中的子分類(lèi)器數(shù)量是否超出種群容量[N，]如超過(guò)，則遺傳算法將基于適應(yīng)度[F]在[P]中進(jìn)行子分類(lèi)器的刪除操作，以保證種群不被無(wú)限擴(kuò)大[6]。

2 XCS與序列分類(lèi)

2.1 序列特性與機(jī)器學(xué)習(xí)

對(duì)于簡(jiǎn)單序列——如頻率相差較大的正弦序列，人眼很容易加以區(qū)分，這是因?yàn)樗鼈兊淖兓炻煌?，而機(jī)器本身并不具備這樣的理解能力，所以需要設(shè)計(jì)一個(gè)檢測(cè)頻率的分類(lèi)系統(tǒng)，通過(guò)設(shè)定判決閾值來(lái)實(shí)現(xiàn)自動(dòng)分類(lèi)。

對(duì)于復(fù)雜序列，事先并不知道其特性，無(wú)法直接為其設(shè)計(jì)分類(lèi)系統(tǒng)，但如果已經(jīng)具備了大量的類(lèi)別已知的數(shù)據(jù)，則可以通過(guò)機(jī)器學(xué)習(xí)方法實(shí)現(xiàn)對(duì)復(fù)雜序列特征的學(xué)習(xí)[7]，從而達(dá)到自動(dòng)分類(lèi)的目的。

2.2 二進(jìn)制序列的分類(lèi)

序列分類(lèi)是相對(duì)寬泛的概念，為便于觀(guān)察實(shí)驗(yàn)結(jié)果，本文采取了簡(jiǎn)單的二進(jìn)制序列分類(lèi)問(wèn)題來(lái)驗(yàn)證XCS的有效性。圖3為4選1數(shù)據(jù)選擇器的示意圖，其中S0和S1控制輸出端OUT選擇哪個(gè)輸入，傳遞的數(shù)據(jù)為邏輯“0”或邏輯“1”。

4 結(jié) 語(yǔ)

XCS是一種通用性很強(qiáng)的學(xué)習(xí)算法[8]，但就其本身而言只是給出了一種學(xué)習(xí)的手段和框架，要用于解決實(shí)際問(wèn)題，必須輔以合理的定義和建模手段[9]。本文就簡(jiǎn)單的二進(jìn)制序列分類(lèi)問(wèn)題進(jìn)行了相關(guān)的研究和實(shí)驗(yàn)，討論并驗(yàn)證了XCS的學(xué)習(xí)性能。除此之外，XCS還可應(yīng)用于解決許多實(shí)際問(wèn)題，如經(jīng)濟(jì)學(xué)領(lǐng)域的數(shù)據(jù)挖掘問(wèn)題[10]和機(jī)器人領(lǐng)域的自主導(dǎo)航問(wèn)題等[11]。

參考文獻(xiàn)

[1] BUTZ M V. Rule?based evolutionary online learning system [M]. Berlin： Springer?Verlag， 2006.

[2] BUTZ M V， WILSON S W. An algorithmic description of XCA [J]. Soft Computing， 2002， 6（3?4）： 144?153.

[3] BOLCHINI C， FERRANDI P， LANZI P L， et al. Evolving classifiers on field programmable gate arrays： Migrating XCS to FPGAs [J]. Journal of Systems Architecture， 2006， 52（8?9）： 516?533.

[4] WILSON S W. Classifier fitness based on accuracy [J]. Evolutionary Computation， 1995， 3（2）： 149?175.

[5] BUTZ M V， GOLDBERG D E， THARAKUNNEL K. Analysis and improvement of fitness exploitation in XCS： bounding models， tournament selection， and bilateral accuracy [J]. Evolutionary Computation， 2003， 11（4）： 239?277.

[6] DRUGOWITSCH J. Design and analysis of learning classifier systems： a probabilistic approach （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[7] BENGIO Y， COURVILLE A， VINCENT P. Representation learning： a review and new perspectives [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（8）： 1798?1828.

[8] BUTZ M V. Anticipatory learning classifier systems [M]. Boston， MA： Kluwer Academic Publishers， 2002.

[9] KOVACS T， KERBER M. What makes a problem hard for XCS？ [M]// LANZI P L， STOLZMANN W， WILSON S W， et al. Advances in learning classifier systems. Berlin： Springer?Verlag， 2001.

[10] BULL L， BERNADO?MANSILLA E， HOLMES J， et al. Learning classifier systems in data mining （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[11] 邵杰.基于學(xué)習(xí)分類(lèi)器的多機(jī)器人路徑規(guī)劃關(guān)鍵技術(shù)研究[D].南京：南京理工大學(xué)，2011.

[4] WILSON S W. Classifier fitness based on accuracy [J]. Evolutionary Computation， 1995， 3（2）： 149?175.

[5] BUTZ M V， GOLDBERG D E， THARAKUNNEL K. Analysis and improvement of fitness exploitation in XCS： bounding models， tournament selection， and bilateral accuracy [J]. Evolutionary Computation， 2003， 11（4）： 239?277.

[6] DRUGOWITSCH J. Design and analysis of learning classifier systems： a probabilistic approach （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[7] BENGIO Y， COURVILLE A， VINCENT P. Representation learning： a review and new perspectives [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（8）： 1798?1828.

[8] BUTZ M V. Anticipatory learning classifier systems [M]. Boston， MA： Kluwer Academic Publishers， 2002.

[9] KOVACS T， KERBER M. What makes a problem hard for XCS？ [M]// LANZI P L， STOLZMANN W， WILSON S W， et al. Advances in learning classifier systems. Berlin： Springer?Verlag， 2001.

[10] BULL L， BERNADO?MANSILLA E， HOLMES J， et al. Learning classifier systems in data mining （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[11] 邵杰.基于學(xué)習(xí)分類(lèi)器的多機(jī)器人路徑規(guī)劃關(guān)鍵技術(shù)研究[D].南京：南京理工大學(xué)，2011.

[4] WILSON S W. Classifier fitness based on accuracy [J]. Evolutionary Computation， 1995， 3（2）： 149?175.

[5] BUTZ M V， GOLDBERG D E， THARAKUNNEL K. Analysis and improvement of fitness exploitation in XCS： bounding models， tournament selection， and bilateral accuracy [J]. Evolutionary Computation， 2003， 11（4）： 239?277.

[6] DRUGOWITSCH J. Design and analysis of learning classifier systems： a probabilistic approach （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[7] BENGIO Y， COURVILLE A， VINCENT P. Representation learning： a review and new perspectives [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（8）： 1798?1828.

[8] BUTZ M V. Anticipatory learning classifier systems [M]. Boston， MA： Kluwer Academic Publishers， 2002.

[9] KOVACS T， KERBER M. What makes a problem hard for XCS？ [M]// LANZI P L， STOLZMANN W， WILSON S W， et al. Advances in learning classifier systems. Berlin： Springer?Verlag， 2001.

[10] BULL L， BERNADO?MANSILLA E， HOLMES J， et al. Learning classifier systems in data mining （Studies in computational intelligence） [M]. Berlin： Springer?Verlag， 2008.

[11] 邵杰.基于學(xué)習(xí)分類(lèi)器的多機(jī)器人路徑規(guī)劃關(guān)鍵技術(shù)研究[D].南京：南京理工大學(xué)，2011.