Skip to content
返回搜索结果

在线Bagging

提出者
Oza, N. C. & Russell, S.
年份
2001
类型
Online ensemble (streaming bagging)
类别
Machine learning

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

在线Bagging是由Oza和Russell在2001年提出的一种流式集成方法,它将经典的bootstrap聚合(Bagging)框架适应于在线学习场景。每个传入的实例不是通过重采样固定数据集获得,而是以服从泊松分布(泊松(1))的次数被馈送到每个基学习器中,从而在流演进过程中忠实地近似bootstrap采样。其结果是一个鲁棒的、增量更新的集成模型,能够处理概念漂移和连续数据到达,而无需存储整个数据集。

方法背后的直觉

经典的Bagging从固定数据集中抽取随机bootstrap样本,并为每个样本训练一棵树。在线Bagging在从未一次性看到整个数据集的情况下模仿了这一点:当新样本到达时,它会根据从均值为1的泊松分布中抽取的随机次数被传递给每个基学习器。平均而言,每个学习器会看到该样本一次——这正是bootstrap重采样在批量模式下实现的效果——但这种随机性会使学习器去相关。由于不需要存储数据,集成模型可以随着流的增长而无限增长,并随着时间的推移自然地适应分布的变化。

历史学

在线Bagging由Nitesh Oza和Stuart Russell在2001年的AISTATS会议上提出,作为Breiman 1996年Bagging算法在在线场景下的理论和实践扩展。关键的创新——用每个实例的泊松(1)加权替换bootstrap重采样——使得近似在数学上严谨。它成为流式机器学习文献中的基础算法,并且是MOA(Massive Online Analysis)等平台的基线集成模型,自2010年以来,MOA驱动了大多数流式分类器的实证评估。

何时使用

当数据以连续流的形式到达,并且存储完整数据集不可行或被禁止时(例如,传感器日志、点击流、金融Tick数据、实时监控),请使用在线Bagging。当您需要分类或回归,并且模型需要随着每个新观测值进行更新,能够容忍轻微的概念漂移,并且保持内存效率时,它就很合适。不要将在线Bagging作为批量随机森林在固定、中小型数据集上的即插即用替代品——在这些情况下,具有交叉验证的批量集成模型会表现得更好。当数据流表现出严重 abrupt 漂移而没有添加显式的漂移检测机制时,也要避免使用它。

局限与注意事项

  • 在静态数据集上,批量方法(如随机森林或XGBoost)的表现始终优于在线Bagging,因为它们可以使用完整的交叉验证和最优分裂。
  • 基本的在线Bagging对严重的概念漂移的抵抗能力有限;必须外部添加专门的漂移检测器(例如,ADWIN)。
  • 泊松加权为每个实例引入了额外的方差,这可能会减慢短流的收敛速度。
  • 可解释性较低:许多增量增长的树组成的集成模型比单个决策树更难检查。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 一次处理一个实例,内存恒定,支持真正无界的数据流。
  • 泊松加权被证明可以近似bootstrap重采样,从而提供与批量Bagging相当的集成方差降低效果。
  • 自然可并行化:每个基学习器独立更新,适合分布式流式架构。
  • 没有像树深度那样敏感的超参数——集成模型通过多样性进行自我正则化。
  • 无需结构性改变即可轻松扩展到多类分类和回归。

应用

  • 对连续交易流进行实时欺诈检测。
  • 在工业物联网环境中,从传感器数据流中进行预测性维护。
  • 在线广告中的点击率预测,其中用户行为不断演变。
  • 对高吞吐量数据包流进行网络入侵检测。
  • 环境监测:对空气质量或天气传感器读数进行增量分类。

使用方式

使用方式

1

对于每个到达的实例,都会为每个基学习器独立地从泊松(1)分布中采样一个权重k。权重为0意味着学习器完全跳过该实例;权重为2意味着它学习该实例两次。这种随机加权是bootstrap重采样的在线对应物,也是该算法的数学核心。

公式
k \sim \text{Poisson}(1)
2

每个基学习器——通常是增量决策树,如Hoeffding树——接收带有其分配权重的当前实例,并立即更新其内部模型。处理完后不存储任何实例。这种单遍处理的特性使内存保持有界,并允许集成模型扩展到任意长的流。

3

当需要进行预测时,所有M个基学习器都会为查询实例产生其个体输出。集成模型通过多数投票(分类)或算术平均(回归)组合这些输出,产生与批量Bagging相同的聚合逻辑,但计算的是增量训练的模型。

公式
\hat{y} = \text{mode/mean of } M \text{ base learners}

常见陷阱

  • 使用在训练开始前创建的保留测试集来评估在线Bagging——应改用预取(先测试后训练)评估,这是流式机器学习的标准。
  • 假设默认的基学习器数量(通常为10)足够;通常需要至少50-100个学习器的集成模型才能获得稳定的预测。
  • 忽略概念漂移:在没有漂移检测的情况下,在漂移流上部署在线Bagging会导致准确率的静默下降。
  • 在静态基准上将准确率与批量方法进行比较,并得出在线Bagging较差的结论——正确的比较是在流式基准上每看到一个实例的准确率。
  • 使用并非真正增量的基学习器(例如,重新训练的批量树),这会抵消在线框架的内存和速度优势。

常见问题

为什么是泊松(1)?

当n趋于无穷大时,均值为1的泊松分布近似了观测值在大小为n的bootstrap样本中出现的次数。每个学习器每个实例使用泊松(1)精确地复制了这种极限行为,使得在线近似在理论上是合理的。

在线Bagging与自适应随机森林有何不同?

自适应随机森林(Gomes等,2017)通过在每个分裂点添加随机特征子采样(类似于批量随机森林)并集成每个树的漂移检测器(当检测到概念漂移时重置单个学习器)来扩展在线Bagging。在线Bagging是更简单的基础;自适应随机森林是建立在其之上的当前最先进的流式集成模型。

应该使用哪个基学习器?

最常见的选择是Hoeffding树(也称为VFDT),它是典型的增量决策树。它使用Hoeffding界来决定在节点上看到多少数据足以进行分裂,从而使树无需存储过去实例即可进行更新。

需要多少个基学习器?

MOA框架中的实证基准测试表明,对于大多数流式任务,需要50-100个基学习器才能获得稳定的集成性能。较少的学习器会降低计算成本,但会增加预测方差,尤其是在流的早期阶段。

如何评估在线Bagging分类器?

使用预取评估:对于每个传入的实例,首先预测其标签,然后更新模型。准确率计算为正确预测的运行平均值。这避免了任何前瞻性偏差,并反映了真实的部署条件。

相关方法

参考文献

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    打开出版物文献
    已复制。
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    打开出版物文献
    已复制。