第3章
降維——非線性方法
本章涉及許多非線性的降維方法，這裡的非線性體現在高維空間與低維空間之間的映射關繫為非線性。首先介紹多維尺度分析，該方法已經被廣泛應用。接著介紹一些近年來提出的非線性降維方法，包括局部線性嵌入、等距特征映射以及海森特征映射。*後對機器學習當中的一些降維方法進行討論，例如自組織映射、生成式拓撲映射以及曲元分析。
3.1多維尺度分析——MDS
多維尺度分析(MDS)是用於分析測量物體的數據集合之間鄰近性的一組方法，它可以揭示出數據集內在的隱藏結構。MDS算法的目的是為原始數據集合尋找一個低維結構，並且滿足在此低維結構中數據點之間的距離不失真。這就意味著，高維空間中較近的點在低維空間中也較近。MDS算法*初是由社會科學研究者提出的，如今在很多統計軟件包中都有該算法，包括MATLAB統計工具箱。
在介紹不同的MDS［Cox和Cox,2001］方法之前，首先介紹一些相關的定義和符號。如前面所述，假設數據集合包含n個觀測點。MDS算法首先測量出鄰近性，用以衡量物體之間的距離或者相似度。鄰近性包含兩種類型： 相似性和相異性。定義符號δrs用於衡量物體r和s之間的相異性，Srs用於衡量相似性。對於大多數情況下，滿足：
δrs≥0，δrr=0
和
0≤srs≤1，srr=1
因此，從δrs的滿足條件可以看出，δrs越小則觀測點離得越近； 對於相似性測量Srs而言，值越大則離得越近。這兩種鄰近性的測量可以很容易地相互轉換(詳見附錄A)。因此在本章後續部分，都假設采用相異性作為鄰近性測量。同時，物體間相異性可采用矩陣的形式表示，記為Δ。大多數情況下，相異性矩陣都是一個n×n的對角陣(有些情況下，用下三角矩陣或者上三角矩陣的形式給出)。
定義drs為低維空間中觀測點r和s之間的距離。在MDS的文獻中，定義X為低維空間中坐標值矩陣。值得注意的是，此處可能與之前定義的X（表示具有n個p維觀測點的原始數據集合）相混淆。
在MDS中，通常從研究相異性矩陣Δ入手，而不是直接研究原始數據。事實上，在MDS的初始公式中，對不同類對像進行定性判斷時，原始的p維空間的觀測點並無意義。歸納而言，MDS首先研究相異性矩陣Δ，*終得到d維雖然符號d既用於表示低維空間維數(d
MDS有許多不同算法，通常把這些方法分為度量MDS和非度量MDS這兩大類。這兩種不同類別的方法的主要區分在於相異性δrs轉換成低維空間距離drs的方式不同。度量MDS假設δrs與drs之間的關繫滿足式(3.1)。
drs≈f(δrs)(3.1)
其中f為連續單調函數，它的函數形式決定了MDS的模型。例如，f的形式可能如式(3.2)所示：
f(δrs)=bδrs(3.2)
式(3.2)定義的映射稱為比例MDS［Borg和Groenen,1997］。另一種MDS稱之為間隔MDS，其定義為：
f(δrs) = a+bδrs
其中a、b為自由參數。其他形式的f可能會包含高階多項式、指數或者對數函數。
非度量MDS放松了f(·)的度量特性，但規定保留相異性的次序。其變換函數或者尺度函數必須滿足單調性的約束:
δrs<δabf(δrs)≤f(δab)
由於這個約束性的存在，非度量MDS也被稱為順序MDS。
3.1.1度量MDS
大多數的度量MDS都是尋找一個滿足式(3.1)的映射變換，這一過程通常是定義一個目標函數，並對其進行優化。其中一種目標函數可以通過f(δrs)與drs之間的均方差來定義，如式(3.3)所示。
s(drs)=∑r∑s［f(δrs)-drs］2尺度因子(3.3)
一般而言，稱式(3.3)為壓力。分母中不同的尺度因子會形成不同形式的壓力以及不同類型的MDS算法。式(3.3)中分母的尺度因子通常采用如下形式：
∑r∑s(drs)2
在這種情況下，我們稱該表達式為“壓力-1”［Kruskal,1964a］。
因此，在MDS算法中，我們利用f函數對相異性矩陣進行縮放，從而找到對應的d維空間的點分布。通過*小化壓力，計算出距離d。這一過程可以通過數值的方法進行實現(例如梯度法或*速下降法)。這些方法通常都是迭代進行且不一定能保證收斂到全局*優解。下面首先介紹一種封閉解的情況，然後在後續章節中對這部分進行細節擴展。
通常在文獻中出現的多維尺度分析是指經典MDS，然而度量MDS包含多種方法，例如*小二乘尺度分析等［Cox和Cox,2001］。下面首先介紹一種基於損失函數*優化的經典MDS方法。
