机器学习（9）决策树

决策树仍然是监督学习方法，其基本思路跟我们人做一些决策的思路类似：可能要下雨，那就带伞；可能要停水，那就提前备水……

这个决策的数学模型是熵。

熵是信息学概念，表示的是信息量的大小，越不可能发生的事情，它的信息量就越大；越是可能发生板上钉钉的事情，它的信息量就越小。

有一个有名的理论叫熵增，它说的是万事万物在不加干扰的情况下，都在向混乱和无序发展：不加节制只会越来越肥；放在桌子上的苹果总会腐烂掉；热量总会流失；……

熵增它描述了宇宙和人类的终极命运。

决策树的模型中，无论是ID3，还是C4.5，亦或者是CART，它们在每个节点做判据的目标都是为了让熵最小化！

核心的内容已经说完了，具体的内容参见如下的推导，一些数学公式的细节可以自行网查。

相关数学概念准备：

决策树的算法推导流程如下：

如下示例的题材，最后一列是结果，其他列是输入。

ID3的手推示例如下所示：

CART的手推示例如下所示：