FAFU机器学习 08-1upportectorachine中文

机器学习基础支持向量机（）数据挖掘十大算法C4.5.K均值支持向量机先验的EM（最大似然）PageRank阿达博斯特KNN奈韦巴耶斯推车支持向量机Sklearn中的支持向量机2020/12/3支持向量机第7-3课背景最早的SVM算法是由VladimirN.Vapnik和AlexeyYa发明的。1963年，切尔沃年基斯最大边缘分类器1992年，BernhardE.Boser，IsabelleM.Guyon和VladimirN.Vapnik提出了一种通过将核技巧应用于最大边距超平面来创建非线性分类器的方法使用内核技巧的内核化版本目前的标准化身（软边际）是由CorinnaCortes和Vapnik于1993年提出，并于1995年出版软边距分类器软边距内核化版本（组合了1，2和3）2020/12/3支持向量机第7-4课背景1996年，Vapnik等人。提出了一种支持向量机的方法来进行回归而不是分类。支持向量回归(SVR)在机器学习中，支持向量机（SVM，也称支持向量网络）是具有相关学习算法的监督学习模型，该学习算法分析用于分类和回归分析的数据。但多用于分类问题由于支持向量机在手写体数字识别中的成功应用，支持向量机开始受到人们的青睐2020/12/3支持向量机第7-5课专业人士基于内核的框架非常强大，灵活在实践中工作得非常好，即使训练样本容量非常小解可表示为二次规划问题许多公开可用的SVM包:例如LIBSVM，LIBLINEAR，SVMLight罪名为一个问题选择最好的核函数是很棘手的计算，记忆在训练时，必须计算所有示例对的核值对于大规模的问题，学习可能需要非常长的时间2020/12/3支持向量机第7-6课支持向量机Sklearn中的支持向量机2020/12/3支持向量机第7-7课

2020/12/3支持向量机第7-8课哪一个最好？D={(X1，Y1)，(X2，Y2)，…，（Xm，Ym）}，Yi{-1，+1}，D，。2020/12/3支持向量机第7-9课哪一个最好？D={(X1，Y1)，(X2，Y2)，…，（Xm，Ym）}，Yi{-1，+1}，D，。，:徐:2020/12/3支持向量机第7-10课（w，b），（xi，yi），yi=+1，wtxi+b>0；yi=-1，wtxi+b<0。:支持向量：使上式等号成立的训练样本点。间隔：两个异类支持向量到超平面的距离之和。2023/11/4SupportVectorMachineLesson7-11间隔与支持向量欲找到具有“最大间隔”(maximummargin)的划分超平面，也就是要找到能满足约束的参数w

和b

，使得

γ最大，即：为了最大化间隔，

仅需最大化||w||-1，这等价于最小化||w||2.于是:2023/11/4SupportVectorMachineLesson7-12SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-13对偶问题MaximizethemarginItisaconvexquadraticprogramming(QP)optimizationproblem.ConvexQPproblemshaveconvexobjectivefunctions.Theseproblemscanbesolvedeasilyandefficientlybygreedyalgorithms(becauseeverylocalminimumisaglobalminimum).Butwehavemoreeffectivemethodtosolveit.2023/11/4SupportVectorMachineLesson7-14对偶问题Maximizethemargin拉格朗日乘子法,定义拉格朗日函数:令L(w，b，α)对w

和b

的偏导为零可得:2023/11/4SupportVectorMachineLesson7-15对偶问题Maximizethemargin拉格朗日乘子法,定义拉格朗日函数:将L(ω

，b，α)中的ω

和b

消去，可得对偶问题:2023/11/4SupportVectorMachineLesson7-16解出α

后，求出ω

与b

即可得到模型：2023/11/4SupportVectorMachineLesson7-17SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-18核函数在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面，比如：2023/11/4SupportVectorMachineLesson7-19将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分.核函数令Φ(x)表示将x

