維數災難

維數災難(Curse of Dimensionality)：通常是指在涉及到向量的計算的問題中，隨著維數的增加，計算量呈指數倍增長的一種現象。維數災難涉及數字分析、抽樣、組合、機器學習、數據挖掘和資料庫等諸多領域。

基本介紹

• 中文名：維數災難
• 外文名：Curse of Dimensionality
• 定義：計算量呈指數倍增長的一種現象
• 適用範圍：動態規劃，模式識別

背景

維數災難最早是由理察·貝爾曼（Richard E. Bellman）在考慮最佳化問題時提出來的，它用來描述當(數學)空間維度增加時，分析和組織高維空間(通常有成百上千維)中的數據，因體積指數增加而遇到各種問題場景。

該名詞涉及數字分析、抽樣、組合、機器學習、數據挖掘和資料庫等諸多領域。 在這些領域中，該名詞代表的共同特點是：當維度增加時，空間的體積增加得很快，使得可用的數據變得稀疏。稀疏性對於任何要求有統計學意義的方法而言都是一個問題，為了獲得在統計學上正確並且有可靠的結果，用來支撐這一結果所需要的數據量通常隨著維數的提高而呈指數級增長。而且，在組織和搜尋數據時也有賴於檢測對象區域，這些區域中的對象通過相似度屬性而形成分組。然而在高維空間中，所有的數據都很稀疏，從很多角度看都不相似，因而平常使用的數據組織策略變得極其低效。

“維數災難”通常是用來作為不要處理高維數據的無力藉口。然而，學術界一直都對其有興趣，而且在繼續研究。另一方面，也由於本徵維度的存在，其概念是指任意低維數據空間可簡單地通過增加空餘或隨機維將其轉換至更高維空間中，相反地，許多高維空間中的數據集也可降維至低維空間數據，而不必丟失重要信息。當前的研究也表明除非其中存在太多不相關的維度，帶有維數災難特色的數據集依然可以處理，因為相關維度實際上可使得許多問題(如聚類分析)變得更加容易。

涉及領域

組合學

在一些問題中，每個變數都可取一系列離散值中的一個，或者可能值的範圍被劃分為有限個可能性。把這些變數放在一起，則必須考慮很多種值的組合方式，這後果就是常說的組合爆炸。即使在最簡單的二元變數例子中，可能產生的組合總數就已經是在維數上呈現指數級的 。一般而言，每個額外的維度都需要成倍地增加嘗試所有組合方式的影響。

採樣

當在數學空間上額外增加一個維度時，其體積會呈指數級的增長。如，點間距離不超過 ， 個均勻間距的樣本點足夠採樣到一個單元區間（“一個維度的立方體”）；一個10維單元超立方體的等價採樣，其相鄰兩點間的距離為 ，則需要 個樣本點。一般而言，點距為 的10維超立方體所需要的樣本點數量，是1維超立方體這樣的單元區間的 倍。

在上面的n=2的例子中：當樣本距離為0.01時，10維超立方體所需要的樣本點數量會比單元區間多 倍。這一影響就是上面所述組合學問題中的組合結果。

機器學習

在機器學習問題中，需要在高維特徵空間(每個特徵都能夠取一系列可能值)的有限數據樣本中學習一種“自然狀態”（可能是無窮分布），要求有相當數量的訓練數據含有一些樣本組合。給定固定數量的訓練樣本，其預測能力隨著維度的增加而減小。

貝葉斯統計

在貝葉斯統計中維數災難通常是一個難點，因為其後驗分布通常都包含著許多參數。

然而，這一問題在基於模擬的貝葉斯推理（尤其是適應於很多實踐問題的馬爾科夫蒙特卡洛方法）出現後得到極大地克服。當然，基於模擬的方法收斂很慢，因此這也並不是解決高維問題的靈丹妙藥。

距離函式

一種用來描述高維歐幾里德空間的巨型性的方法是將超球體中半徑 和維數 的比例，和超立方體中邊長 和等值維數的比例相比較。 這樣一個球體的體積計算如下：

立方體的體積計算如下：

隨著空間維度 的增加，相對於超立方體的體積來說，超球體的體積就變得微不足道了。這一點可以從當 趨於無窮時比較前面的比例清楚地看出

在某種意義上，幾乎所有的高維空間都遠離其中心。給定一個單一分布，由於其最小值和最大值與最小值相比收斂於0，即 。因此，其最小值和最大值的距離變得不可辨別。

這通常被引證為距離函式在高維環境下失去其意義的例子。

最近鄰查詢

最近鄰查詢是區別於點的定位查詢和範圍查詢的另一查詢類型，人們的研究興趣尤其是在高維空間，比如一些視頻、圖像、形狀等數據。目前已有很多的最近鄰查詢方法被不斷提出來，但是在高維情況下(比如 20 維)，這些方法查詢性能還不如對整個數據集合進行順序檢索性能好，甚至在10維就開始急劇惡化，人們稱這種現象為維數災難。

可以證明，當維數趨於極限值時，查詢點到數據集中所有點的距離都相等，此時最近鄰已經沒有意義，也稱為最近鄰查詢的不穩定性。

動態規劃

動態規劃問題的維數即指的是各階段上狀態變數的維數。當狀態變數的維數增加時，動態規劃問題的計算量會呈指數倍增長，限制了人們用動態規劃研究問題和解決問題的能力。

解決動態規劃中的維數災難的思想：降維，即通過一些特殊技巧或算法把一個高維的動態規劃問題逐步分解為一些低維的動態規劃問題，以此來減輕維數災難。

模式識別

根據模式識別理論，低維空間線性不可分的模式通過非線性映射到高維特徵空間則可能實現線性可分，但是如果直接採用這種技術在高維空間進行分類或回歸，則存在確定非線性映射函式的形式和參數、特徵空間維數等問題，而最大的障礙則是在高維特徵空間運算時存在的“維數災難”。即維數越高，計算量越大。

解決方法：採用核函式技術可以有效地解決“維數災難”。

現有降維方法

綜述

降維是通過將數據點映射到更低維的空間上以尋求數據的緊湊表示的一種技術，這種低維空間的緊湊表示將
有利於對數據的進一步處理。根據如何從原始特徵中得到新的特徵, 降維可分為特徵選擇和特徵抽取兩種。前者尋找原始特 征的一個子集來表達數據，後者則是尋找數據的新的低維特徵，而這些新的特徵不僅僅局限於原始特徵的子集。

特徵抽取

基於低維投影的降維：主要包括主成分分析( Principal Component Analysis, PCA) 方法和投影尋蹤 ( Projection Pursuit,PP) 方法

基於神經網路的降維：主要包括自動編碼網路、自組織映射網路和生成建模
基於數據間相似度的降維：主要包括多維尺度、隨機鄰居嵌入、Isomap、局部線性嵌入和拉普拉斯特徵映射
基於分形的降維

特徵選擇

主要分為三大類：一類屬於“過濾”的(filter)方法，另一類屬於“包裹”的方法，還有通過範數進行特徵選擇的方法。