2020年7月3日 星期五

One-Class SVM:檢測出異常的樣本(Anomaly Detection)

本文主要是簡介 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 的話那麼這個樣本便是異常樣本。

沒有留言:

張貼留言