类内距离和类内散布矩阵ppt课件.ppt

《类内距离和类内散布矩阵ppt课件.ppt》由会员分享，可在线阅读，更多相关《类内距离和类内散布矩阵ppt课件.ppt（47页珍藏版）》请在三一办公上搜索。

1、第5章 特征选择与特征提取,5.1 基本概念5.2 类别可分性测度5.3 基于类内散布矩阵的单类模式特征提取5.4 基于K-L变换的多类模式特征提取,第5章 特征选择与特征提取,5.1 基本概念, 由于测量上可实现性的限制或经济上的考虑，所获得的测量值为数不多。 能获得的性质测量值很多。如果全部直接作为分类特征，耗费机时，且分类效果不一定好。有人称之为“特征维数灾难”。,特征选择和提取的目的：经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。,1两种数据测量情况,(1) 具有很大的识别信息量。即应具有很好的可分性。(2) 具有

2、可靠性。模棱两可、似是而非、时是时非等不易判别 的特征应丢掉。(3) 尽可能强的独立性。重复的、相关性强的特征只选一个。(4) 数量尽量少，同时损失的信息尽量小。,2对特征的要求,3. 特征选择和特征提取的异同,（1）特征选择：从L个度量值集合 中按一定准 则选出供分类用的子集，作为降维（m维，m L）的分类 特征。,（2）特征提取：使一组度量值 通过某种变换 产生新的m个特征 ，作为降维的分类特征， 其中 。,(c)是具有分类能力的特征，故选(c)，扔掉(a) 、 (b) 。,解：法1 特征抽取：测量三个结构特征 (a) 周长 (b) 面积 (c)两个互相垂直的内径比, 特征选择：一般根据物

3、理特征或结构特征进行压缩。, 分析：,例：特征选择与特征提取的区别：对一个条形和圆进行识别。,当模式在空间中发生移动、旋转、缩放时，特征值应保持不变，保证仍可得到同样的识别效果。,法2： 特征抽取：测量物体向两个坐标轴的投影值，则A、B各有2个值域区间。可以看出，两个物体的投影有重叠，直接使用投影值无法将两者区分开。, 分析：将坐标系按逆时针方向做一旋转变化，或物体按顺时针方向变，并适当平移等。根据物体在 轴上投影的坐标值的正负可区分两个物体。,特征提取，一般用数学的方法进行压缩。,5.2 类别可分性测度,5.2.1 基于距离的可分性测度,类别可分性测度：衡量类别间可分性的尺度。,相似性测度：

4、衡量模式之间相似性的一种尺度,类内距离和类间距离,类概率密度函数,1类内距离和类内散布矩阵,1) 类内距离：同一类模式点集内，各样本间的均方距离。,平方形式：,Xi,，Xj： n维模式点集X中的任意两个样本 。,特征选择和提取的结果应使类内散布矩阵的迹愈 ？愈好。,特征选择和提取的结果应使类内散布矩阵的迹愈 小愈好。,若X中的样本相互独立，有,式中，R：该类模式分布的自相关矩阵； M：均值向量； C：协方差矩阵；,：C主对角线上的元素，表示模式向量第k个分量的方差；,tr：矩阵的迹（方阵主对角线上各元素之和）。,2) 类内散布矩阵：表示各样本点围绕均值的散布情况 该类分布的协方差矩阵。,类间散

5、布矩阵的迹愈大愈有利于分类。,2类间距离和类间散布矩阵,1) 类间距离：模式类之间的距离，记为 。,每类模式均值向量与模式总体均值向量之间平方距离的先验概率加权和。,2) 类间散布矩阵：表示c类模式在空间的散布情况，记为Sb。,类间散布矩阵的迹愈？愈有利于分类。,3) 类间距离与类间散布矩阵的关系：,注意：与类间距离的转置位置不同。,3多类模式向量间的距离和总体散布矩阵,1）两类情况的距离,q个,个,共pq个距离,两个类区之间的距离 = pq个距离的平均距离,（5-8）,2）多类情况的距离,(2) Jd的另一种形式：将以下3式代入(5-8)式,(1)多类模式向量间的平均平方距离Jd,任意类的组

