关闭
当前位置:首页 - 西甲联赛 - 正文

湖南科技大学,机器学习实战项目-支撑向量机,you

admin 2019-04-14 175°c

支撑向量机 概述

支撑向量机(Support Vector Machines, SVM):是一种机器学习算法。

  • 支撑向量(Support Vector)便是离分隔超平面最近的那些点。
  • 机(Machine)便是表明一种算法,而不是表明机器。

支撑向量机 场景

  • 要给左右两头的点进行分类
  • 显着发现:挑选D会比B、C分隔的作用要好许多。
机器学习实战项目-支撑向量机

支撑向量机 原理

SVM 作业原理

关于上述的苹果和香蕉,咱们幻想为2种生果类型的炸弹。(确保距离最近的炸弹,距离它们最远)

  1. 寻觅最大分类距离
  2. 转而经过拉格朗日函数求优化的问题
  • 数据能够经过画一条直线就能够将它们彻底分隔,这组数据叫线性可分(linearly separable)数据,而这条分隔直线称为分隔超平面(separating hyperplane)。
  • 假如数据集上升到1024维呢?那么需求1023维来分隔数据集,也就说需求N-1维的方针来分隔,这个方针叫做超平面(hyperlane),也便是分类的决议计划鸿沟。

寻觅最大距离

为什么寻觅最大距离

摘抄地址:http://slideplayer.com/slide/8610144 (第12条信息winscp)
Support Vector Machines: Slide 12 Copyright 2001, 2003, Andrew W. Moore Why Maximum Margin?
denotes +1 denotes -1 f(x,w,b) = sign(w. x - b) The maximum margin linear classifier is the linear classifier with the, um, maximum margin.
This is the simplest kind of SVM (Called an LSVM) Support Vectors are those datapoints that the margin pushes up against
1.Intuitively this f舍利子eels safest.
2.If we’ve made a small error in the location of the boundary (it’s been jolted in its perpendicular direction) this gives us least chance of causing a misclassification.
3.CV is easy since the model is immune to removal of any non-support-vector datapoints.
4.There’s some theory that this is a good thing.
5.Empirically it works very very well.
* * *
1. 直觉上是安全的
2. 假如咱们在鸿沟的方位发作了一个小过错(它在笔直方向上被倒置),这给咱们最小的过错分类时机。
3. CV(Computer Vision 核算机视觉 - 这缩写看着可怕)很简略,由于该模型对任何非支撑向量数据点的去除是免疫的。
4. 有一些理论,这是一件功德。
5. 一般它的作业非常好。

怎样寻觅最大距离

点到超平面的距离

  • min关于w,bL(w,b,)=12∗||w||2+∑i=1ni∗[1−label∗(wTx+b)]
  • 便是求L(w,b,a)关于[w, b]的偏导数, 得到w和b的值,并化简为:L和a的方程。
  • 参阅: 假如公式推导仍是不明白,也能够参阅《核算学习办法》李航-P103<学习的对偶算法>


松懈变量(slack variable)

参阅地址:http://blog.csdn.net/wusecaiyun/article/details/49659183

  • 咱们知道简直一切的数据都不那么洁净, 经过引进松懈变量来 答应数据点能够处于分隔面过错的一侧。
  • 约束条件: C>=a>=0
  • C>=a>=0 而且 ∑
  • m
  • i=1
  • a
  • i
  • ⋅label
  • i
  • =0
  • ∑i=1mailabeli=0
  • 总的来说:

  • 表明 松懈变量
  • 常量C是 赏罚因子, 表明离群点的权重(用于操控“最大化距离”和“确保大部分点的函数距离小于1.0” )
  • label∗(w
  • T
  • x+b)>1
  • label∗(wTx+b)>1 and alpha = 0 (在鸿沟外,便是pv非支撑向量)
  • label∗(w
  • T
  • x+b)=1
  • label∗(wTx+b)=1 and 0< alpha < C (在切割超平面上,就支撑向量)
  • label∗(w
  • T
  • x+b)<1
  • label∗(wTx+b)<1 and alpha = C (在切割超平面内,是误差点 -> C表明它该遭到的赏罚因子程度)
  • 参阅地址:https://www.zhihu.com/question/48351234/answ挥洒自如江一龙er/110486455
  • C值越大,表明离群点影响越大,就越简略过度拟合;反之有或许欠拟合。
  • 咱们看到,方针函数操控了离群点的数目和程度,使大部分样本点依然恪守约束条件。
  • 例如:正类有10000个样本,而负类只给了100个(C越大表明100个负样本的影响越大,就会呈现过度拟合,所以C决议了负样本对模型拟合程度的影响!,C便是一个非常要害的优化点!)
  • 这必定论非常直接,SVM中的首要作业便是要求解 alpha.

