流形学习中的本质维数估计方法的研究

    李春霞　李燕杰　胡潇涵　张林

    

    摘要：文章旨在将近年来出现的流形学习中的本质维数估计方法进行分类，通过在典型数据集上的实验比较，得出针对不同现实应用的本质维数估计方法选取策略，将对高雏数据的降雏及后续处理产生指导意义。

    关键词：本质维数；维数估计；流形学习

    流形学习是建立在数据分布于高维空间的一个低维流形的假设基础上的，而如何确定该低维流形对应的本质维数是流形学习的一个重要研究方向。本质维数，即描述数据集中全部数据所需要的自由参数（或独立坐标）的最小数目。可见，将高维数据降到它的本质维数坐标系，便能提取数据的本质特征。尽管近年来本质维数估计引起国内外研究者的广泛关注，但目前仍缺少对如何科学选取本质维数估计方法的研究。

    1.本质维数估计方法分类

    笔者将近年来出现的数据本质维数估计方法，按照构造原理的不同，大致分为4类：基于k-近邻距离的方法、基于特征值的方法、基于分形维数的方法和基于熵图的方法。

    1.1基于k-近邻距离的方法

    该类方法利用了k-近邻距离与邻域尺寸k间线性关系中蕴涵的本质维数信息，构造快速的本质维数估计方法。

    全局方法直接估计数据集的本质维数。此类方法基于rk（x）的密度估计，利用数据与其近邻间距离的分布信息迭代地估计数据集的本质维数。该算法对样本数目及算法参数的选择比较稳定，但对噪声比较敏感。局部方法则只能直接估计出各数据点的局部本质维数，结合所有点，求其全局本质维数。提出k-k/2近邻法，基于数据分布在rk（x），rk2（x）内的概率与本质维数的关系进行估计。该算法思想简单，快速有效，具有完整的统计收敛性理论。

    基于k-近邻距离的方法计算速度较快，但对于噪声较敏感，因此需加强算法鲁棒性。

    1.2基于特征值的方法

    该类方法通过分析数据的协方差矩阵的特征结构，描述数据所需特征值的最小数目（本质维数）由协方差矩阵特征值的重要程度来决定。

    全局方法在将数据从高维空间映射到低维空间的过程中寻找使映射误差最小的子空间。例如，主成分分析（PCA）由非零特征值的数目来估计本质维数。但它并未考虑数据的非线性性质，往往过高估计维数。鉴于PCA的缺点，文献提出了基于全局保持的局部线性嵌入（GPLLE）算法，不但保留原始高维数据的重要信息，同时去除噪声和异常点的影响。

    该类方法对特定分布的数据集计算效果较好，但依赖于特征结构估计，计算复杂度较大。

    1.3基于分形维数的方法

    该类方法利用数据的分形结构自相似特性近似估计本质维数。常用方法是通过估计关联维数近似表示本质维数，与传统算法相比，该算法计算效果显著，但需充分的先验知识，而且它所基于的维数估计与分布相独立的假设并不总是一致。对非均匀分布数据，关联维数不能较好近似本质维数，所以文献通过计盒维数来近似估计本质维数，该算法对于样本的不同分布较稳定，但计算复杂度较高。

    基于分形维数的方法可得到非整数的维数，可精细度量数据的复杂度。但一般需要大量数据，且存在尺度r的选择问题，因此仍存在计算普适性问题。

    1.4基于熵图的方法

    该类方法是基于图论中的本质熵、本质维数与图拓扑量之间的函数关系，通过拟合曲线的方法估计本质维数与本质熵。最常用的有测地最小生成树（GMST）和k-近邻图（k-NNG）。这两种方法均避免了重构流形或估计样本密度。特别地，k-NNG不需估计测地距离，算法复杂度较小，适用于更广泛的本质维数估计应用。

    基于熵图的方法具有坚实的理论基础，计算较稳健；但其计算效率低，尤其对于较大规模的數据集，此问题甚至会对算法可行性造成负面影响。

    2.实验比较

    文章采用高维正弦数据集、10-Mobius带数据集、Swiss roll数据集作为实验数据，选取各类方法的代表算法：基于k-近邻距离的k-k/2近邻法、基于特征值的GPLLE、基于分形维数的填充数法、基于熵图的k-NNG法作为测试算法，分别从估计精度、计算速度、抗噪性进行比较。实验结果如表1所示。

    3.结语

    本文对近年来出现的流形学习中本质维数的估计方法进行了总结，按其内在构造原理大致分为4类：基于k-近邻距离的方法，基于特征值的方法，基于分形维数的方法和基于熵图的方法。通过在典型高维数据集上的实验分析，得出如下结论：①无噪声数据，当要求计算速度时，基于k-近邻距离的方法较优；不要求计算速度时，基于熵图的方法较优；②有噪声数据，当具有噪声先验信息时，基于特征值的方法较优；而无此信息时，基于分形维数的方法最佳。此结论将对高维数据的降维及后续处理具有指导意义。