大数据十大经典算法讲解优品文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,大数据十大经典算法讲解,分类,概念：,通过构造一个,分类函数,或,分类器,的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。,数据：,线性可分,线性不可分,什么是,SVM,全名：,Support Vector Machine,（支持向量机）,支持向量,：,支持或支撑平面,上把两类类别划分开来的超平面的,向量点,。,机,：一个算法,基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。,SVM,的特点,SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广能力（或泛化能力）。,核函数,松弛变量,线性分类,1,线性分类,1,线性分类,问题,1.如何求得最优的g(x)？,2.最优的标准是什么？,3.g(x)=wx+b中的w和b如何确定？,最优标准：分类间隔,数据表示Di=(xi,yi),分类间隔即两分类之间的距离越远越不易混淆,定义i=(1/|w|)|g(xi)|，称为几何间隔,|w|叫做向量w的范数,WX的p范数为|w|p=(X1p+X2p+.+Xnp）(1/p),最优标准：分类间隔,H2与H之间的间隔便是几何间隔。其中H1：+b=1；H2：+b=-1；,几何间隔与样本的误分次数间的关系：误分次数=(2R/)2，其中是样本集合到分类面的间隔，R=max|xi|,i=1,.,n;,所以问题转化成为求最大值。,因为w是超平面的法向量，所以w实际上只由在H1平面上的样本点确定；,在H1上的向量则叫做Supported Vectors，因为它们“撑”起了分界线。,求最大的,于是问题便转化成了求,很容易看出当|w|=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带,解决方法：加一个约束条件,求最大的,H2：+b=-1；,令：Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2,核函数应用广泛的原因：,几何间隔与样本的误分次数间的关系：误分次数,二次凸优化问题,=,对偶问题,对偶问题求解：,更巧妙的地方：,未知数据,x,的预测，只需要计算它与训练数据点的内积即可,非线性分类,对于以上所述的,SVM,，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。,非线性分类,找不到一个超平面（二维空间：直线）将其分割开来，而很自然的想到可以用一个椭圆将数据分为两类,Z,1,=X,1,Z,2,=X,1,2,Z,3,=X,2,Z,4,=X,2,2,Z,5,=X,1,X,2,(X,1,X,2,),(Z,1,Z,2,Z,3,Z,4,Z,5,),即将：,R,2,空间映射到,R,5,空间。,此时，总能找到一个超平面,w,T,Z+b=0,w,T,=a,1,，,a,2,，,a,3,，,a,4,，,a,5,T,，,b=a,6,使得数据很好的分类。,映射过后的空间,:,非线性分类,令：,Z,1,=X,1,Z,2,=X,1,2,Z,3,=X,2,Z,4,=X,2,2,Z,5,=X,1,X,2,(X,1,X,2,),(Z,1,Z,2,Z,3,Z,4,Z,5,),则：对于样本,x,1,=(,1,2,),x,2,=(,1,2,),(x,1,)=,1,1,2,2,2,2,1,2,T,(x,2,)=,1,1,2,2,2,2,1,2,T,内积,:,我们注意到：,非线性分类,我们注意到：,若令,(x,1,)=,2,1,1,2,2,2,2,2,2,1,2,1,T,则：,那么区别在于什么地方呢？,1.,一个是将低维空间数据映射到高维空间中，然后再根据内积的公式进行计算；,另一个则直接在原来的,低维空间中进行计算,，而,不需要显式,地写出映射后的结果。,当样本空间处于高维度时，第一种方法将引发,维度灾难,，第二种方法仍然能够从容处理,核函数,核函数：,概念：,x,zX,X,属于,R,n,空间,非线性函数,实现输入空间,X,到特征空间,F,的映射,其中,F,属于,R,m,，,n(Z1,Z2,Z3,Z4,Z5,),所以问题转化成为求最大值。,代入 L(w,b,a):,H2与H之间的间隔便是几何间隔。,加入核函数以后的分类函数为：,|w|叫做向量w的范数,WX的p范数为|w|p=(X1p+X2p+.,|w|叫做向量w的范数,WX的p范数为|w|p=(X1p+X2p+.,即将：R2空间映射到R5空间。,Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2,基于统计学习理论的一种机器学习方法。,令：Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2,常用的核函数,多项式核：,线性核：,高斯核：,总结,线性可分：,求解使得超平面具有最大内间间隔的,w,T,，,b,参数。,将问题转化为对偶问题进行快速求解。,改进：加入松弛变量 和惩罚因子,C,的,SVM,松弛变量允许实际分类中一定的不准确性的存在，引入松弛变量后原先的约束条件变为：,惩罚因子C则是为了避免系统轻易放弃一些重要的数据，减小系统损失。引入C后目标函数变为：,感谢观看,