如何理解可視化利器t-SNE演算法？

T 分布隨機近鄰嵌入（T-Distribution Stochastic Neighbour Embedding）是一種用於降維的機器學習方法，它能幫我們識別相關連的模式。t-SNE 主要的優勢就是保持局部結構的能力。這意味著高維數據空間中距離相近的點投影到低維中仍然相近。t-SNE 同樣能生成漂亮的可視化。

當構建一個預測模型時，第一步一般都需要理解數據。雖然搜索原始數據並計算一些基本的統計學數字特徵有助於理解，但沒有什麼是可以和圖表可視化展示更直觀的。然而將高維數據擬合到一張簡單的圖表（降維）通常是非常困難的，這就正是 t-SNE 發揮作用的地方。

在本文中，我們將探討 t-SNE 的原理，以及 t-SNE 將如何有助於我們可視化數據。

t-SNE 演算法概念

這篇文章主要是介紹如何使用 t-SNE 進行可視化。雖然我們可以跳過這一章節而生成出漂亮的可視化，但我們還是需要討論 t-SNE 演算法的基本原理。

t-SNE 演算法對每個數據點近鄰的分布進行建模，其中近鄰是指相互靠近數據點的集合。在原始高維空間中，我們將高維空間建模為高斯分布，而在二維輸出空間中，我們可以將其建模為 t 分布。該過程的目標是找到將高維空間映射到二維空間的變換，並且最小化所有點在這兩個分布之間的差距。與高斯分布相比 t 分布有較長的尾部，這有助於數據點在二維空間中更均勻地分布。

控制擬合的主要參數為困惑度（Perplexity）。困惑度大致等價於在匹配每個點的原始和擬合分布時考慮的最近鄰數，較低的困惑度意味著我們在匹配原分布並擬合每一個數據點到目標分布時只考慮最近的幾個最近鄰，而較高的困惑度意味著擁有較大的「全局觀」。

因為分布是基於距離的，所以所有的數據必須是數值型。我們應該將類別變數通過二值編碼或相似的方法轉化為數值型變數，並且歸一化數據也是也十分有效，因為歸一化數據後就不會出現變數的取值範圍相差過大。

T 分布隨機近鄰嵌入演算法（t-SNE）

http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf

Jake Hoare 的博客並沒有詳細解釋 t-SNE 的具體原理和推導過程，因此下面我們將基於 Geoffrey Hinton 在 2008 年提出的論文詳細介紹 t-SNE 演算法。如果讀者對這一章節不感興趣，也可以直接閱讀下一章節 Jake Hoare 在實踐中使用 t-SNE 進行數據可視化。

https://nlml.github.io/in-raw-numpy/in-raw-numpy-t-sne/

因為 t_SNE 是基於隨機近鄰嵌入而實現的，所以首先我們需要理解隨機近鄰嵌入演算法。

隨機近鄰嵌入（SNE）

假設我們有數據集 X，它共有 N 個數據點。每一個數據點 x_i 的維度為 D，我們希望降低為 d 維。在一般用於可視化的條件下，d 的取值為 2，即在平面上表示出所有數據。

SNE 通過將數據點間的歐幾里德距離轉化為條件概率而表徵相似性（下文用 p_j|i 表示）：

如果以數據點在 x_i 為中心的高斯分布所佔的概率密度為標準選擇近鄰，那麼 p_j|i 就代表 x_i 將選擇 x_j 作為它的近鄰。對於相近的數據點，條件概率 p_j|i 是相對較高的，然而對於分離的數據點，p_j|i 幾乎是無窮小量（若高斯分布的方差σ_i 選擇合理）。

其中σ_i 是以數據點 x_i 為均值的高斯分布標準差，決定σ_i 值的方法將在本章後一部分討論。因為我們只對成對相似性的建模感興趣，所以可以令 p_i|i 的值為零。

現在引入矩陣 Y，Y 是 N*2 階矩陣，即輸入矩陣 X 的 2 維表徵。基於矩陣 Y，我們可以構建一個分布 q，其形式與 p 類似。

對於高維數據點 x_i 和 x_j 在低維空間中的映射點 y_i 和 y_j，計算一個相似的條件概率 q_j|i 是可以實現的。我們將計算條件概率 q_i|j 中用到的高斯分布的方差設置為 1/2。因此我們可以對映射的低維數據點 y_j 和 y_i 之間的相似度進行建模：

我們的總體目標是選擇 Y 中的一個數據點，然後其令條件概率分布 q 近似於 p。這一步可以通過最小化兩個分布之間的 KL 散度（損失函數）而實現，這一過程可以定義為：

