流式树集成中无标签分歧漂移检测的陷阱

# 基于未标记分歧的数据流树集成漂移检测的陷阱
来源：https://arxiv.org/html/2605.12803
Lara Sá Neves, Afonso Lourenço, Goreti Marreiros GECAD, ISEP, 波尔图理工学院, 葡萄牙 \{lspsn,fonso,mgt\}@isep\.ipp\.pt &Lizy K\. John 德克萨斯大学奥斯汀分校, 美国 ljohn@ece\.utexas\.edu

###### 摘要

在高速数据流中检测概念漂移仍然具有挑战性，特别是当模型必须在未标记数据上运行，并且需要避免由良性偏移引起的误报时。尽管基于分歧的不确定性在神经网络中显示出前景，但其在增量决策树（IDT）集成中的适应性仍未得到充分探索。我们通过集成成员中的标签翻转来构建批次特定的分歧度量，并评估其在表格数据流漂移检测中的有效性，从而研究这种方法。我们的实验表明，尽管该方法在多层感知器（MLP）集成中表现良好，但当应用于 IDT 时，其性能始终不如基于损失的检测器。我们将此归因于 IDT 固有的刚性：主要通过结构扩展进行学习，参数适应有限，这限制了模型的可塑性，并妨碍了分歧可靠地反映学习潜力。最近利用 IDT 固有的非重叠规则分解对其进行重构的工作，为提高适应性提供了一个有希望的方向。

## 1 引言

