降維技術解析：PCA, t-SNE and Auto Encoders

02-25

降維技術對於統計學專業的同學來說並不陌生，特別是PCA和LDA，算是玩得比較溜的演算法之一。我們可能認為用PCA降低了輸入數據的維度同時保有了主要信息，將是解決過擬合的有效方法，但由於PCA整個方案都不考慮我們結果的值y，因此在實際工作或者打比賽中，PCA並不被推薦用來避免過擬合，還是老老實實的用正則化吧。自編碼器作為一種神經網路降維技術，近年來越來越流行，最近在看谷歌和uber發表的一些paper的時候，常常能看到自編碼器技術的應用。因此借這個機會梳理一下三大維降維技術：PCA，t-SNE和自編碼器。

PCA （Principal Component Analysis，主成分分析）

PCA通過正交變換將一組可能存在相關性的變數轉換為一組線性不相關的變數，即把多指標轉化為少數幾個綜合指標，轉換後的這組變數就叫做主成分，其中每個主成分都能夠反映原始變數的大部分信息，且所含信息互不重複，以此達到降維的目的。

1.演算法步驟

設有 $m$ 條 $n$ 維數據。

將原始數據按列組成 $n$ 行 $m$ 列矩陣 $X$ ；
將 $X$ 的每一行（代表一個屬性欄位）進行零均值化，即減去這一行的均值；
求出協方差矩陣 $C=frac{1}{m}XX^{T}$ ；
求出協方差矩陣的特徵值及對應的特徵向量；
將特徵向量按對應特徵值大小從上到下按行排列成矩陣，取前 $k$ 行組成矩陣 $P$ ；
$Y=PX$ 即為降維到k維後的數據。

2.數學原理

PCA中有兩個很重要的思想：

最大可分性思想，即樣本點在超平面上的投影能儘可能的分開。基於最大可分性思想，我們要找的方向是使得降維後損失最小的方向，可以理解為投影后的數據儘可能的分開，這種分散程度可以用數學上的方差來表示，方差越大數據越分散。
主成分相互獨立思想，即主成分之間不能存在線性相關性的，不然的話必然存在重複表示的信息，那麼第二個主成分只能在與第一個主成分正交的方向上選擇。

協方差矩陣就代表了欄位與欄位之間的相關關係，因此我們的目標就是協方差矩陣對角化，並且在對角線上將元素按大小從上到下排列。這個協方差矩陣是對稱的，我們知道，實對稱矩陣是一定能對角化的。

我們進一步看下原協方差矩陣與基變換後的對角陣之間的關係：設原始數據矩陣 $X$ 對應的協方差矩陣為 $C$ ，而 $P$ 是一組基按行組成的矩陣，設 $Y=PX$ ，則 $Y$ 為 $X$ 對 $P$ 做基變換後的數據。設 $Y$ 的協方差矩陣（對角陣）為 $D$ ，我們推導一下 $D$ 與 $C$ 的關係：

$egin{align} D &= frac{1}{m}YY^ op \ &=frac{1}{m}(PX)(PX)^ op\ &= frac{1}{m}PX X^ op P^ op\ &= P(frac{1}{m}X X^ op) P^ op\ &=PCP^ opend{align}$

其中，P的每一行都是C的一個特徵向量。

降維投影可視化效果

t-SNE

t-SNE演算法仿射(affinitie)變換將數據點映射到概率分布上，利用條件概率來衡量數據點之間的相似性，通過使數據集在高維和低維兩個空間的條件概率儘可能接近，將數據從高維空間映射到低維空間。通過t-SNE降維不僅可以保持數據的差異性，而且可以很好地保持數據的局部結構。

1.演算法步驟

t-SNE演算法步驟如下圖所示。

t-SNE演算法步驟

2.數學原理

下面就寫一下自己在閱讀時對於這個流程中每一步的理解，序號對應圖中的序號。

（0）演算法的輸入有兩個：

$n$ 條 $m$ 維數據；
$Perp$ ，困惑度。困惑度可以解釋為一個點附近的有效近鄰點個數，SNE對困惑度的調整比較有魯棒性，通常選擇5-50之間。

（1）是SNE演算法中設置的一個條件概率用來衡量高維數據的相似性， $p_{j|i}$ 衡量的是數據點 $j$ 作為數據點 $i$ 的鄰域的概率； $σ$ 是方差，這個方差大小與輸入的困惑度有關。

（2）是為了解決引入異常值的問題，比如 $x_i$ 是異常值，那麼 $||x_i?x_j||^{2}$ 會很大，對應的所有的 $j$ ， $p_{ij}$ 都會很小，導致低維映射下的 $y_i$ 對損失函數影響很小。為了解決這個問題，將聯合概率分布定義修正為： $p_{ij}=frac{p_{i∣j}+p_{j∣i}}{2}$ ，使得每個點對於損失函數都會有一定的貢獻。

