Svm算法原理及实现

野性酷女 2023-10-05 11:04 37阅读 0赞

Svm（support Vector Mac）又称为支持向量机，是一种二分类的模型。当然如果进行修改之后也是可以用于多类别问题的分类。支持向量机可以分为线性核非线性两大类。其主要思想为找到空间中的一个更够将所有数据样本划开的超平面，并且使得本本集中所有数据到这个超平面的距离最短。

### 一、**基于最大间隔分隔数据** ###

#### **1.1支持向量与超平面** ####

在了解svm算法之前，我们首先需要了解一下线性分类器这个概念。比如给定一系列的数据样本，每个样本都有对应的一个标签。为了使得描述更加直观，我们采用二维平面进行解释，高维空间原理也是一样。举个简单子：如下图所示是一个二维平面，平面上有两类不同的数据，分别用圆圈和方块表示。我们可以很简单地找到一条直线使得两类数据正好能够完全分开。但是能将据点完全划开直线不止一条，那么在如此众多的直线中我们应该选择哪一条呢？从直观感觉上看图中的几条直线，![20180521042741112][]是不是要更好一些呢？是的我们就是希望寻找到这样的直线，使得距离这条直线最近的点到这条直线的距离最短。这读起来有些拗口，我们从图三中直观来解释这一句话就是要求的两条外面的线之间的间隔最大。这是可以理解的，因为假如数据样本是随机出现的，那么这样分割之后数据点落入到其类别一侧的概率越高那么最终预测的准确率也会越高。在高维空间中这样的直线称之为超平面，因为当维数大于三的时候我们已经无法想象出这个平面的具体样子。那些距离这个超平面最近的点就是所谓支持向量，实际上如果确定了支持向量也就确定了这个超平面，找到这些支持向量之后其他样本就不会起作用了。

![20180521035815684][]

图 1 图2

#### **1.2寻找最大间隔** ####

**1.2.1点到超平面的距离公式**

既然这样的直线是存在的，那么我们怎样寻找出这样的直线呢？与二维空间类似，超平面的方程也可以写成一下形式：

![20180521035838305][] （1.1）

有了超平面的表达式之后之后，我们就可以计算样本点到平面的距离了。假设![20180521042813312][]为样本的中的一个点，其中![2018052104282066][]表示为第个特征变量。那么该点到超平面的距离![2018052104292189][]就可以用如下公式进行计算：

![20180521035845894][] （1.2）

其中||W||为超平面的范数，常数b类似于直线方程中的截距。

上面的公式可以利用解析几何或高中平面几何知识进行推导，这里不做进一步解释。

**1.2.2最大间隔的优化模型**

现在我们已经知道了如何去求数据点到超平面的距离，在超平面确定的情况下，我们就能够找出所有支持向量，然后计算出间隔margin。每一个超平面都对应着一个margin，我们的目标就是找出所有margin中最大的那个值对应的超平面。因此用数学语言描述就是确定w、b使得margin最大。这是一个优化问题其目标函数可以写成：

![20180521035922810][] （1.3）

其中![20180521043023931][]表示数据点的标签，且其为-1或1。距离用![201805210430080][]计算，这是就能体会出-1和1的好处了。如果数据点在平面的正方向(即+1类)那么![201805210430080][]是一个正数，而当数据点在平面的负方向时(即-1类)，![201805210430080][]依然是一个正数，这样就能够保证始终大于零了。注意到当w和b等比例放大时，d的结果是不会改变的。因此我们可以令所有支持向量的u为1，而其他点的u大1这是可以办通过调节w和b求到的。因此上面的问题可以简化为： ![20180521040724600][] （1.4）

为了后面计算的方便，我们将目标函数等价替换为：

![20180521035939837][] （1.5）

这是一个有约束条件的优化问题，通常我们可以用拉格朗日乘子法来求解。拉格朗日乘子法的介绍可以参考这篇博客。应用拉格朗日乘子法如下：

令 ![20180521040036958][] （1.6）

求L关于求偏导数得：![20180521040043988][] （1.7）

将(1.7)代入到(1.6)中化简得：

![20180521040054915][] （1.8）

原问题的对偶问题为：

![20180521040907231][] （1.9）

该对偶问题的KKT条件为

![2018052104011217][] （1.10）

