在茫茫决策树入门帖里，强推这篇！
介绍
数据样本
决策树的算法步骤
数学表示
由上图可以得到每个叶子节点都落有样本,该决策树是一种由根至叶的算法, 其中每个叶子节点需要通过贪心算法进行划分最优属性,使得每一个的”纯度“更高,其中纯度的度量方式有一下几种
信息增益 "ID3"
:原先信息熵
: 给定 后的信息熵
以上图为例我们可以计算当前的信息增益为:
假设:一种有8个好瓜,9个坏瓜. 则原先信息熵:
计算在给定特征下信息熵增益最大的是纹理具体计算步骤如下:
一共17个样本, 9个清晰纹理(2个坏瓜,7个好瓜),5个稍糊(1个好瓜,4个坏瓜),3个模糊(3个坏瓜)
纹理
信息增益比 "C4.5"
由上述可以得到: Gain(D,纹理) = 0.381, 一共17个样本, 9个清晰纹理(2个坏瓜,7个好瓜),5个稍糊(1个好瓜,4个坏瓜),3个模糊(3个坏瓜)\hspace{4cm}
纹理
纹理纹理纹理
分类回归树 "CART"(基尼系数)
由上述可以得到: 一种有8个好瓜,9个坏瓜 \ \ \ \
一共17个样本, 9个清晰纹理(2个坏瓜,7个好瓜),5个稍糊(1个好瓜,4个坏瓜),3个模糊(3个坏瓜)
纹理清晰
稍糊模糊
稍糊
纹理清晰模糊
模糊
稍糊纹理清晰
Gini_{纹理}(D)_{max} = Gini(稍糊\&模糊)&Gini(纹理清晰) = 0.502-0.302=0.2
假设我们对所有的特征进行尝试寻找全局最优解,时间的复杂度比较高为: 2^p
信息增益的表达式用泰勒一阶展开后和Gini指数的表达式相等
将在x=1处进行一阶泰勒展开 $f(x = f(x_0)+f'(x_0)(x-x_0) = f(1)+f'(1)(x-1)=1-x$
减缓决策树过拟合的方法:
集成模型例如:随机森林
设置树的最大深度
当叶节点里的样本个数少于阈值的时候停止分裂
具体阈值选择取决于交叉验证的结果
决策树缺失值处理
删除特征
高概率估计
对含有缺失值的样本添加权重
决策树的不同指标
信息增益 :ID3
增益率: C4.5
基尼指数: CART
决策树的应用
标准差(std)作为最后的目标函数
使用交叉熵作为最后的目标函数
分类树
回归树
决策树集成算法(dropout 也是一种集成算法)
Bagging算法特点
Boosting 算法特点
Random forest
Adaboost
每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
根据错误率不断调整样例的权值，错误率越大则权重越大
每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
使用均匀取样，每个样例的权重相等
所有预测函数的权重相等。
各个预测函数可以并行生成
简介
推导:
加法模型
: 是每个基函数的系数
: 是每个基函数的参数
: 就是一个基函数了
前向分步算法
可见最终分类器是一个加法模型,所以每当增加一个基分类器时候,都会使得分类结果逼近真实
结果. 也就是说每次计算损失点时候只需要考虑当前基分类器的系数和参数, 不受之前分类器点影响
指数损失函数
步骤
根据前向分步算法求的最小值只需求α和G即可;由于当G和y的取指只能是-1或者+1.所以对上式子进行改写
``` 所以对α进行求导, 得出 决策树权重α的值, 错误率e的值, 抽样权重w样本的值, 归一化Z的值.
构建最终的分类器
简介
计算过程
GBDT
GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，从名字中我们可以看出来它是属于 Boosting 策略。GBDT 是被公认的泛化能力较强的算法。
推导:
加法模型(与上同理)
前向分步算法(与上同理)
指数损失函数(可以自定义)
最后式子写为(也就是模型沿着负度方向优化)
- 计算步骤
XGboost
首先XGboost是Gradient Boosting的一种高效系统实现，并不是一种单一算法。XGboost里面的基学习器除了用tree(gbtree)，也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。
将树模型的复杂度作为正则项加在优化目标
使用到了二阶导数使得损失函数更具有扩展性,并且加速收敛,类似牛顿法比SGD收敛更快。一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化
允许使用column(feature) sampling来防止过拟合
使用一种分裂节点寻找的近似算法，用于加速和减小内存消耗
节点分裂算法能自动利用特征的稀疏性
data事先排好序并以block的形式存储，利于并行计算
支持分布式计算可以运行在MPI，YARN上，得益于底层支持容错的分布式通信框架rabit。
相比GBDT改进了什么
特点
lightGBM
LightGBM使用基于直方图的算法。例如，它将连续的特征值分桶(buckets)装进离散的箱子(bins)，这是的训练过程中变得更快
更低的内存占用：使用离散的箱子(bins)保存并替换连续值导致更少的内存
更高的准确率(相比于其他任何提升算法) : 它通过leaf-wise分裂方法产生比level-wise分裂方法更复杂的树，这就是实现更高准确率的主要因素。然而，它有时候或导致过拟合，但是我们可以通过设置 max-depth 参数来防止过拟合的发生
大数据处理能力
支持并行学习
相比XGboost改进了什么
catboost
catboost 处理特征为分类的神器，你用ligtbgm或者XGboost在处理具有大量分类特征的时候，独热编码不好用，因为你一个特征就有上千个分类，每个都独热，效果特别差，好的方法是每个分类用均值编码，这种容易过拟合，catboost 设计了一种算法验证改进，避免了过拟合。因此处理分类数据应该比lightgbm 和XGboost 强很多，我观察在处理分类数据中一般会有很大提升(未调参)。
特点
参考
Bagging和Boosting 概念及区别
一文弄懂AdaBoost、提升树、残差树、GDBT
Adaboost, GBDT 与 XGBoost 的区别``
转载https://mp.weixin.qq.com/s/uY4FNkjRnutfoYBMrEaFfg
欢迎学习更多相关知识：
