1.2　决策树算法的起源

曼努埃尔·利马的The Book of Trees: Visualizing Branches of Knowledge（见图1.1），探讨了树状图800年的辉煌历史，从笛卡儿到数据可视化，从中世纪手稿到现代信息设计均有涉及。利马在书中指出，几千年来，树木不仅为我们提供了住所和食物，而且还为我们提供了医药、火、能源、武器装备、制造工具和建筑等似乎无限的资源。人类在观察它们复杂的枝叶结构和叶子季节性的枯萎和复苏时，将树木视为生长、腐烂和复活的强大形象。事实上，树木对人类具有如此巨大的意义，几乎没有任何文化未赋予它们崇高的象征意义。在某些文化中，对树木的崇拜被称为“树枝崇拜”，与生育、不朽和重生的观念联系在一起，通常通过世界轴、世界树或生命之树（arbor vitae）来表达，这类图案在全球各地的神话和民间传说中都很常见。这种魅力也吸引了哲学家、科学家和艺术家，他们同样被树的高深莫测和它的原始、直率及坚韧的美所吸引。

事实上，人们非常喜爱将知识分类归纳，然后用树描述出来。大约270年，新柏拉图派哲学家波菲利发表了其著作《〈范畴篇〉导论》，将亚里士多德的《工具论》中定义的praedicamenta重新规划为五个类别——genos、eidos、diaphora、idion和sumbebekos，并画出了图1.2所示的波菲利之树（tree of Porphyry）。在同类作品中，波菲利的著作是有史以来最成功的。它被翻译成多种语言，1500年来，每个学生都把它作为了解这一主题的第一篇文章来阅读。因此，它在哲学和逻辑学以及知识组织方面的影响是巨大的，而且其树状形式的可视化也令人印象深刻。

图1.1　曼努埃尔·利马的The Book of Trees: Visualizing Branches of Knowledge［17］的封面

图1.2　宾夕法尼亚大学图书馆藏书LJS 457中的波菲利之树［18］

图1.3　Chrétien Frederic Guillaume Roth的“艺术和科学的家谱分布”，引自法国《百科全书》（1780年）

德尼·狄德罗等学者主持编撰的法国《百科全书》（1780年）中，有一棵引人注目的树（见图1.3）。这棵树描绘了知识的谱系结构，其三个突出的分支遵循弗朗西斯·培根1605年在《学习的进步》中提出的分类：记忆和历史（左），理性和哲学（中），想象力和诗歌（右）。树上结着大小不一的圆形果实，代表着人类已知的科学领域。

正如利马的书中所说，树最大的影响是在分类学领域，作为抽象概念的视觉代表。分类学的复杂性和视觉上的简单性的有力结合促使树成为人们学习和认知的有效手段。

“解释和教育；促进认知和获得洞察力；以及最终，使不可见的东西变得可见。”这句话揭示了树形概念在人类发展中的重要作用，也预示着决策树这一工具的巨大潜力。

下面介绍决策树算法起源中的重要里程碑。

●1936年，Ronald Fisher提出了“线性判别分析”，他将其应用于一个二分类问题。1948年，C.R.Rao将其发展为应用于多分类问题。

●20世纪50年代，自动交互检测［1］（Interaction Detection，AID）在运筹学研究中的应用得到了很大的发展。1959年6月，William A. Belson的论文“Matching and Prediction on the Principle of Biological Classification”［2］发表，这被认为是现代决策树算法的开端。

●1963年，Morgan和Sonquist首次提出回归树［9］，它基于的是AID项目。他们提出了不纯度量（impurity）的概念，并递归地将排序数据不断分成两个子集。比如，有序变量X的分割形式为X≤c。如果X有n个不同的观测值，则进行n-1次这样的分割。如果X是一个分类变量，有m个不同的观测值，则有2m-1个X∈A形式的分割，其中A是X值的一个子集。

●1966年，Hunt发表了“Experiments in induction”［10］，确立了决策树“分而治之”的学习策略。他通过将训练记录相继划分为较纯的子集，以递归方式建立决策树。我们将在1.6.2节进行详细介绍。

●1972年，第一个分类树出现在THAID（THeta Automatic Interaction Detection）［21］项目中（由Messenger和Mandell领导）。THAID选择分割是为了最大化每个模式类别（即拥有最多观测值的类别）中的观测值数量之和。预测的类别是一个模式类，替代的不纯度量函数是熵和基尼系数——基尼系数最早由Light和Margolin于1971年提出。

●1974年，加州大学伯克利分校的统计学教授Leo Breiman和Charles Stone以及斯坦福大学的Jerome Friedman和Richard Olshen开始开发分类与回归树（Classification ＆ Regression Tree，CART）算法，它基于递归的数值分割准则来构建树。1977年他们发布了第一个CART版本，1983年发表了该方法的论文［3］，1984年正式发布了CART软件［19］。这是算法世界的一场革命。即使在今天，CART也是数据分析中使用最多的方法之一，其主要升级包括截断不必要的树、隧道和选择最佳树的版本。CART已经成为决策树的世界标准，并在不断发展进步。

●1986年，Ross J.Quinlan应邀在Machine Learning创刊号上发表了ID3（Iterative Dichotomiser 3）算法。Quinlan在Hunt的指导下于1968年在美国华盛顿大学获得计算机博士学位，1978年他在学术休假期间到斯坦福大学访问，在针对国际象棋残局中一方是否会在两步棋后被将死的问题研究中，提出ID3算法并在1979年发表［20］。他提出了一个新的概念：有多个答案的树。需要指出的是，CART和之前其他决策树算法的每个分支只有两个（称为二元树）。ID3使用了一个叫作增益比的不纯度量标准。但是ID3并不理想，所以，Quinlan继续升级了算法结构。

●1993年，C4.5诞生［22］（参见J.R.Quinlan的书C4.5：Programs for Machine Learning，Morgan Kaufmann，1993），它解决了ID3的不足，并在论文《数据挖掘十大算法》中排名第一（Springer LNCS，2008），ID3算法掀起了决策树研究的热潮，短短几年间众多决策树算法问世，ID4、ID5等名字迅速被其他研究者提出的算法占用。因此，Ross J.Quinlan只好将自己的ID3后续算法命名为C4.0，在此基础上进一步提出了著名的C4.5（只是对C4.0做了些小改进），以及后续的商业化版本C5.0。

随着CART、ID3和C4.5这些经典决策树算法的诞生，决策树在流程决策、数据分析和处理领域开始被广泛应用。随着机器学习和各类人工智能技术的迅速推广，决策树良好的可解释性促进了其与各类深度学习方法的融合，本书将在第8章对此进行深入探讨。