在线随机森林
- 提出者
- Saffari, A. et al.
- 年份
- 2009
- 类型
- Incremental ensemble (streaming decision trees)
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
在线随机森林(ORF)将经典的随机森林扩展到流式设置,在不存储或重放完整训练集的情况下,随着新观测值的到来而逐步更新每个树。自适应随机森林(ARF)等算法增加了漂移检测,以便在数据分布随时间变化时,集成模型能够进行自适应调整。
方法背后的直觉
经典的随机森林需要一次性提供整个数据集来构建其树。在线随机森林用泊松加权在线装袋技巧取代了批处理引导采样:每个传入的观测值都会被传递给每棵树,每棵树通过抽取泊松计数来决定将该样本作为新的训练点使用多少次。树使用在线分裂查找标准(例如,霍夫丁界)进行增量生长,并且漂移检测模块会监视概念漂移,用新的树替换过时的树。其结果是一个森林,它可以在学习流数据的同时,仍然组合多个多样化的树以减少方差。
历史学
在线装袋由Oza & Russell (2001)形式化为引导聚合的泊松加权近似。Saffari等人 (2009)引入了在线随机森林,将在线装袋与随机特征选择和基于霍夫丁的分裂标准相结合,用于计算机视觉流。Gomes等人 (2017)引入了自适应随机森林(ARF),通过ADWIN增加了每棵树的漂移检测,并在基准数据流分类任务上展示了最先进的准确性。ARF已成为MOA(大规模在线分析)框架中的标准基线。
何时使用
当数据连续到达或以无法存储在内存中的大批量形式到达时,当概念漂移是可能发生的情况时(例如,金融流、传感器网络、用户行为日志),或者在完整数据集可用之前需要低延迟预测时,请使用在线随机森林。当标记数据随时间缓慢流入时,它也是一个自然的选择。当完整数据集可以轻松地存储在内存中且重新训练成本不高时,应避免使用它——在这种情况下,离线训练的标准随机森林通常会更准确且更易于验证。当您需要稳定、可复现的特征重要性排序时,也应避免使用它,因为在线森林产生的估计值比其批处理对应项更不稳定。
局限与注意事项
- 早期基于稀疏数据的分裂决策可能不是最优的,并且难以修正。
- 特征重要性估计不如批处理随机森林稳定。
- 超参数调优(树的数量、漂移检测阈值)在流式环境中更复杂。
- 评估需要专门的基于流的协议(预测/测试后训练),这与标准交叉验证不同。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 从流式数据中学习,每棵树的内存恒定,与流的长度无关。
- 当与ADWIN等漂移检测机制配对时,能够适应概念漂移。
- 即使在在线设置中,也能继承集成聚合的方差减少优点。
- 从最初的几个观测值开始提供可用的预测,并随时间推移而改进。
- 无需存储或重放完整的历史数据集。
应用
- 对网络或交易流进行实时欺诈和入侵检测。
- 从传感器流中进行预测性维护,其中分布会随着设备老化而变化。
- 广告中的点击率预测,其中用户行为每天都在演变。
- 医疗监测,其中患者状态随时间持续变化。
- 环境和气候传感,具有非平稳的季节性模式。
使用方式
使用方式
初始化一组T棵树(或霍夫丁树)。每棵树维护每个叶节点的充分统计量——分类计数或回归的平方和——而不是存储原始观测值,这使得模型每棵树的内存恒定。
对于每个到达的观测值,每棵树独立地从泊松(1)分布中抽取k,并将该观测值视为自身的k个虚拟副本。当k=0时,树会跳过该点(作为其袋外样本)。这在不需要完整数据集的情况下近似了引导采样。
公式
k \sim \text{Poisson}(\lambda),\; \lambda=1每棵树更新其活动叶节点处的充分统计量。当一个统计上可靠的标准(如霍夫丁界)表明最佳分裂不太可能随更多数据而改变时,就会触发一个分裂,之后该叶节点被扩展为一个内部节点,并初始化新的叶节点。
一个可选的漂移检测模块(例如,ADWIN)监视每棵树在袋外流上的预测误差。当检测到统计上显著的性能下降时,受影响的树会被重置或替换为新初始化的树,从而使集成模型与不断演变的数据分布保持同步。
在任何时候,所有活动的树都会投票:分类采用多数投票,回归采用平均预测。处理过很少样本的树可能会被降权或排除,直到它们积累足够的数据以提供可靠的投票。
公式
\hat{y} = \text{mode/mean of active trees}常见陷阱
- 使用标准的k折交叉验证进行评估,该方法假设数据独立同分布(i.i.d.)并忽略时间顺序。
- 忽略概念漂移:当数据分布随时间变化时,未能包含漂移检测组件。
- 将在线森林的准确性直接与在完整历史数据集上训练的批处理随机森林进行比较——后者具有固有的信息优势。
- 在流的早期使用过少的树,在每棵树看到足够的数据做出可靠分裂之前。
- 忘记泊松加权装袋近似了引导采样——它并没有精确地重现批处理引导采样的统计特性。
常见问题
在线随机森林与标准随机森林有何不同?
标准随机森林使用引导采样在完整数据集上一次性训练所有树。在线随机森林用泊松加权在线装袋取代了批处理引导采样,在每个观测值到达时逐步更新树分裂,并可选地检测和适应概念漂移——所有这些都不存储历史数据。
什么是泊松加权技巧?
每个传入的样本被展示给每棵树k次,其中k是从泊松(1)分布中抽取的。由于k的期望值为1,并且k=0的概率约为37%,这在统计上近似了引导过程(有放回抽样),而无需将完整数据集存储在内存中。
我应该如何评估在线随机森林?
使用预测(测试后训练)协议:对于每个传入的观测值,首先用当前模型进行预测,记录误差,然后更新模型。这提供了无偏的、按时间顺序排列的预测性能估计,而没有数据泄露。
我什么时候应该添加漂移检测?
当数据生成过程可能随时间变化时——例如,用户偏好、金融市场或磨损的机械系统。没有漂移检测,过时的树会累积并拖累集成模型的准确性。ADWIN是一个常见且经过充分测试的选择。
自适应随机森林是同一个东西吗?
ARF是在线随机森林中采用最广泛的变体。它结合了在线装袋、随机特征选择和每棵树的ADWIN漂移检测,并且在MOA和scikit-multiflow/River库中可用。术语“在线随机森林”通常泛指该系列;ARF是一个具体且强烈推荐的实现。
相关方法
参考文献
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.
打开出版物文献已复制。Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.
打开 DOI 文献已复制。