通俗理解一個常用的降維演算法(t-SNE)

2019 年 12 月 6 日
筆記

以下文章來源於Python與演算法社區，作者zhenguo

作者：草yang年華

來源：python與演算法社區

1 t-SNE 背景介紹

最易被我們視覺觀察到的維數是一維，二維和三維，四維及以上用圖形表達都不會那麼直觀。

然而，現實情況卻是隨意拿個數據集，都有上千上百個維度。比如，經典的MNIST維度是64，所以使用二維的笛卡爾坐標系，註定無法繪製64個維度。

當我們想對高維數據集進行分類，但又不清楚這個數據集有沒有很好的可分性（同類之間間隔小、異類之間間隔大）時，可以通過降維演算法將數據投影到二維或三維空間中。

很久以前，就有人提出一種降維演算法，主成分分析(PCA) 降維法，中間其他的降維演算法陸續出現，比如多維縮放(MDS)，線性判別分析(LDA)，等度量映射(Isomap)。

等時間來到2008年，另外一個和我們比較熟悉的大牛 Geoffrey Hinton在 2008 年一同提出了t-SNE 演算法。

他們改進SNE演算法為t-SNE演算法，並使它在降維領域得到更廣泛的應用。

2 t-SNE 演算法概述

全稱為 t-distributed Stochastic Neighbor Embedding，翻譯為 t分布-隨機鄰近嵌入。

怎麼理解這個名字？

首先，t-分布是關於樣本(而非總體)的t 變換值的分布，它是對u 變換變數值的標準正態分布的估計分布，是一位學生首先提出的，所以 t-分布全稱：學生t-分布。

其次，t-SNE本質是一種嵌入模型，能夠將高維空間中的數據映射到低維空間中，並保留數據集的局部特性。t-SNE 可以算是目前效果很好的數據降維和可視化方法之一。

缺點主要是佔用記憶體較多、運行時間長。

t-SNE變換後，如果在低維空間中具有可分性，則數據是可分的；如果在低維空間中不可分，則可能是因為數據集本身不可分，或者數據集中的數據不適合投影到低維空間。

該演算法在論文中非常常見，主要用於高維數據的降維和可視化。

Visualizing Data using t-SNE，2008年發表在Journal of Machine Learning Research，大神Hinton的文章：

http://www.jmlr.org/papers/v9/vandermaaten08a.html

3 t-SNE 原理描述

t-SNE將數據點之間的相似度轉化為條件概率，原始空間中數據點的相似度由高斯聯合分布表示，嵌入空間中數據點的相似度由學生t分布 表示。

通過原始空間和嵌入空間的聯合概率分布的KL散度（用於評估兩個分布的相似度的指標，經常用於評估機器學習模型的好壞）來評估嵌入效果的好壞。

也就是，將有關KL散度的函數作為損失函數（loss function），通過梯度下降演算法最小化損失函數，最終獲得收斂結果。

4 t-SNE 精華所在

t-SNE的精華都在以下這些文字：

在文中提到的論文中，主要討論降維出現的擁擠問題，解決的方法也很巧妙，一旦理解它後就明白為什麼叫t-分布隨機近鄰嵌入。

如果想像在一個三維的球裡面有均勻分布的點，不難想像，如果把這些點投影到一個二維的圓上一定會有很多點是重合的。

所以，為了在二維的圓上想儘可能表達出三維里的點的資訊，大神Hinton採取的方法：

把由於投影所重合的點用不同的距離（差別很小）表示。

這樣就會佔用原來在那些距離上的點，原來那些點會被趕到更遠一點的地方。

t分布是長尾的，意味著距離更遠的點依然能給出和高斯分布下距離小的點相同的概率值。

從而達到高維空間和低維空間對應的點概率相同的目的。

5 t-SNE降維對比分析

以MNIST數據集，降維並可視化為例，可以看到t-SNE 演算法明顯好於其他降維演算法：

在人臉數據集olivertti 上表現：

在哥倫比亞大學 Columbia University Image Library (COIL-20) 數據集上的表現：

6 sklearn實現t-SNE

import numpy as np  import matplotlib.pyplot as plt  from sklearn import datasets  from sklearn.manifold import TSNE      # 載入數據  def get_data():      """      :return: 數據集、標籤、樣本數量、特徵數量      """      digits = datasets.load_digits(n_class=10)      data = digits.data      # 圖片特徵      label = digits.target       # 圖片標籤      n_samples, n_features = data.shape      # 數據集的形狀      return data, label, n_samples, n_features      # 對樣本進行預處理並畫圖  def plot_embedding(data, label, title):      """      :param data:數據集      :param label:樣本標籤      :param title:影像標題      :return:影像      """      x_min, x_max = np.min(data, 0), np.max(data, 0)      data = (data - x_min) / (x_max - x_min)     # 對數據進行歸一化處理      fig = plt.figure()      # 創建圖形實例      ax = plt.subplot(111)       # 創建子圖      # 遍歷所有樣本      for i in range(data.shape[0]):          # 在圖中為每個數據點畫出標籤          plt.text(data[i, 0], data[i, 1], str(label[i]), color=plt.cm.Set1(label[i] / 10),                   fontdict={ weight :  bold ,  size : 10})      plt.xticks()        # 指定坐標的刻度      plt.yticks()      plt.title(title, fontsize=14)      # 返回值      return fig      # 主函數，執行t-SNE降維  def main():      data, label , n_samples, n_features = get_data()        # 調用函數，獲取數據集資訊      print( Starting compute t-SNE Embedding... )      ts = TSNE(n_components=2, init= pca , random_state=0)      # t-SNE降維      reslut = ts.fit_transform(data)      # 調用函數，繪製影像      fig = plot_embedding(reslut, label,  t-SNE Embedding of digits )      # 顯示影像      plt.show()      # 主函數  if __name__ ==  __main__ :      main()

結果：