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

基于遗传算法的分类器设计 主要内容 目标概念的表示 有哪些信誉好的足球投注网站空间的表示 遗传操作 适应度函数 系统地执行过程 实验结果 参考文献 目标概念的表示 用遗传算法做分类问题,就是找到一组能很好拟合训练样例的IF-THEN规则(目标概念)。学习过程可看作一个有哪些信誉好的足球投注网站过程,就是在假设空间中有哪些信誉好的足球投注网站目标概念。目标概念的表示通常有两种： Michigan方法 一条染色体表示一条规则，种群中的各条规则互相竞争。整个种群表示一个目标概念。 Pittsburgh方法 每条染色体是由一组定长的规则组成，代表一个侯选概念。 有哪些信誉好的足球投注网站空间的表示一 这里的有哪些信誉好的足球投注网站空间,就是侯选假设空间,遗传算法中的假设常被表示成二进制位串,编码方式确定了,假设空间也就相应定了. 有哪些信誉好的足球投注网站空间的表示二 比如一条规则： If (Outlook=Sunny) and (Temperature=Hot) and (Humidity=High) and (Wind=Weak or Strong) then PlayTennis=No 二进制编码形式为：100100101101 联赛选择算子 两点交叉算子一 两点交叉算子二 例如：如果两个双亲串是： 两点交叉算子三 变异算子 变异操作是对标准遗传算法的变异算子做了一个约束，因为决策属性比较特殊，它的位串中只能有一位是1，大于1或全0不符合语义，无法对规则做出解释，所以决策属性的位串不参与变异操作。 适应度函数 设计原则 MDL公式描述 关于参数W的自动调整 MDL结合删除规则操作 设计原则 MDL公式描述一 本问题中的假设就是染色体—用于描述目标概念的规则集，需要考虑到规则集合本身的复杂度以及没有被分对和不能给出决策的训练样例两部分，描述长度最小的染色体适应度最高。适应度函数变成了以下MDL公式的最小值： 其中W是调整TL和EL 的权值。 MDL公式描述二 MDL公式描述三 关于参数W的自动调整一 具体方法是：在学习过程开始的时候更重视规则集合的复杂性，限制规则的数目， W取得比较大，随着进化过程的进行，当GA连续一定代数都没有进化的时候，就缩小W，从而更重视分类精度。 关于参数W的自动调整二 关于参数W的自动调整三 MDL结合删除规则操作 系统地执行过程一 系统地执行过程二 实验 先对连续值属性进行了离散化，采用的是十字交叉验证的方法，每次结果都取得十次测试的平均值。主要参数设置为：种群规模300，联赛规模3，最大繁衍代数100， 交叉概率0.6，变异概率0.6，每个个体初始规则数目15，训练样例被分成2部分(Mushroom被分成了4部分)。 参考文献一 参考文献二 [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! 冯利美 E-mail: fenglimei1981@126.com 返回 把if-then规则编码成位串 首先使用位串描述单个属性的值约束.比如属性Outlook, 取值有三个:Sunny、Overcast、Rain. 使用一个长度为3的位串,每位对应一个可能值,若某位为1,表示这个属性可以取对应的值 多个属性约束的合取表示为各个属性对应位串的连接 整个规则表示为规则前件和后件位串的连接 返回 由于传统的比例算子容易发生早熟现象,而联赛选择算子的局部有哪些信誉好的足球投注网站能力比较强，所以并没有采用常用的比例选择算子公式，而采用了该算子，操作思想：从群体中任意选择一定数目的个体(称为联赛规模)，其中适应度最高的个体保存到下一代，这一过程反复进行，直到保存到下一代的个体数目达到群体规模。 它是基本两点交叉算子的一个扩展。为了适应编码规则集的位串长度可变性，并且限制系统以使交叉发生在位串的相似片段间，采用下面方法： 在第一个双亲