機器學習-異常檢測演算法（三）：Principal Component Analysis

01-27

Principal Component Analysis（PCA）是最常見的數據降維的方法。根據 Wikipedia 的介紹，它最早是由 Karl Pearson（同時也是卡方檢驗的發明者）在1901年提出，到現在已經一百多年了。作為一種降維的方法，PCA可以將原數據進行線性變換，並找出數據中信息含量最大的主要成分，去除信息含量較低的成分，從而減少冗餘，降低噪音。通常在異常檢測的語境里，噪音（noise）、離群點（outlier）和異常值（anomaly）是同一件事情的不同表述。所以，PCA既然可以識別噪音，自然也可以檢測異常。

PCA的相關概念

我們先簡單回顧一下 PCA的相關概念。假設原始數據是一個 $mtimes{n}$ 的矩陣，這裡m表示數據樣本的數量，n表示每一條數據樣本的特徵數目。一般的，我們先要對原始數據做一些預處理：

1. 中心化：將原始數據每一列進行零均值化，即將該列上的每一個數值都減去該列的均值。

2. 歸一化：將中心化之後的數據的每一列進行方差歸一化，即將該列上的每一個數值都除以該列的標準差。

上面的兩步預處理是通常做法。中心化的主要目的是讓後面的公式描述更簡潔，並不影響特徵值分解。歸一化是為了讓不同變數的方差變化尺度控制在相同的範圍內，消除不同量綱的影響，使得它們更有可比性。我們將預處理之後的矩陣表示為 $X$ ，則 PCA 的主要步驟如下：

計算協方差矩陣 $C=frac{1}{m-1}X^{T}X$
求解協方差矩陣的特徵值 $lambda_{1}, lambda_{2}, ldots ,lambda_{i}$ 和特徵向量 $bf{e_{1}},bf{e_{2}},ldots, bf{e_{i}}$
按照特徵值從大到小的順序，將特徵向量從左至右排列，將前k個特徵向量組成的矩陣表示為 $P_{k}$
將 $X$ 映射到低維的k維空間（ $kll{n}$ ），則映射之後的數據 $Y_{k}=XP_{k}$

為了更清楚的理解步驟4里的「映射」操作，我們可以拿單個數據樣本 $bf{x}$ 和特徵向量 $bf{e_j}$ 來舉例。根據步驟4中的公式，樣本 $bf{x}$ 在特徵向量 $bf{e_j}$ 方向上的坐標為 $bf{x^{T}}cdotbf{{e_j}}$ 。回想一下關於點乘的幾何定義，我們有：

$bf{x^{T}}cdotbf{{e_j}}=|bf{x^{T}}|cdot|bf{e_j}|cdotcos theta$

這裡 $theta$ 為點乘的兩個向量的夾角，這裡 $bf{e_j}$ 是長度為1的單位向量，所以 $bf{x^{T}}cdotbf{{e_j}}=|bf{x^{T}}|cdotcos theta$ ，剛好為樣本 $bf{x}$ 在特徵向量 $bf{e_j}$ 方向上的投影（坐標）。如果把所有數據點的映射用矩陣的形式表示出來，那就是步驟4的公式了。

我們將原始數據映射到低維空間之後，也可以根據數據在低維空間里的坐標來重構原始數據。PCA的其中一種推導方式就是基於重構誤差得到的。假設數據樣本 $bf{x_i}$ 映射到 k 維空間的坐標為 ${y_1,y_2,ldots,y_k}$ , 則基於該 k 維坐標重構的數據為：

${bf {x}_{ik}} = sum_{i=1}^{k}y_i{bf e_i}$

上面的重構公式比較直觀，即：重構的數據坐標為數據在低維空間每個方向上的坐標乘以該方向上的單位向量之後的求和。如果把所有數據樣本的重構用矩陣的形式表示出來，則：

${X} = {Y_k}P_{k}^{T}$

後面我們在描述PCA用於異常檢測的時候還會用到這裡的重構公式。

PCA用於異常檢測

PCA在異常檢測方面的做法，大體有兩種思路：一種是將數據映射到低維特徵空間，然後在特徵空間不同維度上查看每個數據點跟其它數據的偏差；另外一種是將數據映射到低維特徵空間，然後由低維特徵空間重新映射回原空間，嘗試用低維特徵重構原始數據，看重構誤差的大小。兩種思路看似不太一樣，其實本質上是差不多的。

我們先來講講第一種思路。PCA在做特徵值分解之後得到的特徵向量反應了原始數據方差變化程度的不同方向，特徵值為數據在對應方向上的方差大小。所以，最大特徵值對應的特徵向量為數據方差最大的方向，最小特徵值對應的特徵向量為數據方差最小的方向。原始數據在不同方向上的方差變化反應了其內在特點。如果單個數據樣本跟整體數據樣本表現出的特點不太一致，比如在某些方向上跟其它數據樣本偏離較大，可能就表示該數據樣本是一個異常點。

