1 前言

??將高維數(shù)據(jù)點(diǎn)以可視化的方式呈現(xiàn)出來是探索式數(shù)據(jù)分析的一個(gè)重要研究課題,例如對于多張64*64的像素圖肢础，將每張圖轉(zhuǎn)化為行向量后可以表示為4096維空間中的數(shù)據(jù)點(diǎn)闷串，如果能將這些數(shù)據(jù)點(diǎn)可視化到平面視圖中, 并在某種程度上保留數(shù)據(jù)點(diǎn)間的分布規(guī)律待牵，就能以人類可感知的方式探索原始圖像集背后隱藏的規(guī)律馒过。各個(gè)學(xué)科領(lǐng)域采集的數(shù)據(jù)如全球氣候數(shù)據(jù)坚俗、人類基因分布禽作、金融統(tǒng)計(jì)等經(jīng)常呈現(xiàn)出高維的特征,所以研究高維數(shù)據(jù)的可視化方法具有極大的現(xiàn)實(shí)意義尸昧。
??由于人類肉眼僅限于感知二/三維空間中的幾何圖形，所以高維數(shù)據(jù)點(diǎn)只有以二/三維的視覺元素表達(dá)后才能使人直觀的觀測數(shù)據(jù)分布的規(guī)律旷偿。在二維平面上可視化超過兩個(gè)維度的方法有很多烹俗，比如散點(diǎn)圖矩陣,平行坐標(biāo),Andrew曲線,星形圖等，這些方法面對高維數(shù)據(jù)時(shí)也會(huì)產(chǎn)生視覺混淆的問題萍程。降維算法是利用線性或者非線性變換將高維觀測空間中的數(shù)據(jù)投影到一個(gè)有意義的低維空間中幢妄，同時(shí)盡量保持?jǐn)?shù)據(jù)的內(nèi)在結(jié)構(gòu)不被改變，進(jìn)而獲取數(shù)據(jù)集內(nèi)在特征的低維表示茫负。

圖1.1(a)5維的平行坐標(biāo)圖	圖1.1(b)高維的平行坐標(biāo)圖

2 降維方法

??針對不同目的所使用的降維方法有所不同蕉鸳，比如特征工程是利用專家的知識(shí)和經(jīng)驗(yàn)進(jìn)行特征抽取和組合以達(dá)到降低運(yùn)算復(fù)雜度的目的，而針對可視化呈現(xiàn)效果我們對不同的降維技術(shù)又有不同的評估標(biāo)準(zhǔn)忍法。
??通常針對可視化的降維問題的形式化表述如下：

??令觀測數(shù)據(jù)集 $X = \{ x_{1},x_{2},...,x_{N} \}$ , 由 $N$ 個(gè) $D$ 維數(shù)據(jù) $x_{i} = \{ x_{i_{1}},x_{i_{2}},...,x_{i_{D}} \}\in R^{D}$ 構(gòu)成潮尝。
??令 $\delta _{D}:R_{D} \times R_{D} \to R$ 和 $\delta _gow5sbe:R_un5z5ft \times R_kdpa5ag \to R$ 分別為高維空間 $R^{D}$ 和低維嵌入空間 $R^tq2n97c$ 的相似度度量函數(shù)榕吼。
??數(shù)據(jù)降維可以定義為 $D$ 維數(shù)據(jù) $x_{i}$ 到 $d$ 維數(shù)據(jù) $y_{i}$ 的映射：
$\Phi: R_{D} \to R_jgv7ri5 ,d \ll D\\ x_{i} \mapsto y_{i}, i = 1,2,...,N\\ x_{i} \in X,y_{i} \in Y$
??使得 $\delta _{D}(x_{i},x_{j}) \approx \delta _{D}(y_{i},y_{j}), i,j = 1,2,...,N$

??該映射要使在高維空間中相距較近的點(diǎn)在低維空間中也應(yīng)較近，在高維空間中相距較遠(yuǎn)的點(diǎn)在低維空間中也應(yīng)較遠(yuǎn)衍锚。使高維數(shù)據(jù)點(diǎn)集嵌入到低維空間后盡量還原其整體和局部的拓?fù)浣Y(jié)構(gòu)友题。根據(jù)映射 $\Phi$ 的性質(zhì)，降維可分為線性的和非線性的戴质。

