XCS及其在二进制序列分类问题中的应用

李鑫　陶华敏　罗辉舞　吴东娅

摘 要： XCS作为一种基于精度的学习分类器系统，是近年来机器学习领域研究的热点。介绍了XCS的基本结构，研究了其在序列分类问题中的应用，并以此为基础构建一个学习/测试系统，实现了对二进制序列的学习和分类，讨论了相关参数对学习性能的影响，最后对XCS的应用前景进行了总结。

关键词： XCS； 学习分类器系统； 机器学习； 二进制序列

中图分类号： TN957.52?34 文献标识码： A 文章编号： 1004?373X（2014）05?0090?04

0 引 言

自计算机问世以来，人们就一直在研究怎样使其具备和人类一样强大的学习能力，并因此产生了多种机器学习算法。LCS（学习分类器系统）作为一种基于规则的自主学习方法，在机器学习领域占有重要的地位[1]。

1978年，John Holland首次将遗传算法和强化学习的思想结合起来，提出了LCS的概念[1]。但起初LCS规则集的更新方式相对复杂，且更新过程不稳定。为提高LCS的学习性能，S.W. Wilson在1995年提出了XCS（拓展的学习分类器系统）作为LCS的改进形式，XCS对LCS的结构进行了简化，系统内部不再需要复杂的消息列表，并将适应度取值从基于预测回报的强度改为基于预测回报的精度，因此XCS也常叫做基于精度的学习分类器系统[2]。

序列分类是机器学习领域的经典问题，通过对二进制序列的学习与分类，可以更直观地理解XCS的工作特点和学习过程。本文首先介绍了XCS的基本结构；然后讨论了序列学习与分类的问题，构建了二进制序列分类的实验环境并给出部分实验结果，分析了XCS的学习性能；最后对XCS的应用前景进行了总结。

1 XCS的基本结构

图1 XCS的基本组成

XCS的基本工作流程是：当有外界环境输入时，执行部分会根据环境的状态从种群[P]中选取与之相匹配的分类器集合[M]，然后依据一定的准则确定动作集[A]并将动作输出，获得环境反馈后强化部分将更新集合[A]中分类器的参数，而后发现部分应用遗传算法在集合[A]中进行分类器的交叉和变异，依此循环往复，不断更新种群[P]中的分类器，直至获得最优的种群或达到规定的学习次数。为进一步说明XCS的学习机制，下面简要介绍各个部分的组成。

1.1 分类器种群

1.4 发现部分

发现部分主要由覆盖机制和遗传算法两部分组成。一般地，为保证匹配集[M]非空且不直接等于[A]，当[M]中包含的动作数小于设定的阈值[θmna]（一般为最大动作数）时，覆盖机制将被激活，用于产生状态与环境状态相匹配的新分类器，新分类器的动作在当前[M]不包含的动作中随机选取，其他参数的初始化采用默认值。覆盖机制一般发生在种群初始化为空的学习开始阶段[4]。

遗传算法是XCS学习机制的核心之一，是分类器种群[P]淘汰低准确率分类器、保留和遗传高准确率分类器的主要途径。和经典的遗传策略相一致，这里的遗传算法采取了交叉和变异两种遗传算子，遗传算子操作的对象的一般为分类器的状态或动作。在强化部分更新[A]中的分类器参数之后，遗传操作将基于适应度[F]选取父代分类器，并以交叉概率[χ]和变异概率[μ]进行分类器的交叉和变异[5]。如果有子代分类器产生，发现部分将检查[P]中的子分类器数量是否超出种群容量[N，]如超过，则遗传算法将基于适应度[F]在[P]中进行子分类器的删除操作，以保证种群不被无限扩大[6]。

2 XCS与序列分类

2.1 序列特性与机器学习

对于简单序列——如频率相差较大的正弦序列，人眼很容易加以区分，这是因为它们的变化快慢不同，而机器本身并不具备这样的理解能力，所以需要设计一个检测频率的分类系统，通过设定判决阈值来实现自动分类。

对于复杂序列，事先并不知道其特性，无法直接为其设计分类系统，但如果已经具备了大量的类别已知的数据，则可以通过机器学习方法实现对复杂序列特征的学习[7]，从而达到自动分类的目的。

2.2 二进制序列的分类

序列分类是相对宽泛的概念，为便于观察实验结果，本文采取了简单的二进制序列分类问题来验证XCS的有效性。图3为4选1数据选择器的示意图，其中S0和S1控制输出端OUT选择哪个输入，传递的数据为逻辑“0”或逻辑“1”。

4 结 语

XCS是一种通用性很强的学习算法[8]，但就其本身而言只是给出了一种学习的手段和框架，要用于解决实际问题，必须辅以合理的定义和建模手段[9]。本文就简单的二进制序列分类问题进行了相关的研究和实验，讨论并验证了XCS的学习性能。除此之外，XCS还可应用于解决许多实际问题，如经济学领域的数据挖掘问题[10]和机器人领域的自主导航问题等[11]。

参考文献

[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] 邵杰.基于学习分类器的多机器人路径规划关键技术研究[D].南京：南京理工大学，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] 邵杰.基于学习分类器的多机器人路径规划关键技术研究[D].南京：南京理工大学，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] 邵杰.基于学习分类器的多机器人路径规划关键技术研究[D].南京：南京理工大学，2011.