包含映射与嵌入映射,映射的嵌入
传统的线性降维方法，如主成分分析和因子分析，侧重于样本的方差，可以学习线性流形的结构，但不能学习非线性流形。经典的流形学习方法可以学习非线性流形结构，但由于属于直接学习，不能推广新样本。另外，一些基于核函数的降维方法，如KPCA，可以处理非线性问题，但忽略了流形的非线性结构。
作为LLE算法的线性近似，NPE不仅能捕捉到流形的非线性结构，而且保留了线性性质，并能推广新的样本。因此，NPE可以很容易地处理新的样品，同时取得令人满意的结果，并已广泛应用于工业。
关于流形的问题，比如流形是什么，为什么要研究流形，请看我之前的博客《学习流形》。
NPE算法的思路和步骤与LLE相同，主要是在降维过程中保持流形的局部线性结构不变，从而从数据中提取有用的信息。这里，局部线性结构用重构权矩阵来表征，重构权矩阵是邻居对邻域内节点线性重构的系数矩阵。
与其他经典流形学习算法类似，NPE的算法步骤主要分为三步：
1.构建邻域图。k近邻(KNN)算法用于构建邻域图。假设有m个样本，邻域图中有m个节点，其中( mathbf{x} _ {i} )表示第I个节点。如果( mathbf{x} _ {j} )是( mathbf{x} _ {i} )的k个最近邻之一，则连接这两点，否则不连接。
2.计算权重矩阵(提取流形特征)。设权重矩阵为(mathbf{W})，其中元素(W _{ij})表示节点I和节点j之间边的权重，如果两点之间没有变化，则对应的矩阵元素为0。matrix (mathbf{W})的元素值主要通过最小化以下目标函数来获得：
[ min sum _ { I } left left mathbf { x } _ { I }- sum _ { j } w _ { ij } mathbf { x } _ { j } right right ^{2}，]
其中(mathbf{W})应满足规范化约束：
[ sum _{j} W _{ij}=1，j=1，2，m. ]
3.计算映射。通过求解广义特征向量问题来计算降维线性映射：
[ mathbf { xmx } ^{t} mathbf { a }= lambda mathbf { xx } ^{t} mathbf { a }，]
其中数据集 ( mathbf {x}=( mathbf {x} _ {1}， mathbf {x} _ {m}) )，matrix ( mathbf { m }=( mathbf { I }-
将求解的特征向量按特征值降序排列( (lambda _ {0} leq. leq lambda _ { d-1 } )( mathbf { a } _ { 0 }， mathbf {a})
[ mathbf { y } _ { I }= mathbf { a } ^{t} mathbf { x } _ { I }，]
在…之中
[ mathbf{A}=( mathbf{a} _{0}，mathbf{a} _{1}，mathbf{a} _{d-1})。]
NPE算法的推导NPE算法主要是先提取流形的局部线性信息，然后通过保留这些信息来降维。具体来说，NPE首先用局部线性重构来表示流形的局部线性结构，其形式是均方偏差。如果样本数为m，维数为n，降维后的维数为d，且(mathbf{Q} (i))为样本I的k个相邻样本的集合，则在高维空间中表征重构误差的目标函数为：
[ phi( mathbf { w })= sum ^{m} _ { I=1 } left left mathbf { x } _ { I }- sum _ { j in mathbf { q }(I)} w _ { ij } mathbf { x } _ { j } right right ^{2}，]
通过优化目标函数得到的矩阵(mathbf{W})包含流形的局部信息。在降维过程中，NPE的目标是在参数空间(降维后的低维空间)保持与高维原始空间相同的局部线性重构(即在目标函数中使用相同的权重矩阵(mathbf{W} ))实现线性降维。其低维空间的目标函数是：
[ phi( mathbf { y })= sum ^{m} _ { I=1 } 左 左 y _ { I }- sum ^{m} _ { j=1 } w _ { ij } y _ { j } 右 右 ^{2}.]
NPE的算法推导主要分为两步，一是计算权重矩阵，二是计算映射和低维嵌入。具体推导如下：
首先，第一目标函数被表示为矩阵：
[ phi( mathbf { w })= sum ^{m} _ { I=1 } left left mathbf { x } _ { I }- sum _ { j in mathbf { q }(I)} w _ { ij } mathbf { x } _ { j } right right ^{2} ]
[= sum ^{m} _ { I=1 } left left sum _ { j in mathbf { q }(I)} w _ { ij } mathbf { x } _ { I }- sum _ { j in mathbf { q }(I)} w _ { ij } mathbf { x } _ { j } right right ^{2} ]
[= sum ^{m} _ { I=1 } left left sum _ { j in mathbf { q }(I)} w _ { ij }( mathbf { x } _ { I }- mathbf { x } _ { j }) right right ^{2} ]
[= mathbf { w } ^{t} _ { I }( mathbf { x } _ { I }- mathbf { x } _ { j })( mathbf { x } _ { I }- mathbf { x } _ { j })^{t} mathbf { w } _ { I } ]
[= sum ^{m} _ { I=1 } mathbf { w } ^{t} _ { I } mathbf { z } _ { I } mathbf { w } _ { I } ]
其中(mathbf{W} _ {i})是由样本I的k个相邻点对应的权重系数组成的列向量，矩阵( mathbf { z } _ { I }=( mathbf { x } _ { I }- mathbf { x } _ { j
考虑到归一化的约束，我们将约束方程转换成矩阵形式：
[ sum _ { j in mathbf { q }(I)} w _ { ij }= mathbf { w } ^{t} _ { I } mathbf { 1 } _ { k }=1，]
其中(mathbf{1} _{k})是k维全1向量。
拉格朗日乘数法用于将矩阵形式的目标函数和约束方程组合成一个目标：
[ mathbf { l }( mathbf { w })= sum ^{m} _ { I=1 } mathbf { w } ^{t} _ { I } mathbf { z } _ { I } mathbf { w } _ { I } lambda ( mathbf { w } ^{t} _ { I } mathbf { 1 } _ { k }-1)。]
对(mathbf{W})求导，设其值为0，则：
[ mathbf { w } _ { I }=- dfrac { 1 } { 2 } lambda mathbf { z } ^{-1} _ { I } mathbf { 1 } _ { k }。]
使用归一化约束对结果进行归一化，最终权重矩阵(mathbf{W} _{i})为：
[ mathbf { w } _ { I }= dfrac {- dfrac { 1 } { 2 } lambda mathbf { z } ^{-1} _ { I } mathbf { 1 } _ { k } } { mathbf { w } ^{t} _ { I } mathbf { 1 } _ { k } } ]
[= dfrac { mathbf { z } ^{-1} _ { I } mathbf { 1 } _ { k } } { mathbf { 1 } ^{t} _ { k }( mathbf { z } ^{-1} _ { I })^{t} mathbf { 1 } _ { k } }。]
得到权重矩阵后，就可以计算降维映射了。首先定义：
[z _ { I }=y _ { I }- sum ^{m} _ { j=1 } w _ { ij } y _ { j }，]
然后将上述公式转换成矩阵形式：
[ mathbf { z }= mathbf { y }- mathbf { Wy }=( mathbf { I }- mathbf { W }) mathbf { y }。]
那么第二目标函数可以简化为：
[ phi( mathbf { y })= sum ^{m} _ { I=1 } left(y _ { I }- sum ^{m} _ { j=1 } w _ { ij } y _ { j } right)^{2} ]
[=sum ^{m} _{i=1} (z _{i}) ^{2} ]
[=mathbf{z} ^{T} mathbf{z} ]
[= mathbf { y } ^{t}( mathbf { I }- mathbf { w })^{t}( mathbf { I }- mathbf { w }) mathbf { y }。]
由于NPE算法是一种线性降维方法，降维后的嵌入可以表示为：
[ mathbf { y } ^{t}= mathbf { a } ^{t} mathbf { x }，]
这里(mathbf{y})只是m个样本降维后的嵌入坐标，(mathbf{a})是其对应的映射。
那么第二目标函数可以进一步表示为：
[ phi( mathbf { y })= mathbf { a } ^{t} mathbf { x }( mathbf { I }- mathbf { w })^{t}( mathbf { I }- mathbf { w }) mathbf { x } ^{t} mathbf { a } ]
[= mathbf { a } ^{t} mathbf { x } mathbf { m } mathbf { x } ^{t} mathbf { a }。]
并且参数空间的嵌入坐标也有约束：
[ mathbf { y } ^{t} mathbf { y }=1 implies mathbf { a } ^{t} mathbf { x } mathbf { x } ^{t} mathbf { a }。]
对于第一个目标函数的求解，这里用拉格朗日乘子法将第二个目标函数与约束条件结合起来，求其导数，可以得到如下的广义特征向量问题：
[ mathbf { xmx } ^{t} mathbf { a }=拉姆达mathbf{XX} ^{T} mathbf{a}。]
其中(mathbf{M})可以从得到的权重矩阵(mathbf{W})中得到，则可以求解上述广义特征向量。最后，将从解中获得的特征向量排列成映射矩阵。
代码实现这里分别给出了python和matlab的代码实现。
Python首先创建了一个典型的“瑞士体”数据集：
进口瑞士卷(N=1000):TT=numpy。数组((5 * numpy。/4)*(1 ^ 2 * numpy。兰德。rand(N)))height=numpy。数组((numpy。兰德。N)-0.5))噪声=0.0x=numpy。数组((TT噪声* numpy。随机的。randn(N))* numpy。cos(TT)，10 *身高，(TT噪音* numpy。随机的。边缘接着，再利用幕府时代的将军库来进行NPE算法的实现：
将现代的幕府导入为SG #加载数据feature _ matrix=Swiss roll()#创建特征实例features=SG .真实特征(feature_matrix)#创建邻域保持嵌入转换器instanceconverter=sg .neighborhoodspreservingembedding()#设置目标dimensionalityconverter。set _ target _ dim(2)#设置相邻转换器的数量。set _ k(10)# set num _ threads(2)# set null space shift(可选)转换器。set _ nullspace _ shift(-1e-6)#使用邻域保留投影方法计算嵌入嵌入=转换器。嵌入(特性)MATLAB至于矩阵实验室代码在何晓飞教授的主页上有，由于篇幅过长，这里就不贴出来了。
转载于：https://www。cn博客。com/woaiml/p/manifold 2。超文本标记语言