SMO 高效优化算法

  • SVM有许多种完成,最盛行的一种完成是: 序列最小优化(Sequential Minimal Optimization, SMO)算法。
  • 下面还会介绍一种称为 核函数(kernel) 的办法将SVM扩展到更多数据集上。
  • 注湖南科技大学,机器学习实战项目-支撑向量机,you意:SVM几许意义比较直观,但其算法完成较杂乱,牵扯许多数学公式的推导。

序列最小优化(Sequential Minimal Optimization, SMO)

  • 创立作者:John Platt
  • 创立时刻:1996年
  • SMO用处:用于练习 SVM
  • SMO方针:求出一系列 alpha 和 b,一旦求出 alpha,就很简略核算出权重向量 w 并得到分隔超平面。
  • SMO思维:是将大优化问题分解为多个小优化问题来求解的。
  • SMO原理:每次循环挑选两个 alpha 进行优化处理,一旦找出一对适宜的 alpha,那么就增大一个一起削减一个。
  • 这儿指的适宜必需求契合必定的条件
  1. 这两个 alpha 必需求在距离鸿沟之外
  2. 这两个 alpha 还没有进行过区间化处理或许不在鸿沟上。
  • ∑i=1mailabeli=0;假如只是修正一个 alpha,很或许导致约束条件失效。

SMO 伪代码大致如下:

创立一个 alpha 向量并将其初始化为0向量
当迭代次数小于最大迭代次数时(外循环)
对数据会集的每个数据向量(内循环):
假如该数据向量能够被优化
随机挑选别的一个数据向量
一起优化这两个向量
假如两个向量都不能被优化,退出内循环
假如一切向量都没王覃渝被优化,添加迭代数目,持续下一次循环

SVM 开发流程

搜集数据:能够运用恣意办法。
预备数据:需求数值型数据。
剖析数据:有助于可视化分隔超平面。
练习算法:SVM的大部分时刻都源自练习,该进程首要完成两个参数的调优。
测验算法:非常简略的核算进程就能够完成。
运用斗破天穹之碧落黄泉算法:简直一切分类问题都能够运用SVM,值得一提的是,SVM自身是一个二类分类器,对多类问题运用SVM需求对代码做一些修正。

SVM 算法特色

长处:泛化(由详细的、单个的扩大为一般的,便是说:模型练习完后的新样本)过错率低,核算开支不大,成果易了解。
缺陷:对参数调理和核函数的挑选灵敏,原始分类器不加修正仅适合于处理二分类问题。
运用数据类型:数值型和标称型数据。

讲义事例(无核函数)

项目概述

对小规模数据点进行分类

开发流程

搜集数据

文本文件格局:

3.542485 1.977398 -1
3.018896 2.556416 -1
7.551510 -1.580030 1
2.114999 -0.004466 -1
8.127113 1.274372 1

预备数据

