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

MDL=W*theory bits+exception bits （MDL=W*TL+EL）
其中W是调整TL和EL 的权值。
MDL公式描述二
描述一条染色体（规则集）的理论长度TL定义：
TL TLi
i 1
nr
其中nr是规则数（nr体现规则复杂性高占劣势），规则的表示形 式都是：IF条件THEN 决策。条件是若干个对属性约束的合取.因 此TLi如下定义： na
两点交叉算子三
如此例所示，这种交叉方法中后代可以包含与双亲不同数 量的规则，同时保证了按这种方式产生的位串表示良定义的 （well-defined）规则集。需要说明的是，交叉算子的交叉点 不能落在决策属性的编码位串中，否则规则的决策属性位串 中不止一个1或者全0，规则将不符合语义，成为一条无效规 则。
主要内容
目标概念的表示
搜索空间的表示
遗传操作 适应度函数
系统地执行过程
实验结果 参考文献
目标概念的表示
用遗传算法做分类问题,就是找到一组能很好拟合 训练样例的IF-THEN规则(目标概念)。学习过程可 看作一个搜索过程,就是在假设空间中搜索目标概 念。目标概念的表示通常有两种： Michigan方法 一条染色体表示一条规则，种群中的各条规则互 相竞争。整个种群表示一个目标概念。 Pittsburgh方法 每条染色体是由一组定长的规则组成，代表一个 侯选概念。 返回
两点交叉算子二
例如：如果两个双亲串是：
a1 a2 c a1 a2 c h1: 10 01 10 11 10 01 a1 a2 c a1 a2 c h2: 01 11 01 10 01 01
并且为第一个双亲h1选取交叉点位置是第1位和第9位，那么 d1=1并且d2=3。允许选取第二个双亲交叉点的位置有 <1,3>,<1,9>和<7,9>。如果恰巧选取了<1,3>，如下所示：
搜索空间的表示一
这里的搜索空间,就是侯选假设空间,遗传算法中的假设常被 表示成二进制位串,编码方式确定了,假设空间也就相应定了.
把if-then规则编码成位串
•首先使用位串描述单个属性的值约束.比如属性Outlook,
取值 有三个:Sunny、Overcast、Rain. 使用一个长度为3的位串,每位对 应一个可能值,若某位为1,表示这个属性可以取对应的值
变异算子
变异操作是对标准遗传算法的变异算子做了一个
约束，因为决策属性比较特殊，它的位串中只能
，，
有一位是1，大于1或全0不符合语义，无法对规则
做出解释，所以决策属性的位串不参与变异操作。
返回
适应度函数
设计原则 MDL公式描述 关于参数W的自动调整 MDL结合删除规则操作
返回
设计原则
返回
MDL公式描述一
MDL Principle在假设的复杂性和假设产生错误的数量之间
进行了折中，选择两部分描述长度之和最小的假设。 本问题中的假设就是染色体—用于描述目标概念的规则集， 需要考虑到规则集合本身的复杂度以及没有被分对和不能 给出决策的训练样例两部分，描述长度最小的染色体适应 度最高。适应度函数变成了以下MDL公式的最小值：
TL log2 10 1 3 * log2 10
两点交叉算子一
它是基本两点交叉算子的一个扩展。为了适应编码规则集 的位串长度可变性，并且限制系统以使交叉发生在位串的 相似片段间，采用下面方法： 在第一个双亲串上随机选取两个交叉点，它们之间划分 出了一个位串片段。这两个交叉点可能取在了两条规则中。 令d1表示第一个交叉点到它左侧第一个规则边界的距离。 d2表示第二个交叉点到它左侧第一个规则边界的距离。在 第二个双亲上随机选取交叉点，要求选择的交叉点具有同 样d1和d2值。
a1 a2 c a1 a2 c h1: 1[0 01 10 11 1]0 01 a1 a2 c a1 a2 c h2: 0[1 1]1 01 10 01 01
那么结果生成的两个后代是：
a1 a2 c h3: 11 10 01 a1 a2 c a1 a2 c a1 a2 c h4: 00 01 10 11 11 01 10 01 01
二进制编码形式为：100100101101
来自百度文库
返回
联赛选择算子
由于传统的比例算子容易发生早熟现象,而联赛选择算子 的局部搜索能力比较强，所以并没有采用常用的比例选 择算子公式，而采用了该算子，操作思想：从群体中任 意选择一定数目的个体(称为联赛规模)，其中适应度最 高的个体保存到下一代，这一过程反复进行，直到保存 到下一代的个体数目达到群体规模。
•多个属性约束的合取表示为各个属性对应位串的连接
•整个规则表示为规则前件和后件位串的连接
搜索空间的表示二
比如一条规则：
If (Outlook=Sunny) and (Temperature=Hot) and (Humidity=High) and (Wind=Weak or Strong) then PlayTennis=No
TLi TLij
j 1
j i
TL 是第 i条规则的第j个属性的位串长度，由 其中na是条件属性数， 于规则中决策属性需要的编码长度是一样的，所以公式中只考虑 了决策属性。
MDL公式描述三
TL 如下定义： 对于离散值属性，
j i
提高规则的泛化能力，具体到每个属性的编码位串表现为1的数目增多, 有较 少的模拟区间。 比如一个属性的编码位串是 1111100001 ，可以知道这个属性有 10 个可能的 取值，3个模拟区间，则这个属性的TL大小为：
在1993年GABIL系统中，每个规则集的适应度是根据它在训练 数据上的分类精度计算的。确切地讲，度量适应度的函数是：
Fitness(h) (correctRat e(h))2
并没有考虑到规则集合的复杂度，基于这种适应度函数，最 简单的提高适应度的方式就是去学习训练样例本身，而不是 从中学习规律，这样就会使得染色体中规则的数目程指数级 增加，而规则过于特殊，泛化能力差，这不符合Occam’s razor 原则。为了解决这一问题，基于 MDL Principle，同时考虑 规则集合的预测精度和复杂度。