高维数据流形图表分析

2.4.3.1　基本思想

Brand提出的流形Charting方法是一种基于局部邻域差异保持的流形学习方法。流形Charting方法的基本思想是:首先通过Charting，将高维样本数据划分为若干个局部邻域，并且针对每一个邻域分别建立所对应的局部坐标系。然后将这些局部坐标系通过一种仿射关系统一到一个坐标系中，实现高维数据到低维空间的统一映射。

2.4.3.2　算法步骤

(1)Charting

首先将原始数据分割成多个局部线性的邻域，然后将这些领域分别投影到相应的子空间，在投影过程中需要满足以下两个标准:

①在原始空间构成所在邻域的样本点投影到子空间后，其局部协方差损失要最小；

②在原始空间构成所在邻域的样本点投影后到子空间后还是在这个样本点投影的邻域的可能性最大。

对于每一个邻域可以分别采用高斯模型建模，即每一个邻域的中心点就是该邻域所有样本点的均值，其所在的坐标轴由该邻域所有样本点的协方差矩阵所对应的特征向量张成，并且坐标轴的数量由该邻域所有样本点协方差矩阵的特征值的个数决定。如果一个样本点正好落在该邻域范围以内，那么该邻域中所有样本点协方差矩阵的非零特征值个数就是该子流形的特征维数，并且由这些非零特征值对应的特征向量为轴组成的局部坐标系是最优的，能够实现投影前后局部邻域样本点协方差矩阵保持不变。因此，对于所有局部领域，可以采用一个混合高斯模型来建模，建立基于混合高斯模型最大似然目标函数，进行最优值的求解，满足标准①。

标准②隐含了一个要求:在邻域的划分过程中，相邻邻域所投影的子空间应该有相同的坐标轴，即所对应投影子空间尽量相似。因为如果子空间不相似将导致一个高维样本点在对应投影子空间内不一致，那么将最终无法确定该高维样本在低维子空间内的确切投影。在对每一个邻域建立高斯模型的基础上，邻域之间的相似度度量可以采用两个高斯模型的交叉熵进行表示，模型如下:

因此该度量可以测量不同邻域的规模、方向和位置的不同。当上式中右边的前三项均为0时，意味着两个邻域的重合度达到最大。另外，为了度量相邻两个邻域的吻合度，建立如下模型:

其中，mi(μj)是一个邻域局部结构在另一个邻域的度量。(www.xing528.com)

经过优化，可以得到混合高斯模型D(N1‖N2)的协方差估计值:

从上式可以看出，每个高斯模型的协方差都是互相依赖的。如果协方差比较小，就意味着子空间离邻域中心点距离小，满足以上标准②。

(2)连接

最后改优化问题可以简化为:

其中，

因此，映射矩阵G可以将各局部坐标系映射到统一坐标系。最后高维护具在地位空间的映射计算如下:

其中，“＋”表示矩阵的伪逆。

2.4.3.3　算法分析

流形Charting方法能够较好地实现具有复杂结构的数据在低维空间的映射，特别是对于包含有噪声的数据能够较好地学习其几何结构信息。其原因在于:①不仅仅是原始高维数据的局部信息，而且其全局信息都被用来构建局部邻域坐标系以及将它们连接成统一坐标系统；②在投影前后，仅仅是局部邻域中点到点之间的距离信息得到保持。对于流形Charting方法而言，其缺点在于将原始数据自然分割成若干邻域和将这些邻域坐标系连接成统一坐标系的过程中，需要付出极大的计算成本。