第九章特征选择与降维sect91单个特征的评价.ppt

2023/6/23,北京邮电大学信息工程学院,1,第九章 特征选择与降维 9-1 单个特征的评价,在本节中，我们首先介绍几个对于单个特征进行评价的方法。评价每个特征的标准通常是它的分类能力。通过对于各个特征的评价，可以选出那些对于分类最有效的特征，淘汰那些无效的特征。,2023/6/23,北京邮电大学信息工程学院,2,一.K-W 检验,K-W（Kruskal and Wallis）检验是一种常用的特征选择方法。假定要检验某个特征x对于分类的有效程度,已知一批样品共有N个，这批样品分为m类，第i类包括品，则检验方法如下：(1)列出全部样品对应的特征x的取值。(2)按照x取值从小到大的顺序给每个样品编号。例如，x取值最小的样品编号为1，x取值次小的样品编号为2，等等。若有几个样品所对应的x值相同，可以对它们随机编号，也可以采用平均也可以采用随机编号的办法。(3)取每类各样品编号的平均值，分别记作。(4)计算统计量H，公式为：,2023/6/23,北京邮电大学信息工程学院,3,(9.1)在实用中一般只需比较各特征的H值，H越大时，特征的分类能力越强。例9.1 设有N10个样品，共分m2类，每个样品取4个特征，用KW检验比较特征的分类能力。原始资料矩阵见表9.1。,表9.1 原始矩阵,2023/6/23,北京邮电大学信息工程学院,4,首先对 将各样品按值大小编号，所对应的 值最小(0.18)。编号为第1号，编为第2号，全部编号结果列在表9.2的第一行中。于是有 表9.2 对于各样品的重新编号,2023/6/23,北京邮电大学信息工程学院,5,对于 分别有，。所以特征 的分类能力最强，次之，最差。K-W检验的原理是清楚的。首先，式(9.1)括号中的(N1)/2是全体样品编号的均值，而 是各类样品编号的均值，因此H实际上相当于特征x对应编号的组间离差。其次，用编号代替特征x的原有取值也是不难理解的。在表9.1中，两类样品所对应的特征 的原有取值的平均值都是0.7，即两类均值完全相同。从这一事实来看，应该是一个很坏的特征。但是，用 对样品分类时，如果取0.4和0.5之间的某个数，例如0.45作为分界点，被分错的却只有一个点。这又说明 这个特征不太坏。那么何以会出现两类均值相同的现象呢？不难看出，这是由于,2023/6/23,北京邮电大学信息工程学院,6,点 的 值太大而造成的结果。用编号代替特征则可以排除这种干扰。因为编号只反映特征的大小顺序，而不考虑其数值。,二直方图方法,我们仍然考虑例9.1。特征的变化范围在0.1到0.9之间。我们把这一范围分为几个长度为0.1的区间，在每个区间内画出落在该区间内的样品点数与总数之比(f)。这样的图形称为特征值-样品频数直方图。对于每特征分两类做出这样的直方图，其中 和 的直方图见图9.1。,2023/6/23,北京邮电大学信息工程学院,7,图 9.1 特征值-样品频数直方图,a,b,2023/6/23,北京邮电大学信息工程学院,8,在图9.1中可以看到，在 的直方图中两类样品可以比较清楚地分开，而在特征 的直方图则有较多的混淆现象。因此，直方图可以作为检验特征分类能力的一种工具。从直方图出发可以构造所谓可接受的运算特征(ROC)曲线。一个一般的直方图如图9.2(a)所示。任意取x轴上一点t作为分界点。第一类样品被判错部分的面积记为，第二类被判错部分记作，不断改变t的位置，并将点(,1-)画在平面上，便形成图9.2(b)中的ROC曲线。图中的面积A表示特征x的分类能力，A越大，x的分类能力越强。现在我们来做例9.1中特征 的ROC曲线，使t从 开始逐渐增加直到，对应的和值记在表9.3中，ROC曲线见图9.2(c)。,2023/6/23,北京邮电大学信息工程学院,9,从直方图出发还可以设计另外的特征选择方法。例如，在图9.1(a)中把两类中互不混淆的部分分别记作 和。当有多个特征时，先从中挑选一个使 之值最大的特征，并且去掉那些可以用这个特征分开的样品，再从剩下的样品中挑选其他的特征。表9.3 特征的ROC曲线计算步骤,图9.2 ROC曲线,2023/6/23,北京邮电大学信息工程学院,10,三利用不确定性选择特征,不确定性或熵是信息论中的概念。假定要考查某个特征 x的分类能力。首先把x的取值范围分为k段，把样品点落到其中第j段的频率记作。又设样品共有m类，把第i类样品点落到第j段的频率记作。然后计算熵：熵越小则x的分类能力越强。,(9.2),2023/6/23,北京邮电大学信息工程学院,11,例9.2 设有40个样品点共分两类，其中某特征x的变化范围在0.20到0.90之间。将这个范围分为两段，所得结果列在表9.4中。,表9.4 特征x之熵的计算步骤,2023/6/23,北京邮电大学信息工程学院,12,由表9.4求出A0.8089。熵的原理可以用两个极端的例子说明。在上例中，若第一段中只有第一类样品而第二段内只有第二类样品，则 最后得到A0。另一方面，如果每段内的两类样品数都相等，则 最后得到。以上两种情形分别对应于x的分类能力最强和最弱的两种状态。,2023/6/23,北京邮电大学信息工程学院,13,四用于有序样品的特征选择方法,有序样品，指那些按照某种次序或位置排列的样品。例如，在研究某个地区的强震弱震规律时，每个样品表示一个“时间段”，其长度通常取1至3年，全部样品可以按照其时间先后次序排列。对于这种样品的聚类称为满足邻接条件的聚类问题。对于用来描述有序样品的各种特征，可以采用以上所介绍的各种方法进行评价和选择。但是，这时还应该考虑特征的“顺序依赖性”。下面我们通过一个例子介绍顺序依赖性的概念，以及利用这种性质进行特征选择的方法。,2023/6/23,北京邮电大学信息工程学院,14,例 9.3 假设已知10各样品点，按照下标从小到大的次序排列，x是用描述这些样品点的一个特征，它的取值如表9.5所示。由表9.5可见，x共有3种可能的取值：0，1，2。做出x的直方图，并计算x的每种取值出现的概率，见表9.6。,表 9.5 特征x的顺序取值,表 9.6 特征x的取值范围,2023/6/23,北京邮电大学信息工程学院,15,我们假设把样品点 想象为上文中所说的时间段，而把特征x想象为每段时间前的若干年内6.06.9级地震的发生次数。根据这种想象，x在不同时间段上的先后取值应该是有联系的，而不能认为是独立的随机变量。由这一假定出发，我们建立描述这种先后联系关系的转移概率矩阵P。P通过以下两步算出：(1)求矩阵,其中每个元素 等于表中上一段x取值编号为i，而下一段x取值编号为j的次数，i，j1,2,3。例如,当ij1时,表示上段时间x取零,而下段时间x也取零的次数。这种情况在表9.5中共发生了三次，即m从3到4，从4变到5和从9变到10，所以，同样，(m从5到6)，照此计算最后得到矩阵：,2023/6/23,北京邮电大学信息工程学院,16,(2)用 中每行元素之和去除该行的每个元素，得到转移概率矩阵P：其中每个元素 表示特征x从编号i转移到编号j的概率。,2023/6/23,北京邮电大学信息工程学院,17,形成转移概率矩阵P以后，便可由此出发首先计算特征编号i的熵或分散程度：如果所有特征编号为i的样品点都具有这样的性质：它们的下一点特征编号相同，例如为j1，那么，由于，所以;而由于对j1有,所以。这时 将取得最小值零。反之，特征编号为i的诸点下一步转移趋势越分散时，也越大。特征x的总体熵可以定义为：,(9.3),2023/6/23,北京邮电大学信息工程学院,18,其中p(i)等于x取值编号为i的概率，见表9.6的最后一行。同样，E越大表示特征x的分散程度越大。对于上面所举的例子，有：,总体熵是对于特征顺序依赖性的一种量度，它可以作为评价特征作用的参考。一般地说，E取值较小时x的作用较大。但是，由于同一个熵值可能对应着不同的分布情况，因此也有可能出现E很小，分类效果却不好的情况。不过，总体熵作为一种评价顺序依赖性的参考指标仍是有意义的。本节介绍了几种对于单项特征进行评选的方法。当然，根据分类结果对特征进行评选可能更有说服力。,2023/6/23,北京邮电大学信息工程学院,19,9.2 主成分分析和对应分析,在第一节中，我们介绍了评价单个特征分类能力的一些方法，利用这些方法可以挑选出最有效的特征。可惜的是，已经有人证明了以下事实：如果我们依次挑选出前M个最有效的单个特征，那么这M个特征放在一起却不一定是M个特征的最佳组合。这一事实在一定程度上可以这样解释：假定我们在诊断某种疾病时发现体温是最有效的特征，而白血球个数是下一个有效地特征。那么，由于体温与白血球个数之间有着很密切的关系（“相关性”），因此这两个特征组合在一起实质上只相当于一个特征。,2023/6/23,北京邮电大学信息工程学院,20,从本节开始，我们将陆续介绍另外一些特征选择方法。它们的共同特点在于：不在从原有特征中进行选择和淘汰，而是利用原有各个特征去构造一批新特征。每个新特征都是原有各特征的函数。但是新特征的总数应该少于原有特征的总数。这样，我们的新特征集合既保留了原有各特征的主要信息，又达到了减少特征个数，即降低空间维数的目的。这一类方法可以统称为降维映射方法。本节首先介绍两种最常使用的降维映射的方法，即主成分分析和对应分析。它们都属于所谓线性映射方法，也就是说，由它们构造出的每个新特征都是原有各特征的线性函数。,2023/6/23,北京邮电大学信息工程学院,21,一.主成分分析,线性变换实际上相当于一种坐标变换。利用坐标变换可以从原有特征得到一批个数相同的新特征，而且这些特征中的前几个可能包含了原有特征中的主要信息。主成分分析就是从这一观点出发的特征选择方法。一.基本概念 现在来考虑更一般的情况。假定对每个样品取n个特征，即。要求构造n个新特征，并使它们满足以下的条件：,(1)每个新特征是原有各特征的线性组合，即 i=1,2,n 或 其中各 是常数,(9.4),2023/6/23,北京邮电大学信息工程学院,22,(2)各个新变量之间是不相关的，即相关系数为零：i=1,2,n ij(3)使 的方差达到极大，使 的方差达到次大，等等。满足以上条件的新特征 分别称为样品点的第1，2，n个主成分。下面讨论怎样求出各个，或者说怎样求出各个。首先求出全体样品点的协方差矩阵：,(9.5),2023/6/23,北京邮电大学信息工程学院,23,这里S的下标x表示这是对应旧特征 的协方差矩阵。然后，求出 的n个特征值 和与之对应的特征向量。每个 是一个数，而与之对应的特征向量是一个列向量，它们之间的关系是：，i1，2，n 因此求 和 相当于解以上的方程。具体的解法例如，雅克比（Jacobi）方法可在各种计算方法教材中找到。如果我们在解方程时还要求正交归一条件 i,j1，2，n 成立，则各个 就是唯一确定的。,(9.6),(9.7),2023/6/23,北京邮电大学信息工程学院,24,现在我们来说明，用以上方法所求的各个 就可满足前面所说的条件(1)(3)。令，i1，2，n，也就是令 或 YUX(9.8)于是 就是由 经线性变换而得到的新特征。可以证明，当经过上述形式的线性变换后，如果对应于X的协方差矩阵是，那么对应于Y的协方差矩阵就是,(9.9),2023/6/23,北京邮电大学信息工程学院,25,注意到 的每列恰好是 的一个特征向量并利用条件(9.6)得到 其中 是以 为主对角线元素的主对角阵。再利用正交归一条件(9.7)，又可得到 这就是说：新特征 两两之间的协方差为零，即它们是不相关的。这样，我们已经找到了解决主成分分析问题的关键，即求原始协方差矩阵的特征值和特征向量。,(9.10),2023/6/23,北京邮电大学信息工程学院,26,我们再来强调一下主成分分析三条件的作用：条件(1)是线性条件，它反映新老特征之间的关系是简单的，便于计算；条件(2)是不相关性，它要求每个新特征都有着独立的作用；条件(3)是方差极大条件。每个特征的方差数值在一定意义下反映了它所包含的信息量。当前几个新特征的信息量已经足够大时，便可以舍弃其余的新特征，从而达到减少特征个数的目的。二.计算步骤 下面，我们来详细叙述主成分分析的计算步骤。假定原始资料矩阵已知。,2023/6/23,北京邮电大学信息工程学院,27,(1)求出原有特征的协方差矩阵。(2)用任一种计算方法求出 的全部特征值 和对应的特征向量。考虑到上面条件(3)的要求,求出各个特征值后应将它们按照从大到小的顺序排列，也就是使特征向量也应按照对应特征值的顺序排列。在上段中已经知道，这时已经可以求出n个新特征，它们满足条件YUX，其中U等于矩阵 的转置，而且 是对角阵。在 中 主对角元素之和 等于原有各特征方差之和。在 中，分别等于新特征 的方差，而且 之值仍然等于。,(2.11),2023/6/23,北京邮电大学信息工程学院,28,(3)我们定义第i个主成分 的“方差贡献率”为 前m个主成分 的“累计方差贡献率”为 当前m个主成分的累计方差贡献率已经足够大(例如，达到70%，80%或更大)时，就可以只取前m个主成分作为新的特征。这是有其后的nm个新特征可以舍去。,(2.12),(2.13),(2.14),2023/6/23,北京邮电大学信息工程学院,29,主成分分析的计算到这里本来已经完成，下面是两点补充。我们称第k个新特征(主成分)与第i个旧特征 之间的相关系数 为 在 上的“因子负荷量”，计算公式为 求出全体并作出因子负荷量矩阵：这个矩阵有以下两点性质：(1)每行元素平方之和为1。(2)第k列各元素平方再乘以对应原有元素方差之和为,即,(9.15),2023/6/23,北京邮电大学信息工程学院,30,由此出发，也可定义前m个主成分对原有变量 的累计贡献率为当 足够大时，可以认为前m个主成分 已经包含了 中的主要信息量。例9.4 我们举两个最简单的例子说明主成分分析的计算步骤。假设有两批样品，每批样品数为N4，特征数n2。两批样品的原始资料矩阵见表9.7。,样品,特征,特征,样品,表9.7 两批样品的原始资料矩阵,2023/6/23,北京邮电大学信息工程学院,31,根据上面所讲的计算步骤，首先计算每批样品的协方差矩阵，结果为：然后分别计算两个协方差矩阵的特征值和特征向量，得到 特征值 特征向量 特征值 特征向量 与 的相同。由此可知，对于两组样品利用主成分分析所得的新特征都是,2023/6/23,北京邮电大学信息工程学院,32,即：这一公式表示新特征即主成分所对应的坐标系相当于将原坐标系旋转 而得，见图9.3。,图9.3 主成分分析的几何解释,2023/6/23,北京邮电大学信息工程学院,33,下面分别对两组数据计算主成分的累计方差贡献率，对 有：即只用第一主成分已可包含了原数据的全部信息。这点是显而易见的因为全部四4个点都分布在 轴上。对于 则有：即只用 时要损失原有信息的20%。三.应用实例 下面举出一个应用主成分分析解决实际问题的例子。例9.5 为了解决服装定型的问题，对N128个成年男人测量体型，每人测量n16项指标，分别为：,2023/6/23,北京邮电大学信息工程学院,34,(身长)，(坐高)，(胸围)，(头高)，(裤长)，(下裆)，(手长)，(领围)，(前胸)，(后背)，(肩厚)，(肩宽)，(袖长)，(肋围)，(腰围)，(腿肚)为了节省篇幅，只列出各特征的均值和方差，见表9.8。这一问题的讨论共分四步：(1)相关分析。首先，由原始资料矩阵（未列出）求出16个特征的相关系数矩阵R，见表9.9，表中只列出了下三角部分。对相关系数矩阵进行初步观察可以得出以下结论：1)凡是反映“长”的特征，彼此之间的相关系数都比较大。例如，(身长)与(头高)的相关系数为0.96。2)凡是反映“围”的特征，彼此间的相关系数也比较大。,2023/6/23,北京邮电大学信息工程学院,35,例如，(胸围)与(肋围)的相关系数为0.64。3)“长”与“围”之间的相关系数相对较小。例如，与 之间的相关系数为0.36。由此可见，“长”与“围”两类特征大体上反映了两种不同的性质。,表9.8 16项体型特征的均值与方差,2023/6/23,北京邮电大学信息工程学院,36,表9.9 相关系数矩阵,2023/6/23,北京邮电大学信息工程学院,37,(2)主成分的计算与讨论。用相关系数矩阵代替协方差矩阵进行主成分分析。计算步骤同例9.4。计算所得的16个特征值和累计方差贡献率在表9.10中，前三个特征向量 列在表9.11中，因子负荷量矩阵的前三列列在表9.12中。,表9.10 特征值和累计贡献率,表9.11 前三个特征向量,2023/6/23,北京邮电大学信息工程学院,38,由表可见，前三个主成分的累计方差贡献率已达到70%，所以只取前三个主成分进行讨论。,表9.12 因子负荷量与累计贡献率,2023/6/23,北京邮电大学信息工程学院,39,1)第一主成分。由表9.11可见，第一主成分 与原有各特征 间的关系为：在以上表达式中，每项系数都是正数，而数值都在0.09到0.34之间。考虑正交归一条件(9.7)，16项系数的平方和为1，所以各系数的平均值。这样，每项系数都与平均值相差不远。如果某人的原有16项特征值都比较大，则 也会比较大。反之，原有各特征取值都小时 也比较小。因此，可以认为 是全面的反映某人的魁梧或瘦小程度的特征，不妨称之为“大小因子”。2)第二主成分。在第二主成分 的表达式中，原有各特征的系数有正有负，绝对值相差仍不悬殊。系数为正的各项多数对应于反映“长”的旧特征，而系数为负者多数是但应映“围”的旧,2023/6/23,北京邮电大学信息工程学院,40,特征。不难想象，瘦高的人所对应的 值将比较大，而矮胖者对应的则较小。因此，称 为“形状因子”。3)第三主成分。在 的表达式中，多数系数接近于零，绝对值超过0.3的系数只有三个，分别对应(前胸)，(后背)和(肩宽)，因此，是反映有无鸡胸、驼背或宽肩等畸形形状的特征，可以称之为“姿势因子”。由于各主成分是不相关的。所以可以认为 是在 大致相同时区分胖瘦的成分，是在 大致相同时区分有无畸形的成分。(3)对原有各特征的分类。我们以 和 为坐标轴，在平面画出各个(i=1,2,16)的位置，称为各 的平面点图，见图9.4。,2023/6/23,北京邮电大学信息工程学院,41,在图9.4可以明显地看到，多数反映“长”的旧特征集中在一个类中，反映“围”的旧特征集中在另一类中，而反映畸形的3各特征不能归类。这样，我们对于原有各特征的关系有了一个比较清晰的直观认识。(4)对样品的分类。现在，我们用前两个主成分 为坐标轴，做出各个样品点的平面点图，见图9.5。,图9.4 原有特征的平面点图,2023/6/23,北京邮电大学信息工程学院,42,图9.5 样品点的平面点图,2023/6/23,北京邮电大学信息工程学院,43,由图可见，绝大多数样品点聚集在7 个区域内，每个区域的点数和位置接近于中心的代表点点号见表9.13。我们可以用7个代表点(每点对应一个人)的体型作为典型号，将服装分成7种型号。各类服装的数量按25：14：9：7：12：20：8的比例准备。,2023/6/23,北京邮电大学信息工程学院,44,二.对应分析,对应分析是另一种常用的线性降维映射的方法。这一方法的提出主要从主成分分析谈起。在上面已经讲过，主成分分析的目的在于从旧特征X出发构造新特征Y，使得 YUX或 i=1,2,n每个 称为一个主成分，它是综合原有各特征而形成的一种具有代表性的新特征。不难想到，用同样的方法可以从原有样品出发构造一批新样品F，使得 i=1,2,N,2023/6/23,北京邮电大学信息工程学院,45,其中 是旧样品，是新样品，是系数。在求 时，只要用样品间的某种相似系数(例如夹角余弦)矩阵代替特征间的协方差矩阵即可。新样品 可以理解为代表性的典型样品。它通常不是原有样品中的某一个，而是综合原有样品的性质而得到的“标准”样品。例如，英文字母“A”可以被不同的人写成各种不同的形式，但是不会有人反对用印刷体作为这个字母的典型代表。这种研究通常称为因子分析。也有些书籍把对于特征的线性映射称为R型因子分析，而把对样品的线性映射称为Q型因子分析。因子分析（Q型）与主成分分析的原理虽然相同，但在计算上却要困难的多。这是因为，通常情况下样品数目N要远远大于特征数目n。因此，样品相似系数矩阵将是一个庞大的矩,2023/6/23,北京邮电大学信息工程学院,46,矩阵，对它的计算无论在时间或空间上将是很困难的。对应分析便是针对这一问题而提出的一种方法。它可以利用特征间的协方差矩阵同时完成R型和Q型两种因子分析。下面，我们介绍对应分析的计算步骤。资料的标准化 在进行主成分分析时，对原始资料可以进行标准化，也可以不进行。但是，对应分析要求必须对资料进行特定的标准化。首先，假定原始资料矩阵的每个元素(如果某个 只要将第i行的每个元素都减去该元素的最小值便可满足上述条件)。然后做以下两次变换：1)令T等于原始资料矩阵全体元素之和，即,2023/6/23,北京邮电大学信息工程学院,47,然后进行“总和标准化”：总和标准化与常用的极差标准化或标准差标准化不同。它把原始资料矩阵的行与列同等对待，也就是把样品与特征同等对待。经过总和标准化后，全体 之和为1，因此每个 可以看成一种2维情形下的概率。由此将矩阵X变到P。2)令 和 分别表示矩阵P的第i行及第j列元素之和，即然后令得到新的资料矩阵Y，见表9.14。,2023/6/23,北京邮电大学信息工程学院,48,表9.14 对应分析的变化步骤,2023/6/23,北京邮电大学信息工程学院,49,由P到Y的变换可以这样解释：P中任意两点，可以写成,求 与 的欧氏距离平方得：如果考虑到第()列在所有各列中所占比例为()，而第i行在所有各行中所占比例是，因而改用以下的加权欧氏距离平方：就相当于先将 变换成 后，再求欧氏距离平方。R型因子分析 下面来求特征间的协方差矩阵S。根据协方差定义，应有 i,j=1,2,n,2023/6/23,北京邮电大学信息工程学院,50,分别是第i,j行的平均值。现在将这一公式略加修改，令即把通常意义下的算术平均改为加权平均，再令 i,j=1,2,n便得到加权的协方差公式。若令 i,j=1,2,n k=1,2,N其中 是X的第i行元素之和，而 是X的第k列元素之和，则有或 下面的步骤与主成分分析相同：求S的各特征值与特征向量，按照累计方差累计贡献率求出前几个新的特征。,2023/6/23,北京邮电大学信息工程学院,51,由以上的步骤可以看出，若在第1步时直接令而得到新资料阵Z，则可令 而进行R型因子分析。Q型因子分析 我们令样品之间的协方差矩阵为：B是N行N列矩阵，进行分析的计算量很大。但是，已经证明了以下结论：B和S的非零特征值相同。若u是S的特征向量，则 是B的特征向量。若v是B的特征向量，则Zv是S的特征向量。根据以上的结论，如果已经求出了S的前k个特征向量,2023/6/23,北京邮电大学信息工程学院,52,那么只需计算 便可得到B的特征向量，而无需直接计算了。,93考虑多类情形的线性降维法,本节介绍另一种线性映射降维方法。在叙述这种方法之前，我们先对上节所介绍的两种方法做一个简单的回顾。首先，上节所谈的两种方法都是线性映射的方法。从几何学的观点来看，线性映射相当于一次坐标旋转。例如，如果一批样品点散落在一个椭圆形的区域中，那么进行主成分分析的结果将使第一主成分 指向椭圆的长轴方向，第二主成分 指向短轴方向，如图所示。同理，如果样品点是散布在一个椭球,2023/6/23,北京邮电大学信息工程学院,53,或超椭球中，各个主成分便将依次与最长轴、次长轴直至最短轴重合。其次，上节所讲的两种方法都没有考虑样品的类别，而是把全体样品作为一类加以处理的。因此，这种降维方式固然可以较好的保留样品分布的信息，但对于分类则并不一定有利。不妨举一个极端的例子：如果全体样品点被分为图中所示的两类，那么显然可以看到，第一主成分 的分类效果反而不及。在本节中我们将讨论另一种线性映射降维方法，它在映射时将利用有关样品类别的信息，并且设法增强样品的“类别可分离性”。需要指出，这类方法种类很多，限于篇幅，我们只能介绍比较新颖而且有效的一种。,2023/6/23,北京邮电大学信息工程学院,54,一.几种常用线性映射及其性质,设有一批样品,每个样品用n个特征表示,即可写成。对于各原有特征的一个线性变换可以表示为：i=1,2,m;mn或 YAX(9.16)其中A是变换矩阵，可以是方阵，也可不是方阵，即mn。每个 是一新的特征。线性映射对原有样品分布情况的影响，集中,图9.6 主成分分析的几何解释,2023/6/23,北京邮电大学信息工程学院,55,地反映在对于样品均值和协方差的影响上。设原有样品的均值为 而协方差矩阵为，可以证明，经过如式(9.16)的映射后，在新特征空间中的样品均值和协方差矩阵分别变为：正交归一变换 我们在主成分分析中所用的变换称为正交归一变换。在上一节中已经指出，这时所用的变换矩阵AU是以 的各个特征向量为列所形成矩阵的转置，而 是对角矩阵。还可以证明，在正交归一变换之下欧氏距离保持不变。或者说，这种变换只改变了坐标轴的方向，而没有改变分布的形状，即坐标轴只被旋转(图9.6)。白化变换,(9.17),2023/6/23,北京邮电大学信息工程学院,56,如果令变换矩阵。则由式(9.17)可知：其中I是单位矩阵。这种变换称为白化变换。关于白化变换有两个重要的性质：经过白化变换以后，样品的分布形式将发生变化，或者是将被压缩或膨胀，见图9.7。经过白化变换后，由于协方差 已经是单位阵，所以再对Y进行任一种正交归一变换ZUY后所得的新协方差阵 仍是单位阵，即:是正交归一变换的性质。,一类归一变换,(9.18),(9.19),2023/6/23,北京邮电大学信息工程学院,57,图9.8 一类归一变换的几何解释,2023/6/23,北京邮电大学信息工程学院,58,现在我们开始考虑多类情形。为简单起见，先考虑只有两类 的情况。假定两类样品均值分别为 和，而协方差矩阵分别为 和。如果我们对第一类样品实行白化变换，即求 的特征向量转置矩阵，和以特征值为对角线元素的对角阵，并对两类样品同时做变换，则变换后的两类协方差矩阵将分别为：这时，第1类样品的分布将变为圆形（球形、超球），而第2类样品的分布也将随之变为比较规整的形状(图9.8)。在某些情形下,这种变换将会有利于样品分离。下面我们将介绍一个以一类归一变换为出发点的线性特征选择方案。,(9.20),2023/6/23,北京邮电大学信息工程学院,59,二.多类问题线性映射算法,本段介绍由德赛尔(Decell，H.P.)，奥德尔(Odell，P.L.)，科柏利(Coberly，W.A.)以及杨(Young，D.M.)等人提出的一种线性映射降维方法。假定已知N个n维样品，它们分别属于m个不同的类。严格地说，各类样品应当遵从多维正态分布。当这个条件不满足时，可以进行适当的数据变换以达到上述要求。但是，在实践中，即使正态分布的要求不满足，这一算法也可起到较好的效果。算法的步骤如下：(1)实行一类归一化。例如，以为 基础以对全体样品做一,2023/6/23,北京邮电大学信息工程学院,60,类归一变换。这时，经变换后的协方差矩阵变为，而其他各类的协方差阵分别变为。还要注意，本方法要求在归一化之前将类 的样品均值变为零，即先将原点平移到的 均值 处。经过平移后，其它各类的均值仍记作，而一类归一化则将各类均值变到 i2,3,m(2)构造新的原始资料M。经过一类归一化后，构造以下的矩阵：其中竖线是向量或矩阵分割记号。换句话说，M的第1到m1列分别是向量 到，第m到m1n列是矩阵 的各列，等等。n是特征个数。所以M是n行和(m-1)(n+1)列矩阵。以下的步骤和主成分分析相同，即,(9.21),2023/6/23,北京邮电大学信息工程学院,61,(3)求M的协方差矩阵S。(4)计算S的各个特征值并按从大到小的顺序排列，记作。相应的特征向量按同样的次序排列称为一个矩阵，的各列分别是特征向量。的转置记作。(5)选取前p个特征值，使其累计方差贡献率达到所需的比例。(6)取U的前p行形成线性映射矩阵，并作线性变换：i=1,2,p，这样便实现了降维的线性映射。在算法的第(3)步中，也可以用矩阵 代替M。根据我们的实验，两者的效果差别不大。,2023/6/23,北京邮电大学信息工程学院,62,上述的降维方法出去同样可以达到降维的目的外，还有利于区分各类样品。需要说明的是，这一方法是以贝叶斯分类原理作为基础的。例9.6 已知27个样品点，共分3组，每个样品原有3个特征。原始资料见表9.15。,样品,特征,特征,样品,表 9.15 27个样品的原始资料矩阵,2023/6/23,北京邮电大学信息工程学院,63,采用上面所介绍的线性降维映射方法，对类 进行一类归一变换，并将此变换同时用于 和。经过求 的特征值和向量后，发现前两个特征值的累加贡献率达到92.7%。取前两个特征向量进行变换后所得的2维平面点图见图9.9。由图可见，三类点可以较好地分开，而以第1类点最为集中。,样品,特征,2023/6/23,北京邮电大学信息工程学院,64,图9.9 27点经降维映射后的平面点图,2023/6/23,北京邮电大学信息工程学院,65,9.4非线性的降维映射方法,在二三节中所介绍的降维方法都是以线性映射作为基础的。我们自然会想到，如果采用非线性的映射方法，即允许新特征 不一定是原有特征的线性函数，降维的效果或许可以得到进一步的改善。遗憾的是，关于这一方面的研究至今还很不成熟。因此，我们在本节中只能介绍一些简单的情况。,一.降维方法中的几个问题,我们首先讨论降维映射中的一些主要问题，或者说是对于降维方法的一些要求或希望。拟合程度问题 当我们通过降维映射把n维特征空间的N个样品点,2023/6/23,北京邮电大学信息工程学院,66,变换为m维空间中的N个点 时，我们总是希望 的散布方式或者相互关系能与 尽量吻合一致。也就是说，降维映射应当尽量保持原有样品的结构信息。新旧样品点之间的这种结构一致性称为拟合程度。它可以通过以下一些标准进行衡量：应力 设 与 两点间的某种距离(例如，欧氏距离)记作,而经过映射后的对应点 与 间的距离记作。则可用以下函数度量映射前后样品点的拟合程度：若经过映射后所得的每一对点 与 间的距离记作 都和它们所对应的原样品点 与 间的距离 很接近，则 将会接近于零。因此，一个拟合程度较高的映射应使 取极小,(9.22),2023/6/23,北京邮电大学信息工程学院,67,值。是系数，通常可取 是一参数。上式表示，若 很大，则 将会很小。也就 是说，对于那些本来相距很远的点可以不予重视。还要指出，是 的函数，因而是各个新特征 的函数，而 则是常数。连续性指标 沿用上面的记号，可以改用以下目标函数：这里 同样是一个非负的数值。当 很大时，由于权 的作用，将接近于零。因此，要使整个 达到极小，映射就应具有这样的性质：当 较小时，也是很小。,(9.23),2023/6/23,北京邮电大学信息工程学院,68,单调性指标 我们首先定义一个排列函数R，对于最大的，；对次大的，等等。对于 也是一样。其次，定义函数f()，当=0时f()0；0时f()0(例如，等于一个常数或|)。然后取下述目标函数：意味着经过映射之后各点间距离大小的排列次序不变，即在n维特征空间中相距最远的点，映射到m维空间中仍然最远，等等。但是，这一要求往往是难以满足的。有些文献在使用这一指标时先把特征空间划分为几个部分，然后在每个部分上使用单调性指标。,(9.24),2023/6/23,北京邮电大学信息工程学院,69,类别可分离性问题 如同上节所说的那样，当已知样品点分为若干类时，降维映射算法应当尽量设法增加各类间可分离性，即把不同类的样品点“拉开”，而使同一类的各类靠近。类别可分离性同样有很多种度量方式，我们只介绍最简单的一种，即其中 和 的含义同上。和 分别表示 和 所在的类号。如果全体样品共分m类，则 和 都是1,2,m中的某个数。函数函数的定义为：因此，公式(9.25)表示，对原来属于同一类的点(1)，应该,(9.25),2023/6/23,北京邮电大学信息工程学院,70,尽量小。而对不同类的点(0)则不必计较 的大小。一个好的降维映射使 尽量小。新特征空间的维数问题 经过降维映射之后，新的特征空间维数即新特征的个数m应该等于多少？在主成分分析等线性映射方法中，这个问题是通过计算新特征的所谓累计方差贡献率来解决的。但是，在非线性映射中，没有方差贡献率的概念。一种最简单的方案，是纯粹人为地指定新的维数，例如令m2或3。有人企图通过分析样品结构寻找原始各样品的“固有维数”，但是这类算法往往比较复杂而且仅限于局部范围内使用。另一种比较新的思想是将线性映射与非线性映射交替使用，以便不断降维和改善映射效果。,2023/6/23,北京邮电大学信息工程学院,71,二.迭代方法,我们构造如下的目的函数，它同时考虑新旧样品的拟合程度和新样品的类别可分离性两个方面：其中 取(9.22)至(9.26)中的任一种表达式，的可取(9.25)式。当事先不了解样品的类别时，不考虑。是一个起调节作用的参数，它表明在 和 二者之间更强调哪一方面。J是新样品点 的函数。每个 是一个m维点，m由人为指定。先任意给定一组初始点。如果事先进行过对 的主成分来构成各个 的坐标。也可以任意指定 的坐标。然后，可以采取任意一种最优化方法来不断调整各个新样品点的坐标，直到J达到极小为止。当采用(9.22)和(9.25),(9.26),2023/6/23,北京邮电大学信息工程学院,72,分别作为 和 的表达式，迭代公式为(利用最速下降法):其中是一个正的步长参数。当两次迭代所得的 和 足够接近时(i1，2，N)，迭代停止。,三.非迭代方法,迭代方法的一个缺点是运算很慢。而如果企图通过改进最优化方法来提高计算速度，就要占用更多的机器存储。下面介绍的孔茨(Koontz，W.L.G.)算法是一种非迭代方法，因而可以提高计算速度。仍采用(9.22)和(9.25)作为 和，于是,2023/6/23,北京邮电大学信息工程学院,73,其中b与 各无关。所以可以只取不包括b的各项作为目标函数，记作，并将其简化为 越接近于零表示降维效果越好。由式(9.28)可见,若每个 都充分接近,则降维的效果将会很好。由此出发，我们可以假定 是 的某个次数为r的多项式，即其中多项式次数r由人指定，是待定系数。,(9.27),(9.28),(9.29),2023/6/23,北京邮电大学信息工程学院,74,将(9.29)式代入(9.28)的 中，并通过求 的最小值来确定各个，i=0,1,r。这是一个典型的最小二乘问题，各个 可以通过解以下的方程求出：其中,(9.30),(9.31),2023/6/23,北京邮电大学信息工程学院,75,拟合多项式次数r不宜过高，一般取2，3或4即可。因此方程(9.30)的求解并不困难。需要指出，由(9.30)只是解出了各个，即各个样品点在新特征空间中的距离。那么，如何确定各点的新特征即坐标数值呢？通常可以采用以下方法：当新特征的个数m由人为指定(例如令m2)后，任意选择m1个点作为基准点并随意指定它们的坐标。例如，令，于是其他N-(m+1)点的坐标都可根据基准点的位置来确定。于是，整个算法的步骤如下：根据原始资料求出各个，共N(N-1)/2个值。指出参数，和r。通常取1.0，如果希望强调类别 可分离性，可以取得小些，例如0.1，0.01。一般取,2023/6/23,北京邮电大学信息工程学院,76,1或2。r以不超过5为宜。由式(9.31)和(9.27)计算D，H和Q，并由式(9.30)求出诸，共N(N-1)/2个值。给定新特征个数m。任意确定m+1个样品点的新坐 标,以它们作为基准点。利用已求