ML算法：SVM
SVM
实验目标
学习支持向量机的原理，用两种不同的算法寻找支持向量机的解，并完成比较。
实验原理
对于给定样本集，SVM的任务就是基于样本集在样本空间中确定一个划分超平面，将不同类别的样本分开，即找到w,b使得$y(w^T+b)\ge1$成立，并实现最大化间隔，即最大化$||w||^{-1}$。为求解w的最优解，，由于实验中的数据并不完全是线性可分的，因此采用硬间隔的方法求解存在困难，本次实验分别采用梯度下降法和SMO（序列最小优化算法）来求解。
SVM的任务：
- 梯度下降法
SVM中的梯度下降方法也类似于逻辑回归中的梯度下降原理，根据迭代的值计算损失和梯度更新参数，每次迭代过程中，计算当前的$y*(w^T+b)$的值，将值小于一的样本进行累加计算梯度，根据梯度和学习率更新w和b。
- SMO
SMO算法是John Platt在《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》一文中提出的算法，对于解决稀疏数据集上的问题有着很高的效率。已知SVM的对偶问题为：
其中，我们要对$（\alpha_1,\alpha_2,…,\alpha_N)$进行优化，但数据集较大时，直接对N个参数进行优化的效率将很低，因此采用SMO算法求解，SMO的原理是将N个参数的优化问题转化为多个子问题，其中每个子问题只对两个参数进行优化，每次计算并选取一对最优的$(\alpha_i,\alpha_j)$更新对应的$\alpha$值。
实验步骤
梯度下降法
- 损失函数$loss=1/2*w^tw+\sum_{i=1}^mmax{0,1-y_i(wx_i-b)}$
mar=y*(np.dot(X,self.w)+self.b)
lo=0.5*np.sum(np.square(self.w))+np.maximum(0, 1 - mar).sum()
if lo<tol :
break- 损失函数的梯度$\Delta=\lambda w-\sum{i=1}^mI|wx_i+b<1|*x_iy_i$，根据梯度更新w和b
for i in range(len(y)):
if y[i]*(X[i].dot(self.w)+self.b) <= 1:
self.w -= lr * (-y[i]*X[i].reshape((len(X[i]),1)))
self.b -= lr * -y[i]SMO
- 预先存储部分数据，提高运算效率
self.m=X.shape[0]
self.alpha=np.zeros((self.m,1))#每次迭代更新
self.err=-self.y.flatten()#每次迭代更新
#以下是为了方便计算loss的值，不需要计算loss值时无需计算，更节省时间和内存
self.kappa_x=self.kappa(self.X,self.X)
self.mulyx=np.outer(self.y,self.y)*self.kappa_x
self.outer_a=np.zeros((self.m,self.m))#每次迭代更新- 损失函数$\sum _\alpha ^N \alpha _i-1/2*\sum_{i=1}^N\sum_{j=1}^Ny_iy_j\alpha_i\alpha_jx_i^Tx_j$
0.5*(np.sum(self.mulyx*self.outer_a)-np.sum(self.alpha))- 选取合适的$(\alpha _i,\alpha_j)$
- 统计误差不为0的索引值，有不为零的误差时统计误差
- 没有为零误差时，随机选取$\alpha$
if arrlen> 1:
t=np.argmax(np.abs(self.err-ei))
if t!=i and self.step(t,i)==1:
return 1
arr=np.where((self.alpha!=0 )& (self.alpha!=self.c))[0]
ra=np.roll(arr,np.random.choice(np.arange(self.m)))
for j in ra:
if j!=i and self.step(j,i)==1:
return 1
ra=np.roll(np.arange(self.m), np.random.choice(np.arange(self.m)))
for j in ra:
if j!=i and self.step(j,i)==1:
return 1- 每次迭代更新数据
if y1 !=y2:#取L，H
t1=max(0,a2-a1)
t2=min(0,a2-a1)+self.c
else:
t1=max(self.c,a1+a2)-self.c
t2=min(self.c,a1+a2)
if t1==t2:
return 0
t3=k11+k22-2*k12
if t3>0:#求解\alpha新值
al2 = a2+y2*(e1-e2)/t3
if al2<t1:
al2=t1
elif al2>t2:
al2=t2
else:
#意外情况,很少出现
self.alpha[i2]=t1
loss1=self.calloss()
self.alpha[i2]=t2
loss2=self.calloss()
self.alpha[i2]=a2
if loss1-loss2>self.eps:
al2=t2
elif loss2-loss1>self.eps:
al2=t1
else:
al2=a2if al2<=0:
al2=0.0
#截断处理
al2=max(al2,0.0)
al2=min(al2,self.c)
if np.abs(al2-a2)<self.eps*(al2 + a2 + self.eps):
return 0
al1=a1+(a2-al2)*y1*y2
b1 = e1 + y1*(al1 - a1)*k11 + y2*(al2 - a2)*k12 + self.b
b2 = e2 + y1*(al1 - a1)*k12 + y2*(al2 - a2)*k22 + self.b
#根据以上的al1，al2，b1，b2更新参数的值：b,alpha,err- 迭代
- change：上一轮迭代中发生改变的数目
- entire：是否对全部的参数进行检查
- ep:记录迭代次数，迭代次数到最大时退出循环
while change>0 or entire:
change=0
if entire :
for i in range(self.m):
if self.examine(i):
change+=1
else:
ra=np.where((self.alpha!=0) & (self.alpha!=self.c))[0]
for i in ra:
if self.examine(i):
change+=1
if(ep>self.max_iters):
break
if entire==1:
entire=0
elif change==0:
entire=1数据处理，预测和分析
本次实验对训练集和测试集按照8：2进行划分：
mu = np.mean(X_norm,0)
sigma = np.std(X_norm,0)
for i in range(X.shape[1]):
X_norm[:,i]=(X_norm[:,i]-mu[i])/sigma[i]
y=np.array(y)
num=np.random.permutation(len(y))
X_norm=X_norm[num]
y=y[num]
a=int(0.2*len(y))
X_test=X_norm[0:a-1,:]
X_train=X_norm[a:,:]
y_test=y[0:a-1]
y_train=y[a:]预测函数：
m,n=X.shape
##SMO: p=np.dot(self.kappa(X, self.X),self.alpha*self.y) - self.b
##GD: p=np.dot(X,self.w)+self.b
for i in range(m):
ans=np.sign(p[i])
res.append(ans)损失曲线：
loss=model2.fit(X_train,y_train)
x = np.arange(1,len(loss)+1)
plt.plot(x,loss)
plt.xlabel(u"times")
plt.ylabel(u"loss-value")
plt.show()数据分析
pred2 = model.predict(X_test)
m = len(y_test)
for i in range(m):
if(y_test[i]>0 and pred2[i]>0):
sum+=1
if(y_test[i]<0 and pred2[i]<0):
sum+=1
print(sum/m) #SVM预测的准确率
for i in range(m):
if pred1[i]==pred2[i]:
i+=1
print(i/m) #SVM1，SVM2的预测相似率实验结论和分析
梯度下降法
参数解释：
X，训练集X
y，训练集
lr，学习率，默认为0.001
max_iters，最大迭代次数，默认为1000
tol，最小误差， 0.0001
训练一次的损失曲线如下所示（数据规模为10000，维度为20，训练时间为41.2s），初始的loss值较大是训练时预设了w的值为随机生成np.random.randn(col,1).
准确率：96.1%
可以看出梯度下降的收敛效果较好，在训练次数较低时损失函数显著降低，得到的结果准确率也较高。
而当学习率变大（改为lr=0.1)时，损失函数会发生震荡，导致预测的准确率降低
SMO
参数解释：
- dim：数据的维度
- c：松弛变量，默认为1.0
- eps：容错率，默认为0.01
- max_iters:最大迭代次数，默认为1000
- kappa函数：选取的核函数类型，默认为linear
训练一次的损失曲线（数据规模为2000，20维，训练次数1000，训练时间10s）
梯度下降法和SMO的对比
总体来说，梯度下降法和SMO的准确率均在90%以上，收敛的速度都很快，对结果预测的相似度为97%，两种模型的训练效果均较好，梯度下降的准确率相对更高，训练过程相对更直观；SMO的优势在于每次只对最小的问题进行优化，问题规模小，占用的内存少，对硬件的要求低，对于不同的参数，或者较大或较小的数据集都有较好的结果。
