2019-12-25 16:11:48 qq_42003997 阅读数 87
  • 人工智能之机器学习算法的介绍

    机器学习算法入门教程,主要介绍人工智障机器学习常见算法,包括决策树、基于概率论的分类方法:朴素贝叶斯、Logistic回归、支持向量机、第利用AdaBoost元算法提高分类性能。

    4286 人正在学习 去看看 CSDN讲师

一个数据集、单个算法

一次留出法----二项检验

  m个样本的测试集上,泛化错误率为ϵ\epsilon的学习器被测得测试错误率为ϵ^\hat{\epsilon}的概率是:
P(ϵ^;ϵ)=(mc^×m)ϵe^×m(1ϵ)me^×m P(\hat{\epsilon} ; \epsilon)=\left(\begin{array}{c} {m} \\ {\hat{c} \times m} \end{array}\right) \epsilon^{\hat{e} \times m}(1-\epsilon)^{m-\hat{e} \times m}
  服从二项分布,可使用“二项检验”进行检验。

多次重复留出法或交叉验证法----t检验

  多次重复留出法或者交叉验证法进行训练/测试,会得到多个测试错误率,此时可使用“t检验”。假定获得了k个测试错误率,ϵ1^ϵ2^ϵ3^ϵ^k\hat{\epsilon1}、\hat{\epsilon2}、\hat{\epsilon3}…\hat{\epsilon}k,则平均测试错误率为Xˉ\bar{X}S2S^{2}
Xˉ=1ki=1kε^i,S2=1k1i=1k(ε^iXˉ)2 \bar{X}=\frac{1}{k} \sum_{i=1}^{k} \hat{\varepsilon}_{i} \quad, \quad S^{2}=\frac{1}{k-1} \sum_{i=1}^{k}\left(\hat{\varepsilon}_{i}-\bar{X}\right)^{2}
  根据中心极限定理可知,
(Xˉε)S/nt(n1) \frac{(\bar{X}-\varepsilon)}{S / \sqrt{n}} \sim t(\mathrm{n}-1)
  t分布示意图及常用双边临界值表如下所示:
在这里插入图片描述

一个数据集、两个算法----交叉验证t检验

  对于一个数据集,两个算法A和B,使用k折交叉验证法得到的测试错误率分别为ε^iAε^iB(i=1,2,,,k)\hat{\varepsilon}_{iA} 、 \hat{\varepsilon}_{iB}(i=1,2,,,k)。可采用k折交叉验证“成对t检验”来进行检验。
  基本思想是若两个算法的性能相同,则他们使用相同的训练集/测试集得到的测试错误率应相同,即ε^iA=ε^iB\hat{\varepsilon}_{iA} = \hat{\varepsilon}_{iB}
