机器学习08 决策树模型

前面若干篇幅，主要讲了线性分类器，这一节开始，我们会着重介绍决策树模型，从https://www.jianshu.com/p/1416565d268c篇章中，可以知道该模型打破了线性回归中全局性属性，将全局空间进行了划分。决策树是很多集成学习的基模型，在机器学习中有着比较重要的位置。

ID3

ID3是最简单的树模型，树模型树模型，关键就在于要如何从根节点一步步分裂到叶子节点，所以分裂的依据就尤为关键。

ID3模型采用的信息增益，首先介绍一下信息熵，熵是随机变量不确定性的度量，假设X是一个离散标量，其概率分布为

$p(X=x_i) = p_i, i=1,2,...,n$

则随机变量的熵为 $H(x) = -\sum_{i=1}^n p_ilog\ p_i$

这里可以以2为底数，也可以以e为底数，分别是比特和纳特。

当熵最大的时候，p(x)是均匀的，我们可以进行一个简单的证明:

$max \ H(p) = max-\sum_{i=1}^n p_ilog\ p_i = min \sum_{i=-1}^n p_ilog\ p_i$ ，同时满足条件 $\sum_{i=1}^np_i = 1$

利用拉格朗日乘子法（SVM篇章中有过介绍）， $L(p, \lambda) = \sum_{i=1}^n p_i\ log\ p_i +\lambda (1 - \sum_{i=1}^n p_i)$ ,

$\frac{\partial L}{\partial p_i} = log \ p_i + 1 - \lambda = 0$

所以 $\hat p_1 = \hat p_2 = \hat p_3 = ... = \hat p_n$ , 均匀分布, 所以 $0 \leq H(p) \leq log \ n$

可以认为，模型的损失函数就是熵，希望通过特征空间的分裂，起到减小熵的效果。

接下来我们引入条件熵 $H(D|A)$ , 这度量了给定A的条件下，随机变量D的不确定性。

$H(D|A) = \sum_{i=1}^n p_iH(D|A=a_i)$ , 其中 $p_i = P(A = a_i), i = 1,2,3,...,n$

因此可以得到在知道特征A的情况下， D的不确定性减少的程度，这就是信息增益。

信息增益： $Gain(D,A) = H(D) - H(D|A)$

这就是ID3分裂的标准，每次分裂，选择信息增益最大的特征进行分裂，分裂的子节点个数，依赖于本次分裂特征的可能取值个数。当一个特征被切分后，后面不会再考虑了，所以这是一个贪心算法，并不一定可以取到全局最优。

同时可以看出来，ID3这个算法是不能处理连续值的，模型本身也没有包含对缺失值的处理。同时，模型只考虑了树的生成过程，容易过拟合。

对最终学习到的模型，每一片特征空间中，概率最大的类型就是这一个空间的输出。

C4.5

ID3除了上面提到的缺点之外，还有一个比较大的问题是，信息增益作为分裂手段，对可取数值较多的特征有所偏好（这个稍后举例说明）

因此很自然的想到需要给数值较多的特征增加一个惩罚项，因此我们介绍一下信息增益比。

$Gain\_ratio(D,A) =\frac{ Gain(D,A)}{H_A(D)}$ , 其中 $H_A(D) = -\sum_{v=1}^V\frac{|D_v|}{|D|}log_2 \frac{|D_v|}{|D|}$ , V是特征A的取值个数。

C4.5还有的优势在于他是可以处理连续值，对于连续值，从小到大排序，相邻两个值取均值，作为可能的分割点，一个个分割点遍历下来，就可以得到该特征最大的分裂点选择。这边我有一个问题还没有理解，C4.5处理连续值的时候，应该是不能用信息增益比的，所以应该还是信息增益，但这样连续特征要怎么和离散特征（信息增益比）进行比较，选择大的分裂点呢？

除此之外， C4.5引入了剪枝，可以在树生成之后剪枝，选择最好的树，避免了过拟合的问题。这里简单说一下剪枝的原理。

设树T的叶节点有|T|个， t是树的叶节点， t节点有 $N_t$ 个样本， k类样本有 $N_{tk}$ 个， $H_t(T)$ 是节点t上的熵，

