数据挖掘算法(logistic回归,随机森林,GBDT和xgboost)

面网易数据挖掘工程师岗位,第一次面数据挖掘的岗位,只想着能够去多准备一些,体验面这个岗位的感觉,虽然最好心有不甘告终,不过继续加油。

不过总的来看,面试前有准备永远比你没有准备要强好几倍。

因为面试过程看重的不仅是你的实习经历多久怎样,更多的是看重你对基础知识的掌握(即学习能力和逻辑),实际项目中解决问题的能力(做了什么贡献)。


先提一下奥卡姆剃刀:给定两个具有相同泛化误差的模型,较简单的模型比较复杂的模型更可取。以免模型过于复杂,出现过拟合的问题。

如果你想面数据挖掘岗必须先了解下面这部分的基本算法理论:

我们知道,在做数学题的时候,解未知数的方法,是给定自变量和函数,通过函数处理自变量,以获得解。而机器学习就相当于,给定自变量和函数的解,求函数。

类似于:这样:function(x)=y 机器学习就是样本中有大量的x(特征量)和y(目标变量)然后求这个function。(了解更多可以看: https://zhuanlan.zhihu.com/p/21340974?refer=mlearn

求函数的方法,基于理论上来说,大部分函数都能找到一个近似的泰勒展开式。而机器学习,就是用数据去拟合这个所谓的“近似的泰勒展开式”。


实际面试时很看重和考察你的理论基础,所以一定一定要重视各个算法推导过程中的细节问题。这里主要介绍:logistic回归,随机森林,GBDT和Adaboost

1.逻辑回归

逻辑回归从统计学的角度看属于非线性回归中的一种,它实际上是一种分类方法,主要用于两分类问题

Regression问题的常规步骤为: 寻找h函数(即假设估计的函数); 构造J函数(损失函数); 想办法使得J函数最小并求得回归参数(θ); 数据拟合问题

1)利用了Logistic函数(或称为Sigmoid函数),函数形式为最常见的

1.png

2)代价函数J 下面的代价函数J之所有前面加上1/m是为了后面”梯度下降求参数θ时更方便“,也即这里不加1/m也可以。

2.png

3.png

4.png

5.png

3)使得J函数最小并求得回归参数(θ) 如何调整θ以使得J(θ)取得最小值有很多方法,比如最小二乘法,梯度下降也是一种,这里介绍一下梯度下降。

梯度下降是最基础的一个优化算法,学习因子就是梯度下降里的学习率,一个参数。

梯度方向表示了函数增长速度最快的方向,那么和它相反的方向就是函数减少速度最快的方向了。对于机器学习模型优化的问题,当我们需要求解最小值的时候,朝着梯度下降的方向走,就能找到最优值了。

学习因子即步长α的选择对梯度下降算法来说很重要,α过小会导致收敛太慢;若α太大,可能跳过最优,从而找不到最优解。

1)当梯度下降到一定数值后,每次迭代的变化很小,这时可以设定一个阈值,**只要变化小于该阈值,就停止迭代,而得到的结果也近似于最优解。**
2)若损失函数的值不断变大,则有可能是步长速率a太大,导致算法不收敛,这时可适当调整a值

对于样本数量额非常之多的情况,普通的**批量梯度下降**算法(Batch gradient descent )会非常耗时,靠近极小值时收敛速度减慢,因为每次迭代都要便利所有样本,这时可以选择**随机梯度下降算法**(Stochastic gradient descent)梯度下降**需要把m个样本全部带入计算**,迭代一次计算量为m\\*n^2;随机梯度下降每次只使用一个样本,迭代一次计算量为n^2,当m很大的时候,随机梯度下降迭代一次的速度要远高于梯度下降,虽然不是每次迭代得到的损失函数都向着全局最优方向,** 但是大的整体的方向是向全局最优解的,最终的结果往往是在全局最优解附近。**

6.png

4)数据的拟合问题 第一种是欠拟合,通常是因为特征量选少了。 第二种是我们想要的。 第三个是过拟合,通常是因为特征量选多了。

欠拟合的解决方法是增加特征量。 过拟合的解决方法是减少特征量或者正则化。

但是一般情况下我们又不能确定哪些特征量该去掉,所以我们就选择正则化的方式解决过拟合。

7.png

2.决策树

决策树这种算法有着很多良好的特性,比如说训练时间复杂度较低,预测的过程比较快速,模型容易展示。单决策树又有一些不好的地方,比如说容易over-fitting

这里首先介绍如何构造决策树: (1)如何分割某一结点,方法有很多,分别针对二元属性、序数属性、连续属性等进行划分。 (2)在有多个特征时,如何确定最佳的分割特征。 这里就涉及到纯度的概念,若分割后的子结点都更偏向于一个类,那么纯度越高。

实际中我们通常对不纯度进行度量,即不纯度越小,则认为该特征的区分度越高。 不纯度的度量方式有三种:

8.png

具体的计算方法如下:

9.png

10.png

上图10中得到多个子结点M1,M2的GINI或者熵后,一般通过加权平均的方法求M12;

那么增益就可以用M0-M12来表示

在决策树算法中,通过比较划分前后的不纯度值,来确定如何分裂。ID3使用信息增益作为不纯度,C4.5使用信息增益比作为不纯度,CART使用基尼指数作为不纯度。

  • 信息增益为:父结点与所有子结点不纯程度的差值,差越大,则增益越大,表示特征的效果越好。
  • 有时候并不是分割的越多越好,如果某个特征产生了大量的划分,它的划分信息将会很大,此时采用信息增益率 以ID3为例,使用训练样本建立决策树时,在每一个内部节点依据信息论来评估选择哪一个属性作为分割 的依据。对于过拟合的问题,一般要对决策树进行剪枝,剪枝有两种方法:先剪枝,后剪枝。 先剪枝说白了就是提前结束决策树的增长,跟上述决策树停止生长的方法一样。 后剪枝是指在决策树生长完成之后再进行剪枝的过程。

