面向數據集的ST-SNE算法高維數據降維研究

董 駿

（寧夏財經職業技術學院 信息與智能工程系，寧夏銀川750021）

高維數據對數據挖掘、機器學習和可視化提出了很多挑戰，數據降維算法可以通過將高維數據映射到低維空間來解決這些問題。現有的數據降維方法主要分為線性和非線性降維算法[1]。線性降維算法假設低維數據分布在高維空間的線性子空間中，算法試圖找到一個盡可能保存高維數據特性的線性子空間。主要的代表算法是PCA[2]和LDA[3]。由于線性降維算法具有前提條件，這類算法有其局限性，其降維效果在線性結構的數據上效果很好，但是當高維數據中包含非線性結構時，算法的效果并不理想。非線性降維算法的出現解決了這個問題。非線性降維算法的原理各不相同，較受關注的兩類是基于流形[4]和基于概率[5]的算法。基于流形的算法可以保存高維空間中形成局部曲面的數據的結構[6]，從而構建一個聯通的低維流形模型代表算法有 Isomap[7]、LLE[8]和 LE[9]。基于流形的算法計算量較大，且多數需要調整復雜的參數來得到合適的流形模型。在數據點分布疏密不均的情況下，這類算法可能會學習到扭曲的流形。基于概率的算法將高維空間和低維空間中數據的結構分別映射為兩個概率矩陣，矩陣中的每個元素代表著兩點間的近似程度。算法通過最小化代價函數來減小兩個概率矩陣間的差異，最終得到數據的低維分布。這類算法的代表有：SNE[10]、t-SNE[11]和 NERV[12]等。

t-SNE的降維效果在眾多降維算法中表現突出，適應范圍較廣。t-SNE在高維空間中使用歐氏距離來衡量數據間的相似度，但研究表明高維空間中歐氏距離并不可靠。相似度是t-SNE構建概率矩陣的先驗條件，因此t-SNE展開流形的能力受到了不準確先驗條件的約束。本文利用高維空間中兩個數據共享的鄰居信息來衡量數據之間的相似度，提出了計算高維數據間二階鄰近距離的方法，并將二階鄰近距離與t-SNE算法結合，提出基于二階鄰近距離的隨機鄰近嵌入算法（Second Order t-SNE，ST-SNE）。為了對算法進行評價，本文在MNIST、USPS以及COIL-20等數據集上進行了實驗，對ST-SNE和t-SNE算法的降維結果進行了對比。結果表明，ST-SNE算法的降維結果提升了KNN分類的準確度，同時得到了更好的可視化效果。

1 t-SNE

t分布隨機近鄰嵌入算法（t-Distributed Stochastic Neighbor Embedding，t-SNE）是 Laurens于2008年提出的基于SNE的改進降維算法[13]。t-SNE將位于N維空間中的高維數據向量X1，…，Xn映射到D維空間中的低維向量Y1，…，Yn。其中yi與xi一一對應，使得低維空間中數據的分布可以反映出高維空間中數據間的關系。t-SNE的基本原理是將高維和低維空間中數據點之間的歐氏距離分別轉換為兩個n×n的條件概率矩陣來表示數據點間的相似性，然后最小化兩個概率矩陣間的差別。

在高維空間中數據點xi與xj間的相似性被轉化為pj|i：

式中，σ是高斯方差參數，它的大小與點的鄰居疏密有關。pj|i是一個條件概率，如果按照以xi為中心的高斯分布來選擇xi的鄰居，那么xi將會以pj|i的概率選擇xj作為它的鄰居。若xj距離xi較近，則pj|i越大；反之，則pj|i越小。

SNE直接使用條件概率來映射數據間的相似度。但由于pi|j≠pj|i，SNE的代價函數是不對稱的。為了解決這個問題，t-SNE使用聯合概率分布來映射相似度，這樣可以保證任取i和j，都有pij=pji。在高維空間中，t-SNE根據條件概率pi|j和pj|i計算出pij：

因此，對于所有xi有：

這保證了每個xi在代價函數中都有足夠的影響力。在SNE算法中，低維映射yi與yj間的距離同樣使用高斯分布映射為條件概率qj|i。但這導致了SNE算法的“擁擠問題”。“擁擠問題”是由于高維空間特性造成的，高維空間中成對距離的分布與低維非常不同。假設在10維空間中，最多有11個點可以滿足兩兩之間距離相等，當把這11個點降到2維空間中后，這些點的關系就不可能正確的表達了。進一步考慮一個以數據點i為中心的球，其體積為r″′，其中r為半徑，m為球面的維數，點i的鄰居大致均勻的分布在球中。維度越高時，鄰居點中處于球面附近的點的數量占總數量的比例越大。因此，當我們嘗試在低維空間中對點到其鄰居點的距離進行建模時，可用于映射數據點的空間與高維中的空間相比相對較小。如果想得到正確的映射點i與其鄰居點的距離關系，需要將距離不同的點映射到更分散的區域。