def loadDataSet(fileName):
"""
对文件进行逐行解析,然后得到第行的类标签和整个特征矩阵
Args:
fileName 文件名
Returns:
dataMat 特征矩阵
labelMat 类标签
"""
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 smoSimple(dataMatIn, classLabels, C, toler, maxIter):
"""smoSimple
Args:
dataMatIn 特征调集
湖南科技大学,机器学习实战项目-支撑向量机,youclassLabels 类别标签
C 松懈变量(常量值),答应有些数据点能够处于分隔面的过错一侧。
操控最大化距离和确保大部分的函数距离小于1.0这两个方针的权重。
能够经过调理该参数到达不同的成果。
toler 容错率(是指在某个体系中能减小一些要素或挑选对某个体系发作不稳定的概率。)
maxIter 退出前最大的循环次数
Returns:
b 模型的常量值
alphas 拉格朗日乘子
"""
dataMatrix = mat(dataMatIn)
# 矩阵转置 和 .T 相同的功用
labelMat = mat(classLabels).transpose()
m, n = shape(dataMatrix)
# 初始化 b和alphas(alpha有点相似权重值。)
b = 0
alphas = mat(zeros((m湖南科技大学,机器学习实战项目-支撑向量机,you, 1)))
# 没有任何alpha改动的状况下遍历数据的次数
iter = 0
while (iter < maxIter):
# w = calcWs(alphas, dataMatIn, classLabels)
# print("w:", w)
# 记载alpha是否现已进行优化,每次循环时设为0,然后再对整个调集次序遍历赵传
alphaPairsChanged = 0
for i in range(m):
# print 'alphas=', alphas
# print 'labelMat=', labelMat
# print 'multiply(alphas, labelMat)=', multiply(alphas, labelMat)
# 咱们猜测的类别 y[i] = w^Tx[i]+b; 其间由于 w = (1~n) a[n]*lable[n]*x[n]
fXi = float(multiply(alphas, labelMat).T*(dataMatrix*dataMatrix[i, :].T)) + b
# 猜测成果与实在成果比对,核算误差Ei
Ei = fXi - float(labelMat[i])
# 约束条件 (KKT条件是处理最优化问题的时用到的一种办法。咱们这儿说到的最优化问题一般是指关于给定的某一函数,求其在指定作用域上的大局最小值)
# 0<=alphas[i]<=C,但由于0和C是鸿沟值,咱们无法进行优化,由于需求添加一个alphas和下降一个alphas。
# 表明发作过错的概率:labelMat[i]*Ei 假如超出了 toler, 才需求优化。至于正负号,咱们考虑绝对值就对了。
'''
# 查验练习样本(xi, yi)是否满意KKT条件
yi*f(i) >= 1 and alpha = 0 (outside the boundary)
yi*f(i) == 1 and 0< C (on the boundary)
yi*f(i) <= 1 and alpha = C (between the boundary)
'''
if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
# 假如满意优化的条件,咱们就随机选取非i的一个点,进行优化比较
j = selectJrand(i, m)
# 猜测j的成果
fXj = float(multiply(alphas, labelMat).T*(dataMatrix*dataMatrix[j, :].T)) + b
Ej = fXj - float(labelMat[j])
alphaIold = alphas[i].copy()
alphaJold = alphas[j].copy()
# L和H用于将alphas[j]调整到0-C之间。假如L==H,就不做任何改动,直接履行continue句子
# labelMat[i] != labelMat[j] 表明异侧,就相减,不然是同侧,就相加。
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是alphas[j]的最优修正量,假如eta==0,需求退出for循环的当时迭代进程
# 参阅《核算学习办法》李航-P125~P128<序列最小最优化算法>
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]值
alphas[j] -= labelMat[j]*(Ei - 天兆食府Ej)/eta
# 并运用辅佐函数,以及L和H对其进行调整
alphas[j] = clipAlpha(alphas[j], H, L)
# 查看alpha[j]是否只是细微的改动,假如是的话,就退出for循环。
if (abs(alphas[j] - alphaJold) < 0.00001):
print("j not moving enough")
continue
# 然后alphas[i]和alphas[j]相同进行改动,尽管改动的巨细相同,可是改动的方向正好相反
alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
# 在对a超级演说家lpha[i], alpha[j] 进行优化之后,给这两个alpha值设置一个常数b。
# w= [1~n] ai*yi*xi => b = yj- [1~n] ai*yi(xi*xj)
# 所以: b1 - b = (y1-y) - [1~n] yi*(a1-a)*(xi*x1)
# 为什么减2遍? 由于是 减去[1~n],正好2个变量i和j,所以减2遍
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))
# 在for循环外,查看alpha值是否做了更新,假如在更新则将iter设为0后持续运转程序
# 知道更新结束后,iter次循环无变化,才推出循环。
if (alphaPairsChanged == 0):
iter += 1
else:
iter = 0
print("iteration number: %d" % iter)
return b, alphas

完好代码地址:SVM简化版,运用简化版SMO算法处理小规模数据集: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-simple.py

