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）