因為我們希望能最小化該損失函數，所以我們可以使用梯度下降進行迭代更新，我們可能對如何迭代感興趣，但我們會在後文討論與實現。

使用 NumPy 構建歐幾里德距離矩陣

計算 p_i|j 和 q_i|j 的公式都存在負的歐幾里德距離平方，即-||x_i - x_j||^2，下面可以使用代碼實現這一部分：

為了更高的計算效率，該函數使用矩陣運算的方式定義，該函數將返回一個 N 階方陣，其中第 i 行第 j 列個元素為輸入點 x_i 和 x_j 之間的負歐幾里德距離平方。

使用過神經網路的讀者可能熟悉 exp(?)/∑exp(?) 這樣的表達形式，它是一種 softmax 函數，所以我們定義一個 softmax 函數：

注意我們需要考慮 p_i|i=0 這個條件，所以我們可以替換指數負距離矩陣的對角元素為 0，即使用 np.fill_diagonal(e_x, 0.) 方法將 e_x 的對角線填充為 0。

將這兩個函數放在一起後，我們能構建一個函數給出矩陣 P，且元素 P(i,j) 為上式定義的 p_i|j：

感到困惑？

在上面的代碼段中，Sigmas 參數必須是長度為 N 的向量，且包含了每一個σ_i 的值，那麼我們如何取得這些σ_i 呢？這就是困惑度（perplexity）在 SNE 中的作用。條件概率矩陣 P 任意行的困惑度可以定義為：

其中 H(P_i) 為 P_i 的香農熵，即表達式如下：

在 SNE 和 t-SNE 中，困惑度是我們設置的參數（通常為 5 到 50 間）。我們可以為矩陣 P 的每行設置一個σ_i，而該行的困惑度就等於我們設置的這個參數。直觀來說，如果概率分布的熵較大，那麼其分布的形狀就像對平坦，該分布中每個元素的概率就更相近一些。

困惑度隨著熵增而變大，因此如果我們希望有更高的困惑度，那麼所有的 p_j|i（對於給定的 i）就會彼此更相近一些。換而言之，如果我們希望概率分布 P_i 更加平坦，那麼我們就可以增大σ_i。我們配置的σ_i 越大，概率分布中所有元素的出現概率就越接近於 1/N。

所以如果我們希望有更高的困惑度，將σ_i 增大將使條件概率分布變得更加平坦。實際上這增加了每個點的近鄰數，這就是為什麼我們常將困惑度參數大致等同於所需要的近鄰數量。

搜索σ_i

為了確保矩陣 P 每一行的困惑度 Perp(P_i) 就等於我們所希望的值，我們可以簡單簡單地執行一個二元搜索以確定σ_i 能得到我們所希望的困惑度。這一搜索十分簡單，因為困惑度 Perp(P_i) 是隨σ_i 增加而遞增的函數，下面是基本的二元搜索函數：

為了找到期望的σ_i，我們需要將 eval_fn 傳遞到 binary_search 函數，並且將σ_i 作為它的參數而返回 P_i 的困惑度。

以下的 find_optimal_sigmas 函數確實是這樣做的以搜索所有的σ_i，該函數需要採用負歐幾里德距離矩陣和目標困惑度作為輸入。距離矩陣的每一行對所有可能的σ_i 都會執行一個二元搜索以找到能產生目標困惑度的最優σ。該函數最後將返回包含所有最優σ_i 的 NumPy 向量。

對稱 SNE

現在估計 SNE 的所有條件都已經聲明了，我們能通過降低成本 C 對 Y 的梯度而收斂到一個良好的二維表徵 Y。因為 SNE 的梯度實現起來比較難，所以我們可以使用對稱 SNE，對稱 SNE 是 t-SNE 論文中一種替代方法。

在對稱 SNE 中，我們最小化 p_ij 和 q_ij 的聯合概率分布與 p_i|j 和 q_i|j 的條件概率之間的 KL 散度，我們定義的聯合概率分布 q_ij 為：

該表達式就如同我們前面定義的 softmax 函數，只不過分母中的求和是對整個矩陣進行的，而不是當前的行。為了避免涉及到 x 點的異常值，我們不是您 p_ij 服從相似的分布，而是簡單地令 p_ij=(p_i|j+p_j|i)/2N。

我們可以簡單地編寫這些聯合概率分布 q 和 p：

同樣可以定義 p_joint 函數輸入數據矩陣 X 並返回聯合概率 P 的矩陣，此外我們還能一同估計要求的σ_i 和條件概率矩陣：

