模式识别第讲特征的选择与提取.ppt

现在学习的是第1页，共97页第10讲 特征的选择与提取(2)现在学习的是第2页，共97页本节课主要内容n n1 1 类别可分离性判据类别可分离性判据n n2 2 特征提取特征提取n n3 3 特征选择特征选择现在学习的是第3页，共97页3 3 特征选择特征选择n n1 1 最优搜索算法最优搜索算法n n2 2 次优搜索法次优搜索法n n3 3 可分性判据的递推计算可分性判据的递推计算n n4.4.特征选择的几种新方法特征选择的几种新方法现在学习的是第4页，共97页n n 特征选择的任务是从一组数量为特征选择的任务是从一组数量为特征选择的任务是从一组数量为特征选择的任务是从一组数量为D D的特征中选择出的特征中选择出 数量为数量为数量为数量为d d（DdDd）的一组最优特征来）的一组最优特征来）的一组最优特征来）的一组最优特征来.n n 利用穷举法总可以找出最优的特征集利用穷举法总可以找出最优的特征集利用穷举法总可以找出最优的特征集利用穷举法总可以找出最优的特征集,但计算量太但计算量太但计算量太但计算量太 大大.从从从从D D个特征中选取个特征中选取个特征中选取个特征中选取d d个个个个,共共 种组合。种组合。如如:若若D=20,d=10,D=20,d=10,则从则从则从则从D D个特征中选取个特征中选取d d个特征的个特征的个特征的个特征的组合数组合数组合数组合数q=184756,对每一种组合需要计算判据值对每一种组合需要计算判据值对每一种组合需要计算判据值对每一种组合需要计算判据值J(x)J(x)最优特征的选择，要解决最优特征的选择，要解决两个问题两个问题两个问题两个问题:选择的标准选择的标准选择的标准选择的标准，这可以用类可分离性判据，这可以用类可分离性判据，这可以用类可分离性判据，这可以用类可分离性判据.确定一个较好的算法确定一个较好的算法确定一个较好的算法确定一个较好的算法，以便找出最优的特征集，以便找出最优的特征集，以便找出最优的特征集，以便找出最优的特征集.现在学习的是第5页，共97页本节主要讨论第二个问题，简单介绍几种优化算法本节主要讨论第二个问题，简单介绍几种优化算法本节主要讨论第二个问题，简单介绍几种优化算法本节主要讨论第二个问题，简单介绍几种优化算法.自下而上法自下而上法 特征数从特征数从0逐步增加到逐步增加到d用优化算法进行特征选择的两种策略用优化算法进行特征选择的两种策略:自上而下法自上而下法 从特征数从从特征数从D开始逐步减少到开始逐步减少到d现在学习的是第6页，共97页1.1.最优搜索算法最优搜索算法到目前为止唯一能获得最优结果的搜索方法是到目前为止唯一能获得最优结果的搜索方法是到目前为止唯一能获得最优结果的搜索方法是到目前为止唯一能获得最优结果的搜索方法是“分支定界分支定界”算法，它是一种算法，它是一种算法，它是一种算法，它是一种“自上而下自上而下自上而下自上而下”的方法，但具有回溯功能，的方法，但具有回溯功能，的方法，但具有回溯功能，的方法，但具有回溯功能，可使所有可能的特征组合都被考虑到。可使所有可能的特征组合都被考虑到。可使所有可能的特征组合都被考虑到。可使所有可能的特征组合都被考虑到。由于合理的组织搜索过程，使得有可能避免计算某些特由于合理的组织搜索过程，使得有可能避免计算某些特由于合理的组织搜索过程，使得有可能避免计算某些特由于合理的组织搜索过程，使得有可能避免计算某些特征组合而不影响结果为最优。征组合而不影响结果为最优。征组合而不影响结果为最优。征组合而不影响结果为最优。整个搜索过程可用树来表示整个搜索过程可用树来表示整个搜索过程可用树来表示整个搜索过程可用树来表示树的根结点表示原始特征集树的根结点表示原始特征集树的根结点表示原始特征集树的根结点表示原始特征集,其他结点表示从其父结点所其他结点表示从其父结点所其他结点表示从其父结点所其他结点表示从其父结点所代表的特征子集中去掉某一特征后所得到的特征子集代表的特征子集中去掉某一特征后所得到的特征子集代表的特征子集中去掉某一特征后所得到的特征子集代表的特征子集中去掉某一特征后所得到的特征子集,结点结点结点结点上的标号是去掉的特征的编号上的标号是去掉的特征的编号上的标号是去掉的特征的编号上的标号是去掉的特征的编号.现在学习的是第7页，共97页分支定界法的搜索树示意图分支定界法的搜索树示意图(D=6(D=6(D=6(D=6，d=2)d=2)X根结点根结点根结点根结点:原始特征集原始特征集原始特征集原始特征集结点标号结点标号结点标号结点标号:去掉的特征去掉的特征去掉的特征去掉的特征35 645 6654253466 6545566665345544321每一结点表示去掉若干每一结点表示去掉若干每一结点表示去掉若干每一结点表示去掉若干特征后得到的子集特征后得到的子集特征后得到的子集特征后得到的子集.从左到右同一级结点对从左到右同一级结点对从左到右同一级结点对从左到右同一级结点对应的特征子集的类可分应的特征子集的类可分应的特征子集的类可分应的特征子集的类可分性判据值递增性判据值递增性判据值递增性判据值递增.说明说明说明说明现在学习的是第8页，共97页分支定界法之所以有效分支定界法之所以有效,这主要是利用了可分离性判据这主要是利用了可分离性判据的单调性，即对有包含关系的特征组的单调性，即对有包含关系的特征组 A Ak k，k=1=1，2，I I，即有：，即有：，即有：，即有：可分性判据满足：可分性判据满足：现在学习的是第9页，共97页2.2.次优搜索法次优搜索法最优搜索法在有些情况下计算量太大而难以实现，这时最优搜索法在有些情况下计算量太大而难以实现，这时不得不放弃最优解而采取计算量较小的次优搜索方法。不得不放弃最优解而采取计算量较小的次优搜索方法。下面我们介绍一些不同的算法，面对实际问题时可灵活下面我们介绍一些不同的算法，面对实际问题时可灵活选择。选择。（1 1）单独最优特征组合）单独最优特征组合最简单的方法是计算各特征单独使用时的判据值并加以排队，最简单的方法是计算各特征单独使用时的判据值并加以排队，取前取前d d个作为选择结果。但我们需要注意的是，即使各特征是个作为选择结果。但我们需要注意的是，即使各特征是统计独立的，这一结果也不一定就是最优结果。统计独立的，这一结果也不一定就是最优结果。只有当可分性判据只有当可分性判据J可写为如下两种形式时，这种方法才可写为如下两种形式时，这种方法才能选出一组最优的特征来：能选出一组最优的特征来：现在学习的是第10页，共97页（2 2）顺序前进法（）顺序前进法（）顺序前进法（）顺序前进法（SFSSFS）这是最简单的这是最简单的这是最简单的这是最简单的“自下而上自下而上自下而上自下而上”的搜索方法。每次从未入选的的搜索方法。每次从未入选的的搜索方法。每次从未入选的的搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起特征中选择一个特征，使得它与已入选的特征组合在一起特征中选择一个特征，使得它与已入选的特征组合在一起特征中选择一个特征，使得它与已入选的特征组合在一起时所得判据时所得判据时所得判据时所得判据J J值为最大，直到特征数增加到值为最大，直到特征数增加到值为最大，直到特征数增加到值为最大，直到特征数增加到d d d d为止为止为止为止现在学习的是第11页，共97页（3 3 3 3）顺序后退法（）顺序后退法（）顺序后退法（）顺序后退法（SBSSBS）它与顺序前进法的思路刚好相反。这是一种它与顺序前进法的思路刚好相反。这是一种它与顺序前进法的思路刚好相反。这是一种它与顺序前进法的思路刚好相反。这是一种“自上而下自上而下自上而下自上而下”的方法，从全体特征开始每次剔除一个，所剔除的特征应的方法，从全体特征开始每次剔除一个，所剔除的特征应的方法，从全体特征开始每次剔除一个，所剔除的特征应的方法，从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的判据使仍然保留的特征组的判据使仍然保留的特征组的判据使仍然保留的特征组的判据J值最大，直到特征数减少到值最大，直到特征数减少到值最大，直到特征数减少到值最大，直到特征数减少到d d为止。为止。为止。为止。和顺序前进法比较，该方法用两个特点：一是在计算过程中可和顺序前进法比较，该方法用两个特点：一是在计算过程中可和顺序前进法比较，该方法用两个特点：一是在计算过程中可和顺序前进法比较，该方法用两个特点：一是在计算过程中可以估计每去掉一个特征所造成可分性的降低；二是由于它的计以估计每去掉一个特征所造成可分性的降低；二是由于它的计以估计每去掉一个特征所造成可分性的降低；二是由于它的计以估计每去掉一个特征所造成可分性的降低；二是由于它的计算是在高维空间中进行的，所以计算量比较大。算是在高维空间中进行的，所以计算量比较大。算是在高维空间中进行的，所以计算量比较大。算是在高维空间中进行的，所以计算量比较大。现在学习的是第12页，共97页比方说，在第比方说，在第比方说，在第比方说，在第k k步可先用步可先用步可先用步可先用SFSSFS法一个个加入特征到法一个个加入特征到法一个个加入特征到法一个个加入特征到 k+l k+l 个，个，个，个，然后再用然后再用然后再用然后再用SBSSBS法一个个剔去法一个个剔去法一个个剔去法一个个剔去 r 个特征，我们把这样一种算法个特征，我们把这样一种算法个特征，我们把这样一种算法个特征，我们把这样一种算法叫增叫增叫增叫增 l l 减减减减 r r 法（法（法（法（lr lr 法）法）（4）增）增 l 减减减减 r r 法（法（法（法（lr lr 法）法）法）法）这种方法是基于前两种算法的特点提出的这种方法是基于前两种算法的特点提出的这种方法是基于前两种算法的特点提出的这种方法是基于前两种算法的特点提出的.为了避免前面为了避免前面方法的一旦被选入方法的一旦被选入(或剔除或剔除或剔除或剔除)就不能再剔除就不能再剔除就不能再剔除就不能再剔除(或选入或选入或选入或选入)的缺点可的缺点可的缺点可的缺点可在选择过程中加入局部回溯过程。在选择过程中加入局部回溯过程。在选择过程中加入局部回溯过程。在选择过程中加入局部回溯过程。现在学习的是第13页，共97页3.3.可分性判据的递推计算可分性判据的递推计算所有上述搜索算法都有一个共同点，即第所有上述搜索算法都有一个共同点，即第所有上述搜索算法都有一个共同点，即第所有上述搜索算法都有一个共同点，即第 k k 步特征组是在步特征组是在步特征组是在步特征组是在第第第第 k k1 1 1 1 步特征组上加入或剔除某些特征来构成的，因此我步特征组上加入或剔除某些特征来构成的，因此我步特征组上加入或剔除某些特征来构成的，因此我步特征组上加入或剔除某些特征来构成的，因此我们可以分析一下，是否有可能从们可以分析一下，是否有可能从们可以分析一下，是否有可能从们可以分析一下，是否有可能从 k1 1 1 1 步的判据值步的判据值步的判据值步的判据值 J(k-1)J(k-1)推算出推算出 J(k),J(k),J(k),J(k),而不必完全重新计算而不必完全重新计算而不必完全重新计算而不必完全重新计算.事实上，对于有些情况，对于这些判据递推关系是存在的，事实上，对于有些情况，对于这些判据递推关系是存在的，事实上，对于有些情况，对于这些判据递推关系是存在的，事实上，对于有些情况，对于这些判据递推关系是存在的，即求即求即求即求J(k)J(k)J(k)J(k)时可在时可在时可在时可在 J(k-1)J(k-1)J(k-1)J(k-1)的基础上把新加入（或剔除）特征的的基础上把新加入（或剔除）特征的的基础上把新加入（或剔除）特征的的基础上把新加入（或剔除）特征的影响加进去即可，不必从头算起，这样就大大简化了计算影响加进去即可，不必从头算起，这样就大大简化了计算影响加进去即可，不必从头算起，这样就大大简化了计算影响加进去即可，不必从头算起，这样就大大简化了计算工作工作工作工作.现在学习的是第14页，共97页我们注意到在进行特征选择时需要以可分性判据来度量特征我们注意到在进行特征选择时需要以可分性判据来度量特征我们注意到在进行特征选择时需要以可分性判据来度量特征我们注意到在进行特征选择时需要以可分性判据来度量特征选择的好坏选择的好坏选择的好坏选择的好坏.特征选择是一个组合优化问题特征选择是一个组合优化问题特征选择是一个组合优化问题特征选择是一个组合优化问题,因此可以使用解因此可以使用解因此可以使用解因此可以使用解决优化问题的方法来解决特征选择问题决优化问题的方法来解决特征选择问题决优化问题的方法来解决特征选择问题决优化问题的方法来解决特征选择问题.优化问题是很多研究人员关注的一个热点问题，近年来出现了优化问题是很多研究人员关注的一个热点问题，近年来出现了优化问题是很多研究人员关注的一个热点问题，近年来出现了优化问题是很多研究人员关注的一个热点问题，近年来出现了一些有特色的解决方法一些有特色的解决方法一些有特色的解决方法一些有特色的解决方法,如如如如:1)1)1)1)模拟退火算法模拟退火算法2)2)2)2)遗传算法遗传算法遗传算法遗传算法3)Tabu3)Tabu3)Tabu3)Tabu搜索算法搜索算法4.4.特征选择的几种新方法特征选择的几种新方法现在学习的是第15页，共97页来源于统计力学。材料粒子从高温开始，非常缓慢地来源于统计力学。材料粒子从高温开始，非常缓慢地降温降温(退火退火)，粒子就可在每个温度下达到热平衡。假，粒子就可在每个温度下达到热平衡。假设材料在设材料在状态状态状态状态i i的能量为的能量为的能量为的能量为 E(i)，那么材料在，那么材料在，那么材料在，那么材料在温度温度温度温度 T T时时时时从状从状态态i进入状态进入状态j遵循如下规律遵循如下规律遵循如下规律遵循如下规律1)1)模拟退火算法模拟退火算法模拟退火算法模拟退火算法如果如果如果如果 E(j)E(i)E(j)E(i)，接受该状态被转换。，接受该状态被转换。，接受该状态被转换。，接受该状态被转换。如果如果 E(j)E(i)E(j)E(i)，则状态转换以如下概率被接受：，则状态转换以如下概率被接受：，则状态转换以如下概率被接受：，则状态转换以如下概率被接受：现在学习的是第16页，共97页1)1)1)1)模拟退火算法模拟退火算法模拟退火算法模拟退火算法模拟退火优化法：模拟退火优化法：模拟退火优化法：模拟退火优化法：f f :xR:xR+，其中其中xS，表示优化问题的一个可行解。，表示优化问题的一个可行解。N(x)SN(x)S 表示表示表示表示x x的一个邻域集合。的一个邻域集合。的一个邻域集合。的一个邻域集合。现在学习的是第17页，共97页首先给定初始温度首先给定初始温度首先给定初始温度首先给定初始温度T T0 0和初始解和初始解和初始解和初始解 x(0)x(0)，以概率，以概率，以概率，以概率P P生成下一个新生成下一个新生成下一个新生成下一个新解解解解x x 1)1)1)1)模拟退火算法模拟退火算法模拟退火算法模拟退火算法对于温度对于温度对于温度对于温度T Ti i和该优化问题的解和该优化问题的解和该优化问题的解和该优化问题的解x(k)x(k)，可以生成新解，可以生成新解，可以生成新解，可以生成新解xx经过多次转换，降低温度得到经过多次转换，降低温度得到 T T i+1i+1 dY空间空间 D 维维原始特征集原始特征集Y空间空间 d 维维新特征集新特征集变换变换确定变换的依据确定变换的依据确定变换的依据确定变换的依据:类别可分性判据类别可分性判据目标目标目标目标:在新的特征空间中在新的特征空间中在新的特征空间中在新的特征空间中,各类之间容易区分各类之间容易区分.2 特征提取特征提取现在学习的是第62页，共97页 根据前面提到的类别可分离性判据。我们可以依据这些判据根据前面提到的类别可分离性判据。我们可以依据这些判据进行特征的提取。进行特征的提取。设原特征向量设原特征向量 ，对，对 作线性变换，产生作线性变换，产生 d d 维向量维向量 ，即，即 矩阵矩阵 称为特征提取矩阵或变换矩阵，称为特征提取矩阵或变换矩阵，称为二次特征。称为二次特征。现在学习的是第63页，共97页 s s阶阶MinkowskiMinkowski度量度量多维空间中两个向量之间有多种距离度量多维空间中两个向量之间有多种距离度量 欧氏距离欧氏距离在在MinkowskiMinkowski度量中，令度量中，令s=2s=2，得到常用的欧氏距离：，得到常用的欧氏距离：1.1.按欧氏距离度量的特征提取方法按欧氏距离度量的特征提取方法现在学习的是第64页，共97页 Chebychev Chebychev距离距离:棋盘距离棋盘距离 Mahalanobis Mahalanobis距离距离:式中式中Q Q是给定的正定标尺矩阵是给定的正定标尺矩阵现在学习的是第65页，共97页在实际应用中，在计算的复杂性方面，在是否便于进行在实际应用中，在计算的复杂性方面，在是否便于进行解析分析以及用它进行特征提取的效果方面都各不相同。解析分析以及用它进行特征提取的效果方面都各不相同。由于欧氏距离在很多情况下便于分析和计算由于欧氏距离在很多情况下便于分析和计算.前面已经推导出了基于欧氏距离的一种度量函数，前面已经推导出了基于欧氏距离的一种度量函数，其中其中S Sb b为类间离散度矩阵为类间离散度矩阵,S,Sw为类内离散度矩阵为类内离散度矩阵.同样的，我们还可以提出下面各种判据：同样的，我们还可以提出下面各种判据：现在学习的是第66页，共97页以以J J2 2为例为例,特征提取的步骤如下特征提取的步骤如下 作线性映射：作线性映射：其中其中其中其中Y为为D D维原始特征向量；维原始特征向量；X X为为d d维压缩后的特征向量维压缩后的特征向量维压缩后的特征向量维压缩后的特征向量 令令其中其中其中其中S Sw w，Sb b为原空间（即为原空间（即为原空间（即为原空间（即Y的）离散度矩阵，的）离散度矩阵，S S*w w，S S*b 为为为为映射后（即映射后（即映射后（即映射后（即X的）离散度矩阵。的）离散度矩阵。的）离散度矩阵。的）离散度矩阵。现在学习的是第67页，共97页 J J2 2的表达式为：的表达式为：求变换矩阵求变换矩阵求变换矩阵求变换矩阵W,W,使使使使 J J2 2（WW）最大）最大）最大）最大将上式对将上式对将上式对将上式对WW的各分量求偏导数并令其为零的各分量求偏导数并令其为零的各分量求偏导数并令其为零的各分量求偏导数并令其为零,可以确定一可以确定一个个WW，从而得到使判据达最大的变换，从而得到使判据达最大的变换，从而得到使判据达最大的变换，从而得到使判据达最大的变换WW 新特征集为新特征集为其中其中Y为原始特征集为原始特征集(D维维),X为新特征集为新特征集(d 维维)现在学习的是第68页，共97页注注:WW的计算（适用于的计算（适用于的计算（适用于的计算（适用于J J J J2 2 2 2JJ5 5 5 5判据）：判据）：判据）：判据）：则选前则选前d 个特征值对应的特征向量作为个特征值对应的特征向量作为W，即：，即：W=u1,u2,ud 此时此时现在学习的是第69页，共97页2.2.基于判别熵最小化的特征提取基于判别熵最小化的特征提取上节中讨论了用熵作为不确定性的一种度量的表达式，这上节中讨论了用熵作为不确定性的一种度量的表达式，这上节中讨论了用熵作为不确定性的一种度量的表达式，这上节中讨论了用熵作为不确定性的一种度量的表达式，这里我们引入判别熵里我们引入判别熵里我们引入判别熵里我们引入判别熵 W(p,q)W(p,q)来表征两类分布来表征两类分布来表征两类分布来表征两类分布 p p(xi i)和和和和 q q(xj j)差差别大小别大小,令：令：对于特征提取来说，我们应该对于特征提取来说，我们应该对于特征提取来说，我们应该对于特征提取来说，我们应该求得一组特征，它使上述判求得一组特征，它使上述判求得一组特征，它使上述判求得一组特征，它使上述判别熵别熵别熵别熵最小最小最小最小。现在学习的是第70页，共97页计算步骤如下计算步骤如下:A=G1 A=G1-G2,G1G2,G1，G2G2分别是第一类样本集和第二类样本集分别是第一类样本集和第二类样本集分别是第一类样本集和第二类样本集分别是第一类样本集和第二类样本集的协方差矩阵的协方差矩阵的协方差矩阵的协方差矩阵Y Y为所要求的一组特征，它使得判别熵最小为所要求的一组特征，它使得判别熵最小 新特征集为新特征集为 将矩阵将矩阵A A的特征值进行排序的特征值进行排序选取前选取前d d个特征值对应的特征向量构成变换矩阵个特征值对应的特征向量构成变换矩阵W=UW=U1 1，U U2 2，U Ud d 现在学习的是第71页，共97页3.3.两维显示两维显示n n 人的经验和直观对分类有很大作用，如果能将各样本在特人的经验和直观对分类有很大作用，如果能将各样本在特人的经验和直观对分类有很大作用，如果能将各样本在特人的经验和直观对分类有很大作用，如果能将各样本在特征空间的分布情况显示出来，我们可以直接观察哪些样本聚征空间的分布情况显示出来，我们可以直接观察哪些样本聚征空间的分布情况显示出来，我们可以直接观察哪些样本聚征空间的分布情况显示出来，我们可以直接观察哪些样本聚集在一起，因而可能属于一类。集在一起，因而可能属于一类。集在一起，因而可能属于一类。集在一起，因而可能属于一类。n n 最好能把最好能把原来的高维特征空间映射到二维平面上原来的高维特征空间映射到二维平面上原来的高维特征空间映射到二维平面上原来的高维特征空间映射到二维平面上显示出显示出显示出显示出来，这一映射要尽可能的保持原来样本的分布情况，或者尽来，这一映射要尽可能的保持原来样本的分布情况，或者尽来，这一映射要尽可能的保持原来样本的分布情况，或者尽来，这一映射要尽可能的保持原来样本的分布情况，或者尽量使各样本间相互距离关系保持不变量使各样本间相互距离关系保持不变量使各样本间相互距离关系保持不变量使各样本间相互距离关系保持不变.n n 上述所讨论的各种变换方法有利于我们解决这样一种两上述所讨论的各种变换方法有利于我们解决这样一种两上述所讨论的各种变换方法有利于我们解决这样一种两上述所讨论的各种变换方法有利于我们解决这样一种两维显示的任务维显示的任务维显示的任务维显示的任务.现在学习的是第72页，共97页 线性映射线性映射两维显示只不过是前面所涉及的各种映射两维显示只不过是前面所涉及的各种映射(线性线性)的一种特殊情况的一种特殊情况,即即d=2d=2 非线性映射非线性映射对一些比较复杂的样本对一些比较复杂的样本,线性映射常不能满足上面所线性映射常不能满足上面所提的保持分布不变的要求提的保持分布不变的要求,可以用非线性映射替代可以用非线性映射替代现在学习的是第73页，共97页设映射前两点间距离为设映射前两点间距离为设映射前两点间距离为设映射前两点间距离为D D，映射后该两点间距离为，映射后该两点间距离为，映射后该两点间距离为，映射后该两点间距离为D*.D*.希望映射后希望映射后希望映射后希望映射后D*D*尽可能等于尽可能等于尽可能等于尽可能等于D.D.令令令令 e=DD*e=DD*为任意两点映射前后距离之差，我们要为任意两点映射前后距离之差，我们要为任意两点映射前后距离之差，我们要为任意两点映射前后距离之差，我们要选择映射函数选择映射函数选择映射函数选择映射函数 f f使使使使e e的函数值达最小的函数值达最小的函数值达最小的函数值达最小.由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个x x的初值，再逐步调整（每次调整的方向应使误差减小），直到的初值，再逐步调整（每次调整的方向应使误差减小），直到的初值，再逐步调整（每次调整的方向应使误差减小），直到的初值，再逐步调整（每次调整的方向应使误差减小），直到满足一个停止准则（例如，误差小于给定值，迭代次数超过预满足一个停止准则（例如，误差小于给定值，迭代次数超过预满足一个停止准则（例如，误差小于给定值，迭代次数超过预满足一个停止准则（例如，误差小于给定值，迭代次数超过预定次数，或显示结果已满足观察者要求为止定次数，或显示结果已满足观察者要求为止定次数，或显示结果已满足观察者要求为止定次数，或显示结果已满足观察者要求为止).).现在学习的是第74页，共97页本节课结束 谢谢大家！现在学习的是第75页，共97页n n1 设有两类三维样本，都服从正态分布，且样本均设有两类三维样本，都服从正态分布，且样本均值和协方差矩阵分别为：值和协方差矩阵分别为：n n1).1).计算其类可分性散度判据计算其类可分性散度判据计算其类可分性散度判据计算其类可分性散度判据JDJD的值的值的值的值n n2).利用基于类内类间距离的判据利用基于类内类间距离的判据 进行最优特征提取。进行最优特征提取。现在学习的是第76页，共97页n n2 设样本均值为（设样本均值为（1 1，2 2），样本的协方差矩阵和相关），样本的协方差矩阵和相关），样本的协方差矩阵和相关），样本的协方差矩阵和相关矩阵分别为：矩阵分别为：矩阵分别为：矩阵分别为：计算分别用计算分别用计算分别用计算分别用 和和和和R R计算得到的主成分，并说明其差异。计算得到的主成分，并说明其差异。计算得到的主成分，并说明其差异。计算得到的主成分，并说明其差异。现在学习的是第77页，共97页4.4.基于主成分变换的特征提取方法基于主成分变换的特征提取方法n n在实际问题中在实际问题中在实际问题中在实际问题中,研究多变量问题是经常遇到的，然而在多数情况下研究多变量问题是经常遇到的，然而在多数情况下研究多变量问题是经常遇到的，然而在多数情况下研究多变量问题是经常遇到的，然而在多数情况下,不同指标之间是有一定相关性。由于指标较多不同指标之间是有一定相关性。由于指标较多不同指标之间是有一定相关性。由于指标较多不同指标之间是有一定相关性。由于指标较多,再加上指标之间再加上指标之间再加上指标之间再加上指标之间有一定的相关性，势必增加了分析问题的复杂性有一定的相关性，势必增加了分析问题的复杂性有一定的相关性，势必增加了分析问题的复杂性有一定的相关性，势必增加了分析问题的复杂性.主成分分析就是主成分分析就是主成分分析就是主成分分析就是设法将原来指标重新组合成一组新的相互无关的几个综合指标设法将原来指标重新组合成一组新的相互无关的几个综合指标设法将原来指标重新组合成一组新的相互无关的几个综合指标设法将原来指标重新组合成一组新的相互无关的几个综合指标来代替原来指标来代替原来指标来代替原来指标来代替原来指标,同时根据实际需要从中可取几个较少的综合指同时根据实际需要从中可取几个较少的综合指同时根据实际需要从中可取几个较少的综合指同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息。标尽可能多地反映原来指标的信息。标尽可能多地反映原来指标的信息。标尽可能多地反映原来指标的信息。n n这种这种这种这种将多个指标化为少数相互无关的综合指标的统计方法叫做将多个指标化为少数相互无关的综合指标的统计方法叫做将多个指标化为少数相互无关的综合指标的统计方法叫做将多个指标化为少数相互无关的综合指标的统计方法叫做主成分分析（主成分分析（主成分分析（主成分分析（Principal Component Analysis).Principal Component Analysis).现在学习的是第78页，共97页n n某人要做一件上衣要测量很多尺寸某人要做一件上衣要测量很多尺寸,如身长、袖长等十如身长、袖长等十如身长、袖长等十如身长、袖长等十几项指标几项指标几项指标几项指标,但某服装厂要生产一批新型服装绝不可能把但某服装厂要生产一批新型服装绝不可能把尺寸的型号分得过多尺寸的型号分得过多,而是从多种指标中综合成几个少而是从多种指标中综合成几个少而是从多种指标中综合成几个少而是从多种指标中综合成几个少数的综合指标数的综合指标数的综合指标数的综合指标,作为分类的型号作为分类的型号作为分类的型号作为分类的型号,如下图如下图如下图如下图:4 4 基于主成分变换的特征提取方法基于主成分变换的特征提取方法现在学习的是第79页，共97页4 4 基于主成分变换的特征提取方法基于主成分变换的特征提取方法n n主成分分析的基本方法是通过构造原变量的适当的线性组合主成分分析的基本方法是通过构造原变量的适当的线性组合主成分分析的基本方法是通过构造原变量的适当的线性组合主成分分析的基本方法是通过构造原变量的适当的线性组合,以产以产以产以产生一系列互不相关的新信息生一系列互不相关的新信息生一系列互不相关的新信息生一系列互不相关的新信息,从中选出少数几个新变量并使它们含从中选出少数几个新变量并使它们含从中选出少数几个新变量并使它们含从中选出少数几个新变量并使它们含有尽可能多的原变量带有的信息有尽可能多的原变量带有的信息有尽可能多的原变量带有的信息有尽可能多的原变量带有的信息,从而使得用这几个新变量代替原变从而使得用这几个新变量代替原变从而使得用这几个新变量代替原变从而使得用这几个新变量代替原变量分析问题和解决问题成为可能量分析问题和解决问题成为可能量分析问题和解决问题成为可能量分析问题和解决问题成为可能.当研究的问题确定之后当研究的问题确定之后当研究的问题确定之后当研究的问题确定之后,变量中所含变量中所含变量中所含变量中所含“信息信息信息信息”的大小通常用该变量的方差或样本方差来度量的大小通常用该变量的方差或样本方差来度量的大小通常用该变量的方差或样本方差来度量的大小通常用该变量的方差或样本方差来度量.省份省份GDPX1居民消居民消费费水平水平X2固定固定资资产产投投资资X3职职工平工平均工均工资资X4货货物周物周转转 量量X5居民消居民消费费价格指数价格指数X6商品零售商品零售价格指数价格指数X7工工业总业总产产 值值X8现在学习的是第80页，共97页n n如如如如图图图图,设设设设二二二二维样维样维样维样本集呈本集呈本集呈本集呈现现现现扁扁扁扁椭圆椭圆椭圆椭圆分布分布分布分布.x1x2un n将二将二将二将二维样维样维样维样本本本本XiXi向向长长轴轴方向投影方向投影,可得到可得到可得到可得到一一一一维样维样维样维样本本本本YiYin n设设设设u u为长轴为长轴为长轴为长轴方向的方向的方向的方向的单单单单位向量位向量位向量位向量,则则则则有有有有Xi iYi一般如何求一般如何求一般如何求一般如何求“最好最好最好最好”的方向的方向的方向的方向 u u4 4 基于主成分变换的特征提取方法基于主成分变换的特征提取方法现在学习的是第81页，共97页（1）数学模型）数学模型n n设设设设 X1,X X2,Xp p 为某实际问题所涉及的为某实际问题所涉及的为某实际问题所涉及的为某实际问题所涉及的p个随机变量个随机变量个随机变量个随机变量.记记记记 X=X=(X(X1 1,X X2 2,X,Xp)T T,其协方差矩阵为其协方差矩阵为n n设设设设l li i=(=(l l1 1i i,l l2 2i i,l lpipi)T T(i i=1,2,=1,2,p p)为为为为p p个常数向量个常数向量个常数向量个常数向量,考虑如下线考虑如下线考虑如下线考虑如下线性组合性组合性组合性组合:现在学习的是第82页，共97页我们希望用我们希望用Y Y1代替原来代替原来p p个变量个变量个变量个变量,这就要求这就要求这就要求这就要求Y Y1 1尽可能的反映尽可能的反映原原p p个变量的信息个变量的信息,即即即即VarVar(Y Y1)越大越大.为此为此,我们对我们对l li i做如下限制做如下限制做如下限制做如下限制,否则否则否则否则VarVar(Y1 1)无界无界,即即即即:因此因此因此因此,我们希望在约束条件我们希望在约束条件我们希望在约束条件我们希望在约束条件 l l1 1Tl l1 1=1 之下之下之下之下,求求求求l l1 1使达到最大使达到最大使达到最大使达到最大,由此由此l1 1所确定的随机变量所确定的随机变量所确定的随机变量所确定的随机变量 Y1 1=l l1 1T TX X 称为称为 X X1 1,X X2 2,X,Xp p 的的第一主成分第一主成分第一主成分第一主成分.现在学习的是第83页，共97页如果第一主成分如果第一主成分如果第一主成分如果第一主成分Y Y1还不足以反映原变量的信息还不足以反映原变量的信息还不足以反映原变量的信息还不足以反映原变量的信息,考虑采用考虑采用考虑采用考虑采用Y Y2 2.但要求但要求但要求但要求Y Y1 1与与Y2不相关不相关不相关不相关,即即即即于是于是,在约束条件在约束条件 及及 之下之下,求求 l2 使使Var(Y2)达到最大达到最大,由此由此 l2 所确定的随机变量所确定的随机变量Y2=l2TX 称为称为X1,X2,Xp 的的第二主成分第二主成分.一般一般,在约束条件在约束条件 及及 (k=1,2,i-1)之下之下,求求li 使使Var(Yi)达到最大达到最大,由此由此 li 所确所确定的随机变量定的随机变量 Yi=liTX 称为称为 X1,X2,Xp 的的第第i个主成分个主成分.现在学习的是第84页，共97页n n并且有并且有并且有并且有:n n定理定理1 设设是是X=(X1,X2,Xp)T的协方差矩阵的协方差矩阵,的特的特征值及其相应的正交单位特征向量分别为征值及其相应的正交单位特征向量分别为 及及 e1,e2,ep,则则X的第的第i个主成分为个主成分为现在学习的是第85页，共97页n n下面进一步讨论下面进一步讨论下面进一步讨论下面进一步讨论 X X1 1,X X2,X,Xp 的方差与各主成分的方差的方差与各主成分的方差的方差与各主成分的方差的方差与各主成分的方差之间的关系之间的关系之间的关系之间的关系,以确定各主成分所包含的信息占总信息的份额以确定各主成分所包含的信息占总信息的份额以确定各主成分所包含的信息占总信息的份额以确定各主成分所包含的信息占总信息的份额.易证下面结果易证下面结果易证下面结果易证下面结果:n n定理定理定理定理2 2 设设设设Y Yi i=e=ei iTX X(i=i=1,21,2,p,p)为为为为X X的的的的p p各主成分各主成分各主成分各主成分,则则则则:当当 时，时，达到最大值达到最大值现在学习的是第86页，共97页n n定义定义定义定义 第第k k个主成分个主成分个主成分个主成分Y Yk k的贡献率为的贡献率为的贡献率为的贡献率为:n n前前前前mm个主成分个主成分个主成分个主成分Y Y1 1,Y Y2 2,Y,Ym的累计贡献率为的累计贡献率为:n n在实际应用中在实际应用中在实际应用中在实际应用中,通常选取通常选取mpmp,使前使前使前使前m个累计贡献率达到一个累计贡献率达到一定的比例定的比例(80%90%).这样用前这样用前这样用前这样用前mm 个主成分代替原来的变个主成分代替原来的变个主成分代替原来的变个主成分代替原来的变量量量量X1,X,X2,X,Xp p而不至于损失太多的信息而不至于损失太多的信息而不至于损失太多的信息而不至于损失太多的信息,从而到达减少变量从而到达减少变量从而到达减少变量从而到达减少变量个数的目的个数的目的个数的目的个数的目的.现在学习的是第87页，共97页n n在实际问题中在实际问题中在实际问题中在实际问题中,一般一般(或或或或)是未知的是未知的是未知的是未知的,需要通过样本来估需要通过样本来估需要通过样本来估需要通过样本来估计计计计.设设n n其中其中其中其中（2）主成分的计算方法）主成分的计算方法现在学习的是第88页，共97页n n分别以分别以S S和和R R作为作为作为作为和和和和 的估计的估计的估计的估计,按前面所述的方法求得按前面所述