对每一组测试错误率求差值,Δi=ε^Aε^B\Delta_{i}=\hat{\varepsilon}_{A}-\hat{\varepsilon}_{B},若两个算法性能相同,则差值均值为零。可根据Δ1Δ2...Δk\Delta_{1、}\Delta_{2、}... \Delta_{k、}进行t检验,计算出差值的均值Δ|\vec{\Delta}|和方差S2S^2,则:
(Δˉ(εAεB)S/kt(k1) \frac{\left|\left(\bar{\Delta}-\left(\varepsilon_{A}-\varepsilon_{B}\right)\right\rangle\right|}{S / \sqrt{\mathrm{k}}} \sim t(\mathrm{k}-1)
  若假设H0:εA=εB,H1:εAεBH_{0}: \varepsilon_{A}=\varepsilon_{B}, H_{1}: \varepsilon_{A} \neq \varepsilon_{B},则,满足ΔˉS/kt/2\frac{|\bar{\Delta}|}{S / \sqrt{\mathrm{k}}} \leq \mathrm{t}_{\partial / 2}
  由于样本有限,在使用交叉验证等方法的时候,会导致不同轮次的训练集有一定程度的重叠,是的测试错误率不独立,导致过高估计假设成立的概率,为缓解这一问题,可采用“5次2折交叉验证”。

一组数据集、多个算法----Friedman检验与Nemenyi检验

Friedman检验

  假设有数据集D1、D2、D3、D4,算法A、B、C进行比较。
  使用留出法或者交叉验证得到每个算法在每个数据集上的测试结果,然后在每个数据集上根据测试性能由好到坏排序,并赋予序值1,2,…,若算法测试性能相同,则平分序值。
在这里插入图片描述
  使用Friedman检验来判断浙西额算法是否性能相同,若相同,则它们的平均序值应当相同。
  若在N个数据集,比较k个算法,令ri{r_i}表示第i个算法的平均序值,则ri{r_i}的均值和方差分别为(k+1)/2,(k+1)(k1)/12(k+1) / 2, \quad(k+1) \quad(k-1) / 12,则有:
τχ2=k1k12Nk21i=1k(rik+12)2=12Nk(k+1)(i=1kri2k(k+1)24) \begin{aligned} \tau_{\chi^{2}} &=\frac{k-1}{k} \cdot \frac{12 N}{k^{2}-1} \sum_{i=1}^{k}\left(r_{i}-\frac{k+1}{2}\right)^{2} \\ &=\frac{12 N}{k(k+1)}\left(\sum_{i=1}^{k} r_{i}^{2}-\frac{k(k+1)^{2}}{4}\right) \end{aligned}
  在k和N比较大时,服从自由度为k-1的χ2\chi^{2}分布。
τF=(N1)τχ2N(k1)τχ2 \tau_{F}=\frac{(N-1) \tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}
  服从自由度为k-1和(k-1)(N-1)的F分布。下面是F检验常用的临界值:
F检验常用临界值

Nemenyi检验

  若原假设被拒绝,则需要进行后续检验,来得到具体的算法之间的差异。常用的是Nemenyi检验。Nemenyi检验计算出平均序值差别的临界值域,下表是常用的qa值,若两个算法的平均序值差超出了临界值域CD,则相应的置信度1α1-\alpha拒绝“两个算法性能本相同”的假设。
CD=qαk(k+1)6N C D=q_{\alpha} \sqrt{\frac{k(k+1)}{6 N}}
  qa中常用的联临界值:
在这里插入图片描述

链接

https://blog.csdn.net/qqMiSa/article/details/98660515

2016-12-13 21:57:37 mearsedy 阅读数 287
  • 人工智能之机器学习算法的介绍

    机器学习算法入门教程,主要介绍人工智障机器学习常见算法,包括决策树、基于概率论的分类方法:朴素贝叶斯、Logistic回归、支持向量机、第利用AdaBoost元算法提高分类性能。

    4286 人正在学习 去看看 CSDN讲师


版权声明:

    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com。也可以加我的微博: @leftnoteasy

 

前言:

    又有很长的一段时间没有更新博客了,距离上次更新已经有两个月的时间了。其中一个很大的原因是,不知道写什么好-_-,最近一段时间看了看关于SVM(Support Vector Machine)的文章,觉得SVM是一个非常有趣,而且自成一派的方向,所以今天准备写一篇关于关于SVM的文章。

    关于SVM的论文、书籍都非常的多,引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”。SVM对于大部分的普通人来说,要完全理解其中的数学是非常困难的,所以要让这些普通人理解,得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些数学,对学习其他的内容也是大有裨益的。我就是属于绝大多数的普通人,为了看明白SVM,看了不少的资料,这里把我的心得分享分享。

    其实现在能够找到的,关于SVM的中文资料已经不少了,不过个人觉得,每个人的理解都不太一样,所以还是决定写一写,一些雷同的地方肯定是不可避免的,不过还是希望能够写出一点与别人不一样的地方吧。另外本文准备不谈太多的数学(因为很多文章都谈过了),尽量简单地给出结论,就像题目一样-机器学习中的算法(之前叫做机器学习中的数学),所以本系列的内容将更偏重应用一些。如果想看更详细的数学解释,可以看看参考文献中的资料。

 

一、线性分类器:

    首先给出一个非常非常简单的分类问题(线性可分),我们要用一条直线,将下图中黑色的点和白色的点分开,很显然,图上的这条直线就是我们要求的直线之一(可以有无数条这样的直线)

image    假如说,我们令黑色的点 = -1, 白色的点 =  +1,直线f(x) = w.x + b,这儿的x、w是向量,其实写成这种形式也是等价的f(x) = w1x1 + w2x2 … + wnxn + b, 当向量x的维度=2的时候,f(x) 表示二维空间中的一条直线, 当x的维度=3的时候,f(x) 表示3维空间中的一个平面,当x的维度=n > 3的时候,表示n维空间中的n-1维超平面。这些都是比较基础的内容,如果不太清楚,可能需要复习一下微积分、线性代数的内容。

    刚刚说了,我们令黑色白色两类的点分别为+1, -1,所以当有一个新的点x需要预测属于哪个分类的时候,我们用sgn(f(x)),就可以预测了,sgn表示符号函数,当f(x) > 0的时候,sgn(f(x)) = +1, 当f(x) < 0的时候sgn(f(x)) = –1。

    但是,我们怎样才能取得一个最优的划分直线f(x)呢?下图的直线表示几条可能的f(x)

image

    一个很直观的感受是,让这条直线到给定样本中最近的点最远,这句话读起来比较拗口,下面给出几个图,来说明一下:

    第一种分法:

image

    第二种分法:

image

    这两种分法哪种更好呢?从直观上来说,就是分割的间隙越大越好,把两个类别的点分得越开越好。就像我们平时判断一个人是男还是女,就是很难出现分错的情况,这就是男、女两个类别之间的间隙非常的大导致的,让我们可以更准确的进行分类。在SVM中,称为Maximum Marginal,是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是由很多道理的,比如说从概率的角度上来说,就是使得置信度最小的点置信度最大(听起来很拗口),从实践的角度来说,这样的效果非常好,等等。这里就不展开讲,作为一个结论就ok了,:)

    上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。

  image    上图就是一个对之前说的类别中的间隙的一个描述。Classifier Boundary就是f(x),红色和蓝色的线(plus plane与minus plane)就是support vector所在的面,红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。image

    这里直接给出M的式子:(从高中的解析几何就可以很容易的得到了,也可以参考后面Moore的ppt)

image

    另外支持向量位于wx + b = 1与wx + b = -1的直线上,我们在前面乘上一个该点所属的类别y(还记得吗?y不是+1就是-1),就可以得到支持向量的表达式为:y(wx + b) = 1,这样就可以更简单的将支持向量表示出来了。

    当支持向量确定下来的时候,分割函数就确定下来了,两个问题是等价的。得到支持向量,还有一个作用是,让支持向量后方那些点就不用参与计算了。这点在后面将会更详细的讲讲。

    在这个小节的最后,给出我们要优化求解的表达式:

image

    ||w||的意思是w的二范数,跟上面的M表达式的分母是一个意思,之前得到,M = 2 / ||w||,最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数,我们可以对其加入平方,和前面的系数,熟悉的同学应该很容易就看出来了,这个式子是为了方便求导。

    这个式子有还有一些限制条件,完整的写下来,应该是这样的:(原问题

image

    s.t的意思是subject to,也就是在后面这个限制条件下的意思,这个词在svm的论文里面非常容易见到。这个其实是一个带约束的二次规划(quadratic programming, QP)问题,是一个凸问题,凸问题就是指的不会有局部最优解,可以想象一个漏斗,不管我们开始的时候将一个小球放在漏斗的什么位置,这个小球最终一定可以掉出漏斗,也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体,我们要做的就是在这个凸多面体中找到最优解。这些问题这里不展开,因为展开的话,一本书也写不完。如果有疑问请看看wikipedia。

 

二、转化为对偶问题,并优化求解:

    这个优化问题可以用拉格朗日乘子法去解,使用了KKT条件的理论,这里直接作出这个式子的拉格朗日目标函数:

image

    求解这个式子的过程需要拉格朗日对偶性的相关知识(另外pluskid也有一篇文章专门讲这个问题),并且有一定的公式推导,如果不感兴趣,可以直接跳到后面蓝色公式表示的结论,该部分推导主要参考自plukids的文章

    首先让L关于w,b最小化,分别令L关于w,b的偏导数为0,得到关于原问题的一个表达式

image

    将两式带回L(w,b,a)得到对偶问题的表达式

image

    新问题加上其限制条件是(对偶问题):

image

    这个就是我们需要最终优化的式子。至此,得到了线性可分问题的优化式子

    求解这个式子,有很多的方法,比如SMO等等,个人认为,求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情,所以在这篇文章中准备完全不涉及如何求解这个话题,如果之后有时间可以补上一篇文章来谈谈:)。

 

三、线性不可分的情况(软间隔):

    接下来谈谈线性不可分的情况,因为线性可分这种假设实在是太有局限性了:

    下图就是一个典型的线性不可分的分类图,我们没有办法用一条直线去将其分成两个区域,每个区域只包含一种颜色的点。

image     要想在这种情况下的分类器,有两种方式,一种是用曲线去将其完全分开,曲线就是一种非线性的情况,跟之后将谈到的核函数有一定的关系:

image     另外一种还是用直线,不过不用去保证可分性,就是包容那些分错的情况,不过我们得加入惩罚函数,使得点分错的情况越合理越好。其实在很多时候,不是在训练的时候分类函数越完美越好,因为训练函数中有些数据本来就是噪声,可能就是在人工加上分类标签的时候加错了,如果我们在训练(学习)的时候把这些错误的点学习到了,那么模型在下次碰到这些错误情况的时候就难免出错了(假如老师给你讲课的时候,某个知识点讲错了,你还信以为真了,那么在考试的时候就难免出错)。这种学习的时候学到了“噪声”的过程就是一个过拟合(over-fitting),这在机器学习中是一个大忌,我们宁愿少学一些内容,也坚决杜绝多学一些错误的知识。还是回到主题,用直线怎么去分割线性不可分的点:

     我们可以为分错的点加上一点惩罚,对一个分错的点的惩罚函数就是这个点到其正确位置的距离:

image

 

    在上图中,蓝色红色的直线分别为支持向量所在的边界,绿色的线为决策函数,那些紫色的线表示分错的点到其相应的决策面的距离,这样我们可以在原函数上面加上一个惩罚函数,并且带上其限制条件为:

image

    公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分,当xi在正确一边的时候,ε=0,R为全部的点的数目,C是一个由用户去指定的系数,表示对分错的点加入多少的惩罚,当C很大的时候,分错的点就会更少,但是过拟合的情况可能会比较严重,当C很小的时候,分错的点可能会很多,不过可能由此得到的模型也会不太正确,所以如何选择C是有很多学问的,不过在大部分情况下就是通过经验尝试得到的。

    接下来就是同样的,求解一个拉格朗日对偶问题,得到一个原问题的对偶问题的表达式:

image

    蓝色的部分是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题,不同的地方就是α的范围从[0, +∞),变为了[0, C],增加的惩罚ε没有为对偶问题增加什么复杂度。

 

四、核函数:

    刚刚在谈不可分的情况下,提了一句,如果使用某些非线性的方法,可以得到将两个分类完美划分的曲线,比如接下来将要说的核函数。

    我们可以让空间从原本的线性空间变成一个更高维的空间在这个高维的线性空间下,再用一个超平面进行划分。这儿举个例子,来理解一下如何利用空间的维度变得更高来帮助我们分类的(例子以及图片来自pluskid的kernel函数部分):

    下图是一个典型的线性不可分的情况

image

    但是当我们把这两个类似于椭圆形的点映射到一个高维空间后,映射函数为:

image    用这个函数可以将上图的平面中的点映射到一个三维空间(z1,z2,z3),并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

rotate

 

 

 

 

    用另外一个哲学例子来说:世界上本来没有两个完全一样的物体,对于所有的两个物体,我们可以通过增加维度来让他们最终有所区别,比如说两本书,从(颜色,内容)两个维度来说,可能是一样的,我们可以加上 作者 这个维度,是在不行我们还可以加入页码,可以加入 拥有者,可以加入 购买地点,可以加入 笔记内容等等。当维度增加到无限维的时候,一定可以让任意的两个物体可分了

    回忆刚刚得到的对偶问题表达式:

image

    我们可以将红色这个部分进行改造,令:

image     这个式子所做的事情就是将线性的空间映射到高维的空间,k(x, xj)有很多种,下面是比较典型的两种:

image    上面这个核称为多项式核,下面这个核称为高斯核,高斯核甚至是将原始空间映射为无穷维空间,另外核函数有一些比较好的性质,比如说不会比线性条件下增加多少额外的计算量,等等,这里也不再深入。一般对于一个问题,不同的核函数可能会带来不同的结果,一般是需要尝试来得到的。

 

五、一些其他的问题:

     1)如何进行多分类问题:

     上面所谈到的分类都是2分类的情况,当N分类的情况下,主要有两种方式,一种是1 vs (N – 1)一种是1 vs 1,前一种方法我们需要训练N个分类器,第i个分类器是看看是属于分类i还是属于分类i的补集(出去i的N-1个分类)。

     后一种方式我们需要训练N * (N – 1) / 2个分类器,分类器(i,j)能够判断某个点是属于i还是属于j。

     这种处理方式不仅在SVM中会用到,在很多其他的分类中也是被广泛用到,从林教授(libsvm的作者)的结论来看,1 vs 1的方式要优于1 vs (N – 1)。

     2)SVM会overfitting吗?

     SVM避免overfitting,一种是调整之前说的惩罚函数中的C,另一种其实从式子上来看,min ||w||^2这个看起来是不是很眼熟?在最小二乘法回归的时候,我们看到过这个式子,这个式子可以让函数更平滑,所以SVM是一种不太容易over-fitting的方法。

 