完好代码地址:SVM完好版,运用完好 Platt SMO算法加快优化,优化点:挑选alpha的办法不同: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-complete_Non-Kernel.py

核函数(kernel) 运用

  • 关于线性可分的状况,作用显着
  • 关于非线性的状况也相同,此刻需求用到一种叫核函数(kernel)的东西将数据转化为分类器易于了解的方法。

运用核函数将数据映射到高维空间

  • 运用核函数:能够将数据从某个特征空间到另一个特征空间的映射。(一般状况下:这种映射会将低维特征空间映射到高维空间。)
  • 假如觉得特征空间很装逼、很难了解。
  • 能够把核函数幻想成一个包装器(wrapper)或许是接口(interface),它能将数据从某个很难处理的方法转化成为另一个较简略处理的方法。
  • 经过空间转化后:低维需求处理的非线性问题,就变成了高维需求处理的线性问题。
  • SVM 优化特别好的当地,在于一切的运算都能够写成内积(inner product: 是指2个向量相乘,得到单个标量 或许 数值);内积替换成核函数的办法被称为核技巧(kernel trick)或许核"变电"(kernel substation)
  • 核函数并不只是运用于支撑向量机,许多其他的机器学习算法也都用到核函数。最盛行的核函数:径向基函数(ra卞dial basis function)
  • 径向基函数的高斯版别,其详细的公式为:

项目事例: 手写数字辨认的优化(有核函数)

项目概述

你的老板要求:你写的那个手写辨认程序非常好,可是它占用内存太大。顾客无法经过无线的办法下载咱们的运用。
所以:咱们能够考虑运用支撑向量机,保存支撑向量邓州气候就行(knn需求保存一切的向量),就能够取得非常好的作用。

开发流程

搜集数据:供给的文本文件

00000湖南科技大学,机器学习实战项目-支撑向量机,you000000000001111000000000000

00000000000000011111111000000000

00000000000000011111111100000000

00000000000000011111111110000000

00000000000000011111111110000000

00000000000000111111111100000000

00000000000000111111111100000000

00000000000001111111111100000000

00000000000000111111111100000000

00000000000000111111111100000000

00000000000000111111111000000000

00000000000001111111111000000000

00000000000011111111111000000000

00000000000111111111110000000000

00000000001111111111111000000000

00000001111111111111111000000000

00000011111111111111110000000000

00000111111111111111110000000000

00000111111111111111110000000000

00000001111111111111110000000000

00000001111111011111110000000000

00000000111100011111110000000000

00000000000000011111110000000000

00000000000000011111100000000000

00000000000000111111110000000000

00000000000000011111110000000000

00000000000000011111110000000000

00000000000000011111111000000000

00000000000000011111111000000000

00000000000000011111111000000000

00000000000000000111111110000000

00000000000000000111111100000000

预备数据:根据二值图画结构向量

将 32*32的文本转化为 1*1瓦屋山024的矩阵

def img2vector(filename):
returnVect = zeros((1, 1024))
fr = open(filename)
for i in range(32):
lineStr摩托车车技360摆尾 = fr.readline()
for j in range(32):
returnVect[0, 32 * i + j] = int(lineStr[j])
return returnVect
def loadImages(dirName):
from os import listdir
hwLabels = []
print(dirName)
trainingF湖南科技大学,机器学习实战项目-支撑向量机,youileList = listdir(dirName) # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
if classNumStr == 9:
hwLabels.append(-1)
else:
hwLabels.append(1)
trainingMat[i, :] = img2vector('%s/%s' % (dirName, fileNameStr))
return trainingMat, hwLabels

剖析数据:对图画向量进行目测

练习算法:选用两种不同的湖南科技大学,机器学习实战项目-支撑向量机,you核函数,并对径向基核函数选用不同的设置来运转SMO算法