2.1 線性降維

??線性降維方法將高維數(shù)據(jù)集通過線性映射到低維空間度宦，最常見的線性降維算法有PCA(Principal Component Analysis)，MDS(Classical Multidimensional Scaling),等告匠。
??以PCA為例戈抄，通過尋找一組線性向量基，將數(shù)據(jù)映射到其均方誤差失真最小的低維線性空間中并盡量保持高維數(shù)據(jù)集對方差貢獻(xiàn)最大的特征后专。具地地划鸽，對于高維數(shù)據(jù)集 $X$ ，PCA通過將 $cov(X)$ (數(shù)據(jù)集 $X$ 的方差矩陣)進(jìn)行特征值分解戚哎，取前幾個(gè)較大的特征值對應(yīng)的特征向量組成的線性映射矩陣 $M$ 裸诽，也就是最大化 $M^{T}Cov(X)M$ 的線性映射矩陣 $M$ ， $M$ 的行數(shù)就是最終低維空間的維度型凳，通過這種映射方法丈冬，低維空間中的數(shù)據(jù)集將盡量保留最大的信息量(方差),從而達(dá)到壓縮原始數(shù)據(jù)的維度的目的。
??與PCA相似甘畅，MDS(Classical)方法求取的映射也是線性的,不同的是MDS(Classical)算法是從數(shù)據(jù)點(diǎn)對之間的相似性矩陣出發(fā)來構(gòu)造合適的低維空間中的點(diǎn)集埂蕊，使得數(shù)據(jù)的內(nèi)在線性結(jié)構(gòu)在低維空間中得以保持，相似度一般用歐氏距離來衡量疏唾。
??上述方法蓄氧，由于映射方法是線性的，將高維空間中局部存在的線性結(jié)構(gòu)可視化后還能還原其結(jié)構(gòu)槐脏，但對相距較遠(yuǎn)的點(diǎn)之間非線性的關(guān)系映射到低維空間后則會(huì)失真喉童。比如我們將PCA方法應(yīng)用到兩類不同的三維數(shù)據(jù)集。

圖2.1(a)Corner-Plane數(shù)據(jù)集	圖2.1(b)Corner-Plane的PCA降維結(jié)果
圖2.1(c)Swiss-roll數(shù)據(jù)集	圖2.1(d)Swiss-roll的PCA降維結(jié)果

??圖2.1(c)和2.1(d)揭示了對于高維空間中的低維流形准给，更重要的是將那些高維空間中緊密靠近的點(diǎn)集在低維空間中形成聚類效果泄朴，比如圖c三維空間中所有藍(lán)色的點(diǎn)，而對于藍(lán)色和黃色的點(diǎn)在二維平面中則應(yīng)該更加的分散露氮。PCA方法顯然將藍(lán)色點(diǎn)與黃色點(diǎn)混淆在一起了祖灰，所有基于線性映射的方法都存在這樣的缺陷。

2.2 非線性降維

??為了克服線性降維算法的缺陷畔规，涌現(xiàn)了一批非線性降維算法局扶。在探討這些算法之前，有必要引入討論下流形學(xué)習(xí)的背景知識(shí)。

2.2.1 流形學(xué)習(xí)與knn圖

