摘要: 决策树是一种与人类思维一致, 可解释的模型.

1. 决策树的结构

人类的很多知识以决策规则的形式存储:

• 如果今天是阴天 (outlook = overcast), 就去打球.
• 如果今天出太阳 (outlook = sunny) 而且湿度不高于 70% (humidity $\le$ 70), 就去打球.
• 如果今天出太阳 (outlook = sunny) 而且湿度高于 70% (humidity $>$ 70), 就不去打球.

将这些规则组建出一棵树的样子, 如图 1 所示.

图 1. 决策树例.

2. 决策树的优势

• 直观, 易于理解, 易于传授: 学生会迅速掌握这棵树.
• 相比于决策规则集合, 决策树的优点是没有死角: 任何一种情况都被覆盖.
• 与前面的 $k$NN 相比, 它是一个真正的模型 (model), 不依赖于具体的数据.
• 对于机器而言, 使用决策树进行预测非常迅速, 任何新的实例, 都对应于从树根走到某个叶节点的一条路径. 这种路径的长度通常不超过 10.

3. 决策树的原理

• 人为可以构建决策树, 这就是专家知识, 但它不属于我们讨论的范畴.
• 从数据中构建出决策树, 才是机器学习的内容.
• 决策树的构建过程, 实际上是一个不完全归纳 (特殊到一般) 的过程. 为学习到图 1 所示的决策树, 只用了 14 个样本. 但这棵决策树所覆盖的可能情况, 远远超过了 14. outlook 有 3 种情况, humidity 有 100 种情况, rain 有 2 种情况, windy 有 2 种情况, 所以总共是 31002*2 = 1200 种情况.
• 决策树构建的原则是: 越小越好, 即节点树越少越好. 这是基于奥克姆剃刀 (Occam’s razor) 原理.

4. 决策树的构建方法

• 穷举法. 由于数据量比较大, 一般不使用这种方法.
• 启发式方法. 如基于信息熵、基于基尼指数. ID3 适用于枚举型数据, 使用了信息熵 (条件信息熵之差称为信息增益). 对于实数型数据, 则使用 C4.5. 在绝大多数情况下, ID3 可以获得最小的决策树. 但你也可以构造出反例. 在 2000 年前, 决策树火得一蹋糊涂.
• 剪枝. 如果一棵决策树使用一张 A4 纸都画不下, 就失去了泛化能力. 这时候需要剪枝. 例如, 在一个节点处, 有 100 个正样本和 1 个负样本, 虽然可以增加一个属性将它们分开, 但最好不要增加这个属性, 这样节点至少节约了一个.
• 有时候想同时考虑某些属性之和之类 (温度 + 湿度) 的新属性, 可以使用 Oblique decision tree (斜决策树).

5. 常见误区

• 没有认识到决策树是可以直接通过人来传授的.
• 没有认识到现成的决策树, 其实是前人从数据中学习而得的.
• 没有把决策树看成一系列规则 (具有良好的组织).
• 一开始就陷入信息增益的概念, 而没想到决策树其实是一大类方法, 还可以用其它启发式信息. 只是 ID3 最为成功而已.