决策树（Decision Tree）

什么是决策树？
一个决策树里面有哪些概念？
有了决策树，如何使用决策树做分类预测？
怎么得到一个决策树分类器？
用决策树做回归要怎么做？
决策树有哪些不好的地方？

1. 什么是决策树？

一种机器学习算法，可以很直接对数据进行做分类或者回归。
对训练数据做很少的假设

2.决策数里的概念

决策树里有根节点、节点、叶节点的概念；
- 根节点就是最上层的第一个节点，只有子节点，没有父节点；
- 叶节点就是最下层的，没有子节点的节点，其他的节点称为内部节点，或者节点。
- 决策树的每一个内部节点以及根节点都需要做一次决策，以向下分岔，直到成为叶节点为止。

3. 有了一个决策数，如何做预测？

对一个新的样本实例，从根节点开始，按照每个内部节点需要做的预测向下判断，直到走到了某个叶节点，对于分类问题来说，所到达的叶节点的类别分布值，就给出了该样本的属于各个类别的概率。

这个预测的过程很快，只取决于树有多少层，时间复杂度近似为 $O (\log_{2} m)$ , $m$ 为训练时候样本的个数。

$\log_{2} m$ 大概代表一个均匀分岔的树的层数, 对于均匀分岔的数，第k层大概有 $2^{k}$ 个节点, 令 $2^{k} = m \Rightarrow k = \log_{2} m$

4. 如何利用训练数据得到一个决策树？

两个概念：Gini 不纯度，信息熵

Gini 不纯度

G_{i} = 1 - \sum_{k = 1}^{n} p_{i, k}^{2},

p_{i, k}

是第

i

-节点上，属于第

k

类的样例比例。

信息熵

尽管Gini impurity可以作为一个很好的度量来使用, 熵也不失为一个很好的度量量,

H_{i} = - \sum_{k = 1, p_{i, k} \neq 0}^{n} p_{i, k} \log (p_{i, k})

生成一个决策树

CART算法

选定一个特征 $k$ 与阈值 $t_{k}$ ,用它来将数据集分为两类; 比较不同的分类方式, 使用分类后节点的纯度最高的类别,
CART cost function for classification:
$J (k, t_{k}) = \frac{m_{l e f t}}{m} G_{l e f t} + \frac{m_{r i g h t}}{m} G_{r i g h t}$

纯度最高就意味着上述定义的不纯度最小。
对分后的子节点继续按照上述逻辑来分类，直到达到了你指定的最大深度，或者怎么分都不会在降低上述cost function了，也就是不能再提高纯度了。

这里这个算法有一些可以认为控制的超参数，比如：
- 最小样本分割数：如果一个子节点的样本数少于某个值后，就不要再对它进行分类操作了
- 最大叶节点数
- 最大深度
- 等等

训练决策树的时间复杂度 $O (n \times m \log_{2} m)$

找到一个最优的决策树是一个 NP-完全（NP-Complete）问题, 它需要 $O (\exp (m))$ 的时间，因此只要找到一个合理好的解决方案就行。
CART 训练的时候需要对每个数据的每个特征在每个节点上都做判断，因此，其时间复杂度近似为：
$O (n) \times O (m) \times O (\log_{2} m)$

正则化的问题：剪枝操作

对训练数据做很少的假设，如果不对参数加以限制，生成的树很可能会过拟合；提前设置超参数，可以限制模型不要野蛮生长
也有算法先不对决策树加以限制参数，任其野蛮生长，然后采用剪枝的方法来优化决策树的泛化能力, 比如：
- 一个节点的子节点很有可能是没必要的，如果它能提高的纯度增加微乎其微
- 等等吧。。。

5. 决策树回归

不同于分类决策树，回归决策树不是预测一个类的概率，而是输入一个样例，输出一个预测值！
其cost function 可以是MSE（mean squared error）.

CART cost function:

J (k, t_{k}) = \frac{m_{l e f t}}{m} M S E_{l e f t} + \frac{m_{r i g h t}}{m} M S E_{r i g h t},

其中

M S E_{n o d e} = \sum_{i \in n o d e} ({\hat{y}}_{n o d e} - y^{(i)})^{2}, {\hat{y}}_{n o d e} = \frac{1}{m_{n o d e}} \sum_{i \in n o d e} y^{(i)} .

这里看出来，回归是这样做的，先取一个阈值对结果进行粗略分类，用平均值来表示该节点的预测值，再利用MSE最小化的原则，继续向细划分。

如果你不对决策树加以限制的话，很容易过拟合。

6. 决策树的不稳定性问题

偏爱正交的边界设定，对数据的orientation很敏感
对数据集的改变很敏感，你从训练数据中移除或者改变某些数据，决策树可能变化很剧烈。

参考文献：
(小蜥蜴书) Hands on Machine Learning with Scikit-Learn and TensorFlow, A. Geron

决策树（Decision Tree）

决策树 （Decision Tree）

1. 什么是决策树？

2.决策数里的概念

3. 有了一个决策数，如何做预测？

4. 如何利用训练数据得到一个决策树？

两个概念：Gini 不纯度， 信息熵

Gini 不纯度

信息熵

生成一个决策树

CART算法

训练决策树的时间复杂度O(n×mlog2m)O(n×mlog2⁡m)

正则化的问题： 剪枝操作

5. 决策树回归

6. 决策树的不稳定性问题

相关推荐

决策树（Decision Tree）

两个概念：Gini 不纯度，信息熵

训练决策树的时间复杂度 $O (n \times m \log_{2} m)$

正则化的问题：剪枝操作