單類SVM：SVDD

話接上文(SVM的簡單推導)，這篇文章我們來看單類SVM：SVDD?？赡艽蠹視X得很奇怪，我們?yōu)槭裁葱枰獑畏诸惸兀?a target="_blank" rel="nofollow">有篇博客舉了一個很有意思的例子。

花果山上的老猴子，一生閱猴無數(shù)，但是從來沒有見過其它的物種。有一天，豬八戒來到花果山找它們的大王，老猴子一聲令下，把這個東西給我綁起來！

這里老猴子很清楚的知道這個外來物種不是同類，但是它究竟是什么，不得而知。老猴子見過很多猴，它知道猴子的特征，而外來生物明顯不符合這個特征，所以它就不是猴子。

這就是一個單分類的簡單例子。

而美猴王看到這個場景后，哈哈一笑，把這呆子抬過來！

對比二分類，顯著的區(qū)別就是，二分類不但能得出來這個東西不是猴子，他還能告訴你這個東西叫“呆子”（當然我們的美猴王見多識廣，肯定不止是二分類那么簡單了）

今天要介紹的SVDD的全稱是Support vector domain description。首先讓我們簡單了解一下domain description，也就是單分類問題。

單分類問題

不像常見的分類問題，單分類問題的目的并不時將不同類別的數(shù)據(jù)區(qū)分開來，而是對某個類別的數(shù)據(jù)生成一個描述（description）。這里的description比較抽象，可以理解為是樣本空間中的一個區(qū)域，當某個樣本落在這個區(qū)域外，我們就認為該樣本不屬于這個類別。

單分類問題

單分類方法常用于異常檢測，或者類別極度不平衡的分類任務中。

當我們假設數(shù)據(jù)服從一個概率分布，我們就可以對這個分布中的參數(shù)進行估計了。對于一個新樣本，如果這個樣本在給定類別的概率分布中的概率小于閾值，就會被判定為異常樣本。

但是這樣的方法存在的問題是，

  1. 預先假定的概率分布對模型性能的影響很大。
  2. 當特征的維度很大的時候，該方法需要一個很大的數(shù)據(jù)集。
  3. 一些低密度區(qū)域的樣本點會被誤判為異常樣本。

另一種思路就是，在樣本空間中為此類數(shù)據(jù)劃定一個大致的邊界。如何劃定這個邊界，就是SVDD要研究的問題啦。

目標函數(shù)

假設我們有m個樣本點，分別為x^{(1)},x^{(2)},\cdots,x^{(m)}。

我們假設這些樣本點分布在一個球心為a，半徑為R的球中。那么樣本x^{(i)}滿足
(x^{(i)}-a)^T(x^{(i)}-a)\leq R^2.
引入松弛變量，我們允許部分樣本不再這個球中，那么
(x^{(i)}-a)^T(x^{(i)}-a)\leq R^2+\xi_i,\xi\geq 0.
我們的目標是最小球的半徑R和松弛變量的值，于是目標函數(shù)是
\begin{align} \min_{a,\xi_i}\ \ & R^2+C\sum_{i=1}^m\xi_i\\ {\rm s.t.}\ \ & (x^{(i)}-a)^T(x^{(i)}-a)\leq R^2+\xi_i, \\ &\xi_i\geq 0,i=1,2,\cdots,m. \end{align}
其中，C>0是懲罰參數(shù)，由人工設置。

對偶問題

使用拉格朗日乘子法，得到拉格朗日函數(shù)
\begin{align} L(R,a,\alpha,\xi,\gamma)=& R^2+C\sum_{i=1}^m\xi_i\\ & -\sum_{i=1}^m\alpha_i\left(R^2+\xi_i({x^{(i)}}^Tx^{(i)}-2a^Tx^{(i)}+a^2)\right)-\sum_{i=1}^m \gamma_i\xi_i. \end{align}
其中，\alpha_i\ge 0,\gamma_i\ge 0是拉格朗日乘子。令拉格朗日函數(shù)對R,a,\xi_i的偏導為0，得到
\begin{align} &\sum_{i=1}^m \alpha_i=1,\\ &a=\sum_{i=1}^m \alpha_ix^{(i)},\\ &C-\alpha_i-\gamma_i=0 \end{align}
我們可以將\alpha_i看作樣本x^{(i)}的權重。上式表明所有樣本的權重之和為1，而球心a是所有樣本的加權和。將上式帶入到拉格朗日函數(shù)中，得到原問題的對偶問題
\begin{align} \max_\alpha\ \ &L(\alpha)=\sum_{i=1}^m\alpha_i{x^{(i)}}^Tx^{(i)}-\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_j{x^{(i)}}^Tx^{(j)}\\ {\rm s.t.}\ \ & 0\le\alpha_i\le C,\\ & \sum_{i=1}^m\alpha_i=1,i=1,2,\cdots,m. \end{align}
當通過求解對偶問題得到\alpha_i后，可以通過a=\sum_{i=1}^m \alpha_ix^{(i)}計算球心a。至于半徑R，則可以通過計算球與支持向量（\alpha_i< C）之間的距離得到。當\alpha_i=C時，意味著樣本x^{(i)}位于球的外面。

判斷新樣本是否為異常點

對于一個新的樣本點z，如果它滿足下式，那么我們認為它是一個異常點。
(z-a)^T(z-a)> R^2.
展開上式，得
z^Tz-2\sum_{i=1}^m \alpha_iz^Tx^{(i)}+\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j{x^{(i)}}^Tx^{(j)}>R^2.

引入核函數(shù)

正常情況下，數(shù)據(jù)并不會呈現(xiàn)球狀分布，因此有必要使用核函數(shù)的方法提高模型的表達能力。

只需將\cal K(x^{(i)},x^{(j)})替換{x^{(i)}}^Tx^{(j)}即可。于是對偶問題的目標函數(shù)變?yōu)?br> L(\alpha)=\sum_i \alpha_i\cal K(x^{(i)},x^{(i)})-\sum_i\sum_j \alpha_i\alpha_j\cal K(x^{(i)},x^{(j)}).
判別函數(shù)變?yōu)?br> {\cal K}(z,z)-2\sum_i \alpha_i {\cal K}(z,x^{(i)})+\sum_i\sum_j \alpha_i\alpha_j {\cal K}(x^{(i)},x^{(j)})- R^2.
下面考慮核函數(shù)的影響。

多項式核

多項式核函數(shù)的表達式如下
{\cal K}\left({x^{(i)}}^Tx^{(j)}\right)=\left({x^{(i)}}^Tx^{(j)}+1\right)^d.
如下圖所示，多項式核實際上不太適合SVDD。特別是當d取值非常大的時候。

在不同的d值下，超球體邊界的變化

高斯核

高斯核函數(shù)的表達式如下
{\cal K}\left({x^{(i)}}^Tx^{(j)}\right)=\exp\left(\frac{-\left(x^{(i)}-x^{(j)}\right)^2}{s^2}\right).
如下圖，相比于多項式核函數(shù)，高斯核函數(shù)的結果就合理多了?？梢钥吹侥Ｐ偷膹碗s程度隨著s的增大而減小。

在不同的s值下，超球體邊界的變化

在python中使用

可通過下面的代碼在python中使用單類SVM

from sklearn.svm import OneClassSVM

參考文獻

  1. Tax D M J, Duin R P W. Support vector domain description[J]. Pattern recognition letters, 1999, 20(11-13): 1191-1199.
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容