有了关于分类问题的基本认识，本节介绍一种简单的分类算法——决策树。决策的意思就是使用训练数据学习分类的决策依据，从而可以据此对需要分类的数据属于哪一类这样的问题给出决策。决策树是人工智能中的经典算法，既适用于输出结果为连续值的回归问题（又叫回归树），也适用于输出结果为离散值的分类问题，它们的基本想法是一致的，理解了决策树的原理，回归树就很容易掌握了，本节只针对离散值的情形讲解决策树算法。
使用决策树进行分类其实模拟了人类决策的过程。例如，小明想约小红明天去看电影，发生了下述对话过程。
小红：明天有好看的电影吗？
小明：有啊，一部新上映的大片。
小红：看几点的？我只有中午有时间。
小明：正好中午12点有一场。
小红：明天天气怎么样？
小明：天气很舒服，不冷不热。
小红：好的，那你明天按时来接我吧。
小明：明天见。
在这个对话中，小红对明天看电影的事情有“看”和“不看”两类安排，做出“看”的决定需要满足如下要求：电影好看、时间合适，并且天气舒服。这个决策的过程可以通过图3-1来描述。
图3-1
上述图示很好地展示了决策树的直观含义。所谓决策树，指的是一个树形结构，其中每个内部节点代表一个特征属性，内部节点的每个分支路径代表了此特征属性的某个可能的属性值，而每个叶子节点代表一个类别。因为每个内部节点都会生长出几个不同的分支，沿分支可以到达其他的内部节点或叶子节点，所以此内部节点对应的特征属性又叫作分裂属性。
决策树是一个用于分类的预测模型，也就是说，它给出了每个待分类对象到类别的一种映射关系。使用决策树进行决策的过程就是从根节点开始，测试待分类对象相应的特征属性，按照属性值选择分支路径，直至到达某个叶子节点，将此叶子节点存放的类别作为决策结果。
可以结合上面的直观例子理解与决策树相关的概念。所谓树形结构，指的是图3-1就像一棵倒置的树。橙色的节点都是内部节点，代表“电影质量”“时间”“天气”三个特征属性，特别地，“电影质量”叫作根节点。存放决策结果“看”或者“不看”的绿色节点就是叶子节点。有了这个树形结构，根据特征属性的不同取值，沿着决策树的不同路径，就可以做出相应的决策了。
在这个直观的例子中，每个特征属性都有两个可能的取值，所以对应两个分支，这样的树叫作二叉树。决策树对特征属性的取值没有个数限制，所以决策过程对应的树形结构可以更复杂。与决策树复杂程度有关的另外一个因素是决策过程中所使用的特征属性的个数，它决定了树的深度。在这个例子中使用了三个特征属性，所以这是一个三层的决策树。
从这个例子看，决策树的道理很简单，对它进行决策的方式也已经了解得很清楚了。那么读者现在是不是可以完整地针对一个分类问题给出相应的决策树呢？如果尝试一下，会发现还有一个最关键的问题没有解决，就是如何构建一棵决策树。具体地说，关于决策树的构建，需要解决如下两个问题。
（1）如何选择分裂属性
这个问题可以分解成两个小问题：一是选择哪个特征属性作为根节点？二是某个内部节点之下应该选择哪个特征属性作为下一层分裂属性？
（2）何时停止树的生长
在决策树生长成什么样子以后，就可以作为最终进行决策时所使用的决策 树了？
一个分类问题，通常包含多个特征属性。如果可以随意选择根节点和内部节点，当有m个特征属性时，用不同的顺序安排分裂属性，理论上可以生长出m！棵不同的决策树。所谓选择分裂属性的问题，其实是制订一个合理的量化标准，根据这个标准来比较不同的生长顺序的优劣，从而选择出最佳的生长顺序作为最终的决策树。