到此，似乎问题就能够完美地解决了。但是这里有个假设：数据必须是百分之百可分的。但是实际中的数据几乎都不那么“干净”，或多或少都会存在一些噪点。为此下面我们将引入了松弛变量来解决这种问题。

**1.2.3松弛变量**

由上一节的分析我们知道实际中很多样本数据都不能够用一个超平面把数据完全分开。如果数据集中存在噪点的话，那么在求超平的时候就会出现很大问题。从图三中课看出其中一个蓝点偏差太大，如果把它作为支持向量的话所求出来的margin就会比不算入它时要小得多。更糟糕的情况是如果这个蓝点落在了红点之间那么就找不出超平面了。

![20180521040126854][]

图 3

因此引入一个松弛变量ξ来允许一些数据可以处于分隔面错误的一侧。这时新的约束条件变为:

![20180521040136753][] （1.11）

式中ξi的含义为允许第i个数据点允许偏离的间隔。如果让ξ任意大的话，那么任意的超平面都是符合条件的了。所以在原有目标的基础之上，我们也尽可能的让ξ的总量也尽可能地小。所以新的目标函数变为：

![2018052104014338][]（1.12）

![20180521040154617][]（1.13）

其中的C是用于控制“最大化间隔”和“保证大部分的点的函数间隔都小于1”这两个目标的权重。将上述模型完整的写下来就是：

![20180521040203433][]（1.14）

新的拉格朗日函数变为：

![20180521040217479][]（1.15）

接下来将拉格朗日函数转化为其对偶函数，首先对![20180521043256697][]分别求![20180521043306596][]ξ的偏导，并令其为0,结果如下：

![20180521040230365][]（1.16）

代入原式化简之后得到和原来一样的目标函数：

![20180521040239408][]（1.17）

但是由于我们得到![2018052104334596][]而![20180521043355944][]，因此有![20180521043406321][]所以对偶问题写成：

![20180521040249887][]（1.18）

经过添加松弛变量的方法，我们现在能够解决数据更加混乱的问题。通过修改参数C，我们可以得到不同的结果而C的大小到底取多少比较合适，需要根据实际问题进行调节。

1.2.4核函数

以上讨论的都是在线性可分情况进行讨论的，但是实际问题中给出的数据并不是都是线性可分的，比如有些数据可能是如图4样子。 ![20180521040302593][]

图4

那么这种非线性可分的数据是否就不能用svm算法来求解呢？答案是否定的。事实上，对于低维平面内不可分的数据，放在一个高维空间中去就有可能变得可分。以二维平面的数据为例，我们可以通过找到一个映射将二维平面的点放到三维平面之中。理论上任意的数据样本都能够找到一个合适的映射使得这些在低维空间不能划分的样本到高维空间中之后能够线性可分。我们再来看一下之前的目标函数：

![20180521040319232][]（1.19）

定义一个映射使得将所有映射到更高维空间之后等价于求解上述问题的对偶问题：

![20180521040334338][]（1.20）

这样对于线性不可分的问题就解决了，现在只需要找出一个合适的映射即可。当特征变量非常多的时候在，高维空间中计算内积的运算量是非常庞大的。考虑到我们的目的并不是为找到这样一个映射而是为了计算其在高维空间的内积，因此如果我们能够找到计算高维空间下内积的公式，那么就能够避免这样庞大的计算量，我们的问题也就解决了。实际上这就是我们要找的核函数![20180521043454252][]，即两个向量在隐式映射后的空间中的内积。下面的一个简单例子可以帮助我们更好地理解核函数。

通过以上例子，我们可以很明显地看到核函数是怎样运作的。上述问题的对偶问题可以写成如下形式：

![2018052104034641][]（1.21）

那么怎样的函数才可以作为核函数呢？下面的一个定理可以帮助我们判断。

Mercer定理：任何半正定的函数都可以作为核函数。其中所谓半正定函数![20180521043517679][]是指拥有训练集数据集合，我们定义一个矩阵的元素![20180521043539526][]，这个矩阵是![2018052104355651][]的矩阵，如果这个矩阵是半正定的，那么![20180521043612421][]就称为半正定函数。

值得注意的是，上述定理中所给出的条件是充分条件而非充要条件。因为有些非正定函数也可以作为核函数。

下面是一些常用的核函数：

表1 常用核函数表

