决策树（Decision Tree）简介

决策树（DecisionTree），又称为判定树，是另一种特殊的根树，它最初是运筹学中的常用工具之一；之后应用范围不断扩展，目前是人工智能中常见的机器学习方法之一。

决策树的严谨定义比较繁琐，这里将采用一种直观的方式进行描述。假定一个业务需要多轮决策，于是在它对于的决策树中，从根开始，每个分枝点都表示某一轮的一次决策，不同的孩子顶点代表该轮不同的决策结果，叶子顶点表示最终决策的结果。

【例1】决策树可以表示经过对各种方案在各种结果条件下损益值的计算比较，为决策者提供决策依据。某公司正在考虑3种产品A、B、C的研发

• 产品A“短平快”但是风险也比较大、属于“一锤子买卖”
• 产品B中规中矩但也有一定的失败几率
• 产品C则属于稳健型

为简单起见，假定只能选择一种产品且产品失败不造成损失。各种产品的情况如下表所示。

按照概率计算期望值后，得到各个顶点的标号值如下图所示。所做的（理性）决定应该是研发产品C。

【例2】著名的“称币问题”（或称“称球问题”）。首先看它的一个简单版本：有9个外观一致的“金币”，其中一个是铜质的假币，重量比其他金币轻，给定一个无砝码的天平，你会如何使用尽可能少的称量次数确定哪一枚是假币？

这也可以通过一个决策树模型来处理，如下图所示。

称币问题有很多变体，例如：

（1） 有 n 个外观一致的“金币”，其中一个是假币，但不知道重量比其他金币轻还是重，给定一个无砝码的天平，你会如何使用尽可能少的称量次数确定哪一枚是假币？

（2） 有 n 个外观一致的“金币”，其中一个是假币，但不知道重量比其他金币轻还是重，给定一个无砝码的天平，你会如何使用尽可能少的称量次数确定哪一枚是假币且能确定假币是比其他金币轻还是重？

（3） 有 n 个外观一致的“金币”，其中一个是假币，但不知道重量比其他金币轻还是重，给定一个无砝码的天平和一个标准的真币，你会如何使用尽可能少的称量次数确定哪一枚是假币？

（4） 有 n 个外观一致的“金币”，其中一个是假币，但不知道重量比其他金币轻还是重，给定一个无砝码的天平和一个标准的真币，你会如何使用尽可能少的称量次数确定哪一枚是假币且能确定假币是比其他金币轻还是重？

但是，请注意，每次称量至多只能给出3种结论之一，因此层数为 m 的3叉树的叶子顶点至多有 3^m 个，因此对于原始问题而言，经过 m 次称量至多只能确定 3^m-1 个金币与1个较轻的铜币的真伪；或者等价地讲，对于包含1个较轻的铜币的 n 个“金币”，判断其真伪至少需要 \lceil log_3n \rceil 次称量。而对于变体（2）而言，不仅仅要指出哪一枚是假币、还要且能确定假币是比其他金币轻还是重，所以可能的结果数目为 2n ，称量次数的下界为 \lceil log_3 2n \rceil 。

关于“称币问题”（或称“称球问题”）的具体解法，我可能在将来会单开一篇文章讨论。

最后，在人工智能中，决策树可用于解决分类问题。根节点包含了样本的全集，每个分枝点代表对某一特征属性的一次测试，每条边代表一个测试结果，叶子顶点代表某个类或类的分布。简单地说，决策树可以被视作是一个if-then规则的集合。这个过程的关键就是建立决策树，通常的过程是：递归地选择最优特征、并用最优特征生成顶点对数据集进行分割。

【例3】雯雯平时喜欢买衣服或者读书，通过观察，得到了关于她活动规律的一份数据如下表所示。

在这里，将天气、温度、湿度和风力视作4个属性，活动为类别，共两种。

通过决策树学习算法可以得到如下图所示的决策树。之后就可以根据天气、温度、湿度和风力这些客观属性的值，快速查到雯雯的活动选择，而不需要再查询复杂的数据表。

更可以通过得到的决策树，预测推断出在数据缺失的情况下雯雯可能进行的行为。例如已知数据中并不包含天气晴、温度高、湿度正常和风力强的情况，但此时可以根据下图猜测雯雯会去买衣服。

常见的决策树算法有ID3、C4.5、C5.0、CART（classification and regression tree）等，这里不再做深入介绍。有兴趣的读者可以查阅相关资料进行学习。