由于严重的概念漂移，处理高速数据流中的变化具有挑战性。有效的监控算法应满足（R1）在未标记的部署数据上运行以检测模型退化，以及（R2）对具有少量样本的非退化偏移具有抵抗力。虽然现有的基于数据的漂移检测器在未标记数据（R1）上表现良好（Xuan 等人，2021 (https://arxiv.org/html/2605.12803#bib.bib45)；Wan 和 Wang，2021 (https://arxiv.org/html/2605.12803#bib.bib46)），但它们在偏移是良性的（R2）时常常产生误报。许多方法跟踪分类器后验分布的变化（Lindstrom 等人，2013 (https://arxiv.org/html/2605.12803#bib.bib35)；Lughofer 等人，2016 (https://arxiv.org/html/2605.12803#bib.bib31)；Lu 等人，2025 (https://arxiv.org/html/2605.12803#bib.bib26)），这可以指示不确定性。然而，当模型持续适应演化的数据流时，此类估计可能不可靠。为了解决这个问题，我们提出批次特定的不确定性，这比顺序评估指标更实用。流式模型应关注当前分布下的可靠性，而不是假设的泛化能力。与转导推理类似，测量批次中冲突信息对模型的影响，而不是依赖累积的过去不确定性。

一个突出的例子是模型分歧框架（Yu 和 Aizawa，2019 (https://arxiv.org/html/2605.12803#bib.bib12)；Jiang 等人，2021 (https://arxiv.org/html/2605.12803#bib.bib11)；Rosenfeld 和 Garg，2023 (https://arxiv.org/html/2605.12803#bib.bib10)；Ginsberg 等人，2022 (https://arxiv.org/html/2605.12803#bib.bib15)）。迄今为止，它主要在大批量训练的、表达能力强的神经网络上进行了研究，但由于收敛缓慢、权重覆盖和有限的归纳优势（Sahoo 等人，2017 (https://arxiv.org/html/2605.12803#bib.bib21)），这些网络在表格数据流上表现不佳。对于表格数据，增量决策树（IDT）集成仍然是最先进的，它们利用快速的在线收敛和通过基于损失的漂移检测器进行树替换（Bifet 和 Gavaldà，2007 (https://arxiv.org/html/2605.12803#bib.bib37)；Gama 等人，2004 (https://arxiv.org/html/2605.12803#bib.bib19)），并通过自训练、无监督漂移检测和主动学习扩展到未标记数据（Gomes 等人，2025 (https://arxiv.org/html/2605.12803#bib.bib38)）。这提出了一个关键问题：分歧框架能否适用于基于树的流式集成？为了实现这一点，我们利用了在二分类中，为每个集成组件任意翻转标签可以创建多样化的、存在分歧的表示这一事实，这是一种设计真正的分歧批评者的简单而有效的方法（Rosenfeld 和 Garg，2023 (https://arxiv.org/html/2605.12803#bib.bib10)；Ginsberg 等人，2022 (https://arxiv.org/html/2605.12803#bib.bib15)；Pagliardini 等人，2022 (https://arxiv.org/html/2605.12803#bib.bib14)；Chuang 等人，2020 (https://arxiv.org/html/2605.12803#bib.bib13)）。令人惊讶的是，我们发现对于 IDT 集成，该策略在几乎所有评估的数据流上表现都很差，但对 MLP 则不然。我们假设 IDT 之间的分歧未能提供概念变化的可靠信号，这不是因为检测逻辑本身有缺陷，而是因为底层学习器缺乏分歧批评者捕捉其学习潜力所需的可塑性。

## 2 理论

对于漂移概念的数据流DiD\_\{i\}，学习器增量更新θt\\theta\_\{t\}以最小化在DtD\_\{t\}上的风险：

θt:=Algt\(θt−1,Lt\),Lt=∑i=1tE\(x,y\)∼Di\[l\(y,hθt−1\(x\)\)\]\.\\theta\_\{t\}:=\\text\{Alg\}\_\{t\}\(\\theta\_\{t\-1\},\\mathcal\{L\}\_\{t\}\),\\mathcal\{L\}\_\{t\}=\\sum\_\{i=1\}^\{t\}\\mathbb\{E\}\_\{\(x,y\)\\sim D\_\{i\}\}\[\\ell\(y,h\_\{\\theta\_\{t\-1\}\}\(x\)\)\]\.\(1\)存储所有过去的数据是不切实际的。基于树的学习器通过近似来解决这个问题，例如，使用霍夫丁界的增量信息增益，仅当最佳和第二佳分裂之间的差异显著时才进行扩展（Domingos 和 Hulten，2000 (https://arxiv.org/html/2605.12803#bib.bib43)）。这个操作可以描述如下：

引理 1（增量标记更新）。对于h∈Hh\\in\\mathcal\{H\}和历史模型hθt−1h\_\{\\theta\_\{t\-1\}\}：

εDt\(h\)=εDt\(h,hθt−1\)\+εDt\(hθt−1\)，\\varepsilon\_\{D\_\{t\}\}\(h\)=\\varepsilon\_\{D\_\{t\}\}\(h,h\_\{\\theta\_\{t\-1\}\}\)\+\\varepsilon\_\{D\_\{t\}\}\(h\_\{\\theta\_\{t\-1\}\}\)，\(2\)其中εDt\(h,hθt−1\)\\varepsilon\_\{D\_\{t\}\}\(h,h\_\{\\theta\_\{t\-1\}\}\)表示独热分歧。然而，在漂移的未标记分布下，这个界限是不够的。由于在真实数据流中进行手动标记不可行，有意义的误差界限需要分布距离的概念，例如HΔH\\mathcal\{H\}\\Delta\\mathcal\{H\}\-散度（Kifer 等人，2004 (https://arxiv.org/html/2605.12803#bib.bib18)）。

引理 2（基于漂移的更新）。假设一个能够区分Dt−1\\mathcal\{D\}\_\{t\-1\}和Dt\\mathcal\{D\}\_\{t\}的二元假设类别（Ben-David 等人，2010 (https://arxiv.org/html/2605.12803#bib.bib8)），即其HΔH\\mathcal\{H\}\\Delta\\mathcal\{H\}类包含所有成对异或：

εDt\(h\)≤εDt\(h,hθt−1\)\+εDt−1\(hθt−1\)\+12Δ\(hθt−1\)，\\varepsilon\_\{D\_\{t\}\}\(h\)\\leq\\varepsilon\_\{D\_\{t\}\}\(h,h\_\{\\theta\_\{t\-1\}\}\)\+\\varepsilon\_\{D\_\{t\-1\}\}\(h\_\{\\theta\_\{t\-1\}\}\)\+\\frac\{1\}\{2\}\\Delta\(h\_\{\\theta\_\{t\-1\}\}\)，\(3\)
请参考图注图 1：不同复杂度下的漂移检测：（左）基于损失的在过度正则化模型上的假阴性，（中）基于数据的在真正匹配模型复杂度上的假阳性，（右）两者在过于复杂的模型上都成功。虽然这个界限在实践中是空泛的，但它表明（1）hθt−1h\_\{\\theta\_\{t\-1\}\}的保守分裂和父超矩形充当了对hh的正则化器；（2）仅当hθt−1h\_\{\\theta\_\{t\-1\}\}位于Dt\\mathcal\{D\}\_\{t\}附近时偏差最小；并且（3）有用的漂移检测器必须同时考虑数据和模型复杂度（图1 (https://arxiv.org/html/2605.12803#S2.F1)）：如果Dt−1\\mathcal\{D\}\_\{t\-1\}/Dt\\mathcal\{D\}\_\{t\}相似，则界限很小，hθt−1h\_\{\\theta\_\{t\-1\}\}可以重用；否则，通过剪枝、重新生长或集成修改来更新hh。

这促使将误差相对于先前模型而不是整个假设类别进行界定，因为真实标签函数y∗y^\{\*\}和漂移分布Dt\\mathcal\{D\}t不是敌对的。因此，检测可以利用Δ\(hθt−1\)\\Delta\(h\_\{\\theta\_\{t\-1\}\}\)和替代假设来获得漂移下更实际的界限：

引理 3（基于分歧的更新）。设h∗=arg⁡maxh′∈H′⁡Δ\(hθt−1,h′\)h^\{\*\}=\\arg\\max\_\{h^\{\\prime\}\\in\\mathcal\{H\}^\{\\prime\}\\}\\\Delta\(h\_\{\\theta\_\{t\-1\}\},h^\{\\prime\}\)，其中H′\\mathcal\{H\}^\{\\prime\}是针对hθt−1h\_\{\\theta\_\{t\-1\}\}定义的：

εDt\(h\)≤εDt\(h,hθt−1\)\+εDt−1\(hθt−1\)\+12Δ\(hθt−1,h∗\)，\\varepsilon\_\{D\_\{t\}\}\(h\)\\leq\\varepsilon\_\{D\_\{t\}\}\(h,h\_\{\\theta\_\{t\-1\}\}\)\+\\varepsilon\_\{D\_\{t\-1\}\}\(h\_\{\\theta\_\{t\-1\}\}\)\+\\frac\{1\}\{2\}\\Delta\(h\_\{\\theta\_\{t\-1\}\},h^\{\*\}\)，\(4\)
请参考图注图 2：不同复杂度下基于分歧的漂移：（左）在远的输入空间中难以诱导，（中）均匀，（右）在欠正则化的远输入空间中容易诱导。虽然h∗h^\{\*\}难以处理，但它促使最大化Δ\(hθt−1,h′\)\\Delta\(h\_\{\\theta\_\{t\-1\}\},h^\{\\prime\}\)以识别受漂移影响最大的输入空间部分。在二元集成中，这可以简单到翻转标签（Rosenfeld 和 Garg，2023 (https://arxiv.org/html/2605.12803#bib.bib10)；Ginsberg 等人，2022 (https://arxiv.org/html/2605.12803#bib.bib15)）（图2 (https://arxiv.org/html/2605.12803#S2.F2)）：欠正则化的模型无法捕捉漂移，正确正则化的模型平衡分歧，过于复杂的模型会过拟合新区域。在保留εDt−1\(hθt−1\)\\varepsilon\_\{\\mathcal\{D\}\_\{t\-1\}\}\(h\_\{\\theta\_\{t\-1\}\}\)的同时利用这种差异允许功能正则化，而优雅的遗忘和剪枝过时节点可以提高适应性并释放容量。

## 3 方法

初始化集成

gg在历史数据

PP上；

while*流有新批次*do

Q′,R′←Q^\{\\prime\},R^\{\\prime\}\\leftarrow在

QQ，

RR中进行伪标签和翻转；

gQ,gR←g\_\{Q\},g\_\{R\}\\leftarrowgg的副本；

在

Q′Q^\{\\prime\}上训练

gQg\_\{Q\}，

在

R′R^\{\\prime\}上训练

gRg\_\{R\}；

for*每个集成gX∈\{gQ,gR\}g\_\{X\}\\in\\\{g\_\{Q\},g\_\{R\}\\\}*do

for*每个模型对\(ga,gb\)\(g\_\{a\},g\_\{b\}\)在gXg\_\{X\}中*do

da,b=1K∑i=1K1\[ga\(xi\)≠gb\(xi\)\]d\_\{a,b\}=\\frac\{1\}\{K\}\\sum\\limits\_\{i=1\}^\{K\}\\mathbf\{1\}\[g\_\{a\}\(x\_\{i\}\)\\neq g\_\{b\}\(x\_\{i\)\];

DX←D\_\{X\}\\leftarrow所有

da,bd\_\{a,b\}的集合；

if*KS\_test\(DQ,DRD\_\{Q\},D\_\{R\}\)拒绝H0H\_\{0\}*then

检测到漂移；

算法 1分歧框架对于每个批次，数据被分成两个连续的子窗口，QQ和RR。集成gg的两个副本，记为gQg\_\{Q\}和gRg\_\{R\}，被训练为与过去的分布PP保持一致，同时分别暴露于伪标记的QQ和RR的翻转版本（图3 (https://arxiv.org/html/2605.12803#S3.F3)）。基学习器之间的成对分歧形成分布DQD\_\{Q\}和DRD\_\{R\}，捕捉新数据对预测一致性的影响。使用DQD\_\{Q\}和DRD\_\{R\}之间的 Kolmogorov-Smirnov（KS）检验来检测显著的概念漂移。QQ–RR分割自然地平衡了收敛和检测延迟，因为过于小的窗口可能产生有噪声的估计。

请参考图注图 3：窗口化分歧。为了实现表达性适应，而不依赖会延迟检测的过大窗口，我们采用 Oza 的集成主干，其中泊松参数λ\\lambda控制重采样（Oza 和 Russell，2001 (https://arxiv.org/html/2605.12803#bib.bib24)）。然而，不使用λ=1\\lambda=1，而是在欠拟合情况下更积极地利用实例，使用λ\(ε\)=ελmax\\lambda\(\\epsilon\)=\\epsilon\\lambda\_\{\\max\}，其中ε∈⟨0,1⟩\\epsilon\\in\\langle 0,1\\rangle表示当前误差（Korycki 和 Krawczyk，2022 (https://arxiv.org/html/2605.12803#bib.bib25)）。从而加速收敛到更可靠的估计。

## 4 实验

我们评估了 IDT 和 MLP 集成，包含 6 种基于损失的：HDDMA&W（Pesaranghader 和 Viktor，2016 (https://arxiv.org/html/2605.12803#bib.bib41)），ADWIN（Bifet 和 Gavaldà，2007 (https://arxiv.org/html/2605.12803#bib.bib37)），PH（Mousset 等人，2004 (https://arxiv.org/html/2605.12803#bib.bib20)），DDM（Gama 等人，2004 (https://arxiv.org/html/2605.12803#bib.bib19)），EDDM（Baena-García 等人，2006 (https://arxiv.org/html/2605.12803#bib.bib44)）；以及 5 种基于数据的：BNDM（Xuan 等人，2021 (https://arxiv.org/html/2605.12803#bib.bib45)），CSDDM（Wan 和 Wang，2021 (https://arxiv.org/html/2605.12803#bib.bib46)），D3（Sethi 和 Kantardzic，2015 (https://arxiv.org/html/2605.12803#bib.bib39)），IBDD（Souza 等人，2020 (https://arxiv.org/html/2605.12803#bib.bib40)），OCDD（Gözüaçık 和 Can，2021 (https://arxiv.org/html/2605.12803#bib.bib47)）。

请参考图注图 4：评估指标：检测窗口。

我们使用了来自 7 个 SOA 生成器的 12 个合成数据流：SEA（旋转边界）、Hyperplane（10 个特征）、Stagger（特征分布变化）、Anomaly Sine（上下文漂移）、RBF（质心偏移）和 Agrawal（分类变化）。每个数据流包含 90,000 个实例，其中有 5 个 15,000 实例的漂移，包括突然的和重复的。我们采用顺序评估并报告平均检测时间（MTD）、检测准确率（DA）和误报数（FA），将定义检测窗口之外的报警计为假阳性，对于突然漂移和逐渐漂移分别使用 7,500 和 9,000 个实例（图4 (https://arxiv.org/html/2605.12803#S4.F4)）。集成和漂移检测器（包括基于损失和基于数据的方法）的所有超参数都根据原始论文中的推荐范围进行设置，并使用加权最小-最大归一化进行调整：0\.5×DA\+0\.3×\(1−FA\)\+0\.2×\(1−MTD\)0\.5\\times\\text\{DA\}\+0\.3\\times\(1\-\\text\{FA\}\)\+0\.2\\times\(1\-\\text\{MTD\}\)。对于集成，我们使用以下基分类器：Hoeffding 树（Domingos 和 Hulten，2000 (https://arxiv.org/html/2605.12803#bib.bib43)）、Hoeffding Adaptive Tree（Bifet 和 Gavalda，2009 (https://arxiv.org/html/2605.12803#bib.bib42)）和 Extremely Fast Decision Tree（Manapragada 等人，2018 (https://arxiv.org/html/2605.12803#bib.bib2)）用于 IDT，以及标准前馈网络用于 MLP，所有集成配置为包含 100 个学习器。

虽然 MLP 集成表现出良好的行为，但来自 IDT 的基于分歧的不确定性在几乎所有评估的数据流上始终表现不佳（表1 (https://arxiv.org/html/2605.12803#S4.T1)）。它表现出显著延迟的检测，并且在某些设置中，出现了不可忽视数量的误报，特别是与基于损失的基线相比。这些结果表明，从 IDT 集成得出的分歧信号通常太弱或噪声太大，无法作为可靠的漂移指标。

表 1：逐渐（GG）和突然（AA）漂移的 MTD（FA）结果，其中⊗\\otimes表示基于分歧，⋄\\diamond表示基于数据，∇\\nabla表示基于损失的检测器。

## 5 结论

综合来看，我们的结果暗示了当前漂移研究中的一个基本限制：日益复杂的、依赖于模型的检测机制无法弥补刚性基学习器的缺陷。来自 IDT 的分歧估计未能提供概念变化的可靠信号，这不是因为检测逻辑本身有缺陷，而是因为底层学习器缺乏不确定性反映学习潜力所需的可塑性。IDT 凭借其少量可训练参数实现了快速的在线收敛，但这种效率是以严重的刚性为代价的。与通过参数更新和激活动态进行适应的 MLP 系统（Lourenço 等人，2025a (https://arxiv.org/html/2605.12803#bib.bib4)）不同，IDT 几乎完全依赖于由局部最优分裂决策驱动的不可逆结构增长，导致模型具有历史依赖性，并受制于过时的