参考文档:

    主要的参考文档来自4个地方,wikipedia(在文章中已经给出了超链接了),pluskid关于SVM的博文Andrew moore的ppt(文章中不少图片都是引用或者改自Andrew Moore的ppt,以及prml

    

2016-12-09 20:41:45 smilehehe110 阅读数 355
  • 人工智能之机器学习算法的介绍

    机器学习算法入门教程,主要介绍人工智障机器学习常见算法,包括决策树、基于概率论的分类方法:朴素贝叶斯、Logistic回归、支持向量机、第利用AdaBoost元算法提高分类性能。

    4286 人正在学习 去看看 CSDN讲师

    机器学习中的算法(1)-决策树模型组合之随机森林与GBDT

版权声明:

    本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com。也可以加我的微博: @leftnoteasy   (原文作者信息)

 

前言:

    决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示(容易将得到的决策树做成图片展示出来)等。但是同时,单决策树又有一些不好的地方,比如说容易over-fitting,虽然有一些方法,如剪枝可以减少这种情况,但是还是不够的。

    模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大大的减少单决策树带来的毛病,有点类似于三个臭皮匠等于一个诸葛亮的做法,虽然这几百棵决策树中的每一棵都很简单(相对于C4.5这种单决策树来说),但是他们组合起来确是很强大。

    在最近几年的paper上,如iccv这种重量级的会议,iccv 09年的里面有不少的文章都是与Boosting与随机森林相关的。模型组合+决策树相关的算法有两种比较基本的形式 - 随机森林与GBDT((Gradient Boost Decision Tree),其他的比较新的模型组合+决策树的算法都是来自这两种算法的延伸。本文主要侧重于GBDT,对于随机森林只是大概提提,因为它相对比较简单。

    在看本文之前,建议先看看机器学习与数学(3)与其中引用的论文,本文中的GBDT主要基于此,而随机森林相对比较独立。

 

基础内容:

    这里只是准备简单谈谈基础的内容,主要参考一下别人的文章,对于随机森林与GBDT,有两个地方比较重要,首先是information gain,其次是决策树。这里特别推荐Andrew Moore大牛的Decision Trees Tutorial,与Information Gain Tutorial。Moore的Data Mining Tutorial系列非常赞,看懂了上面说的两个内容之后的文章才能继续读下去。

Decision Trees Tutorial (决策树教程)下载地址:http://download.csdn.net/detail/smilehehe110/9707032

Information Gain Tutorial (信息增益教程)下载地址:http://download.csdn.net/detail/smilehehe110/9707034

    决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,比如说下面的决策树:

image

    就是将空间划分成下面的样子:

image

    这样使得每一个叶子节点都是在空间中的一个不相交的区域,在进行决策的时候,会根据输入样本每一维feature的值,一步一步往下,最后使得样本落入N个区域中的一个(假设有N个叶子节点)

 

 

随机森林(Random Forest):

    随机森林是一个最近比较火的算法,它有很多的优点:

  •     在数据集上表现良好
  •     在当前的很多数据集上,相对其他算法有着很大的优势
  •     它能够处理很高维度(feature很多)的数据,并且不用做特征选择
  •     在训练完后,它能够给出哪些feature比较重要
  •     在创建随机森林的时候,对generlization error使用的是无偏估计
  •     训练速度快
  •     在训练过程中,能够检测到feature间的互相影响
  •     容易做成并行化方法
  •     实现比较简单

    随机森林顾名思义,是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本为那一类。

    在建立每一棵决策树的过程中,有两点需要注意 - 采样与完全分裂。首先是两个随机采样的过程,random forest对输入的数据要进行行、列的采样。对于行采样,采用有放回的方式,也就是在采样得到的样本集合中,可能有重复的样本。假设输入样本为N个,那么采样的样本也为N个。这样使得在训练的时候,每一棵树的输入样本都不是全部的样本,使得相对不容易出现over-fitting。然后进行列采样,从M个feature中,选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树,这样决策树的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝,但是这里不这样干,由于之前的两个随机采样的过程保证了随机性,所以就算不剪枝,也不会出现over-fitting。

    按这种算法得到的随机森林中的每一棵都是很弱的,但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法:每一棵决策树就是一个精通于某一个窄领域的专家(因为我们从M个feature中选择m让每一棵决策树进行学习),这样在随机森林中就有了很多个精通不同领域的专家,对一个新的问题(新的输入数据),可以用不同的角度去看待它,最终由各个专家,投票得到结果。

    随机森林的过程请参考Mahout的random forest 。这个页面上写的比较清楚了,其中可能不明白的就是Information Gain,可以看看之前推荐过的Moore的页面。

 

 

Gradient Boost Decision Tree:

   GBDT是一个应用很广泛的算法,可以用来做分类、回归。在很多的数据上都有不错的效果。GBDT这个算法还有一些其他的名字,比如说MART(Multiple Additive Regression Tree),GBRT(Gradient Boost Regression Tree),Tree Net等,其实它们都是一个东西(参考自wikipedia – Gradient Boosting),发明者是Friedman

   Gradient Boost其实是一个框架,里面可以套入很多不同的算法,可以参考一下机器学习与数学(3)中的讲解。Boost是"提升"的意思,一般Boosting算法都是一个迭代的过程,每一次新的训练都是为了改进上一次的结果。

   原始的Boost算法是在算法开始的时候,为每一个样本赋上一个权重值,初始的时候,大家都是一样重要的。在每一步训练中得到的模型,会使得数据点的估计有对有错,我们就在每一步结束后,增加分错的点的权重,减少分对的点的权重,这样使得某些点如果老是被分错,那么就会被“严重关注”,也就被赋上一个很高的权重。然后等进行了N次迭代(由用户指定),将会得到N个简单的分类器(basic learner),然后我们将它们组合起来(比如说可以对它们进行加权、或者让它们进行投票等),得到一个最终的模型。

   而Gradient Boost与传统的Boost的区别是,每一次的计算是为了减少上一次的残差(residual),而为了消除残差,我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说,在Gradient Boost中,每个新的模型的简历是为了使得之前模型的残差往梯度方向减少,与传统Boost对正确、错误的样本进行加权有着很大的区别。

   在分类问题中,有一个很重要的内容叫做Multi-Class Logistic,也就是多分类的Logistic问题,它适用于那些类别数>2的问题,并且在分类结果中,样本x不是一定只属于某一个类可以得到样本x分别属于多个类的概率(也可以说样本x的估计y符合某一个几何分布),这实际上是属于Generalized Linear Model中讨论的内容,这里就先不谈了,以后有机会再用一个专门的章节去做吧。这里就用一个结论:如果一个分类问题符合几何分布,那么就可以用Logistic变换来进行之后的运算

   假设对于一个样本x,它可能属于K个分类,其估计值分别为F1(x)…FK(x),Logistic变换如下,logistic变换是一个平滑且将数据规范化(使得向量的长度为1)的过程,结果为属于类别k的概率pk(x),

image

   对于Logistic变换后的结果,损失函数为:

image    其中,yk为输入的样本数据的估计值,当一个样本x属于类别k时,yk = 1,否则yk = 0。

    将Logistic变换的式子带入损失函数,并且对其求导,可以得到损失函数的梯度

image    上面说的比较抽象,下面举个例子:

    假设输入数据x可能属于5个分类(分别为1,2,3,4,5),训练数据中,x属于类别3,则y = (0, 0, 1, 0, 0),假设模型估计得到的F(x) = (0, 0.3, 0.6, 0, 0),则经过Logistic变换后的数据p(x) = (0.16,0.21,0.29,0.16,0.16),y - p得到梯度g:(-0.16, -0.21, 0.71, -0.16, -0.16)。观察这里可以得到一个比较有意思的结论:

    假设gk为样本当某一维(某一个分类)上的梯度:

    gk>0时,越大表示其在这一维上的概率p(x)越应该提高,比如说上面的第三维的概率为0.29,就应该提高,属于应该往“正确的方向”前进

                  越小表示这个估计越“准确”

    gk<0时,越小,负得越多表示在这一维上的概率应该降低,比如说第二维0.21就应该得到降低。属于应该朝着“错误的反方向”前进

                  越大,负得越少表示这个估计越“不错误 ”

    总的来说,对于一个样本,最理想的梯度是越接近0的梯度。所以,我们要能够让函数的估计值能够使得梯度往反方向移动(>0的维度上,往负方向移动,<0的维度上,往正方向移动)最终使得梯度尽量=0),并且该算法在会严重关注那些梯度比较大的样本,跟Boost的意思类似

 

 

    得到梯度之后,就是如何让梯度减少了。这里是用的一个迭代+决策树的方法,当初始化的时候,随便给出一个估计函数F(x)(可以让F(x)是一个随机的值,也可以让F(x)=0),然后之后每迭代一步就根据当前每一个样本的梯度的情况,建立一棵决策树。就让函数往梯度的反方向前进,最终使得迭代N步后,梯度越小。

    这里建立的决策树和普通的决策树不太一样,首先,这个决策树是一个叶子节点数J固定的,当生成了J个节点后,就不再生成新的节点了。

    算法的流程如下:(参考自treeBoost论文)

image

     0. 表示给定一个初始值

     1. 表示建立M棵决策树(迭代M次)

     2. 表示对函数估计值F(x)进行Logistic变换

     3. 表示对于K个分类进行下面的操作(其实这个for循环也可以理解为向量的操作,每一个样本点xi都对应了K种可能的分类yi,所以yi, F(xi), p(xi)都是一个K维的向量,这样或许容易理解一点)

     4. 表示求得残差减少的梯度方向

     5. 表示根据每一个样本点x,与其残差减少的梯度方向,得到一棵由J个叶子节点组成的决策树

     6. 为当决策树建立完成后,通过这个公式,可以得到每一个叶子节点的增益(这个增益在预测的时候用的)

       每个增益的组成其实也是一个K维的向量,表示如果在决策树预测的过程中,如果某一个样本点掉入了这个叶子节点,则其对应的K个分类的值是多少。比如说,GBDT得到了三棵决策树,一个样本点在预测的时候,也会掉入3个叶子节点上,其增益分别为(假设为3分类的问题):

       (0.5, 0.8, 0.1),  (0.2, 0.6, 0.3),  (0.4, 0.3, 0.3),那么这样最终得到的分类为第二个,因为选择分类2的决策树是最多的。

     7. 的意思为,将当前得到的决策树与之前的那些决策树合并起来,作为新的一个模型(跟6中所举的例子差不多)

     GBDT的算法大概就讲到这里了,希望能够弥补一下上一篇文章中没有说清楚的部分:)

 

 实现:

     看明白了算法,就需要去实现一下,或者看看别人实现的代码,这里推荐一下wikipedia中的gradient boosting页面,下面就有一些开源软件中的一些实现,比如说下面这个:http://elf-project.sourceforge.net/ 


