SVM算法（十）将SVM推廣到單分類問題

在實際場景中，我們可能遇到這樣的問題：已知所有的訓練樣本均屬于一類，要求挖掘出其中的潛在模式，并将這種模式來判斷測試樣本是否屬于同類。

當然，我們可以通過基于顯式的距離計算來判斷新樣本與已知樣本簇的比對與否。這裡介紹兩種基于SVM的單分類模型，來解決此類問題。

一、OCSVM

該算法來源于Schölkopf。盡管名為One-Class-SVM，其實模型除了訓練樣本所屬的類外，隐藏了另外一個類——資料特征空間的零點。

是以，模型的基本思想為：在将所有資料劃分在分隔面遠離特征空間零點的條件下，最大化分隔面與零點間的距離。前者為限制條件，後者為目标函數。寫成數學表達式，即為： max ⁡ ρ ∣ ∣ w ∣ ∣ , ρ > 0 s . t . w x i − ρ > 0 \begin{aligned}&\max \frac{\rho}{||w||} ,\rho>0\\& s.t. \quad wx_i-\rho>0\end{aligned} ​max∣∣w∣∣ρ​,ρ>0s.t.wxi​−ρ>0​

對上述方程進行如下變換：

（1）将 ρ \rho ρ和 w w w的除法進行分離，轉換為加、減法優化目标；

（2）與标準SVM變換類似，引入非線性特征變換項，為後期的核函數引入做好準備；

（3）與标準SVM變換類似，引入分類錯誤的松弛變量。

在此基礎上，目标函數可改寫為：

min ⁡ w , ρ , ζ i 1 2 ∣ ∣ w ∣ ∣ 2 − ρ + 1 ν n ∑ i = 1 n ζ i s . t . w ϕ ( x i ) > ρ − ζ i , i = 1 , . . , n ζ i > 0 , ρ > 0 \begin{aligned}&\min_{w,\rho,\zeta_i}\frac{1}{2}||w||^2-\rho+\frac{1}{\nu n}\sum_{i=1}^n \zeta_i \\&s.t. \quad w\phi(x_i)>\rho-\zeta_i ,i=1,..,n\\&\qquad \zeta_i>0, \rho>0\end{aligned} ​w,ρ,ζi​min​21​∣∣w∣∣2−ρ+νn1​i=1∑n​ζi​s.t.wϕ(xi​)>ρ−ζi​,i=1,..,nζi​>0,ρ>0​上式中， ν \nu ν的作用和标準SVM中的懲罰系數 C C C作用相當，是以這種方法被稱為 ν \nu ν-SMV算法。

後面的推導和标準SVM類似，即轉變為拉格朗日的對偶問題，進而将求原特征空間參數 w w w變為求拉格朗日乘子 α \alpha α，最終的确定函數為： f ( x ) = s i g n ( ∑ i = 1 n α i K ( x , x i ) − ρ ) f(x)=sign(\sum_{i=1}^n \alpha_iK(x,x_i)-\rho) f(x)=sign(i=1∑n​αi​K(x,xi​)−ρ)若結果大于0，則判斷為同類，否則判定為異類。

二、SVDD

該算法來源于Tax and Duin。相較于标準SVM和OCSVM選用超平面的方法，其使用超平面來對資料進行分隔。

模型的基本思想為：在特征空間中得到資料周圍的某個球形邊界，使得該超球體的體積最小化。寫成數學表達式，即為： min ⁡ R , a R 2 s . t ∣ ∣ x i − a ∣ ∣ 2 ≤ R 2 , i = 1 , 2 , . . . n \begin{aligned}&\min_{R,a} R^2\\&s.t\quad||x_i-a||^2\le R^2,i=1,2,...n\end{aligned} ​R,amin​R2s.t∣∣xi​−a∣∣2≤R2,i=1,2,...n​引入松弛因子，可得優化目标： min ⁡ R , a R 2 + C ∑ i = 1 n ζ i s . t ∣ ∣ x i − a ∣ ∣ 2 ≤ R 2 + ζ i , i = 1 , 2 , . . . n \begin{aligned}&\min_{R,a} R^2+C\sum_{i=1}^n\zeta_i\\&s.t\quad||x_i-a||^2\le R^2+\zeta_i,i=1,2,...n\end{aligned} ​R,amin​R2+Ci=1∑n​ζi​s.t∣∣xi​−a∣∣2≤R2+ζi​,i=1,2,...n​上式中 ζ \zeta ζ為松弛變量， C C C為懲罰系數， R R R為目标超球面半徑， a a a為超球面球心坐标，可由超球面支援向量的線性組合得到。

在采用拉格朗日算子求解之後，可以判斷新的資料點 [公式] 是否在類内，如果z到中心的距離小于或者等于半徑。

三、小結

這種适用單分類的算法，主要使用在如下場景：

（1）尋找某一固定類樣本中的隐藏模式，進而判斷新的樣本是否屬于該類；

（2）正負樣本量極度不平衡的分類問題，可将其轉換為單分類問題。（嚴格來說并非outlier detection，而是novelty detection）