3.3 數據降維

3.3.1 基本思想與方法

當嘗試使用機器學習解決實際問題時，遇到的最大問題往往不是算法上的問題，而是數據上的問題。有時會苦惱于沒有數據，而有時又會因為數據太多而陷入“幸福”的困擾。

在前文學習算法時，可以看到許多算法都涉及距離計算，而高維空間會給距離計算帶來很大的麻煩。實際上，在高維空間中出現的數據樣本稀疏、距離計算困難等問題是所有機器學習方法共同面臨的問題，被稱為“維度災難”“維度詛咒”“維度危機”等。尤其是當高維空間數據計算過于復雜或擬合困難時，就需要考慮通過降維的方式降低計算難度，降低算法模型的擬合成本。

1.基本思想

在機器學習領域中的降維是指采用某種映射方法，將原高維空間中的數據映射到低維空間中。降維的本質是學習一個映射函數，如式（3-8）所示。

其中x是原始數據點的表達，y是數據點映射后的低維向量表達，通常y的維度小于x的維度。若y的維度大于x的維度，則稱為升維。f可能是顯式或隱式、線性或非線性的降維方式。

數據降維的目的從直觀上是算法處理的維度降低了，便于計算和可視化，但更深層次的意義在于實現了有效信息的提取，減少了無用信息對算法的干擾。目前，大部分降維算法處理的數據都是向量，也有一些降維算法處理的是高階張量。

2.降維方法

降維方法可以進一步細分為變量選擇和特征提取兩類方式。變量選擇是指通過不同的方法選擇合適的數據變量；特征提取則是通過線性方式或非線性方式完成特征的提取，如圖3-6所示。

3.3.2 變量選擇

變量選擇的前提是數據中含有大量冗余或無關變量（或稱特征、屬性、指標等），旨在從原有變量中找出主要變量，這些方法包括丟失值比例、低方差過濾等。

1.丟失值比例（Missing Value Ratio）

前文曾介紹過多種補齊缺失值的方法，但是當缺失值在數據集中的占比過高時，則可以設置一個閾值，如果缺失值占比高于閾值，則刪除它所在的列。

2.低方差過濾（Low Variance Filter）

如果數據中的某些數據值非常相近，則其對算法的價值可能并不是特別大。低方差過濾可以計算樣本中每個特征值所對應的方差，如果低于閾值，則進行過濾。

3.高相關過濾（High Correlation Filter）

如果兩個變量之間具有相似的趨勢并且可能攜帶類似的信息，則表明它們具有高相關性。這類變量的存在會降低某些算法的性能。例如，在線性模型或邏輯回歸中計算獨立數值變量之間的相關性，如果相關系數超過某個閾值，則刪除其中一個變量，當然，應盡可能保留與目標變量相關的變量。

4.隨機森林（Random Forest）

隨機森林是一種使用非常廣泛的變量選擇方法，通過隨機森林可自動計算出各個變量特征的重要性，篩選出較小的特征子集。隨機森林具有較高的準確性，既能處理離散數據，也能處理連續數據。

5.反向特征消去（Backward Feature Elimination）

反向特征消去是從效果的角度反向消除特征。例如，對于含有K個特征變量的數據集，首先對K個特征變量進行模型生成，然后逐一移除其中一個特征，對剩余K-1個特征變量進行模型生成，接著對原始模型和移除其中一個特征變量的模型效果進行比對，最后把對模型性能影響較小的變量移除。

6.前向特征選擇（Forward Feature Selection）

前向特征選擇與反向特征消去的過程相反，前向特征選擇是找到對模型性能影響最大的特征，然后逐步新增特征訓練模型。首先對每一個特征變量進行模型訓練，得到K個模型；然后選擇K個模型中性能最好的特征變量作為初始變量，把其余變量作為與該變量的一對一組合，進行模型訓練；接著選擇效果最好的一組特征變量作為下一輪的初始變量，依次迭代上述過程，直到模型性能無法再提升。

前向特征選擇和反向特征消去的計算量較大、耗時較久，因此只適用輸入變量較少的數據集。

