【机器学习实战-python3】支持向量机(Support Vecrtor Machines SVM)

3/3/2017来源:C/C++教程人气:1333

有人认为SVM是最好的现成的分类器,“现成”指的是分类器不加修改即可直接使用,意味着直接应用SVM可以取得较低的错误率,对训练集之外的数据点做出很好的分类决策。 SVM有许多实现,这里介绍其中一种最流行的实现,即序列最小优化(SMO)算法,然后添加kernel函数将SVM拓展到更多数据集。 SVM是基于最大间隔分隔数据,若所给数据是二维的,则分隔线为一条直线,若数据为三维的,则分割线为一个平面,依次类推,随着数据维数的增加,分隔面就变成了超平面。而最大间隔,是让离分隔面最近的点,确保他们离分隔面尽可能远。SVM本身是一个二类分类器,若要解决多类问题,需要修改SVM。

一、寻找最大间隔 SVM中为了找到划分数据集的最佳分隔,确保最近的点到分隔的垂线最短,因此转化为了一个优化问题。这里分隔面可以定义为:wT+b,将输入数据给分类器,会输出分隔标签,这里采用sigmoid函数,即f(wT+b),可输出1/-1(与1或0无异)。间隔则通过label∗f(wT+b)来计算。找到最小间隔的数据点,最大化其与间隔的距离。argmaxw,b{minn(label⋅(wT+b))⋅1||w||} 这里 {minn(label⋅(wT+b))⋅1||w||}是点到间隔的几何间隔,与上面所说的label∗f(wT+b)的函数间隔意义相同。这里固定label∗f(wT+b)>=1.0 去优化1||w||,采用拉格朗日乘子法。关于SVM的详细推到公式,可参考其他相关材料:如PRML原书pdf版本

二、SMO高效优化算法 John Platt所提出的SMO算法用于训练SVM,将最大优化问题分解为多个小优化问题,求解的结果是完全一致的,且SMO算法求解的时间短很多。 为了得到分隔的超平面,就需要得到最优的alpha值,上面所提到的最优化式子可化为下式:∑αi⋅labeli=0SMO算法的目标就是求出一系列alpha和b,一旦求出alpha就很容易计算出权重向量从而得到分个超平面。SMO算法的工作原理是,每次循环对两个alpha进行优化处理,得到一对合适的alpha后,就增大其中一个同时减小另一个。这里的“合适”指的是这两个alpha必须在间隔边界之外,并且两个alpha还没有经过区间化处理或者不在边界上。下面是导入数据的代码。

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 def selectJrand(i,m): #i表示alpha的下标,m表示alpha的总数 j=i while(j==i): j=int(random.uniform(0,m)) #简化版SMO,alpha随机选择 return j def clipAlpha(aj,H,L): #辅助函数,用于调整alpha范围 if aj>H: aj=H if L>aj: aj=L return aj

可以看出,类别标签为1与-1

这里写图片描述

下面进入简化版的SMO,伪代码大致如下: 创建一个alpha向量并将其初始化为0向量 当迭代次数小于最大迭代次数(外循环) 对数据集中每个数据向量(内循环): 如果该数据向量可以被优化: 随机选择另外一个数据向量,同时优化这个向量 如果两个向量都不能被优化,退出内循环 如果所有向量都未被优化,增加迭代数,进入下次循环。