编写人：ceys/youyis

最后更新时间：2014.5.27

##一、算法描述

###1.原理 SVM(support vector machine,支持向量机)是一种二分类的模型。支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机及非线性支持向量机。简单模型是复杂模型的基础，也是复杂模型的特殊情况。

支持向量机学习的基本想法是求解能够正确划分训练数据集并且间隔最大的分离超平面。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面,意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点也有足够打的确信度将它们分开，如下图所示(线性可分的情况)。

'f'

####间隔最大化的角度叙述 由于线性可分支持向量机、线性支持向量机是非线性支持向量机的特例，我们叙述非线性支持向量机作为通用形式。

输入：训练数据集$T = \left { (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N}) \right } $,其中$x_{i}\in\mathbb{R}^{n},y_{1}\in\left {-1,+1 \right } ,i = 1,2,...,N$;

输出：分类决策函数

1） 选取适当的核函数$K(x,z)$和适当的参数C,构造并求解最优化问题 $$\underset{a}{min} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}y_{i}y_{j}K(x_{i},x_{j}) - \sum_{j=1}^{N}a_{i} $$

$$ s.t. \sum_{j=1}^{N}a_{i}y_{i} = 0$$

$$0\leq a_{i}\leq C,i = 1,2,...,N$$

求得最优解 $a^{}=(a_{1}^{},a_{2}^{},...,a_{N}^{})$

2)选择$a^{}$的一个正分量$0\leq a_{j}^{}\leq C$,计算

$$ b^{} = y_{j} - \sum_{j=1}^{N}a_{i}^{}y_{i}K(x_{i},x_{j})$$

3. 构造决策函数： $$ f(x) = sign(\sum_{j=1}^{N}a_{i}^{}y_{i}K(x.x_{i}) + b^{})$$

当$K(x,z)$是正定核函数时，上述最优化问题是凸二次规划问题，解是存在的。

####损失函数的角度叙述 线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：

$$\sum_{j=1}^{N}\left [ 1 - y_{i}(w.x_{i} + b) \right ]_{+} + \lambda \left | w\right |^{2}$$

目标函数的第一项是经验损失或经验风险，函数

$$ L(y_{i}(w.x_{i} + b) = \left [ 1 - y_{i}(w.x_{i} + b) \right ]_{+}$$

称为合页损失函数(hinge loss function).下标“+”表示以下取正值的函数

$$\left [ z\right ]_{+} = \left{\begin{matrix} z,& z>0\\ 0,& z\leq 0 \end{matrix}\right.$$

当样本点$(x_{i},y_{i})$被正确分类且函数间隔$ y_{i}(w.x_{i} + b)$大于1时，损失是0，否则损失是$1 - y_{i}(w.x_{i} + b)$。

####适用性 1 由于svm是通过是结构化风险最小化来求解，可以在样本量很少的情况下，达到比较好的效果，可有效处理小样本过拟合问题。

2 svm引进了核函数有效，可有效处理非线性及高维模式识别问题。

###2.伪代码：

###3.并行化方法

###4.文献

• wikipedia support vector machine

• 统计学习方法 李航

##二、具体实现及调用

##三、案例描述

###1. 业务问题描述及分析

• ####问题描述 电商中不断有新用户的注册，也有用户的流失，如何提前预测可能流失的用户，以通过营销活动重新激活并挽留他们？

• ####分析 首先我们定义：历史有购物行为，但后来6个月内没有下过单的用户为流失用户。拟通过流失前的最后一次购物行为及历史购物行为，来预测用户是否会流失。选取的特征为，关于最后一次购物行为的特征选取：是否投诉、是否退换、是否差评、退货是否成功4个特征；关于历史的购物行为选取历史购物频次这个特征。基于这5个特征及流失与否的分类变量，构建logistic模型，来提前6个月预测用户是否会流失。

###2. 数据的准备

###3. 算法的运行及模型生成

###4. 模型的评估 对于一个分类问题我们通常用precision、recall、F1-measure来衡量模型的好坏。对于二分类情况，有四种情况如下表所示：

	predict 1	predict 0	actual total
actual 1	TP(True Positive)	FN（False Negative）	TP + FN (actual positive)
actual 0	FP(False Positive)	TN(True Negative)	FP + TN (actual negative)
predict total	TP + FP(Predict Positive)	FN +TN(Predict Negative)	TP + FP + TN + FN

• precison = TP / (TP + FP)

• recall = TP / (TP + FN)

• F1-measure = 2 * presion * recall / (precison +　recall)

##四、与mahout算法的对比

Written with StackEdit.