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

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

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

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

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

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

• 没有认识到: 师父可以将他大脑里的决策树当成知识, 直接教给徒弟.
• 没有认识到现成的决策树, 其实也是前人从数据中学习而得的知识.
• 没有把决策树看成一系列“具有良好组织”的规则 .
• 一开始就陷入信息增益的概念, 而没想到决策树其实是一大类方法, 还可以用其它启发式信息. 只是 ID3 最为成功而已.