决策树

Posted on | In | 浏览 次
Words count in article: 1.8k | Reading time ≈ 6

决策树优点

  1. 容易解释，可以可视化。
  2. 对数据预处理的要求低，不需要做数据归一化，允许数据有缺失。
  3. 可以处理连续型变量和离散型变量。

决策树的缺点

  1. 容易过拟合，可以通过剪枝，设置每个节点最小样本数量，树的最大深度来避免。
  2. 容易收到干扰，某些数据的微小变化可能带来树的巨大变化。其实就是方差的问题，减小方差可以通过ensemble的方式缓解。
  3. 无法保证找到最优的树，找到最优的树是一个NPC问题。因此，每个节点分裂时，使用贪心算法。只能得到局部最优解。可以通过ensemble的方式缓解，训练每棵树时对数据和特征做采样。
  4. There are concepts that are hard to learn because decision trees do not express them easily, such as XOR, parity or multiplexer problems.
  5. 对于数据不平衡问题，树可能有很大的偏差，需要先解决数据不平衡问题。

时间复杂度分析

使用技巧

  1. 数据量和特征数量要匹配，数据很少，但是特征很多很容易过拟合。
  2. 提前使用PCA，ICA或者Feature Selection降维可以让树学的更好。
  3. 事先解决数据不平衡问题。例如通过采样方式，或者通过normalizing the sum of the sample weights for each class的方式实现。

不同类型的树

ID3

ID3树每个节点有多个分支，根据信息增益来作为分裂标准。在树生成之后使用剪枝来防止过拟合。

缺点：只能使用离散特征，只能针对分类问题。

信息熵，表示数据的不确定程度。公式如下：

信息增益，公式如下：

ID3算法：

  1. 遍历所有特征，找到Gain最大的特征。
  2. 使用该特征进行划分。并删除该特征。
  3. 循环1-2，直到所有数据为相同类别，或者达到叶子节点最小数量要求。

缺点

  • 只能针对分类问题
  • 只能处理离散特征
  • 分裂的时候偏向特征值多的特征。

C4.5

C4.5树是ID3的一个后续，使用信息增益率作为分裂标准，可以使用连续值作为特征(对于一个连续特征，取所有数据中出现的值，排序之后，取相邻的两个值的均值作为划分点)。采用后剪枝防止过拟合。

其中$IV(a) = -\sum\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$

缺点：

  • 只能针对分类问题
  • 分类的时候偏向特征值少的特征

CART

CART树支持回归问题，对于分类问题使用基尼指数的增益作为分裂标准。对于回归问题使用MSE作为分裂标准。基尼指数反应了从样本中随机抽取两个样本，标签不一致的概率。因此基尼指数越小，纯度越大。

剪枝

剪枝的目的是为了防止决策树过拟合，如果一棵决策树不进行任何限制的话，把每个点放到一个叶子节点上，可以坐到100%的准确率。但是这样一方面拟合了噪声，另一方面如果训练集和测试集分布不一致会使得性能下降很多。剪枝分为两种，预剪枝和后剪枝。

预剪枝
预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

对于泛化性能提升的判断有多种，西瓜书在训练集中划分一个验证集，每一个分裂的时候使用验证集判断性能有没有提升。除此之外还可以设定一个阈值，当熵值减少低于阈值的时候停止。但是这种方法实际中的效果并不好。

后剪枝
后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。

后剪枝有以下一些方法

  1. Reduced-Error Pruning (REP,错误率降低剪枝）。把每一个非叶子节点，替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替。如果这个时候验证集上的准确率提升，则简化决策树。

  2. Pessimistic Error Pruning (PEP，悲观剪枝）。PEP剪枝算法是在C4.5决策树算法中提出的，同样使用子树的根代替叶子。首先给出叶子的经验错误率$(E+0.5)/N$，0.5是一个调整系数，人为设定。E为这个叶子节点判断错误的样本的数量，N为这个叶子节点所有样本的数量。那么子树的经验错误率为$(\sum E+0.5*L)/\sum N$。最终判断是否进行剪枝的条件如下：

    其中子树的错误率可以看作一个二项分布，标准差为$\sqrt{Np(1-p)}$。$E(subtree_err_cnt)$就是剪枝之前的错误数量，$var(sub_tree)$是使用剪枝之前的错误率计算出来的标准差。$E(leaf_err_cnt)$是剪枝之后的错误率。

    也就是说，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝。

优点 缺点
预剪枝 降低了过拟合风险；显著的减少了训练和测试的开销 当前表现不好的分裂，后续可能会带来大的提升，基于贪心策略的前剪枝会带来模型欠拟合的风险
后剪枝 欠拟合的风险小，泛化性能优于预剪枝 训练开销比未剪枝和预剪枝大

CART树剪枝

cart树的剪枝方法属于后剪枝，首先定义如下的损失函数：

其中$C(T)$表示树T的基尼指数，后面一项表示树的复杂度。对于T中的一个非叶子节点t，以t为根节点的树的损失为
剪枝之后以t为叶子节点的损失函数为
当$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$的时候两种损失一样。对树中每一个节点t，计算

表示剪枝之后损失函数的增大程度，找到一个最小的$g(t)$，剪枝得到一棵树，剪枝k轮之后得到k棵树，最终使用验证集，找出表现最好的树。