<table> 
 <tbody> 
 <tr> 
 <td> 核函数名称 </td> 
 <td> 核函数表达式 </td> 
 <td> 核函数名称 </td> 
 <td> 核函数表达式 </td> 
 </tr> 
 <tr> 
 <td> 线性核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043843457"> </td> 
 <td> 指数核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043911229"> </td> 
 </tr> 
 <tr> 
 <td> 多项式核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043852784"> </td> 
 <td> 拉普拉斯核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043921148"> </td> 
 </tr> 
 <tr> 
 <td> 高斯核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043900473"> </td> 
 <td> Sigmoid核 </td> 
 <td> <img alt="" src="https://img-blog.csdn.net/20180521043933455"> </td> 
 </tr> 
 </tbody> 
</table>

现在我们已经了解了一些支持向量机的理论基础，我们通过对偶问题的的转化将最开始求![20180521043642596][]的问题转化为求![20180521043655659][]的对偶问题。只要找到所有的![20180521043655659][](即找出所有支持向量)，我们就能够确定![20180521043710476][]。然后就可以通过计算数据点到这个超平面的距离从而判断出该数据点的类别。

### **二、Smo算法原理** ###

#### **2.1 约束条件** ####

根据以上问题的分析，我们已经将原始问题转化为了求的值，即求下面优化模型的解：

![20180521041359429][]（2.1）

求解![20180521043655659][]的值的方法有很多，Smo算法就是其中一种比较常用的方法。该算法是由John Platt在1996年发布，他的思路是将大的优化问题转化为小的优化问题。而这些小的优化问题往往更容易求解，并且对它们进行顺序求解的结果和将它们作为整体求解的结果完全一致但是Smo算法的时间要小得多。

Smo算法的原理为：每次任意抽取两个乘子![2018052104411870][]和，![20180521044126838][]然后固定![2018052104411870][]和![20180521044126838][]以外的其它乘子![20180521044226430][]，使得目标函数只是关于![2018052104411870][]和![20180521044126838][]的函数。然后增大其中一个乘子同时减少另外一个。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。

而原对偶问题的子问题的目标函数可以表达成：

![20180521041411553][]（2.2）

其中：

![20180521041421624][]（2.3）

这里之所以算两个![20180521043655659][]是因为![20180521044423152][]的限制，如果只改变其中的一个量，那么这个约束条件可能就不成立了。要解决这个问题，我们必须得选取这样的两个乘子。那么怎样确定这样的![2018052104411870][]和![20180521044126838][]呢？这是我们首先要考虑的问题，在《机器学习实战》这本书中，作者首先给出了一种简化版的方法，遍历每一个![20180521043655659][]然后在剩余的![20180521043655659][]中随机选取一个进行优化。虽然样也能够解决问题，但是运算量太大，因此考虑找一种更好的方法来寻找对。

为了表述方便，定义一个特征到输出结果的输出函数：

![20180521041433815][]（2.4）

该对偶问题中KKT条件为：

![20180521041446711][]（2.5）

根据上述问题的KKT条件可以得出目标函数中的的![20180521044601574][]含义如下：

1、 ![20180521044639106][]，表明是正常分类，在边界外；

2、![20180521044648455][]，表明是支持向量，在边界上；

3、![20180521044714944][]，表明在两边界之间。

最优解需要满足KKT条件，因此需要满足以上的三个条件都满足。而不满足这三个条件的情况也有三种：

1、![20180521044800853][]<=1但是<C则是不满足的，而原本![20180521044601574][]=C;

2、![20180521044800853][]>=1但是>0则是不满足的，而原本![20180521044601574][]=0;

3、![20180521044800853][]=1但是=0或者=C则表明不满足的，而原本应该是0<![20180521044601574][]<C.

也就是说如果存在不满足这些KKT条件的，我们就要更新它，这就是约束条件之一。其次，![20180521044601574][]还受到约束条件![20180521044944422][]的限制，因此假设选择的两个因子为![2018052104411870][]和![20180521044126838][]，他们在更新前分别为![20180521045117422][]在更新后为![20180521045126124][]，为了保证上述约束条件成立必须要保证下列等式的成立：

![20180521041501144][]（2.6）

其中![20180521045157848][]为常数。

#### `2.2参数优化` ####

`因为两个因子不好同时求解，所以可先求第二个乘子的解，然后再用的解表示的解。为了求解，得先确定的取值范围。假设它的上下边界分别为H和L，那么有：（2.6）`

`接下来，综合和这两个约束条件，求取的取值范围。`