t-SNE在低維空間中使用t分布代替高斯分布。t分布是一種長尾分布。考慮在高維空間中距離較近的兩個點xi與xj。在高維空間中兩點間的歐氏距離被映射為pij，為了達到pij=qij的條件，在低維空間中與會被映射的更近。同理，在高維空間中距離較遠的兩個點xk與xm在低維空間中就會被映射的更遠。使用t分布的低維聯合概率密度為qij：

t分布是高斯分布的無限混合，但是t分布的計算并不需要引入e的指數。這也使得代價函數的計算更加簡潔。t-SNE算法的代價函數如下：

對稱的代價函數使得梯度的計算更加簡潔：

t-SNE通過使用對稱的代價函數和t分布成功的改進了SNE的兩個問題，得到了較好的降維可視化效果。

2 高維數據的二階鄰近距離

2.1 歐氏距離在高維空間中存在的問題

t-SNE算法在高維空間中使用歐氏距離來衡量數據間的距離。但是研究表明，在高維空間中接近度，距離和最近鄰居的概念都與低維空間不同。在某些合理假設的數據分布下，高維空間中最近和最遠鄰居與給定目標之間距離的比率幾乎為1[14]。在這種情況下，由于不同數據點的距離之間的對比度不復存在，最近鄰居問題變得不再明確。文獻[15]中的研究表明，對于計算距離的通式：

其中，k值越小時，所計算出的距離越適合運用在高維空間中，并由此提出了分數距離度量，即利用k＜1的距離來衡量高維空間中數據間的距離。當k=2時，式（7）代表歐氏距離。

根據本文將分數距離度量應用到t-SNE算法的實驗，分數距離度量對值的選擇比較敏感，當數據集的分布和維度不同時，找到合適的值需要花費較大代價。同時，使用分數距離度量對降維效果的提升有限。分數距離度量以及現有的大部分降維算法都在高維空間中直接使用一階鄰近性來度量數據間的相似性。一階鄰近性的信息并不能全面的表達數據的全局和局部結構[16]。因此，本文提出使用二階鄰近距離來度量高維數據間的相似度。

2.2 二階鄰近距離

考慮高維空間中的兩點a和b，首先根據其余數據點到a和b的歐氏距離創建兩個鄰居列表Oa和Ob，與a或b距離越小的點在列表中的位置越靠前，圖1給出了鄰居列表的示例。

圖1 鄰居列表示例圖

其中，K為鄰居列表的長度，若數據集較小，K可以與數據點數量相同；若數據集較大，可以只取前K個鄰居組成列表，以平衡算法復雜度和結果精確度。當二階鄰近距離應用于t-SNE算法時，K可與t-SNE算法中的近似參數配合。

接下來，根據鄰居列表Oa和Ob計算點a到b的非對稱距離 D（a，b）：

其中，1-（i/2K）為線性衰減系數，列表中位置越靠后的點對距離的貢獻越小，Ia（i）返回列表Oa中位于第i位的數據點P，例如圖1中Ia（0）返回點a。Rb（P）返回點P位于列表Ob中的位置，由于列表里只包含前K個最近鄰居，點P有可能不存在于Ob中，故Rb（P）為：

圖1 中的D（a，b）為：

同理可計算出D（b，a）。則點a與點b的對稱距離D為：

本質上，D是點a與點b的鄰居點在對方鄰居列表中位置的加權和。D越小，則代表著點a與點b的最近鄰居的結構越相似。算法實現具體描述如下：

算法1：二階鄰近距離輸入：數據集 X={X1，…，xn}，鄰居列表長度 K；輸出：N×N的距離矩陣Ds；1.按照歐氏距離的大小計算每個數據xi的前K個鄰近點，并按照由近到遠的順序組成鄰居列表Oi。2.for i=1 to n 3.for j=1 to i 4. 按式（8）計算出 D（i，j）和 D（j，i）5.Ds（i，j）=Ds（j，i）=D（i，j）+D（j，i）6.end for 7.end for

3 ST-SNE