原文地址:http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/random-forest-and-gbdt.html

 

2019-06-01 23:54:40 MySundays 阅读数 588
  • 人工智能之机器学习算法的介绍

    机器学习算法入门教程,主要介绍人工智障机器学习常见算法,包括决策树、基于概率论的分类方法:朴素贝叶斯、Logistic回归、支持向量机、第利用AdaBoost元算法提高分类性能。

    4286 人正在学习 去看看 CSDN讲师

目录

1. 机器学习的概述

2. 机器学习系统的特点 

3.机器学习常见分类

4.机器学习常用算法

 

1. 机器学习概述

      机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域,它主要使用归纳、综合而不是演绎。

 

2. 机器学习系统的特点

  • 解决无法直接使用 固定的规则+流程代码
  • 学习能力 从不断的经历和数据中吸取经验教训从而 应对未来的预测
  • 不断改善自身应对具体任务的能力

 

3. 机器学习常见分类

监督学习:

        在监督式学习下,输入数据被称为“训练数据”,每组训练数据有一个明确的标识或结果,如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”,对手写数字识别中的“1“,”2“,”3“,”4“等。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与“训练数据”的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)

 

无监督学习:

        无监督学习(或者叫非监督学习),它与监督学习的不同之处,在于我们事先没有任何训练样本,而需要直接对数据进行建模。 在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

 

