第2章
决策树

昆兰（Quinlan）在1986年发表的论文中详细描述了决策树算法[1]，这是一种用于分类的树状结构，方法简洁、直观而且有效，直到现在仍被广泛使用，或者作为其他方法的基础。决策树最早源于1963年的CLS（Concept Learning System，概念学习系统），用于根据物体的属性进行分类。在1979年，昆兰提出了构造决策树的ID3算法。该算法最初用来判断国际象棋残局的输赢，后来用于通用分类问题。在此基础上还有一系列的改进算法，如C4.5。

在昆兰发表决策树算法的时代，机器学习的概念已经提出。人们认识到，学习是智能行为的重要特征，理解学习的过程是理解智能的必由之路。昆兰将当时的机器学习方法分为两类：一类是能够自我改进的自适应系统，它们通过监测自己的性能，调整系统内部参数，向着目标方向做出改进；另一类是基于结构化知识的学习方法，把学习视为获取知识，比如专家系统中的产生式规则。昆兰将决策树纳入后一类学习方法。后一类学习方法在当时的专家系统研究热潮中显得尤为重要，它解决了专家系统获取知识的瓶颈问题。专家系统通常采用“访谈”的方式获取知识，知识工程师对领域专家进行访谈，进而将领域专家所掌握的知识形式化地描述成计算机能够理解的产生式规则。这个过程是非常耗时和低效的，我们在前面章节已经对专家系统面临的这些困难进行了讨论。昆兰也看到了这一点，决策树正是在这种背景下提出的。