1、第6章 图方法 第6章 图方法 6.1 图的基本概念图的基本概念6.2 相似性计算相似性计算6.3 图嵌入框架图嵌入框架6.4 图嵌入的线性扩展图嵌入的线性扩展6.5 图嵌入的核化扩展图嵌入的核化扩展6.6 图嵌入的张量扩展图嵌入的张量扩展6.7 图嵌入面临的挑战图嵌入面临的挑战第6章 图方法 6.1 图的基本概念图的基本概念1.图的定义图的定义 由若干给定的顶点及连接两顶点的边(线)所构成的图形即为图论中图的定义。图6-1 描述了一个简单的图,图中用点表示顶点,用点之间的连线表示边。同时,图是一种拓扑图 形。一般地,这种图形中的顶点代表事物,连接两点的边代表与两个顶点相应的两个事物 间的某种
2、关系,这样,可以用图来描述某些事物之间的某种特定关系。第6章 图方法 图6-1 简单的图第6章 图方法 总的来说,一个图包括顶点集合和边,具体如下:(1)顶点集合V。顶点代表图中相互关联的事物或个体,是图的基本元素。图6-1中 可以用vi、vj来分别表示第i、j个顶点。同时,令V(G)=v1,v2,vn 表示顶点的集 合V。第6章 图方法(2)边E。图中连接两个顶点的连线称为边。图6-1中eij=vi,vj 为连接第i、j 个 顶点的边,即为i、j两个顶点之间的联系。同时,令E(G)=e1,e2,em 表示边的集 合E。另外,边又分为有向边和无向边,当图6-1中边eij=vi,vj为有向边时,
3、则vi为起 点,vj为终点。一般情况下,图G 表示为G=,每条边对应着一对顶点,即EV V。一系列的顶点V 和连接这些顶点的边E 的集合为数学上对图G 的定义。第6章 图方法 2.邻接结点和邻接边邻接结点和邻接边 图6-1中由一条边连接的两个结点称为邻接结点,由同一个结点连接的两个边称为邻 接边。3.图的矩阵表示图的矩阵表示 可以用矩阵来表示图的顶点与边之间的关联性质,图的矩阵表示的优势主要有:(1)给出了图的一种表示方法;(2)可以借助对图的矩阵的研究结论,得出图的有关性质;(3)由于矩阵的计算更便于计算机处理,运算和操作图可以直接转为对图的矩阵的 处理。第6章 图方法 一般选择邻接矩阵表示
4、图。顶点与顶点之间的邻接关系即为邻接矩阵。图的邻接矩阵 的定义如下:顶点V=v1,v2,vn,边E=e1,e2,em,图G=,可以用一个n n 的矩阵A(G)表示图G=,其中,矩阵A(G)中第i行、第j列的元素为从矩阵的定义中可以看出邻接矩阵为对称阵。第6章 图方法 图6-2给出了有向图和无向图以及它们分别用邻接矩阵表示的例子。图6-2 图及其邻接矩阵的表示第6章 图方法 如果图G=中的边带有权值(weight),则可用一个nn 的矩阵W 来表示,矩阵中第i行、第j列的元素定义为同样地,权值矩阵W 为对称阵,即wij=wji。第6章 图方法 常用的 两 种 建 立 图 形 的 方 法 有k 邻
5、 域 图 和 邻 域 图。对 于 一 个 训 练 样 本 集 X=x1,x2,xn,设 N(xi)表示为xi 的近邻点表示的集合,则 X 上的无向邻域图G=定义如下:顶点集V=X,当且仅当xjN(xi)或xiN(xj),存在xi 和xj相连接 的边,按照上述定义得到的无向邻域图称为k 邻域图。若N(xi)=xj|dij,其中dij定 义为xi 和xj之间的距离,是一个参数,按照上述准则建立的无向邻域图称为邻域图。可 用图6-3直观表示k 邻域图和邻域图的具体建立方法。第6章 图方法 图6-3 两种图形建立方法第6章 图方法 1.高斯核高斯核式中,t为高斯核参数,它可以控制权值的大小,当t时,高
6、斯核就会简化为一个二值 图,也就是第6章 图方法 2.欧氏距离的倒数欧氏距离的倒数xi和xj之间的距离越大,两者之间的权值越小;当距离趋近于无穷大时,两者之间的 权值为0;当两者之间的距离趋于0时,得到的两者之间的权值大小趋近于无穷大。第6章 图方法 3.局部线性重构系数局部线性重构系数 Roweis和Saul于2000年提出 LLE 算法,该算法能够找到嵌入在高维数据空间中的 低维光滑流形,它主要利用局部线性来逼近全局非线性,通过相互重叠的局部邻域来提供 整体的信息,从而保持整体的几何性质。利用欧氏距离作为测度,寻找每个高维数据点xi 的k 最近邻数据点,其组成的集合用 N(xi)表示。第6
7、章 图方法 LLE算法是基于假设每个样本点都可由近邻的样本点线性表示,因此可用重构误差作为成本函数来衡量,可表示为式中,每个数据点只能通过它邻域内的数据点来构造,当某个数据点不属于此邻域内时,Wij=0。此外,还约束权值矩阵每一行的所有元素之和等于1。第6章 图方法 6.2 相似性计算相似性计算除了确定构建什么类型的图,还需要确定如何计算图中连接各个顶点之间的边的权 值,也就是构建权值矩阵。权值矩阵中的权值是样本之间相似性的具体反映,而在计算样 本之间的相似性时,通常使用第3章有关的欧氏、明氏、马氏等方法,还可以使用以下 方法:第6章 图方法(1)负指数法或 RBF核函数法:任意两个数据点xi
8、、xj之间的相似性定义为式中,为常量。(2)正切值法:任意两个数据点xi、xj之间的相似性定义为式中,1、2为常量。第6章 图方法 除了上述几种相似性计算方法外,还有不少研究者提出应该根据数据流形或密度等特 性来衡量数据点之间的相似性。如 Chapelle提出一种基于密度的距离,他指出两个数据点 之间的距离应该是连接它们的所有路径中的最短路径距离,这种方法得出的距离可以看成 是一种体现数据流形的距离,同时也隐含实现了流形假设。第6章 图方法 6.3 图嵌入框架图嵌入框架图谱理论主要研究图的邻接矩阵和拉普拉斯矩阵的特征值与特征向量,图是由若干给 定的点及连接两点的线所构成的图形,这种图形通常用来
9、描述某些事物之间的某种特定关 系,用点代表事物,用连接两点的线表示相应两个事物间具有的某种关系。第6章 图方法 图嵌入通过定义两个不同的图:用来描述数据集的某些需要凸显的统计或几何性质的 本征图(IntrinsicGraph)G(V,W )和用来描述需要保持或者抑制的部分统计或几何性质的 惩罚图(PenaltyGraph)Gp(V,Wp )来考虑样本间的关系。本征图和惩罚图具有相同的顶 点,但图的边权重矩阵不同。第6章 图方法 第6章 图方法 通过定义不同的本征图和惩罚图及其相应的边权重矩阵,目前常见的降维算法,如 PCA、LDA、ISOMAP、LLE、LE等均可统一到图嵌入框架下。式(6-1
10、0)给出了图嵌入算法的最基本形式,相应地,图嵌入算法也有多种扩展,如线 性化、核化及张量化。图6-4给出了图嵌入算法的统一框架及可能的扩展方向。第6章 图方法 图6-4 图嵌入算法的统一框架第6章 图方法 图嵌入算法的相似度保留特性可以从以下两个方面来解释:一方面如果两个点之间的 相似度很大,为了使图嵌入算法的目标函数最小化,两个点之间的距离就应该更小;另一 方面,如果两个点之间的相似度很小甚至是负值,只有当两个点之间的距离很大的时候才能使得图嵌入算法的目标函数更小。第6章 图方法 6.4 图嵌入的线性扩展图嵌入的线性扩展为了得到测试点的低维嵌入,图嵌入框架给出了线性化、核化及张量化的扩展。先
11、看 图嵌入的线性扩展:假定图嵌入中的映射是线性的,即第6章 图方法 则可以推导出线性图嵌入算法。把式(6-11)给出的线性映射代入到式(6-10),则可得到 线性图嵌入算法的目标函数或者第6章 图方法 其可转化为最小化问题由拉格朗日乘数法,上式可转化为广义特征值问题:第6章 图方法 6.4.1 主成分分析主成分分析 主成分分析(PCA)是最为经典、应用最为广泛的线性特征提取方法之一。其主要思想 是在全局最小重构误差的意义下把高维观测数据投影到低维主子空间上,高维观测数据在 子空间上的投影坐标就是对应的低维表示。第6章 图方法 设观测数 据 集 为 xi=f(yi)RD,共 有 n 个 样 本,
12、采 样 自 d 维 嵌 入 流 形,Y=yi是包含在欧氏空间Rd 的在嵌入流形上对应的低维坐标,y=XTa,a 为投影向量。则 PCA 算法就是寻找d 个正交单位投影向量a1,a2,an=A,作为低维空间的正交基,使得从低维空间重构高维数据的重构误差平方和最小,也就是最大化整体方差,PCA 算法的 目标函数为第6章 图方法 设数据集的均值为m,令St为数据集的总体散度矩阵,其定义为则数据集的协方差矩阵C 可表示为由拉格朗日乘数法,式(6-16)的解等价于第6章 图方法 第6章 图方法 第6章 图方法 第6章 图方法 由式(6-27)可见,当图的边权重矩阵定义如式(6-25)时,数据集的协方差矩
13、阵可以由图的拉普拉斯矩阵表示。PCA 寻求能够使得方差最大的投影方向,而图嵌入算法寻求数 据集相似性,因此 PCA 中的最大化问题可以转换为去除图嵌入算法的相似性的最小化问 题,投影向量可按照特征值由大到小的顺序排列最小化问题的特征向量求得。第6章 图方法 6.4.2 线性判别分析线性判别分析 在线性映射中,投影非常关键,相同的样本在向不同方向作投影时,产生的结构的可 分性会有显著的不同。图6-5给出了在二维空间上的示例。第6章 图方法 图6-5 样本在二维空间投影示例第6章 图方法 设观测数据集为xi=f(yi)RD,共有n 个样本,分属于c 个类别,采样自d 维嵌 入流形,Y=yi是包含在
14、欧氏空间R 在嵌入流形上对应的低维坐标,y=XTw,w 为投影 向量。既然不同的投影方向会产生不同的分类效果,如何确定这样最佳的投影方向w 就是我 们关注的焦点。一个可以用来衡量投影结果可分性程度的标准是不同类样本的差。第6章 图方法 设mi表示第i类的样本均值当样本投影到特征空间后,该类数据的样本均值也是原样本均值mi的投影第6章 图方法 从而得到投影到特征空间后数据集中两类样本的均值差可见当投影向量的幅值一定时,投影后的两类样本之间的均值差从一定程度上反映了数据 的可分性,其数值越大说明两类相距越远。但是这个均值差不但受到投影向量的幅值影响,而且与数据的分布有关。第6章 图方法 LDA 算
15、法定义了三个散度矩阵:类内散度矩阵、类间散度矩阵及总体散度矩阵。(1)类内散度矩阵(Within classScatterMatrix)定义:式中,mi为每类的均值。第6章 图方法(2)类间散度矩阵(Between-classScatterMatrix)定义:式中,m 为总体均值。LDA 算法的目标函数可以表示为第6章 图方法(3)总体散度矩阵等于类内散度和类间散度的和,即从而 LDA 算法的目标函数等价于由拉格朗日乘数法,上述优化问题可通过求解如下广义特征值问题获得第6章 图方法 第6章 图方法 6.4.3 边界费舍尔分析边界费舍尔分析MFA 中定义的本征图把每个样本点和与其同类别的近邻点连
16、接起来,表示类内的紧 致度;而惩罚图把每个样本点与其不同类别的近邻点连接起来,表示类间的可分性。MFA 算法的目的就是利用样本的局部关系,使得类间可分性增加的同时保持类内的紧致度。第6章 图方法 第6章 图方法 因此可得 MFA 算法的目标函数:MFA 是基于局部数据关系的监督鉴别方法,它有两个最近邻近点数量的参数k1和k2 要调整,相比 LDA 增加了算法的复杂性。第6章 图方法 6.5 图嵌入的核化扩展图嵌入的核化扩展根据模式识别理论,低维空间线性不可分的模式通过非线性映射到高维特征空间则可 能实现线性可分或者近似线性可分,如图6-6所示。设K 是 Gram 矩阵,则第6章 图方法 图6-
17、6-数据在原始空间中线性不可分,映射到核空间后线性可分第6章 图方法 当数据集在原始空间是线性不可分时,通过一个非线性映射到更高维的特征空间,在 更高维的特征空间中线性可分或者近似线性可分,设图嵌入的核函数扩展中的 Gram 矩阵 定义如式(6-50),在非线性映射后的高维空间中的投影向量为第6章 图方法 则此时图嵌入算法的目标函数为从而上式转换为广义特征值问题的求解:第6章 图方法 6.6-图嵌入的张量扩展图嵌入的张量扩展线性化与核扩展方式都是以提取的特征向量形式表征图上顶点之间的联系的,但 是在实际应用中,可能在目标中提取的特征包含高阶结构信息。第6章 图方法 第6章 图方法 如果B 通过
18、惩罚图来计算,例如B=Lp=Dp-Wp,则第6章 图方法 下面介绍2DLDA 算法设A 为一个mn 像素的随机图像矩阵,x 为一个待选定的n 维列向量,代表n 维的 空间向量。A 可以通过下式被投影到x 上:从而得到一个m 维的向量y,称其为图像A 的一个特征向量。第6章 图方法 第6章 图方法 第6章 图方法 从而,2DLDA 的目标函数可以表示为上述问题可转化为广义特征值问题第6章 图方法 现在再来看图嵌入框架的张量化扩展,张量化扩展把数据从向量形式扩展为任意阶张 量,图的定义不变,对数据的运算引入了张量分析,既然 LDA 可以用线性图嵌入框架解 释,那么 2DLDA 也同样可以用图嵌入的
19、张量化扩展来解释,2D 只是张量的一个特定 阶数。第6章 图方法 6.7 图嵌入面临的挑战图嵌入面临的挑战1.局部与类别的矛盾局部与类别的矛盾 通常,局部型降维方法假设样本位于或近似位于嵌入在高维空间的低维流形,并满足 光滑性假设。然而,这往往局限于理想情形或人工数据(如 SwissRole),实际情况远非 如此。第6章 图方法 2.挥之不去的维数灾难挥之不去的维数灾难 多数局部型降维方法基于k 近邻准则建图,这将导致后续工作(降维、分类或聚类等)严重依赖于最近邻准则在原始空间的性能。通常,我们期望一个好的“近邻图”能潜在地使 同类样本相连,异类样本不连。然而,不幸的是,最近邻准则往往需要大量
20、训练样本,并且 在很多情形下不适合在原始高维空间工作。如此一来,虽然降维的目的之一是为了克服维 数灾难,但局部型算法自身却受维数灾难的困扰,这似乎有点自相矛盾。第6章 图方法 3.参数选择的代价与困难参数选择的代价与困难 尽管局部保持降维技术通常较全局保持降维技术具有更好的性能,但需要付出参数 选择的额外代价。例如,样本xi和xj之间的连接权。最近的研究表明,在半监督学习中近邻 图参数的微小变化将导致最终结果大相径庭。局部保持降维算法的经验研究也发现类似 的问题。虽然交叉验证(cross validation)是常用的参数选择技术,但往往只适合监督问 题,并且耗费大量训练样本,导致高的计算开销
21、。事实上,在无监督情况下或者训练样本(特别是带标号训练样本)较少时,目前尚无可靠的方法进行参数选择。第6章 图方法 4.建图与降维过程的人为剥离建图与降维过程的人为剥离 现有的大多数基于图的降维方法需要预先建图。首先根据原始数据构造近邻图,然后 学习最优的投影方向(或相应的子空间)并旨在保持由此近邻图刻画的数据分布关系。也就 是说,一旦给定近邻图,在后续的操作中将始终保持不变。这样一来,不仅无法保证所建近 邻图一定有助于后续的学习任务,反而导致诸如参数敏感等一系列问题。第6章 图方法 5.其他问题其他问题 事实上,除了上述四点,局部型降维算法仍然面临诸多其他问题。例如,所有样本共享 相同的近邻数,而无视数据的具体分布,等等。尽管近年来已有工作12对上述部分问题进 行了有益的探讨,并对现有的“局部性保持”降维方法进行了改进,但很少从根本上给出系 统的解决方案,这说明仅在原有“局部性保持”降维框架下解决这些问题存在一定的困难,也进一步表明探索新的构图方式、降维技术及框架的重要性和迫切性。
