学习目标

理解决策树的原理和实现，用于解决分类和回归问题。

笔记

1 决策树模型介绍

1.1 决策树构成

由根节点（root node）、左右分支（left and right branches）、内部节点和叶节点（leaf node）构成。内部节点表示一个特征，叶节点表示一个类。

1.2 决策树适用情况

1. 在结构化数据集上表现很好，但不推荐用于非结构化数据；
2. 训练速度非常快；
3. 小的决策树模型可以解释。

2 （分类）决策树的构建

2.1 熵

如果一类事物A混入了其他类别的事物（如事物B,C,…），就说事物A的分类是不纯的，混入的越多，越不纯。度量纯度的指标是熵（Entropy），用$H(p_i)$表示，i是类别。熵的取值范围是0到1，熵越大，越不纯。熵函数为：
$$H(p_1)=-p_1{\text{log}}_2(p_1)-(1-p_1){\text{log}}_2(1-p_1)$$
其中，令$0{\text{log}}_2(0)=0$。

2.2 信息增益

熵的减少被称为信息增益（Information Gain）,计算信息增益的公式是：
$$\text{Information Gain}=H(p_1^{\text{node}})-(w^{\text{left}}H(p_1^{\text{left}})+w^{\text{right}}H(p_1^{\text{right}}))$$
信息增益的计算帮助我们选择合适的特征来分割一个节点，能提供最大信息增益的特征被作为分割的节点。

2.3 构建整个决策树

1. 在根节点上，在整个训练集上计算所有特征的信息增益，将信息增益最大的特征作为下一个节点；
2. 按照当前特征分割训练集，创建树的左右分支；
3. 重复上述分割过程，直到满足停止分割的标准：
   （1）一个节点完全成为一类；
   （2）进一步分割当前节点会导致树超过设定的最大深度；
   （3）信息增益小得超过了阈值；
   （4）节点包含的样本数量少得超过了阈值。
   

2.4 决策树解决分类问题时需要注意的点

1. 当特征变量由三个及以上的不同的离散特征值构成时：利用**独热编码（One-hot）**可以使决策树分类继续进行。
   独热编码是一种构造特征的方式，是对分类问题的特征进行编码。如果一个特征变量存在k个（k>2）特征值，就创建k个特征变量，新建的每个变量由0、1组成。
2. 当特征变量由连续的特征值构成时：尝试设置不同的阈值（此处的阈值选择：相邻两点间的中点），进行信息增益计算，并使用带来最大信息增益的阈值分割连续特征。

3 （回归）决策树

3.1 节点选择

此处的信息增益是加权方差的减少，所以节点选择能够最大程度减少方差的特征。
$$\text{Information Gain}={\sigma }_{\text{node}}^2-(w_{\text{left}}{\sigma }_{\text{left}}^2+w_{\text{right}}{\sigma }_{\text{right}}^2)$$
如下图，选择Ear shape作为下一个节点。

4 决策树集成（Tree ensemble）

使用多个决策树分类模型，并对结果进行投票。这样做可以增强算法的鲁棒性。

4.1 随机森林（Random Forest）

4.1.1 构建集成树的步骤

1. 使用有放回抽样（Sampling with replacement）的方式创建B个随机训练集（尽管有些样本重复出现），每个新训练集中包含m个样本。在选择每一个节点时，如果还有n个特征可以选择的话，从中随机选择$k$（$k=\sqrt{n}$）个特征，在这$k$个特征中选择下一个节点。随机森林适合用在特征数量较大的数据集；
2. 在每个新训练集上训练一棵树。

注：
(1)B即树的个数，当B远大于100时，实际上并不会取得很好的效果。
(2)随机森林的树在根节点附近往往采用相同的特征。

4.2 XGBoost（Extreme Gradient Boosting）

4.2.1 构建集成树的步骤

1. 抽样：不同于从所有样本中以同等概率（1/m）取出样本，而是更可能地取出之前训练的树分类错误的样本（思路类似于刻意练习）；
2. 在每个新训练集上训练一棵树。

from xgboost import XGBClassifier

model = XGBClassifier()
model.fit(X_train,y_train)
y_pred = model.predict(X_test)

4.2.2 XGBoost的优点

1. 开源；
2. 快速且高效；
3. 默认的拆分标准和停止拆分标准就很好；
4. 内置正则化技术；
5. 在ML竞赛中很有竞争力。

总结

XGBoost和深度学习算法是赢得很多比赛的两种算法，要用决策树的时候不妨就用XGBoost。

需要注意的地方

1. XGBoost原理比较复杂，网课没细说；
2. 复习的时候再看看作业。