摘要：話接上文的簡單推導(dǎo)，這篇文章我們來看單類。單分類方法常用于異常檢測，或者類別極度不平衡的分類任務(wù)中。另一種思路就是，在樣本空間中為此類數(shù)據(jù)劃定一個大致的邊界。上式表明所有樣本的權(quán)重之和為，而球心是所有樣本的加權(quán)和。

話接上文(SVM的簡單推導(dǎo))，這篇文章我們來看單類SVM：SVDD?？赡艽蠹視X得很奇怪，我們?yōu)槭裁葱枰獑畏诸惸兀坑衅┛团e了一個很有意思的例子。

花果山上的老猴子，一生閱猴無數(shù)，但是從來沒有見過其它的物種。有一天，豬八戒來到花果山找它們的大王，老猴子一聲令下，把這個東西給我綁起來！
這里老猴子很清楚的知道這個外來物種不是同類，但是它究竟是什么，不得而知。老猴子見過很多猴，它知道猴子的特征，而外來生物明顯不符合這個特征，所以它就不是猴子。
這就是一個單分類的簡單例子。
而美猴王看到這個場景后，哈哈一笑，把這呆子抬過來！
對比二分類，顯著的區(qū)別就是，二分類不但能得出來這個東西不是猴子，他還能告訴你這個東西叫“呆子”（當(dāng)然我們的美猴王見多識廣，肯定不止是二分類那么簡單了）

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

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

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

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

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

預(yù)先假定的概率分布對模型性能的影響很大。

當(dāng)特征的維度很大的時候，該方法需要一個很大的數(shù)據(jù)集。

一些低密度區(qū)域的樣本點會被誤判為異常樣本。

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

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

我們假設(shè)這些樣本點分布在一個球心為$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,xigeq 0. $$

我們的目標(biāo)是最小球的半徑$R$和松弛變量的值，于是目標(biāo)函數(shù)是

$$ egin{align} min_{a,xi_i} & R^2+Csum_{i=1}^mxi_i { m s.t.} & (x^{(i)}-a)^T(x^{(i)}-a)leq R^2+xi_i, &xi_igeq 0,i=1,2,cdots,m. end{align} $$

其中，$C>0$是懲罰參數(shù)，由人工設(shè)置。

使用拉格朗日乘子法，得到拉格朗日函數(shù)

$$ egin{align} L(R,a,alpha,xi,gamma)=& R^2+Csum_{i=1}^mxi_i & -sum_{i=1}^malpha_ileft(R^2+xi_i({x^{(i)}}^Tx^{(i)}-2a^Tx^{(i)}+a^2) ight)-sum_{i=1}^m gamma_ixi_i. end{align} $$

其中，$alpha_ige 0,gamma_ige 0$是拉格朗日乘子。令拉格朗日函數(shù)對$R,a,xi_i$的偏導(dǎo)為0，得到

$$ egin{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)}$的權(quán)重。上式表明所有樣本的權(quán)重之和為1，而球心$a$是所有樣本的加權(quán)和。將上式帶入到拉格朗日函數(shù)中，得到原問題的對偶問題

$$ egin{align} max_alpha &L(alpha)=sum_{i=1}^malpha_i{x^{(i)}}^Tx^{(i)}-sum_{i=1}^msum_{j=1}^m alpha_ialpha_j{x^{(i)}}^Tx^{(j)} { m s.t.} & 0lealpha_ile C, & sum_{i=1}^malpha_i=1,i=1,2,cdots,m. end{align} $$

當(dāng)通過求解對偶問題得到$alpha_i$后，可以通過$a=sum_{i=1}^m alpha_ix^{(i)}$計算球心$a$。至于半徑$R$，則可以通過計算球與支持向量（$alpha_i< C$）之間的距離得到。當(dāng)$alpha_i=C$時，意味著樣本$x^{(i)}$位于球的外面。

對于一個新的樣本點$z$，如果它滿足下式，那么我們認(rèn)為它是一個異常點。

$$ (z-a)^T(z-a)> R^2. $$

展開上式，得

$$ z^Tz-2sum_{i=1}^m alpha_iz^Tx^{(i)}+sum_{i=1}^msum_{j=1}^malpha_ialpha_j{x^{(i)}}^Tx^{(j)}>R^2. $$

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

只需將$cal K(x^{(i)},x^{(j)})$替換${x^{(i)}}^Tx^{(j)}$即可。于是對偶問題的目標(biāo)函數(shù)變?yōu)?/p>

$$ L(alpha)=sum_i alpha_ical K(x^{(i)},x^{(i)})-sum_isum_j alpha_ialpha_jcal K(x^{(i)},x^{(j)}). $$

判別函數(shù)變?yōu)?/p>

$$ {cal K}(z,z)-2sum_i alpha_i {cal K}(z,x^{(i)})+sum_isum_j alpha_ialpha_j {cal K}(x^{(i)},x^{(j)})- R^2. $$

下面考慮核函數(shù)的影響。

多項式核

多項式核函數(shù)的表達(dá)式如下

$$ {cal K}left({x^{(i)}}^Tx^{(j)} ight)=left({x^{(i)}}^Tx^{(j)}+1 ight)^d. $$

如下圖所示，多項式核實際上不太適合SVDD。特別是當(dāng)d取值非常大的時候。

高斯核

高斯核函數(shù)的表達(dá)式如下

$$ {cal K}left({x^{(i)}}^Tx^{(j)} ight)=expleft(frac{-left(x^{(i)}-x^{(j)} ight)^2}{s^2} ight). $$

如下圖，相比于多項式核函數(shù)，高斯核函數(shù)的結(jié)果就合理多了?？梢钥吹侥Ｐ偷膹?fù)雜程度隨著$s$的增大而減小。

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

from sklearn.svm import OneClassSVM

Tax D M J, Duin R P W. Support vector domain description[J]. Pattern recognition letters, 1999, 20(11-13): 1191-1199.