映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为：2023/11/4SupportVectorMachineLesson7-20核函数令Φ(x)表示将x映射后的特征向量，对偶问题：由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:2023/11/4SupportVectorMachineLesson7-21核函数由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:对偶问题可重写为：2023/11/4SupportVectorMachineLesson7-22核函数由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算Φ(xi)TΦ(xj)通常是困难的.为了避开这个障碍，可以设想这样一个函数:重写对偶问题求解对偶问题后即可得到2023/11/4SupportVectorMachineLesson7-23核函数核函数定理2023/11/4SupportVectorMachineLesson7-24核函数常用核函数2023/11/4SupportVectorMachineLesson7-25核函数常用核函数通过函数组合得到核函数若κ1和κ2为核函数，则对于任意正数ϒ1、ϒ2，其线性组合ϒ1*κ1+ϒ2*κ2也是核函数;若κ1和κ2为核函数，则核函数的直积κ1⊕κ2(x,z)=κ1(x,z)κ2(x,z)也是核函数；若κ1和κ2为核函数，则对于任意函数g(x)，κ(x,z)=g(x)κ1(x,z)g(z)也是核函数；2023/11/4SupportVectorMachineLesson7-26SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-27软间隔与正则化在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的?即存在一个超平面能将不同类的样本完全划分开.然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分;退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的.缓解该问题的一个办法是允许支持向量机在一些样本上出错.为此，要引入“软间隔”(Softmargin)的概念.2023/11/4SupportVectorMachineLesson7-28软间隔与正则化“软间隔”(Softmargin)示意图.软间隔允许某些样本不满足约束2023/11/4SupportVectorMachineLesson7-29软间隔与正则化软间隔允许某些样本不满足约束,当然，在最大化间隔的同时，不满足约束的样本应尽可能少.于是，优化目标可写为:2023/11/4SupportVectorMachineLesson7-30软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好,于是，人们通常用其他一些函数来代替l0/1，称为“替代损失”(surrogateloss).替代损失函数一般具有较好的数学性质，如它们通常是凸的连续函数且是l0/1的上界.三种常用的替代损失函数:2023/11/4SupportVectorMachineLesson7-31软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好采用hinge损失失函数:引入"松弛变量"(slackvariables)ξi>=0这就是常用的"软间隔支持向量机"2023/11/4SupportVectorMachineLesson7-32软间隔与正则化然而，l0/1非凸、非连续，数学性质不太好我们还可以把0/1损失函数换成别的替代损失函数以得到其他学习模型，这些模型的性质与所用的替代函数直接相关，但它们具有一个共性:优化目标中的第一项用来描述划分超平面的“间隔”大小，另一项

用来表述训练集上的误差，可写为更一般的形式：结构风险：用于描述模型f的某些性质经验风险：用于描述模型与训练数据的契合程度C用于对二者进行折中可以把上式看着是“正则化”(regularization)问题，Ω(f)称为正则化项，C则称为正则化常数.2023/11/4SupportVectorMachineLesson7-33SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-34支持向量回归给定训练样本集D={(x1,y1)，(x2，y2),...,(xm,ym)},yi属于实数，希望学得一个形如式下式的回归模型，使得f(x)与y尽可能接近，ω和b是待确定的模型参数.对样本(x，y)，传统回归模型通常直接基于模型输出f(x)与真实输出y之间的差别来计算损失，当且仅当f(x)与y完全相同时，损失才为零.与此不同，支持向量回归(SupportVectorRegression，简称SVR)假设我们能容忍f(x)与y之间最多有ϵ的偏差，即仅当f(x)与y之间的差别绝对值大于ϵ

时才计算损失.这相当于以f(x)为中心构建了一个宽度为2ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.2023/11/4SupportVectorMachineLesson7-35支持向量回归以f(x)为中心构建了一个宽度为2

ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.2023/11/4SupportVectorMachineLesson7-36支持向量回归以f(x)为中心构建了一个宽度为2ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.于是，SVR问题可形式化为:其中C为正则化常数，lϵ

为损失函数2023/11/4SupportVectorMachineLesson7-37SupportVectorMachine背景间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归SVMinsklearn2023/11/4SupportVectorMachineLesson7-38SVMinsklearn2023/11/4SupportVectorMachineLesson7-39svm.LinearSVC([penalty,

loss,

dual,

tol,

C,

…])LinearSupportVectorClassification.svm.LinearSVR(*[,

epsilon,

tol,

C,

loss,

…])LinearSupportVectorRegression.svm.NuSVC(*[,

nu,

kernel,

degree,

gamma,

…])Nu-SupportVectorClassification.svm.NuSVR(*[,

nu,

C,

kernel,

degree,

gamma,

…])NuSupportVectorRegression.svm.OneClassSVM(*[,

kernel,

degree,

gamma,

…])UnsupervisedOutlierDetection.svm.SVC(*[,

C,

kernel,

degree,

gamma,

…])C-SupportVectorClassification.svm.SVR(*[,

kernel,

degree,

gamma,

coef0,

…])Epsilon-SupportVectorRegression.SVMinsklearn/stable/modules/svm.html#svm-classificationSVC,

