流形學習中的本質維數估計方法的研究

李春霞　李燕杰　胡瀟涵　張林

摘要：文章旨在將近年來出現的流形學習中的本質維數估計方法進行分類，通過在典型數據集上的實驗比較，得出針對不同現實應用的本質維數估計方法選取策略，將對高雛數據的降雛及后續處理產生指導意義。

關鍵詞：本質維數；維數估計；流形學習

流形學習是建立在數據分布于高維空間的一個低維流形的假設基礎上的，而如何確定該低維流形對應的本質維數是流形學習的一個重要研究方向。本質維數，即描述數據集中全部數據所需要的自由參數（或獨立坐標）的最小數目。可見，將高維數據降到它的本質維數坐標系，便能提取數據的本質特征。盡管近年來本質維數估計引起國內外研究者的廣泛關注，但目前仍缺少對如何科學選取本質維數估計方法的研究。

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-近鄰距離的方法較優；不要求計算速度時，基于熵圖的方法較優；②有噪聲數據，當具有噪聲先驗信息時，基于特征值的方法較優；而無此信息時，基于分形維數的方法最佳。此結論將對高維數據的降維及后續處理具有指導意義。