基于遗传算法的特征选择.ppt

文档介绍：基于遗传算法的特征选择
What
Why
How
回答什么是遗传算法?什么是特征选择?
遗传算法是模拟进化论,搜索优化问题最优解的一种算法。它采用群体搜索策略,一代一代逐步进化,直到收敛到问题的最优解。
群体是个体的集合,个体模拟一个问题的一个解。
关键问题:
个体如何表示?
方法:问题编码
如何产生下一代?
方法:遗传操作
如何评价种群的质量?
方法:适应度函数
What
什么是特征选择?
就是从一个特征集合中选择一个最优子集。
遗传算法流程图
How
1. 问题编码
对于特征选择问题,问题编码很简单,采用0-1编码即可。
任何一个n元0-1串,都表示问题的一个解。
2. 如何产生下一代
通过选择、交叉、变异三种遗传操作产生下一代,前两种操作每一次都要用的,而第三种则不一定,但没有规则。
选择是用来选择交叉的父本,交叉(模拟有性繁殖)产生新的个体,变异是某一位的变异。

适应度函数设计,对于特征选择问题可采用如下的类别可分离性准则,设计适应度函数。
适应度函数为
需要注意的是这种适应度函数,只适用于连续值数据库的情况。下面如何计算?
Iris数据库
选择的特征子集应使类内散度尽可能小,而使类间散度尽可能大.
设xk(i)和xl(j)分别为i类和j类中的D维特征向量,(xk(i) , xk(j))为这两个向量间的距离,则类间平均距离为:
其中,Pi和Pj为先验概率。
通常采用欧氏距离:
JD称为各类之间的平均平方距离。
定义类均值向量为和总均值向量分别为:
和