等距特征映射

作者: 凉拌东坡肉 | 来源:发表于2020-10-09 22:57 被阅读0次

等距特征映射
机器学习day11降维
降维
Coordinate Transformation
降维
机器学习第二课_数据预处理
实验的tricks
特征提取和特征选择
全面解读深度学习的世纪晟人脸识别技术（二）
【第25期】练字

以人脸识别为例，假设人脸维数是2020维的，那么在流形上认为人脸是2020维这个高维空间上的一个点，可以认为这两个人脸头像经过不同光照内嵌到2020维的高维空间中。

传统降维方法

经典的降维算法是PCA（主成分分析）和多维尺度分析（MDS），两个算法都能保证高维输入空间的位于线性子空间上的真实数据结构。

PCA 以方差大小衡量信息量的多少，认为方差正比于信息量，其基本思想是通过线性变换尽可能地保留方差大的数据量。

MDS 在低维嵌入空间中尽量保持原始数据任意两点之间的欧式距离。

缺点

PCA、MDS方法都是线性降维方法，对于包含非线性结构的数据，往往无法起到作用。

非线性流形需要解决的问题

对于线性方法无法解决的非线性空间结构，我们引入流形概念，将高位非线性空间引入到流形中，那么在高维非线性空间度量问题就变成了流形上的度量问题。

如何测量流形上的几何距离？
如何将高维空间映射到三维子空间？

流形方法

首先将欧式距离转换成测地距离，测地距离由测地线确定，测地线可视作直线在弯曲空间中的推广，在有度规定义存在时，测地线可以定义为空间中两点的局部最短路径。

因为流行空间的局部邻域和欧式空间同胚，因此测地距离可以通过局部邻近点的欧氏距离的积分得到。

假设领域点的集合 $X=\{x_1, x_2, x_3, \cdots, x_n\}$ ，相邻点距离为 $d_{x_i,x_j}, i \in \mathring{U}{x, \delta}$ ，那么从点 $x_1$ 到点 $x_n$ 的距离为：
$d_{x_1, x_n} = \sum_{i=1}^{n-1}d_{x_i, x_{i+1}}$
即，结果如下图所示。

因此，我们可以得到实现方法

引入图论框架，将数据作为图中的点，点与其邻近点之间使用边来连接，逼近的测地线使用最短路径代替。

ISOMap方法

步骤如下：

构建邻接图 $G$ （复杂度： $O(DN^2)$ ）

基于输入空间中 $X$ 中流形 $G$ 的邻近点对 $(i, j)$ 之间的欧氏距离 $d_x(i,j)$ ，选取每个样本点距离最近的 $K$ 个点（K-ISOMap）或在样本点选定半径为 $\varepsilon$ 的圆内所有点为该样本点的近邻点，将这些近邻点用边连接，将流形 $G$ 构建为一个反映邻近关系的带权流通图 $G$ ;
计算所有点对之间的最短路径（复杂度： $O(DN^2)$ ）

通过计算邻接图 $G$ 上任意两点之间的最短路径逼近流形上的测地距离矩阵 $D_G = \{d_G(i,j)\}$ ，实现最短路径的常用算法有Floyd或者Dijkstra。
构建k维坐标向量（复杂度： $O(dN^2)$ ）

根据图距离矩阵 $D_G=\{d_G(i,j)\}$ 使用经典MDS算法在d维空间Y中构造数据的嵌入坐标表示（如下图C所示），选择低维空间Y的任意两个嵌入坐标向量 $y_i$ 与 $y_j$ 使得代价函数最小：
$min \space \phi(Y)=\sum^N_{i=1}\sum^N_{j=1}(d^G_{ij}-\|y_i-y_j\|)^2$
式2的全局最优解可以通过将坐标向量 $y_j$ 设置为距离矩阵 $D_G$ 前 $d$ 个特征值对应的特征向量来得到。