我试图追踪谁发明了决策树数据结构和算法。
在关于决策树学习的维基百科条目中，声称“ID3 和 CART 是在大约同一时间（1970 年至 1980 年间）独立发明的”。ID3 后来出现在：
所以我不确定这个说法是否属实。
我发现使用 Google 书籍可以参考 1959 年出版的《统计决策系列》和 1958 年的工作论文集。上下文不清楚，他们似乎没有提出算法。但是，他们没有定义数据结构并将其视为众所周知的。
使用 Google Scholar 我发现了一个可以追溯到 1853 年的引文，但这些是解析错误，而不是那个日期的真实引文。
好问题。@G5W 在引用 Wei-Yin Loh 的论文方面走在了正确的轨道上。Loh 的论文讨论了决策树的统计前因，并且正确地追溯到了 Fisher (1936) 关于判别分析的论文——本质上是将多个组作为因变量进行回归分类——并从那里通过 AID、THAID、CHAID 和购物车模型。
简短的回答是，我能够找到的第一篇开发“决策树”方法的文章可以追溯到 1959 年，英国研究员威廉贝尔森在一篇题为“生物分类原理的匹配和预测”的论文中( JRSS , Series C, Applied Statistics, Vol. 8, No. 2, June, 65-75)，其摘要将他的方法描述为匹配人口样本和为此制定标准之一：
在这篇文章中，贝尔森博士描述了一种匹配人口样本的技术。这取决于经验开发的预测变量的组合，以提供最佳可用的预测或匹配组合。基本原理与多重相关方法中固有的原理完全不同。
“长”的答案是其他甚至更早的思想流在这里似乎相关。例如，死亡率精算表中使用的简单的年龄-性别队列分组为思考可以追溯到几个世纪的决策提供了一个框架。也可以说，追溯到巴比伦人的努力使用了二次方程，这些方程在变量中是非线性的（不是在参数中，http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations。 html）具有相关性，至少在它们预示物流增长的参数模型方面（我认识到这是一个延伸评论，请继续阅读以获得更充分的动机）。此外，哲学家们早就认识到并理论化了分层排列的定性信息的存在，例如亚里士多德关于类别的书。层次结构的概念和假设是这里的关键。其他相关的、更晚的发现是在大卫希尔伯特的无限发展中超越了 3-D 欧几里得空间的边界，希尔伯特空间、组合学、与 4-D Minkowski 空间、距离和时间相关的物理学发现，爱因斯坦狭义相对论背后的统计力学，以及与马尔可夫链、跃迁和过程模型相关的概率论创新。这里的要点是，任何理论与其应用之间都可能存在显着滞后——在这种情况下，关于定性信息的理论与与其经验评估、预测、分类和建模相关的发展之间的滞后。
最好的猜测是，这些发展可能与统计学家日益成熟的历史有关，主要是在 20 世纪，在开发利用除连续之外的尺度类型（例如，名义或更简单的分类信息）、计数数据模型的模型时（泊松）、交叉分类列联表、无分布非参数统计、多维标度（例如，JG Carroll 等）、具有定性因变量的模型，例如两组逻辑回归以及对应分析（主要在荷兰和法国在 70 年代和 80 年代）。
有大量文献讨论并比较了两组逻辑回归与两组判别分析，并且对于完全名义特征，发现它们提供了等效的解决方案（例如，Dillon 和 Goldstein 的多元分析，1984）。
JS Cramer 关于逻辑回归历史的文章（The History of Logistic Regression，http ://papers.tinbergen.nl/02119.pdf ）将其描述为起源于单变量、逻辑函数或经典S 形曲线的发展：
逻辑术语的生存和设备的广泛应用已决定性地由少数学者的个人历史和个人行为决定......
逻辑曲线的确定性模型起源于 1825 年，当时 Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) 发表了一篇论文，开发了第一个真正的非线性逻辑模型（参数非线性，而不仅仅是变量巴比伦人）——Gompertz 模型和曲线。
我认为导致决策树发明的这条链条中的另一个重要环节是哥伦比亚社会学家 Paul Lazarsfeld 在潜在结构模型方面的工作。他的工作始于 30 年代，在二战期间继续他对新生 OSS（后来的中央情报局，如约翰·奈斯贝特的《大趋势》一书中所述）的德国报纸的内容分析，并最终于 1950 年出版。安徒生这样描述它（潜在结构分析：调查，Erling B. Andersen，斯堪的纳维亚统计杂志，第 9 卷，第 1 期，1982 年，第 1-12 页）：
潜在结构分析的经典理论的基础是保罗·拉扎斯菲尔德在 1950 年对二战期间美国士兵的种族中心主义的研究中发展起来的。Lazarsfeld 主要对开发潜在结构模型的概念基础感兴趣……然而，Lazarsfeld 开发的统计方法相当原始……Lazarsfeld 在哥伦比亚大学的同事早期尝试推导有效的估计方法和测试程序, TW Anderson, who 在一篇论文（Psychometrika，1954 年 3 月，第 19 卷，第 1 期，第 1-10 页，关于潜在结构分析中的参数估计）)，为潜在类模型的参数开发了一种有效的估计方法...为了介绍（潜在类模型的）框架，我们将简要概述基本概念...并使用古德曼后来开发的符号系统(1974a)...数据以多重列联表的形式给出...
这里有一个有用的区别值得做，因为它可能与从 AID 到 CHAID（后来的 CART）的进展、基于列联表的模型（模型中的所有变量都名义上缩放）和最近的潜在类模型（更多准确地说，基于尺度和分布的“混合”的有限混合模型，例如，Kamakura 和 Russell，1989，A Probabilistic Choice Model for Market Segmentation and Elasticity Structure) 他们如何创建模型的残差。对于较旧的列联表模型，完全交叉分类表中固有的单元格计数构成了“复制”的基础，因此，用于划分类别的模型残差的异质性。另一方面，最近的混合模型依赖于对单个受试者的重复测量作为划分残差异质性的基础。这个回应不暗示了潜在类模型和决策树之间的直接联系。与 AID 和 CHAID 的相关性可以总结为用于评估模型的统计数据，AID 使用连续 F 分布，而 CHAID 使用卡方分布，适用于分类信息。在我看来，在他们对列联表的分析和建模中，LCM 构成了导致决策树发展的难题或叙述中的重要部分，以及已经提到的许多其他创新。
CHAID 是后来的发展，最初是在 1980 年南非 Gordon Kass 的博士论文中提出的，正如这篇关于 CHAID 的 Wiki 文章 ( https://en.wikipedia.org/wiki/CHAID ) 中所述。当然，CART 是在几年后的 80 年代与 Breiman 等人的，现在著名的著作分类和回归树一起出现的。
AID、CHAID 和 CART 都将树状、分层排列的结构视为现实的最佳表示。他们只是使用不同的算法和方法来解决这个问题。对我来说，这个渐进式创新链的下一步是异质结构理论的出现。正如这篇 Wiki 文章中所定义的那样，异质性“是一种组织系统，其中组织的元素没有排名（非等级），或者它们有可能以多种不同的方式进行排名”（https://en.wikipedia 。 _ _）。从经验的角度来看，网络结构的分析和建模最能代表这种结构理解的历史发展（例如，弗里曼的著作《社会网络分析的发展》）。虽然许多网络分析师会尝试在生成的网络上强制进行分层排列，但这更多地表达了根深蒂固的和无意识的假设，而不是对复杂世界中多重网络结构的经验现实的陈述。
这种回应表明，导致决策树发展的进化弧线在流程的每个步骤或阶段产生了新问题或对现有“最先进”方法的不满，需要新的解决方案和新模型。在这种情况下，不满可以体现在对两组进行建模（逻辑回归）的局限性以及认识到需要将该框架扩展到两个以上的组。对潜在正态分布（判别分析或 AID）的不具代表性假设以及与在采用非参数、无分布假设和模型（例如，CHAID 和 CART）中发现的相对“自由度”的比较的不满。
正如所建议的那样，决策树的起源几乎可以肯定有很长的历史，可以追溯到几个世纪以前，并且在地理上是分散的。人类历史、科学、哲学和思想中的多种流派都可以在勾勒出导致当今存在的多种决策树发展的叙述中被追溯。我将是第一个承认我对这段历史的简要概述的重大局限性。
/** 附录 **/
《新科学家》杂志2014 年的这篇文章的标题是为什么我们喜欢将知识组织成树？( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ )，这是对数据可视化大师 Manuel Lima 的书The Book of树木追溯了数千年来树木作为知识的可视化和助记符的用途。似乎没什么问题，但 AID、CHAID 和 CART 等方法中固有的世俗和经验模型和图形代表了这种原始宗教分类传统的持续演变。
在这段视频（由 CART 软件的实施者 Salford Systems 在线发布）中，向 Leo Breiman 致敬，Breiman 谈到了他的思想发展，这导致了 CART 方法论。这一切都始于一堵贴满不同二战时期战舰轮廓的墙壁。
在阅读 Denis Konig 1936 年的《有限和无限图理论》的导言时，人们普遍认为它为以前被视为儿童娱乐和谜题的领域提供了第一个严格的数学基础，Tutte 指出（第 13 页）该章Konig 书中的第 4 章（从第 62 页开始）专门讨论图论中的树。Tutte 对 Konig 对树的定义的解释是“‘无环’图是没有回路的图，树是有限连通的无环图……换句话说，在树中，从给另一个顶点......”对我来说（我既不是图论者也不是数学家），这表明图论及其在 Poincare 的Analysis Situs或 Veblen 中的先驱关于组合拓扑的讲座，可能为后来成为统计学家的话题提供了早期的知识和数学先例。
第一棵知识树被广泛归因于新柏拉图哲学家波菲里，他在公元 270 年左右写了一本逻辑导论，使用隐喻树来描述和组织知识…… http://www.historyofinformation.com/expanded.php？编号=3857
刚刚在圣经的创世记中发现了更早的对知识树的引用，在这篇 Wiki 文章中进行了讨论... https://en.wikipedia.org/wiki/Tree_of_life_(biblical)。根据这个参考，创世纪可能可以追溯到公元前 1400 年...... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ 不管怎样，创世记早在几个世纪之前就出现了斑岩。
CART 的主要参考是：
分类和回归树
Leo Breiman、Jerome Friedman、Charles J. Stone、RA Olshen (1984)
但这肯定不是有关该主题的最早著作。
在他 1986 年的论文Induction of Decision Trees中，Quinlan 本人将 Hunt 的概念学习系统 (CLS) 确定为 ID3 的前身。他在 1963 年与 CLS 约会，但参考
EB Hunt、J.Marin、PJ Stone，
《归纳实验》
学术出版社，纽约，1966 年
威斯康星大学的 Wei-Yin Loh 写过关于决策树的历史的文章。有一张纸
五十年分类和回归树 Wei-Yin Loh 国际统计评论 (2014), 82, 3, 329–348 doi:10.1111/insr.12016
他就该主题发表的演讲中还有一张幻灯片。