特征选择与特征提取2014学习教案.pptx

会计学1特征选择与特征提取特征选择与特征提取2014第一页，共58页。2引言引言(ynyn)n n特征是决定样本之间的相似性和分类器设计的关键n n如何(rh)找到合适的特征是模式识别的核心问题n n在实际问题中,常常不容易找到那些最重要的特征n n 或者受条件限制不能对它们进行测量,这使得特征选择和提取的任务复杂化 n n特征选择成为构造模式识别系统、提高决策精度的最困难的任务之一第2页/共58页第二页，共58页。3引言引言(ynyn)n n模式(msh)三大基本特征：物理、结构和数字特征n n物理和结构特征：易于为人的直觉感知，但有时难于定量描述，因而不易用于机器判别n n数字特征：易于用机器定量描述和判别，如基于统计的特征第3页/共58页第三页，共58页。4引言引言(ynyn)n n一般情况下普遍认为，增加(zngji)特征向量的维数（增加(zngji)特征数）将有助于提高分类器的质量n n但实际应用中特征维数却收到多方面因素的约束和限制n n用较多的特征进行分类器设计，无论从计算的复杂程度还是就分类器性能来看都是不适宜的 第4页/共58页第四页，共58页。5特征特征(tzhng)的形成的形成n n特征形成特征形成(acquisition)：n n信号采集信号采集原始测量原始测量原始特征原始特征n n实例实例(shl)n n数字图像中的各像素灰度值数字图像中的各像素灰度值n n人体的各种生理指标人体的各种生理指标n n语音的音调周期、共振峰、声道参数、频谱语音的音调周期、共振峰、声道参数、频谱第5页/共58页第五页，共58页。6特征特征(tzhng)的形成的形成n n高维原始高维原始(yunsh)特征不利于分类器设计特征不利于分类器设计n n计算量大计算量大n n信息冗余信息冗余第6页/共58页第六页，共58页。7特征选择与提取特征选择与提取(tq)n n分析原始特征的有效性，选出最有代表性的特征是模式识别的关键(gunjin)一步n n降低特征维数在很多情况下是有效设计分类器的重要课题第7页/共58页第七页，共58页。8特征选择与提取特征选择与提取(tq)n n两类获取有效(yuxio)特征信息、压缩特征空间的方法：特征提取和特征选择n n基本任务是如何从原始特征中获取最有效(yuxio)的信息第8页/共58页第八页，共58页。9特征选择与提取特征选择与提取(tq)n n特征(tzhng)选择(selection)n n从原始特征(tzhng)中挑选出一些最有代表性，分类性能最好的特征(tzhng)n n特征(tzhng)提取(extraction)n n通过映射或变换的方法把高维的原始特征(tzhng)变换为低维的新特征(tzhng)，新的特征(tzhng)包含了原有特征(tzhng)的有用信息第9页/共58页第九页，共58页。10特征选择与提取特征选择与提取(tq)n n目前，还没有特征选择和提取的一般方法，这是由于特征选择一般是面向(min xin)问题的，很难对这些方法去作评价和比较 n n特征选择与提取是模式识别中重要而困难的一个环节第10页/共58页第十页，共58页。11特征选择与提取特征选择与提取(tq)n n细胞自动识别n n原始测量(cling)n n 正常或异常细胞的数字图像n n原始特征n n 找到一组代表细胞性质的特征：细胞面积，胞核面积，形状系数，光密度，核内纹理，和浆比n n 原始特征的维数仍很高，需压缩以便于分类！第11页/共58页第十一页，共58页。12特征选择与提取特征选择与提取(tq)n n细胞自动识别n n特征选择n n 挑选最有分类信息(xnx)的特征n n特征提取n n 数学变换：傅立叶变换或小波变换、特征压缩第12页/共58页第十二页，共58页。13特征选择特征选择n n特征选择的任务是从一组数量为D的特征中选择出数量为d(D d)的一组最优特征n n各个特征之间存在复杂的相互关系n n 如果仅对每个单独的特征按照一定的统计进行排队(pi du),取排在前面的d个特征n n 所得结果在大多数情况下不是最优特征组第13页/共58页第十三页，共58页。14特征选择特征选择n n从D个特征中选择出d个最优的特征,在这两个(lin)参数都已知的状况下,所有可能的组合数为n n如果D=100，d=10，则的Q数量级是1013第14页/共58页第十四页，共58页。15特征选择特征选择n n在实际问题的研究过程当中，D的维数往往远远高于100n n例如,在利用生物芯片来进行药物设计和癌症诊断时,其产生的有效特征维数往往在10000左右n n实际需要选取的优化特征组的特征数量是未知的n n寻找可行的特征选择算法已逐渐成为国际(guj)上研究的热点第15页/共58页第十五页，共58页。16特征选择特征选择n n一般来看，特征(tzhng)选择（确定优化的特征(tzhng)子集）需要两个主要步骤n n确定评价准则来评价所选择的特征(tzhng)子集的性能n n确定进行特征(tzhng)搜索所需要的策略第16页/共58页第十六页，共58页。17特征选择特征选择n n按搜索策略划分的特征选择算法(sun f)n n全局最优搜索策略n n “分支定界”算法(sun f)：该方法能保证在事先确定优化特征子集中特征数目的情况下,找到相对于所设计的可分性判据而言的最优特征子集。n n 如何事先确定优化特征子集当中特征的数目？n n 当处理高维度多类问题时，算法(sun f)运算效率低下第17页/共58页第十七页，共58页。18特征选择特征选择n n按搜索(su su)策略划分的特征选择算法n n随机搜索(su su)策略n n 将特征选择视为组合优化问题，采用非全局最优搜索(su su)方法n n 把特征选择问题和模拟退火算法、禁忌搜索(su su)算法、遗传算法、或随机重采样过程结合,以概率推理和采样过程作为算法基础n n 遗传算法在这一领域的应用最为广泛第18页/共58页第十八页，共58页。19特征选择特征选择n n按搜索策略划分(hu fn)的特征选择算法n n启发式搜索策略n n 单独最优特征组合算法n n 序列前向选择算法n n 序列后向选择算法n n 浮动搜索算法第19页/共58页第十九页，共58页。20特征选择特征选择n n特征选择的原则n n选择反映模式(msh)本质特性的参数作为特征n n使样本类间距离较大、类内距离较小n n与类别信息不相关的变换（平移、旋转、尺度变换）具有不变性n n尽量选择相关性小的特征n n尽可能不受噪声的干扰第20页/共58页第二十页，共58页。21基于基于(jy)主成份的特征提取：主成份的特征提取：K-L变换变换n nK-L变换(Karhunen-Loeve Transform,卡洛南-洛伊变换)是将高维特征向量映射为低维特征向量的有效方法n n目的：n n 提取出空间原始数据(shj)的主要特征(主元或主成份)，减少数据(shj)冗余，使得数据(shj)在一个低维的特征空间被处理，同时保持原始数据(shj)的绝大部份有用信息，从而解决数据(shj)维度过高的瓶颈问题。第21页/共58页第二十一页，共58页。方法：将 维特征向量 ，通过特征变换(binhun)得到另一 维特征向量特征向量 ，使得 与原向量 的均方误差最小 22第22页/共58页第二十二页，共58页。23K-L变换变换(binhun)n n设 为 维特征向量，即：n n 现在(xinzi)维特征空间中选取一组新的正交基底向量 n n 即：第23页/共58页第二十三页，共58页。24K-L变换变换(binhun)n n将 在该基底(j d)向量上进行投影得到新向量 ，即n n 则向量 可表示为：第24页/共58页第二十四页，共58页。25K-L变换变换(binhun)X原空间原空间Y新空间新空间y1y2x1x2第25页/共58页第二十五页，共58页。26K-L变换变换(binhun)n n可见不同的基底向量 ，将 投影后可产生不同的向量n n现要寻求(xnqi)一组有效的基底向量，实现特征压缩的目的 第26页/共58页第二十六页，共58页。27K-L变换变换(binhun)n n考虑(kol)：第27页/共58页第二十七页，共58页。28K-L变换变换(binhun)n n 将 中 以后各项用常数(chngsh)代替得：第28页/共58页第二十八页，共58页。29K-L变换变换(binhun)n n 定义(dngy)误差向量第29页/共58页第二十九页，共58页。30K-L变换变换(binhun)X原空间原空间y新空间新空间yX第30页/共58页第三十页，共58页。31K-L变换变换(binhun)n n则平方(pngfng)误差为第31页/共58页第三十一页，共58页。32K-L变换变换(binhun)n n由于(yuy)n n则有第32页/共58页第三十二页，共58页。33K-L变换变换(binhun)n n若现有一批样本(yngbn)，则均方误差为：n n 可见，均方误差与基底向量 和 有关 第33页/共58页第三十三页，共58页。34K-L变换变换(binhun)n n如何选择 和 ，使得均方误差(wch)最小？n n为什么要这样做？第34页/共58页第三十四页，共58页。35K-L变换变换(binhun)n n首先考虑(kol)若 确定，如何选择？n n 令n n 即第35页/共58页第三十五页，共58页。36K-L变换变换(binhun)n n则有第36页/共58页第三十六页，共58页。37K-L变换变换(binhun)n n再考虑(kol)当 用最佳值 代替后，如何确定？n n 第37页/共58页第三十七页，共58页。38K-L变换变换(binhun)n n 确定(qudng)后，均方误差第38页/共58页第三十八页，共58页。39K-L变换变换(binhun)n n即：协方差矩阵协方差矩阵(j zhn)经典数学经典数学(shxu)问题问题第39页/共58页第三十九页，共58页。40K-L变换变换(binhun)n n结论：n n使均方误差 最小的基底向量 ，即是协方差矩阵(j zhn)n n 的本征向量n n 如何求本征向量？第40页/共58页第四十页，共58页。41K-L变换变换(binhun)n n本征值n n协方差矩阵 的本征值，即满足(mnz)的 值n n共有i 个本征值单位矩阵单位矩阵第41页/共58页第四十一页，共58页。42K-L变换变换(binhun)n n本征向量(xingling)n n满足方程 的向量(xingling)n n共有i 个本征向量(xingling)第42页/共58页第四十二页，共58页。43K-L变换变换(binhun)n n当 为协方差矩阵 的本征向量时，均方误差n n可见应保留本征值较大(jio d)的本征向量为基底向量！为什么？第43页/共58页第四十三页，共58页。44K-L变换变换(binhun)n n总结：n n将 压缩(y su)到n n 将产生误差n n 压缩(y su)维数越多 将越大，即丢失的信息越多。n n 第44页/共58页第四十四页，共58页。45K-L变换变换(binhun)n n为了有效减少 ，应在压缩时，保留本征较大的本征向量为基底(j d)向量，即排序n n而选择本征值较大的m个本征向量为基底(j d)向量n n压缩后的特征向量为 第45页/共58页第四十五页，共58页。46K-L变换变换(binhun)n n而n n称为(chn wi)X的m个主成份第46页/共58页第四十六页，共58页。47K-L变换变换(binhun)n nK-L变换进行特征(tzhng)维数压缩的过程：n n获取一批学习样本 n n计算其均值 n n计算其协方差矩阵n n计算协方差矩阵的n个本征值 第47页/共58页第四十七页，共58页。48K-L变换变换(binhun)n n将 由大到小排序值为 n n计算本征值对应的本征向量(xingling)，即 n n根据具体要求将特征向量(xingling)降为m维向量(xingling)第48页/共58页第四十八页，共58页。49K-L变换变换(binhun)n n例：设已知样本的特征向量为：n n试用K-L变换(binhun)将X压缩为一维的4个样本，并求出均方误差 第49页/共58页第四十九页，共58页。50K-L变换变换(binhun)X2X3X4X1第50页/共58页第五十页，共58页。51K-L变换变换(binhun)n n解：n n 求出样本均值（期望值）第51页/共58页第五十一页，共58页。52K-L变换变换(binhun)n n求协方差矩阵(j zhn)第52页/共58页第五十二页，共58页。53K-L变换变换(binhun)n n计算(j sun)协方差矩阵的本征值 n n 即计算(j sun)n n 解得第53页/共58页第五十三页，共58页。54K-L变换变换(binhun)n n计算协方差矩阵(j zhn)的本征向量 n n 解得：第54页/共58页第五十四页，共58页。55K-L变换变换(binhun)n n特征(tzhng)压缩后 第55页/共58页第五十五页，共58页。56K-L变换变换(binhun)Y3Y4Y1Y2第56页/共58页第五十六页，共58页。57K-L变换变换(binhun)n n均方误差(wch)第57页/共58页第五十七页，共58页。模式识别(m sh sh bi)，第八章58感谢您的观看感谢您的观看(gunkn)！第58页/共58页第五十八页，共58页。