强化学习:

        在这种学习模式下,输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)

 

深度学习:

       深度学习算法是对人工神经网络的发展。 在近期赢得了很多关注, 特别是百度也开始发力深度学习后, 更是在国内引起了很多关注。   在计算能力变得日益廉价的今天,深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法,用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括:受限波尔兹曼机(Restricted Boltzmann Machine, RBN), Deep Belief Networks(DBN),卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。

 

4. 机器学习常用算法

 

  • 决策树

        决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3, C4.5C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

      决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。根据一些 feature (特征)进行分类,每个节点提一个问题,通过判断,将数据分为两类,再继续提问。这些问题是根据已有数据学习出来的,再投入新数据的时候,就可以根据这棵树上的问题,将数据划分到合适的叶子上。

 

  • 随机森林算法

        随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。在机器学习中,随机森林是一个包含多个决策树的分类器, 并且其输出的类别是由个别树输出的类别的众数而定。分类器就是给定一个样本的数据,判定这个样本属于哪个类别的算法。例如在股票涨跌预测中,我们认为前一天的交易量和收盘价对于第二天的涨跌是有影响的,那么分类器就是通过样本的交易量和收盘价预测第二天的涨跌情况的算法。

 

  • 逻辑回归

         logistic回归(逻辑回归)是一种广义的线性回归,它将数据拟合到一个logit函数(或者叫做logistic函数)中,从而能够完成对事件发生的概率进行预测。

 

  • SVM

        SVM方法是通过一个非线性映射p,把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert空间),使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题.简单地说,就是升维和线性化.升维,就是把样本向高维空间做映射,一般情况下这会增加计算的复杂性,甚至会引起"维数灾难",因而人们很少问津.但是作为分类、回归等问题来说,很可能在低维样本空间无法线性处理的样本集,在高维特征空间中却可以通过一个线性超平面实现线性划分(或回归).一般的升维都会带来计算的复杂化,SVM方法巧妙地解决了这个难题:应用核函数的展开定理,就不需要知道非线性映射的显式表达式;由于是在高维特征空间中建立线性学习机,所以与线性模型相比,不但几乎不增加计算的复杂性,而且在某种程度上避免了"维数灾难".这一切要归功于核函数的展开和计算理论.

 

  • 朴素贝叶斯

        朴素贝叶斯分类是一种十分简单的分类算法,叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素,朴素贝叶斯的思想基础是这样的:对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别。

 

  • K最近邻算法

       K最近邻(k-Nearest Neighbor,KNN)分类算法,是最简单的机器学习算法之一。所谓K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居), 这K个实例的多数属于某个类,就把该输入实例分类到这个类中。

 

2017-04-14 12:08:13 YCM1101743158 阅读数 44983
  • 人工智能之机器学习算法的介绍

    机器学习算法入门教程,主要介绍人工智障机器学习常见算法,包括决策树、基于概率论的分类方法:朴素贝叶斯、Logistic回归、支持向量机、第利用AdaBoost元算法提高分类性能。

    4286 人正在学习 去看看 CSDN讲师
       机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。本文为您总结一下常见的机器学习算法,以供您在工作和学习中参考。

       机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。

学习方式

根据数据类型的不同,对一个问题的建模有不同的方式。在机器学习或者人工智能领域,人们首先会考虑算法的学习方式。在机器学习领域,有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法,这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。

监督式学习:

 

1479572800-6899-evMLVhLXNyCVuzslOH6trnicCxIA

在监督式学习下,输入数据被称为“训练数据”,每组训练数据有一个明确的标识或结果,如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”,对手写数字识别中的“1“,”2“,”3“,”4“等。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与“训练数据”的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)。

非监督式学习:

1479572801-7126-ekuYvKanIu4oBcJLm4yvfbDYos0g

在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

半监督式学习:

1479572801-6242-FrMf8f7298cBr0DPW5flDlDMicIw

在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归,算法包括一些对常用监督式学习算法的延伸,这些算法首先试图对未标识数据进行建模,在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。

 

强化学习:

1479572801-3762-Y2Xia0H1SegEtIt80ZphH1rueoxg

在这种学习模式下,输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)

 

在企业数据应用的场景下, 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域,由于存在大量的非标识的数据和少量的可标识数据, 目前半监督式学习是一个很热的话题。 而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。

 

算法类似性

根据算法的功能和形式的类似性,我们可以把算法分类,比如说基于树的算法,基于神经网络的算法等等。当然,机器学习的范围非常庞大,有些算法很难明确归类到某一类。而对于有些分类来说,同一分类的算法可以针对不同类型的问题。这里,我们尽量把常用的算法按照最容易理解的方式进行分类。

回归算法:

1479572801-1279-psQzicMbvjWArXBU2JNAOPBODxPA

回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域,人们说起回归,有时候是指一类问题,有时候是指一类算法,这一点常常会使初学者有所困惑。常见的回归算法包括:最小二乘法(Ordinary Least Square),逻辑回归(Logistic Regression),逐步式回归(Stepwise Regression),多元自适应回归样条(Multivariate Adaptive Regression Splines)以及本地散点平滑估计(Locally Estimated Scatterplot Smoothing)。

基于实例的算法

1479572801-1131-ac78ib7ynEpxJzhsOGARzvdvicKA

