拉普拉斯矩阵/特征映射
https://www.jianshu.com/p/87057397a070
https://blog.csdn.net/v_july_v/article/details/40738211
https://blog.csdn.net/yujianmin1990/article/details/48420483
https://www.cnblogs.com/xbinworld/archive/2012/11/29/2795287.html
http://web.cse.ohio-state.edu/~belkin.8/papers/LEM_NIPS_01.pdf
1.拉普拉斯矩阵(Laplacian Matrix)
- 表示图的一种矩阵,给定n个顶点的图,分别表示graph、vertex、edge
- Laplacian Matrix定义为,D为度矩阵,W为邻接矩阵
例子:
则邻接矩阵W为
度矩阵D为
则拉普拉斯矩阵为
拉普拉斯矩阵的性质
- L是对称半正定矩阵
- ,即最小特征值是0,
- L有n个非负的实特征值
- 对任意实向量,成立
2.拉普拉斯特征映射步骤
拉普拉斯特征映射将处于流形上的数据,在尽量保留原数据间相似度的情况下,映射到低维下表示。 流程:2.1 构造邻近图(用邻近图近似流形)
- 距离阈值,
- K近邻
2.2 计算边权重(样本间相似度)
- 热核
- 简单形式
2.3 特征映射
- 求解;——广义特征值问题
- 得到特征值和特征向量
- 取最小的m个非零特征值的特征向量作为降维结果,即
3.推导
希望相互间有关系的点(在图中相连的点)在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。
假设样本n个,目标维度m,则目标矩阵为,每个行向量表示在目标空间中的向量那个表示,拉普拉斯特征映射要最小化目标函数
令对角阵D为W中每行之和,经过线性变化([3]中有推导)转化为优化
使得公式最小化的Y的列向量是以下广义特征值问题的m个最小非0特征值对应的特征向量