1、第5章 非线性特征提取第5章 非线性特征提取5.1 核方法核方法5.2 流形学习方法流形学习方法第5章 非线性特征提取5.1 核核 方方 法法5.1.1 核方法原理核方法原理 核函数是一种非线性投影方法,通过引入核函数,原空间中非线性的算法可以在一个 高维的空间中用一般的线性算法来实现。高维特征空间中所有的运算都是通过原空间中的 内积核函数来实现的。第5章 非线性特征提取即任何(线性)只用到向量内积的算法都可以通过一个核函数在特征 空间中隐含地进行运算。利用此思想在高维特征空间中用一般的线性算法实现相对于原空 间来说是非线性的算法,将会大大地提高学习算法的效率,还可以改进现有算法,提高各 类识
2、别任务的识别率。第5章 非线性特征提取对于核函数与非线性映射 之间的关系,根据 Mercer理论可知:一个正定积分算子的 任何核都可以按它的特征函数i(i0,NH )进行展开,即这时第5章 非线性特征提取对于线性不可分的两类数据,通过一个非线性映射 将原空间的数据映射到 某 个(由内积核函数决定的)高维特征空间中,在高维空间中,数据变得线性可分,如图5-1 所示。第5章 非线性特征提取图5-1 将原空间的数据映射到某个高维特征空间第5章 非线性特征提取构造如上映射的方法:第5章 非线性特征提取目前常用的满足 Mercer条件的核函数只有几种,一般分为两大类:点积型核函数和转 移不变型核函数。(
3、1)多项式内积核函数:式中,核参数q 为多项式的阶次,取自然数,属于点积型核函数。第5章 非线性特征提取(2)径向基内积核函数:式中,核参数 控制核函数的宽度,属于转移不变型核函数。第5章 非线性特征提取(3)Sigmoid内积核函数:式中,核参数k、分别控制核函数的斜率和偏移量,属于点积型核函数。第5章 非线性特征提取还有一些其他的核函数,如全子集核、高斯核、ANOVA 核、集合核、随机核、最大最小值核等。而根据核函数的运算规则又可以演变出各种形式的组合。要根据每个核函数的 特点和应用范围及实际情况选择合适的核函数,这样既能简化运算,又可以有效地解决 问题。第5章 非线性特征提取5.1.2
4、核主成分分析核主成分分析 核主成分分析(KPCA)通过非线性映射,将原始数据从数据空间变换到特征空间,然 后在特征空间中利用统计主元分析求出最佳投影方向,从而获得非线性特征。KPCA 的基本思想如图5-2所示。第5章 非线性特征提取图5-2 KPCA 的基本思想第5章 非线性特征提取在高维特征空间F 进行线性PCA 变换(见图5-2(b),就好像PCA 在输入空间(见图 5-2(a):因为特征空间F 相对于输入空间是非线性的,因此在输入空间投影到主本征向 量上就称为非线性。对于 KPCA,重要的是实际上并没有向F 空间进行映射,而是在输入 空间进行了核函数 K 的计算。第5章 非线性特征提取假
5、定 X=(x1,x2,xm)是输入空间的数据集,其中xi(i=1,2,m)是d 维向 量,m 是数据集中的总样本数。存在一个函数 把数据映射到高维(甚至无限维)的再生核 希尔伯特空间(RKHS)。第5章 非线性特征提取使用这个映射函数,我们可以得到特征空间的数据集(X)=(x1),(x2),(xm),这样在映射的特征空间协方差定义为它符合特征方程:第5章 非线性特征提取式中,v 和 分别对应协方差矩阵的特征向量和特征值。因为一般情况下映射函数并不知 道,而且映射的空间是高维甚至是无限维,因此在特征空间中计算协方差是最难以处理的,正如前面所介绍的那样,利用核技巧,采用核函数可以不用显式地知道映射
6、函数,也不用 考虑具体特征空间的维数,而实现数据的高维特征空间的嵌入。在特征空间中一个核函数 被用于计算这 些 映 射 数 据 样 本 之 间 的 内 积,这 个 核 函 数 定 义 为k(.,.)=k(xi,xj)=(xi)T(xj)。第5章 非线性特征提取第5章 非线性特征提取第5章 非线性特征提取则归一化的特征向量为这样得到特征向量 后,可以使用式(5-15)计算核主成分v。对于任何一个测试样本x,其非线性特征为第5章 非线性特征提取特征提取过程可以用图5-3表示。图5-3 非线性特征提取结构第5章 非线性特征提取第5章 非线性特征提取第5章 非线性特征提取概括起来,计算核主成分的步骤如
7、下:(1)计算核矩阵K=(X)T(X);(2)对核矩阵特征K 分解,得到相应的特征值 和特征向量;(3)归一化特征向量v;(4)对测试样本,计算其在特征向量v上的投影。第5章 非线性特征提取5.1.3 核线性判别分析核线性判别分析 核线性判别分析(KFDA)是将核学习方法的思想与 FDA 算法相结合的产物。KFDA 算法的思路是:首先通过一个非线性映射,将输入数据映射到一个高维的特征空间中,然 后,在这个高维特征空间中再进行线性 Fisher判别分析,从而实现相对于原空间为非线性 判别分析。第5章 非线性特征提取在进行 KFDA 时,首先通过一个非线性映射 将输入数据映射到一个高维的 特征空间
8、中,即这时输入的训练 样 本 由 原 来 的 x 变 为(x),然 后 在 这 个 特 征 空 间 F 中 进 行 线 性 FDA。KFDA 就是在F 空间中求解以下问题第5章 非线性特征提取假定在F 空间中,所有的样本都是去均值的则类间散度矩 阵为第5章 非线性特征提取第5章 非线性特征提取第5章 非线性特征提取第5章 非线性特征提取以上就是 KDA 算法的推导过程,它是在线性鉴别分析的基础上通过分别对类内散度 矩阵和类间散度矩阵进行推导的。由于 Fisher准则在计算过程中存在矩阵奇异的情况,因 此 KDA 同样具有小样本问题,本章我们就不再赘述对于小样本问题的解决方法,具体方 法留待后续
9、算法进行解决。第5章 非线性特征提取5.1.4 核局部线性判别分析核局部线性判别分析第5章 非线性特征提取第5章 非线性特征提取5.2 流形学习方法流形学习方法5.2.1 流形学习方法的概念流形学习方法的概念 1.流形学习方法的基本思想流形学习方法的基本思想 流形(Manifold)在局部具有欧氏空间性质,是欧氏空间中曲线、曲面等概念的推广,欧 氏空间就是最简单的流形的实例。第5章 非线性特征提取我们存在的三维空间就是典型的欧式空间,像地球表 面这样的球面就是一个典型流形:历史上人类曾经认为地球是平面的,因为人相对于地球 来讲只是球面上的一个点,一个点在球面上只能做二维运动,所以人平常看到的只
10、是一个 局部的二维空间,即在局部具有二维欧式空间性质;当人乘坐航空器离开地表,就看到地 球是个三维空间的球形,就像足球一样。一个理想的球面在局部足够小的区域上可近似为 一个平面,即在局部具有欧式空间性质,这就表明它是一个流形。但是从整体全局看,球面 和平面具有本质区别,球面上一个点沿着直线运动会回到起点,但在平面上这个点可以无 限向前移动而不会回到起点。第5章 非线性特征提取流形在微分几何中用于描述形体,它的可微性为研究几何形体提供了平台和工具。从 拓扑结构看,流形是柔软的,因为所有变形(同胚)会保持拓扑结构不变;而从解析几何看,流形是硬的,因为流形局部的数据结构是固定的。所以这种局部是硬的,
11、而整体可以流动 的几何形体就称之为流形。第5章 非线性特征提取拓扑流形是一种最简单的流形,它由局部普通的欧氏空间Rn 组成,形式化地讲,一个 拓扑流形是一个局部同胚于一个欧氏空间的拓扑空间。这表示每个点有一个邻域,它有一 个同胚(连续双射,其逆也连续)将它映射到Rn,这些同胚是流形的坐标图。拓扑流形就是一个集合,上面赋予了拓扑结构,拓扑空间之间可以定义连续映射。第5章 非线性特征提取拓扑空间 M 在满足以下条件时,称 M 为m 维流形。(1)M 为豪斯多夫空间。豪斯多夫空间是数学拓扑学中的一个分离空间,满足分离定 理:对于拓扑空间 M 中任意2个不同的点x 和y,存在x 的邻域U 和y 的邻域
12、V,满足 UV=。(2)对于任意一点pM,存在包含p 的m 维坐标邻域(U,),坐标邻域是拓扑空间 中的开集与其在欧几里德空间中的映射 的有序对。第5章 非线性特征提取2.形学习概念形学习概念 对于给定的数据集 X=xi,i=1,nRD,并假设 X 中的数据样本是由低维空 间中的数据集Y=yi,i=1,n Rd 经过系列的非线性数学变换f 而生成为xi=f(yi)+i,这里的,dD,f:Rd RD 是C 嵌入映射。流形学习就是在给定观察样本集 xi的条件下重构f 和yi。第5章 非线性特征提取5.2.2 流形学习方法的分类流形学习方法的分类 根据流形学习方法的实质,可将其分为两类,第一类是构建
13、关系矩阵方法,主要包括 等距映射、局部线性嵌入等;第二类是基于局部模型的全局坐标对齐,主要有局部切空间 排列、黎曼流形等。流形学习如果按照算法对样本涵盖范围来分,可以分为两类,如图5-4所示。第5章 非线性特征提取图5-4 流形学习方法的分类第5章 非线性特征提取(1)全局方法是从全局角度出发,在降维时流形上临近的点映射到低维空间时保持临 近,但这种方法条件较为苛刻,算法复杂度很高;(2)局部方法则只要求在一个局部范围内映射到低维空间的临近关系保持不变即可。如果按照样本的特征变换方式来分,还可分为线性和非线性两大类。第5章 非线性特征提取5.2.3 等距映射算法等距映射算法 等距映射(ISOM
14、AP)算法实际上是 MDS算法的推广。在 MDS思想中,约简后低维空 间中任意两点间的距离应该与它们在原高维空间中的距离是相同的,所以对距离度量是算 法的关键,很显然当数据为线性结构时欧氏距离度量是有效的,但当样本数据是在流形曲 面上采样时,欧氏距离就不再反映数据集的内在结构。基于以上的问题,在ISOMAP算法 可以得到有效解决。第5章 非线性特征提取ISOMAP的计算步骤如下:(1)确定邻域,构造邻近图G。计算每个点的近邻点,可以使用 邻域法或k 邻域法,这两种邻域选取方式均是以样本点间的欧式距离为基础,对这两种邻域法进行定义。第5章 非线性特征提取(2)估 计 点 对 间 测 地 距 离d
15、M(xi,xj)。用 邻 近 图 G 上xi 和xj 之 间 的 最 短 路 径 dM(xi,xj)近似流行 M 上的测地距离,得到距离矩阵DM。最短路径dM(xi,xj)的计算方法 如下:当G 中存在边(i,j)时,存在最短路径dM(xi,xj)=dE(xi,xj ),否则dM(xi,xj)=;对于p=1,2,n,dM(xi,xj)=mindM(xi,xj),dM(xi,xj)+dM(xi,xj)最短 路径矩阵可表示为第5章 非线性特征提取(3)应用 MDS算法计算低维嵌入。计算对称矩阵:式中,I 为n 阶单位矩阵;l是矩阵内全部元素为1的n 维列向量。第5章 非线性特征提取第5章 非线性特
16、征提取通过式(5-43)式(5-45)可以总结出ISOMAP的特点:(1)计算点对间的最短路径比较耗时,当样本数和邻域取值较大,全局计算量将会非 常巨大。(2)因为数据所在的低维流形与欧式空间的一个子集整体等距,该欧式空间的子集是 一个凸集,如果当这个低维子集非凸时,流形上样本点间的最短路径计算会产生较大的偏 差,从而导致嵌入结果产生较为明显的变形,所以,该算法只适用于学习内部平坦的低维 流形,不适于学习有较大内在曲率的流形。第5章 非线性特征提取(3)当样本点采样稀疏,或数据集变形或扭曲,测地线距离的计算就会出现较大的误 差,使得嵌入结果产生变形。(4)当进行等距计算时,会要求在高维数据空间
17、向低维参数空间存在等距映射时,邻图上样本点间最短路径逼近的测地线距离,是无法描述数据集的内在低维几何结构,而 导致错误嵌入结果。第5章 非线性特征提取5.2.4 局部线性嵌入算法局部线性嵌入算法 局部线性嵌入算法(LLE)是 Roweis在 2000 年的Science上提出的,并引起了轰动,因为 LLE算法与ISOMAP 算法相比,其局部线性更优,更具有研究价值。LLE 算法是假 设采样数据所在的低维流形在局部是线性的,而且每个采样点均可以利用其近邻样本进行 线性重构表示。第5章 非线性特征提取LLE算法的基本思想:对于一组具有嵌套流形的数据集,在嵌套空间与内在低维空间 局部邻域间的点的关系
18、应该不变。即在嵌套空间每个采样点可以用它的近邻点线性表示,在低维空间中保持每个邻域中的权值不变,重构原数据点,使重构误差最小。第5章 非线性特征提取LLE算法包括三个步骤,如图5-5所示:(1)选择邻近样本;(2)利用线性权值重构矩阵W;(3)利用矩阵W 计算映射到低维空间。第5章 非线性特征提取图5-5-LLE算法步骤示意图第5章 非线性特征提取LLE算法具体如下:(1)设d 维空间中有n 个数据属于同一流形,记作:Xi=(xi1,xi2,xi1),i=1,2,n。假设有足够的数据点,并且认为空间中的每一个数据点可以用它的k 个近邻线 性表示。求近邻点,一般采用k 邻域法或邻域法。(2)计算
19、权值短阵W,代价函数为第5章 非线性特征提取并且权值要满足两个约束条件:每一个数据点Xi都只能由它的邻近点来表示,若Xj不是邻近点,则wij=0;权值矩 阵 的 每 一 行 的 和 为 1,即:这 样,求 最 优 权 值 就 是 对 于 式(5-46)在两个约束条件下求解最小二乘问题。权值体现了数据间内在的几何关系:利用 Lagrangemultiplier对式(5-47)求解得重构权值的矩阵W。第5章 非线性特征提取(3)保持权值不变,在低维空间d dD()中对原数据点重构。设低维空间的数据点为 Yi,可以通过求最小的代价函数式(5-46)求得:式(5-48)中的最优解需要满足下面的约束条件
20、:第5章 非线性特征提取第5章 非线性特征提取LLE算法的优点:(1)算法适用于各种的低维流形学习;(2)算法只需确定邻域参数和维度参数即可,相比ISOMAP待定参数较少;(3)算法中每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的;(4)算法通过最小二乘可以求得整体最优解,而且不需重复步骤,计算简单。第5章 非线性特征提取LLE算法的缺点:(1)对所学习的流形假设是不闭合的,而且是局部线性的;(2)要求在流形上进行稠密的采样;(3)对样本中的噪音很敏感;(4)对于新样本的映射过程则需要重新计算。第5章 非线性特征提取5.2.5-拉普拉斯特征映射算法拉普拉斯特征映射算法 拉普拉斯特征映射算
21、法8(LE)来源于图谱理论,假设有 N 个数据样本,则由 N 个数 据样本及相邻样本间的边构成一个拉普拉斯图,嵌入映射可通过求解拉普拉斯映射的特征 向量得到,算法过程如下:1.构造邻域图构造邻域图 构造邻域图,主要是构造边系数,即如果两个数据样本点间是“接近的”,就在这两个 数据样本间设置一条边,否则两个数据样本间就不存在边,判断两个数据样本间是否“接 近”,可以用两种方法:第5章 非线性特征提取第5章 非线性特征提取(2)k 邻域法,如果节点i是节点j的k 个最近邻之一,或者节点j 是节点i的k 个最 近邻之一,则认为节点i与节点j 之间存在一条边。注意上述条件满足之一则两个节点间 就存在一
22、条边,所以关系式是对称的。此种方法优势在于容易选择,而且不容易出现不连 通的图;缺点是缺少直观几何意义。第5章 非线性特征提取2.计算拉普拉斯图的边系数计算拉普拉斯图的边系数 计算拉普拉斯图的边系数,可以使用以下两种方法:(1)使用热核方程计算边的系数,即如果节点i与节点j之间存在一条边,则该边的系 数为否则Wij=0。式中t为热核参数。(2)简化的方式计算边系数,即如果节点i与节点j之间存在一条边,则Wij=1,否则 Wij=0。第5章 非线性特征提取3.重构样本数据重构样本数据 在d 维空间用各个样本的近邻重构该样本数据,其思想可描述为:使任意Xi的近邻在 降维后仍然尽可能靠近Xi,即所有
23、点与其近邻的距离和最小,因此有如下代价函数第5章 非线性特征提取拉普拉斯特征映射算法其实与 LLE算法类似。都是保持投影后点关系特征,也是分 三个步骤。该算法主要思想是设在高维空间中样本点之间的相关性投影到低维空间中点的 相关性保持不变,并通过使用两点间的加权距离作为目标函数,可求得相应的约简结果。相应的损失函数为第5章 非线性特征提取矩阵D 是流形顶点的一种自然测度,Dij越大,说明这个顶点越重要,LE 算法的三个 步骤中,对于流行描述是通过邻域图去近似的。描述如下:(1)构造邻域图从样本点构建一个近邻图,图的顶点为样本点,离得最近两点用 边相连,这里可以继续采用邻域法或k 邻域法计算。第5
24、章 非线性特征提取(2)构造权值矩阵给每条边赋予权值,如果点i和点j为非邻域点时,Wij=0;如 果点i和点j为邻域点相连时,则有以下两种方法:两点间的权值为式中,t为热核参数。采用简单权值法,两点间的权值Wij直接设为1。第5章 非线性特征提取(3)计算d 维嵌入计算图拉普拉斯算子的广义特征向量,求得低维嵌入。设式(5-54)中D 为对角矩阵,Dii=jWji,L=D-W,L 是近邻图上的拉普拉斯算子,求解 广义特征值问题Lf=Df,这里最小特征值为对应的特征向量。第5章 非线性特征提取与 LLE算法相比 LE算法具有如下优点:(1)LE算法的思想较简单,是局部非线性方法,主要目的是保留流形
25、的局部近邻信 息,使原空间中离得很近的点在低维空间也离得很近,可以用于聚类。(2)计算复杂度较低。LE算法只考虑局部邻域直接的关系,其求解过程为稀疏矩阵的 特征值,求出整体最优解,效率非常高,能有效反映数据集所在低维流形上局部的内在几 何信息。第5章 非线性特征提取LE算法的缺点:(1)对算法参数和数据采样密度较敏感。(2)不能有效保持流形的全局几何结构。第5章 非线性特征提取5.2.6 海赛局部线性嵌入算法海赛局部线性嵌入算法 海赛局部线性嵌入算法(HLLE)也称为 Hessian特征映射,是由 Donoho和 Grimes提 出来的。HLLE与 LE的理论架构很类似,所不同的是,HLLE
26、是用二阶海赛算子替代拉普拉 斯算子映射第5章 非线性特征提取HLLE的优点是:无需要求流形所对应的低维空间为凸;计算复杂度比 LE更为简单。缺点是:HLLE恢复低维流形坐标时需要知道流形的维度 D;对噪音分布不均匀会有较大 误差;对于计算高维数据局部邻域内的二阶导相对比较困难。第5章 非线性特征提取5.2.7 局部切空间排列算法局部切空间排列算法 局部切空间排列算法(LTSA)是由张振跃等人于 2004年提出的。其基本思想是:每 个局部邻域由局部切空间近似表示,每个样本点通过局部切坐标来表示,LTSA 认为全局 低维坐标可以通过局部切坐标的仿射变换得到。对于大多数的非线性流形来说,LTSA 可
27、 以通过局部线性信息,来整合发现它的全局非线性结构。第5章 非线性特征提取同样 LTSA 也分为三个步骤:(1)用k 邻域法或者邻域法求出样本点的邻域;(2)求邻域的局部坐标;(3)求出局部坐标的全局排列。LTSA 的优点:计算比较简单;无需要求流形所对应的低维空间为凸;能很好地恢复 出流形等距的低维空间的子集。缺点:算法中特征值分解的矩阵阶数等于样本数,如果样 本大,则难以计算高阶矩阵;与之前 LLE 一样,对于新样本还是无法有效处理;另外对流 形样本点的曲率和密度都比较敏感。第5章 非线性特征提取5.2.8 流形学习方法在应用中遇到的主要问题流形学习方法在应用中遇到的主要问题1.本征维数估
28、计本征维数估计 本征维数估计是流形学习方法中的一个重点和难点,同时也是特征提取中的一个棘手 问题。通常认为本征维数就是高维数据中内蕴低维流形的维数,但数据中的噪声会导致内 蕴流形维数不准确,而且内蕴的流形维数在降维前是未知参数,所以实际应用中本征维数 常常是靠先验知识人为估计。第5章 非线性特征提取当流形学习被作为非线性降维算法使用时,本征维数的确定直接决定着后续分类结果 的精度,本征维数过大则降维结果中掺杂大量噪声冗余,本征维数过小则不能保证降维后 结果含有足够的特征向量长度,所以选取适当的本征维数是流形学习中的一个首要难题。第5章 非线性特征提取2.噪声干扰噪声干扰 流形学习方法对噪声较为
29、敏感,当高维样本数据近似为一个光滑流形时,方法可以成 功找出内部的流形结构并进行低维重构,但实际应用中通过各种手段获取的高维数据中难 免存在噪声干扰,这就会导致高维到低维映射时出现流形结构的扭曲和变形,从而影响降 维结果的正确性。第5章 非线性特征提取3.近邻点的选择近邻点的选择 上述介绍的经典流形学习方法,都是基于局部线性假设,即假设数据点和其近邻数据 点处于一个局部线性平面上,首先在局部欧式空间进行线性操作把流形放入局部外围空 间,然后通过一定规则和关系将局部坐标系集成在一个整体的坐标框架内,最后基于全局 坐标系将高维数据映射至低维空间。但这种首先基于局部邻域点构建局部关系图从而建立 局部
30、坐标系的方法很依赖于邻域大小K 的选取,其次邻域距离测度的选取,ISOMAP选用 测地线作为邻域距离测度而 LLE 选取欧式距离作为邻域距离测度,但二者的邻域大小 K 的选取是一个需要优化和斟酌的参数,邻域值 K 选取过大则容易出现短路边,如果过小又 容易导致重构错误。第5章 非线性特征提取4.样本外点学习问题样本外点学习问题 样本外点学习问题属于泛化学习能力问题,对数据进行维数约简或特征提取时,所有 的操作都要求在已训练样本上完成。在ISOMAP和 LLE 中即要求对所有样本点的邻域图 构建完毕后才能进行重构,如果加入了新的样本点,则需要对整个邻域图进行重新计算。例如ISOMAP中需要对以测地线为测度的全局邻域图进行重新构建,然后再重新进行 MDS;在 LLE中则需要对新加入点的 K 邻域权值矩阵进行重新计算,这就导致每加入一 个新样本点就需要对整体结构进行重新估算,这是一个牵一发而动全身的难题,无疑会大 幅度提高计算量。