基于实例的算法常常用来对决策问题建立模型,这样的模型常常先选取一批样本数据,然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此,基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化(Learning Vector Quantization, LVQ),以及自组织映射算法(Self-Organizing Map , SOM)

正则化方法

1479572801-7007-cm573ULFNhgoEA8EJujubjLDb2qA

正则化方法是其他算法(通常是回归算法)的延伸,根据算法的复杂度对算法进行调整。正则化方法通常对简单模型予以奖励而对复杂算法予以惩罚。常见的算法包括:Ridge Regression, Least Absolute Shrinkage and Selection Operator(LASSO),以及弹性网络(Elastic Net)。

 

决策树学习

1479572801-4358-PiaYUw7zqu3954RyeBwhTHkHWk6Q

决策树算法根据数据的属性采用树状结构建立决策模型, 决策树模型常常用来解决分类和回归问题。常见的算法包括:分类及回归树(Classification And Regression Tree, CART), ID3 (Iterative Dichotomiser 3), C4.5, Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林(Random Forest), 多元自适应回归样条(MARS)以及梯度推进机(Gradient Boosting Machine, GBM)

 

贝叶斯方法

1479572802-1427-c3vzbPgNXvHoaaNyzGPlN8PBGZFw

贝叶斯方法算法是基于贝叶斯定理的一类算法,主要用来解决分类和回归问题。常见算法包括:朴素贝叶斯算法,平均单依赖估计(Averaged One-Dependence Estimators, AODE),以及Bayesian Belief Network(BBN)。

基于核的算法

1479572802-7140-pibItcdx0RaA35mJGsoZKgBpPmzA

基于核的算法中最著名的莫过于支持向量机(SVM)了。 基于核的算法把输入数据映射到一个高阶的向量空间, 在这些高阶向量空间里, 有些分类或者回归问题能够更容易的解决。 常见的基于核的算法包括:支持向量机(Support Vector Machine, SVM), 径向基函数(Radial Basis Function ,RBF), 以及线性判别分析(Linear Discriminate Analysis ,LDA)等

聚类算法

1479572802-3592-ibHWZ7EllSXgcrDJB9wKJVwbaQ2Q

聚类,就像回归一样,有时候人们描述的是一类问题,有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构,以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization, EM)。

关联规则学习

1479572802-6857-9tm3bibPFEcJ9w2KBxLV7mRn1exQ

关联规则学习通过寻找最能够解释数据变量之间关系的规则,来找出大量多元数据集中有用的关联规则。常见算法包括 Apriori算法和Eclat算法等。

 

人工神经网络

1479572803-5509-3CeY57PHXriauFqH1dVnOmP3P4RA

 

人工神经网络算法模拟生物神经网络,是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络是机器学习的一个庞大的分支,有几百种不同的算法。(其中深度学习就是其中的一类算法,我们会单独讨论),重要的人工神经网络算法包括:感知器神经网络(Perceptron Neural Network), 反向传递(Back Propagation), Hopfield网络,自组织映射(Self-Organizing Map, SOM)。学习矢量量化(Learning Vector Quantization, LVQ)

 

深度学习

1479572802-5101-zwjPk6sicl7s6PDnQWfsibJZ4SDQ

深度学习算法是对人工神经网络的发展。 在近期赢得了很多关注, 特别是百度也开始发力深度学习后, 更是在国内引起了很多关注。 在计算能力变得日益廉价的今天,深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法,用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括:受限波尔兹曼机(Restricted Boltzmann Machine, RBN), Deep Belief Networks(DBN),卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。

 

降低维度算法

1479572803-3312-5jc4UiaQCF66HAQia3icnwxyYK2A

像聚类算法一样,降低维度算法试图分析数据的内在结构,不过降低维度算法是以非监督学习的方式试图利用较少的信息来归纳或者解释数据。这类算法可以用于高维数据的可视化或者用来简化数据以便监督式学习使用。常见的算法包括:主成份分析(Principle Component Analysis, PCA),偏最小二乘回归(Partial Least Square Regression,PLS), Sammon映射,多维尺度(Multi-Dimensional Scaling, MDS), 投影追踪(Projection Pursuit)等。

 

集成算法:

1479572803-6688-tf1SIoQxZaasKHftspLAvvpDWANQ

集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练,然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法,同时也非常流行。常见的算法包括:Boosting, Bootstrapped Aggregation(Bagging), AdaBoost,堆叠泛化(Stacked Generalization, Blending),梯度推进机(Gradient Boosting Machine, GBM),随机森林(Random Forest)。

决策树

一、  决策树优点

1、决策树易于理解和解释,可以可视化分析,容易提取出规则。

2、可以同时处理标称型和数值型数据。

3、测试数据集时,运行速度比较快。

4、决策树可以很好的扩展到大型数据库中,同时它的大小独立于数据库大小。

二、决策树缺点

1、对缺失数据处理比较困难。

2、容易出现过拟合问题。

3、忽略数据集中属性的相互关联。

4、ID3算法计算信息增益时结果偏向数值比较多的特征。

三、改进措施

1、对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法。

2、使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题

三、应用领域

企业管理实践,企业投资决策,由于决策树很好的分析能力,在决策过程应用较多。

 

KNN算法

一、KNN算法的优点

 

1、KNN是一种在线技术,新数据可以直接加入数据集而不必进行重新训练

2、KNN理论简单,容易实现

二、KNN算法的缺点

1、对于样本容量大的数据集计算量比较大。

2、样本不平衡时,预测偏差比较大。如:某一类的样本比较少,而其它类样本比较多。

3、KNN每一次分类都会重新进行一次全局运算。

4、k值大小的选择。

三、KNN算法应用领域

文本分类、模式识别、聚类分析,多分类领域

支持向量机(SVM)

一、  SVM优点

1、解决小样本下机器学习问题。

2、解决非线性问题。

3、无局部极小值问题。(相对于神经网络等算法)

4、可以很好的处理高维数据集。

5、泛化能力比较强。

二、SVM缺点

1、对于核函数的高维映射解释力不强,尤其是径向基函数。

2、对缺失数据敏感。

三、SVM应用领域

文本分类、图像识别、主要二分类领域

AdaBoost算法

一、  AdaBoost算法优点

1、很好的利用了弱分类器进行级联。

2、可以将不同的分类算法作为弱分类器。

3、AdaBoost具有很高的精度。

4、相对于bagging算法和Random Forest算法,AdaBoost充分考虑的每个分类器的权重。

二、Adaboost算法缺点

1、AdaBoost迭代次数也就是弱分类器数目不太好设定,可以使用交叉验证来进行确定。

2、数据不平衡导致分类精度下降。

3、训练比较耗时,每次重新选择当前分类器最好切分点。

三、AdaBoost应用领域

模式识别、计算机视觉领域,用于二分类和多分类场景

朴素贝叶斯算法

一、  朴素贝叶斯算法优点

1、对大数量训练和查询时具有较高的速度。即使使用超大规模的训练集,针对每个项目通常也只会有相对较少的特征数,并且对项目的训练和分类也仅仅是特征概率的数学运算而已。

2、支持增量式运算。即可以实时的对新增的样本进行训练。

3、朴素贝叶斯对结果解释容易理解。

