導讀
由於編輯器不支援公式編輯，公式較多的地方，用截圖代替。
高維空間中的球體
人類生活在三維空間，大腦的直覺也以三維空間為參考系建立，到了高維空間這種直覺就不再起作用，甚至在潛意識裡形成誤導。回到導讀中的高維球體的問題，我們將其轉化為如下形式。
從上述例子中可以得到如下推論：
在高維空間中，假如樣本在空間中是均勻分佈的，那麼絕大多數的樣本都稀疏地分佈在球的表面附近。
高維空間中的區域性方法
假設在特徵空間中，基於目標點區域性的觀測，可以很好地預測出目標點的特性，此類方法稱為區域性方法。典型的區域性方法有近鄰方法和核方法，這兩種方法在高維空間中都會遇到問題。
近鄰方法（kNN：knearest neighbors）
該方法的思想是：對樣本空間中一個新的輸入x（稱為目標點）進行預測時，先找到空間中距x最近的k個已知樣本（稱為k個近鄰），並用這k個樣本對應的輸出來產生預測結果。如果是分類問題，就進行多數投票；如果是迴歸問題，就對k個輸出進行平均。
上述邏輯似乎無懈可擊，因為即便是高維空間也總能找到離目標點最近的k個樣本吧？但其實kNN有一個容易被忽略的隱含假設，即k個最近的樣本離目標點都不能太遠。在低維空間中，這是很容易滿足的；但在高維空間卻並非如此。結合上面高維空間中球體的例子，來考慮下面的問題。
核方法
與近鄰方法相對應的，是核方法。核方法是在目標點周圍先選擇一個半徑固定的鄰域，鄰域裡有幾個樣本算幾個樣本，用來估計目標點的值。顯然，核方法在高維空間中遇到的問題是，在目標點的鄰域裡可能根本找不到樣本點，因此無法做出有效估計。
高維空間的劃分
有一些機器學習演算法，有賴於對空間的劃分。其主要思想是先將整個輸入空間劃分為足夠小的子空間，小到每個子空間裡的模式都足夠簡單，這樣就可以在區域性進行簡單建模。以決策樹為例，它透過自上而下的二分過程，將整個輸入空間（或特徵空間）劃分為一系列的小區間（樹的葉子節點），然後在這些小區間上直接用常量建模。另外一個例子是非引數密度估計，下面以此為例進行詳細介紹。
非引數密度估計
假設，我們要對下圖中某一個位置的點進行分類預測，判斷其顏色。
非引數密度估計的想法很簡單，首先將整個區間劃分為如圖的16個小區間，在每個小區間中屬於某種顏色的機率用頻率來代替。那麼對於圖中畫×的點，預測如下：
最後會預測為紅色。
這種方法的問題在於，隨著空間維度的增加，子區間的個數指數增加。必須確保子區間中有樣本點才能進行預測，那麼需要的樣本點也會指數增加。用圖示例如下：
基於空間劃分的方法，本質上是把整體模式的複雜性轉移到了空間劃分的複雜性上。因為指數是爆炸增長的，所需樣本點的個數也會成爆炸趨勢，且不說實際根本沒有足夠多的樣本，即便有了這些樣本，樣本的儲存也是個問題。因此，這種在低維空間中很樸素很好用的方法，在高維空間中就形成了災難。
高維空間中的基函式方法
還記得函式的taylor展開式嗎？這說明只要函式在某一點的各階導數存在，就可以在該點附近用一組多項式函式來近似表達原函式。這種情況下，多項式函式就形成了一組基函式。類似的，傅立葉級數則是用三角函式來作為基。
從函式擬合的角度來理解機器學習模型，自然就有了機器學習中的基函式方法。我們在此以多項式基函式為例，說明基函式方法在高維空間中應用的困難。
多項式基函式方法
總結
從上面的這些例子可以看出，我們在低維空間中建立的很多直覺，無法直接類推到高維空間。而在機器學習領域，高維特徵是相當常見的。隨著特徵空間維度的增加，樣本空間分佈的稀疏程度、模型的複雜度和演算法的計算量一般都會指數增長，這給機器學習領域的取樣、計算和儲存都帶來了很大的困難，我們稱之為“維度災難”。
如何理解維度災難的本質呢？假設平均每個特徵維度的變數，平均可以取N種不同的值（對連續值的情況，對應該維度上空間的N個劃分），那麼D個維度變數組合的結果就是N的D次方。這個組合數是呈指數增長的，這種現象被稱為“組合爆炸”。也就是說，在特徵空間中每增加一個維度，都需要在先前的基礎上成倍地增加嘗試所有組合方式對結果的影響。組合爆炸之時，也就形成了災難。
對於高維空間給機器學習帶來的這些“災難性”的後果，我們又該如何應對呢？一般可以考慮以下思路：
降維：如果不同維度之間存線上性相關的關係，或者資料集在某些維度上相對於另外的維度方差很小，可以用PCA或LDA等方法先進行降維，然後轉化到低維空間再進行處理。
最佳化計算：雖然空間維度理論上帶來計算量的指數增長，但通常可以利用模型的實際特性來最佳化計算。比如，變數的對稱性（如FM：Factorization Machine），或空間距離的三角不等式（如kNN）等。
選擇更適用於高維空間的方法：比如，同樣是基函式方法，不同於多項式基函式的是，MARS（Multivariate Adaptive Regression Splines）使用分段線性的基函式，可以將基函式的數量降低到2N*D（N為樣本數量，D為特徵空間維度）。
參考文獻
《The Elements of Statistical Learning: Data Mining, Inference, and Prediction》，Second Edition，Jerome Friedman
《Pattern Recognition and Machine Learning》，Bishop