SVM算是整本书最不好理解的一块了，也是代码最多的一块。
6.1前奏
优点：泛化错误率低，计算开销不大，结果易解释。
缺点：对参数调节和核函数的选择敏感（不懂什么是核函数？没关系，继续往下看呗），原始分类器不加修改仅适用于处理二类问题。
鉴于SVM不怎么好理解下面先给出一些概念。
①分隔超平面：N维的数据需要N-1维的某某对象来对数据集进行分隔，该对象就被称为超平面，分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据都属于另一个类别。如二维数据，分隔超平面是一条直线，三维数据，分隔超平面是一个平面等等。
②基于最大间隔来构建分类器：找到离分隔超平面最近的点，确保它们离分隔面的距离尽可能远（点到分隔面的距离称为间隔），间隔越大，结果越可信，分类器越健壮。
③支持向量：指离分隔超平面最近的那些点。
现在知道SVM（support vector machines）是什么意思了吧。然后要做的工作就是最大化支持向量到分隔面的距离。
④该如何寻找最大间隔呢？
分隔超平面的形式可以写成wTx+b,那么点A到分隔超平面的距离就是|wTA+b|/|w|,
常数b类似于Logistic回归中的截距w0。这样由向量w和常数b就刻画了所给数据的分隔线或超平面。
⑤单位阶跃函数，用其对wTx+b作用得到f(wTx+b),若wTx+b<0则输出-1，反之输出+1（-1，+1表类别）。
剩下的一大堆工作就是在求w和b.
找到最小间隔的数据点，再对间隔最大化，写作：（公式难写就不写了，見书吧），由于求解困难引入拉格朗日乘子最后优化目标函数转化为：（公式难写就不写了，見书吧），约束条件：C≥α≥0，和Σαi·label(i)=0
好了，去求alpha吧，求得以后和label一乘就是w了，就可以得到分隔超平面了。
6.2 SMO高效优化算法之简化版的SMO
由于存在约束条件:Σαi·label(i)=0(鉴于浏览器不支持在word里编写好的公式粘贴在这里，就这么丑丑的放着吧)，所以要同时改变两个alpha,首先在数据集上遍历每一个alpha,然后再剩下的alpha集合里随机选择另一个alpha，从而构建alpha对，增大其中一个同时减小另一个。当然这两个alpha 要符合一定的条件:必须要在间隔边界之外，还没有经过区间化处理或者不在边界上。
首先当然是要构建一些辅助函数：
def loadDateSet(fileName):#准备数据，老生常谈了。
dataMat=[];labelMat=[]
fr=open(fileName)
for line in
fr.readlines():
lineArr=line.strip().split(‘\t‘)
dataMat.append([float(lineArr[0]),float(lineArr[1])])
labelMat.append(float(lineArr[2]))
return dataMat,labelMat
def selectJrand(i,m):#构建alpha对
j=i
while(j!=i):
j=int(random.uniform(0,m))
return j
def clipAlpha(aj,H,L):#保证alpha在H和L之间（即0到C之间）
if
aj>H:
aj=H
if L>aj:
aj=L
return aj
接下来就可以使用简化版的SMO了，先给伪代码：
创建一个alpha向量并将其初始化为0向量#因为alpha的最小值为0
当迭代次数小于最大迭代次数时（外循环）
对数据集中的每个数据向量（内循环）：
如果该向量可以被优化：
随机选择另外一个数据向量
同时优化这两个向量
如果这两个向量都不能被优化，退出内循环
如果所有向量都不能被优化，增加迭代次数目，继续下一次循环.代码来了（不要问太多问题，我也不是理解的十分十分透彻）：
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#toler容错率
dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
b =
0; m,n = shape(dataMatrix)
alphas = mat(zeros((m,1)))
iter =
0#没有任何alpha改变的情况下迭代的次数
while (iter <
maxIter):
alphaPairsChanged = 0#是否已经改变alpha
for i in
range(m):
fXi =
float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) +
b#预估类别；multiply(alphas,labelMat)相当于w,dataMatrix*dataMatrix[i,:].T数据点为什么要这么算，呜呜呜？？
Ei = fXi - float(labelMat[i])#误差
if
((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei >
toler) and (alphas[i] >
0)):#随机选择另一个alpha，如果alpha[i]为0或C的话则已处在边界，无需调整，进行下一次for循环。
j = selectJrand(i,m)
fXj =
float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) +
b
Ej = fXj - float(labelMat[j])
alphaIold = alphas[i].copy();
alphaJold = alphas[j].copy();#用来比较前后变化
if (labelMat[i]
!= labelMat[j]):#确保alpha在0~C之间
L = max(0,
alphas[j] - alphas[i])
H = min(C, C + alphas[j] -
alphas[i])
else:
L = max(0, alphas[j] + alphas[i] -
C)
H = min(C, alphas[j] + alphas[i])
if L==H: print "L==H";
continue
eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T -
dataMatrix[i,:]*dataMatrix[i,:].T -
dataMatrix[j,:]*dataMatrix[j,:].T#alpha[j]的最优修改量
if eta
>= 0: print "eta>=0"; continue#下边从相反方向改变alphas[i]和alphas[j]的值
alphas[j] -= labelMat[j]*(Ei - Ej)/eta
alphas[j] =
clipAlpha(alphas[j],H,L)
if (abs(alphas[j] - alphaJold) < 0.00001):
print "j not moving enough"; continue
alphas[i] +=
labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#update i by the same amount as
j,下边设置b的值
b1 = b - Ei-
labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T -
labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
b2
= b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T -
labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
if
(0 < alphas[i]) and (C > alphas[i]): b = b1
elif (0 <
alphas[j]) and (C > alphas[j]): b = b2
else: b = (b1 +
b2)/2.0
alphaPairsChanged += 1
print "iter: %d i:%d, pairs
changed %d" % (iter,i,alphaPairsChanged)
if (alphaPairsChanged == 0):
iter += 1
else: iter = 0
print "iteration number: %d" %
iter
return b,alphas
就这样吧，头大，我已经写不下去了，等过段时间再看。
待续
原文：http://www.cnblogs.com/woshikafeidouha/p/3578773.html