二、朴素贝叶斯缺点

1、由于使用了样本属性独立性的假设,所以如果样本属性有关联时其效果不好。

三、朴素贝叶斯应用领域

文本分类、欺诈检测中使用较多

Logistic回归算法

一、logistic回归优点

1、计算代价不高,易于理解和实现

二、logistic回归缺点

1、容易产生欠拟合。

2、分类精度不高。

三、logistic回归应用领域

用于二分类领域,可以得出概率值,适用于根据分类概率排名的领域,如搜索排名等。

Logistic回归的扩展softmax可以应用于多分类领域,如手写字识别等。

人工神经网络

一、  神经网络优点

1、分类准确度高,学习能力极强。

2、对噪声数据鲁棒性和容错性较强。

3、有联想能力,能逼近任意非线性关系。

二、神经网络缺点

1、神经网络参数较多,权值和阈值。

2、黑盒过程,不能观察中间结果。

3、学习过程比较长,有可能陷入局部极小值。

三、人工神经网络应用领域

目前深度神经网络已经应用与计算机视觉,自然语言处理,语音识别等领域并取得很好的效果。

 ===============================================================================================

原文:http://suanfazu.com/t/qian-tan-wo-dui-ji-qi-xue-xi-de-dian-li-jie/305

机器学习方法非常多,也很成熟。下面我挑几个说。

  1. 首先是SVM。因为我做的文本处理比较多,所以比较熟悉SVM。SVM也叫支持向量机,其把数据映射到多维空间中以点的形式存在,然后找到能够分类的最优超平面,最后根据这个平面来分类。SVM能对训练集之外的数据做很好的预测、泛化错误率低、计算开销小、结果易解释,但其对参数调节和核函数的参数过于敏感。个人感觉SVM是二分类的最好的方法,但也仅限于二分类。如果要使用SVM进行多分类,也是在向量空间中实现多次二分类。
    SVM有一个核心函数SMO,也就是序列最小最优化算法。SMO基本是最快的二次规划优化算法,其核心就是找到最优参数α,计算超平面后进行分类。SMO方法可以将大优化问题分解为多个小优化问题求解,大大简化求解过程。某些条件下,把原始的约束问题通过拉格朗日函数转化为无约束问题,如果原始问题求解棘手,在满足KKT的条件下用求解对偶问题来代替求解原始问题,使得问题求解更加容易。 SVM还有一个重要函数是核函数。核函数的主要作用是将数据从低位空间映射到高维空间。详细的内容我就不说了,因为内容实在太多了。总之,核函数可以很好的解决数据的非线性问题,而无需考虑映射过程。

  2. 第二个是KNN。KNN将测试集的数据特征与训练集的数据进行特征比较,然后算法提取样本集中特征最近邻数据的分类标签,即KNN算法采用测量不同特征值之间的距离的方法进行分类。KNN的思路很简单,就是计算测试数据与类别中心的距离。KNN具有精度高、对异常值不敏感、无数据输入假定、简单有效的特点,但其缺点也很明显,计算复杂度太高。要分类一个数据,却要计算所有数据,这在大数据的环境下是很可怕的事情。而且,当类别存在范围重叠时,KNN分类的精度也不太高。所以,KNN比较适合小量数据且精度要求不高的数据。
    KNN有两个影响分类结果较大的函数,一个是数据归一化,一个是距离计算。如果数据不进行归一化,当多个特征的值域差别很大的时候,最终结果就会受到较大影响;第二个是距离计算。这应该算是KNN的核心了。目前用的最多的距离计算公式是欧几里得距离,也就是我们常用的向量距离计算方法。
    个人感觉,KNN最大的作用是可以随时间序列计算,即样本不能一次性获取只能随着时间一个一个得到的时候,KNN能发挥它的价值。至于其他的特点,它能做的,很多方法都能做;其他能做的它却做不了。

  3. 第三个就是Naive Bayes了。Naive Bayes简称NB(牛X),为啥它牛X呢,因为它是基于Bayes概率的一种分类方法。贝叶斯方法可以追溯到几百年前,具有深厚的概率学基础,可信度非常高。Naive Baye中文名叫朴素贝叶斯,为啥叫“朴素”呢?因为其基于一个给定假设:给定目标值时属性之间相互条件独立。比如我说“我喜欢你”,该假设就会假定“我”、“喜欢”、“你”三者之间毫无关联。仔细想想,这几乎是不可能的。马克思告诉我们:事物之间是有联系的。同一个事物的属性之间就更有联系了。所以,单纯的使用NB算法效率并不高,大都是对该方法进行了一定的改进,以便适应数据的需求。
    NB算法在文本分类中用的非常多,因为文本类别主要取决于关键词,基于词频的文本分类正中NB的下怀。但由于前面提到的假设,该方法对中文的分类效果不好,因为中文顾左右而言他的情况太多,但对直来直去的老美的语言,效果良好。至于核心算法嘛,主要思想全在贝叶斯里面了,没啥可说的。

  4. 第四个是回归。回归有很多,Logistic回归啊、岭回归啊什么的,根据不同的需求可以分出很多种。这里我主要说说Logistic回归。为啥呢?因为Logistic回归主要是用来分类的,而非预测。回归就是将一些数据点用一条直线对这些点进行拟合。而Logistic回归是指根据现有数据对分类边界线建立回归公式,以此进行分类。该方法计算代价不高,易于理解和实现,而且大部分时间用于训练,训练完成后分类很快;但它容易欠拟合,分类精度也不高。主要原因就是Logistic主要是线性拟合,但现实中很多事物都不满足线性的。即便有二次拟合、三次拟合等曲线拟合,也只能满足小部分数据,而无法适应绝大多数数据,所以回归方法本身就具有局限性。但为什么还要在这里提出来呢?因为回归方法虽然大多数都不合适,但一旦合适,效果就非常好。
    Logistic回归其实是基于一种曲线的,“线”这种连续的表示方法有一个很大的问题,就是在表示跳变数据时会产生“阶跃”的现象,说白了就是很难表示数据的突然转折。所以用Logistic回归必须使用一个称为“海维塞德阶跃函数”的Sigmoid函数来表示跳变。通过Sigmoid就可以得到分类的结果。
    为了优化Logistic回归参数,需要使用一种“梯度上升法”的优化方法。该方法的核心是,只要沿着函数的梯度方向搜寻,就可以找到函数的最佳参数。但该方法在每次更新回归系数时都需要遍历整个数据集,对于大数据效果还不理想。所以还需要一个“随机梯度上升算法”对其进行改进。该方法一次仅用一个样本点来更新回归系数,所以效率要高得多。

  5. 第五个是决策树。据我了解,决策树是最简单,也是曾经最常用的分类方法了。决策树基于树理论实现数据分类,个人感觉就是数据结构中的B+树。决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。决策树计算复杂度不高、输出结果易于理解、对中间值缺失不敏感、可以处理不相关特征数据。其比KNN好的是可以了解数据的内在含义。但其缺点是容易产生过度匹配的问题,且构建很耗时。决策树还有一个问题就是,如果不绘制树结构,分类细节很难明白。所以,生成决策树,然后再绘制决策树,最后再分类,才能更好的了解数据的分类过程。
    决策树的核心树的分裂。到底该选择什么来决定树的分叉是决策树构建的基础。最好的方法是利用信息熵实现。熵这个概念很头疼,很容易让人迷糊,简单来说就是信息的复杂程度。信息越多,熵越高。所以决策树的核心是通过计算信息熵划分数据集。

  6. 我还得说一个比较特殊的分类方法:AdaBoost。AdaBoost是boosting算法的代表分类器。boosting基于元算法(集成算法)。即考虑其他方法的结果作为参考意见,也就是对其他算法进行组合的一种方式。说白了,就是在一个数据集上的随机数据使用一个分类训练多次,每次对分类正确的数据赋权值较小,同时增大分类错误的数据的权重,如此反复迭代,直到达到所需的要求。AdaBoost泛化错误率低、易编码、可以应用在大部分分类器上、无参数调整,但对离群点敏感。该方法其实并不是一个独立的方法,而是必须基于元方法进行效率提升。个人认为,所谓的“AdaBoost是最好的分类方法”这句话是错误的,应该是“AdaBoost是比较好的优化方法”才对。

