在线决策树
- 提出者
- Domingos, P. & Hulten, G.
- 年份
- 2000
- 类型
- Incremental supervised classifier
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
在线决策树是一种决策树,它从连续的数据流中增量式地生长,而不重新访问过去的样本。占主导地位的算法是 Hoeffding 树(VFDT),它使用 Hoeffding 界来决定何时在节点上看到了足够多的样本可以有信心地进行分裂,从而能够对潜在的无限数据流进行可扩展的实时分类。
方法背后的直觉
标准的决策树是通过反复扫描整个数据集来构建的,以找到最佳分裂点。在流式设置中,这是不可能的,因为数据是逐个到达的,并且无法存储。在线方法只在每个叶节点保留运行统计数据。当累积了足够的样本时,Hoeffding 界——一个统计保证——确认了显而易见的最优分裂点即使在看到了所有可能的样本后仍然是最佳分裂点。只有到那时,树才会实际分裂,从一个叶节点生长成一个不断加深的结构,而无需回顾过去的数据。
历史学
基础算法,即非常快速决策树(VFDT)或 Hoeffding 树,由 Domingos 和 Hulten 于 2000 年 KDD 会议提出。他们将 Hoeffding 不等式应用于有界数据流中分裂属性选择的误差,从而实现了无需存储样本的渐近正确的树归纳。Hulten、Spencer 和 Domingos 于 2001 年将其扩展到概念漂移流。该方法成为 MOA(大规模在线分析)框架的基石,并影响了一代流式集成方法。
何时使用
当数据以连续流的形式到达时,当由于数据量或隐私限制而无法存储整个数据集时,或者当模型必须随着每个新观测值实时更新时,请使用在线决策树。它非常适合物联网传感器流、点击流分类、具有演变模式的欺诈检测以及任何预期存在概念漂移且模型必须适应而无需从头重新训练的场景。当数据集很小且是静态的时,不要使用它——标准的决策树或随机森林在实现上会更快,并且更准确。如果精确分裂阈值的可解释性至关重要,并且不能接受阈值会随时间变化,也应避免使用。
局限与注意事项
- 在小数据集上的准确性通常低于批量决策树,因为 Hoeffding 界需要大量样本才能进行早期分裂。
- 基本算法中的分裂决策是不可逆的;除非添加显式的子树替换,否则早期糟糕的分裂可能会持续存在。
- 调整置信度参数 δ 和分裂评估之间的宽限期需要领域知识。
- 树的可解释性会随着新分裂的添加而随时间变化,使得静态报告变得困难。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 以单次扫描处理数据,每个节点具有恒定的内存,可扩展至理论上无限的数据流。
- 通过 Hoeffding 界提供理论保证,在给定足够数据的情况下,分裂点渐近地与批量树相同。
- 可以整合漂移检测器以适应非平稳分布,而无需完全重新训练。
- 与批量方法不同,它在第一个样本到达时即可提供可用模型,而批量方法需要完整数据集才能产生任何预测。
- 自然地处理存储数据不切实际或在法律上受限的高吞吐量场景。
应用
- 金融交易流的实时欺诈检测。
- 网络入侵检测,其中流量统计数据连续到达。
- 物联网和传感器数据的分类,适用于内存受限的边缘设备。
- 点击流或用户行为建模,其中数据量排除了完全存储。
- 自适应垃圾邮件过滤,因为电子邮件中的语言模式会随时间演变。
- 作为基准的流式分类器,用于与更复杂的流式集成方法进行比较。
使用方式
使用方式
每个带标签的样本都从数据流中逐个到达。树将它从根节点向下路由,穿过现有的分裂点到达相应的叶节点,在标记实例之前对其进行预测。
所有候选分裂属性的充分统计量——例如条件计数或高斯均值和方差——都在接收到实例的叶节点处更新。不保留原始数据;只保留这些紧凑的摘要。
Hoeffding 界(或 Chernoff 界)ε = sqrt(R^2 * ln(1/δ) / (2n)) 以至少 1 - δ 的概率量化了观察到的最佳分裂属性与真实最佳分裂属性之间的最大误差。随着 n 的增长,ε 趋近于零。
公式
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}如果最佳和次佳分裂候选的信息增益差超过当前的 Hoeffding 界,则该叶节点将被获胜属性上的内部分裂节点替换,并初始化两个新的叶计数器。否则,该节点将等待更多数据。
每个到达的实例在用其标签进行更新之前,都会从当前树中获得一个类别预测。可选地,漂移检测器(例如 ADWIN)会监控叶节点的错误率;当检测到概念漂移时,可以替换子树以保持模型最新。
常见陷阱
- 将 Hoeffding 置信度 δ 设置得太宽松,导致对无代表性的早期数据过早分裂。
- 忽略概念漂移——在具有变化分布的数据上运行静态在线树会导致静默的准确性下降。
- 将准确性与在同一数据流的整个数据集上训练的批量模型进行比较,这使得批量模型具有不公平的优势。
- 忘记叶节点在其第一次分裂之前总是预测迄今为止看到的大多数类别,这在早期不平衡数据流阶段可能具有误导性。
常见问题
Hoeffding 树与标准的 CART 决策树有何不同?
CART 树在每个节点扫描整个数据集以找到全局最优分裂点。Hoeffding 树则逐个观察到达的样本,并且仅当统计理论保证显而易见的最优分裂点即使在更多数据下仍然获胜时才确定分裂——不存储任何原始样本。
在线决策树是否处理概念漂移?
基本的 Hoeffding 树不自动检测漂移。像概念自适应非常快速决策树(CVFDT)这样的扩展,以及与 ADWIN 或 Page-Hinkley 漂移检测器结合的版本,可以在检测到漂移时替换过时的子树。
什么是宽限期,我应该如何设置它?
宽限期是指在连续分裂评估之间到达叶节点的样本数量。较大的值会减少计算量但会延迟分裂;较小的值会以更高的 CPU 成本更频繁地评估分裂。典型的默认值范围从 200 到 1000 个样本。
在线决策树是否适用于小型、静态数据集?
不。对于小型、完全可用的数据集,标准的批量决策树或随机森林几乎总能以更低的复杂性获得更好的准确性。在线树专门为流式、大规模或资源受限的场景设计。
在固定数据集上的准确性与批量方法相比如何?
在有足够数据的情况下,Hoeffding 树会收敛到批量学习器产生的相同树,因此准确性最终会匹配。在数据流的早期,在叶节点看到大量样本之前,准确性低于在迄今为止已看到的数据上训练的批量树。
相关方法
参考文献
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
打开出版物文献已复制。Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
打开 DOI 文献已复制。