局部线性嵌入算法及其稳定性实现.pdf

《局部线性嵌入算法及其稳定性实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、电信息技术局部线性嵌入算法及其稳定性实现夏洁云(广东工程职业技术学院)摘要：局部线性嵌入(1ocallylinearembedding，LLE)算法是一种非常有效的非线性数据降维算法，广泛应用于机器学习、数据挖掘、模式识别等领域。它通过两次局部最小化实现对高维数据的非线性降维。首先给出了LLE算法关键步骤的理论实现，然后对LLE算法降维效果进行验证，最后在非均匀采样数据集上，分别验证了LLE算法的邻域点稳定性和数据点采样稳定性，有效地验证了LLE算法作为非线性降维算法的良好性能。关键词：LLE；数据降维；局部最小化性组合来逼

2、近它(重构这个数据点)。O引言重构误差使用式(1)度量：局部线性嵌入(1ocallylinearembedding，LLE)算法[】基于简单的几何直觉，由于计算简单，性能良c，Ⅳ=善Il一芸『·好，被广泛应用【3_5l。近些年来对LLE算法的改进有其中，权重反映了第，个数据点对重构第个数据很多，如改进距离测度的有：加权距离[6]、核相关变换[7]．改进权重计算的有：局部线性变换[驯、多权重点的贡献。组合方法[¨】；改进嵌入计算的有：减少孤立子影响重构权重反映了数据的内在属性，且对于旋算法[12-13]、展开流形算、法【]等。

3、虽然这些改进算法对转、尺度、平移等变换具有不变性。据此，对数据在LLE算法的性能有很大的提升，但对于LLE算法关原高维空间的局部几何关系的刻画同样适用于流形键步骤的理论实现却相对较少，并且对LLE算法在上的patch。即在维空间里用于重构数据点的非均匀采样条件下，对邻域点数以及数据采样点数的权重与在m维空间里重构的权重一样。LLE稳定性实现也很少。本文对LLE算法的关键步骤进基于上述思想，构造一个能够保持邻居关系的映射。行理论实现，同时在各种经典流形上对LLE算法的算法的最后结果是，每一个高维的观测数据Xiro都实际降维效果

4、进行验证分析，并在非均匀采样条件被映射到一个低维表示。数据的低维表示通过下，验证并讨论LLE算法对邻域点数和采样点数的式(2)求得：稳定性。-T)=一W1LLE算法⋯j=l『给定一个数据点集Ⅳ，这里式(2)与式(1)一样，都是基于重构误差。不同的是，XN=[21，．．．，、v]表示一个Ⅳ×的矩阵，这里是固定而求得的坐标的最优解。】，表示其中Ⅳ的每一行表示某个数据点的各个坐标。假一个N×m的矩阵，其中y的每一行表示某个数据点定这些数据点是采样自一个潜在的流形。如果这些数在低维空间的坐标。据是充足的(即对流形是一个充分的采样)，

5、即使不2算法关键步骤知道这个潜在的流形是什么样，但可以认为，对于每一个数据点，它与其邻点所形成的局部区域(通常称对LLE算法两个关键步骤的理论基础进行分析为一个patch)是线性的。可用一个数据点的邻点线和推导，从理论层面实现LLE算法的具体过程。122．1权重构建限制Il=1，且考虑到是一个实对称令∈RD，一，∈RD是它的邻域，令矩阵，则irⅣowⅣⅣ()实质上就是矩阵=【⋯】∈Rr表示每个邻域的权重，并且，Ⅳ×ⅣⅣ在上的瑞利商值：满足∑W=f=l，则有：／lOWi=1ⅣⅣⅣ()=哌l()l，i=1，⋯，d。根据瑞利商的性

6、质，对于任意的向量，0一喜暑fl=II喜c置．II．mRA()，这里和分别是矩阵=IlGG硎=GDA的最小和最大特征值，而且，R()在与i相对应的特征向量上达到最小值，在与‰相对应的特其中GD=【i一⋯XK一】。征向量匕达到最大值。通过正则化可得：3U正算法实验()=TGD+(F-1)LLE算法的降维效果在3个比较经典的人工流形一阶微分可得：数据集Swissroll、Twopeaks和Punchedsphere上进()=2GKGo+rKl=0行验证，其中Punchedsphere为非均匀采样数据集。另外，在Punchedsp

7、here上又分别验证LLE算法在非即GDT~一删。从而均匀数据集上对于邻域点选择和数据点采样的稳定=一()～r删。又由于rT=1，也性。3．1LLE算法的实际降维效果即：l=r=一。()～r，则有图1～图3分别为LLE算法在Swissroll、Two：～一兰一：一一从而可得：peaks和Punchedsphere上的数据降维效果。数据集统rGD~)～r删一采样1000个数据点，采样8个点的数据邻域。由图1～图3可以看出，LLE算法具有很好的非一(GGD)一r线性数据降维效果。在有效降低高维数据的同时还能r(GG。)一F，(5

8、)够有效保持数据点之间的邻域关系不变。从图像上数2．2嵌入向量据点的分布情况可以看到，降维之前相对较近的数据Ⅳ=l⋯I，则目标函数变为：点，降维之后依然保持近邻关系。图1(为三维的卷曲瑞士卷曲面，图1(b)为LLE算法的降维效果图，虽(Ⅳ)=lIⅣⅣI『然不能将瑞士卷完全展开成平面，但已经