100天搞定机器学习|Day16 通过内核技巧实现SVM
100天搞定机器学习|Day16 通过内核技巧实现SVM
svm算法
01
再简单回顾一下svm算法的思路，详细推导请看前情回顾相关内容，或在文末下载之前推荐的《理解SVM 的三层境界》PDF版。
1. svm的关键是找最优分类超平面，也即最大间隔超平面
样本与超平面距离
求最大间隔分离超平面即：
经过一系列推导可得为优化下面原始目标：
2. 构建拉格朗日函数：
可以将1中的优化目标转换为拉格朗日的形式（通过各种对偶优化，KKD条件），最后目标函数为：
只需要最小化上述目标函数，其中的α为原始优化问题中的不等式约束拉格朗日系数。
3. 对2中最后的式子分别w和b求导可得：
由上面第1式子可以知道，如果我们优化出了α，则直接可以求出w了，即模型的参数搞定。而上面第2个式子可以作为后续优化的一个约束条件。
4. 对2中最后一个目标函数用对偶优化理论可以转换为优化下面的目标函数：
而这个函数可以用常用的优化方法求得α，进而求得w和b。
5. 在预测时有：
那个尖括号我们可以用核函数代替，这也是svm经常和核函数扯在一起的原因。
6. 最后是关于松弛变量的引入，因此原始的目标优化公式为：
此时对应的对偶优化公式为：
与前面的相比只是α多了个上界。
回顾结束，再谈一下需要对svm算法需要熟悉到什么程度，这里引用七月在线创始人July的微博：
SVM理解到了一定程度后，是的确能在脑海里从头至尾推导出相关公式的，最初分类函数，最大化分类间隔，max1/||w||，min1/2||w||^2，凸二次规划，拉格朗日函数，转化为对偶问题，SMO算法，都为寻找一个最优解，一个最优分类平面。一步步梳理下来，为什么这样那样，太多东西可以追究，最后实现。
sklearn.svm
02
Sklearn包含的常用算法里介绍过常用的算法，scikit-learn中学习模式的调用，有很强的统一性，调用机器学习的方法都是一个道理，算法就是一个类，其中包含fit(),predict()等等许多方法，我们只要输入训练样本和标记，以及模型的一些可能的参数，自然就直接出分类的结果。
总结起来就是8个字：导入-建模-训练-预测
先看个小例子，然后再细解。
import numpy as np
X = np.array([[-1, -1], [-2, -1], [1, 1], [2, 1]])
y = np.array([1, 1, 2, 2])
from sklearn.svm import NuSVC
clf = NuSVC()
clf.fit(X, y)
print(clf.fit(X,y))
NuSVC(cache_size=200, class_weight=None, coef0=0.0,
decision_function_shape='ovr', degree=3, gamma='auto', kernel='rbf',
max_iter=-1, nu=0.5, probability=False, random_state=None,
shrinking=True, tol=0.001, verbose=False)
print(clf.predict([[-0.8, -1]]))
[1] 更多案例，大家可以移步scikit-learn官网
https://scikit-learn.org/stable/modules/svm.html#svm-classification
scikit-learn中SVM的算法库分为两类，
一类是分类的算法库，包括SVC， NuSVC，和LinearSVC 3个类。
另一类是回归算法库，包括SVR， NuSVR，和LinearSVR 3个类。
相关的类都包裹在sklearn.svm模块之中。
对于SVC， NuSVC，和LinearSVC 3个分类的类，SVC和 NuSVC差不多，区别仅仅在于对损失的度量方式不同，而LinearSVC从名字就可以看出，他是线性分类，也就是不支持各种低维到高维的核函数，仅仅支持线性核函数，对线性不可分的数据不能使用。
同样的，对于SVR， NuSVR，和LinearSVR 3个回归的类， SVR和NuSVR差不多，区别也仅仅在于对损失的度量方式不同。LinearSVR是线性回归，只能使用线性核函数。
下面我们只说看一下SVC详细用法，NuSVC、LinearSVC建议大家看一下刘建平Pinard@cnblogs统计的表格
https://www.cnblogs.com/pinard/p/6117515.html
SVC函数一共有14个参数：
SVC参数解释
(1)C: 目标函数的惩罚系数C，用来平衡分类间隔margin和错分样本的，default C = 1.0；
(2)kernel：参数选择有RBF, Linear, Poly, Sigmoid, 默认的是"RBF";
(3)degree：if you choose 'Poly' in param 2, this is effective, degree决定了多项式的最高次幂；
(4)gamma：核函数的系数('Poly', 'RBF' and 'Sigmoid'), 默认是gamma = 1 / n_features;
(5)coef0：核函数中的独立项，'RBF' and 'Poly'有效；
(6)probablity: 可能性估计是否使用(true or false)；
(7)shrinking：是否进行启发式；
(8)tol(default = 1e - 3): svm结束标准的精度;
(9)cache_size: 制定训练所需要的内存(以MB为单位)；
(10)class_weight: 每个类所占据的权重，不同的类设置不同的惩罚参数C, 缺省的话自适应；
(11)verbose: 跟多线程有关;
(12)max_iter: 最大迭代次数，default = 1， if max_iter = -1, no limited;
(13)decision_function_shape ：‘ovo’ 一对一, ‘ovr’ 多对多 or None 无, default=None
(14)random_state ：用于概率估计的数据重排时的伪随机数生成器的种子。核函数如何选取
03
核函数
1）线性核函数（Linear Kernel）表达式为：K(x,z)=x∙z，就是普通的内积，LinearSVC 和 LinearSVR 只能使用它。
2) 多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为：
，其中，γ,r,d都需要自己调参定义,比较麻烦。
3）高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是libsvm默认的核函数，当然也是scikit-learn默认的核函数。表达式为：
， 其中，γ大于0，需要自己调参定义。
4）Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为：
， 其中，γ,r都需要自己调参定义。
更多案例，大家可以移步scikit-learn官网
最常用的是核函数是Linear与RBF，需要注意的是对数据归一化处理。
1、Linear：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
2、RBF：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。
吴恩达也曾经给出过选择核函数的方法：
1、如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM 2、 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel 3、 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况
Kernel Trick实现svm
04
主要思想及算法流程来自李航的《统计学习方法》和之前推荐的《理解SVM的三重境界》（文末有PDF）
#coding=utf-8
import time
import random
import numpy as np
import math
import copy
a=np.matrix([[1.2,3.1,3.1]])
#print a.astype(int)
#print a.A
class SVM:
def __init__(self,data,kernel,maxIter,C,epsilon):
self.trainData=data
self.C=C #惩罚因子
self.kernel=kernel
self.maxIter=maxIter
self.epsilon=epsilon
self.a=[0 for i in range(len(self.trainData))]
self.w=[0 for i in range(len(self.trainData[0][0]))]
self.eCache=[[0,0] for i in range(len(self.trainData))]
self.b=0
self.xL=[self.trainData[i][0] for i in range(len(self.trainData))]
self.yL=[self.trainData[i][1] for i in range(len(self.trainData))]
def train(self):
#support_Vector=self.__SMO()
self.__SMO()
self.__update()
def __kernel(self,A,B):
#核函数 是对输入的向量进行变形 从低维映射到高维度
res=0
if self.kernel=='Line':
res=self.__Tdot(A,B)
elif self.kernel[0]=='Gauss':
K=0
for m in range(len(A)):
K+=(A[m]-B[m])**2
res=math.exp(-0.5*K/(self.kernel[1]**2))
return res
def __Tdot(self,A,B):
res=0
for k in range(len(A)):
res+=A[k]*B[k]
return res
def __SMO(self):
#SMO是基于 KKT 条件的迭代求解最优化问题算法
#SMO是SVM的核心算法
support_Vector=[]
self.a=[0 for i in range(len(self.trainData))]
pre_a=copy.deepcopy(self.a)
for it in range(self.maxIter):
flag=1
for i in range(len(self.xL)):
#print self.a
#更新 self.a 使用 机器学习实战的求解思路
#计算 j更新
diff=0
self.__update()
#选择有最大误差的j 丹麦理工大学的算法是 对j在数据集上循环, 随机选取i 显然效率不是很高
#机器学习实战 硬币书表述正常 代码混乱且有错误 启发式搜索
Ei=self.__calE(self.xL[i],self.yL[i])
j,Ej=self.__chooseJ(i,Ei)
#计算 L H
(L,H)=self.__calLH(pre_a,j,i)
#思路是先表示为self.a[j] 的唯一变量的函数 再进行求导（一阶导数=0 更新）
kij=self.__kernel(self.xL[i],self.xL[i])+self.__kernel(self.xL[j],self.xL[j])-2*self.__kernel(self.xL[i],self.xL[j])
#print kij,"aa"
if(kij==0):
continue
self.a[j] = pre_a[j] + float(1.0*self.yL[j]*(Ei-Ej))/kij
#下届是L 也就是截距,小于0时为0
#上届是H 也就是最大值,大于H时为H
self.a[j] = min(self.a[j], H)
self.a[j] = max(self.a[j], L)
#self.a[j] = min(self.a[j], H)
#print L,H
self.eCache[j]=[1,self.__calE(self.xL[j],self.yL[j])]
self.a[i] = pre_a[i]+self.yL[i]*self.yL[j]*(pre_a[j]-self.a[j])
self.eCache[i]=[1,self.__calE(self.xL[i],self.yL[i])]
diff=sum([abs(pre_a[m]-self.a[m]) for m in range(len(self.a))])
#print diff,pre_a,self.a
if diff < self.epsilon:
flag=0
pre_a=copy.deepcopy(self.a)
if flag==0:
print (it,"break")
break
#return support_Vector
def __chooseJ(self,i,Ei):
self.eCache[i]=[1,Ei]
chooseList=[]
#print self.eCache
#从误差缓存中得到备选的j的列表 chooseList 误差缓存的作用：解决初始选择问题
for p in range(len(self.eCache)):
if self.eCache[p][0]!=0 and p!=i:
chooseList.append(p)
if len(chooseList)>1:
delta_E=0
maxE=0
j=0
Ej=0
for k in chooseList:
Ek=self.__calE(self.xL[k],self.yL[k])
delta_E=abs(Ek-Ei)
if delta_E>maxE:
maxE=delta_E
j=k
Ej=Ek
return j,Ej
else:
#最初始状态
j=self.__randJ(i)
Ej=self.__calE(self.xL[j],self.yL[j])
return j,Ej
def __randJ(self,i):
j=i
while(j==i):
j=random.randint(0,len(self.xL)-1)
return j
def __calLH(self,pre_a,j,i):
if(self.yL[j]!= self.yL[i]):
return (max(0,pre_a[j]-pre_a[i]),min(self.C,self.C-pre_a[i]+pre_a[j]))
else:
return (max(0,-self.C+pre_a[i]+pre_a[j]),min(self.C,pre_a[i]+pre_a[j]))
def __calE(self,x,y):
#print x,y
y_,q=self.predict(x)
return y_-y
def __calW(self):
self.w=[0 for i in range(len(self.trainData[0][0]))]
for i in range(len(self.trainData)):
for j in range(len(self.w)):
self.w[j]+=self.a[i]*self.yL[i]*self.xL[i][j]
def __update(self):
#更新 self.b 和 self.w
self.__calW()
#得到了self.w 下面求b
#print self.a
maxf1=-99999
min1=99999
for k in range(len(self.trainData)):
y_v=self.__Tdot(self.w,self.xL[k])
#print y_v
if self.yL[k]==-1:
if y_v>maxf1:
maxf1=y_v
else:
if y_v<min1:
min1=y_v
self.b=-0.5*(maxf1+min1)
def predict(self,testData):
pre_value=0
#从trainData 改成 suport_Vector
for i in range(len(self.trainData)):
pre_value+=self.a[i]*self.yL[i]*self.__kernel(self.xL[i],testData)
pre_value+=self.b
#print pre_value,"pre_value"
if pre_value<0:
y=-1
else:
y=1
return y,abs(pre_value-0)
def save(self):
pass
def LoadSVM():
pass另存为SVM.py
from SVM import *
data=[
[[1,1],1],
[[2,1],1],
[[1,0],1],
[[3,7],-1],
[[4,8],-1],
[[4,10],-1],
]#如果为gauss核的话 ['Gauss',标准差]
svm=SVM(data,'Line',1000,0.02,0.001)
print (svm.predict([4,0]))
(1, 0.6300000000000001)
print (svm.a)
[0.02, 0.0, 0.0, 0.0, 0.0, 0.02]
print (svm.w)
[-0.06, -0.18000000000000002]
print (svm.b)
0.8700000000000001