3.3.3 特征提取

特征提取可以看作變量選擇方法的一般化。特征選擇是去掉無關特征，保留相關特征的過程，或是從所有的特征中選擇一個最好的特征子集的過程。

特征提取則是將機器學習算法不能識別的原始數據轉換為算法可以識別的特征的過程。例如，組合不同的特征變量可以得到新的特征變量，改變原有的數據特征空間。典型的特征提取方式有線性和非線性兩種，如圖3-7所示。

線性

1.主成分分析

主成分分析（Principal Component Analysis, PCA）是常用的線性降維方法，通過正交變換將原始的N維數據集映射到一個主成分數據中，即把高維空間中的數據映射到低維空間，并在投影維度上使數據的方差盡可能大，從而減少數據維度，同時盡可能保留原始數據的特性，如圖3-8所示。

在圖3-8中，相關變量x₁、x₂、x₃、x₄映射到了兩個無關的成分變量pc₁和pc₂上。下面用一個實例介紹主成分分析的步驟和方法，假設有10組二維特征數據，如表3-2所示。

通過繪制二維坐標可知，10個樣本數據基本處于比較雜亂的狀態，很難通過簡單的方式進行降維，如圖3-9所示。

（1）對樣本數據求均值，并進行去均值處理。x的均值為2.199，y的均值為2.253，通過及，重新映射坐標位置得到的結果如圖3-10所示。可以發現，均值處理并未改變相對大小和結構，只是中心位移了。

（2）計算協方差矩陣。協方差公式為，由于本例的特征為x和y，因此協方差矩陣是一個2×2的矩陣，即

計算得到的協方差矩陣為（（0.74261 0.28652556））（（0.28652556 0.42833444））。

（3）計算協方差矩陣的特征值和特征向量，將特征向量繪制到圖中，如圖3-11所示。

特征向量之間是正交的，主成分分析正是利用特征向量這個特點構建了新的空間體系，將原始數據乘以特征向量，得到的空間體系如圖3-12所示。其中，“+”是通過坐標變換之后得到的新點，即每一個原始數據點投影到特征向量的結果。

（4）選擇主成分。根據特征值的大小，從大到小選擇K個特征值對應的特征向量，例如，本例排序后的特征值和特征向量如表3-3所示。

由于選擇的是K個特征向量，而本例中僅有兩個特征，因此選擇K=1，即選擇其中最大的特征值及對應的特征向量。

（5）生成降維數據。將原始數據乘以上一步篩選出的特征向量組成特征矩陣之后，即可得到新的降維數據。例如，本例得到的結果如表3-4所示，z即為從x和y映射的新特征。

如果把z可視化到二維坐標系中，固定其另外一維的值為1.0，則效果如圖3-13所示，從二維的小圓點數據映射到一維的小菱形數據。

至此，主成分分析完成了利用少數幾個綜合變量來代替原始多個變量的過程，也可以看出主成分分析的數據不需要數據滿足特定分布（例如正態分布）。

2.因子分析

因子分析（Factor Analysis）可以理解為是主成分分析的一種改進。因子分析基于原始變量相關矩陣內部的依賴關系，把一些關系錯綜復雜的變量歸結為少數幾個綜合因子，實質則是從多個變量中提取共性因子，并得到最優解的過程。

在因子分析過程中，將變量按照相關性進行分組，組內的相關性足夠高，組間的相關性相對較低，每個組即為因子。由于根據相關性進行了分組，每個組又包含了多個變量，因此因子的數量小于原始變量的數量，從而達到降維的目的。例如，針對學生的各科學習成績的因子分析，若單科成績優異的學生，其他科目的成績也不差，則抽取的共性因子為學習能力或學習方法。

相較于主成分分析，因子分析是把變量表示成各因子的線性組合，而在主成分分析中，則是把主成分表示成各個變量的線性組合。

與主成分分析、因子分析類似的特征提取方式有線性判別分析（Linear Discriminant Analysis）、獨立成分分析（Independent Components Analysis, ICA）等，它們都是通過線性變換的方式完成對數據的降維的。