所以現在已經定義了聯合概率分布 p 與 q，若我們計算了這兩個聯合分布，那麼我們能使用以下梯度更新低維表徵 Y 的第 i 行：

在 Python 中，我們能使用以下函數估計梯度，即給定聯合概率矩陣 P、Q 和當前低維表徵 Y 估計梯度：

為了向量化變數，np.expand_dims 方法將十分有用，該函數最後返回的 grad 為 N*2 階矩陣，其中第 i 行為 dC/dy_i。一旦我們計算完梯度，那麼我們就能利用它執行梯度下降，即通過梯度下降迭代式更新 y_i。

我們對 t-SNE 的符號定義為：X 是原來的數據；P 是一個矩陣，顯示了高維（原來的）空間中 X 中的點之間的親和度（affinities，約等於距離）；Q 也是一個矩陣，顯示了低維空間中數據點之間的親和度。如果你有 n 個數據樣本，那麼 Q 和 P 都是 n×n 的矩陣（從任意點到任意點的距離包含自身）。

現在 t-SNE 有自己的「獨特的」測量事物之間距離的方式（我們下面就會介紹）、一種測量高維空間中數據點之間的距離的方式、一種測量低維空間中數據點之間的距離的方式以及一種測量 P 和 Q 之間的距離的方式。

根據原始論文，一個數據點 x_j 與另一個點 x_i 之間的相似度是 p_j|i，其定義為：「x_i 選取 x_j 為其近鄰點（neighbor），而近鄰點的選取與以 x_i 為中心的高斯分布概率密度成正比。」

「這是什麼意思！」不要擔心，我前面說了，t-SNE 有自己測量距離的獨特方式，所以讓我們看看用於測量距離（親和度）的公式，然後從中取出我們理解 t-SNE 的行為所需的見解。

從高層面來講，這就是演算法的工作方式（注意和 PCA 不一樣，這是一個迭代式的演算法）。

圖 3：t-SNE 工作流程

讓我們一步步地研究一下這個流程。

這個演算法有兩個輸入，一個是數據本身，另一個被稱為困惑度（Perp）。

簡單來說，困惑度（perplexity）是指在優化過程中數據的局部（封閉點）和全局結構的焦點的平衡程度——本文建議將其保持在 5 到 50 之間。

更高的困惑度意味著一個數據點會把更多的數據點看作是其緊密的近鄰點，更低的困惑度就更少。

困惑度會實際影響可視化的結果，而且你需要小心應對，因為它可能會在可視化低維數據時出現誤導現象——我強烈推薦閱讀這篇文章了解如何使用 t-SNE 困惑度：http://distill.pub/2016/misread-tsne，其中介紹了不同困惑度的影響。

這種困惑度從何而來？它被用於求解式子 (1) 中的 σ_i，而且因為它們有單調的連接，所以可以通過二元搜索（binary search）找到。

所以使用我們提供給演算法的困惑度，我們基本上會找到不同的 σ_i。

讓我們看看公式為我們提供了哪些關於 t-SNE 的信息。

在我們探索公式 (1) 和 (2) 之前，需要知道 p_ii 和 q_ii 被設置為 0（即使我們將它們應用到兩個相似的點上，公式的輸出也不會是 0，這只是給定的值）。

所以看看公式 (1) 和 (2)，我希望你注意到，當兩個點很接近時（在高維表徵中），分子的值大約為 1，而如果它們相距非常遠，那麼我們會接近無窮小——這將有助於我們後面理解成本函數。

現在我們可以了解關於 t-SNE 的一些事情了。

一是因為親和度公式的構建方式，在 t-SNE 圖中解讀距離可能會出問題。

這意味著聚類之間的距離和聚類大小可能被誤導，並且也會受到所選擇的困惑度的影響（在上面我推薦的文章中，你可以看到這些現象的可視化）。

第二件要注意的事情是，怎麼在等式 (1) 中我們基本上計算的是點之間的歐幾里得距離？這方面 t-SNE 很強大，我們可以用任何我們喜歡的距離測量來取代它，比如餘弦距離、Manhattan 距離，也可以使用任何你想用的測量方法（只要其保持空間度量（space metric），而且保持低維親和度一樣）——以歐幾里得的方式會得到複雜的距離繪圖。

比如說，如果你是一位 CTO，你有一些數據需要根據餘弦相似度測量距離，而你的 CEO 想要你通過圖表的形式呈現這些數據。我不確定你是否有時間向董事會解釋什麼是餘弦相似度以及解讀聚類的方式，你可以直接繪製餘弦相似度聚類，因為歐幾里得距離聚類使用 t-SNE——要我說，這確實很酷。

