文章目录
前言
支持向量机就是寻找一个超平面，将不同的样本分分隔开来，其中间隔分为硬间隔和软间隔，硬间隔就是不允许样本分错，而软间隔就是允许一定程度上样本存在偏差，后者更符合实际。
支持向量机思路简单但是求解过程还是比较复杂，需要将原函数通过拉格朗日乘子法并附上KKT条件是的问题有强对偶性，再使用SMO等算法进行高效的求解。
推导过程可以参考：
机器学习之支持向量机之线性可分型原理介绍及代码实现（SVM）
下面主要实现模型的求解方法。
梯度下降法
梯度下降法是一种比较普适的方法，当模型无法得出解析解，或者解析解求解困难的时候，都可以使用梯度下降法来近似求解。因为梯度下降法需要一轮轮迭代，也需要定义损失函数，因此一般而言，梯度下降法只能获得近似最优解。
SVM可以使用梯度下降法求解，不过得出的解大概率只是近似解，并且不一定满足SVM的公式里的约束条件。
import sys;
import random;
import numpy as np
import math
EPS = 0.000000001
def load_data(filename, dim):
'''
输入数据格式: label\tindex1:value1\tindex2:value2\tindex3:value3..., 其中index是特征的编号, 从1开始
data的数据格式: [[label, sample],[label, sample], ...], 其中sample: [v0, v1, v2, v3, ..., v[dim]]
'''
label_ = []
data_ = []
for line in open(filename, 'rt'):
sample = [0.0 for v in range(0, dim + 1)];
line = line.rstrip("\r\n\t ");
fields = line.split("\t");
label = int(fields[0]);
sample[0] = 1.0;
for field in fields[1:]:
kv = field.split(":");
idx = int(kv[0]);
val = float(kv[1]);
sample[idx] = val;
label_.append(label)
data_.append(sample)
label_ = np.array(label_)
data_ = np.array(data_)
return label_, data_
def svm_train(train_x, train_y, dim, iterations, lm, lr):
'''
data4train:数据集
dim:样本特征维度
W:SVM模型的权重
iterations:迭代次数
目标函数: obj(, W) = (对所有SUM{max{0, 1 - W*X*y}}) + lm / 2 * ||W||^2, 即：hinge+L2
'''
X = np.zeros(dim + 1)
grad = np.zeros(dim + 1)
num_train = len(train_x);
global W
for i in range(0, iterations):
index = random.randint(0, num_train - 1);
y = train_y[index]
X = train_x[index]
WX = 0.0
WX += (W * X).sum()
if 1 - WX * y > 0:
grad = lm * W - X * y
else:
grad = lm * W - 0;
W = W - lr * grad
def svm_predict(x, y, dim, W):
num_test = len(x);
num_correct = 0;
for i in range(0, num_test):
target = y[i]
X = x[i]
sum = 0.0;
sum += (X * W).sum()
predict = -1;
if sum > 0:
predict = 1;
if predict * target > 0:
num_correct += 1;
return num_correct * 1.0 / num_test;
if __name__ == "__main__":
epochs = 10;
iterations = 10;
lm = 0.0001;
lr = 0.01;
dim = 1000;
W = np.zeros(dim + 1)
train_y, train_x = load_data("train.txt", dim)
test_y, test_x = load_data("test.txt", dim)
for i in range(0, epochs):
svm_train(train_x, train_y, dim, iterations, lm, lr);
accuracy = svm_predict(test_x, test_y, dim, W);
print("epoch:%d\taccuracy:%f" % (i, accuracy));
for i in range(0, dim + 1):
if math.fabs(W[i]) > EPS:
print("权值W%d\t%f" % (i, W[i]));
print(W)
这个是参考支持向量机SVM-手写笔记&手动实现这篇博客的，代码改成numpy进行运算了，进行改动的过程也是读懂代码的过程。
这个例子使用的梯度下降法，损失函数应该大概也许相当于用了max(0, x)。整体思路就是，每次就选一个样本点进行参数更新，如果这个样本点对于当前的参数能够正确分类，那么就不更新，如果不能正确分类，就更新。
运行结果如下：
因为每次随机选择样本，那么其实找到的那个超平面大概率不会将样本集完全分开的，但是事实证明梯度下降法还是有效果的，所有，应该可以勉强认为训练出来的是软间隔的SVM吧？
; SMO算法
贴上b站视频，以便日后再去看，实话说目前也没有完全走通这个算法的流程。
快速理解SMO算法
SMO算法思路很简单，因为存在约束条件
所以每次更新两个α，剩余看成常量，α能够通过看成的常量导出，然后满足约束条件的情况下求出极值，更新α。每次都更新两个，当固定其他的α时，能够求出选取α的更新的解析解，所以就算起来非常快。
那么该如何选择呢？
第一个αi应该选择违反KKT条件最大的。
第二个αj应该选择于第一个αi差值最大的。
这样能够保证每次更新都是向最快的方向进行更新。
思路是很简单，但是实践起来还是很困难的，因为里面涉及到许多的约束条件，不同情况下需要分类讨论等等。
直接贴上别人的代码吧
from numpy import *
import matplotlib.pyplot as plt
import random
def loadDataSet(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
class optStruct:
def __init__(self,dataMatIn, classLabels, C, toler):
self.X = dataMatIn
self.labelMat = classLabels
self.C = C
self.tol = toler
self.m = shape(dataMatIn)[0]
self.alphas = mat(zeros((self.m,1)))
self.b = 0
self.eCache = mat(zeros((self.m,2)))
def print_m(self):
print("self.X", self.X)
print("self.labelMat", self.labelMat)
print("self.C", self.C)
print("self.tol", self.tol)
print("self.m", self.m)
print("self.alphas", self.alphas)
print("self.b", self.b)
print("self.eCache", self.eCache)
def selectJrand(i,m):
j=i
while (j==i):
j=int(random.uniform(0,m))
return j
def clipAlpha(aj,H,L):
if aj>H:
aj=H
if L>aj:
aj=L
return aj
def calcEk(oS, k):
fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T) + oS.b)
Ek = fXk - float(oS.labelMat[k])
return Ek
def selectJ(i, oS, Ei):
maxK = -1
maxDeltaE = 0
Ej = 0
oS.eCache[i] = [1,Ei]
validEcacheList = nonzero(oS.eCache[:,0].A)[0]
if (len(validEcacheList)) > 1:
for k in validEcacheList:
if k == i:
continue
Ek = calcEk(oS, k)
deltaE = abs(Ei - Ek)
if (deltaE > maxDeltaE):
maxK = k
maxDeltaE = deltaE
Ej = Ek
return maxK, Ej
else:
j = selectJrand(i, oS.m)
Ej = calcEk(oS, j)
return j, Ej
def updateEk(oS, k):
Ek = calcEk(oS, k)
oS.eCache[k] = [1,Ek]
def innerL(i, oS):
Ei = calcEk(oS, i)
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)):
j,Ej = selectJ(i, oS, Ei)
alphaIold = oS.alphas[i].copy()
alphaJold = oS.alphas[j].copy()
if (oS.labelMat[i] != oS.labelMat[j]):
L = max(0, oS.alphas[j] - oS.alphas[i])
H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
else:
L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
H = min(oS.C, oS.alphas[j] + oS.alphas[i])
if L==H:
print("L==H")
return 0
eta = 2.0 * oS.X[i,:]*oS.X[j,:].T-oS.X[i,:]*oS.X[i,:].T-oS.X[j,:]*oS.X[j,:].T
if eta >= 0:
print("eta>=0")
return 0
oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
updateEk(oS, j)
if (abs(oS.alphas[j] - alphaJold) < oS.tol):
print("j not moving enough")
return 0
oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])
updateEk(oS, i)
b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[i,:]*oS.X[j,:].T
b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[j,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[j,:]*oS.X[j,:].T
if (0 < oS.alphas[i]<oS.C):
oS.b = b1
elif (0 < oS.alphas[j]<oS.C):
oS.b = b2
else:
oS.b = (b1 + b2)/2.0
return 1
else:
return 0
def calcWs(dataMat, labelMat, alphas):
alphas, dataMat, labelMat = array(alphas), array(dataMat), array(labelMat)
w = dot((tile(labelMat.reshape(1, -1).T, (1, 2)) * dataMat).T, alphas)
return w.tolist()
def smoP(dataMatIn, classLabels, C, toler, maxIter):
oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler)
iter = 0
entireSet = True
alphaPairsChanged = 0
while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
alphaPairsChanged = 0
if entireSet:
for i in range(oS.m):
alphaPairsChanged += innerL(i,oS)
print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
iter += 1
else:
nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
for i in nonBoundIs:
alphaPairsChanged += innerL(i,oS)
print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
iter += 1
if entireSet:
entireSet = False
elif (alphaPairsChanged == 0):
entireSet = True
print("iteration number: %d" % iter)
return oS.b,oS.alphas,oS
def showClassifer(dataMat,labelMat,alphas, w, b):
data_plus = []
data_minus = []
for i in range(len(dataMat)):
if labelMat[i] > 0:
data_plus.append(dataMat[i])
else:
data_minus.append(dataMat[i])
data_plus_np = array(data_plus)
data_minus_np = array(data_minus)
plt.scatter(transpose(data_plus_np)[0], transpose(data_plus_np)[1], s=30, alpha=0.7)
plt.scatter(transpose(data_minus_np)[0], transpose(data_minus_np)[1], s=30, alpha=0.7)
x1 = max(dataMat)[0]
x2 = min(dataMat)[0]
a1, a2 = w
b = float(b)
a1 = float(a1[0])
a2 = float(a2[0])
y1, y2 = (-b- a1*x1)/a2, (-b - a1*x2)/a2
plt.plot([x1, x2], [y1, y2])
for i, alpha in enumerate(alphas):
if 0.6>abs(alpha) > 0:
x, y = dataMat[i]
plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')
if 50==abs(alpha) :
x, y = dataMat[i]
plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='yellow')
plt.show()
if __name__ == "__main__":
x = [[1,8],[3,20],[1,15],[3,35],[5,35],[4,40],[7,80],[6,49],[1.5,25],[3.5,45],[4.5,50],[6.5,15],[5.5,20],[5.8,74],[2.5,5]]
y = [1,1,-1,-1,1,-1,-1,1,-1,-1,-1,1,1,-1,1]
b, alphas, oS = smoP(dataMatIn=x,classLabels=y,C=50, toler=0.001,maxIter=400)
w = calcWs(x,y,alphas)
showClassifer(x,y,alphas, w, b)
运行结果：
其中画圈的就是支持向量机的支持向量，也就是α不为0的样本是对超平面位置有影响的样本点。
SMO算法实现细节可能还是没完全明白，以后懂了再来补吧。
参考
支持向量机SVM-手写笔记&手动实现
https://www.cnblogs.com/ssyfj/p/13363526.html
SVM SMO算法代码详细剖析
Original: https://blog.csdn.net/qq_52785473/article/details/127262872
Author: Icy Hunter
Title: 机器学习之支持向量机（SVM）的求解方法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/613822/
转载文章受原作者版权保护。转载请注明原作者出处！