基于遗传算法的分类器设计.ppt

基于遗传算法的分类器设计,冯利美 E-mail: ,主要内容,目标概念的表示 搜索空间的表示 遗传操作 适应度函数 系统地执行过程 实验结果 参考文献,用遗传算法做分类问题,就是找到一组能很好拟合训练样例的IF-THEN规则(目标概念)。学习过程可看作一个搜索过程,就是在假设空间中搜索目标概念。目标概念的表示通常有两种： Michigan方法 一条染色体表示一条规则，种群中的各条规则互相竞争。整个种群表示一个目标概念。 Pittsburgh方法 每条染色体是由一组定长的规则组成，代表一个侯选概念。,返回,目标概念的表示,搜索空间的表示一,这里的搜索空间,就是侯选假设空间,遗传算法中的假设常被表示成二进制位串,编码方式确定了,假设空间也就相应定了.,把if-then规则编码成位串,首先使用位串描述单个属性的值约束.比如属性Outlook, 取值有三个:Sunny、Overcast、Rain. 使用一个长度为3的位串,每位对应一个可能值,若某位为1,表示这个属性可以取对应的值 多个属性约束的合取表示为各个属性对应位串的连接 整个规则表示为规则前件和后件位串的连接,搜索空间的表示二,比如一条规则： If (Outlook=Sunny) and (Temperature=Hot) and (Humidity=High) and (Wind=Weak or Strong) then PlayTennis=No 二进制编码形式为：100100101101,返回,联赛选择算子,由于传统的比例算子容易发生早熟现象,而联赛选择算子的局部搜索能力比较强，所以并没有采用常用的比例选择算子公式，而采用了该算子，操作思想：从群体中任意选择一定数目的个体(称为联赛规模)，其中适应度最高的个体保存到下一代，这一过程反复进行，直到保存到下一代的个体数目达到群体规模。,两点交叉算子一,它是基本两点交叉算子的一个扩展。为了适应编码规则集的位串长度可变性，并且限制系统以使交叉发生在位串的相似片段间，采用下面方法： 在第一个双亲串上随机选取两个交叉点，它们之间划分出了一个位串片段。这两个交叉点可能取在了两条规则中。 令d1表示第一个交叉点到它左侧第一个规则边界的距离。d2表示第二个交叉点到它左侧第一个规则边界的距离。在第二个双亲上随机选取交叉点，要求选择的交叉点具有同样d1和d2值。,例如：如果两个双亲串是：,两点交叉算子二,并且为第一个双亲h1选取交叉点位置是第1位和第9位，那么d1=1并且d2=3。允许选取第二个双亲交叉点的位置有,和。如果恰巧选取了，如下所示：,那么结果生成的两个后代是：,两点交叉算子三,如此例所示，这种交叉方法中后代可以包含与双亲不同数量的规则，同时保证了按这种方式产生的位串表示良定义的（well-defined）规则集。需要说明的是，交叉算子的交叉点不能落在决策属性的编码位串中，否则规则的决策属性位串中不止一个1或者全0，规则将不符合语义，成为一条无效规则。,变异算子,变异操作是对标准遗传算法的变异算子做了一个约束，因为决策属性比较特殊，它的位串中只能有一位是1，大于1或全0不符合语义，无法对规则做出解释，所以决策属性的位串不参与变异操作。,， ，,返回,适应度函数,设计原则 MDL公式描述 关于参数W的自动调整 MDL结合删除规则操作,返回,在1993年GABIL系统中，每个规则集的适应度是根据它在训练数据上的分类精度计算的。确切地讲，度量适应度的函数是： 并没有考虑到规则集合的复杂度，基于这种适应度函数，最简单的提高适应度的方式就是去学习训练样例本身，而不是从中学习规律，这样就会使得染色体中规则的数目程指数级增加，而规则过于特殊，泛化能力差，这不符合Occams razor 原则。为了解决这一问题，基于 MDL Principle，同时考虑规则集合的预测精度和复杂度。,设计原则,返回,本问题中的假设就是染色体用于描述目标概念的规则集，需要考虑到规则集合本身的复杂度以及没有被分对和不能给出决策的训练样例两部分，描述长度最小的染色体适应度最高。适应度函数变成了以下MDL公式的最小值： 其中W是调整TL和EL 的权值。,MDL公式描述一,MDL Principle在假设的复杂性和假设产生错误的数量之间进行了折中，选择两部分描述长度之和最小的假设。,MDL公式描述二,其中na是条件属性数， 是第 i条规则的第j个属性的位串长度，由于规则中决策属性需要的编码长度是一样的，所以公式中只考虑了决策属性。,描述一条染色体（规则集）的理论长度TL定义：,其中nr是规则数（nr体现规则复杂性高占劣势），规则的表示形式都是：IF条件THEN 决策。条件是若干个对属性约束的合取.因此TLi如下定义：,比如一个属性的编码位串是1111100001，可以知道这个属性有10个可能的取值，3个模拟区间，则这个属性的TL大小为：,MDL公式描述三,其中nvj 是属性j的取值数， 是属性j编码位串中的模拟区间数。 提高规则的泛化能力，具体到每个属性的编码位串表现为1的数目增多, 有较少的模拟区间。,对于离散值属性， 如下定义：,用于描述不能被正确分类的训练样例的信息EL如下定义：,其中ne是所有训练样例的数目，nm是被错误分类的样例数，nu是不能做出决策的样例数，nc是类别数,(nm+nu)体现规则精度差占劣势) 。,返回,关于参数W的自动调整一,具体方法是：在学习过程开始的时候更重视规则集合的复杂性，限制规则的数目， W取得比较大，随着进化过程的进行，当GA连续一定代数都没有进化的时候，就缩小W，从而更重视分类精度。,MDL公式中的W是为了调整TL和EL。实验证明，算法对W很敏感，如果W太大，也就是过于重视规则的复杂度，最终会导致种群中的染色体只包含一条规则（条件属性位串为全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 population 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，MaximumBestDelay=10（对应于使用联赛选择，联赛规模3，种群规模300）。,返回,MDL结合删除规则操作,返回,为了进一步控制染色体中规则的数目，在计算了染色体的适应度后，删除规则集中不能覆盖任何训练样例的规则。,该操作有两个前提条件：,为了保证群体的多样性，在进行了一定次数的迭代后， 才开始删除规则。 当染色体中规则数小于一个给定阈值（比如：取类别数加3 ）时，停止删除操作。,系统地执行过程一,采用了特殊的增量方式ILAS（Incremental Learning with Alternating Segments）。让系统在变化的环境中来学习，这样可以惩罚过于特殊的规则，提高规则集合的泛化能力。具体过程如下：,把训练样例分成几个部分，使用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 Iteration=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 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部分)。,参考文献一,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 concept 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 minimum description length principle for a Pittsburgh approach Learning Classifier System. Sixth International Workshop on Learning Classifier Systems (IWLCS-2003) Chicago, July 2003.,参考文献二,6 Pfahringet.J. Modeling bu shortest data description. Automatica vol.14(1978)165-171. 7 Wolpert, D.H., Macready, W.G.:No free lunch theorems for search.Technical Report SFI-TR-95-02-010, Santa Fe, NM (1995) 8 Jaume Bacardit. Pittsburgh Genetics-Based Machine Learning in the Data Mining era: Representations, generalization, and run-time. Doctoral disertation, Ramon Llull University, Barcelona, Catalonia, Spain.,Thank you!,