??三維空間中的地球三妈，我們只用兩個(gè)維度（經(jīng)度和緯度）就可以維一的定位地面上任意一點(diǎn)畜埋。如圖3.1c所示三維空間中的面包卷結(jié)構(gòu)上，我們將它錘平后可以近似看作幾個(gè)二維平面拼接在一起,我們可以確認(rèn)它的本征維度為2〕肫眩現(xiàn)實(shí)生活中的高維數(shù)據(jù)其實(shí)大量存在低維流形結(jié)構(gòu)悠鞍。2000年，Seung等人在《Science》上發(fā)表的論文【8】首次從流形的角度解釋了人類的視覺認(rèn)知形式模燥，提出了流形是人類認(rèn)知的基礎(chǔ)的觀點(diǎn)咖祭，這種認(rèn)知形式可以抽象成維數(shù)與神經(jīng)元數(shù)目相當(dāng)?shù)某橄罂臻g中的點(diǎn)。例如,雖然人臉的圖像是由 $N\times N$ 像素點(diǎn)組成的高維數(shù)據(jù)點(diǎn)蔫骂，但是圖2.2中只有頭像的角度變化么翰，理論上可以只用一個(gè)自由度去描述這幾個(gè)頭像圖的變化，也就是 $R^{N\times N}$ 高維空間中的一維流形,而人類認(rèn)知這個(gè)復(fù)雜人臉的變化可能只需要一個(gè)感知角度的神經(jīng)元×尚現(xiàn)實(shí)中浩嫌，一個(gè)圖像中的人臉可能還加入明暗度，大小补胚，表情變化等自由度码耐，但其本征維度遠(yuǎn)低于 $N\times N$ 像素點(diǎn)的維度。更重要的是溶其，隨著分辨率的提高伐坏，維度急劇增加，流形的本征維度卻沒有變化握联。

圖2.2 視覺認(rèn)知中的流形

??上文提到線性降維方法對面包卷流形可視化效果不好的原因，就是在流形中并非任意兩點(diǎn)的距離都適合用歐氏距離去衡量每瞒。比如對于地球金闽，當(dāng)測地的范圍較小時(shí)近似于二維平面。從百米跑道的起點(diǎn)走到終點(diǎn)剿骨，我們可以直接用歐氏距離來度量代芜，但是對于一艘做環(huán)球航行的船來說，再用歐氏距離去測量出來的距離就是0,這顯然是不合適的浓利。目前主流方法計(jì)算高維空間中的流形上的兩點(diǎn)距離進(jìn)而得出相似度矩陣都是使用knn圖,對于A點(diǎn)到B點(diǎn)的距離挤庇，我們測量A點(diǎn)與最近鄰點(diǎn)的歐氏距離，然后從A點(diǎn)出發(fā)找到一條到B點(diǎn)的路徑贷掖，用路徑上所有點(diǎn)對的距離之和近似A與B的距離嫡秕。

圖2.3(a)	圖2.3(b)	圖2.3(c)

??圖2.3(a)中的紅色虛線表示兩點(diǎn)間的歐氏距離，藍(lán)線表示實(shí)際距離苹威。圖2.3(c)中的紅色實(shí)線表示knn路徑對實(shí)際距離的近似昆咽。
??有了計(jì)算流形中兩點(diǎn)相似度的方法后，在這之上就有了將高維空間中的低維流形嵌入低維空間中以表征其結(jié)構(gòu)的降維方法，這被稱為流形學(xué)習(xí)掷酗。 ISOMAP和LLE降維算法是流形學(xué)習(xí)的奠基之作,它們從算法層面印證了高維非線性數(shù)據(jù)確實(shí)存在低維流形結(jié)果调违，分別從全局特征構(gòu)造和局部特征構(gòu)造兩個(gè)角度對高維非線性數(shù)據(jù)進(jìn)行低維流形結(jié)構(gòu)的還原。

2.2.2 ISOMAP算法

??ISOMAP算法是一種基于全局特征保持的流形學(xué)習(xí)算法泻轰。其算法的思路基本與MDS方法一致技肩，也是根據(jù)點(diǎn)對相似度距陣不斷迭代尋找各數(shù)據(jù)點(diǎn)在低維空間中放置的位置。不同的是ISOMAP通過knn計(jì)算點(diǎn)對相似度距陣浮声，用測地距離替代MDS中的歐氏距離虚婿。最終代價(jià)函數(shù)為高維空間點(diǎn)距離與低維空間點(diǎn)距離差之和，這里可以看出優(yōu)化目標(biāo)是全局特征阿蝶，然后對這個(gè)目標(biāo)函數(shù)用梯度下降迭代求最優(yōu)雳锋。
??ISOMAP算法在可視化流形時(shí)主要存在兩個(gè)問題：(1) “短路邊”的存在會(huì)嚴(yán)重破壞低維空間中的可視化效果，在構(gòu)建knn圖時(shí)如果為每個(gè)數(shù)據(jù)點(diǎn)選擇的領(lǐng)域過大或者輸入樣本中存在異常點(diǎn)羡洁，可能會(huì)導(dǎo)致流形上不相關(guān)的兩個(gè)點(diǎn)間產(chǎn)生過近的距離玷过。(2)對于非凸的高維數(shù)據(jù)集（有孔洞）,如圖2.4(b), ISOMAP不能很好的處理。(3)鄰域選取過小會(huì)導(dǎo)致圖非連通