损失函数可以定义为 $C_{\alpha}(T) = \sum_{t=1}^{|T|}N_tH_t(T) + \alpha |T|$ , 其中 $H_t(T) = -\sum_{k}\frac{N_{tk}}{N_t}log\ \frac{N_{tk}}{N_t}$

所以确定 $\alpha$ 后，从叶子结点向上回缩，判断每一组叶子结点回缩到父节点前后整棵树的损失函数，若损失函数变小，即进行剪枝。

Cart算法

Cart树既可以用来分类，也可以用来回归， cart算法不同于ID3和C4.5，它构建的是一颗二叉树，特征可能会多次被用来当做分割点。

分类树

Cart分类算法采用了基尼指数作为分裂依据， $Gini(D) = 1 - \sum_{i=1}^kp_k(1-p_k) = 1 - \sum_{i=1}^kp_k^2$ ，

某个特征A = a，把数据集D分为了D1，D2（二叉树，每次分裂都是分为两部分），

则在特征A = a 的条件下，基尼指数是 $Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1 ) + \frac{|D_2|}{|D|}Gini(D_2)$

基尼指数同样表示了数据集的不确定性，作为我们要优化的损失函数，选择基尼指数最小的分裂特征(连续变量的处理方式和C4.5一样），作为分裂点，减小损失函数。然后一步步分裂下去即可。

回归树

数据集， $D = \{{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}\}$ ， y是连续变量

cart树将特征空间划分成一个个单元，回归树模型可以表示为

$f(x) = \sum_{i=1}^mc_m1(x\in R_m)$

当划分确定后，我们又回到了熟悉的损失函数了，因为是回归问题，所以采用平方误差作为loss function

单元Rm上的损失为 $l = \sum_{x_i\in R_m}(y_i - f(x_i)^2)$ ，所以每个单元的输出值cm是这个单元内所有样本的y的均值，即 $\hat c_m = ave(y_i|x_i\in R_m)$

接下来就是如何优化损失函数了，做法是选择最优切分特征j及对应的切分点s，即求解

$min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$ ,即每次遍历特征和切分点，使该式最小。 $c_1,c_2$ 其实就是该区域的样本的均值，即上面的 $\hat cm$ 。找到最佳的特征j和切分点s，即可将节点一分为二，分成两个子节点。

然后对新生成的节点继续求解该式，一步步划分。

接下来介绍一下Cart的剪枝：

首先子树的损失函数： $C_{\alpha}(T) = C(T) +\alpha |T|$ , 其中T是任意子树， C(T)是预测误差，例如基尼指数或是平方误差，得看具体是分类树还是回归树，这边统一记为C(T)， |T|是树的叶子节点个数， $\alpha$ 权衡了训练模型的拟合程度和模型的复杂度

当前的树为 $T_0$ 。对某个内部节点t而言，假设剪枝发生在这一个节点，先考虑没有剪枝前的，损失函数是 $C_{\alpha}(T_t) = C(T_t) +\alpha |T_t|$ （这边我们只需要考虑以t节点为根节点的子树就可以了，因为剪枝与否不会影响剩下的树）

剪枝后，t就是叶节点了，损失函数就是 $C_{\alpha}(t) = C(t) +\alpha$ ，当 $\alpha$ 比较小的时候， $C_{\alpha}(T_t)$ 会比较小，

当 $\alpha \geq \frac{C(t) - C(T_t)}{|T_t| - 1}$ , 节点t就需要剪枝了，等号的时候损失一样，优先选择简单的模型，所以也会发生剪枝。

每一个内部节点（假设叶节点一共有n个，则内部节点有n-1个），都对应着一个剪枝阈值 $\alpha$ ，我们可以算出所有内部节点的 $\alpha$ ，从小到大排列，逐渐增大 $\alpha$ ，每到一个临界值，对 $T_0$ 可以进行一次剪枝，得到每次剪枝后的树，一共有n-1课，同时还有未剪枝的树T0，一共有n棵树。对这n棵树进行交叉验证，选择最好的树，即得到了最终的模型。

分类树和回归树都是一样的处理方法，只是预测误差 $C(T)$ 的表达式不一样（基尼指数或是平方误差）。

以上就是树模型的一些概念，我这篇主要是讲树模型的基本原理及一些细节，后面会开始介绍集成学习相关的内容，很多集成学习的基模型都是cart树。