由于t-SNE使用的歐氏距離在高維空間中不能全面的表達數據集的全局和局部結構。本文在計算高維空間中數據點間的距離時使用數據的二階鄰近距離替換歐式距離。改進后的算法稱為STSNE（Second Order t-SNE）。ST-SNE 基于 BH-SNE算法[17]，后者使用一定程度的近似提升了t-SNE在處理大數據集時的速度。

ST-SNE主要有三個步驟：首先計算高維空間中數據點間的二階鄰近距離并將距離轉化為聯合概率矩陣P，接著隨機初始化低維空間中的數據分布并根據數據點間的歐氏距離生成聯合概率矩陣Q，最后使用梯度下降法最小化P與Q之間的差異。

在計算二階鄰近距離時，首先要為每個數據點生成長度為K的鄰居列表Oi。Oi通過在高維空間數據上構建vantage-point樹并在樹上進行最近鄰居搜索生成，時間復雜度為O（N log N）。BH-SNE中的參數perplexity（ρ）決定了算法近似程度，在ST-SNE中規定鄰居列表長度K=3ρ。根據數據集的不同，ρ的典型值為10-100，故鄰居列表Oi的長度一般為30-300。這將后續計算數據點間距離的時間復雜度由 O（N2）降為了 O（KN），同時可以得到可靠的降維結果。當所有數據點的鄰居列表Oi生成完畢后，即可根據式（8）計算數據點間的二階鄰近距離。

在將高維空間中的二階鄰近距離映射到聯合概率矩陣P時，對于每個點只計算其與前K個鄰居點的pi|j，與其余所有點的pi|j近似為0：

其中，D（xi，xj）表示點xi與xj間的二階鄰近距離。pj|i與pi|j相加計算出pij：

其中，N為數據點的總數量。使用這種方法計算pij以保證每個點在代價函數中有足夠的影響力。pij最終形成聯合概率矩陣p。

在低維空間中，歐式距離可以正確的表達數據的結構，所以在計算低維空間中的聯合概率分布時直接使用歐氏距離，并沿用t分布將距離映射為概率：

ST-SNE同樣使用Kullback-Leibler距離來最小化概率矩陣P與Q之間的差異，目標函數為：

由于KL距離的不對稱性，目標函數傾向于使用大qij的值來映射大的pij。ST-SNE使用梯度下降法最小化目標函數，梯度可以整理為如下形式：

在這種情況下，當計算yj和yk兩個點yi與之間的M時，yj和yk可以合并為一個點來考慮。BHSNE通過使用Barnes-Hut算法[18]來決定哪些點可以合并，ST-SNE也沿用這一做法。進行近似后計算式（16）后半部分的時間復雜度降為O（N log N）。ST-SNE算法實現具體描述如下：

算法 2：ST-SNE輸入：高維數據集 X={X1，…，xn}，perplexity ρ，learning rate η，momentum α（t），最大迭代次數 T；輸出：低維數據分布：；1.構建vantage-point樹并進行鄰近點查找，構建鄰居列表；2.使用式（11）計算點i與點j間的條件概率Pj|i；3.將點i與j點間聯合概率設為Pij，得到聯合概率矩陣；4.在原點附近隨機初始化地位分布：Y（0）={y1，…，yn}5.for t=1 to T 6.按式（13）計算低維聯合概率分布7.按式（15）計算梯度8.Y（t）=Y（t）+ η δC δY + α（t）（Y（t-1）-Y（t-2））9.end for

4 實驗與分析

在4個公共數據集上對ST-SNE和BH-SNE進行了對比測試，對比了兩個降維算法的結果在可視化效果和KNN分類準確率兩方面的表現。在實驗的過程中，兩個降維算法使用相同的參數和條件。下面針對每個數據集逐一進行描述。

4.1 MNIST數據集

MNIST數據集中包含了60000個灰度圖片，圖片的內容是手寫的0-9阿拉伯數字。每張圖片的分辨率為28×28=784像素，每一幅圖都屬于十個類別中的一類。本文直接使用像素的灰度值作為輸入。在實驗中，兩個算法都先使用PCA將數據降維到55維，再運行各自的降維過程將數據降到2維。兩個算法的perplexity參數都設置為30，在最小化目標函數的過程中都進行20000次迭代。

圖2 BH-SNE與ST-SNE在MNIST數據集上的可視化對比

可視化效果對比如圖2所示，其中每種顏色代表一類數據。可以觀察到，兩個算法都正確的將相同類別的點聚成了簇。ST-SNE不同類別之間的間隔更加明顯，且相同類別的點都處于同一個簇中。而BH-SNE有些簇的邊界不分明，有小部分相同類別的點形成了多個簇。

