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