网站开发兴趣组,浙江网缘电子商务有限公司,南宁网站建设贴吧,网站成品超市拉普拉斯特征映射#xff08;Laplacian Eigenmaps#xff09;#xff0c;主要包括拉普拉斯特征映射#xff08;Laplacian Eigenmaps#xff09;使用实例、应用技巧、基本知识点总结和需要注意事项#xff0c;具有一定的参考价值#xff0c;需要的朋友可以参考一下。
1 …拉普拉斯特征映射Laplacian Eigenmaps主要包括拉普拉斯特征映射Laplacian Eigenmaps使用实例、应用技巧、基本知识点总结和需要注意事项具有一定的参考价值需要的朋友可以参考一下。
1 介绍 拉普拉斯特征映射Laplacian Eigenmaps是一种不太常见的降维算法它看问题的角度和常见的降维算法不太相同是从局部的角度去构建数据之间的关系。也许这样讲有些抽象具体来讲拉普拉斯特征映射是一种基于图的降维算法它希望相互间有关系的点在图中相连的点在降维后的空间中尽可能的靠近从而在降维后仍能保持原有的数据结构。
2 推导 拉普拉斯特征映射通过构建邻接矩阵为 W W W (邻接矩阵定义见这里) 的图来重构数据流形的局部结构特征。其主要思想是如果两个数据 实例 i i i 和 j j j 很相似那么 i i i 和 j j j 在 降维后目标子空间中应该尽量接近。设数据实例的数目为 n n n 目标子空间即最终的降维目标的维度为 m m m 。 定义 $ n \times m$ 大小的矩阵 Y Y Y 其中每一个行向量 y i T y_{i}^{T} yiT 是数据实例 i i i 在目标 m m m 维子空间中的向量表示即降维后的数据实例 i i i 。我们的目的是 让相似的数据样例 i i i 和 j j j 在降维后的目标子空间里仍旧尽量接近故拉普拉斯特征映射优化的目标函数如下: min ∑ i , j ∥ y i − y j ∥ 2 W i j \min \sum\limits _{i, j}\left\|y_{i}-y_{j}\right\|^{2} W_{i j} mini,j∑∥yi−yj∥2Wij
下面开始推导
$ \begin{array}{l} \sum\limits_{i1}^{n} \sum\limits_{j1}{n}\left|y_{i}-y_{j}\right|{2} W_{i j} \ \sum\limits_{i1}^{n} \sum\limits_{j1}{n}\left(y_{i}{T} y_{i}-2 y_{i}^{T} y_{j}y_{j}^{T} y_{j}\right) W_{i j} \ \sum\limits_{i1}{n}\left(\sum\limits_{j1}{n} W_{i j}\right) y_{i}^{T} y_{i}\sum\limits_{j1}{n}\left(\sum\limits_{i1}{n} W_{i j}\right) y_{j}^{T} y_{j}-2 \sum\limits_{i1}^{n} \sum\limits_{j1}^{n} y_{i}^{T} y_{j} W_{i j} \ 2 \sum\limits_{i1}^{n} D_{i i} y_{i}^{T} y_{i}-2 \sum\limits_{i1}^{n} \sum\limits_{j1}^{n} y_{i}^{T} y_{j} W_{i j} \ 2 \sum\limits_{i1}^{n}\left(\sqrt{D_{i i}} y_{i}\right)^{T}\left(\sqrt{D_{i i}} y_{i}\right)-2 \sum\limits_{i1}^{n} y_{i}{T}\left(\sum\limits_{j1}{n} y_{j} W i j\right) \ 2 \operatorname{trace}\left(Y^{T} D Y\right)-2 \sum\limits_{i1}^{n} y_{i}^{T}(Y W)_{i} \ 2 \operatorname{trace}\left(Y^{T} D Y\right)-2 \operatorname{trace}\left(Y^{T} W Y\right) \ 2 \operatorname{trace}\left[Y^{T}(D-W) Y\right] \ 2 \operatorname{trace}\left(Y^{T} L Y\right) \end{array} $
其中 $W $ 是图的邻接矩阵对角矩阵 D D D 是图的度矩阵 ( D i i ∑ j 1 n W i j ) \left(D_{i i}\sum\limits_{j1}^{n} W_{i j}\right) (Diij1∑nWij) $ LD-W$ 成为图的拉普拉斯矩阵。
变换后的拉普拉斯特征映射优化的目标函数如下: min trace ( Y T L Y ) s.t. Y T D Y I \begin{array}{l}\min \operatorname{trace}\left(Y^{T} L Y\right)\\ \text { s.t. } Y^{T} D YI \end{array} mintrace(YTLY) s.t. YTDYI
其中限制条件 s . t . Y T D Y I s . t . Y^{T} D YI s.t.YTDYI 保证优化问题有解下面用拉格朗日乘子法对目标函数求解: f ( Y ) tr ( Y T L Y ) tr [ Λ ( Y T D Y − I ) ] f(Y)\operatorname{tr}\left(Y^{T} L Y\right)\operatorname{tr}\left[\Lambda\left(Y^{T} D Y-I\right)\right] f(Y)tr(YTLY)tr[Λ(YTDY−I)] ∂ f ( Y ) ∂ Y L Y L T Y D T Y Λ T D Y Λ 2 L Y 2 D Y Λ 0 \begin{array}{l} \frac{\partial f(Y)}{\partial Y}L YL^{T} YD^{T} Y \Lambda^{T}D Y \Lambda \\ 2 L Y2 D Y \Lambda0 \end{array} ∂Y∂f(Y)LYLTYDTYΛTDYΛ2LY2DYΛ0 ∴ L Y − D Y Λ \therefore L Y-D Y \Lambda ∴LY−DYΛ
其中用到了矩阵的迹的求导具体方法见 迹求导。 Λ \Lambda Λ 为一个对角矩阵另外 L L L 、 D D D 均为实对称矩阵其转置与自身相等。对于单独的 y y y 向量上式可写为: L y λ D y L y\lambda D y LyλDy这是一个广义特征值问题。通过求得 m m m 个最小非零特征值所对应的特征向量即可达到降维的目 的。
关于这里为什么要选择 m m m 个最小非零特征值所对应的特征向量。将 $L Y-D Y \Lambda $ 带回到 min trace ( Y T L Y ) \min \operatorname{trace}\left(Y^{T} L Y\right) mintrace(YTLY) 中由于有着约束条件 Y T D Y I Y^{T} D YI YTDYI 的限制可以得到 $ \min \quad \operatorname{trace}\left(Y^{T} L Y\right)\min \quad t r a c e(-\Lambda)$ 。即为特 征值之和。我们为了目标函数最小化要选择最小的 m m m 个特征值所对应的特征向量。
3 步骤 使用时算法具体步骤为:
步骤1构建图
使用某一种方法来将所有的点构建成一个图例如使用KNN算法将每个点最近的K个点连上边。K是一个预先设定的值。
步骤2确定权重
确定点与点之间的权重大小例如选用热核函数来确定如果点 i 和点 j 相连那么它们关系的权重设定为 W i j e − ∥ x i − x j ∥ 2 t W_{i j}e^{-\frac{\left\|x_{i}-x_{j}\right\|^{2}}{t}} Wije−t∥xi−xj∥2
另外一种可选的简化设定是 W i j 1 W_{i j}1 Wij1 如果点 i i i $ j$ 相连否则 $W_{i j}0 $ 。
步骤3特征映射
计算拉普拉斯矩阵 L L L 的特征向量与特征值: $L y\lambda D y $
使用最小的 m m m 个非零特征值对应的特征向量作为降维后的结果输出。
