1、支持向量机（SVM）support vector machines
序列最小优化（SMO）sequential minimal optimization
适用数据类型：数值型和标称型
优点：泛化错误率低，计算开销不大，结果易解释
缺点：对参数调节和核函数的选择敏感，原是分类器不加修改仅适用于处理二类问题。
2、点到分隔面的距离称为间隔
间隔尽可能大，如果我们犯错或者在有限数据上训练分类器的话，希望分类器尽可能健壮。
支持向量：就是离分隔超平面最近的那些点
3、训练算法：SVM大部分时间都源于训练，该过程主要实现两个参数的调优。SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改。
4、SVM高效优化算法
一个是最小化的目标函数，一个是在优化过程中必须遵循的约束条件。
Jhon Platt的SMO算法是将大优化问题分解为多个小优化问题来求解。SMO目标是求出一系列alpha和b，一旦求出了这些alpha，就很容易计算出权重向量w并得到分隔超平面。
SMO算法的工作原理：每次循环中选择两个alpha进行优化处理，一旦找到一对合适的alpha，那么就增大其中一个减小另一个。这里的“合适”就是指两个alpha必须要符合一定的条件，条件之一就是这两个alpha必须要在间隔边界之外，而其第二个条件则是这两个alpha还没有进行过区间化处理或者不在边界上。
简化的SMO算法：首先在数据集上遍历每一个alpha，然后在剩下的alpha集合中随机选择另外一个alpha，从而构建alpha对。
我们构建一个辅助函数，用于在某个区间范围内随机选择一个整数，同时我们也需要构建另一个辅助函数，用于在数值太大时对其进行调整。
5、SVM辅助函数
def loadDataSet(fileName):
dataMat = []; labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr = line.strip().split('\t')
dataMat.append([float(lineArr[]), float(lineArr[])])
labelMat.append(float(lineArr[]))
return dataMat,labelMat
def selectJrand(i,m):
j=i #we want to select any J not equal to i
while (j==i):
j = int(random.uniform(,m))
return j
def clipAlpha(aj,H,L):
if aj > H:
aj = H
if L > aj:
aj = L
return aj
函数selectJrand()由两个参数值，其中i是第一个alpha的下标，m是所有alpha的数目。只要函数值不等于输入值i，函数就会进行随机选择。
最后一个辅助函数clipAlpha(),它是用于调整大于H或者小于L的alpha值。
SMO函数的伪代码：
创建一个alpha向量并将其初始化为0向量
当迭代次数小于最大迭代次数时（外循环）
对数据集中的每个数据向量（内循环）：
如果还数据向量可以被优化：
随机选择另外一个数据向量
同时优化这两个向量
如果两个向量都不能被优化，退出内循环
如果所有向量都没被优化，增加迭代数目，继续下一次循环
6、简化版SMO代码
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):#5个输入参数，数据集、类别标签、常数c、容错率、退出前最大的循环次数
dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
b = ; m,n = shape(dataMatrix)
alphas = mat(zeros((m,)))
iter = #存储的是在没有任何alpha改变的情况下遍历数据集的次数
while (iter < maxIter):
alphaPairsChanged = #用于记录alpha是否已经进行优化，在循环结束才能知道
for i in range(m):
fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b#fXi能够计算出来，这就是我们预测的类别，然后基于这个实例的预测结果和真实结果的对比，就可以计算误差Ei.如果误差很大，那么可以对数据实例所对应的alpha值进行优化。
Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions
if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > )):
j = selectJrand(i,m)#利用上次的函数选择另一个alpha,即alpha[j]，然后计算误差
fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
Ej = fXj - float(labelMat[j])
alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();#copy()方法，为alphaIold和alphaJold分配内存。否则在对新值和旧值进行比较
if (labelMat[i] != labelMat[j]):#计算L和H，用于将alpha[j]调整到0到C之间
L = max(, alphas[j] - alphas[i])
H = min(C, C + alphas[j] - alphas[i])
else:
L = max(, alphas[j] + alphas[i] - C)
H = min(C, alphas[j] + alphas[i])
if L==H: print "L==H"; continue#continue语句，意味着本次循环结束直接运行下一次for循环
eta = * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
if eta >= : print "eta>=0"; continue
alphas[j] -= labelMat[j]*(Ei - Ej)/eta
alphas[j] = clipAlpha(alphas[j],H,L)
if (abs(alphas[j] - alphaJold) < .): print "j not moving enough"; continue
alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])#update i by the same amount as j
#the update is in the oppostie direction
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 ( < alphas[i]) and (C > alphas[i]): b = b1
elif ( < alphas[j]) and (C > alphas[j]): b = b2
else: b = (b1 + b2)/
alphaPairsChanged +=
print "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
if (alphaPairsChanged == ): iter +=
else: iter =
print "iteration number: %d" % iter
return b,alphas