`当时，根据可得，所以有。`

`当时，同样根据可得：，所以有。`

`回顾第二个约束条件 ：（2.7）`

`令其两边同时乘y1，可得：`

`. （2.8）`

`其中：.`

`因此可以用表示，即： （2.9）`

`令 （2.10）`

`经过转化之后可得：`

`,. (2.11)`

`那么如何来选择乘子呢？对于第一个乘子，我们可以按照3种不满足KTT的条件来寻找。对于第二个乘子，我们可以寻找满足条件的乘子。`

`而b在满足以下条件时需要更新：`

`(2.12)`

`且更新后的和如下：`

`(2.13）`

`每次更新完两个乘子之后，都需要重新计算b以及对应的E。最后更新完所有的,y和b,这样模型也就出来了，从而可以计算出开始所说的分类函数：`

`（2.14）`

### `三、Svm的python实现与应用` ###

`第二节已经对Smo算法进行了充分的说明并进行了推导，现在一切都准备好了。接下来需要做的就是实现这些算法了，这里我参考了《机器学习实战》这本书中的代码，并利用该程序对一个问题进行了求解。由于代码数量过大，因此这里就不再列出，而是放在附录中。有兴趣的朋友可以直接下载，也可以去官网下载源代码。笔者在读这些代码的过程中，也遇到了许多困难，大部分都根据自己的情况进行了注释。`

#### `3.1问题描述` ####

`这里我选取的一个数据集为声呐数据集，该问题为需要根据声呐从不同角度返回的声音强度来预测被测物体是岩石还是矿井。数据集中共有208个数据，60个输入变量和1个输出变量。每个数据的前60个元素为不同方向返回的声音强度，最后一个元素为本次用于声呐测试的物体类型。其中标签M表示矿井，标签R为岩石。`

#### `3.2数据预处理` ####

`所给数据中没有缺失值和异常值，因此不需要对数据集进行清洗。注意到所给数据集的标签为字母类型，而svm算法的标准标签为“-1”和“1”的形式，所以需要对标签进行转化，用“-1”、“1”分别代替M和R。由于该数据集中所给标签相同的数据都放在了一起，因此先对数据顺序进行了打乱。代码如下：`

<table> 
 <tbody> 
 <tr> 
 <td> def&nbsp;loadDataSet(fileName):&nbsp;&nbsp;&nbsp;&nbsp;dataMat=[];labelMat=[];data=[]&nbsp;&nbsp;&nbsp;&nbsp;fr=open(fileName)&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;line&nbsp;in&nbsp;fr.readlines():&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line=line.replace(',','\t')#去除逗号&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line=line.replace('M','-1')#对标签进行替换&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line=line.replace('R','1')&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lineArr=line.strip('\n').split('\t')#分割数据&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;data.append([float(lineArr[i])&nbsp;for&nbsp;i&nbsp;in&nbsp;range(len(lineArr))])&nbsp;&nbsp;&nbsp;&nbsp;random.shuffle(data) &nbsp;#随机打乱列表&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(len(data)):&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dataMat.append(data[i][0:len(data)-1])&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;labelMat.append(data[i][-1])&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;dataMat,labelMat </td> 
 </tr> 
 </tbody> 
</table>

#### `3.3模型训练及测试` ####

`首先测试了一下将所有数据即作为训练集又作为测试集，然后用Smo模型进行训练找到所有的支持向量。最后根据训练好的模型进行求解，最终测试的准确率平均为54%。如果把数据集分成测试集和训练集，发现测试的准确率也在这附近。而根据网上数据统计该数据集测试的准确率最高为84%，一般情况下为百分之六十几。数据集本身是造成测试准确率低的一个原因，但是另外一个更加重要的原因大概是参数的选择问题。如何选取合适的参数是一个值得思考的问题，在接下来的学习过程中我也会注意一下参数选取这个问题。到这里，关于svm的算法就告一段落了。`

