拉普拉斯特征映射

4星(超过85%的资源)
所需积分/C币:50 2018-12-04 15:43:16 1.13MB PDF
160
收藏 收藏
举报

拉普拉斯特征映射、流形学习、拉普拉斯MTALB实验及代码
拉普拉斯特征映射 1.算法 给定k个点x1,x2…xk在R中,我们构造了一个有k个节点的加权图,每个节点对应一个点, 以及相邻点之间的边集. 1.Step1.构造图如果x1,x;是按近的,我们在节点i,j之间添加一条边,有两种变化 (a)c-邻点参数E∈R如果‖x;-;‖2<E那么节点,是连接的。 优点:几何驱动,关系自然对称 缺点:往往会导致图形具有多个连接的组成部分,很难选择c (b)n个最近邻[参数n∈N如果i是j的n个最近的邻点或者j是i的n个最近的邻点,那么 与j是连通的 伉点:选择简单,容易产生连通图 缺点:几何上不太直观。 2.Step2.[选择权重]这里也有两种选择权重的方法 (a)热核参数t∈R]如果节点,是连接的,使 (1) 对于权重选择的选择的原因将会在后面解释。 (b)最简单思维没有参数]如果,之间是有边连接的,那么W-1 这种简化避免了选择参数t 3.Step3特征映射]假设上面构造的图G是连通的,否则对每个连通的分量进行步骤3。计算广义 特征向量问题的特征偵和特征向量 Ly= ADy 其中D为对角权矩阵,其元素为该列元素W的和(或行,因为W是对称的),Da=∑;Wn L=D-W是拉普拉斯矩阵。拉普拉斯算了是个对称的正半定矩阵,它可以看作是G顶点上 函数的算子。让,……,k-1为方程2的解,根据特征值排序,为最小特征值(实际上是O). 图像x;在低维空间Rm的嵌入由(n(),,ymn()给出 2.解释 回想一下,给定一个数据集,我们构造了一个加权图G=(V,E),它的边连接着相邻的点。考虑将 加权连通图G映射到一条直线的问题,以便连通点尽可能地保持在一起。我们希望在适当的约束下选 择y2∈R来最小化 ∑(m-9) 让y=(y1,y2,,yn)成为从图到实线的映射.首先,注意对于任何一个y我们都有 ∑(.-v1)2=2L 拉普拉斯特征映射 与之前样,L=D-W.看到这个,注意W是对称的并且Da=∑;W。因此∑;(v;-v)2W 也可以写成如下: 2yi9j ∑sD+∑D1;-2∑ t.7 因此,最小化问题减小到寻找 argmin23TDy=12y2Ly.约束y2Dy=1移除嵌入屮的任意缩放因子。矩 阵D提供了对图形顶点的自然度量。由式4可知,Ⅰ是一个半正定矩阵,使日标函数最小的向量y由 广义特征值问题Ly=ADy的最小特征值解给出 设1是在每个顶点取1的常数函数。很容易看出1是特征向量的特征值为0。如果图是连通的,1 是当入=0时唯一的特征向量。为了消去这个不重要的点将会引起G上的顶点为1时的坍塌,我们增 加了正交性的约束条件得到: yopt=argminy"Dy=1.yD1o Ly 因此,解yont由所给出的最小非零特征值所对应的特征向量,更一般地,图嵌入Rm(m>1)由 n×m矩阵Y={孙1,y,m给出。其中第i行,由Yr表示,提供了第i个顶点的嵌入坐标。因此 我们需要最小化 ∑‖Y-Y|2W;=t 简化为 Yopt argminyT Dy-1tr(y' Ly) 对于一维的嵌入问题,约束条件避免了倒塌到一个点上。对于Ⅲ维的嵌入问题,约束避免了子空间的 维数坍塌少于m。 (1)拉普拉斯贝尔特拉米算子 拉普拉斯图与流形上的帕普拉斯贝尔特拉米算子是类似的。 考虑到嵌入到R上的m维流形M。流形上的黎曼结构(度量张量)是由R上的标准黎曼结构 导出的。假设我们有一个映射∫:M→R。梯度Vf(x)(在局部坐标下可以写成Vf(x)=>=1a1) 是流形上的向量场,类似于6x(在局部坐标图中) Jf(x+6x)-f(c)≈|Vf(x),6)≤‖Vf(x)‖6c‖ 因此我们知道如果‖ⅴ∫(α)‖很小的时候,ⅹ点附近的邻点将会映射到f(x)附近。因此,我们通过寻 找一种平均上最能保持局部性的映射 Vf(a) 最小化V(x)2与最小化在图上D∫=2∑(一f)2W是一致的。最小化梯度的平方变为找 拉布拉斯贝尔特拉米算子的特征方程C,C=diυVf(x),diⅳy是散度。根据 Stokes定理,div和V是 形式上的伴随算子,即如果f是一个函数,Ⅹ是一个向量场,那么Jx(X,Vf)=Jdv(X)f.因此 A v C(力)∫ (11 我们知道,C是个正半定的并且最小化了∫Vf2的f必须是C的特征函数 拉普拉斯特征映射 (2)热核和权重矩阵的选择 流形M上可微函数上的拉普拉斯-贝尔特拉米算子m与热场的时间相关。设f:M→R为初 始热分布,u(x,t)为t(u(x,0)=f(x)时刻的热分布。热方程为偏微分方程m=Cu。解由(x,t) AxH4(x,y)f(y)给出,其中H4是热核,即这个偏微分方程的格林函数。因此。 Cf()= Cu(, O) aM Ht(r, y)f(g) 在局部,热核近似等于高斯函数H4(x,y)≈(4xt)-e,其中‖x-y‖和t都足够的小并且 n=dimM,xy为局部坐标。注意,当t趋于0时,热核H(x,y)趋于局域化,趋于狄拉克函数,即 imn→0JMH4(x,3y)f(y)=f(x)因此,对于小t从导数的定义我们有 Cf(il 2 如果x1,,xk是M上的数据点,最后一个表达式可以近似为 Lf(il f(x:) (14) 该系数是全局的,不会影响离散拉普拉斯算子的特征向量。由于M的固有维度可能是未知的,所以 我们将a=k(4mit)。注意到常数函数的拉普拉斯变换是零,我们不需要注意a,因此拉普拉斯T将 为我们选择正确的乘数。最后了解了如何选择邻接矩阵W的边权值 W f0<‖ (15) 0 otherwise 四、实验 上面介绍了算法的具体过程,也解释了算法更细节方面的事情,我们在这里利用从网上找到的程序 对拉普拉斯特征嵌入算法在图像上的表现进行更深层次的理解。 1.实验 在参数为总数据点1000,欧氏距离,邻点数量为5,随机采样。对分布可近似看做在三维坐标中 的直线、一个平面、 Swiss roll s- curve、 Severd sphere型的数据进行拉普拉斯特征嵌入,并观察效果 Line Embedding 0 2 拉普拉斯特征映射 ZD grIc x10-3 bedding 10 2101234 Swiss roll bedding 5 0 -3 S-curve 3 拉普拉斯特征映射 2.实验二 这里我们产生在 Swiss roll形上具有些许噪声的数据100个分布在三维坐标系中,我们分别使 用邻点N为5、10、15、20、25、50、100、200的参数进行拉普拉斯特征映射,将其映射到二维坐标 系中,牛成如下为实验图像 Swiss roll ×103 Embedding 0 5 x103 Embedding Swiss ro‖l 10-3 Embedding 5 N=20 N=25 Swiss roll x103 Embedding N-50 拉普拉斯特征映射 10 N=100 N=200 同样的,这里产生随机数据在 Severed sphere形上,1000个数据点,三维坐标系,我们分别使用 邻点N为5、10、15、20、25、50、100、200的数据进行拉普拉斯特征映射,将其映射到二维坐标系 中,生成如下为实验图像 Severed sphere Embedding 平 N=5 102N=10 拉普拉斯特征映射 Severed sphere Embedding 家 N=25 Severed sphere Embedding 100 拉普拉斯特征映射 3 :3 200 通过观察图中数据,我们可以看出当邻点的数量越来越多的时候嵌入后的尺寸会变得越来越小。 10

...展开详情
试读 18P 拉普拉斯特征映射
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
Roswell_lou LE在不同数据集上的嵌入效果展示(无代码),不推荐
2020-04-26
回复
邵楷 good, 可以的
2019-03-06
回复
gadflycq 这个非常不错
2019-02-26
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
拉普拉斯特征映射 50积分/C币 立即下载
1/18
拉普拉斯特征映射第1页
拉普拉斯特征映射第2页
拉普拉斯特征映射第3页
拉普拉斯特征映射第4页

试读结束, 可继续读2页

50积分/C币 立即下载