非線性

前面介紹的是線性降維處理方式，對于非線性降維處理方式，常用的是基于流形學習的方法。

流形是幾何中的一個概念，表示在高維空間中的幾何結構，它是由空間中的點構成的集合，可以將流形理解成二維空間的曲線。例如，三維空間中的一個流形如圖3-14所示，它實際上是一個二維數據的卷曲面。

流形學習的關鍵是假設觀察的數據實際上是由一個低維流形映射到高維空間上的，流行學習的基本方法有多維尺度縮放、等距特征映射、局部線性嵌入等。

1.多維尺度縮放

多維尺度縮放（Multidimensional Scaling, MDS）是一種比較經典的降維方法，它的核心思想是，高維空間的距離狀態在低維空間中保持不變。由于距離計算對于數據的維度并沒有直接依賴關系，因此保持距離狀態不變也就保持了在低維空間中的相對距離。

對圖3-14所示的流形進行多維尺度縮放，由三維降到二維的效果如圖3-15所示。

多維尺度縮放不需要先驗知識即可進行計算，整個過程相對比較簡單，且保留了原始數據的相對關系，能夠較好地可視化。但是，多維尺度縮放在計算過程中認為各個維度對于結果的影響是相同的，然而事實上可能存在部分維度貢獻度不同的情況。

2.等距特征映射

等距特征映射（Isometric Feature Mapping, ISOMAP）是被廣泛使用的低維嵌入方法之一，等距特征映射建立在多維尺度縮放的基礎上，兩者的原理基本相同。等距特征映射試圖保留數據原有的幾何形狀，最大的差異在于它采用最短路徑距離替代了多維尺度縮放中的歐氏距離，這種最短路徑距離采用測地線距離（曲線距離）作為空間中的兩點距離，可以更好地擬合流形中的數據。

等距特征映射的計算過程分為三步。

① 為每個樣本點確定鄰居，確定鄰居的方法可以采用KNN的方式或將半徑閾值以內的作為鄰居，因此可以形成一個加權圖，邊上的權重即為兩點的空間距離。

② 對于圖中的任意兩點，計算最短路徑，可以采用Dijkstra算法計算最短路徑；

③ 把計算出的最短路徑作為多維尺度縮放的輸入，進行降維。

等距特征映射變換得到的低維空間中較好地保留了數據的本質特征，能夠較好地處理非線性數據，屬于非迭代的全局優化算法。

3.局部線性嵌入

局部線性嵌入（Locally Linear Embedding, LLE）是比較重要的非線性降維方法之一，局部線性嵌入在降維時保持了局部線性特征，因此被稱作局部線性特征。

局部線性嵌入表示數據在較小的范圍內是保持線性關系的，某個變量可以由其附近的若干個樣本線性表示。例如，變量x₁附近的變量x₂、x₃、x₄可以表示為式（3-9）所示的線性形式。

通過局部線性嵌入降維之后，每一個變量x_i的投影為，應盡可能保持w₁₂、w₁₃、w₁₄在有限范圍內變化的同時滿足式（3-10）。

即在變量附近依然產生線性關系，距離觀測樣本x₁較遠的其他樣本對局部線性嵌入不產生任何影響。

局部線性嵌入的步驟主要有三步：

① 對樣本求K近鄰樣本，和KNN算法流程一致，樣本數量K需要提前設定，表示用多少樣本表示單個樣本；

② 對每個樣本求其K近鄰樣本的線性組合，計算線性關系的權重系數；

③ 利用線性關系的權重系數在低維空間中重構樣本，完成降維。

局部線性嵌入與計算機圖形中的局部視覺感知有一定相似之處，因此局部線性嵌入被廣泛應用在圖形圖像領域。

局部線性嵌入可以學習任意維度的局部線性的低維流形，整個算法可以歸納為對稀疏矩陣進行特征分解。由于局部線性特征及KNN算法本身的缺陷限定了局部線性嵌入對數據的處理，因此在處理閉合的流形、稀疏的數據樣本或分布不均的樣本時效果相對較差。