本文主要是簡介 Tax 與 Duin 於 2004 年發表的著作 Support Vector Data Description。
什麼是異常檢測 anomaly detection
維基百科的 anomaly detection 是這樣說的："Anomaly detection is the identification of rare items, events or observations which raise
suspicions by differing significantly from the majority of the data." 意思是要找出與大多數樣本都不同的樣本。其中又分成兩個比較細的類別：Outlier detection 以及 Novelty detection，這篇 scikit-learn 的文件中有提到兩者的差別：主要差別是看訓練資料中是否已經包含了 outlier 的樣本。
One-Class SVM 簡介
One-Class SVM 的想法是把訓練資料訓練出一個類似於 Support Vector Machine (SVM) 概念的模型，再訂出一個是否為同一類別的標準。對於任何新的樣本，只要不符合此標準，那麼這個樣本便為異常的樣本。接下來要介紹的 Support Vector Data Description (SVDD) 就是實現這個想法的一種演算法。
Support Vector Data Description 簡介
SVDD 的想法是假設訓練資料分布在一個中心為 a，半徑為 R 的球中，也就是說對於每一個樣本 \(x_i\) 都滿足以下式子：
\[
(x_i - a)^T(x_i - a) \leq R^2
\]
引用 SVM 的想法，在上式中加入 slack variable \(\xi_i\) 來允許某些樣本可以不在這個球之中：
\[
(x_i - a)^T(x_i - a) \leq R^2 + \xi_i, \ \xi_i \geq 0
\]
我們想要找出的是一個最小的球，因此 loss function 為：
\[
\underset{a, \xi_i}{min}\ R^2 + C \sum_i \xi_i.
\\
s.t.(x_i - a)^T(x_i - a) \leq R^2 + \xi_i
\\
\forall \xi_i \geq 0
\]
要解這類型的優化問題時，當然就是拿出 Lagrange Multiplier（不熟的讀者可以閱讀前文）：
\[
\underset{a, \xi_i}{min}\ L(R, a, \alpha_i, \gamma_i, \xi_i) = R^2 + C \sum_i \xi_i - \sum_i \alpha_i \{R^2 + \xi_i - (x_i - a)^T(x_i - a)\} - \sum_i \gamma_i \xi_i
\]
對 R、a、\(\xi_i\) 取偏微分讓導數為零：
\[
\frac{\partial L}{\partial R} = 2R - 2R \sum_i \alpha_i = 0
\\
\frac{\partial L}{\partial a} = \sum_i \alpha_i (-2a + 2 x_i)
\\
\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \gamma_i = 0
\]
因此可以得到以下結果：
\[
\sum_i \alpha_i = 1
\\
a = \frac{\sum_i \alpha_i x_i}{\sum_i \alpha_i} = \sum_i \alpha_i x_i
\\
\alpha_i = C - \gamma_i
\]
將以上三個式子代回 L：
\[
\underset{a, \xi_i}{min}\ L(R, a, \alpha_i, \gamma_i, \xi_i) = R^2 + C \sum_i \xi_i - \sum_i \alpha_i \{R^2 + \xi_i - (x_i - a)^T(x_i - a)\} - \sum_i \gamma_i \xi_i
\\
= R^2 + C \sum_i \xi_i - \sum_i \alpha_i R^2 - \sum_i \alpha_i \xi_i + \sum_i \alpha_i (x_i - a)^T(x_i - a) - \sum_i \gamma_i \xi_i
\\
= C \sum_i \xi_i - \sum_i \alpha_i \xi_i + \sum_i \alpha_i (x_i - a)^T(x_i - a) - \sum_i \gamma_i \xi_i
\\
= C \sum_i \xi_i - \sum_i (C - \gamma_i) \xi_i + \sum_i \alpha_i (x_i - a)^T(x_i - a) - \sum_i \gamma_i \xi_i
\\
= \sum_i \alpha_i (x_i - a)^T(x_i - a)
\\
= \sum_i \alpha_i x_i^T x_i - 2 a^T x_i + a^T a
\\
= \sum_i \alpha_i x_i^T x_i - 2 \sum_i \alpha_i x_i^T x_i + \sum_i \sum_j \alpha_i \alpha_j x_i^T x_j
\\
= - \sum_i \alpha_i x_i^T x_i + \sum_i \sum_j \alpha_i \alpha_j x_i^T x_j
\]
上式求的是最小值，加負號等價於求最大值，並且因為 \(\alpha_i \leq 0, \gamma_i \leq 0\)，必須加上此約束\( 0 \leq \alpha_i \leq C\)：
\[
arg\ \underset{\alpha}{max}\ L = \sum_i \alpha_i x_i^T x_i - \sum_i \sum_j \alpha_i \alpha_j x_i^T x_j
\\
s.t.\ 0 \leq \alpha_i \leq C
\]
上面的式子就是個常見的二次規劃問題了。
判斷新樣本是否為異常樣本
當手上有一個新樣本 z 時，我們計算它與 a 的距離，如果距離大於 R 則這個樣本為異常樣本。計算的方法如下：
\[
f(z) = (z-a)^T(z-a)
\\
= z^Tz - 2 \sum_i \alpha_i z^T x_i + \sum_i \sum_j \alpha_i \alpha_j x_i^T x_j
\]
如果 f(z) 大於 R 的話那麼這個樣本便是異常樣本。
參考資料
[1] Support Vector Data Description, Tax and Duin, 2004
沒有留言:
張貼留言