高维数据流行学习分析方法：本征维数估计

在ISOMAP算法中，本征维数可以由嵌入向量重构的残余误差来估计。图3-1显示了用ISOMAP、PCA和MDS映射后嵌入向量重构的残余误差来分别估计姿态、光照条件变化的人脸图像、Swiss Roll数据集、人手姿态图像和手写数字“2”的本征维数，其中图3-1的(A)、(B)和(C)中实心圆点标记的曲线对应的是应用ISOMAP算法，在(D)中，空心圆点标记的曲线对应的是应用MDS算法，三角形标记的曲线对应的是应用PCA算法。从图中可以发现，对于这四种数据，当它们所对应的维数在分别达到3、2、2和4后，随着维数的增加，它们的残余误差将基本保持不变或变化不大。也就是说它们所对应的本征维数分别是3、2、2和4。

图3-1　(A)姿态、光照变化的人脸图像
(B)Swiss Roll数据集
(C)人手姿态图像
(D)手写数字“2”的特征维数与残余差的变化关系曲线图

目前常用的本征维数估计方法可分为三类:特征映射法、几何学习法和统计学习法。下面分别对这三种方法进行介绍。

(1)特征映射法

特征映射法是一种基于全局PCA或者局部PCA的方法，其关键在于PCA能得到一个从高维空间到低维空间的均方误差最小的映射。因此可以对局部数据采用局部PCA进行特征分解，选取对应特征值最大的几个的特征向量作为本征特征。本征特征数是由特征值比值大于一个给定阈值的个数决定的，即:

其中，λi是特征值，d是选取的特征个数，n是样本个数，δ是所选取的阈值。表3-1为局部PCA方法选取本征特征的算法提纲。

表3-1　局部PCA方法选取本征特征的算法提纲

从式(3.1)可以看出，应用局部PCA来选取本征维数取决于数据的局部邻域划分和阈值的选择，所以特征映射方法虽然是数据分析中的一个简单实用的工具，却不能对本征维数提供可靠的估计。

(2)几何学习法

几何学习法主要是通过挖掘数据的本质几何特征确定本征维数。这种方法是一种基于不规则小块维数的本征维数征确定方法。在几何学习方法中，首先定义了一个“箱子计数”维数，该定义可以看做Haussdorff维数的一种简化形式。对于一个数据集Ω而言，其“箱子计数”维数可以进行如下的定义:

(www.xing528.com)

其中，DB为数据集的“箱子计数”维数为，v(r)表示能够覆盖数据子集Ω且大小为r的“箱子”的个数。

然而“箱子计数”维数只能计算低维数据的本征维数。当数据集的维数很高时，“箱子计数”维数的计算复杂度就相当的大。为了解决这个问题，研究者提出了用相关维数来取代“箱子计数”维数。相关维数具有计算简单的特点。在相关维数中，首先定义了一个如下所示的相关函数Cm(r):

其中，I是一个显示器函数，N为数据中样本的个数。在此基础上，相关维数按照下面的表达式计算:

(3)统计学习方法

统计学习方法是Levina提出的一种新的本征维数估计方法，它在近邻点的距离度量中采用最大似然估计方法(Maximum Likelihood Estimation，MLE)来设计分类器，并从理论和仿真结果证明了其可行性。

最大似然估计方法通过建立近邻点对间距离的似然函数来得到基于本征维数的最大似然函数，从而对本征维数进行最大似然估计。

设X1，X2，…，Xn是D维空间中的随机采样样本，构造一个二项随机过程:

其中，Sx(t)表示以Xi为中心、半径为t的球。N(t，x)记录X1，X2，…，Xn落在Sx(t)中的次数。