支持向量机概念

线性分类器

g(x) = wx + b

支持向量机(Support Vector Machine, SVM)

** 凸集 ** 是指一个点的集合，其中任取两个点连一条直线，这条线上的点仍然在这个集合内部。因为求解最优分类平面的优化问题可行域为一个凸集，所以这个问题为一个** 凸优化问题 **。

(1)

(2)

SMO优化算法

SMO(Sequential Minimal Optimization)优化算法是求解SVM的重要工具

SMO在每次循环中选择两个a进行优化，SMO算法的流程大致如下：

创建一个a向量并初始化为0向量

令a[i]遍历数据集中的向量 {
使用KKT条件判断a[i]是否可以优化 {
随机选择另外一个向量a[j]
同时优化两个向量(a[i]+a[j]不变)
若a[i],a[j]均不能被优化则跳出内循环
}
}

def RandJ(i,m):
j=i
while (j==i):
j = int(random.uniform(0,m))
return j

if alpha > upper:
alpha = upper
if lower > alpha:
alpha = lower
return alpha

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
b = 0; m,n = shape(dataMatrix)
alphas = mat(zeros((m,1)))
iter = 0
while (iter < maxIter):
alphaPairsChanged = 0
for i in range(m):
fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
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] > 0)):
# random select a[j]
j = RandJ(i,m)
fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
Ej = fXj - float(labelMat[j])
# maintain a between 0 and C
alphaIold = alphas[i].copy();
alphaJold = alphas[j].copy();
if (labelMat[i] != labelMat[j]):
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
if eta >= 0: print "eta>=0"; continue
alphas[j] -= labelMat[j]*(Ei - Ej)/eta
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, 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 (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 

• 多项式核函数

SVM工具

Matlab

Matlab丰富的工具箱提供了各种方便。

Statistic Tools工具箱提供了svmtrain和svmclassify函数进行SVM分类。

traindata = [0 1; -1 0; 2 2; 3 3; -2 -1;-4.5 -4; 2 -1; -1 -3];
group = [1 1 -1 -1 1 1 -1 -1]‘;
testdata = [5 2;3 1;-4 -3];
svm_struct = svmtrain(traindata,group);
Group = svmclassify(svm_struct,testdata);

svmtrain接受traindata和group两个参数，traindata以一行表示一个样本，group是与traindata中样本对应的分类结果，用1和-1表示。

svmtrain返回一个存储了训练好的svm所需的参数的结构体svm_struct。

svmclassify接受svm_struct和以一行表示一个样本的testdata，并以1和-1列向量的形式返回分类结果。

SVM -支持向量机原理详解与实践之四

SVM -支持向量机原理详解与实践之四 SVM原理分析 SMO算法分析 SMO即Sequential minmal optimization, 是最快的二次规划的优化算法,特使对线性SVM和稀疏数据性能更优.在正式介绍SMO算法之前,首先要了解坐标上升法. 坐标上升法(Coordinate ascent) 坐标上升法(Coordinate Ascent)简单点说就是它每次通过更新函数中的一维,通过多次的迭代以达到优化函数的目的. 坐标上升法原理讲解 为了更加通用的表示算法的求解过程,我们将算法表

SVM -支持向量机原理详解与实践之二

SVM -支持向量机原理详解与实践之二 SVM原理分析 以下内容接上篇. 拉格朗日对偶性(Largrange duality)深入分析 前面提到了支持向量机的凸优化问题中拉格朗日对偶性的重要性. 因为通过应用拉格朗日对偶性我们可以寻找到最优超平面的二次最优化, 所以以下可以将寻找最优超平面二次最优化(原问题),总结为以下几个步骤: 在原始权重空间的带约束的优化问题.(注意带约束) 对优化问题建立拉格朗日函数 推导出机器的最优化条件 最后就是在对偶空间解决带拉格朗日乘子的优化问题. 注:以上这个四

SVM -支持向量机原理详解与实践之三

SVM -支持向量机原理详解与实践之三 什么是核 什么是核,核其实就是一种特殊的函数,更确切的说是核技巧(Kernel trick),清楚的明白这一点很重要. 为什么说是核技巧呢?回顾到我们的对偶问题:     映射到特征空间后约束条件不变,则为:     在原始特征空间中主要是求,也就是和的内积(Inner Product),也称数量积(Scalar Product)或是点积(Dot Product),映射到特征空间后就变成了求,也就是和的映射到特征空间之后的内积,就如我前面所提到的在原始空间

svm支持向量机系列(1) -- 线性支持向量机

1.主要内容 沿着之前学些机器学习基石课程中学习到的工具进行分析,该工具主要就是vc维,沿着特征转换这一目标进行探讨: (1).当数据的特征的数量很大时,如何进行特征转换?支撑向量机 (2).能不能找到具有预测性的特征然后联合起来? (3).如何发现隐藏的具有预测意义的特征?原先的神经网络到现在的深度学习技术. 这节课主要讲述svm的由来,背后的原理,最佳化的求解问题. 2.线性支持向量机的由来 (1).从线性分类器说起到svm问题的提出 如果数据线性可分,那么必然可以找到一条线对齐进行分类,计