流形學(xué)習(xí)中的本質(zhì)維數(shù)估計(jì)方法的研究

李春霞　李燕杰　胡瀟涵　張林

摘要：文章旨在將近年來出現(xiàn)的流形學(xué)習(xí)中的本質(zhì)維數(shù)估計(jì)方法進(jìn)行分類，通過在典型數(shù)據(jù)集上的實(shí)驗(yàn)比較，得出針對(duì)不同現(xiàn)實(shí)應(yīng)用的本質(zhì)維數(shù)估計(jì)方法選取策略，將對(duì)高雛數(shù)據(jù)的降雛及后續(xù)處理產(chǎn)生指導(dǎo)意義。

關(guān)鍵詞：本質(zhì)維數(shù)；維數(shù)估計(jì)；流形學(xué)習(xí)

流形學(xué)習(xí)是建立在數(shù)據(jù)分布于高維空間的一個(gè)低維流形的假設(shè)基礎(chǔ)上的，而如何確定該低維流形對(duì)應(yīng)的本質(zhì)維數(shù)是流形學(xué)習(xí)的一個(gè)重要研究方向。本質(zhì)維數(shù)，即描述數(shù)據(jù)集中全部數(shù)據(jù)所需要的自由參數(shù)（或獨(dú)立坐標(biāo)）的最小數(shù)目。可見，將高維數(shù)據(jù)降到它的本質(zhì)維數(shù)坐標(biāo)系，便能提取數(shù)據(jù)的本質(zhì)特征。盡管近年來本質(zhì)維數(shù)估計(jì)引起國(guó)內(nèi)外研究者的廣泛關(guān)注，但目前仍缺少對(duì)如何科學(xué)選取本質(zhì)維數(shù)估計(jì)方法的研究。

1.本質(zhì)維數(shù)估計(jì)方法分類

筆者將近年來出現(xiàn)的數(shù)據(jù)本質(zhì)維數(shù)估計(jì)方法，按照構(gòu)造原理的不同，大致分為4類：基于k-近鄰距離的方法、基于特征值的方法、基于分形維數(shù)的方法和基于熵圖的方法。

1.1基于k-近鄰距離的方法

該類方法利用了k-近鄰距離與鄰域尺寸k間線性關(guān)系中蘊(yùn)涵的本質(zhì)維數(shù)信息，構(gòu)造快速的本質(zhì)維數(shù)估計(jì)方法。

全局方法直接估計(jì)數(shù)據(jù)集的本質(zhì)維數(shù)。此類方法基于rk（x）的密度估計(jì)，利用數(shù)據(jù)與其近鄰間距離的分布信息迭代地估計(jì)數(shù)據(jù)集的本質(zhì)維數(shù)。該算法對(duì)樣本數(shù)目及算法參數(shù)的選擇比較穩(wěn)定，但對(duì)噪聲比較敏感。局部方法則只能直接估計(jì)出各數(shù)據(jù)點(diǎn)的局部本質(zhì)維數(shù)，結(jié)合所有點(diǎn)，求其全局本質(zhì)維數(shù)。提出k-k/2近鄰法，基于數(shù)據(jù)分布在rk（x），rk2（x）內(nèi)的概率與本質(zhì)維數(shù)的關(guān)系進(jìn)行估計(jì)。該算法思想簡(jiǎn)單，快速有效，具有完整的統(tǒng)計(jì)收斂性理論。

基于k-近鄰距離的方法計(jì)算速度較快，但對(duì)于噪聲較敏感，因此需加強(qiáng)算法魯棒性。

1.2基于特征值的方法

該類方法通過分析數(shù)據(jù)的協(xié)方差矩陣的特征結(jié)構(gòu)，描述數(shù)據(jù)所需特征值的最小數(shù)目（本質(zhì)維數(shù)）由協(xié)方差矩陣特征值的重要程度來決定。

全局方法在將數(shù)據(jù)從高維空間映射到低維空間的過程中尋找使映射誤差最小的子空間。例如，主成分分析（PCA）由非零特征值的數(shù)目來估計(jì)本質(zhì)維數(shù)。但它并未考慮數(shù)據(jù)的非線性性質(zhì)，往往過高估計(jì)維數(shù)。鑒于PCA的缺點(diǎn)，文獻(xiàn)提出了基于全局保持的局部線性嵌入（GPLLE）算法，不但保留原始高維數(shù)據(jù)的重要信息，同時(shí)去除噪聲和異常點(diǎn)的影響。