6、合,特定两类间任意样本的组合,得,某类类内平方距离平均值,某类类间平方距离,多类模式向量之间的平方距离=各类平方距离的先验概率加权和,3）多类情况的散布矩阵,多类类间散布矩阵 ：,4）多类模式平均平方距离与总体散布矩阵的关系,多类类内散布矩阵：, 各类模式协方差矩阵的 先验概率加权平均值。,多类模式的总体散布矩阵：,得,距离与散布矩阵作为可分性测度的特点： * 计算方便，概念直观（反映模式的空间分布情况 ）； * 与分类错误率没有直接的联系。,5.2.2 基于概率分布的可分性测度,1散度,出发点：对数似然比含有类别的可分性信息。,1）散度的定义,对不同的X，似然函数不同，对数似然比体现的可分性

7、不同，通常采用平均可分性信息对数似然比的期望值 。,类对数似然比的期望值：,类对数似然比的期望值：,散度等于两类的对数似然比期望值之和。,散度表示了区分i类和j 类的总的平均信息。,2）散度的性质,（1）,特征选择和特征提取应使散度尽可能的 ？,特征选择和特征提取应使散度尽可能的大。,（3）错误率分析中，两类概率密度曲线交叠越少，错误率越小。,由散度的定义式,可知，散度愈大，两类概率密度函数曲线相差愈大，交叠愈少，分类错误率愈小。,据此可估计每一个特征在分类中的重要性： 散度较大的特征含有较大的可分信息保留。,（5）可加性表明，加入新的特征，不会使散度减小。即,3）两个正态分布模式类的散度,设

8、i类和j 类的概率密度函数分别为,两类模式之间马氏距离的平方,一维正态分布时：,两类均值向量距离越远，散度愈大,每类自身分布愈集中，两类间的散度愈大,5.3 基于类内散布矩阵的单类模式特征提取,对某类模式：压缩模式向量的维数。,对多类分类：压缩维数； 保留类别间的鉴别信息，突出可分性。,特征提取的目的：,特征提取操作方法：,注意：维数降低后，在新的m维空间里各模式类之间的分布规 律应至少保持不变或更优化。,讨论内容： * 根据类内散布矩阵如何确定变换矩阵A； * 通过A如何进行特征提取。,1根据类内散布矩阵确定变换矩阵,式中，X为n维向量，C为 nn 的实对称矩阵。, n个特征向量相互正交。,

9、若选n个归一化特征向量作为A的行，则A为归一化正交矩阵：,(1),(2),Ann,(3) 变换后的类内距离,变换后：类内距离保持不变 。,根据以上特点得到构造变换矩阵的方法：,思路：,目标：构造一变换矩阵，可以将n维向量X变换成m维（mn）。,将变换前的C的n个特征值从小到大排队,选择前m个小的特征值对应的特征向量作为矩阵A的行（mn）,对X进行A变换,优点：压缩了维数； 类内距离减小，样本更密集 相当去掉了方差大的特征分量。,后 续,2特征提取的方法,其中，,第二步：计算C的特征值，对特征值从小到大进行排队，选择 前m个。,第四步：利用A对样本集X进行变换。,则m维（m n）模式向量X *就

10、是作为分类用的模式向量。,解：1) 求样本均值向量和协方差矩阵。,由,得,由归一化特征向量u1构成变换矩阵A：,变换前,变换后,5.4 基于K-L变换的多类模式特征提取,对一类模式：维数压缩。,对多类模式：维数压缩，突出类别的可分性。,特征提取的目的：,卡洛南-洛伊（Karhunen-Loeve）变换（K-L变换）：,* 一种常用的特征提取方法；,* 最小均方误差意义下的最优正交变换；,* 适用于任意的概率密度函数；,* 在消除模式特征之间的相关性、突出差异性方面 有最优的效果。,离散K-L变换,连续K-L变换,分为：,1K-L展开式,aj：随机系数；,用有限项估计X时 ：,引起的均方误差：,