2.2.3 LLE算法

??ISOMAP試圖在低維空間從全局上還原所有點(diǎn)對間測地距離筑煮，而LLE則試圖在低維空間還原點(diǎn)與鄰近點(diǎn)的局部線性關(guān)系辛蚊。具體來說，LLE根據(jù)相似度矩陣構(gòu)造每個(gè)點(diǎn)與周圍幾個(gè)鄰近點(diǎn)人線性關(guān)系真仲，然后對這個(gè)線性系數(shù)矩陣做特征分解袋马，求出在低位空間中的坐標(biāo)。LLE算法在可視化流形時(shí)主要存在兩個(gè)問題：(1)鄰域選取過大有時(shí)會(huì)導(dǎo)致很大一部分非近鄰點(diǎn)映射為近鄰點(diǎn)秸应。(2)不能處理首尾相接的閉環(huán)流形虑凛。(3)鄰域選取過小又可能導(dǎo)致找不到點(diǎn)的局部線性關(guān)系。

圖2.4(a)	圖2.4(b)	圖2.4(c)

3 確定本征維度的方法和擁擠問題

??前面提到過高維空間中的流形具有遠(yuǎn)低于所在空間的本征維度软啼，而如何估計(jì)低維流形的本征維度也是流形學(xué)習(xí)中的一個(gè)重要問題桑谍。而且這也是可視化的重要問題。如果低維流形的本征維度遠(yuǎn)大于2度祸挪，那利用降維算法將這些數(shù)據(jù)點(diǎn)可視化到二維散點(diǎn)圖中就會(huì)比較困難锣披。一個(gè)比較明顯的問題就是擁擠問題【11】, 對于10維空間中的一個(gè)點(diǎn)A，其以R為半徑的鄰域?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=R%5E%7B10%7D" alt="R^{10}" mathimg="1">空間中的球形, 我們假設(shè)這個(gè)鄰域中均勻分布著一系列點(diǎn)贿条，現(xiàn)在我們將點(diǎn)A和所有鄰域中的點(diǎn)映射到二維平面中雹仿，將會(huì)近似一個(gè)圓。在10維空間中鄰域內(nèi)離A較遠(yuǎn)的點(diǎn)遠(yuǎn)多于A附近的點(diǎn)整以，而這些較遠(yuǎn)點(diǎn)的象在二維平面上將集中在圓周附近胧辽，隨著原始維度的上升，這些圓周附近的點(diǎn)將會(huì)變得更加擁擠悄蕾，從而導(dǎo)致原始拓?fù)浣Y(jié)構(gòu)的失真票顾。在10維空間中我們至少能同時(shí)找到10個(gè)彼此距離相等的點(diǎn)础浮，而在2維空間中我們只能找到3個(gè)。如果不能解決擁擠問題奠骄，那么以低于流形本征維度的方式可視化就有很大可能失真豆同。
??本征維度被定義為在不損失信息的前提下，用來描述數(shù)據(jù)的自由變量的最小數(shù)量含鳞。局部本征維度估計(jì)方法可以分為全局本征維度估計(jì)法和局部本征維度估計(jì)法【6】影锈。

4 t-SNE可視化

