7.7特征选择 7.7特征选择 口单独最优特征组合 口顺序前进法 ■计算各特征单独使用时的可分性判据并加以排 序，取前d个作为选择结果， ·自下而上的搜索方法； ■不一定是最优结果： ■每次从未入选的特征中选择一个特征，使得它与 ■当可分性判据对各特征具有（广义）可加性，该 已入选的特征组合在一起时所得的准则值为最 方法可以选出一组最优的特征；例如： 大，直至特征数目增加到d为止： 口各类县有正态分布： ■该方法考虑了所选特征与已入选特征之间的相关 口各特征统计独立： 性。 ▣可分性判据基于Mahalanobis距离； J,,,)=2J,Jo=,-,-y 7.7.1特征选择一遗传算法 7.7.1特征选择一遗传算法 口该算法受进化论启迪，根据“物竞天择，适者生 口术语 存”规则演变； ■群体：若干个体的集合，也就是一些解的集合； 口术语： ■交叉：选择群体中的两个个体，以这两个个体为 ■基因链码：使用遗传算法时要把问题的每个解编 双亲作基因链码的交叉，从而产生两个新的个 码成一个基因链码。 体，作为后代：X100,J00 ◆ X,10001010 比如要从D个特征中挑选d个，就用一个D位 X20100010 X:01001100 的0或1组成的字符串表示一种特征组合；1表 ■变异：对某个体，随机选取其中一位，将其翻转 示该特征被选中。 1000010◆1001010 每个基因链码代表一个解，称作一个“个体”，其 音 中的每一位看作是一个“基因”。 ■适应度：对每个解，以给定的优化准则来评价其 性能的优劣，作为其适应度。 7.7.1特征选择一遗传算法 7.7.1特征选择一遗传算法 遗传算法的基本框架 口关于遗传算法的说明 1. 初始化进化代数0： ■由步骤3保证了最终解是所搜索过的最优解： 2. 给出初始化群体P0),并令X2为任意一个体； ■常用的终止条件是群体的世代数超过一个给定 3.对P()中每个个体估值，并将群体中最优解x 值，或连续数个世代都没有得到更优解： 与x2比较，若优于g则令X= ■群体的大小和演化代数是值得重视的参数；在一 4.如果终止条件满足，则算法结束，X2为最终结 定范围内，这两个参数大些能得到更好的解； 果。否则，转步骤5； 5.从P()选择个体并进行交又和变异操作，得到 ■对交叉的亲本选择可采用如下规则：个体的性能 新一代个体P(t什1)，令1=什1，转步骤3。 越好，被选中的可能性也越大。43 7.7 特征选择  单独最优特征组合  计算各特征单独使用时的可分性判据并加以排 序，取前 d 个作为选择结果。  不一定是最优结果；  当可分性判据对各特征具有（广义）可加性，该 方法可以选出一组最优的特征；例如： 各类具有正态分布； 各特征统计独立； 可分性判据基于 Mahalanobis 距离； ( , , , ) ( ), ( ) ( ) ( ). 1 1 1 2 i j T D i j d k ij d ij k J x x x  J x J x  μ μ Σ μ μ     44 7.7 特征选择  顺序前进法  自下而上的搜索方法；  每次从未入选的特征中选择一个特征，使得它与 已入选的特征组合在一起时所得的准则值为最 大，直至特征数目增加到 d 为止；  该方法考虑了所选特征与已入选特征之间的相关 性。 45 7.7.1 特征选择 — 遗传算法  该算法受进化论启迪，根据“物竞天择，适者生 存”规则演变；  术语：  基因链码：使用遗传算法时要把问题的每个解编 码成一个基因链码。 比如要从 D 个特征中挑选 d个，就用一个 D 位 的 0 或 1 组成的字符串表示一种特征组合； 1 表 示该特征被选中。 每个基因链码代表一个解，称作一个“个体”，其 中的每一位看作是一个“基因”。 46 7.7.1 特征选择 — 遗传算法  术语  群体：若干个体的集合，也就是一些解的集合；  交叉：选择群体中的两个个体，以这两个个体为 双亲作基因链码的交叉，从而产生两个新的个 体，作为后代；  变异：对某个体，随机选取其中一位，将其翻转  适应度：对每个解，以给定的优化准则来评价其 性能的优劣，作为其适应度。 47 7.7.1 特征选择 — 遗传算法  遗传算法的基本框架 1. 初始化进化代数 t=0； 2. 给出初始化群体 P(t)，并令 xg 为任意一个体； 3. 对 P(t) 中每个个体估值，并将群体中最优解 x’ 与 xg 比较，若优于 xg，则令 xg= x’； 4. 如果终止条件满足，则算法结束，xg 为最终结 果。否则，转步骤 5； 5. 从 P(t) 选择个体并进行交叉和变异操作，得到 新一代个体 P(t+1) ，令 t=t+1，转步骤 3。 48 7.7.1 特征选择 — 遗传算法  关于遗传算法的说明  由步骤 3 保证了最终解是所搜索过的最优解；  常用的终止条件是群体的世代数超过一个给定 值，或连续数个世代都没有得到更优解；  群体的大小和演化代数是值得重视的参数；在一 定范围内，这两个参数大些能得到更好的解；  对交叉的亲本选择可采用如下规则：个体的性能 越好，被选中的可能性也越大