11、uj为确定性向量,R：自相关矩阵。,：拉格朗日乘数,说明：当用X的自相关矩阵R的特征值对应的特征向量展开X 时，截断误差最小。,选前d项估计X时引起的均方误差为,因此，当用X的正交展开式中前d项估计X时，展开式中的uj应当是前d个较大的特征值对应的特征向量。,K-L变换方法：,对R的特征值由大到小进行排队：,均方误差最小的X的近似式：,矩阵形式：,式中， ， 。,其中：,（5-49）, K-L展开式,系数向量a就是变换后的模式向量。,2利用自相关矩阵的K-L变换进行特征提取,第一步：求样本集X的总体自相关矩阵R。,决定压缩后的维数,3不同散布矩阵的K-L变换,根据不同的散布矩阵进行K-L变换，

12、对保留分类鉴别信息的效果不同。,多类类内散布矩阵：,若要突出各类模式的主要特征分量： 选用对应于大特征值的特征向量组成变换矩阵；,若要使同一类模式聚集于最小的特征空间范围： 选用对应于小特征值的特征向量组成变换矩阵。,类间散布矩阵：,适用于类间距离比类内距离大得多的多类问题，选择与大特征值对应的特征向量组成变换矩阵。,总体散布矩阵：,把多类模式合并起来看成一个总体分布。,适合于多类模式在总体分布上具有良好的可分性的情况。采用大特征值对应的特征向量组成变换矩阵，能够保留模式原有分布的主要结构。,1）变换在均方误差最小的意义下使新样本集X *逼近原样本集 X的分布，既压缩了维数又保留了类别鉴别信息

13、。,利用K-L变换进行特征提取的优点：,2）变换后的新模式向量各分量相对总体均值的方差等于原样本 集总体自相关矩阵的大特征值，表明变换突出了模式类之间 的差异性。,3）C*为对角矩阵说明了变换后样本各分量互不相关，亦即消 除了原来特征之间的相关性，便于进一步进行特征的选择。,K-L变换的不足之处：,1）对两类问题容易得到较满意的结果。类别愈多，效果愈差。,2）需要通过足够多的样本估计样本集的协方差矩阵或其它类型的散布矩阵。当样本数不足时，矩阵的估计会变得十分粗略，变换的优越性也就不能充分的地显示出来。,3）计算矩阵的本征值和本征向量缺乏统一的快速算法，给计算带来困难。,例5.3 两个模式类的样

14、本分别为,利用自相关矩阵R作K-L变换，把原样本集压缩成一维样本集。,解：第一步：计算总体自相关矩阵R。,第二步：计算R的本征值，并选择较大者。由 得,多类类内散布矩阵Sw,5.5 特征选择,从n个特征中选择d个(d n)最优特征构成分类用特征向量。,5.5.1 特征选取择的准则,1散布矩阵准则,类别可分性测度,类间散布矩阵Sb,多类总体散布矩阵St,特征选择准则,使tr(Sw)最小,使tr(Sb)最大,使J1J4最大,2散度准则,用于正态分布的模式类。,两类的散度表达式,* 平均散度,选择使J最大的特征子集,* 变换散度,* 平均变换散度,5.5.2 特征选择的方法,从n个特征中挑选d个特征

15、，所有可能的特征子集数为,组合数很大,穷举法：,计算出各种可能特征组合的某个测度值，加以比较，选择最优特征组。,特点：,计算量大，难实现。采取搜索技术可降低计算量。,可以得到最优特征组；,1最优搜索算法,分支定界算法：唯一能获得最优结果的搜索方法。,自上而下、具有回溯功能。,使用条件：,可分性测度 J 对维数单调。,方法：,待选择的n个原特征为根；,* 将可能的特征组构成树结构。,子结点的特征组元素个数逐级下降；,叶结点按照规定的特征数构成特征组合。,* 从最右边的叶结点开始，根据选择的测度回溯搜索。,* 找到最优特征组，结束。,例：从5个特征中选出2个特征作为模式向量。,2次优搜索算法,虽然不能得到最优解，但可减少计算量。,1）单独最优特征组合,2）顺序前进法（Sequential Forward Selection，SFS）,3）顺序后退法（Sequential Backward Selection，SBS）,4）增l减r法（lr法）：SFS和SBS的组合。,广义顺序前进法（Generalized SFS，GSFS）,广义顺序后退法（Generalized SBS，GSBS）,广义的lr法,其他：模拟退火（Simulated Annealing）算法 Tabu搜索（Tabu Search）算法 遗传算法（Genetic Algorithm）,结束,