机器学习-决策树，随机森林和 XGBoost

本文内容主要参考了 [^1] [^2]

决策树

决策树的思想其实就是一个树形的判断过程，比如判断对水果分类，先判断是否是绿色，然后判断大小，两次判断通过后我们将水果分类成西瓜。
西瓜书对决策树的解释如下：

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;叶结点对应于决策结果，其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集.从根结点到每个叶结点的路径对应了一个判定测试序列.决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的"分而治之" (divide-and-conquer) 策略
其生成的过程是递归的过程，比如当前我们要选取一个属性作为当前子树的划分节点，然后对于划分后的结点，我们对该子树下的节点继续划分。

现在的问题是怎么选取最优的划分节点？决策树的想法是，让每一次划分后的分支结点的纯度尽可能的高，即尽可能的属于同一类别；从信息论的角度来看就是让划分后的信息量尽可能小。我们假设样本集合是 $D$ ，属性集合是 $A$ ，样本集合是 $\mathcal Y$

首先划分前的信息量均值为：

$H(D)=-\sum_{k=1}^{|\mathcal Y|}p_k\log p_k$

如果当前划分我们采取的是属性 a，且属性 a 的取值为 $\lbrace a^1,a^2,\cdots,a^V\rbrace$ 。需要注意的是熵是信息量的均值，因此当我们按照 a 划分后，信息量其实是一个条件熵，即：

$H(D|a)=\sum_{v=1}^VP(a=a^v)H(D|a=a^v)$

如果所有属性 a 值为 $a^v$ 的样本组成集合 $D^v$ ，那么上式可以整理为：

$H(D|v)=\sum_{v=1}^V\frac{|D^v|}{|D|}H(D^v)$

ID3 算法

该算法是考虑信息增益最大化，即划分后的信息量比划分前信息量小的部分就是信息，其实就是互信息。

$\text{Gain}(D, a)=H(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}H(D^v)\\ a_*=\underset{a\in A}{\arg\max}\text{\,Gain}(D,a)$

但是这种算法有个缺点，因为我们每次选取的策略是，让选取后条件熵最小，因此如果按照某个属性值划分后，每个属性值都只有一种类别，这样熵是 0，是很小的。但是这样的决策树显然是不够好的，因为泛化能力太弱。

C4.5 算法

为了解决 ID3 算法的问题，ID3 算法偏好属性值取值较多的属性，即偏好较高的属性熵。C4.5 算法的思路是，在 ID3 的基础上，我们除以属性熵得到一个增益率，我们让增益率最大，从而弥补 ID3 对较高属性熵的偏好，属性熵为：

$H(a)=-\sum_{v=1}^Vp_v\log p_v\\ p_v=\frac{|D^v|}{|D|}$

因此增益率为：

$Gain\_ratio(D,a)=\frac{Gain(D,a)}{H(a)}$

容易看出 C4.5 算法是偏好属性值少的属性，因此往往是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

CART 算法

CART 算法用另一种方式衡量“纯度”，即我们随机从数据集中抽取两个样本，他们不一致的概率可以用基尼指数表示

$\text{Gini}(D)=\sum_{k=1}^{|\mathcal Y|}\sum_{k'\neq k}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal Y|}p_k^2$

因此我们想让划分后基尼指数尽可能小，划分后某个分支下的基尼指数为 $\text{Gini}(D^v)$ ，此时“纯度的均值”为：

$\text{Gini\_index(D,a)}=\sum_{v=1}^Vp_v\text{Gini}(D^v)\\ a_*=\underset{a\in A}{\arg\min}\text{\,Gini\_index}(D,a)$

剪枝

西瓜书如是说：

剪枝(pruning) 是决策树学习算法对付"过拟合"的主要手段.在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合.因此，可通过主动去掉一些分支来降低过拟合的风险.
决策树剪枝的基本策略有"预剪枝" (prepruning) 和"后剪枝"(postpruning) [Quinlan, 1993]. 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

在 python 中使用

from sklearn.tree import DecisionTreeRegressor
from sklearn.tree import DecisionTreeClassifier
model = DecisionTreeClassifier()
model.fit(train_X,Y)
model.predict(test_X)

随机森林

随机森林其实是集成学习中 bagging思想的运用。我们可以从名字上来理解随即森林，首先我们利用 bagging 进行多次采样，然后每次采样我们需要得到一个基学习器，这里面的每一个基学习器相当于是一个决策树。而随机则是该决策树的学习过程引入了随机状态 $k$ ，在学习决策树的过程中，我们需要从当前的属性集 $A$ 中选一个最优属性作为依据进行划分结点，而随机状态的作用是，我们需要先从这个 $A$ 中随机抽取 $k$ 个元素组成一个特征子集 $A^k$ ，然后再从 $A^K$ 中选最优属性进行划分。分般情况下，推荐值 $k= \log_2 d$ [Breiman, 2001a].