非常见降维方法：Laplacian Eigenmaps 拉普拉斯特征映射

古城微笑少年丶 2022-06-11 07:52 220阅读 0赞

# [原文地址][Link 1] #

# 拉普拉斯矩阵 #

## Laplacian matrix 的定义 ##

谈到机器学习中的降维技术，可能大多数了解一点机器学习的朋友都知道PCA，今天为大家介绍一种新的降维方法——拉普拉斯特征映射

拉普拉斯矩阵（Laplacian matrix)），也称为基尔霍夫矩阵, 是表示图的一种矩阵。给定一个有n个顶点的图G=（V，E） ，其拉普拉斯矩阵被定义为:L=D-W

其中D为图的度矩阵，W为图的邻接矩阵。（不知道度矩阵和邻接矩阵的请自行百度）

## 拉普拉斯矩阵L的性质 ##

*  L是对称半正定矩阵；
 *  L 1 = 0 1 ，即 的最小特征值是0，相应的特征向量是 。证明：L\* 1 = ( D-W) \* 1 = 0 = 0 \* 1 。
 *  L 有n个非负实特征值
 *  且对于任何一个属于实向量f ，有以下式子成立 :   
    ![这里写图片描述][20160617095438323]

证明如下：   
![这里写图片描述][20160617095556980]

## Laplacian Eigenmaps 拉普拉斯特征映射 ##

Laplacian Eigenmaps 是用局部的角度去构建数据之间的关系。如果两个数据实例i和j很相似，那么i和j在降维后目标子空间中应该尽量接近。它的直观思想是希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。   
![这里写图片描述][20160617101302331]

使用时算法具体步骤为：

步骤1：构建图

使用某一种方法来将所有的点构建成一个图，例如使用KNN算法，将每个点最近的K个点连上边。K是一个预先设定的值。这样构建的图矩阵就是一个稀疏矩阵，只保留了最相似的K个邻居关系。

步骤2：确定权重

确定点与点之间的权重大小，例如选用热核函数来确定（当然这个地方你完全可以选择其他的相似度度量方式来衡量），如果点i和点j相连，那么它们关系的权重设定为：

![这里写图片描述][20160617102040397]

使用最小的m个非零特征值对应的特征向量作为降维后的结果输出。

前面提到过，Laplacian Eigenmap具有区分数据点的特性，可以从下面的例子看出：   
![这里写图片描述][20160617102358023]

见图1所示，左边的图表示有两类数据点（数据是图片），中间图表示采用Laplacian Eigenmap降维后每个数据点在二维空间中的位置，右边的图表示采用PCA并取前两个主要方向投影后的结果，可以清楚地看到，在此分类问题上，Laplacian Eigenmap的结果明显优于PCA。

[Link 1]: http://blog.csdn.net/dylanzr/article/details/51698249
[20160617095438323]: /images/20220611/9ec87c30c69741f7bc61ef62b546046e.png
[20160617095556980]: /images/20220611/5714cb90a7e7476bae606aace31e5b17.png
[20160617101302331]: /images/20220611/c8db0666b48440218af3a926779bbadd.png
[20160617102040397]: /images/20220611/a5070c1ce7c64bb9ba353fc3680796ad.png
[20160617102358023]: /images/20220611/bde5a5615b7e49539f1c03c2d8aef0f1.png