1. `#svm算法的实现`
2. `from numpy import*`
3. `import random`
4. `from time import*`
5. `def loadDataSet(fileName):#输出dataArr(m*n),labelArr(1*m)其中m为数据集的个数`
6. `dataMat=[];labelMat=[]`
7. `fr=open(fileName)`
8. `for line in fr.readlines():`
9. `lineArr=line.strip().split('\t')#去除制表符，将数据分开`
10. `dataMat.append([float(lineArr[0]),float(lineArr[1])])#数组矩阵`
11. `labelMat.append(float(lineArr[2]))#标签`
12. `return dataMat,labelMat`
13. 
14. `def selectJrand(i,m):#随机找一个和i不同的j`
15. `j=i`
16. `while(j==i):`
17. `j=int(random.uniform(0,m))`
18. `return j`
19. 
20. `def clipAlpha(aj,H,L):#调整大于H或小于L的alpha的值`
21. `if aj>H:`
22. `aj=H`
23. `if aj<L:`
24. `aj=L`
25. `return aj`
26. 
27. `def smoSimple(dataMatIn,classLabels,C,toler,maxIter):`
28. `dataMatrix=mat(dataMatIn);labelMat=mat(classLabels).transpose()#转置`
29. `b=0;m,n=shape(dataMatrix)#m为输入数据的个数，n为输入向量的维数`
30. `alpha=mat(zeros((m,1)))#初始化参数，确定m个alpha`
31. `iter=0#用于计算迭代次数`
32. `while (iter<maxIter):#当迭代次数小于最大迭代次数时（外循环）`
33. `alphaPairsChanged=0#初始化alpha的改变量为0`
34. `for i in range(m):#内循环`
35. `fXi=float(multiply(alpha,labelMat).T*\`
36. `(dataMatrix*dataMatrix[i,:].T))+b#计算f(xi)`
37. `Ei=fXi-float(labelMat[i])#计算f(xi)与标签之间的误差`
38. `if ((labelMat[i]*Ei<-toler)and(alpha[i]<C))or\`
39. `((labelMat[i]*Ei>toler)and(alpha[i]>0)):#如果可以进行优化`
40. `j=selectJrand(i,m)#随机选择一个j与i配对`
41. `fXj=float(multiply(alpha,labelMat).T*\`
42. `(dataMatrix*dataMatrix[j,:].T))+b#计算f(xj)`
43. `Ej=fXj-float(labelMat[j])#计算j的误差`
44. `alphaIold=alpha[i].copy()#保存原来的alpha(i)`
45. `alphaJold=alpha[j].copy()`
46. `if(labelMat[i]!=labelMat[j]):#保证alpha在0到c之间`
47. `L=max(0,alpha[j]-alpha[i])`
48. `H=min(C,C+alpha[j]-alpha[i])`
49. `else:`
50. `L=max(0,alpha[j]+alpha[i]-C)`
51. `H=min(C,alpha[j]+alpha[i])`
52. `if L==H:print('L=H');continue`
53. `eta=2*dataMatrix[i,:]*dataMatrix[j,:].T-\`
54. `dataMatrix[i,:]*dataMatrix[i,:].T-\`
55. `dataMatrix[j,:]*dataMatrix[j,:].T`
56. `if eta>=0:print('eta=0');continue`
57. `alpha[j]-=labelMat[j]*(Ei-Ej)/eta`
58. `alpha[j]=clipAlpha(alpha[j],H,L)#调整大于H或小于L的alpha`
59. `if (abs(alpha[j]-alphaJold)<0.0001):`
60. `print('j not move enough');continue`
61. `alpha[i]+=labelMat[j]*labelMat[i]*(alphaJold-alpha[j])`
62. `b1=b-Ei-labelMat[i]*(alpha[i]-alphaIold)*\`
63. `dataMatrix[i,:]*dataMatrix[i,:].T-\`
64. `labelMat[j]*(alpha[j]-alphaJold)*\`
65. `dataMatrix[i,:]*dataMatrix[j,:].T#设置b`
66. `b2=b-Ej-labelMat[i]*(alpha[i]-alphaIold)*\`
67. `dataMatrix[i,:]*dataMatrix[i,:].T-\`
68. `labelMat[j]*(alpha[j]-alphaJold)*\`
69. `dataMatrix[j,:]*dataMatrix[j,:].T`
70. `if (0<alpha[i])and(C>alpha[j]):b=b1`
71. `elif(0<alpha[j])and(C>alpha[j]):b=b2`
72. `else:b=(b1+b2)/2`
73. `alphaPairsChanged+=1`
74. `print('iter:%d i:%d,pairs changed%d'%(iter,i,alphaPairsChanged))`
75. `if (alphaPairsChanged==0):iter+=1`
76. `else:iter=0`
77. `print('iteraction number:%d'%iter)`
78. `return b,alpha`
79. `#定义径向基函数`
80. `def kernelTrans(X, A, kTup):#定义核转换函数（径向基函数）`
81. `m,n = shape(X)`
82. `K = mat(zeros((m,1)))`
83. `if kTup[0]=='lin': K = X * A.T #线性核K为m*1的矩阵`
84. `elif kTup[0]=='rbf':`
85. `for j in range(m):`
86. `deltaRow = X[j,:] - A`
87. `K[j] = deltaRow*deltaRow.T`
88. `K = exp(K/(-1*kTup[1]**2)) #divide in NumPy is element-wise not matrix like Matlab`
89. `else: raise NameError('Houston We Have a Problem -- \`
90. `That Kernel is not recognized')`
91. `return K`
92. 
93. `class optStruct:`
94. `def __init__(self,dataMatIn, classLabels, C, toler, kTup): # Initialize the structure with the parameters`
95. `self.X = dataMatIn`
96. `self.labelMat = classLabels`
97. `self.C = C`
98. `self.tol = toler`
99. `self.m = shape(dataMatIn)[0]`
100. `self.alphas = mat(zeros((self.m,1)))`
101. `self.b = 0`
102. `self.eCache = mat(zeros((self.m,2))) #first column is valid flag`
103. `self.K = mat(zeros((self.m,self.m)))`
104. `for i in range(self.m):`
105. `self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)`
106. 
107. `def calcEk(oS, k):`
108. `fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)`
109. `Ek = fXk - float(oS.labelMat[k])`
110. `return Ek`
111. 
112. `def selectJ(i, oS, Ei):`
113. `maxK = -1; maxDeltaE = 0; Ej = 0`
114. `oS.eCache[i] = [1,Ei]`
115. `validEcacheList = nonzero(oS.eCache[:,0].A)[0]`
116. `if (len(validEcacheList)) > 1:`
117. `for k in validEcacheList: #loop through valid Ecache values and find the one that maximizes delta E`
118. `if k == i: continue #don't calc for i, waste of time`
119. `Ek = calcEk(oS, k)`
120. `deltaE = abs(Ei - Ek)`
121. `if (deltaE > maxDeltaE):`
122. `maxK = k; maxDeltaE = deltaE; Ej = Ek`
123. `return maxK, Ej`
124. `else: #in this case (first time around) we don't have any valid eCache values`
125. `j = selectJrand(i, oS.m)`
126. `Ej = calcEk(oS, j)`
127. `return j, Ej`
128. 
129. `def updateEk(oS, k):#after any alpha has changed update the new value in the cache`
130. `Ek = calcEk(oS, k)`
131. `oS.eCache[k] = [1,Ek]`
132. 
133. `def innerL(i, oS):`
134. `Ei = calcEk(oS, i)`
135. `if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):`
136. `j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand`
137. `alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy()`
138. `if (oS.labelMat[i] != oS.labelMat[j]):`
139. `L = max(0, oS.alphas[j] - oS.alphas[i])`
140. `H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])`
141. `else:`
142. `L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)`
143. `H = min(oS.C, oS.alphas[j] + oS.alphas[i])`
144. `if L==H: print("L==H"); return 0`
145. `eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j] #changed for kernel`
146. `if eta >= 0: print("eta>=0"); return 0`
147. `oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta`
148. `oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)`
149. `updateEk(oS, j) #added this for the Ecache`
150. `if (abs(oS.alphas[j] - alphaJold) < 0.00001): print("j not moving enough"); return 0`
151. `oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j`
152. `updateEk(oS, i) #added this for the Ecache #the update is in the oppostie direction`
153. `b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]`
154. `b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]`
155. `if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1`
156. `elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2`
157. `else: oS.b = (b1 + b2)/2.0`
158. `return 1`
159. `else: return 0`
160. `#smoP函数用于计算超平的alpha,b`
161. `def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)): #完整的Platter SMO`
162. `oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)`
163. `iter = 0#计算循环的次数`
164. `entireSet = True; alphaPairsChanged = 0`
165. `while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):`
166. `alphaPairsChanged = 0`
167. `if entireSet: #go over all`
168. `for i in range(oS.m):`
169. `alphaPairsChanged += innerL(i,oS)`
170. `print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))`
171. `iter += 1`
172. `else:#go over non-bound (railed) alphas`
173. `nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]`
174. `for i in nonBoundIs:`
175. `alphaPairsChanged += innerL(i,oS)`
176. `print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))`
177. `iter += 1`
178. `if entireSet: entireSet = False #toggle entire set loop`
179. `elif (alphaPairsChanged == 0): entireSet = True`
180. `print("iteration number: %d" % iter)`
181. `return oS.b,oS.alphas`
182. `#calcWs用于计算权重值w`
183. `def calcWs(alphas,dataArr,classLabels):#计算权重W`
184. `X = mat(dataArr); labelMat = mat(classLabels).transpose()`
185. `m,n = shape(X)`
186. `w = zeros((n,1))`
187. `for i in range(m):`
188. `w += multiply(alphas[i]*labelMat[i],X[i,:].T)`
189. `return w`
190. 
191. `#值得注意的是测试准确与k1和C的取值有关。`
192. `def testRbf(k1=1.3):#给定输入参数K1`
193. `#测试训练集上的准确率`
194. `dataArr,labelArr = loadDataSet('testSetRBF.txt')#导入数据作为训练集`
195. `b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, ('rbf', k1)) #C=200 important`
196. `datMat=mat(dataArr); labelMat = mat(labelArr).transpose()`
197. `svInd=nonzero(alphas.A>0)[0]#找出alphas中大于0的元素的位置`
198. `#此处需要说明一下alphas.A的含义`
199. `sVs=datMat[svInd] #获取支持向量的矩阵，因为只要alpha中不等于0的元素都是支持向量`
200. `labelSV = labelMat[svInd]#支持向量的标签`
201. `print("there are %d Support Vectors" % shape(sVs)[0])#输出有多少个支持向量`
202. `m,n = shape(datMat)#数据组的矩阵形状表示为有m个数据，数据维数为n`
203. `errorCount = 0#计算错误的个数`
204. `for i in range(m):#开始分类，是函数的核心`
205. `kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))#计算原数据集中各元素的核值`
206. `predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b#计算预测结果y的值`
207. `if sign(predict)!=sign(labelArr[i]): errorCount += 1#利用符号判断类别`
208. `### sign（a）为符号函数：若a>0则输出1，若a<0则输出-1.###`
209. `print("the training error rate is: %f" % (float(errorCount)/m))`
210. `#2、测试测试集上的准确率`
211. `dataArr,labelArr = loadDataSet('testSetRBF2.txt')`
212. `errorCount = 0`
213. `datMat=mat(dataArr)#labelMat = mat(labelArr).transpose()此处可以不用`
214. `m,n = shape(datMat)`
215. `for i in range(m):`
216. `kernelEval = kernelTrans(sVs,datMat[i,:],('rbf', k1))`
217. `predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b`
218. `if sign(predict)!=sign(labelArr[i]): errorCount += 1`
219. `print("the test error rate is: %f" % (float(errorCount)/m))`
220. `def main():`
221. `t1=time()`
222. `dataArr,labelArr=loadDataSet('testSet.txt')`
223. `b,alphas=smoP(dataArr,labelArr,0.6,0.01,40)`
224. `ws=calcWs(alphas,dataArr,labelArr)`
225. `testRbf()`
226. `t2=time()`
227. `print("程序所用时间为%ss"%(t2-t1))`
228. 
229. `if __name__=='__main__':`
230. `main()`