在代碼中，你可以在 scikit-learn 中通過向 TSNE 方法提供一個距離矩陣來實現。

現在，我們知道當 x_i 和 x_j 更近時，p_ij/q_ij 的值更大；相反則該值更小。

讓我們看看這會對我們的成本函數（被稱為 KL 散度（Kullback–Leibler divergence））帶來怎樣的影響。讓我們繪圖，然後看看沒有求和部分的公式 (3)。

圖 4：沒有求和部分的 t-SNE 成本函數

很難看明白這是啥？但我在上面給軸加了名字。

如你所見，這個成本函數是不對稱的。

對於高維空間中臨近的點，其得出了非常高的成本（p 軸），但這些點是低維空間中很遠的點表示的；而在高維空間中遠離的點則成本更低，它們則是用低維空間中臨近的點表示的。

這說明在 t-SNE 圖中，距離解釋能力的問題甚至還更多。

t-SNE 可視化

我們將要使用的第一個數據集是基於物理特徵分類的 10 種不同葉片。這種情況下，t-SNE 需要使用 14 個數值變數作為輸入，其中就包括葉片的生長率和長寬比等。下圖展示了 2 維可視化輸出，植物的種類（標籤）使用不同的顏色表達。

物種 Acer palmatum 的數據點在右上角形成了一個橙色集群，這表明它的葉子和其他物種有很大的不同。該示例中類別通常會有很好的分組，相同物種的葉子（同一顏色的數據點）趨向於彼此靠緊聚集在一起。左下角有兩種顏色的數據點靠近在一起，說明這兩個物種的葉子形狀十分相似。

最近鄰準確度表明給定兩個隨機點，它們是相同物種的概率是多少。如果這些數據點完美地根據不同物種而分類，那麼準確度就會非常接近 100%，高準確度意味著數據能被乾淨地分為不同的集群。

困惑度

下面，我們對可樂品牌做了類似的分析。為了演示困惑度（perplexity）的影響，我們首先需要將困惑度設置為較低的值 2，每個數據點的映射只考慮最近鄰。如下，我們將看到許多離散的小集群，並且每一個集群只有少量的數據點。

下面我們將 t-SNE 的困惑度設置為 100，我們可以看到數據點變得更加擴散，並且同一類之間的聯繫變弱。

在該案例中，可樂本身就要比樹葉更難分割，即使一類數據點某個品牌要更集中一些，但仍然沒有明確的邊界。

在實踐中，困惑度並沒以一個絕對的標準，不過一般選擇 5 到 50 之間會有比較好的結果。並且在這個範圍內，t-SNE 一般是比較魯棒的。

預測的解釋

度量數據點之間的角度或距離並不能推斷出任何數據上的具體或定量的信息，所以 t-SNE 的預測更多的是用於可視化數據。

在模型搭建前期直觀地挖掘數據模式有助於指導數據科學下一步進程。如果 t-SNE 能很好地分割數據點，那麼機器學習同樣也能找到一種將未知新數據投影到相應類別的好方法。給定一種預測演算法，我們就能實現很難搞的準確度。

上例中每一個類別都是孤立分類的，因此簡單的機器學習模型就能將該類別與其他類別分離開。但如果類別重疊，我們可能就要構建更精細的模型做出預測。如下所示，如果我們按照某個品牌的偏好從 1 到 5 進行分類，那麼類別可能更加離散、更難以預測，最近鄰精度也會相對較低。

對比 PCA

很自然我們就希望將 t-SNE 和其他降維演算法做比較。降維演算法中比較流行的是主成分分析法（PCA），PCA 會尋找能儘可能保留數據方差的新維度。有較大的方差的數據保留的信息就越多，因為彼此不同的數據可以提供不同的信息，所以我們最好是保留彼此分離的數據點，因為它們提供了較大的方差。

下面是採用 PCA 演算法對上文的樹葉類別進行降維的結果，我們看到雖然左側的橙色是分離的，但其它類別都有點混合在一起。這是因為 PCA 並不關心局部的最近鄰關係，此外 PCA 是一種線性方法，所以它表徵非線性關係可能效果並不是很好。不過 PCA 演算法在壓縮數據為更小的特徵向量而投入到預測演算法中有很好地表現，這一點它要比 t-SNE 效果更好。

結語

t-SNE 是一種可視化高維數據的優秀演算法，它經常要比其它降維演算法生成更具特點的可視化結果。