资源描述：
《大数据十大经典算法SVM讲解PPT》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据挖掘十大算法之SVM程广兵2014.12.22分类概念：通过构造一个分类函数或分类器的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。数据：线性可分线性不可分什么是SVM全名：SupportVectorMachine（支持向量机）支持向量：支持或支撑平面上把两类类别划分开来的超平面的向量点。机：一个算法基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。SVM的特点SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻
2、求最佳折衷，以期获得最好的推广能力（或泛化能力）。核函数松弛变量线性分类1线性分类1线性分类最优标准：分类间隔对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点（xi,yi）的函数间隔为对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点（xi,yi）的几何间隔为
3、
4、w
5、
6、叫做向量w的范数,WX的p范数为
7、
8、w
9、
10、p=(X1^p+X2^p+...+Xn^p）^(1/p)函数间隔和几何间隔的关系ɤ=ȓ/
11、
12、w
13、
14、（1）最优标准：分类间隔H2与H之间的间隔便是几何间隔。其中H1：wx+b=1；H2：wx+b=-1；定义超平
15、面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点（xi,yi）的函数间隔之最小值，即同理最终问题转化成为求最大ɤ值。（ps:我的理解在找到几何间隔ɤ后，就要使H1和H2尽可能的离H远，这样分类就更有说服力）在H1和H2上的点就叫做支持向量H1和H2之间的距离称为间隔，间隔依赖于法向量w,等于2/
16、
17、w
18、
19、,H1和H2称为间隔边界由等式（1），可将问题写为求最大的ɤ由于函数间隔ȓ不影响最优化问题的解，这样可以取ȓ=1，由于最大化1/
20、
21、w
22、
23、和最小化1/2*
24、
25、w
26、
27、*
28、
29、w
30、
31、问题是等价的于是问题便转化成了求很容易看出当
32、
33、w
34、
35、=0
36、的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带解决方法：加一个约束条件求最大的ɤ我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，于是不难得到有不等式：yi[+b]≥1(i=1,2,…,l)总成立。于是上面的问题便转化成了求条件最优化问题：约束条件这是一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。（2）（3）最优问题的求解为了求解线性可分支
37、持向量机的最优化问题（2）~（3），将它作为原始最优化问题，应用拉格朗日对偶性（参考李航的统计学习方法附录C），通过求解对偶问题得到原始问题的最优解，这是线性可分支持向量机的对偶算法。最优问题的求解引入拉格朗日乘子（ps:之所以，>=0是因为如果不做限定，因为要求极大值，而，那么可以取负无穷，这样目标值就会无穷大，其实当点是支持向量时>0,其他的点=0）利用Lagrange乘子法：当点是支持向量时y(wx+b)=1当点不是支持向量时y(wx+b)>1这样Lagrange函数的第二项始终为零凸二次规划问题求解代入L(w,b,a):问题转换为凸二次规划问题求解凸二
38、次规划问题求解更多细节请参照李航的统计学习方法SVM这一章凸二次规划问题求解为了例题例题线性分类目标函数：约束条件：目标函数：约束条件：拉格朗日乘数法可将问题转化为对偶问题：目标函数：约束条件：线性分类巧妙之处：原问题=>二次凸优化问题=>对偶问题对偶问题求解：更巧妙的地方：未知数据x的预测，只需要计算它与训练数据点的内积即可非线性分类对于以上所述的SVM，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。非线性分类找不到一个超平面（二维空间：直线）将其分割
39、开来，而很自然的想到可以用一个椭圆将数据分为两类Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2(X1,X2)——>(Z1,Z2,Z3,Z4,Z5,)即将：R2空间映射到R5空间。此时，总能找到一个超平面wTZ+b=0wT={a1，a2，a3，a4，a5}T，b=a6使得数据很好的分类。映射过后的空间:非线性分类令：Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2(X1,X2)—Φ—>(Z1,Z2,Z3,Z4,Z5,)则：对于样本x1=(η1,η2),x2=(ξ1,ξ2)Φ(x1)=[η1,η12,η2,η22,η1η2]T
40、Φ(x2)=[ξ1,ξ12,ξ2,ξ2
