《模式识别课件特征pcac》由会员分享，可在线阅读，更多相关《模式识别课件特征pcac（120页珍藏版）》请在金锄头文库上搜索。
1、Chapter 6 第6章,Feature extraction and selection (特征提取和选择),特征提取和选择的目的(The Purpose of Feature extraction and selection),维数灾难(Curse of dimensionality) 计算复杂度(Computational complexity) 使分类器具有较好的推广能力(Good generalization properties of the classifier),维数灾难(Curse of dimensionality),在低维空间里很复杂的决策面，在高维空间里可以成为线性的
2、：,维数灾难(Curse of dimensionality),如果增加一些特征，会增加样本到类别均值的距离。,在高维空间里或用更加复杂的决策面可以改进分类性能。,维数灾难(Curse of dimensionality),但在实际中这种性能的提高却是行不通的。如只有n6个样本，维数d2，样本是线性可分的。,维数灾难(Curse of dimensionality),当样本数达到n10。与之对应的分布图如图所示。用二次函数解决。,维数灾难(Curse of dimensionality),当n=30时，其分布情况如图所示。,维数灾难(Curse of dimensionality),在样本数和
3、特征数相比较小时，即运用一个低维数比率n/d时，在训练集合上得到的分类器将会是完全错误的。 在设计分类器时需要多少个样本，就是说训练集合的最少样本数是多少？,维数灾难(Curse of dimensionality),在d维空间里基于每个样本的位置提炼出一个规则从而训练分类器，从某种意义上讲，这实际上是神经网络的工作过程。 为了得到有效的方法，可以人为地将每个特征值的范围分成m个间隔；在每个md超立方体中估计每个样本的位置。,维数灾难(Curse of dimensionality),由于这种超立方体的个数呈现指数增长，所以对于一个不是很小的d值，必须在一个稀疏空间里找到对应的映射，此时映射的
4、代表意义不是很好。 这种现象通常称之为维数灾难。,The Task of Feature extraction,存在大量特征，怎样选择最重要的特征使特征数减少同时尽可能地保证特征的分类判别信息？(Given a number of feature, how can one select the most important of them so as to reduce their number and at the same time retain as much as possible of their class discriminatory information?),基本概念,特征选
5、择和提取方法的优劣强烈地影响到分类器的设计及其性能，是模式识别中的关键问题之一。 特征选择和提取的基本任务是如何从许多原始特征中找出那些最有效、数目最少的特征。 一般首先制定特征提取和选择的准则，可以直接以反映类内类间距离的函数作为准则，以误判概率最小为准则，以类别判别函数为准则等。,类别可分离性判据,特征选择与提取的任务是求出一组对分类最有效的特征。因此需要一个定量的准则(或称判据)来衡量特征对分类的有效性。 这些判据应能反映各类在特征空间的中的分布情况，刻画各特征分量在分类识别中的重要性或贡献。希望可分性判据满足下列几条要求：,与错误概率有单调关系,与错误概率P(e)(或错误概率的上界及下
6、界)有单调关系。 这样使判据取最大值的效果一般说来其错误概率也较小，即测度，P(e),当特征独立时有可加性,即,这里Jij是第i类和第j类的可分性准则函数，Jij愈大，两类的分离程度就愈大，x1，x2，xd是一定类别相应特征的随机变量。,度量特性,判据具有“距离”的某些特性： Jij0， 当ij时 Jij = 0， 当i = j时 Jij = Jji,单调性,即加入新的特征时，判据不减小。 Jij (x1，x2，xd) Jij (x1，x2，xd，xd+1) 所构造的可分性判据不一定同时具有上述四个性质。,可分性判据,基于距离的可分性判据 基于概率的可分性判据 基于熵函数的可分性判据,基于距离
7、的可分性判据(1),各类样本可以分开是因为它们位于特征空间中的不同区域，显然这些区域之间距离越大类别可分性就越大。 对于空间中两个点之间的距离度量 d(x，y) = |xy| 求如何表示两个类区之间的距离。,基于距离的可分性判据(2),对于两类1及2情况，1中任一点与2中的每一点都有一个距离，把所有这些距离相加求平均，可用这个均值来代表这两类之间的距离。 假设x是1类中的某个点； Al= al，l =1，2，N2，是2类的点集，d为维数。,（共有Ni个距离）,基于距离的可分性判据(3),其均方距离,对于多类1，2，c情况，令 ， 分别为i类及j类中的d维特征向量， 为这两个向量间的距离，,则各
8、类特征向量之间的平均距离为：,基于距离的可分性判据(4),多维空间中两个向量之间有许多距离度量，在欧氏空间有：,用mi表示第i类样本集的均值向量：,用m表示所有各类的样本集总平均向量：,基于距离的可分性判据(5),其中(mi-m)T(mi-m)是第i类的均值向量与总体均值向量m间的平方距离，用先验概率加权平均后可以代表各类均值向量的平均平方距离：,也可以用类内和类间离散度矩阵定义Jd(x)的表达式：,令,基于距离的可分性判据(6),则,上面的推导是建立在有限样本集上的，式中的mi，m， ， 是对类均值 、总体均值 ，类间离散度矩阵Sb，和类内离散度矩阵Sw在样本基础上的估计值， 、 ，Sb，S
9、w的表达式如下：,基于距离的可分性判据(7),各类之间的平均距离也可表示为： Jd(x) = tr(Sw+Sb),基于概率的可分性判据(1),距离准则是直接从各类样本间的距离算出的，没有考虑各类的概率分布，不能确切表明各类交叠的情况，因此与错误概率没有直接关系。 优点是计算方便、直观、概念清楚。 对于两类问题，如图6.1，其中(a)为完全可分的情况，(b)为完全不可分的情况。,基于概率的可分性判据(2),假设先验概率相等，若对所有使p(x|2)0的点有p(x|1) = 0，如图6.1(a)，则两类完全可分；相反，如果对所有x，都有p(x|1) = p(x|2)，如图6.1(b)所示，则两类完全
10、不可分。,基于概率的可分性判据(3),分布密度的交叠程度可用分布密度函数p(x|1)和p(x|2)之间的距离Jp来度量，任何满足下述条件的函数都可作为类分离性的概率距离量度。 Jp为非负，即Jp0。 当两类完全不交叠时，Jp取最大值，若对所有x有p(x|2)0时有p(x|1) = 0，则Jp=Jpmax。 当两类分布密度相同时，Jp应为零，即若p(x|2) = p(x|1)，则Jp=0。,基于概率的可分性判据(4),离散度用来量度两类概率分布的模式之间的不一致性，得到最大离散度可成为使两类样本很好地区别开而选取特征的准则。 两类密度函数的似然比或负对数似然比对分类来说是一个重要的度量。设有两类
11、i及j，其对数似然比为：,基于概率的可分性判据(5),它可以提供i对j类的可分性信息，对i类的平均可分性信息为：,同样对j类的平均可分性信息为：,基于概率的可分性判据(6),定义离散度JD为区分i类和j类的总的平均信息，它等于两类平均可分信息之和：,离散度满足类别可分离性判据的条件。,设i、j两类都是d维的正态分布， ， ，即：,基于概率的可分性判据(7),对数似然比为：,基于概率的可分性判据(8),对于这两类的平均可分性信息为：,基于概率的可分性判据(9),两类间的离散度为：,上式中利用了迹的性质：trBAT = ATB（A、B是向量）。,基于概率的可分性判据(10),当两类的协方差矩阵相等
12、时，即当i =j =时，,对一维正态分布（d =1）时,特征提取的关键技术(Key techniques of the Feature extraction ),线性变换(Liner Transforms) 主成分分析(The Principal Components Analysis or KL transform) 奇异值分解(The Singular Value Decomposition) 离散傅立叶变换(The Discrete Fourier Transform ) 离散余弦和正弦变换(The Discrete Cosine and Sine Transforms) 小波变换(Wa
13、velet Transform),特征提取主成分分析(Feature extraction-PCA),Principal Components Analysis,什么是主成分分析(What is it?),主成分分析(PCA)是在最小均方误差意义上寻找最能代表原始数据的投影方向，目的是减少数据集的维数。(Principal component analysis (PCA) is seeking a projection that best represents the data in a least-squares sense . The purpose is to reduce the di
14、mensionality of a data set (sample).,Example 1,体重和身高是相关的，收缩压和心率也是相关的(Weight and height are probably highly correlated, and sbp (systolic blood pressure) and heart rate may be related. ) 用2个新变量pc1和pc2分别表示体重和身高的组合、收缩压、年龄和心率的组合(Imagine 2 new variables, pc1 and pc2, where pc1 is a combination of weight
15、and height while pc2 is a combination of sbp, age and heart rate. ),Example 1 (cont),因此，在信息损失很少的情况下，变量数从5个减少到2个。(Hence, the number of variables could be reduced from 5 to 2 with little loss of information. ) 这些新变量是从原始变量中提取的，称作主成分。(These new variables, derived from the original variables, are called
16、components. ),Example 1 (cont),这样，主成分分析的目的就是在信息损失最小的前提下，减少特征维数。通过变量间的相互关系，把数据投影到较少的维数空间。(Thus, the main aim of PCA is to reduce dimensionality with a minimum loss of information. This is achieved by projecting the data onto fewer dimensions that are chosen to exploit the relationships between the variables. ),Example 2,鹫是3维，但其照片是2维的，如图所示。(The golden eagle is 3-dimensional, but its photograph is 2-dimensio
