機器學習10——降維與度量學習（K近鄰、多維縮放、主成分分析）

上一章：機器學習09——聚類
下一章：機器學習11——特征選擇與稀疏學習
機器學習實戰項目：【從 0 到 1 落地】機器學習實操項目目錄：覆蓋入門到進階，大學生就業 / 競賽必備

文章目錄

- - 一、k近鄰學習（kNN）
  - - （一）基本原理
  - 二、維數災難與降維
  - - （一）維數災難的表現
    - （二）降維的可行性
  - 三、多維縮放（MDS）
  - - （一）核心目標
    - （二）算法步驟
    - （三）擴展
  - 四、主成分分析（PCA）
  - - （一）核心思想
    - （二）算法步驟
    - （三）低維維數 $d^{'}$ 的選擇
    - （四）優勢
  - 五、流形學習
  - - （一）核心概念
    - （二）Isomap算法（典型流形學習方法）
    - （三）應用
  - 六、度量學習
  - - （一）距離度量的擴展
    - （二）學習目標
  - 總結

一、k近鄰學習（kNN）

k近鄰學習是一種簡單的監督學習方法，核心是基于距離度量找到測試樣本的近鄰，通過近鄰的標簽預測結果。

（一）基本原理

核心步驟：
1. 確定訓練樣本和距離度量（如歐氏距離）；
2. 對測試樣本，找到訓練集中距離最近的k個樣本；
3. 分類任務用“投票法”（取k個樣本中最多的類別），回歸任務用“平均法”（取k個樣本輸出的平均值）；也可基于距離加權，近鄰權重更大。
關鍵參數：
- k值：k=1時為最近鄰分類器，k越大模型越簡單（欠擬合風險增加），k越小越容易過擬合；
- 距離度量：不同度量會導致“近鄰”定義不同，直接影響分類結果。
學習類型：
- “懶惰學習”：訓練階段僅存儲樣本，無訓練開銷，測試時才計算距離（如kNN）；
- “急切學習”：訓練階段即學習模型（如SVM、決策樹）。
性能分析：
最近鄰分類器（k=1）的泛化錯誤率不超過貝葉斯最優分類器錯誤率的兩倍，前提是訓練樣本“密采樣”（任意測試樣本附近都有訓練樣本）。

二、維數災難與降維

高維空間中樣本稀疏、距離計算困難的問題稱為“維數災難”，降維是主要解決途徑，核心是將高維數據映射到低維子空間。

（一）維數災難的表現

高維空間中，滿足“密采樣”所需樣本數呈指數增長（如1000個樣本可滿足1維密采樣，20維則需 $10^{60}$ 個樣本）；
距離計算可靠性下降，甚至內積計算都變得困難。

（二）降維的可行性

高維數據往往隱含低維結構（如三維空間中的曲面可嵌入二維），即“低維嵌入”，因此可通過數學變換提取有效低維特征。

三、多維縮放（MDS）

MDS通過保持樣本間的距離，將高維數據映射到低維空間，核心是“距離不變性”。

（一）核心目標

給定高維空間的距離矩陣 $D$ （ $dist_{ij}$ 為樣本 $x_i$ 與 $x_j$ 的距離），找到低維空間表示 $z_i$ ，使 $z_i - z_j\| = dist_{ij}$ 。

（二）算法步驟

計算內積矩陣 $B$ ：通過距離公式推導 $bij=?12(distij2?disti.2?dist.j2+dist..2)b_{ij} = -\frac{1}{2}(dist_{ij}^2 - dist_{i.}^2 - dist_{.j}^2 + dist_{..}^2)$ ，其中 $dist_{i.}^2$ 為第i行距離的均值；
特征值分解：對 $B$ 做特征值分解，取前 $d^{'}$ 個最大特征值及對應特征向量；
低維映射：低維坐標為 $\tilde{\Lambda}^{1/2} \tilde{V}^T$ （ $Λ~\tilde{\Lambda}$ 為前 $d^{'}$ 個特征值構成的對角矩陣， $V~\tilde{V}$ 為對應特征向量）。

（三）擴展

實際應用中可放寬“嚴格距離不變”，僅需低維距離盡可能接近原始距離，以實現有效降維。

四、主成分分析（PCA）

PCA是最常用的線性降維方法，通過尋找數據的主成分（最大方差方向），保留主要信息。

（一）核心思想

最近重構性：樣本到低維超平面的距離最小（重構誤差最小）；
最大可分性：樣本在低維超平面上的投影方差最大，信息保留最多。

（二）算法步驟

中心化：對所有樣本去均值（ $xi←xi?xˉx_i \leftarrow x_i - \bar{x}$ ， $xˉ\bar{x}$ 為樣本均值）；
計算協方差矩陣： $XX^T$ （ $X$ 為中心化后的樣本矩陣）；
特征值分解：對協方差矩陣分解，取前 $d^{'}$ 個最大特征值對應的特征向量構成投影矩陣 $W$ ；
映射：低維坐標為 $z_i = W^T x_i$ 。

（三）低維維數 $d^{'}$ 的選擇

交叉驗證：在不同 $d^{'}$ 下訓練模型（如kNN），選擇性能最優值；
重構閾值：選取最小 $d^{'}$ 使 $∑i=1d′λi∑i=1dλi≥t\frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^d \lambda_i} \geq t$ （ $t$ 為閾值，如0.95）。

（四）優勢

計算簡單，可去噪（最小特征值常對應噪聲，舍棄后提升魯棒性）；
新樣本可直接通過投影矩陣映射到低維空間。

五、流形學習

流形學習假設高維數據分布在低維流形上（局部與歐氏空間同胚），通過局部距離推廣到全局，實現非線性降維。

（一）核心概念

流形：局部與歐氏空間同胚的空間（如球面局部像平面）；
測地線距離：流形上兩點的真實距離（高維空間直線距離可能不反映真實鄰近關系）。

（二）Isomap算法（典型流形學習方法）

構建近鄰圖：對每個樣本，用歐氏距離找k近鄰，近鄰間距離為歐氏距離，非近鄰為無窮大；
計算測地線距離：通過Dijkstra或Floyd算法計算近鄰圖上的最短路徑，作為樣本間真實距離；
MDS降維：將測地線距離作為MDS的輸入，得到低維坐標。

（三）應用

適合可視化（降維至2D/3D），但計算復雜度高， scalability較差。

六、度量學習

度量學習直接學習合適的距離度量，替代歐氏距離，提升近鄰學習等任務的性能。

（一）距離度量的擴展

加權歐氏距離：為不同屬性分配權重 $w_i$ ， $dist^2 = (x_i - x_j)^T W (x_i - x_j)$ （ $W$ 為對角矩陣， $W_{ii}=w_i$ ）；
馬氏距離：用半正定矩陣 $M$ 建模屬性相關性， $dist^2 = (x_i - x_j)^T M (x_i - x_j)$ ， $M$ 為度量矩陣。

（二）學習目標

通過優化任務性能（如kNN分類準確率）學習 $M$ ，若 $M$ 為低秩矩陣，可提取投影矩陣 $P$ 實現降維（ $z = P^T x$ ）。

總結

降維與度量學習通過提取低維有效特征或優化距離度量，緩解維數災難。kNN是簡單的近鄰學習方法，MDS和PCA是經典線性降維方法，流形學習適用于非線性數據，度量學習則直接優化距離以提升任務性能。實際應用中需根據數據特性選擇方法（線性/非線性、可解釋性要求等）。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/96251.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/96251.shtml
英文地址，請注明出處：http://en.pswp.cn/web/96251.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！