def kernelTrans(X, A, kTup): # calc the kernel or transform data to a higher dimensional space
"""
核转化函数
Args:
X dataMatIn数据集
A dataMatIn数据集的第i行的数据
kTup 核函数的信息
Returns:
"""
m, n = shape(X)
K = mat(zeros((m, 1)))
if kTup[0] == 'lin':
# linear kernel: m*n * n*1 = m*1
K = X * A.T
elif kTup[0] == 'rbf':
for j in range(m):
deltaRow = X[j, :] - A
K[j] = deltaRow * deltaRow.T
# 径向基函数的高斯版别
K = exp(K / (-1 * kTup[1] ** 2)) # divide in NumPy is element-wise not matrix like Matlab
else:
raise NameError('Houston We Have a Problem -- That Kernel is not recognized')
return K
def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)):
"""
完好SMO算法外循环,与smoSimple有些相似,但这儿的循环退出条件更多一些
Args:
dataMatIn 数据集
classLabels 类别标签
C 松懈变量(常量值),答应有些数据点能够处于分隔面的过错一侧。
操控最大化距离和确保大部分的函数距离小于1.0这两个方针的权重。
能够经过调理该参数到达不同的成果。
toler 容错率
maxIter 退出前最大的循环次数
kTup 包括核函数信息的元组
Returns:
b 模型的常量值
alphas 拉格朗日乘子
"""
# 创立一个 optStruct 方针
oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler, kTup)
iter = 0
entireSet = True
alphaPairsChanged = 0
# 循环遍历:循环maxIter次 而且 (alphaPairsChanged存在能够改动 or 一切行遍历一遍)
while (iter < maxIter) and ((alphaPairsChanged > 0) o湖南科技大学,机器学习实战项目-支撑向量机,your (entireSet)):
alphaPairsChanged = 0
# 当entireSet=true or 非鸿沟alpha对没有了;就开端寻觅 alpha对,然后决议是否要进行else。
if entireSet:
# 在数据集上遍历一切或许的alpha
for i in range(oS.m):
# 是否存在alpha对,存在就+1
alphaPairsChanged += innerL(i, oS)
# print("fullSet, iter: %d i:%d, pairs changed %d" % (iter, i, alphaPairsChanged))
iter += 1
# 对已存在 alpha对,选出非华莱士加盟费多少鸿沟的alpha值,进行优化。
else:
# 遍历一切的非鸿沟alpha值,也便是不在鸿沟0或C上的值。
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
# 假如找到alpha对,就优化非鸿沟alpha值,不然,就从头进行寻觅,假如寻觅一遍 遍历一切的行仍是没找到,就退出循环。
if entireSet:
entireSet = False # toggle entire set loop
elif (alphaPairsChanged == 0):
enti经略盛唐reSet = True
print("iteration number: %d" % iter)
return oS.b, oS.alphas

测验算法:便携一个函数来测验不同的和函数并核算过错率

def testDigits(kTup=('rbf', 10)):
# 1. 导入练习数据
dataArr, labelArr = loadImages('input/6.SVM/trainingDigits')
b, alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup)
datMat = mat(dataArr)
labelMat = mat(labelArr).transpose()
svInd = nonzero(alphas.A > 0)[0]
sVs = datMat[svInd]
labelSV = labelMat[svInd]
# print("there are %d Support Vectors" % shape(sVs)[0])
m, n = shape(datMat)
errorCount = 0
for i in range(m):
kernelEval = kernelTrans(sVs, datMat[i, :], kTup)
# 1*m * m*1 = 1*1 单个猜测成果
predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b
isoref sign(predict) != sign(labelArr[i]): errorCount += 1
print("the training error rate is: %f" % (float(errorCount) / m))
# 2. 导入测验数据
dataArr, labelArr = loadImages('input/6.SVM/testDigits')
errorCount = 0
datMat = mat(dataArr)
labelMat = mat(labelArr).transpose()
m, n = shape(datMat)
for i in range(m):
kernelEval = kernelTrans(sVs, datMat[i, :], kTup)
# 1*m * m*1 = 1*1 单个猜测成果
pred古间圆儿ict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b
if sign(predict) != sign(labelArr[i]): err直播采蘑菇遇腐尸orCount += 1
print("the test error rate is: %f" % (float(errorCount) / m))

运用算法:一个图画辨认的完好运用还需求一些图画处只需你姜宁理的常识,这儿并不计划深化介绍

完好代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/6.SVM/svm-complete.py

来历:顷刻 geekidentity / ApacheCN ,只作共享,不作任何商业用处,版权归原作者一切

admin 14文章 0评论 主页

相关文章

  用户登录