Question

5.1 one class 分类

1. 通常分类问题是两类或者多类，但有一种分类为一类one class 的分类问题：它只有一个类，预测结果为是否属于这个类。

2. 一类分类的策略是：训练出一个最小的超球面把正类数据包起来。识别一个新的数据点时，如果这个数据点落在超球面内，则属于正类；否则不是。

3. 示例：给定一些用户的购物行为日志，其中包括两类用户：

   • 购买了某个商品的用户。可以肯定该类用户对于该商品是感兴趣的（标记为正例）。
   • 未购买某个商品的用户。此时无法断定该用户是对该商品感兴趣，还是不感兴趣（无法标记为反例）。

   现在给定一群新的用户，预测这些用户中，哪些可能对该商品有兴趣。

   如果简单的使用二类分类问题，则有两个问题：

   • 未购买商品的用户，不一定是对该商品不感兴趣，可能是由于某些原因未能购买。
   • 通常未购买商品的用户数量远大于购买用户的数量。如果使用二类分类，则容易造成正负样本不均匀。

5.2 SVDD 算法

1. support vector domain description:SVDD可以用于一类分类问题。

2. 给定训练集 $ MathJax-Element-378 $ ，这些样本都是属于同一类。SVDD 的的优化目标是：求一个中心为 $ MathJax-Element-379 $ ，半径为 $ MathJax-Element-380 $ 的最小球面，使得 $ MathJax-Element-381 $ 中的样本都在该球面中。

3. 类似SVR，SVDD 允许一定程度上的放松，引入松弛变量。对松弛变量 $ MathJax-Element-382 $ ，其代价为 $ MathJax-Element-383 $ 。

   $ L(R,\mathbf{\vec o},\vec\xi)=R^2+C\sum_{i=1}^{N}\xi_i\\ s.t.\quad ||\mathbf{\vec x}_i-\mathbf{\vec o}||_2^2\le R^2+\xi_i\\ \xi_i\ge 0\\ i=1,2,\cdots,N $

   其中 $ MathJax-Element-384 $ 为惩罚系数：​

   • 若 $ MathJax-Element-504 $ 较大，则不能容忍那些球面之外的点，因此球面会较大。
   • 若 $ MathJax-Element-504 $ 较小，则给予球面之外的点较大的弹性，因此球面会较小。

4. SVDD 的求解也是采用拉格朗日乘子法：

   $ L(R,\mathbf{\vec o},\vec\alpha,\vec\xi,\vec\gamma)=R^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i\left(R^2+\xi_i-||\mathbf{\vec x}_i-\mathbf{\vec o}||_2^2\right)-\sum_{i=1}^{N}\gamma_i\xi_i\\ s.t. \alpha_i\ge 0,\gamma_i\ge 0,\xi_i\ge 0 $
   • 根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题： $ MathJax-Element-387 $ 。
   • 先求极小问题：根据 $ MathJax-Element-388 $ 对 $ MathJax-Element-389 $ 偏导数为零可得：
   $ \sum_{i=1}^{N}\alpha_i=1\\ \mathbf{\vec o}=\frac{\sum_{i=1}^N\alpha_i\mathbf{\vec x}_i}{\sum_{i=1}^N\alpha_i}=\sum_{i=1}^N\alpha_i\mathbf{\vec x}_i\\ C-\alpha_i-\gamma_i=0,i=1,2,\cdots,N $
   • 代入拉格朗日函数有：
   $ L=\sum_{i=1}^{N}\alpha_i(\mathbf{\vec x}_i\cdot \mathbf{\vec x}_i)-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j(\mathbf{\vec x}_i\cdot \mathbf{\vec x}_j)\\ s.t. 0\le \alpha_i\le C\\ \sum_{i=1}^N\alpha_i=1 $

   • 引入核函数：

     $ L=\sum_{i=1}^{N}\alpha_iK(\mathbf{\vec x}_i, \mathbf{\vec x}_i)-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jK(\mathbf{\vec x}_i, \mathbf{\vec x}_j)\\ s.t. 0\le \alpha_i\le C\\ \sum_{i=1}^N\alpha_i=1 $

     其解法类似支持向量机的解法。

5. 判断一个新的数据点 $ MathJax-Element-390 $ 是否属于这个类，主要看它是否在训练出来的超球面内：若 $ MathJax-Element-391 $ ，则判定为属于该类。

   • 如果使用支持向量，则判定准则为： $ MathJax-Element-392 $ 。
   • 如果是用核函数，则判定准则为： $ MathJax-Element-393 $ 。