5.1.4 局部线性嵌入法
局部线性嵌入(locally linear embedding)算法是针对非线性信号特征矢量维数的优化方法,这种维数优化并不是仅仅在数量上简单的约简,而是在保持原始数据性质不变的情况下,将高维空间的信号映射到低维空间上,即特征值的二次提取。LLE算法假设在局部领域内数据点是线性的,所以邻域内任意一点,都可用局部近邻点来线性表示。LLE算法是由重构成本函数最小化求出最优权值,各点的局部邻域权值能够在多尺度变换下仍保持不变。LLE算法无迭代计算过程,可使计算复杂度大幅度减小。
LLE首先假设数据在较小的局部是线性的,也就是说,某一个数据可以由它邻域中的几个样本来线性表示。比如我们有一个样本x 1,在它的原始高维邻域里用K-近邻思想找到和它最近的三个样本x 2,x 3,x 4,然后假设x 1可以由x 2,x 3,x 4线性表示,即
x 1=w 12x 2+w 13x 3+w 14x 4
其中,w 12,w 13,w 14为权重系数。通过LLE降维后,我们希望x 1在低维空间对应的投影x'1和x 2,x 3,x 4对应的投影x'2,x'3,x'4也尽量保持同样的线性关系,即
x 1≈w 12x'2+w 13x'3+w 14x'4
也就是说,投影前后线性关系的权重系数w 12,w 13,w 14是尽量不变或者最小改变的。从上面可以看出,线性关系只在样本的附近起作用,离样本远的样本对局部的线性关系没有影响,因此降维的复杂度降低了很多。
LLE算法主要分为三步。第一步是求K近邻的过程,这个过程使用了和KNN算法一样的求最近邻的方法。第二步是对每个样本求它在邻域里的K个近邻的线性关系,得到线性关系权重系数W。第三步是利用权重系数来在低维里重构样本数据。
具体过程如下:输入为样本集D={x 1,x 2,…,x m},最近邻数k,降维到的维数d,输出是低维样本集矩阵D'。
(1)for i 1 to m,按欧氏距离作为度量,计算和x i最近的k个最近邻(x i1,x i2,…,x ik)。(https://www.daowen.com)
(2)for i 1 to m,求出局部协方差矩阵Z i=(x i-x j)T(x i-x j),并求出对应的权重系数向量:
(3)由权重系数向量W i组成权重系数矩阵W,计算矩阵M=(I-W)(I-W)T。
(4)计算矩阵M的前d+1个特征值,并计算这d+1个特征值对应的特征向量{y 1,y 2,…,y d+1}。
(5)由第二个特征向量到第d+1个特征向量所张成的矩阵即为输出低维样本集矩阵D'=(y 2,y 3,…,y d+1)。
整个LLE算法用一张图可以表示如图5.10所示。
图5.10 LLE算法