圖3中展示了兩個算法KNN分類準確率的結果，兩個算法的表現相差不多，隨著K的增大，STSNE的分類準確率更有優勢。

圖3 BH-SNE與ST-SNE在MNIST上KNN分類準確率對比

4.2 UCI Letter Recognition數據集

UCI Letter Recognition數據集中包含20000個手寫字母的數據，每個數據的維度為16維，每個數據都屬于26類手寫字母中的一類。由于數據維度較低，不需要使用PCA進行預處理。perplexity參數都設置為20，在最小化目標函數的過程中都進行20000次迭代。

可視化效果如圖4所示。可以看到兩個算法在這個數據集上表現的都不好，不能正確的把相同類別的點聚到一簇中，這主要是由于同一種字母的寫法差異較大導致的。特征明顯的數據大多被算法移動到了邊緣，這些數據由于特征突出并一致，比較容易形成獨立分隔開的簇，在這個方面ST-SNE與BH-SNE都做到了。

圖4 BH-SNE與ST-SNE在UCI Letter Recognition數據集上的可視化對比

在中間的部分，數據的特征都比較模糊不易區分。ST-SNE在這部分數據中識別出了更多的特征，并形成了一些獨立的簇和模糊的簇，模糊的簇在有染色的情況下是比較清晰的。BH-SNE這部分的結果顯得比較雜亂，沒有識別出不明顯的特征。

圖5中展示了兩個算法KNN分類準確率的結果。在這個數據集上，ST-SNE的分類準確率高于BH-SNE，當K增大時優勢更加明顯。這個結果也印證了可視化結果中ST-SNE識別出了更多的特征。

4.3 USPS數據集

USPS數據集和MNIST數據集類似，數據集里包含7291個手寫數字圖片，圖片的分辨率為16×16=256像素。每幅圖片都屬于0-9數字中的一類。在實驗過程中，兩個算法都使用PCA算法先行降維到55維。perplexity參數都設置為20，在最小化目標函數的過程中都進行20000次迭代。

圖6中展示了兩個算法的可視化結果，兩個算法都得到了較為不錯的效果，同一類別的點基本都聚集在了一個簇中。相比于BH-SNE，ST-SNE的結果中，同一類別的點聚集的更加緊密，類間的分隔更加明顯。

兩個算法在USPS數據集上的KNN分類準確率的結果如圖7所示，兩個算法的表現接近，可以看到ST-SNE的準確率在各個K值上均高于BHSNE。

圖7 BH-SNE與ST-SNE在USPS上的KNN分類準確率對比

4.4 COIL-20數據集

COIL-20數據集是一個物體圖片的數據集，包含20種物品的灰階圖片，共1440張圖片，每張圖片的分辨率為64×64=4096像素。每種物體在光照下從不同的角度拍攝72張圖片。在實驗過程中，先使用PCA將數據從4096維降至55維，然后分別運行兩種降維算法。perplexity參數都設置為20，在最小化目標函數的過程中都進行10000次迭代。

可視化結果如圖8所示，可見兩個算法都很好的識別出了屬于各個物體的數據并聚在了一起，在結果的局部結構中，可以清晰的觀察到對于同一物體由于拍攝角度變化而形成的旋轉流形。ST-SNE在這個數據集可視化結果上的表現與BH-SNE相似。

圖8 BH-SNE與ST-SNE在COIL-20數據集上的可視化對比

圖9展示了KNN分類準確率的結果，兩個算法的準確率在值較小時相差不多，當值逐漸增大時，ST-SNE的分類準確率高于BH-SHE。

圖9 BH-SNE與ST-SNE在COIL-20上KNN分類準確率對比

5 結論

提出了基于二階鄰近距離的隨機近鄰嵌入算法ST-SNE。二階鄰近距離在高維空間中利用鄰居結構來衡量數據點間的相似度，相較于歐式距離可以更加準確的描述數據間關系。ST-SNE算法使用二階鄰近距離將高維數據結構映射為概率矩陣，解決了t-SNE中歐式距離在高維空間不可靠的問題。在MNIST等公開數據集上的對比實驗結果表明，ST-SNE提升了降維結果的可視化效果和KNN分類準確率。本研究還存在一些不足：二階鄰近距離需要逐一尋找每個點在鄰近點的鄰居列表中的位置，時間復雜度較高；計算二階鄰近距離時，使用線性衰減來決定每個點的權重，可以研究效果更好的衰減函數；ST-SNE在更多數據集中的表現有待進一步驗證。