《基于遗传算法的分类器设计》由会员分享，可在线阅读，更多相关《基于遗传算法的分类器设计（25页珍藏版）》请在金锄头文库上搜索。
1、基于遗传算法的分类器设计冯冯冯冯利美利美E-mail: 主要内容 目标概念的表示 搜索空间的表示 遗传操作 适应度函数 系统地执行过程 实验结果 参考文献 用遗传算法做分类问题,就是找到一组能很好拟合 训练样例的IF-THEN规则(目标概念)。学习过程可 看作一个搜索过程,就是在假设空间中搜索目标概 念。目标概念的表示通常有两种： Michigan方法 一条染色体表示一条规则，种群中的各条规则互 相竞争。整个种群表示一个目标概念。 Pittsburgh方法 每条染色体是由一组定长的规则组成，代表一个 侯选概念。返回目标概念的表示搜索空间的表示一这里的搜索空间,就是侯选假设空间,遗传算法中的假设
2、常被 表示成二进制位串,编码方式确定了,假设空间也就相应定了. 把if-then规则编码成位串首先使用位串描述单个属性的值约束.比如属性Outlook, 取值 有三个:Sunny、Overcast、Rain. 使用一个长度为3的位串,每位对 应一个可能值,若某位为1,表示这个属性可以取对应的值多个属性约束的合取表示为各个属性对应位串的连接整个规则表示为规则前件和后件位串的连接搜索空间的表示二比如一条规则：If (Outlook=Sunny) and (Temperature=Hot) and (Humidity=High) and (Wind=Weak or Strong) then Play
3、Tennis=No二进制编码形式为：100100101101返回联赛选择算子由于传统的比例算子容易发生早熟现象,而联赛选择算子 的局部搜索能力比较强，所以并没有采用常用的比例选 择算子公式，而采用了该算子，操作思想：从群体中任 意选择一定数目的个体(称为联赛规模)，其中适应度最 高的个体保存到下一代，这一过程反复进行，直到保存 到下一代的个体数目达到群体规模。两点交叉算子一它是基本两点交叉算子的一个扩展。为了适应编码规则集 的位串长度可变性，并且限制系统以使交叉发生在位串的 相似片段间，采用下面方法： 在第一个双亲串上随机选取两个交叉点，它们之间划分 出了一个位串片段。这两个交叉点可能取在了两
4、条规则中 。 令d1表示第一个交叉点到它左侧第一个规则边界的距离。 d2表示第二个交叉点到它左侧第一个规则边界的距离。在 第二个双亲上随机选取交叉点，要求选择的交叉点具有同 样d1和d2值。例如：如果两个双亲串是：两点交叉算子二并且为第一个双亲h1选取交叉点位置是第1位和第9位，那么 d1=1并且d2=3。允许选取第二个双亲交叉点的位置有 ,和。如果恰巧选取了，如下所示：那么结果生成的两个后代是：两点交叉算子三 如此例所示，这种交叉方法中后代可以包含与双亲不同数量 的规则，同时保证了按这种方式产生的位串表示良定义的（ well-defined）规则集。需要说明的是，交叉算子的交叉点不 能落在决
5、策属性的编码位串中，否则规则的决策属性位串中 不止一个1或者全0，规则将不符合语义，成为一条无效规则 。变异算子变异操作是对标准遗传算法的变异算子做了一个约束，因为决策属性比较特殊，它的位串中只能有一位是1，大于1或全0不符合语义，无法对规则做出解释，所以决策属性的位串不参与变异操作。， ， 返回适应度函数设计原则 MDL公式描述 关于参数W的自动调整 MDL结合删除规则操作 返回在1993年GABIL系统中，每个规则集的适应度是根据它在训练 数据上的分类精度计算的。确切地讲，度量适应度的函数是 ：并没有考虑到规则集合的复杂度，基于这种适应度函数，最 简单的提高适应度的方式就是去学习训练样例本
6、身，而不是 从中学习规律，这样就会使得染色体中规则的数目程指数级 增加，而规则过于特殊，泛化能力差，这不符合Occams razor 原则。为了解决这一问题，基于 MDL Principle，同时考虑 规则集合的预测精度和复杂度。 设计原则返回 本问题中的假设就是染色体用于描述目标概念的规则集 ，需要考虑到规则集合本身的复杂度以及没有被分对和不 能给出决策的训练样例两部分，描述长度最小的染色体适 应度最高。适应度函数变成了以下MDL公式的最小值：其中W是调整TL和EL 的权值。 MDL公式描述一 MDL Principle在假设的复杂性和假设产生错误的数量之间 进行了折中，选择两部分描述长度之
7、和最小的假设。MDL公式描述二其中na是条件属性数， 是第 i条规则的第j个属性的位串长度，由 于规则中决策属性需要的编码长度是一样的，所以公式中只考虑 了决策属性。 描述一条染色体（规则集）的理论长度TL定义：其中nr是规则数（nr体现规则复杂性高占劣势），规则的表示形 式都是：IF条件THEN 决策。条件是若干个对属性约束的合取.因 此TLi如下定义： 比如一个属性的编码位串是1111100001，可以知道这个属性有10个可能的 取值，3个模拟区间，则这个属性的TL大小为：MDL公式描述三其中nvj 是属性j的取值数， 是属性j编码位串中的模拟区间数。 提高规则的泛化能力，具体到每个属性的
8、编码位串表现为1的数目增多, 有较 少的模拟区间。 对于离散值属性， 如下定义： 用于描述不能被正确分类的训练样例的信息EL如下定义：其中ne是所有训练样例的数目，nm是被错误分类的样例数，nu是不能做出决策 的样例数，nc是类别数,(nm+nu)体现规则精度差占劣势) 。返回关于参数W的自动调整一具体方法是：在学习过程开始的时候更重视规 则集合的复杂性，限制规则的数目， W取得比 较大，随着进化过程的进行，当GA连续一定代 数都没有进化的时候，就缩小W，从而更重视 分类精度。 MDL公式中的W是为了调整TL和EL。实验证明，算法对 W很敏感，如果W太大，也就是过于重视规则的复杂度， 最终会导
9、致种群中的染色体只包含一条规则（条件属性 位串为全1）如果W太小，也就是过于重视规则的分类精 度，就会导致规则太多，泛化能力差，易发生过度拟合 。Iteration=0;IterationSinceBest=0; While Iteration MaximumBestDelay then W=W*WeightRelaxationFactor IterationSinceBest=0; EndIf Iteration=Iteration+1 EndWhile关于参数W的自动调整二备注：Ind=Individual with best accuracy from the initial GA po
10、pulation TL=Theory Length of Ind EL=Exception Length of Ind NR=Number of rules of Ind NC=Number of Classes of the domain关于参数W的自动调整三为了调整参数W又引入了三个变量InitialRateOfComplexity， MaximumBestDelay WeightRelaxationFactor观察试验结果，比 较稳定的参数设置如下：InitialRateOfComplexity=0.075， WeightRelaxationFactor=0.9，MaximumBestD
11、elay=10（对应于 使用联赛选择，联赛规模3，种群规模300）。返回MDL结合删除规则操作返回 为了进一步控制染色体中规则的数目，在计算了染色体 的适应度后，删除规则集中不能覆盖任何训练样例的规 则。 该操作有两个前提条件：为了保证群体的多样性，在进行了一定次数的迭代后 ， 才开始删除规则。当染色体中规则数小于一个给定阈值（比如：取类别 数加3 ）时，停止删除操作。系统地执行过程一采用了特殊的增量方式ILAS（Incremental Learning with Alternating Segments）。让系统在变化的环境中来学习， 这样可以惩罚过于特殊的规则，提高规则集合的泛化能力 。具
12、体过程如下： 把训练样例分成几个部分，使用round-robin policy。 就是在迭代过程中轮流使用那几部分训练样例，最后 一次迭代用全部的训练样例。这样可以保证最终得到 的规则集在全部训练样例上有一个好的性能。系统地执行过程二Procedure Incremental Learning with Alternating Segments（ILAS） Input:Examples;NumSegments,NumIteratins Initial GA Recorder Examples in NumSegments parts of equal class distribution It
13、eration=0; SegmentSize=size(Examples)/NumSegments While IterationNumiterations If Iteration=NumIterations-1 Then TrainSet=Examples; Else CurrentSegment=Iteration mod Numsegments TrainSet=examples from ExamplesCurrentSegment*SegmentSizeto Examples(CurrentSegment+1)*SegmentSize EndIf Run one iteration
14、 of the GA with TrainSet Iteration=Iteration+1 EndWhile Output:Best set of rules from GA population返回实验 先对连续值属性进行了离散化，采用的是十字交叉验证的方法 ，每次结果都取得十次测试的平均值。主要参数设置为：种群 规模300，联赛规模3，最大繁衍代数100， 交叉概率0.6，变异 概率0.6，每个个体初始规则数目15，训练样例被分成2部分 (Mushroom被分成了4部分)。数据库训练精度测试精度规则数目运行时间Balance82.88%78.30%53.865.26sHatehi88.0
15、8%85.50%13.610.15sheart83.87%77.46%45.130.45sMushroom97.81%93.32%17.914.81mTic-tac-toe81.38%70.85%13.317.76s参考文献一1 Tom M. Mitchell, Machine Learning, China Machine Press, 2003. 2李敏强,林丹等,遗传算法的基本理论与应用,科学出版社,2002. 3Kenneth A.DeJong,William M.Spears, and Diana F.Gordon. Using genetic algorithms for conc
16、ept learning. Machine Learning，vol.13,no.2/3,pp.161 -188,1993. 4 Jaume Bacardit and Josep M. Garrell. Incremental Learning for Pittsburgh Approach Classifier Systems. Proceedings of the “Segundo Congreso Espanol de Metaheuisticas, Algorithms Evolutions y Bioinspirados“,(2003) pages 303-311. 5 Jaume Bacardit and Josep M. Garrell. Bloat control and generalization pressure using the m