好了,说了这么多了,我有点晕了,还有一些方法过几天再写。总的来说,机器学习方法是利用现有数据作为经验让机器学习,以便指导以后再次碰到的决策。目前来说,对于大数据分类,还是要借助分布式处理技术和云技术才有可能完成,但一旦训练成功,分类的效率还是很可观的,这就好比人年龄越大看待问题越精准的道理是一样的。这八个月里,从最初的理解到一步步实现;从需求的逻辑推断到实现的方法选择,每天都是辛苦的,但每天也都是紧张刺激的。我每天都在想学了这个以后可以实现什么样的分类,其实想想都是让人兴奋的。当初,我逃避做程序员,主要原因就是我不喜欢做已经知道结果的事情,因为那样的工作没有什么期盼感;而现在,我可以利用数据分析得到我想象不到的事情,这不仅满足了我的好奇感,也让我能在工作中乐在其中。也许,我距离社会的技术需求还有很远的距离,但我对自己充满信心,因为,我不感到枯燥,不感到彷徨,虽然有些力不从心,但态度坚定。

 

 

===================================================

http://blog.csdn.NET/vola9527/article/details/43347747

简述机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优缺点等。

1)C4.5算法:

ID3算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益,并选取具有最高增益的属性作为给定的测试属性。

C4.5算法核心思想是ID3算法,是ID3算法的改进,改进方面有:

1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;

2)在树构造过程中进行剪枝

3)能处理非离散的数据

4)能处理不完整的数据

 C4.5算法优点:产生的分类规则易于理解,准确率较高。

缺点:

1)在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

2)C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

 

2)K means 算法

是一个简单的聚类算法,把n的对象根据他们的属性分为k个分割,k< n。 算法的核心就是要优化失真函数J,使其收敛到局部最小值但不是全局最小值。

其中N为样本数,K是簇数,rnk b表示n属于第k个簇,uk 是第k个中心点的值。然后求出最优的uk

 

优点:算法速度很快

缺点是,分组的数目k是一个输入参数,不合适的k可能返回较差的结果。

 

 

3)朴素贝叶斯算法:

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。算法的基础是概率问题,分类原理是通过某对象的先验概率,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。朴素贝叶斯假设是约束性很强的假设,假设特征条件独立,但朴素贝叶斯算法简单,快速,具有较小的出错率。

在朴素贝叶斯的应用中,主要研究了电子邮件过滤以及文本分类研究。

 

4)K最近邻分类算法(KNN)

分类思想比较简单,从训练样本中找出K个与其最相近的样本,然后看这k个样本中哪个类别的样本多,则待判定的值(或说抽样)就属于这个类别。

缺点:

1)K值需要预先设定,而不能自适应

2)当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。

该算法适用于对样本容量比较大的类域进行自动分类。

 

 

5)EM最大期望算法

EM算法是基于模型的聚类方法,是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量,M步估计其他参数,交替将极值推向最大。

EM算法比K-means算法计算复杂,收敛也较慢,不适于大规模数据集和高维数据,但比K-means算法计算结果稳定、准确。EM经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。

 

6)PageRank算法

是google的页面排序算法,是基于从许多优质的网页链接过来的网页,必定还是优质网页的回归关系,来判定所有网页的重要性。(也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。)

优点:

完全独立于查询,只依赖于网页链接结构,可以离线计算。

缺点:

1)PageRank算法忽略了网页搜索的时效性。

2)旧网页排序很高,存在时间长,积累了大量的in-links,拥有最新资讯的新网页排名却很低,因为它们几乎没有in-links。

 

7)AdaBoost

Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。

整个过程如下所示:
1. 先通过对N个训练样本的学习得到第一个弱分类器;
2. 将分错的样本和其他的新数据一起构成一个新的N个的训练样本,通过对这个样本的学习得到第二个弱分类器;
3. 将和都分错了的样本加上其他的新样本构成另一个新的N个的训练样本,通过对这个样本的学习得到第三个弱分类器;
4. 如此反复,最终得到经过提升的强分类器。

目前AdaBoost算法广泛的应用于人脸检测、目标识别等领域。

 

8)Apriori算法

Apriori算法是一种挖掘关联规则的算法,用于挖掘其内含的、未知的却又实际存在的数据关系,其核心是基于两阶段频集思想的递推算法 。

Apriori算法分为两个阶段:

1)寻找频繁项集

2)由频繁项集找关联规则

算法缺点:

1) 在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;

2) 每次计算项集的支持度时,都对数据库中    的全部记录进行了一遍扫描比较,需要很大的I/O负载。

 

9)SVM支持向量机

支持向量机是一种基于分类边界的方法。其基本原理是(以二维数据为例):如果训练数据分布在二维平面上的点,它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是,通过训练,找到这些分类之间的边界(直线的――称为线性划分,曲线的――称为非线性划分)。对于多维数据(如N维),可以将它们视为N维空间中的点,而分类边界就是N维空间中的面,称为超面(超面比N维空间少一维)。线性分类器使用超平面类型的边界,非线性分类器使用超曲面。

支持向量机的原理是将低维空间的点映射到高维空间,使它们成为线性可分,再使用线性划分的原理来判断分类边界。在高维空间中是一种线性划分,而在原有的数据空间中,是一种非线性划分。

SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。

 

 

 

10)CART分类与回归树

是一种决策树分类方法,采用基于最小距离的基尼指数估计函数,用来决定由该子数

据集生成的决策树的拓展形。如果目标变量是标称的,称为分类树;如果目标变量是连续的,称为回归树。分类树是使用树结构算法将数据分成离散类的方法。

优点

1)非常灵活,可以允许有部分错分成本,还可指定先验概率分布,可使用自动的成本复杂性剪枝来得到归纳性更强的树。

2)在面对诸如存在缺失值、变量数多等问题时CART 显得非常稳健。







文章参考http://blog.csdn.net/u012422446/article/details/53034260


没有更多推荐了,返回首页