精华内容
下载资源
问答
  • 还有一种流程图,叫做N-S图,是在以前的流程图的基础上重新进行了改变,去掉了流程线,并且算法的每一步都用一个框进行描述,最终的执行是将所有的矩形框按照顺序连接起来。二、伪代码伪代码是一种介于我们编写的由....

    答案

    一、流程图

    流程图是描述代码的一种很好的工具,利用流程图,可以很好的表现出秩序执行过程中的三种基本结构组成—顺序结构、选择结构、循环结构等。需要注意的是,在使用流程图时,规定需要使用一些基本图形。

    还有一种流程图,叫做N-S图,是在以前的流程图的基础上重新进行了改变,去掉了流程线,并且算法的每一步都用一个框进行描述,最终的执行是将所有的矩形框按照顺序连接起来。

    二、伪代码

    伪代码是一种介于我们编写的由机器执行的语言,但是又不受语法约束的代码。这种语言时无法被机器执行的,但是和流程图一样,也是一种常用的描述算法的方法。

    伪代码主要是用来表示代码之间的逻辑关系,并不能交由计算机执行。因此,主要使用对象是设计师和程序员,是用来表达在编码前对算法执行过程中的一些想法的工具。

    三、自然语言

    算法的第三种表述,就是使用自然语言进行描述。自然语言比较符合我们的阅读习惯,是一种我们都能够理解的方式。不过,这种方式的缺点是无法很准确的描述循环、选择等结构。在使用自然语言描述算法的过程中,要求算法语言简练、层次清楚。因此,要注意语言和标点符号的使用。初次之外,还要在每个步骤前加上数字的标号。

    展开全文
  • 算法描述

    千次阅读 2019-09-22 17:40:02
    (2)描述算法的工具:算法可用自然语言、框图或高级程序设计语言进行描述。自然语言简单但易产生二义性;框图直观但不擅长表达数据的组织结构;而高级程序设计语言则较为准确、严谨,但因需考虑细节问题而显得相对...

    1.算法、语言、程序的关系

    首先分析数据结构中算法、语言和程序的关系。

    (1)算法:描述数据对象之间的关系(包括数据逻辑关系、存储关系描述)。

    (2)描述算法的工具:算法可用自然语言、框图或高级程序设计语言进行描述。自然语言简单但易产生二义性;框图直观但不擅长表达数据的组织结构;而高级程序设计语言则较为准确、严谨,但因需考虑细节问题而显得相对繁琐。

    (3)程序是算法在计算机中的实现(与所用计算机及所用语言有关)。程序设计的实质是对实际问题选择一种好的数据结构,加之设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。

    2.设计实现算法过程的步骤

    (1)找出与求解有关的数据元素之间的关系(建立结构关系)

    (2)确定在某一数据对象上所施加的运算。

    (3)考虑数据元素的存储表示。

    (4)选择描述算法的语言。

    (5)设计实现求解的算法,并用程序语言加以描述。

    3.描述算法的语言选择

    高级语言描述算法具有严格、准确的优点,但用于描述算法,也有语言细节过多的弱点,为此可采用类语言形式。所谓类语言,是指接近于高级语言而又不是严格的高级语言,它具有高级语言的一般语句,撇掉语言中的细节,以便把注意力集中在算法处理步骤本身的描述上。

    传统的描述语言是采用Pascal语言,由于该语言语法规范严谨,非常适合于数据结构。在Windows环境下,又出现了一系列功能强大且面向对象的程序开发工具,如visual C++、Borland C++、Visual Basic等。近年来在计算机科学研究、系统开发、教学以及应用开发中,C语言的使用范围越来越广,C语言成为许多学校计算机专业与非计算机专业必修的高级程序设计语言。C语言类型丰富,执行效率高。

     

    展开全文
  • GBDT基本原理及算法描述

    万次阅读 多人点赞 2018-08-25 13:16:21
    在AdaBoost基本原理与算法描述中,我们介绍了AdaBoost的基本原理,本篇博客将介绍boosting系列算法中的另一个代表算法GBDT(Gradient Boosting Decision Tree,梯度提升树)算法。这里对GBDT的学习做一个总结,也...

    一. 前言

    AdaBoost基本原理与算法描述中,我们介绍了AdaBoost的基本原理,本篇博客将介绍boosting系列算法中的另一个代表算法GBDT(Gradient Boosting Decision Tree,梯度提升树)算法。这里对GBDT的学习做一个总结,也希望对有帮助的同学能有一个帮助。

    在介绍AdaBoost的时候我们讲到了,AdaBoost算法是模型为加法模型,损失函数为指数函数,学习算法为前向分步算法时的分类问题。而GBDT算法是模型为加法模型,学习算法为前向分步算法,基函数为CART树,损失函数为平方损失函数的回归问题,为指数函数的分类问题和为一般损失函数的一般决策问题。在针对基学习器的不足上,AdaBoost算法是通过提升错分数据点的权重来定位模型的不足,而梯度提升算法是通过算梯度来定位模型的不足。

    当GBDT的损失函数是平方损失时,即L(y,f(x))=\frac{1}{2}(y-f(x))^2时,则负梯度-\frac{\partial L}{\partial f(x)}=y-f(x),而y-f(x)即为我们所说的残差,而我们的GBDT的思想就是在每次迭代中拟合残差来学习一个弱学习器。而残差的方向即为我们全局最优的方向。但是当损失函数不为平方损失时,我们该如何拟合弱学习器呢?大牛Friedman提出使用损失函数负梯度的方向代替残差方向,我们称损失函数负梯度为伪残差。而伪残差的方向即为我们局部最优的方向。所以在GBDT中,当损失函数不为平方损失时,用每次迭代的局部最优方向代替全局最优方向(这种方法是不是很熟悉?)。

    说了这么多,现在举个例子来看看GBDT是如何拟合残差来学习弱学习器的。我们可以证明,当损失函数为平方损失时,叶节点中使平方损失误差达到最小值的是叶节点中所有值的均值;而当损失函数为绝对值损失时,叶节点中使绝对损失误差达到最小值的是叶节点中所有值的中位数。相关证明将在最后的附录中给出。

    训练集是4个人,A,B,C,D年龄分别是14,16,24,26。样本中有购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下:(图片来源

    从上图可以看出,第一棵树建立的时候使用的是原始数据,而后每一棵树建立使用的是前n-1次的残差来拟合弱学习器。

    下面,我们就来简单的介绍一下GBDT的基本原理和算法描述。

    二. GBDT回归树基本模版

    梯度提升算法的回归树基本模版,如下所示:

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y,f(x))

    输出:回归树F(x)

    (1)初始化:(估计使损失函数极小化的常数值,它是只有一个根节点的树,一般平方损失函数为节点的均值,而绝对损失函数为节点样本的中位数)

                           f{_{0}}(x)=arg\underset{c}{min}\sum_{i=1}^{N}L(y{_{i}},c)

    (2)对m=1,2,...,M(M表示迭代次数,即生成的弱学习器个数):

    (a)对样本i=1,2,...N,计算损失函数的负梯度在当前模型的值将它作为残差的估计,对于平方损失函数为,它就是通常所说的残差;而对于一般损失函数,它就是残差的近似值(伪残差):

                          r{_{mi}}=-[\frac{\partial L(y{_{i}},f(x{_{i}}))}{\partial f((x{_{i}}))}]_{f(x)=f{_{m-1}}(x)}

    (b)对\left \{ (x{_{1}},r{_{m1}}),..., (x{_{N}},r{_{mN}})\right \}拟合一个回归树,得到第m棵树的叶节点区域R{_{mj}}j=1,2,...,J(J表示每棵树的叶节点个数)

    (c)对j=1,2,...,J,利用线性搜索,估计叶节点区域的值,使损失函数最小化,计算

                        c{_{mj}}=arg\underset{c}{min}\sum_{x{_{i}}\in R{_{mj}}}L(y{_{i}},f{_{m-1}}(x{_{i}}+c)))

    (d)更新

                        f{_{m}}(x)=f{_{m-1}}(x)+\sum_{J}^{j=1}c{_{mj}}I(x\in R{_{mj}})

    (3)得到最终的回归树

                                   F(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mj}}I(x\in R{_{mj}})

    三. GBDT的算法描述

    3.1 GBDT的损失函数

    在sklearn中梯度提升回归树有四种可选的损失函数,分别为'ls:平方损失','lad:绝对损失','huber:huber损失','quantile:分位数损失';而在sklearn中梯度提升分类树有两种可选的损失函数,一种是‘exponential:指数损失’,一种是‘deviance:对数损失’。下面分别介绍这几种损失函数。

    3.1.1 梯度提升回归树损失函数介绍

    (1)ls:平方损失,这是最常见的回归损失函数了,如下:

                      L(y,f(x))=(y-f(x))^2

    (2)lad:绝对损失,这个损失函数也很常见,如下:

                                 L(y,f(x))=|y-f(x)|

    对应负梯度为:

                                 r(y{_{i}},f(x{_{i}}))=sign(y{_{i}}-f(x{_{i}}))

    (3)huber:huber损失,它是平方损失和绝对损失的这种产物,对于远离中心的异常点采用绝对损失,而中心附近的点采用平方损失。这个界限一般用分位数点度量。损失函数如下:

                                L(y,f(x))=\begin{cases} \frac{1}{2}(y-f(x))^2 & \text{ if } |y-f(x)|\leq \delta \\ \delta (|y-f(x)|-\frac{\delta }{2})& \text{ if } |y-f(x)|> \delta \end{cases}

    对应的负梯度为:

                                r(y{_{i}},f(x{_{i}}))=\begin{cases} y{_{i}}-f(x{_{i}}) & \text{ if }|y{_{i}}-f(x{_{i}})|\leq \delta \\ \delta sign(y{_{i}}-f(x{_{i}})) & \text{ if } |y{_{i}}-f(x{_{i}})|> \delta \end{cases}

    (4)quantile:分位数损失,它对应的是分位数回归的损失函数,表达式如下:

                               L(y,f(x))=\sum_{y\geq f(x)}\theta |y-f(x)|+\sum_{y<f(x)}(1-\theta )|y-f(x)|

    其中θ为分位数,需要我们在回归前指定。对应的负梯度为:

                              r(y{_{i}},f(x{_{i}}))=\begin{cases} \theta & \text{ if } y{_{i}}\geq f(x{_{i}}) \\\theta-1 &\text{ if } y{_{i}}< f(x{_{i}}) \end{cases}

    对于huber损失和分位数损失主要作用就是减少异常点对损失函数的影响。

    3.1.2 梯度提升分类树损失函数介绍

    (1)exponential:指数损失,表达式如下:

                              L(y,f(x))=exp(-yf(x))

    (2)deviance:对数损失,类似于logistic回归的损失函数,输出的是类别的概率,表达式如下:

                              L(y,f(x))=ln(1+exp(-2yf(x)))

    下面我们来分别的介绍一下,这几种损失函数对应GBDT算法。

    3.2 GBDT回归算法描述

    3.2.1 平方损失GBDT算法描述

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y,f(x))=(y-f(x))^2

    输出:回归树F(x)

    (1)初始化:(可以证明当损失函数为平方损失时,节点的平均值即为该节点中使损失函数达到最小值的最优预测值,证明在最下面的附录给出)

                           f{_{0}}(x)=\bar{y}  

    (2)对m=1,2,...,M

    (a)对样本i=1,2,...N,计算伪残差(对于平方损失来说,伪残差就是真残差)

                          r{_{mi}}=-[\frac{\partial L(y{_{i}},f(x{_{i}}))}{\partial f((x{_{i}}))}]_{f(x)=f{_{m-1}}(x)}=y-f(x{_{i}})

    (b)对\left \{ (x{_{1}},r{_{m1}}),..., (x{_{N}},r{_{mN}})\right \}拟合一个回归树,得到第m棵树的叶节点区域R{_{mj}}j=1,2,...,J

    (c)对j=1,2,...,J,利用线性搜索,估计叶节点区域的值,使损失函数最小化,计算

                        c{_{mj}}=\frac{1}{K}\sum_{x{_{i}}\in R{_{mj}}}(y{_{i}}-f(x{_{i}})),K表示第m棵树的第j个节点中的样本数量

    上式表示c{_{mj}}的取值为第m棵树的第j个叶节点中伪残差的平均数

    (d)更新

                        f{_{m}}(x)=f{_{m-1}}(x)+\sum_{J}^{j=1}c{_{mj}}I(x\in R{_{mj}})

    (3)得到最终的回归树

                                   F(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mj}}I(x\in R{_{mj}})

    3.2.2 绝对损失GBDT算法描述

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y,f(x))=|y-f(x)|

    输出:回归树F(x)

    (1)初始化:(可以证明当损失函数为绝对损失时,节点中样本的中位数即为该节点中使损失函数达到最小值的最优预测值,证明在最下面的附录给出)

                           f{_{0}}(x)=median\left \{ y \right \}

    (2)对m=1,2,...,M

    (a)对样本i=1,2,...N,计算伪残差

                          r{_{mi}}=-[\frac{\partial L(y{_{i}},f(x{_{i}}))}{\partial f((x{_{i}}))}]_{f(x)=f{_{m-1}}(x)}=sign(y{_{i}}-f(x{_{i}}))

    (b)对\left \{ (x{_{1}},r{_{m1}}),..., (x{_{N}},r{_{mN}})\right \}拟合一个回归树,得到第m棵树的叶节点区域R{_{mj}}j=1,2,...,J

    (c)对j=1,2,...,Ji=1,2,...,N,计算

                        c{_{mj}}=\underset{​{x{_{i}}\in R{_{mj}}}}{median}\left \{ y{_{i}}-f{_{m-1}(x{_{i}})} \right \}

    上式表示c{_{mj}}的取值为第m棵树的第j个叶节点中伪残差的中位数

    (d)更新

                        f{_{m}}(x)=f{_{m-1}}(x)+\sum_{J}^{j=1}c{_{mj}}I(x\in R{_{mj}})

    (3)得到最终的回归树

                                   F(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mj}}I(x\in R{_{mj}})

    3.2.3 huber损失GBDT算法描述

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y,f(x))=\begin{cases} \frac{1}{2}(y-f(x))^2 & \text{ if } |y-f(x)|\leq \delta \\ \delta (|y-f(x)|-\frac{\delta }{2})& \text{ if } |y-f(x)|> \delta \end{cases}

    输出:回归树F(x)

    (1)初始化:

                           f{_{0}}(x)=median\left \{ y \right \}

    (2)对m=1,2,...,M

    (a)对样本i=1,2,...N,计算

                          \delta {_{m}}=\underset{\alpha }{quantile}\left \{ y{_{i}}-f{_{m-1}(x{_{i}})} \right \}

    \delta {_{m}}表示分位数;\alpha表示将伪残差的百分之多少设为分位数,在sklearn中是需要我们自己设置的,默认为0.9

                          r{_{mj}}=\begin{cases} y{_{i}}-f(x{_{i}}) & \text{ if }|y{_{i}}-f(x{_{i}})|\leq \delta{_{m}} \\ \delta{_{m}} sign(y{_{i}}-f(x{_{i}})) & \text{ if } |y{_{i}}-f(x{_{i}})|> \delta{_{m}} \end{cases}

    (b)对\left \{ (x{_{1}},r{_{m1}}),..., (x{_{N}},r{_{mN}})\right \}拟合一个回归树,得到第m棵树的叶节点区域R{_{mj}}j=1,2,...,J

    (c)对j=1,2,...,Ji=1,2,...,N,计算

                        \bar{r}{_{mj}}=\underset{x{_{i}}\in R{_{mj}}}{median}\left \{y{_{i}}-f{_{m-1}}(x{_{i}}) \right \}

                        \tiny c{_{mj}}=\bar{r}{_{mj}}+\frac{1}{N{_{mj}}}\sum_{x{_{i}}\in R{_{mj}}}sign(y{_{i}}-f{_{m-1}(x{_{i}})}-\bar{r}{_{mj}})*min(\delta {_{m}},abs(y{_{i}}-f{_{m-1}(x{_{i}})}-\bar{r}{_{mj}}))

    (d)更新

                        f{_{m}}(x)=f{_{m-1}}(x)+\sum_{J}^{j=1}c{_{mj}}I(x\in R{_{mj}})

    (3)得到最终的回归树

                                   F(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mj}}I(x\in R{_{mj}})

    3.3 GBDT分类算法描述

    GBDT分类算法思想上和GBDT的回归算法没有什么区别,但是由于样本输出不是连续值,而是离散类别,导致我们无法直接从输出类别去拟合类别输出误差。为了解决这个问题,主要有两种方法。一是用指数损失函数,此时GBDT算法退化为AdaBoost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说,我们用的是类别的预测概率值和真实概率值的差来拟合损失。当损失函数为指数函数时,类似于AdaBoost算法,这里不做介绍,下面介绍损失函数为log函数时的GBDT二分类和多分类算法。

    3.3.1 log损失GBDT的二分类算法描述

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y,f(x))=ln(1+exp(-2yf(x))),y={-1,1}

    输出:分类树F(x)

    (1)初始化:

                           f{_{0}}(x)=\frac{1}{2}ln\frac{P(y=1|x)}{P(y=-1|x)}

    (2)对m=1,2,...,M

    (a)对样本i=1,2,...N,计算伪残差

                          r{_{mi}}=\frac{2y{_{i}}}{1+exp(2y{_{i}}f{_{m-1}}(x{_{i}}))}

    (b)对概率残差\left \{ (x{_{1}},r{_{m1}}),..., (x{_{N}},r{_{mN}})\right \}拟合一个分类树,得到第m棵树的叶节点区域R{_{mj}}j=1,2,...,J

    (c)对j=1,2,...,Ji=1,2,...,N,计算

                        c{_{mj}}=\frac{\sum_{x{_{i}}\in R{_{mj}}}r{_{mj}}}{\sum_{x{_{i}}\in R{_{mj}}}|r{_{mj}}|(2-|r{_{mj}}|)}

    (d)更新

                        f{_{m}}(x)=f{_{m-1}}(x)+\sum_{J}^{j=1}c{_{mj}}I(x\in R{_{mj}})

    (3)得到最终的分类树

                                   F(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mj}}I(x\in R{_{mj}})

    由于我们用的是类别的预测概率值和真实概率值的差来拟合损失,所以最后还要讲概率转换为类别,如下:

                                   P(y=1|x)=\frac{1}{1+exp(-2F(x))}

                                   P(y=-1|x)=\frac{1}{1+exp(2F(x))}

    最终输出比较类别概率大小,概率大的就预测为该类别。

    3.3.2 log损失GBDT的多分类算法描述         

    输入:训练数据集T=\left \{ (x{_{1},y{_{1}}}),(x{_{2}},y{_{2}}),...,(x{_{N}},y{_{N}}) \right \},损失函数为L(y{_{k}},f{_{k}}(x))=-\sum_{k=1}^{K}y{_{k}}lnP{_{k}}(x)y{_{k}}={0,1}表示是否属于第k类别,1表示是,0表示否。k=1,2,...,K,表示共有多少分类的类别。

    输出:分类树F(x)

    (1)初始化:

                           f{_{k0}}(x)=0k=1,2,...,K

    (2)对m=1,2,...,M

    (a)计算样本点俗属于每个类别的概率:

                        P{_{k}}(x)=exp(f{_{k}}(x))/\sum_{l=1}^{K}exp(f{_{l}}(x))

    (b)对k=1,2,...,K:

            1) r{_{ki}}=y{_{ki}}-P{_{k}}(x{_{i}})i=1,2,...,N

            2)对概率伪残差\left \{ (x{_{1}},r{_{k1}}),..., (x{_{N}},r{_{kN}})\right \}拟合一个分类树

            3)c{_{mkj}}=\frac{K-1}{K}\frac{\sum_{x{_{i}}\in R{_{mkj}}}r{_{ki}}}{\sum_{x{_{i}}\in R{_{mkj}}}|c{_{ki}}|(1-|c{_{ki}}|)}

            4)f{_{mk}}(x)=f{_{k,m-1}}(x)+\sum_{j=1}^{J}c{_{mkj}}I(x\in R{_{mkj}})

    (3)得到最终的分类树

                                   F{_{Mk}}(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c{_{mkj}}I(x\in R{_{mkj}})

    最后得到的F{_{Mk}}(x)可以被用来去得到分为第k类的相应的概率P{_{Mk}}(x)

                                   P{_{Mk}}=exp(F{_{Mk}}(x))/\sum_{l=1}^{K}exp(F{_{Ml}}(x))

    由于我们用的是类别的预测概率值和真实概率值的差来拟合损失,所以最后还要将概率转换为类别,如下:

                                   \hat{k}(x)=arg\underset{1\leq k\leq K}{min}\sum_{​{k}'=1}^{K}[c(k,{k}')P{_{M{k}'}(x)}]

    \hat{k}(x)为最终的输出类别,c(k,{k}')为当真实值为{k}'时,预测为第k类时的联合代价,即概率最大的类别即为我们所预测的类别。当K=2时,该算法等价于为二分类算法。

    到这里,我们算法的描述环节已经介绍完毕。还有一个算法就是分位数回归的算法描述没有介绍,因为早期的论文里面并没有介绍到该算法,所以,这里我们也不予以介绍,感兴趣的小伙伴可以查阅相关资料或者直接看sklearn有关该算法的源码。

    最后,我们还有两个证明没有说,接下来我们证明我们在上面提到的有关损失函数为平方损失时叶节点的最佳预测为叶节点的残差均值和损失函数为绝对损失时,叶节点的最佳预测为叶节点残差的中位数。

    四. 附录

    4.1 证明:损失函数为平方损失时,叶节点的最佳预测为叶节点残差均值

    节点R中有N个样本点,假设s为切分点,R{_{1}}R{_{2}}分别为切分后的左节点和右节点,分别有节点个数为N{_{1}},N{_{2}}

    我们的目标是找到切分点s,在R{_{1}}R{_{2}}内部使平方损失误差达到最小值的c{_{1}},c{_{2}},如下:

                                  \underset{s}{min}[\underset{c{_{1}}}{min}\sum_{x{_{i}}\in R{_{1}}}(y{_{i}}-c{_{1}})^2+\underset{c{_{2}}}{min}\sum_{x{_{i}}\in R{_{2}}}(y{_{i}}-c{_{2}})^2]

    \sum_{x{_{i}}\in R{_{1}}}(y{_{i}}-c{_{1}})^2\sum_{x{_{i}}\in R{_{2}}}(y{_{i}}-c{_{2}})^2分别对c{_{1}},c{_{2}}求偏导,并令偏导等于0,得到在R{_{1}}R{_{2}}内部使平方损失误差达到最小值的c{_{1}},c{_{2}}

                                  c{_{1}}=\frac{1}{N{_{1}}}\sum_{x{_{i}}\in R{_{1}}}y{_{i}},   c{_{2}}=\frac{1}{N{_{2}}}\sum_{x{_{i}}\in R{_{2}}}y{_{i}}

    c{_{1}},c{_{2}}和即为各自叶节点中的残差的均值。

    4.2 证明:损失函数为绝对损失时,叶节点的最佳预测为叶节点残差的中位数。

    损失函数L(y{_{i}},f(x{_{i}}))=\sum_{i=1}^{N}|y{_{i}}-f(x{_{i}})|

    假设在节点中有N{_{1}}个节点使y{_{i}}-f(x{_{i}})>0,则有N-N{_{1}}个节点使y{_{i}}-f(x{_{i}})<0,那么:

                                  L(y{_{i}},f(x{_{i}}))=\sum_{x{_{i}}\in N{_{1}}}[y{_{i}}-f(x{_{i}})]+\sum_{x{_{i}}\in N-N{_{1}}}[f(x{_{i}})-y{_{i}}]

    我们的目标是是损失函数最小化,所以,上式对f(x{_{i}})求偏导,并令偏导等于0,得:

                                  \frac{\partial L}{\partial f(x{_{i}})}=\sum_{x{_{i}}\in N{_{1}}}(-1)+\sum_{x{_{i}}\in N-N{_{1}}}(1)=-N{_{1}}+(N-N{_{1}})=0

    得:

                                 N{_{1}}=\frac{N}{2}

    而N为节点中样本的总数,所以使节点的最佳预测为节点中残差的中位数。

    五. 参考文献/博文

    (1)大牛Friedman关于梯度提升的论文

    (2)《统计学习方法》第八章

    (3)关于机器学习总结比较好的博客

     

     

    展开全文
  • 算法描述---伪代码

    千次阅读 2017-11-23 14:13:40
     算法描述是指对设计出的算法,用一种方式进行详细的描述,以便与人交流。描述可以使用自然语言、伪代码,也可使用程序流程图,但描述的结果必须满足算法的五个特征。  使用自然语言描述算法显然很有吸引力,但是...

     算法描述

       算法描述是指对设计出的算法,用一种方式进行详细的描述,以便与人交流。描述可以使用自然语言、伪代码,也可使用程序流程图,但描述的结果必须满足算法的五个特征。

      使用自然语言描述算法显然很有吸引力,但是自然语言固有的不严密性使得要简单清晰的描述算法变得很困难。因此,使用伪代码来描述算法是一个很好的选择。

      算法的特征

    1. 输入:一个算法必须有零个或以上输入量。
    2. 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
    3. 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际运行结果是确定的。
    4. 有限性:依据图灵的定义,一个算法是能够被任何 图灵完备系统模拟的一串运算,而图灵机器只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
    5. 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

      伪代码

      伪代码是自然语言和类编程语言组成的混合结构。它比自然语言更精确,描述算法很简洁;同时也可以很容易转换成计算机程序。虽然如此,但计算机科学家们从来就没有对伪代码的形式达成共识,不同作者的教材会设计他们自己的“方言”(伪代码)。幸运的是,这些伪代码都十分相似,任何熟悉一门现代变成语言的人都完全能够理解。

      使用伪代码描述算法可以让程序员很容易将算法转换成程序,同时还可以避开不同程序语言的语法差别,如Pascal语言使用“:=”作为赋值,使用“=”作为比较;又如C/C++的赋值使用“=”,而判断相等的比较则是用“==”。

      常用的微带关键词含义如下表所示:

     

    伪代码含义C/C++语言
    缩进程序块{}
    / /行注释/ /
    赋值=
    =比较运算——等于==
    比较运算——不等于!=
    比较运算——小于或等于< =
    比较运算——大于或等于>=
    for i←1 to n doFor循环for(i=1;i⇐n;i++){}
    for i←n downto 1 doFor循环for(i=n;i>=1;i–){}
    while i<n doWihle循环while(i<n){}
    do while i<nDo-While循环do {} while(i<n)
    repeat until i<nRepeat循环
    if i<n elseIf-Else语句if(i<n){} else {}
    return函数返回值return
    A[0..n-1]数组定义int A[n-1]
    A[i]引用数组A[i]
    SubFun()函数调用SubFun()
     

     

     

     

     

     

     

     

     

     

     

     

     

    伪代码(Pseudocode)是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。 介于自然语言与编程语言之间。

      它以编程语言的书写形式指明算法的职能。相比于程序语言(例如Java, C++,C, Dephi 等等)它更类似自然语言。它是半角式化、不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式(这里,你可以使用任何一种你熟悉的文字,中文,英文 等等,关键是你把你程序的意思表达出来)描述出来. 使用伪代码, 可以帮助我们更好的表述算法, 不用拘泥于具体的实现.

      人们在用不同的编程语言实现同一个算法时意识到,他们的实现(注意:这里是实现,不是功能)很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个(用其他编程语言编写的程序的)功能时可能很难,因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。

      当考虑算法功能(而不是其语言实现)时,伪代码常常得到应用。计算机科学在教学中通常使用虚拟码,以使得所有的程序员都能理解。

      综上,简单的说,让人便于理解的代码。不依赖于语言的,用来表示程序执行过程,而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。 

    语法规则

      例如,类Pascal语言的伪代码的语法规则是: 在伪代码中,每一条指令占一行(else if,例外)。指令后不跟任何符号(Pascal和C中语句要以分号结尾)。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进。

        算法的伪代码语言在某些方面可能显得不太正规,但是给我们描述算法提供了很多方便,并且可以使我们忽略算法实现中很多麻烦的细节。通常每个算法开始时都要描述它的输入和输出,而且算法中的每一行都给编上号码,在解释算法的过程中会经常使用算法步骤中的行号来指代算法的步骤。算法的伪代码描述形式上并不是非常严格,其主要特性和通常的规定如下:
            1) 算法中出现的数组、变量可以是以下类型:整数、实数、字符、位串或指针。通常这些类型可以从算法的上下文来看是清楚的,并不需要额外加以说明。
            2) 在算法中的某些指令或子任务可以用文字来叙述,例如,"设x是A中的最大项",这里A是一个数组;或者"将x插入L中",这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。
            3) 算术表达式可以使用通常的算术运算符(+,-,*,/,以及表示幂的^)。逻辑表达式可以使用关系运算符=,≠,<,>,≤和≥,以及逻辑运算符与(and),或(or),非(not)。
            4) 赋值语句是如下形式的语句:a<-b 。
    这里a是变量、数组项,b是算术表达式、逻辑表达式或指针表达式。语句的含义是将b的值赋给a。
            5) 若a和b都是变量、数组项,那么记号a<->b 表示a和b的内容进行交换。
            6) goto语句具有形式
                                            goto label(goto标号)
    它将导致转向具有指定标号的语句。
            7) 条件语句有以下两种形式:
                                                if c then s或者 
                                                   if c then s
                                                      else s′
    这里c是逻辑表达式,s和s′是单一的语句或者是被括在do和end之间的语句串。对于上述两种形式,假若c为真,则s被执行一次。假若c为假,则在第一种形式中,if语句的执行就完成了,而在第二种形式中,执行s′。在所有的情况下,控制就进行到了下一个语句,除非在s或s′中的goto语句使控制转向到其它地方。
             8) 有两种循环指令:while和for。
             while语句的形式是
                                                  while c do  
                                                        s
                                                      end
    这里c是逻辑表达式,而s是由一个或更多个语句组成的语句串。当c为真时,执行s。在每一次执行s之前,c都被检查一下;假若c为假,控制就进行到紧跟在while语句后面的语句。注意,当控制第一次达到while语句时,假若c为假,则s一次也不执行。 
           for语句的形式是
                                          for var init to limit by incr do
                                                            s
                                                          end
    这里var是变量,init、limit和incr都是算术表达式,而s是由一个或多个语句组成的语句串。初始时,var被赋予init的值。假若incr≥0,则只要var≤limit,就执行s并且将incr加到var上。(假若incr<0,则只要var≥limit,就执行s并且将incr加到var上)。incr的符号不能由s来该改变。
          9) exit语句可以在通常的结束条件满足之前,被用来结束while循环或者for循环的执行。exit导致转向到紧接在包含exit的(最内层)while或者for循环后面的一个语句。
         10) return用来指出一个算法执行的终点;如果算法在最后一条指令之后结束,它通常是被省略的;它被用得最多的场合是检测到不合需要的条件时。return的后面可以紧接被括在引号的信息。
          11) 算法中的注释被括在/* */之中。诸如read和output之类的各种输入或者输出也在需要时被用到。
         

    伪代码实例

      伪代码只是像流程图一样用在程序设计的初期,帮助写出程序流程。简单的程序一般都不用写流程、写思路,但是复杂的代码,最好还是把流程写下来,总体上去考虑整个功能如何实现。写完以后不仅可以用来作为以后测试,维护的基础,还可用来与他人交流。但是,如果把全部的东西写下来必定可能会让费很多时间,那么这个时候可以采用伪代码方式。比如:

      IF 九点以前 THEN

         do 私人事务;

      ELSE 9点到18点 THEN

      工作;

      ELSE

      下班;

      END IF

      这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观.

     

      下面介绍一种类Pascal语言的伪代码的语法规则。

      在伪代码中,每一条指令占一行(else if 例外,),指令后不跟任何符号(Pascal和C中语句要以分号结尾);

      书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进; 

      在伪代码中,通常用连续的数字或字母来标示同一即模块中的连续语句,有时也可省略标号。

      符号△后的内容表示注释;

      在伪代码中,变量名和保留字不区分大小写,这一点和Pascal相同,与C或C++不同;

      在伪代码中,变量不需声明,但变量局部于特定过程,不能不加显示的说明就使用全局变量;

      赋值语句用符号←表示,x←exp表示将exp的值赋给x,其中x是一个变量,exp是一个与x同类型的变量或表达式(该表达式的结果与x同类型);多重赋值i←j←e是将表达式e的值赋给变量i和j,这种表示与j←e和i←e等价。

      例如:

      x←y

      x←20*(y+1)

      x←y←30

      以上语句用C分别表示为:

      x = y;

      x = 20*(y+1);

      x = y = 30;

      选择语句用if-then-else来表示,并且这种if-then-else可以嵌套,与Pascal中的if-then-else没有什么区别。

      例如:

      if (Condition1)

      then [ Block 1 ]

      else if (Condition2)

      then [ Block 2 ]

      else [ Block 3 ]

      循环语句有三种:while循环、repeat-until循环和for循环,其语法均与Pascal类似,只是用缩进代替begin - end;

     

      例如:

      1. x ← 0

      2. y ← 0

      3. z ← 0

      4. while x < N

      1. do x ← x + 1

      2. y ← x + y

      3. for t ← 0 to 10

      1. do z ← ( z + x * y ) / 100

      2. repeat

      1. y ← y + 1

      2. z ← z - y

      3. until z < 0

      4. z ← x * y

      5. y ← y / 2

       上述语句用C或C++来描述是:

      x = y = z = 0;

      while( z < N )

      {

      x ++;

      y += x;

      for( t = 0; t < 10; t++ )

      {

      z = ( z + x * y ) / 100;

      do {

      y ++;

      z -= y;

      } while( z >= 0 );
         }
      z = x * y;

      }

      y /= 2;

      数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。

      例如:

      A[1…j]表示含元素A[1], A[2], … , A[j]的子数组;

      复合数据用对象(Object)来表示,对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。

      例如:

      数组可被看作是一个对象,其属性有length,表示其中元素的个数,则length[A]就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号,一般来说从上下文可以看出其含义。

      用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f,赋值y←x就使f[y]=f[x],更进一步,若有f[x]←3,则不仅有f[x]=3,同时有f[y]=3,换言之,在赋值y←x后,x和y指向同一个对象。

      有时,一个指针不指向任何对象,这时我们赋给他nil。

      函数和过程语法与Pascal类似。

      函数值利用 “return (函数返回值)” 语句来返回,调用方法与Pascal类似;过程用 “call 过程名”语句来调用;

      例如:

      1. x ← t + 10

      2. y ← sin(x)

      3. call CalValue(x,y)

      参数用按值传递方式传给一个过程:被调用过程接受参数的一份副本,若他对某个参数赋值,则这种变化对发出调用的过程是不可见的。当传递一个对象时,只是拷贝指向该对象的指针,而不拷贝其各个域。

    展开全文
  • 算法描述

    千次阅读 2020-04-13 21:34:45
    算法描述</center> 注:本文为学习《C语言从入门到精通》时,对部分章节的总结 1、自然语言 人们日常使用的语言,通俗易懂,但用来描述较为复杂的算法时,不是很方便。 2、流程图 流程图是一种传统的...
  • LibTomCtypt中为密码算法定义了一个算法描述子cipher_descriptor,可以把它理解为一个类,里面描述了密码算法应该有的变量和函数操作。密码算法描述子的详细描述可以参见tomcrypt_cipher.h   extern struct ltc_...
  • 用流程图描述算法

    万次阅读 多人点赞 2018-07-18 08:41:11
    哪还有没有其它描述算法方式呢?毕竟文字看起来比较费劲。流程图就是一种描述算法的图形化描述,用流程图可以清晰地描述算法的思路和过程。通过本篇的学习,你将了解到如何用流程图来描述算法。】   流程图是...
  • 算法及其描述

    千次阅读 2018-03-01 16:48:00
    算法有五个重要的特性1)有穷性 2)确定性 3)可行性 4)有输入 5)有输出算法设计应满足以下几条目标: 1)正确性 2)可使用性 3)可读性 4)健壮性 5)高效率和低存储量需求二、 算法时间复杂度分析通常有两种衡量算法效率的...
  • 算法

    万次阅读 2018-02-08 00:13:09
    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有...
  • 漫水填充算法描述

    千次阅读 2015-07-07 16:22:52
    漫水填充算法描述 1.1、种子填充算法 种子填充算法是从多边形区域内部的一点开始,由此出发找到区域内的所有像素。 种子填充算法采用的边界定义是区域边界上所有像素具有某个特定的颜色值,区域内部所有...
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...
  • AdaBoost基本原理与算法描述

    万次阅读 多人点赞 2018-08-21 19:59:33
    最近在看集成学习方法,前面已经对XGBoost的原理与简单实践做了介绍,这次对AdaBoost算法做个学习笔记,来巩固自己所学的知识,同时也希望对需要帮助的人有所帮助。 关于集成学习主要有两大分支,一种是bagging方法...
  • java里reverse 算法描述

    千次阅读 2013-06-20 07:33:31
    算法多种多样 关键是理解原理 这个算法的实现并不复杂 下面是我自己写的一个算法 public class StringUtils{    /**  *隐藏构造函数 避免实例化这个类的对象  *对于只有方法 没有任何...
  • static const uint32_t rcon[10] = { 0x01000000UL, 0x02000000UL, 0x04000000UL, 0x08000000UL, 0x10000000UL, 0x20000000UL, 0x40000000UL, 0x80000000UL, 0x1B000000UL, 0x36000000UL };
  • 随机森林基本原理与算法描述

    万次阅读 2018-08-27 23:17:49
    在前几篇博文中我们介绍了boosting系列的几个主要算法GBDT、AdaBoost和XGboost的基本原理与算法描述。本篇博文将介绍集成学习的另一大分支bagging方法的代表算法随机森林(Random Forest)算法。 bagging系列的算法...
  • 声纹识别之PLDA算法描述

    万次阅读 多人点赞 2015-08-05 09:59:41
    因为国内博士论文前面的综述写的还不错,嘿嘿~我写这个主要是给不熟悉这个领域内的朋友看的,用通熟的话描述这个领域内重要的一些算法,等于是入个门吧。PLDA算法前面博客已经提到过声纹识别的信道补偿算法
  • 无向图以邻接矩阵存储,请算法描述深度优先遍历该图的非递归算法。哪位大神可以帮忙写具体点用栈怎么实现?谢谢了!![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/1.gif)
  • 使用通俗的语言简单回顾一下JVM GC的垃圾标记算法和垃圾收集算法。 一、什么是Garbage(辣鸡)? 通俗的认为,不被任何在用的引用所指向的资源称为垃圾。硬件资源是有限的,如何准确的标识出垃圾,让JVM来做后续...
  • 算法精解:C语言描述(中文版).pdf

    千次下载 热门讨论 2014-03-23 08:21:49
    适合学习算法和程序员。算法精解:C语言描述(中文版).pdf
  • Dijkstra算法描述及其正确性证明
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • 层次聚类分为两种: (1) 凝聚的层次聚类:自底向上的策略,首先将每个对象作为一个簇,然后合并这些原子簇为更大的... AGNES(Agglomerative Nesting) 是凝聚的层次聚类算法,如果簇C1中的一个对象和簇C2中的一个
  • 数据结构与算法分析C++描述第三版中文

    千次下载 热门讨论 2010-06-03 08:53:18
    数据结构与算法分析C++描述第三版中文 数据结构与算法分析C++描述第三版中文
  • 伪代码描述归并排序算法

    千次阅读 2015-09-24 19:50:45
    百度百科上介绍,伪码(Pseudocode)是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java等)实现。归并排序是分治法(Divide and conquer)一个非常典型的应用,时间...
  • 【特征检测】BRIEF特征点描述算法

    万次阅读 多人点赞 2015-07-16 13:08:13
    它是一种二进制编码的描述子,摈弃了利用区域灰度直方图描述特征点的传统方法,大大的加快了特征描述符建立的速度,同时也极大的降低了特征匹配的时间,是一种非常快速,很有潜力的算法
  • [密码学]DES算法过程描述

    万次阅读 多人点赞 2014-01-16 22:12:02
    DES算法曾是美国政府保护非机密的敏感数据使用的数据加密标准,虽然现在已经因为安全性不足被AES算法取代,不过作为第一个公开...本文描述了DES加密算法的整个流程和其中的细节,看完本文,读者就可以自己实现DES了: )
  • 光线跟踪算法描述—计算机图形学

    万次阅读 2017-05-04 15:10:35
    光线跟踪算法原理: 步骤一:从视点出发通过该像素中心向场景发出一条光线R,并求出R与场景中物体的全部交点;获得离视点最近交点P;并依据局部光照明模型计算P处颜色值Ic (光线投射)。 步骤二:在P处沿着R镜面...
  • 数据结构算法描述和分析

    千次阅读 2018-08-17 19:25:49
    高级语言程序设计在解决某一实际问题的一般步骤是:分析实际问题、确定数学模型、设计或选择一个求解此数学模型的算法、编写程序进行调试和测试解决问题等几个步骤。 例1:已知:游泳池的长length和宽winde,求面积...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,000,275
精华内容 400,110
关键字:

属于算法描述方式的是