NuSVC

and

LinearSVC

areclassescapableofperformingmulti-classclassificationonadataset.SVC

and

NuSVC

aresimilarmethods,butacceptslightlydifferentsetsofparametersandhavedifferentmathematicalformulations.Ontheotherhand,LinearSVCisanotherimplementationofSupportVectorClassificationforthecaseofalinearkernel.Notethat

LinearSVC

doesnotacceptkeyword

kernel,asthisisassumedtobelinear2023/11/4SupportVectorMachineLesson7-40SVMinsklearnclass

sklearn.svm.SVC(C=1.0,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

probability=False,

tol=0.001,

cache_size=200,

class_weight=None,

verbose=False,

max_iter=-1,

decision_function_shape=’ovr’,

random_state=None)2023/11/4SupportVectorMachineLesson7-41>>>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

importSVC>>>clf=SVC(gamma='auto')>>>clf.fit(X,y)#SVC(C=1.0,cache_size=200,class_weight=None,coef0=0.0,decision_function_shape='ovr',degree=3,gamma='auto',kernel='rbf',max_iter=-1,probability=False,random_state=None,shrinking=True,tol=0.001,verbose=False)>>>print(clf.predict([[-0.8,-1]]))2023/11/4SupportVectorMachineLesson7-42SVMinsklearnclass

sklearn.svm.NuSVC(nu=0.5,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

probability=False,

tol=0.001,

cache_size=200,

class_weight=None,

verbose=False,

max_iter=-1,

decision_function_shape=’ovr’,

random_state=None)Parameternu

:

float,optional(default=0.5)Anupperboundonthefractionoftrainingerrorsandalowerboundofthefractionofsupportvectors.Shouldbeintheinterval(0,1].2023/11/4SupportVectorMachineLesson7-43SVMinsklearnclass

sklearn.svm.LinearSVC(penalty=’l2’,

loss=’squared_hinge’,

dual=True,

tol=0.0001,

C=1.0,

multi_class=’ovr’,

fit_intercept=True,

intercept_scaling=1,

class_weight=None,

verbose=0,

random_state=None,

max_iter=1000)SimilartoSVCwithparameterkernel=’linear’,butimplementedintermsofliblinearratherthanlibsvm,soithasmoreflexibilityinthechoiceofpenaltiesandlossfunctionsandshouldscalebettertolargenumbersofsamples.Thisclasssupportsbothdenseandsparseinputandthemulticlasssupportishandledaccordingtoaone-vs-the-restscheme.2023/11/4SupportVectorMachineLesson7-44SVMinsklearnclass

sklearn.svm.SVR(kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

tol=0.001,

C=1.0,

epsilon=0.1,

shrinking=True,

cache_size=200,

verbose=False,

max_iter=-1)Epsilon-SupportVectorRegressionTheimplementationisbasedonlibsvm.2023/11/4SupportVectorMachineLesson7-45SVMinsklearnclass

sklearn.svm.NuSVR(nu=0.5,

C=1.0,

kernel=’rbf’,

degree=3,

gamma=’auto_deprecated’,

coef0=0.0,

shrinking=True,

tol=0.001,

cache_size=200,

verbose=False,

max_iter=-1)NuSupportVectorRegression.SimilartoNuSVC,forregression,usesaparameternutocontrolthenumberofsupportvectors.However,unlikeNuSVC,wherenureplacesC,herenureplacestheparameterepsilonofepsilon-SVR.Theimplementationisbasedonlibsvm2023/11/4SupportVectorMachineLesson7-46SVMinsklearnclass

sklearn.svm.LinearSVR(epsilon=0.0,

tol=0.0001,

C=1.0,

loss=’epsilon_insensitive’,

fit_in