模式识别-第6章-特征的选择和提取

1、模式识别: 特征的选择和提取第6章 特征的选择和提取目录6.1引言6.2 类别可分离性判据6.3 特征提取6.4 特征选择(重点)6.1 引言特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步降低特征维数在很多情况下是有效设计分类器的重要课题特征的选择与提取简述两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取 (extraction)：用映射（坐标变换）的方法把原始特征变换为较少的新特征特征选择(selection) ：从原始特征中挑选出一些最有代表性，分类性能最好的特征目的：降维特征的选择与提取举例细胞自动识别：原

2、始测量： 细胞的数字图像原始特征： 细胞面积，胞核面积，形状系数，光密度，核内纹理，和浆比压缩特征：原始特征的维数很高，需压缩以便于分类特征选择：挑选最具分类信息的特征 挑选两个好的特征：胞核面积、光密度特征提取：坐标变换 产生两个新的特征，它们由原始特征的变换得到特征选择？特征提取？哪种方法更适用于我们专业？生物相关的问题，往往需要真实的特征。例如：基因芯片中的特征为基因：特征选择将得到有代表性的重要基因，这些特征基因是真实的。特征提取将从原始特征得到新的特征，这些特征不能称为特征基因。特征选择特征选择？特征提取？哪种方法更适用于我们专业？提取选择目录6.1引言6.2 类别可分离性判据6.3

3、 特征提取6.4 特征选择(重点)6.2 类别可分离性判据类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则理想准则：某组特征使分类器错误概率最小实际的类别可分离性判据应满足的条件：度量特性：与错误率有单调关系当特征独立时有可加性：单调性：常见类别可分离性判据：基于距离、概率分布、熵函数准则函数例子准则函数例子其它可分性判据基于概率的可分性判据：用概率密度函数间的距离来度量正态分布的散度Mahalanobis基于熵函数的可分性判据Shannon熵：平方熵：目录6.1引言6.2 类别可分离性判据6.3 特征提取6.4 特征选择(重点) 此时，对 求导，令 得变换w为： 的特征值 按大

4、小顺序排列为则选前r个特征值对应的特征向量作为w。即目录6.1引言6.2 类别可分离性判据6.3 特征提取6.4 特征选择(重点)经典特征选择算法许多特征选择算法力求解决搜索问题，经典算法有单独最优特征组合法、后退法、前进法(重点)分支定界法模拟退火法(重点)Tabu禁忌搜索法遗传算法(重点)穷举法由原始的D维空间降到d维空间问题。一共有q=CDd种特征组合结果。 D=20，d=10时，q= D=100，d=10时，q= 穷举法（最优方法）：一定能找到最优解如果计算每组特征组合的J值，然后选择J值最优的特征组合，往往非常耗时。计算量上无法承受。耗时!1847561013怎样减少计算时间？ 使用

5、一些次优方法，以大大减少计算时间。为什么有如此多的特征选择算法？ 没有哪个算法能够保证兼顾运算时间又能得到更优的解。单独最优特征组合计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果 特征选择结果（取前d个）不一定是最优结果当可分性判据对各特征具有可加性（各特征独立），该方法可以选出一组最优的特征来，例：顺序前进法顺序前进法（ Sequential Forward Selection ，SFS）是一种自下而上的搜索方法，它从0个特征开始每次增加一个特征，所增加的特征应使它与已入选的特征组合在一起所得J值为最大，直到特征数增加到d为止。设已选入了k个特征构成了一个大小为k的特征组

6、Xk，把未入选的D-K个特征xj，j=1,2,D-k,按与已入选特征组合后的J值大小排列：若则下一步的特征组选为Xk+1=Xk+x1顺序前进法考虑了所选特征与已入选特征之间的相关性，一般来说比单独方法好。主要缺点是一旦某特征已选入，即使由于后加入的特征使它变为多余，也无法再把它剔除。广义顺序前进法把SFS法推广为每次不止增加一个特征而是增加L个特征，就成为广义顺序前进法（Generalized Sequential Forward Selection, GSFS）。即每次从未入选的特征中选择出L个特征，使得这r个特征加入后J值达最大。GSFS法计算量大（每步有C LD-k 个候选特征组需要逐个

7、计算）。另外它也无法剔除已入选的特征。顺序后退法顺序后退法（Sequential Backward Selection, SBS）是一种自上而下的方法，它从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的J值最大，直到特征数减少到d为止。设已剔除了k个特征，剩下的特征组为 ，将 中的各特征xj按上述J值大小排序，j=1,2,D-k。若则顺序后退法的优点在计算过程中可以估计每去掉一个特征所造成可分性的降低，缺点是由于顺序后退法的计算是在高维空间进行，所以计算量比顺序前进法要大。同样，该方法也可推广为广义顺序后退法（Generalized Sequential Backward Sel

