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

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

适应度函数设计，对于特征选择问题可采用如下的类别可分离性准则，设计适应度函数。
第5页/共28页
适应度函数为
需要注意的是这种适应度函数，只适用于连续值数据库的情况。下面如何计算？
第6页/共28页
Iris数据库
第7页/共28页
选择的特征子集应使类内散度尽可能小，而使类间散度尽可能大.
设xk(i)和xl(j)分别为i类和j类中的D维特征向量，(xk(i) , xk(j))为这两个向量间的距离，则类间平均距离为：
第8页/共28页
其中，Pi和Pj为先验概率。
通常采用欧氏距离：
JD称为各类之间的平均平方距离。
定义 类均值向量为和总均值向量分别为：
和
第9页/共28页
定义 类间散度矩阵Sb的估计为：
定义 类内散度矩阵Sw的估计为：
其中，i为类协方差矩阵。
其他需要说明的问题还有：
第10页/共28页