??t-SNE算法是SNE算法的改進(jìn)，SNE將點(diǎn)對間的相似度用條件概率表述蝉绷，這樣任一點(diǎn)周圍的點(diǎn)分布可以用高斯分布表示鸭廷，然后用KL散度衡量低維空間中的分布于高維空間分布間的近視度,SNE的最終目標(biāo)就是對所有點(diǎn)最小化這個(gè)KL散度。
??t-SNE作出的改進(jìn)就是用在低維空間中用t分布替代高斯分布熔吗，如圖1所示辆床，高斯分布對應(yīng)高維空間，t-分布對應(yīng)低維空間桅狠。對于高維空間中相距較近的點(diǎn)讼载，為了滿足 $p_{ij} = q_{ij}$ ，低維空間中的距離需要稍小一點(diǎn)中跌；而對于高維空間中相距較遠(yuǎn)的點(diǎn)咨堤，為了滿足 $p_{ij} = q_{ij}$ ，低維空間中的距離需要更遠(yuǎn)漩符。這就使最終的可視化效果有更好的聚類表現(xiàn)一喘。t-分布的長尾效應(yīng)某種程度上緩解了擁擠問題。t-SNE作者還在論文【11】中提到嗜暴，t-分布只適合二維可視化凸克，其他維度的可視化需要其他分布。
??t-SNE相較于ISOMAP和LLE來說有更好的可視化效果闷沥，因?yàn)樗瑫r(shí)兼顧了全局特征和局部特征触徐。

圖4.1(a)t-SNE在MINIST數(shù)據(jù)上的可視化效果	圖4.2(b)ISOMAP可視化效果	圖4.2(c)LLE可視化效果

??圖4.1是t-SNE,ISOMAP,LLE在MINIST數(shù)據(jù)(手寫體數(shù)字)上的可視化效果，可以看出t-SNE在不同的類簇間形成清晰的間隔狐赡，而ISOMAP和LLE不同類間存在重疊。

5 總結(jié)

??本文簡述了從線性降維到非線性降維的發(fā)展歷史疟丙，列舉了幾種經(jīng)典的流行學(xué)習(xí)的算法在可視化方面的效果颖侄，包括當(dāng)前最流行的t-SNE算法。當(dāng)前的大量降維算法均是對這幾種算法的改進(jìn)或是基于類似的思想享郊。本文所有討論都只涉及了可視化效果這一角度览祖，而沒有分析各算法的時(shí)間空間復(fù)雜度。實(shí)際上炊琉，由于“維數(shù)災(zāi)難“問題和高維數(shù)據(jù)通常伴隨大尺度的特征展蒂，降維算法的運(yùn)算復(fù)雜度也是一個(gè)不容忽視的問題又活。
??最后指出一點(diǎn)，這些可視化的方法只能用于理論的探索和猜測锰悼，而不能做為驗(yàn)證理論正確性的工具柳骄，t-SNE的作者曾指出，相當(dāng)一部分學(xué)術(shù)論文使用t-SNE方法時(shí)犯了這樣的錯(cuò)誤箕般。

6 引用

??[1]陳為,沈則潛,陶煜波.數(shù)據(jù)可視化[M].北京:電子工業(yè)出版社,2013
??[2]詹宇斌.流形學(xué)習(xí)理論與方法及其應(yīng)用研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2011
??[3]石浩.基于等距特征映射的非線性降維及其應(yīng)用研究[D].合服:中國科學(xué)技術(shù)大學(xué),2017.
??[4]Jolliffe I T.Principal Component Analysis[M].New York:Springer-Verlag,1986
??[5]從SNE到t-SNE再到LargeVis
??[6]Camastra F.Data dimensionality estimation methods:a survey[J].Pattern recognition,2003,36(12):2945-2954.
??[7]Pettis K W,Bailey T A,Jain A K, et al.An intrinsic dimensionality estimator from near-neighbor information[J].IEEE Transactions on pattern analysis and machine intelligence,1979,PAMI-1(1):25-37
??[8]Seung,HS,Lee D D.The manifold ways of perception[J].science,2000,290(5500):2268-2269.
??[9]Tenenbaum J B,De Silva V,Langford J C. A global geometric framework for nonlinear dimensionality reduction[J].science, 2000,290(5500):2319-2323.
??[10]Roweis S T,Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J].science,2000,290(5500):2323-2326.
??[11]Laurens V D,Geoffrey Hinton. Visualizing Data using t-SNE[J].Machine Learning Research 9(2008):2579-2605.

降維與可視化