8、ection, GSBS).增L减r法（L-r法）为了避免前面方法一旦被选入（或剔除）就不能再剔除（或选入）的缺点，可在选择过程中加入局部回溯过程。例如，在第k步可先用SFS法一个个加入特征到k+L个，然后再用SBS法一个个剔除r个特征，我们把这样一种算法叫增L减r法。增L减r法（L-r法）步骤一：用SFS法在未入选特征组中逐个选入L个特征，形成新特征组Xk+L ，设置k=k+L，步骤二：用SBS法从特征组Xk中逐个剔除r个最差的特征，形成新特征组Xk-r，设置k=k-r，若k=d，则终止算法，否则设置xk=xk-r，转向第一步。（1）当Lr时，L-r法是一种自下而上的算法，先执行第一步，然后

9、执行第二步，开始时，设置k=0，x0=空（2）当Lr时，L-r法是一种自上而下的算法，此时先执行第二步，然后执行第一步，开始时设置k=0，x0=x1，,xD （ZL，Zr）法：广义L-r法Li, i=1,2,ZLrj, j=1,2,Zr （ZL，Zr）法：广义L-r法WKEA特征选择模拟退火算法1982年，Kirkpatrick(译名：科克派特瑞克)等人将退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP完全组合优化问题的有效近似算法 模拟退火算法（simulated annealing algorithm)。他源于对固体退火过程的模拟；采用Metropolis接受准则；并用一

10、组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻

11、空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。模拟退火算法应用的一般形式从选定的初始解开始，借助于控制温度t递减时产生的一系列Mapkob（马尔科夫）链，利用一个新解产生装置和接受准则, 重复进行包括“产生新解计算目标函数判断是否接受新解（或舍弃）新解”这三个阶段，不断对当前解迭代，从而达到使目标函数最优（最大或最小）的执行过程。书中用于特征选择的模拟退火算法initilaize(i0,T0,L0)k:=0;i:=i0repeat for L:=1 to Lk do begin generate(j from Si); if f(i)949。经验法则

12、要求算法进程在合理时间里搜索尽可能大的空间范围，只有足够大的值才能满足这个要求。温度T的衰减函数衰减函数 (k0，1，2，.)。其中 是一个接近1的常数。这个衰减函数是Kirkpatrick等人首先提出来的，他们取 。Bonomi以及Lutton等许多研究者研究，认为值一般在0.5-0.99范围内取值为宜。Mapkob链的长度直接指定方式 n为循环次数此外，Skiscim和Nahar等人提出用单个Mapkob链的终止准则去产生Lk，Lk的值与Tk值相关。这类方法便于控制最终解的质量，却难以把握算法进程的时间。在Mapkob链的终止准准则选择不当时，甚至可能危及模拟退火算法的收敛性。而用限定Lk

13、的方法和他相反，它便于直接控制算法进程的CPU时间。停止准则停止准则1:循环n次停止。停止准则2:在若干个相继的Mapkob链无任何优化就停止算法。这种停止准则（准则2 ）兼顾了最终解的质量和CPU时间。在T，L等参数的配合下，可得到高质量最终解。模拟退火算法与初始值无关，算法求得的解与初始解状态无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法 。习题：叙述用于特征选择的增l减r搜索算法的算法步骤。并考虑l值大于（或小于）r值时，增l减r算法步骤应做出怎样的修改，以及该情况下，增l减r搜索算法的特点？为什么分类器设计中的最近邻法可以适用于线性不可

14、分的样本集？为什么最近邻法又称为分类器设计的非参数方法？它与fisher等参数方法在训练和预测阶段效率上有什么不同？遗传算法的运算过程主要分四个阶段，包括编码阶段、_、交叉阶段、_。叙述怎样利用模拟退火算法是进行特征选择。模拟退火算法采用_准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。其中，冷却进度表中的参数主要包括：初始温度、_、_、_等。 遗传算法的运算过程主要分四个阶段：包括编码阶段、选择阶段、交叉阶段、_。其中，_阶段可以加入最优保留策略，该策略的优点是_。遗传算法的初始群体规模过小，可能导致算法_现象发生，从而降低算法的搜索性能。遗传算法的终

15、止条件有多种，你认为使用_方法终止算法，能较好提高搜索结果的质量。 遗传算法遗传算法生物学基础遗传算法简介遗传算法的手工模拟计算示例0.650.240.4800.240.240.170.35个体1个体3个体4个体20.220.70.90.3选中1号个体选中4号个体选中4号个体选中2号个体产生一个0到1之间的随机数第1次第2次第3次第4次*轮盘赌方法，能够使得适应度大的个体更容易 存活和遗传到下一代存活个体四号个体被选中两次编码方法综述格雷码编码方法符号编码方法适应度尺度变换线性变换乘幂尺度变换指数尺度变换选择算子比例选择最优保存策略 随机联赛选择随机选择排序选择交叉算子单点交叉双点交叉和多点交叉均匀交叉算术交叉启发式交叉变异算子基本位变异均匀变异非均匀变异遗传算法的运行参数参考遗传算法原理及应用 周明 孙树栋 国防工业出版社 *生物应用：遗传算法支持向量机耦合特征基因挖掘方法（lili）为了芯片数据中挖掘与疾病相关基因，我