1 相关概念
1.1 信息熵
信息熵时用来哦衡量信息不确定性的指标，不确定性时一个时间出现不同结果的可能性。
其中：P(X=i)为随机变量x取值为i的概率
### 1.2 条件熵
条件熵：再给定随机变量Y的条件下，随机变量X的不确定性
1.3 信息增益
信息增益：熵-条件熵。代表了在一个条件下，信息不确定性减少的程度。
1.4 基尼指数
基尼指数：又称为Gini不纯度，表示在样本集合中一个随机选中的样本杯分错的概率。
注意：Gini指数越小表示集合中被选中的样本被分错的概率越小，也就说集合的纯度越高，反之，集合越不纯。当集合中所有样本为一个类时，基尼指数为0。
其中pk表示选中的样本属于第k个类别的概率。
### 1.5 集成学习
集成学习是通过构建并组合多个学习器来完成学习任务的算法，集成学习常用的有两类：
Bagging：基学习器之间无强依赖关系，可同时生成的并行化方法
Boosting：基学习器之间存在强烈的依赖关系，必须穿行生成基分类器的方法
（1）Bagging（Bootstrap Aggregating）算法
N个弱学习器，每个学习器的训练数据，来自于原始数据中的随机采样的部分数据。训练模型后，预测新数据。在分类问题中，选择多N个学习器的预测结果中的众数（即，投票方法）作为最终的预测结果。在回归问题中，选择多N个学习器的预测结果中的平均值作为最终的预测结果。
（2）Boosting算法
是将弱学算法提升为强学习算法的过程，通过反复学习得到一系列弱分类器（决策树和逻辑回归）组合这些弱分类器得到一个强分类器。Boosting算法要涉及到两个部分，加法模型和前向分布算法。
加法模型：强分类器由一系列弱分类器线性相加而成。一般组合形式如下：
2 随机森林
（1）概念
随机森林 = Bagging+决策树
同时训练多个决策树，预测试综合考虑多个结果进行预测，例如取多个节点的均值（回归问题），或者众数（分类）。
（2）优缺点
优点
- 它可以出来很高维度（特征很多）的数据，并且不用降维，无需做特征选择
- 它可以判断特征的重要程度
- 可以判断出不同特征之间的相互影响
- 消除了决策树容易过拟合的缺点
- 减小了预测的方差，预测值不会因训练数据的小变化而剧烈变化
- 训练速度比较快，容易做成并行方法
- 实现起来比较简单
- 对于不平衡的数据集来说，它可以平衡误差。
- 如果有很大一部分的特征遗失，仍可以维持准确度。
缺点
- 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
- 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的
（3）随机性体现在两点
- 从原来是训练数据集随机（带放回Boostrap）取一个子集，作为森林中某一个决策树的训练数据集
- 每一次选择分叉的特征时，限定为在随机选择的特征的子集中寻找一个特征
3 AdaBoost
（1）概念
AdaBoost的思想时将关注点放在被错误分类的样本上，减小上一轮被正确分类的样本权值，提高被错误分类的样本权值。
Adaboost采用加权投票的方法，分类误差小的弱分类器的权重大，而分类误差大的弱分类器的权重小。
（2）算法过程
假设输入的训练数据为：
迭代次数即弱分类器个数M
1. 初始化训练样本的权值分布为
3. 得到最终的分类器为：
4 GBDT
（1）BDT提升树概念
BDT提升树：是以CART决策树为基学习器的集成学习方法。实际上就是加法模型和前向分布算法
（2）提升树算法
（3）GBDT算法概念
GBDT（Gradient Boosting Decision Tree）梯度提升决策树，理解为梯度提升+决策树。利用最速下降的近似方法，利用损失函数的负梯度拟合基学习器。
所以在GBDT中使用负梯度替代BDT中的残差进行拟合
（4）GBDT的梯度提升过程
（5）GBDT是算法过程图
每次更新梯度让下一个弱学习器来学习。
（6）回归问题中，GBDT算法过程
基学习器是CART回归树，CART回归树是将空间内划分为K个不相交的区域，并确定每个区域的输出ck，数学表达式如下：
则GBDT应用到回归问题的算法过程如下
（7）分类问题中，GBDT仍然使用CART回归树作为基学习器，使用Softmax进行概率的映射，然后对概率的残差进行拟合。所以算法过程如下。
（8）举例理解
GDBT在三个类别的分类问题中
5 XGBoost
------------------------------------------------------------------------
（1）基本基本概念
XGBoost是GBDT的一种，也是加法模型和前向优化算法。
在监督学习中，可以分为：模型，参数，目标函数和学习方法。
模型：给定输入x后预测输出y的方法，比如说回归，分类，排序等 参数：模型中的参数，比如线性回归中的权重和偏置
目标函数：即损失函数，包含正则化项 学习方法：给定目标函数后求解模型和参数的方法，比如：梯度下降法，数学推导等。
这四个方面的内容，也指导着XBGBoost系统的设计。
（2）XGB的模型形式
给定数据集
（2）XGB的目标函数
定义目标函数，包含正则项
在t轮时，前t-1次迭代，正则项看作是常熟，即constant表示。
要求解以上局部最优解，引入泰勒展开式。
接下来采用泰勒展开对目标参数进行近似：
所以目标函数只依赖每条数据在误差函数的一阶导数和二阶导数。
XGB中正则项用来表示树的复杂度：树的叶子节点个数T和每棵树的叶子节点输出分数W的平方和（相当于L2正则化）
其中T为叶子节点个数，ω j为叶节点的输出，λ是常熟。
则目标函数改写为
上面式子中第一部分是对样本的累加，而后面部分是正则项，即对叶子节点的累加。
定义q函数将输入x映射到某个叶子节点上，则有：
则目标函数进一步改写为：
得到最终的目标函数。
（3）优化目标函数
接下来我们继续目标函数的优化，即计算第t轮时使得目标函数最小的叶节点的输出分数w。直接对w求导，使得导数为0，得到
将其带入损失函数中，得到损失函数
（4）计算目标函数的例子
（5）XGBoost的学习策略
采用贪心算法，每次尝试分裂一个叶节点，计算分裂后的增益，选择增益最大的，类似于ID3中的信息增益，和CART树中 基尼指数。那XGB中怎么计算增益呢？损失函数是
Gain值越大，说明分裂后能使目标函数减小的越多，也就是越好。
一般树结构的及确定，初期采用精确贪心算法，就像CART树一样，枚举所有的特征和特征值，计算树的分裂方式。
但精确贪心算法优缺点，当数据量庞大，无法全部存入内存中，精确算法就很慢，因此引入近似算法。根据特征k的分布确定l个候选切分点 S k = { s k 1 , s k 2 , . . . , s k l } S_k = \{s_{k1},s_{k2},...,s_{kl}\} Sk\={sk1,sk2,...,skl}，然后根据候选切分点把相应的样本放入对应的桶中，对每个桶的G，H进行累加，在候选切分点集合上进行精确贪心查找。算法过程如下：
近似算法根据分位数给出对应的候选切分点，例子如下：
近似算法中如何选取切分点？全局策略和局部策略又是什么？
全局策略：学习每棵树前，提出候选的切分点，当切分点数足够多时，和精确的贪心算法性能相当。
局部策略：树节点分割时，重新提出候选切分点，切分点个数不需要那么多，性能与精确贪心算法差不多。
XGB并没有采用简单的分位数方法，而是提出以二阶梯度h为权重的分位数算法（Weighted Quantile Sketch），对特征k构造muti-set的数据集。
稀疏值处理：稀疏值产生的原因时，数据缺失值，大量的零值，One-hot编码。
XGB能对缺失值自动进行处理，思想是对于缺失值自动学习出它该划分的方向。简单来说，三个步骤：
第一步：将特征k的缺失值都放在右子树，枚举划分点，计算最大的增益
第二步：将特征k的缺失值都放在左子树，枚举划分点，计算最大的增益
第三步：最后求出最大增益，确定缺失值的划分
在XGB中加入了步长 η \eta η，也叫做收缩率Shrinkage:
这有助于防止过拟合，通常取值为0.1
列采用技术：一种是按层随机采样，另一种是按树随机采样（构建树前就随机选择特征）
按层随机方式：在每次分裂一个节点的时候，对同一层内的每一个节点分裂之间，先随机选择一部分特征，这时只需要遍历一部分特征，来确定最后分割点。
按树随机方式：即构建树结构前就随机选择特征，之后所有叶子节点的分裂都只只用这部分特征。
（6）XGB的系统设计
分块并行：在建树的过程中，最耗时的是找最优的切分点，而这个过程中，最耗时的部分是将数据排序。见了减少排序的时间，提出Block结构存储数据。 Block中的数据以稀疏格式CSC进行存储
Block中的特征进行排序（不对缺失值排序） Block中特征害需要存储指向样本的索引，这样才能根据特征的值来取梯度。
* 一个Block中存储一个或多个特征的值。
只需在建树前排序一次，后买你节点分裂时可以直接根据索引得到梯度信息。
缓存优化：使用Block结构的缺点时取梯度的时候，时通过索引来获取的额，而这些梯度的获取顺序时按照特征大小顺序的。这将导致非连续的内存访问，可能使CPU cache缓存命中率低，从而影响算法效率。
对于精确算法中，使用缓存预取。具体来说，对每个线程分配一个连续的Buffer，读取梯度信息并存入Buffer中（这样就实现了非连续到连续的转化），然后再统计梯度信息。该方式再训练样本数大的时候特别有用。
再近似算法中，对Block的大小进行了合理的设置。定义Block的大小为Block中最多的样本数。设置合适的大小时重要的，设置过大则容易导致命中率低，过小容易导致并行化效率不高。
Out of core Computation：当数据量太大不能全部不放入主内存的时候，为了使得out of core 计算称为可能，将数据划分为多个Block并存放在磁盘上。
计算的时候，使用独立的线程预先将Block放入主内存，因此可以在计算的同时读取磁盘。
Block压缩
Block Sharding，将数据划分到不同磁盘上，提高磁盘吞吐率