對於某一個特徵向量 $bf{e_j}$ ，數據樣本 $bf{x_i}$ 在該方向上的偏離程度 $d_{ij}$ 可以用如下的公式計算：

$d_{ij} = frac{(bf{x_i}^{T}cdotbf{e_j})^2}{lambda_{j}}$

這裡的 $lambda_j$ 主要起歸一化的作用，這樣可以使得不同方向上的偏離程度具有可比性。在計算了數據樣本在所有方向上的偏離程度之後，為了給出一個綜合的異常得分，最自然的做法是將樣本在所有方向上的偏離程度加起來，即：

$Score({bf{x_i}})=sum_{j=1}^n{d_{ij}}=sum_{j=1}^{n}frac{(bf{x_i}^{T}cdotbf{e_j})^2}{lambda_{j}}$

這個公式只是計算異常得分的一種方式。也有一些演算法採取了略微不同的做法，比如，有的只考慮數據在前 k 個特徵向量方向上的偏差，或者只考慮後 r 個特徵向量方向上的偏差，即：

$sum_{j=1}^{k}d_{ij} > C_1 quad or quad sum_{j=n-r+1}^{n}d_{ij} > C_2$

這裡的 $C_1$ 和 $C_2$ 是人為設定的兩個閾值，如果得分大於閾值則判斷為異常。

一般而言，前幾個特徵向量往往直接對應原始數據里的某幾個特徵，在前幾個特徵向量方向上偏差比較大的數據樣本，往往就是在原始數據中那幾個特徵上的極值點。而後幾個特徵向量有些不同，它們通常表示某幾個原始特徵的線性組合，線性組合之後的方差比較小反應了這幾個特徵之間的某種關係。在後幾個特徵方向上偏差比較大的數據樣本，表示它在原始數據里對應的那幾個特徵上出現了與預計不太一致的情況。到底是考慮全部特徵方向上的偏差，前幾個特徵向量上的偏差，還是後幾個特徵向量上的偏差，在具體使用時可以根據具體數據靈活處理。

前面提到，PCA用於異常檢測時候，還有一種思路是基於重構誤差的。直觀上理解，PCA提取了數據的主要特徵，如果一個數據樣本不容易被重構出來，表示這個數據樣本的特徵跟整體數據樣本的特徵不一致，那麼它顯然就是一個異常的樣本。對於數據樣本 $bf{x_i}$ , 假設其基於 k 維特徵向量重構的樣本為 $bf{x_{ik}}$ , 則該數據樣本的異常得分可以用如下的公式計算：

$Score(x_i) = sum_{k=1}^{n}(|{bf x_i} -{bf x_{ik}}|)times{ev(k)}$

$ev(k)=frac{sum_{j=1}^{k}lambda_{j}}{sum_{j=1}^{n}lambda_j}$

上面的公式考慮了重構使用的特徵向量的個數 k 的影響，將 k 的所有可能做了一個加權求和，得出了一個綜合的異常得分。顯然，基於重構誤差來計算異常得分的公式也不是唯一的，這裡只是其中的一種做法。

根據前面一節提到的重構公式，我們在基於低維特徵進行數據樣本的重構時，捨棄了較小的特徵值對應的特徵向量方向上的信息。換一句話說，重構誤差其實主要來自較小的特徵值對應的特徵向量方向上的信息。基於這個直觀的理解，PCA在異常檢測上的兩種不同思路都會特別關注較小的特徵值對應的特徵向量。所以，我們說PCA在做異常檢測時候的兩種思路本質上是相似的。

演算法延伸

PCA 是一種線性的數據降維的方法，為了識別一些更為複雜的異常，最自然的做法是應用 kernel PCA。就異常檢測的使用方式而言，kernel PCA 並無太大差異，這裡就不做贅述。

在深度學習大行其道的今天，另外一種備受關注的數據降維的方法是深度學習中的 Autoencoder。它跟PCA的差別主要是非線性和線性的差別。相信很多人看到前面基於PCA的重構誤差進行異常檢測時，也意識到了 Autoencoder 也可以以類似的方式做異常檢測。而 Autoencoder 有很多種不同的類型，比如 Denoising Autoencoder，Variational Autoencoder 等等，後面我們可以用單獨的篇幅再來具體講解如何用它們來做異常檢測。

參考文獻

1. Veeramachaneni, K., Arnaldo, I., Korrapati, V., Bassias, C., Li, K.: AI^2 : training a big data machine to defend. In: 2016 IEEE 2nd International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing (HPSC), and IEEE International Conference on Intelligent Data and Security (IDS), pp. 49–54 (2016)

2. Shyu M L, Chen S C, Sarinnapakorn K, et al. A novel anomaly detection scheme based on principal component classifier. ICDM, 2003.