0. 相关基础概念
0.1 熵(entropy)和条件熵
又被称为信息熵、信源熵、平均自信息量。熵的单位通常为比特，但也用Sh、nat、Hart计量，取决于定义用到对数的底。
熵最好理解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大，其包含的信息量越大。
熵的本质是香浓信息量(
)的期望：
在这里b是对数所使用的底，通常是2,自然常数e，或是10。当b = 2，熵的单位是bit；当b = e，熵的单位是nat；而当b = 10,熵的单位是Hart。
抛硬币的熵H(X)（即期望自信息），以比特度量，与之相对的是硬币的公正度Pr(X=1)。
注意图的最大值取决于分布；在这里，要传达一个公正的抛硬币结果至多需要1比特，但要传达一个公正的抛骰子结果至多需要log2(6)比特。
当所有符号有同等机会出现的情况下，熵达到最大值（所有可能的事件同等概率时不确定性最高）：
熵只依赖X的分布，和X的取值没有关系，所以树形结构用到熵来进行特征选择，所以无需归一化操作。
等概率事件的熵应随符号的数量增加：
为变量
在变量
取特定值
条件下的熵，即
就是
在
取遍所有可能的
后取平均的结果：
0.2 信息增益(Information gain)和信息增益比
信息增益(Information gain)，即待分类的集合的熵和选定某个特征的条件熵之差：
用信息增益作为判别标准时，会存在偏向于选择取值较多的特征的问题，为了避免这个问题，可以在信息增益的基础上除以一个惩罚参数，惩罚参数是训练数据集 D 关于特征 A 的值的熵：
这里要注意
与
计算方法的区别，
是把集合类别作为随机变量，计算数据集关于类别的熵，
现在把
特征作为随机变量，按照此特征的特征取值对集合D进行划分，计算数据集关于该特征的熵。
下面给出信息增益和信息增益比计算的具体例子，以便更好的理解他们：
比如我们有15个样本D，输出为0或者1。其中有9个输出为1， 6个输出为0。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0.
为什么信息增益偏向于选择取值较多的特征? 极限情况下，每个特征值都独立的情况下，计算信息增益后半部分的条件熵为0，信息增益最大，不太符和现实，所以引入计算信息增益率的分母来为划分行为带来的信息。 https://www.zhihu.com/question/22928442
0.3 基尼(Gini)系数
Gini系数是一种与信息熵类似的做特征选择的方式，可以用来数据的不纯度。具体的，在分类问题中，假设有K个类别，第k个类别的概率为𝑝𝑘, 则基尼系数的表达式为：
为啥基尼系数可以近似替代熵的效果，从而简化计算？
从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。此外可以从另一角度分析，熵的运算在x=1处的一阶泰勒公式展开即为基尼指数：
0.3 相对熵和交叉熵
相对熵，又称为KL散度，是一种量化两种概率分布P和Q之间差异的方式。
度量使用一个分布来近似另一个分布时所损失的信息量。
设p为观察得到的概率分布，q为另一分布来近似p，则p、q的K-L散度为：
显然，根据上面的公式，K-L散度其实是数据的原始分布p和近似分布q之间的对数差值的期望。其中，公式的后半部分即为交叉熵：
交叉熵常常在机器学习中用作损失函数p(x)表示真实标记的分布，q(x)表示训练后模型预测的分布。机器学习的目的就是希望q(x)尽可能地逼近甚至等于p(x) ，从而使得相对熵接近最小值0. 由于真实的概率分布是固定的，相对熵公式的前半部分就成了一个常数。那么相对熵达到最小值的时候，也意味着交叉熵达到了最小值。对q(x)的优化就等效于求交叉熵的最小值。最常见的就是LR模型的损失函数。
1. DT
决策树学习通常包括3个步骤：
- 特征选择
- 决策树生成
- 剪枝
决策树生成过程：
- 构建根结点：将所有训练数据放在根结点。
- 选择一个最优特征，根据这个特征将训练数据分割成子集，使得各个子集有一个在当前条件下最好的分类。
- f若这些子集已能够被基本正确分类，则将该子集构成叶结点。
- 若某个子集不能够被基本正确分类，则对该子集选择新的最优的特征，继续对该子集进行分割，构建相应的结点。
- 如此递归下去，直至所有训练数据子集都被基本正确分类，或者没有合适的特征为止。
生成后剪枝以防止过拟合，即去掉过于细分的叶结点，使得该叶结点中的子集回退到父结点或更高层次的结点并让其成为叶结点。决策树的生成对应着模型的局部最优，决策树的剪枝则考虑全局最优。
如果学习任意大小的决策树，则可以将决策树算法视作非参数算法。但是实践中经常有大小限制（如限制树的高度、限制树的叶结点数量），从而使得决策树成为有参数模型。
1.1 ID3和C4.5算法
决策树的两种常用生成算法。
ID3算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。
- 从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。
- 再对子结点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树
- 如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。
ID3伪代码：
C4.5算法与ID3算法类似，只是生成过程中用信息增益比来选择特征。
C4.5较ID3的改进：
能够处理连续特征
C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为𝑎1,𝑎2,…,𝑎𝑚,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点𝑇𝑖表示为：𝑇𝑖=(𝑎𝑖+𝑎𝑖+1)/2。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为𝑎𝑡,则小于𝑎𝑡的值为类别1，大于𝑎𝑡的值为类别2，这样我们就做到了连续特征的离散化。 要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
优化特征选择方式。
通过信息增益比代替信息增益来选择特征。
能够处理缺失值。
这里需要注意，缺失值处理和缺失值填充不是一个事情，缺失值处理并没有对缺失值进行填充，它指的是该算法可以对缺失值具有良好的兼容性，在某一步处理完缺失值后，该缺失值仍然存在，即不改变原来数据的特征情况；而缺失值填充改变了原始特征情况，所以属于特征工程。
缺失值处理分两种情况：
- 一种是在特征选择划分时遇到特征值缺失时该如何处理？
对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
- 另一种是在给定划分属性后，若样本在该属性上的值缺失，如何对样本进行划分？
可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
- 一定程度解决过拟合问题
C4.5引入了正则化系数进行初步的剪枝。
1.2 CART树
CART(classfification and regression tree)，即分类回归树。
CART采用基尼系数来简化代替熵的运算，此外，CART树是二叉树，回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{𝐴1}和{𝐴2,𝐴3}, {𝐴2}和{𝐴1,𝐴3}, {𝐴3}和{𝐴1,𝐴2}三种情况，找到基尼系数最小的组合，比如{𝐴2}和{𝐴1,𝐴3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。
CART为什么是二叉树的形式？ 这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。
下面主要阐述一下CART回归树的原理：
下面举个具体例子，便于理解。现有5个训练样本，每个样本有三个特征，具体取值情况如下。这里的情况，我们取特征A为切分特征，随后进一步取特征A取值中的0.3为切分点，则数据集会被划分成如下两部分，这就是上述所说的切分特征和切分点两个重要概念。
也就是说，在寻找最优切分点时，
可以替换为该特征在所有训练样本上的取值的平均值。
CART回归树和CART分类树的建立和预测的区别主要有下面两点：
- 连续值的处理方法不同
CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为：
其中，𝑐1为D1数据集的样本输出均值，𝑐2为D2数据集的样本输出均值。
- 决策树建立后做预测的方式不同。
CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。
1.3 剪枝
- 决策树的剪枝是从已生成的树上裁掉一些子树或者叶结点，并将根结点或者其父结点作为新的叶结点。
- 剪枝的依据是：极小化决策树的整体损失函数或者代价函数。
- 决策树生成算法是学习局部的模型，决策树剪枝是学习整体的模型。即：生成算法仅考虑局部最优，而剪枝算法考虑全局最优。
剪枝分为预剪枝和后剪枝。
预剪枝：就是在构建决策树的时候提前停止。比如指定树的深度最大为3，那么训练出来决策树的高度就是3,预剪枝主要是建立某些规则限制决策树的生长，降低了过拟合的风险，降低了建树的时间，但是有可能带来欠拟合问题。 后剪枝：后剪枝是一种全局的优化方法，在决策树构建好之后，然后才开始进行剪枝。后剪枝的过程就是删除一些子树，这个叶子节点的标识类别通过大多数原则来确定，即属于这个叶子节点下大多数样本所属的类别就是该叶子节点的标识。选择减掉哪些子树时，可以计算没有减掉子树之前的误差和减掉子树之后的误差，如果相差不大，可以将子树减掉。一般使用后剪枝得到的结果比较好。
后剪枝算法思想：
伪代码：
CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。
2. Ensemble Learning
将多个基算法模型通过某种方式组合起来，形成一个效果更好的预测结果。
2.1 Bagging
- 各弱学习器并行(互不影响)，综合做出最终决策；
- 对原始数据及进行有放回随机采样；
一般会随机采集和训练集样本数m一样个数的样本，对于一个样本，它在某一次含m个样本的训练集的随机采样中，每次被采集到的概率是1/m。不被采集到的概率为1−1/m。如果m次采样都没有被采集中的概率是(1−1/m)^m。当m→∞m→∞时,(1−1/m)^m→ 1/e≃0.368。也就是说，在bagging每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。
- 分类一般采取投票法决策；回归一般采取平均法决策；
- bagging能够降低弱分类器的方差，所以在选择弱分类器时偏向于低偏差该方差的模型
2.2 Boosting
- 各弱学习器串行，后一学习器基于前一学习器的结果对转换后的数据集进行训练；
- boosting能够降低模型的偏差，所以选择弱分类器时偏向于高偏差低方差的模型。
2.3 Stacking
stacking一般分为两层：
- 第一层采用不同的基学习器，对数据集进行k折交叉验证。
各个基分类器要“准而不同”，可以是不同参数的相同模型，也可以是完全不同的模型。
- 第二层采用一个学习器，以第一层输出作为特征进行训练(类似于神经网络)。
为了防止过拟合，一般第二层的模型不再使用原始训练数据进行训练，而仅依赖于第一层训练器的输出结果。
3. 随机森林RF(Random Forest)
理解了bagging算法，随机森林(Random Forest,以下简称RF)就好理解了。它是Bagging算法的进化版，也就是说，它的思想仍然是bagging,但是进行了独有的改进。
- RF使用了CART决策树作为弱学习器。
- RF通过随机选择节点上的一部分样本特征，进一步增强了模型的泛化能力。
RF算法伪代码：
输入为样本集D={(x1,y1),(x2,y2),…(xm,ym)}，弱分类器迭代次数T。输出为最终的强分类器f(x)。
- 对于t=1,2…,T:
a)对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集Dm b)用采样集Dm训练第m个决策树模型Gm(x)，在训练决策树模型的节点的时候， 在节点上所有的样本特征中选择一部分样本特征，在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分。
- 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。
RF的优点：
- 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。
- 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
- 在训练后，可以给出各个特征对于输出的重要性。用作树中决策节点的特征的相对等级（即深度）可用于评估该特征相对于目标变量的可预测性的相对重要性。 在树的顶部使用的特征有助于更大比例的输入样本的最终预测决策。
- 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
- 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。
- 对部分特征缺失不敏感。 ???
RF的缺点： ???
在某些噪音比较大的样本集上，RF模型容易陷入过拟合。 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。
4. Adaboost(Adaptive Boosting)
4.1 Adaboost简介
- 根据前一弱分类器的误差得到该弱分类器权重α，并进一步得到更新后的样本权重D
- 弱分类器的误差即为错分类样本的权重之和
4.2 训练误差边界
4.3 前向分步加法模型与Adaboost
AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的学习方法。根据前向分步算法可以推导出AdaBoost，用一句话叙述这一关系：AdaBoost算法是前向分步加法算法的特例。此时，模型是由基本分类器组成的加法模型，损失函数是指数函数。
3.3.1 加法模型(addtive model)
3.3.2 前向分步算法
在给定训练数据及损失函数L(y,f(x))的条件下，学习加法模型f(x)成为经验风险极小化即损失函数极小化的问题：
通常这是一个复杂的优化问题。前向分布算法（forward stagwise algorithm）求解这一优化问题的思路是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式(ml.1.6.1)，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
这样前向分步算法将同时求解从k=1到K的所有参数βk,γk的优化问题简化为逐次求解各个βk,γk的优化问题。
3.3.3 证明
证明：前向分步算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器：
由基本分类器Gk(x)及其系数αk组成，k=1,2,⋯,K。前向分步算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基本分类器的过程一致。
3.4 AdaBoost算法缺点
对异常点敏感
指数损失存在的一个问题是不断增加误分类样本的权重（指数上升）。如果数据样本是异常点（outlier），会极大的干扰后面基本分类器学习效果；
模型无法用于概率估计
意思就是说对于取值为ỹ ∈{−1,+1}的随机变量来说，e−ỹ f不是任何概率密度函数的对数形式，模型f(x)的结果无法用概率解释。
5. GBDT
AdaBoost 是通过提升错分数据点的权重来定位模型的不足而 Gradient Boosting 是通过算梯度（gradient）来定位模型的不足。因此相比 AdaBoost, Gradient Boosting 可以使用更多种类的目标函数。
举个形象点的例子就是，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最终将所有拟合后的模型结果相加就会得到一个较好的结果。
4.1 提升树(Boosting Tree)
由于损失函数是平方损失，因此该方法属于L2Boosting的一种实现。
用回归树拟合残差实际上就是用回归树拟合负梯度（当损失函数不为square loss时残差并不一定等于负梯度）。我们实际上是在通过梯度下降法对模型参数进行更新。这样理解的好处在于我们可以把这一算法推广到其它的损失函数上。
4.2 梯度提升树(Gradient Boosting)
AdaBoost 是通过提升错分数据点的权重来定位模型的不足而 Gradient Boosting 是通过算梯度（gradient）来定位模型的不足。因此相比 AdaBoost, Gradient Boosting 可以使用更多种类的目标函数。
用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
两者的不同主要在于每步迭代时，是否使用Gradient作为求解方法。前者不用Gradient而是用残差—-残差是全局最优值，Gradient是局部最优方向*步长，即前者每一步都在试图让结果变成最好，后者则每步试图让结果更好一点。 两者优缺点。看起来前者更科学一点–有绝对最优方向不学，为什么舍近求远去估计一个局部最优方向呢？原因在于灵活性。前者最大问题是，由于它依赖残差，cost function一般固定为反映残差的均方差，因此很难处理纯回归问题之外的问题。而后者求解方法为梯度下降，只要可求导的cost function都可以使用。 残差版本只是GBDT损失函数是平方误差时候的一种特例（对平方误差求导，就是残差），因为平方误差对异常值比较敏感，所以一般用的比较少
4.3 GBDT回归算法
GBDT并不一定总是好于线性回归或逻辑回归。根据没有免费的午餐原则，没有一个算法是在所有问题上都能好于另一个算法的。根据奥卡姆剃刀原则，如果GBDT和线性回归或逻辑回归在某个问题上表现接近，那么我们应该选择相对比较简单的线性回归或逻辑回归。具体选择哪一个算法还是要根据实际问题来决定。
4.4 GBDT分类算法
GBDT处理分类问题比较特殊，由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法：
- 用指数损失函数，此时GBDT退化为Adaboost算法。
- 用类似于逻辑回归的对数似然损失函数的方法，即用类别的预测概率值和真实概率值的差来拟合损失。
4.5 GBDT常用损失函数
对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种：
4.6 GBDT正则化
4.7 GBDT优缺点
优点：
- 可以灵活处理各种类型的数据，包括连续值和离散值。
- 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
- 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
缺点
由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
6. XGBoost
- 采用二阶梯度(相对于GBDT的一阶梯度)，能更快更准确的优化目标；
- 采用正则化(替代剪枝)，并采用列采样(借鉴于RF)和权值缩放，以防止过拟合；
- 采用近似算法寻找最优分裂点(相对于精确贪婪算法)，进行预排序操作，利用样本在损失函数上面的二阶梯度作为权值。
- 兼容稀疏数据：对于缺失值将其划分为默认分支(默认分支算法根据无缺失值数据训练得出)
- 在特征粒度上并行化处理(树粒度上无法并行，因为本质还是boosting方法)
- 系统设计上的一些trick：缓存处理能力优化和数据块以外的算力提升
参考文献
- 决策树算法原理
- 决策树
- c4.5为什么使用信息增益比来选择特征？
- 机器学习笔记十二：分类与回归树CART
- MachineLearningNote
- treelib
- Bagging与随机森林算法原理小结
- 集成学习原理小结
- 集成学习之Adaboost算法原理小结
- 为什么做stacking之后，准确率反而降低了？
- Adaboost, GBDT 与 XGBoost 的区别
- 深入浅出ML之Boosting家族
- A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting(Adaboost原论文)
- XGBoost: A Scalable Tree Boosting System(XGBoost原论文)
- GBDT与Adaboost的区别与联系
若有收获，就点个赞吧
0 人点赞