(3)何时停止划分。

11.png

3.随机森林

随机森林是一个包含多个决策树的分类器,构建过程如下: 1)决策树相当于一个大师,通过自己在数据集中学到的知识对于新的数据进行分类。但是俗话说得好,一个诸葛亮,玩不过三个臭皮匠。随机森林就是希望构建多个臭皮匠,希望最终的分类效果能够超过单个大师的一种算法。

2)那随机森林具体如何构建呢?有两个方面:数据的随机性选取,以及待选特征的随机选取。

  • 数据的随机选取: 第一,从原始的数据集中采取有放回的抽样,构造子数据集,子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复,同一个子数据集中的元素也可以重复。 第二,利用子数据集来构建子决策树,将这个数据放到每个子决策树中,每个子决策树输出一个结果。最后,如果有了新的数据需要通过随机森林得到分类结果,就可以通过对子决策树的判断结果的投票,得到随机森林的输出结果了。如下图,假设随机森林中有3棵子决策树,2棵子树的分类结果是A类,1棵子树的分类结果是B类,那么随机森林的分类结果就是A类。

12.png

  • 待选特征的随机选取: 与数据集的随机选取类似,随机森林中的子树的每一个分裂过程并未用到所有的待选特征,而是从所有的待选特征中随机选取一定的特征,之后再在随机选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同,提升系统的多样性,从而提升分类性能。

此外,以决策树为基函数的提升方法称为提升树(boosting tree),包括GBDT,xgboost,adaboost,这里只主要介绍GBDT和xgboost。

先说说bootstrap, bagging,boosting 的含义。 Bootstrap是一种有放回的抽样方法思想。

该思想的应用有两方面:bagging和boosting 虽然都是有放回的抽样,但二者的区别在于:Bagging采用有放回的均匀取样,而Boosting根据错误率来取样(Boosting初始化时对每一个训练例赋相等的权重1/n,然后用该学算法对训练集训练t轮,每次训练后,对训练失败的训练例赋以较大的权重),因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的,各轮训练集之间相互独立,而Boostlng的各轮训练集的选择与前面各轮的学习结果有关。

4.GBDT(Gradient Boost Decision Tree 梯度提升决策树)

GBDT是以决策树(CART)为基学习器的GB算法,是迭代树,而不是分类树。 Boost是"提升"的意思,一般Boosting算法都是一个迭代的过程,每一次新的训练都是为了改进上一次的结果。

GBDT的核心就在于:每一棵树学的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁,但第一棵树的预测年龄是12岁,差了6岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁,继续学习。

13.png

14.png

5.xgboost

xgboos也是以(CART)为基学习器的GB算法**,但是扩展和改进了GDBT。相比GBDT的优点有:

(1)xgboost在代价函数里自带加入了正则项,用于控制模型的复杂度。

(2)xgboost在进行节点的分裂时,支持各个特征多线程进行增益计算,因此算法更快,准确率也相对高一些。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2017-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

人脸识别技术大总结1——Face Detection &Alignment

2365
来自专栏Duncan's Blog

记录几个经典模型

2.1 gbdt 的算法的流程? gbdt通过多轮迭代,每轮迭代生成一个弱分类器,每个分类器在上一轮分类器的残差基础上进行训练.(弱分类器一般会选择CART T...

1592
来自专栏AI科技大本营的专栏

干货 | 上手机器学习,从搞懂这十大经典算法开始

翻译 | AI科技大本营(rgznai100) 参与 | 林椿眄 编辑 | 波波,Donna 在机器学习领域,“没有免费的午餐”是一个不变的定理。简而言之,没有...

37210
来自专栏大数据文摘

斯坦福CS231N深度学习与计算机视觉第七弹:神经网络数据预处理,正则化与损失函数

2062
来自专栏大数据挖掘DT机器学习

隐马尔可夫模型攻略

隐马尔可夫模型 (Hidden Markov Model,HMM) 最初由 L. E. Baum 和其它一些学者发表在一系列的统计学论文中,随后在语言识别,自然...

36811
来自专栏AI科技评论

深度学习元老Yann Lecun详解卷积神经网络(30页干货PPT)

雷锋网注:卷积神经网络(Convolutional Neural Network)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型...

4839
来自专栏木东居士的专栏

漫谈机器学习之过拟合

1614
来自专栏数据派THU

一文读懂生成对抗网络GANs

原文标题:AnIntuitive Introduction to Generative Adversarial Networks 作者:KeshavDhandh...

3293
来自专栏PPV课数据科学社区

机器学习常见的算法面试题总结

摘要:包含机器学习常见算法公式、原理和优缺点比较,简介清洗,适合作为面试和考试前速查和记忆使用。 朴素贝叶斯 P(A∩B)=P(A)*P(B|A)=P(B)*P...

1.1K5
来自专栏红色石头的机器学习之路

台湾大学林轩田机器学习技法课程学习笔记1 -- Linear Support Vector Machine

关于台湾大学林轩田老师的《机器学习基石》课程,我们已经总结了16节课的笔记。这里附上基石第一节课的博客地址: 台湾大学林轩田机器学习基石课程学习笔记1 – Th...

2600

扫码关注云+社区

领取腾讯云代金券