（3）—（4）不太理解為什麼 $Y$ 是 $n*n$ 維的，按道理說 $Y$ 是最終的輸出，維度應該是 $n*n\_components$ 。

（5）是SNE演算法中設置的一個條件概率用來衡量低維數據的相似性。

（6） $Q_{n,n}$ 表示低維數據集中所有其他數據點之間的相對條件概率。

（7）是目標函數(cost function)，是兩個分布之間的距離-KL散度(Kullback-Leibler divergences)。

（4）（5）（6）（7）是個循環，通過不斷地利用梯度下降演算法，得到最優解。

Auto Encoders（自編碼器）

自編碼器是一種用於高效編碼的無監督學習人工神經網路，其目標是通過使用比輸入節點更少的隱藏節點（在編碼器一端）預測輸入（訓練該網路使其輸出儘可能與輸入相似），為此該網路需要儘可能多地將信息編碼到隱藏節點中。

在結構上，自編碼器的最簡單形式是一個前饋非遞歸神經網路，它與多層感知器（MLP）非常相似，具有輸入層、輸出層以及連接它們的一個或多個隱藏層。然而自編碼器和MLP之間的差異在於，在自編碼器中，輸出層具有與輸入層相同數量的節點，並且不是訓練預測給定的目標值，而是將它們自己作為目標值投入訓練。因此自編碼器屬於無監督學習模型。

自編碼器總是由兩個部分組成，編碼器和解碼器。在最簡單的情況下，一個自編碼器只有一個隱藏層，該隱藏層接收輸入並將其映射到輸出上（如下圖所示）。自編碼器也是被訓練以最小化損失函數（例如MSE）：

如上所述，自編碼器主要致力於減少特徵空間，以提取數據的基本特徵，而傳統的深度學習則擴大了特徵空間，捕捉數據中的非線性和微妙的相互作用。自編碼器也可以看作PCA的非線性替代。

具有單個隱藏層的自編碼器示意結構

代碼實現

引用莫煩大神的代碼來看一下如何實現一個Autoencoder。

"""To know more or get code samples, please visit my website:https://morvanzhou.github.io/tutorials/Or search: 莫煩PythonThank you for supporting!"""# please note, all tutorial code are running under python3.5.# If you use the version like python2.7, please modify the code accordingly# 9 - Autoencoder example# to try tensorflow, un-comment following two lines# import os# os.environ[KERAS_BACKEND]=tensorflowimport numpy as npnp.random.seed(1337) # for reproducibilityfrom keras.datasets import mnistfrom keras.models import Modelfrom keras.layers import Dense, Inputimport matplotlib.pyplot as plt# download the mnist to the path ~/.keras/datasets/ if it is the first time to be called# X shape (60,000 28x28), y shape (10,000, )(x_train, _), (x_test, y_test) = mnist.load_data()# data pre-processingx_train = x_train.astype(float32) / 255. - 0.5 # minmax_normalizedx_test = x_test.astype(float32) / 255. - 0.5 # minmax_normalizedx_train = x_train.reshape((x_train.shape[0], -1))x_test = x_test.reshape((x_test.shape[0], -1))print(x_train.shape)print(x_test.shape)# in order to plot in a 2D figureencoding_dim = 2# this is our input placeholderinput_img = Input(shape=(784,))# encoder layersencoded = Dense(128, activation=relu)(input_img)encoded = Dense(64, activation=relu)(encoded)encoded = Dense(10, activation=relu)(encoded)encoder_output = Dense(encoding_dim)(encoded)# decoder layersdecoded = Dense(10, activation=relu)(encoder_output)decoded = Dense(64, activation=relu)(decoded)decoded = Dense(128, activation=relu)(decoded)decoded = Dense(784, activation=tanh)(decoded)# construct the autoencoder modelautoencoder = Model(input=input_img, output=decoded)# construct the encoder model for plottingencoder = Model(input=input_img, output=encoder_output)# compile autoencoderautoencoder.compile(optimizer=adam, loss=mse)# trainingautoencoder.fit(x_train, x_train, epochs=20, batch_size=256, shuffle=True)# plottingencoded_imgs = encoder.predict(x_test)plt.scatter(encoded_imgs[:, 0], encoded_imgs[:, 1], c=y_test)plt.colorbar()plt.show()

參考資料

PCA 的數學原理和可視化效果www.jianshu.com

機器之心：基於TensorFlow理解三大降維技術：PCA、t-SNE 和自編碼器zhuanlan.zhihu.com

t-SNE完整筆記www.datakit.cn

機器學習: t-Stochastic Neighbor Embedding 降維演算法 (一)blog.csdn.net

機器學習: t-Stochastic Neighbor Embedding 降維演算法 (二)blog.csdn.netAnomaly Detection in Time Series using Auto Encodersphilipperemy.github.io

推薦閱讀：

徐小賤民：FingercrossAI鏈接匯總zhuanlan.zhihu.com