后记

这是第一次写博客，其中难免会出错，因此希望大家能够批评指正。首先非常感谢网上的一些朋友，在理解svm这算法他们给了我很多启发，在公式推导中给了我很多参考的地方。本文主要参考的资料是《机器学习实战》和《惊呼！理解svm的三种境界》这篇博客。对于svm虽然学的时间不长，但是对它一直有种特别的感觉。第一次听说svm是在做一个验证码识别问题的时候，但那时候我使用的是KNN算法，尽管效果还不错，但是我一直希望能够用svm算法来完成这个题目。本来这次是打算把这个问题一起解决的，但是由于时间关系，没有来得及做。只能等下次有空闲的时候再来做这个问题了。

来源：[https://blog.csdn.net/d\_\_760/article/details/80387432][https_blog.csdn.net_d_760_article_details_80387432]

[20180521042741112]: https://img-blog.csdn.net/20180521042741112
[20180521035815684]: https://img-blog.csdn.net/20180521035815684
[20180521035838305]: https://img-blog.csdn.net/20180521035838305
[20180521042813312]: https://img-blog.csdn.net/20180521042813312
[2018052104282066]: https://img-blog.csdn.net/2018052104282066
[2018052104292189]: https://img-blog.csdn.net/2018052104292189
[20180521035845894]: https://img-blog.csdn.net/20180521035845894
[20180521035922810]: https://img-blog.csdn.net/20180521035922810
[20180521043023931]: https://img-blog.csdn.net/20180521043023931
[201805210430080]: https://img-blog.csdn.net/201805210430080
[20180521040724600]: https://img-blog.csdn.net/20180521040724600
[20180521035939837]: https://img-blog.csdn.net/20180521035939837
[20180521040036958]: https://img-blog.csdn.net/20180521040036958
[20180521040043988]: https://img-blog.csdn.net/20180521040043988
[20180521040054915]: https://img-blog.csdn.net/20180521040054915
[20180521040907231]: https://img-blog.csdn.net/20180521040907231
[2018052104011217]: https://img-blog.csdn.net/2018052104011217
[20180521040126854]: https://img-blog.csdn.net/20180521040126854
[20180521040136753]: https://img-blog.csdn.net/20180521040136753
[2018052104014338]: https://img-blog.csdn.net/2018052104014338
[20180521040154617]: https://img-blog.csdn.net/20180521040154617
[20180521040203433]: https://img-blog.csdn.net/20180521040203433
[20180521040217479]: https://img-blog.csdn.net/20180521040217479
[20180521043256697]: https://img-blog.csdn.net/20180521043256697
[20180521043306596]: https://img-blog.csdn.net/20180521043306596
[20180521040230365]: https://img-blog.csdn.net/20180521040230365
[20180521040239408]: https://img-blog.csdn.net/20180521040239408
[2018052104334596]: https://img-blog.csdn.net/2018052104334596
[20180521043355944]: https://img-blog.csdn.net/20180521043355944
[20180521043406321]: https://img-blog.csdn.net/20180521043406321
[20180521040249887]: https://img-blog.csdn.net/20180521040249887
[20180521040302593]: https://img-blog.csdn.net/20180521040302593
[20180521040319232]: https://img-blog.csdn.net/20180521040319232
[20180521040334338]: https://img-blog.csdn.net/20180521040334338
[20180521043454252]: https://img-blog.csdn.net/20180521043454252
[2018052104034641]: https://img-blog.csdn.net/2018052104034641
[20180521043517679]: https://img-blog.csdn.net/20180521043517679
[20180521043539526]: https://img-blog.csdn.net/20180521043539526
[2018052104355651]: https://img-blog.csdn.net/2018052104355651
[20180521043612421]: https://img-blog.csdn.net/20180521043612421
[20180521043642596]: https://img-blog.csdn.net/20180521043642596
[20180521043655659]: https://img-blog.csdn.net/20180521043655659
[20180521043710476]: https://img-blog.csdn.net/20180521043710476
[20180521041359429]: https://img-blog.csdn.net/20180521041359429
[2018052104411870]: https://img-blog.csdn.net/2018052104411870
[20180521044126838]: https://img-blog.csdn.net/20180521044126838
[20180521044226430]: https://img-blog.csdn.net/20180521044226430
[20180521041411553]: https://img-blog.csdn.net/20180521041411553
[20180521041421624]: https://img-blog.csdn.net/20180521041421624
[20180521044423152]: https://img-blog.csdn.net/20180521044423152
[20180521041433815]: https://img-blog.csdn.net/20180521041433815
[20180521041446711]: https://img-blog.csdn.net/20180521041446711
[20180521044601574]: https://img-blog.csdn.net/20180521044601574
[20180521044639106]: https://img-blog.csdn.net/20180521044639106
[20180521044648455]: https://img-blog.csdn.net/20180521044648455
[20180521044714944]: https://img-blog.csdn.net/20180521044714944
[20180521044800853]: https://img-blog.csdn.net/20180521044800853
[20180521044944422]: https://img-blog.csdn.net/20180521044944422
[20180521045117422]: https://img-blog.csdn.net/20180521045117422
[20180521045126124]: https://img-blog.csdn.net/20180521045126124
[20180521041501144]: https://img-blog.csdn.net/20180521041501144
[20180521045157848]: https://img-blog.csdn.net/20180521045157848
[https_blog.csdn.net_d_760_article_details_80387432]: https://blog.csdn.net/d__760/article/details/80387432