該類方法對(duì)特定分布的數(shù)據(jù)集計(jì)算效果較好，但依賴于特征結(jié)構(gòu)估計(jì)，計(jì)算復(fù)雜度較大。

1.3基于分形維數(shù)的方法

該類方法利用數(shù)據(jù)的分形結(jié)構(gòu)自相似特性近似估計(jì)本質(zhì)維數(shù)。常用方法是通過估計(jì)關(guān)聯(lián)維數(shù)近似表示本質(zhì)維數(shù)，與傳統(tǒng)算法相比，該算法計(jì)算效果顯著，但需充分的先驗(yàn)知識(shí)，而且它所基于的維數(shù)估計(jì)與分布相獨(dú)立的假設(shè)并不總是一致。對(duì)非均勻分布數(shù)據(jù)，關(guān)聯(lián)維數(shù)不能較好近似本質(zhì)維數(shù)，所以文獻(xiàn)通過計(jì)盒維數(shù)來近似估計(jì)本質(zhì)維數(shù)，該算法對(duì)于樣本的不同分布較穩(wěn)定，但計(jì)算復(fù)雜度較高。

基于分形維數(shù)的方法可得到非整數(shù)的維數(shù)，可精細(xì)度量數(shù)據(jù)的復(fù)雜度。但一般需要大量數(shù)據(jù)，且存在尺度r的選擇問題，因此仍存在計(jì)算普適性問題。

1.4基于熵圖的方法

該類方法是基于圖論中的本質(zhì)熵、本質(zhì)維數(shù)與圖拓?fù)淞恐g的函數(shù)關(guān)系，通過擬合曲線的方法估計(jì)本質(zhì)維數(shù)與本質(zhì)熵。最常用的有測(cè)地最小生成樹（GMST）和k-近鄰圖（k-NNG）。這兩種方法均避免了重構(gòu)流形或估計(jì)樣本密度。特別地，k-NNG不需估計(jì)測(cè)地距離，算法復(fù)雜度較小，適用于更廣泛的本質(zhì)維數(shù)估計(jì)應(yīng)用。

基于熵圖的方法具有堅(jiān)實(shí)的理論基礎(chǔ)，計(jì)算較穩(wěn)?。坏溆?jì)算效率低，尤其對(duì)于較大規(guī)模的數(shù)據(jù)集，此問題甚至?xí)?duì)算法可行性造成負(fù)面影響。

2.實(shí)驗(yàn)比較

文章采用高維正弦數(shù)據(jù)集、10-Mobius帶數(shù)據(jù)集、Swiss roll數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，選取各類方法的代表算法：基于k-近鄰距離的k-k/2近鄰法、基于特征值的GPLLE、基于分形維數(shù)的填充數(shù)法、基于熵圖的k-NNG法作為測(cè)試算法，分別從估計(jì)精度、計(jì)算速度、抗噪性進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表1所示。

3.結(jié)語(yǔ)

本文對(duì)近年來出現(xiàn)的流形學(xué)習(xí)中本質(zhì)維數(shù)的估計(jì)方法進(jìn)行了總結(jié)，按其內(nèi)在構(gòu)造原理大致分為4類：基于k-近鄰距離的方法，基于特征值的方法，基于分形維數(shù)的方法和基于熵圖的方法。通過在典型高維數(shù)據(jù)集上的實(shí)驗(yàn)分析，得出如下結(jié)論：①無噪聲數(shù)據(jù)，當(dāng)要求計(jì)算速度時(shí)，基于k-近鄰距離的方法較優(yōu)；不要求計(jì)算速度時(shí)，基于熵圖的方法較優(yōu)；②有噪聲數(shù)據(jù)，當(dāng)具有噪聲先驗(yàn)信息時(shí)，基于特征值的方法較優(yōu)；而無此信息時(shí)，基于分形維數(shù)的方法最佳。此結(jié)論將對(duì)高維數(shù)據(jù)的降維及后續(xù)處理具有指導(dǎo)意義。