大数据时代，各种应用领域都不断涌现出动态数据，涵盖网购、气象、舆情、智能城市以及病毒传播等方面. 相对于静态数据，这些数据以高速、实时、多变、难以预测为特点，通常被称为流数据^[1-3]. 流数据挖掘的目标是使学习模型更准确地预测数据分布变化，从而提高在线学习模型的性能.

概念漂移是流数据在现实世界中的一个重要特征，也是流数据分析挖掘不可避免的挑战之一，其典型特征是当环境发生变化时，数据分布也会相应改变^[4-5]. 然而，由于流数据分布变化方式的多样性，不同类型的概念漂移^[6-7]（如突变型和渐变型）会以多种方式发生，例如变化时间、速度和方式等方面都可能存在差异. 不同类型概念漂移的发生会直接影响模型性能，并导致性能不同程度的下降^[8-9].

现有的概念漂移处理方法大多基于集成学习，通过特定规则（如加权平均、组合投票等）组合训练好的分类器，以达到比单一学习器更出色的性能 ^[10-11]. 然而，当前相关研究大多集中在单一类别概念漂移上，对于不同类型概念漂移的适应性建模相对欠缺^[12]. 在概念漂移发生后，如何有效应用模型和合理调整学习器，以提高模型的稳定性和适应性，依然是一个亟待解决的问题.

为解决上述问题，本文提出了一种弹性梯度集成的概念漂移适应方法. 该方法采取先检测后适应的策略，首先计算流动残差比检测漂移位点，之后利用残差波动率识别漂移类型；随后，根据梯度损失特征提取漂移学习器，结合漂移类型与残差分布特征，采取弹性梯度剪枝策略删除漂移学习器以提高模型稳定性；最后，通过计算最优拟合率优化学习器拟合过程，并结合滑动采样方法，采取增量梯度生长策略增量更新学习器以提高模型适应性. 本文工作的主要贡献有3点：

1）通过探测流动残差比与残差波动率，判断残差稳定程度，为集成模型识别不同类型概念漂移提供了一种可行方案；

2）通过分析梯度损失特征提取漂移学习器，并对其进行弹性梯度剪枝以提高模型的稳定性；

3）通过滑动采样数据优化学习器拟合过程，增量更新学习器以提高模型的适应性.

1.   相关工作

目前，已有较多文献对含概念漂移的流数据挖掘问题进行了研究，根据是否对概念漂移的发生进行检测，大致可分为基于主动检测的概念漂移处理方法与基于被动自适应的概念漂移处理方法.

基于主动检测的概念漂移处理方法将概念漂移检测融入模型中，通过对学习模型的性能指标进行监测来判断是否发生概念漂移，当检测到概念漂移发生时对模型做出相应调整. 常见的主动检测方法通常使用滑动窗口技术来实现，其通过将数据流划分为固定大小的窗口，利用窗口的滑动来判断是否有概念漂移发生. ADWIN^[13]通过滑动窗口保存最新数据，利用2个子窗口内样本的均值差异来检测概念漂移. DDM（drift detection method）^[14]通过监测窗口中分类误差的置信度和误差标准差来检测概念漂移. CD-TW^[15]通过对比历史窗口与实时窗口的数据分布变化来检测漂移，并依靠时间步长识别概念漂移类型. EOCD（ensemble optimization for concept drift）^[16]将遗忘机制与DDM方法结合，当检测到概念漂移时，通过删除较长的旧概念以减少性能损失. DAWIDD（dynamic adapting window independence drift detection）^[17]利用滑动窗口进行样本的保存与删除，结合样本独立性测试检测概念漂移. OCDD（one-class drift detector）^[18]方法使用带滑动窗口的单类学习器实现了无监督问题的概念漂移检测. SNDC（self-adaption neighborhood density clustering）^[19]方法通过比较相邻数据块聚类的相似性检测概念漂移，随后调整聚类中心点适应概念漂移. 基于主动检测的概念漂移处理方法有助于学习模型及时发现漂移并触发模型更新，但当漂移检测出现误检或漏检时，模型容易错误更新，导致模型性能下降.

基于被动自适应的概念漂移处理方法不检测数据流中是否存在概念漂移，其通过不断调整学习器来适应数据分布的变化. 在被动自适应方法中，基于集成学习的处理方式较为常见，其根据学习单元大小分为基于数据块的集成和在线集成. 基于数据块的集成是一种对固定数量的输入实例进行处理的方法. SEA（streaming ensemble algorithm）^[20]在连续的数据块上构建分类器，再使用启发式替换策略对分类器进行集成. ACDWM（adaptive chunk-based dynamic weighted majority）^[21]为每个数据块构建单独的分类器，根据其在当前数据块上的性能动态加权. SEOA（selective ensemble-based online adaptive deep neural network）^[22]根据每个分类器的损失将神经网络不同层次的自适应密度单元作为集成的基分类器进行动态加权. EnHAT（ensemble combined with Hoeffding adaptive tree）^[23]将霍夫丁自适应树算法与基于数据块生成的决策树集成相结合，以在更短时间内适应概念漂移. 在线集成方法是一种对样本进行逐一处理的增量学习方法. OAUE（online accuracy updated ensemble）^[24]在增量更新的基础上提出一种具有成本效益的分量权重函数，以估计分类器的误差. AUE2（accuracy updated ensemble）^[25]将基于精度的加权机制与霍夫丁树的增量特性结合，以改善集成对不同类型概念漂移的反应. OnlineBagging^[26]将在线学习与Bagging^[27]方法结合，并通过权重分配机制调整不同学习器的权重. DSEL（dynamic ensemble selection）^[28]基于Bagging方法将数据预处理与动态集成选择结合，提高了对模型复杂数据流的有效性. OneNet（online ensembling network）^[29]将指数梯度下降方法与离线强化学习结合，动态调整模型权重，提高了概念漂移的适应速度. 基于被动自适应的概念漂移处理方法不会受到漂移检测过程中漏检或误检的影响，但由于需要根据模型性能逐步更新模型，故模型效率较低.

本文提出了一种弹性梯度集成的概念漂移适应方法. 与传统方法相比，该方法通过探测梯度提升残差变化，实现了对不同概念漂移类型的识别，根据不同漂移类型特征，采取弹性梯度剪枝与增量梯度生长，有针对性地更新模型，提高了模型在不同类型概念漂移中的泛化性能.

2.   弹性梯度集成的概念漂移适应方法

本文提出了一种弹性梯度集成的概念漂移适应方法，模型总体结构如图1所示. 在漂移类型检测阶段，首先利用梯度提升残差变化特征计算流动残差比，检测概念漂移位点，再计算残差波动率判断残差变化幅度识别漂移类型. 在弹性梯度剪枝阶段，首先利用学习器损失变化特征提取漂移学习器，再结合不同漂移类型与残差分布特征删除合适的漂移学习器，提高模型的稳定性. 在增量梯度生长阶段，结合增量学习方法，利用滑动采样数据计算最优拟合率，以优化学习器拟合过程，同时根据残差变化动态增量更新学习器，提高模型的适应性.

图  1  EGE_CD模型总体结构

Figure  1.  Overall structure of EGE_CD model

下载: 全尺寸图片 幻灯片

2.1   漂移类型检测

数据序列可以用时间步长划分，因此，流数据可以被形式化为

其中${x_i}$是对应时刻的样本实例，${y_i}$是该样本实例对应的标签. 假设流数据中数据的联合概率分布表示为$P({\boldsymbol{x}},{\boldsymbol{y}})$，若在时刻$t$，流数据的概率分布发生变化，即${P_{t - 1}}({\boldsymbol{x}},{\boldsymbol{y}}) \ne {P_t}({\boldsymbol{x}},{\boldsymbol{y}})$，则该时刻发生了概念漂移. 其中， $\boldsymbol{x}=(x_i)_{i=1}^t$.

为根据不同漂移类型调整模型，首先需要检测漂移位点并识别漂移类型，本文通过计算流动残差比检测漂移位点，其次通过计算残差波动率识别漂移类型. 梯度提升残差作为梯度提升模型^[30]更新的重要指标，伴随模型的更新生成，梯度提升模型${F_m}$象征着$m$个学习器的集成，第$m$轮梯度提升模型的更新可以表示为

学习器${h_m}({\boldsymbol{x}})$正是对${F_{m - 1}}({\boldsymbol{x}})$与真实标签${\boldsymbol{y}}$之间差异的拟合结果，其主要依靠拟合第$m$轮样本${x_i}$的梯度提升残差形成，残差的计算方法为：

因本文损失函数采用平方损失计算，则模型损失$l({y_i},{F_{m - 1}}({x_i})) = \dfrac{1}{2}{\left({y_i} - \displaystyle\sum\limits_{j = 1}^{m - 1} {{h_j}({x_i})} \right)^2}$，此时残差可以化简为${r_m}({x_i}) = {y_i} - {F_{m - 1}}({x_i})$. 所得残差将作为新的样本标签，用于生成新的学习器. 因此，在模型的预测过程中，可通过提取所有学习器的残差计算模型残差，其可反映数据分布变化对模型的影响. 模型整体残差可表示为

其中$M$为模型中学习器的总数. 给定初始梯度提升模型${F_M}({\boldsymbol{x}})$，其训练过程中可得初始模型残差为$\widetilde R$，在$s$个连续的数据块$\{ {D_1},{D_2}, … ,{D_s}\}$上，可得对应模型残差为$\{ {R_1},{R_2}, … ,{R_s}\}$，则流动残差比可表示为

若${p_i}$满足${p_i} > \tau$（$\tau$为漂移位点探测参数），则将$i$作为概念漂移起始位点输出，反之继续进行检测，直到找到满足${p_i} > \tau$的数据块时停止检测.

假设第b个数据块${D_b}$处发生概念漂移，残差大幅度增加. 若漂移类型不同，残差变化幅度也会存在明显差异. 因此本文将数据块${D_b}$后$n$个模型残差的标准差作为残差波动率来识别漂移类型，其计算方法如式（6）所示.

其中$\overline R$为${D_b}$后$n$个模型残差的平均值，${\sigma _R}$可以反映不同数据块上残差的变化幅度. 若${\sigma _R} > \delta$（$\delta$为漂移稳定性探测参数），则残差变化幅度过大，识别此次漂移为突变型，否则识别此次漂移为渐变型. 漂移类型检测过程如图2所示.

图  2  漂移类型检测过程

Figure  2.  Drift type detection process

下载: 全尺寸图片 幻灯片

2.2   弹性梯度剪枝

当出现不同类型漂移时，模型泛化性能也会存在差异，为减小不同类型漂移对模型的影响，本节提出了一种弹性梯度剪枝方法. 该方法利用梯度提升模型中学习器的损失变化特征提取漂移学习器，结合漂移类型与残差分布特征，采取不同剪枝策略以删除合适的漂移学习器，提高模型稳定性. 模型弹性梯度剪枝过程如图3所示.

图  3  弹性梯度剪枝过程

Figure  3.  Elastic gradient pruning process

下载: 全尺寸图片 幻灯片

在梯度提升模型中，伴随学习器的迭代更新，学习器损失应满足${l_{m + 1}} - {l_m} \leqslant 0$，但当发生概念漂移时，部分学习器受漂移影响，会使本应下降的损失增加. 假设数据块${D_b}$处发生概念漂移，若学习器${h_m}$与${h_{m - 1}}$损失满足：

则${h_m}({\boldsymbol{x}})$是漂移学习器. $E\left( {l_m^b} \right)$为学习器${h_m}$在数据块${D_b}$上损失的期望. 当发生不同类型漂移时，漂移学习器的个数不同，因此为提高模型在不同漂移类型下的稳定性，需采取针对性的剪枝策略对模型进行调整.

当数据块${D_b}$处发生突变型概念漂移时，数据分布迅速变化，新的数据分布持续很长时间，模型残差大幅度上升，学习器残差分布满足$\displaystyle\sum\limits_{m = 1}^M {\mathbb{I}({r_m} > {R_{b - 1}})} > \frac{M}{2}$. 此时，漂移学习器数量较多，旧模型已不再适用，需删除所有学习器，并使用漂移数据${D_b}$训练新的梯度提升模型. 突变型漂移剪枝策略可表示为

其中$k = M$，此时在数据块${D_{b + 1}}$处的模型损失为

当数据块${D_b}$处发生渐变型概念漂移时，数据分布缓慢变化，模型残差在一段时间内持续小幅度上升，学习器残差分布满足$\displaystyle\sum\limits_{m = 1}^M {\mathbb{I}({r_m} > {R_{b - 1}})} \leqslant \frac{M}{2}$. 此时，漂移学习器数量较少，由梯度提升模型学习器迭代更新的特性可知，累积损失最小学习器${h_d}$后的学习器即为漂移学习器，因此为快速恢复模型稳定性，仅需删除${h_d}$后合适的$k$个学习器. 渐变型漂移剪枝策略可表示为

其中$k = \mathop {\arg \min }\limits_k {l_{b + 1}}({\boldsymbol{y}},{F_{M - k}}({\boldsymbol{x}}))(0 \leqslant k < M)$，此时在数据块${D_{b + 1}}$处的模型损失可表示为

2.3   增量梯度生长

在含概念漂移的流数据中，模型剪枝之后，其适应能力会出现一定程度的下降. 为使剪枝后的模型能够快速适应新的分布，本节在模型剪枝的基础上引入学习器的增量更新，利用滑动采样方法更新学习器训练数据，通过计算最优拟合率优化学习器拟合过程，再结合漂移类型变化调整增量学习器个数，实现模型的增量梯度生长，提高模型的适应性. 模型增量梯度生长过程如图4所示.

图  4  增量梯度生长过程

Figure  4.  Incremental gradient growth process

下载: 全尺寸图片 幻灯片

模型首先利用滑动窗口${w_{\text{s}}}$抽取实时漂移数据作为滑动采样数据${D'_{{w_{\text{s}}}}} = \{ ({x'_i},{y'_i})\} _{i = 1}^{{w_{\mathrm{s}}}}$，之后使用剪枝后的模型${F_{{\text{pru}}}}({\boldsymbol{x}})$计算最优拟合率$\theta$，并更新增量学习数据为$\{ ({x'_i},\theta {r_c}({x'_i}))\} _{i = 1}^{{w_{\mathrm{s}}}}$，最优拟合率可表示为

其中$M'$为剪枝后学习器的个数，${h_m}({\boldsymbol{x}}';\theta )$为剪枝后的学习器. 使用增量学习数据训练学习器，可得增量学习器为

其中${\hat a_{cj}}$为增量学习器的叶节点，$J$为叶节点的个数，$I$为固定的叶节点学习率，${\hat R_{cj}}$为对应的叶节点区域. 然而，单个学习器难以适应不同漂移类型，因此需针对不同漂移类型制定合适的增量梯度生长策略.

当数据块${D_b}$处发生突变型概念漂移时，由于此时残差变化幅度较大，新数据持续时间较长，剪枝后的模型仍不能快速拟合残差至正常水平，此时需在剪枝模型的基础上训练$M$个增量学习器以快速拟合残差. 突变型漂移增量梯度生长策略可表示为

此时在数据块${D_{b + 1}}$处的模型损失可表示为

当数据块${D_b}$处发生渐变型概念漂移时，由于此时残差增长幅度小、上升时间长，与突变型漂移对比，残差容易拟合，此时仅需在剪枝模型的基础上将模型增量生长至$M$个学习器，即训练$k$个增量学习器以持续拟合残差. 渐变型漂移增量梯度生长策略可表示为

此时在数据块${D_{b + 1}}$处的模型损失可表示为

2.4   算法实施流程

本文提出一种弹性梯度集成的概念漂移适应方法，该方法首先计算流动残差比检测漂移位点，再计算残差波动率识别漂移类型. 之后在弹性梯度剪枝阶段，利用学习器损失提取漂移学习器，针对不同漂移类型，删除对应的漂移学习器，以提高模型稳定性；在增量梯度生长阶段，采用滑动窗口抽取漂移数据，计算最优拟合率，优化学习器拟合过程，再针对不同漂移类型，调整增量学习器个数，以提高模型适应性.

算法1. 弹性梯度集成的概念漂移适应算法.

初始化：数据流$SD = \{ {D_1},{D_2}, … ,{D_t}, … \}$，初始梯度提升模型${F_M} = \{ {h_1},{h_2}, … ,{h_M}\}$，初始模型残差$\widetilde R$，漂移稳定性探测参数$\delta$，漂移位点探测参数$\tau$.

① while流数据$SD$未结束

② 第$t$个位点对应数据块${D_t}$进入；

③ 采用${F_M}$中的每个基学习器${h_i}$对当前样本预 测，根据式（4）计算模型残差${R_t}$；

④ 根据式（5）计算流动残差比${p_i}$；

⑤ if ${p_i} > \tau$ /*发生概念漂移*/

⑥ 根据式（6）计算模型残差波动率${\sigma _R}$；

⑦ if ${\sigma _R} > \delta$ /*发生突变型概念漂移*/

⑧ 模型剪枝更新：

$F_{{\text{pru}}}^{{\text{SU}}}({\boldsymbol{x}}) \leftarrow {F_{M - k}}({\boldsymbol{x}}) + {F'_M}({\boldsymbol{x}})$；

⑨ 根据式（12）计算最优拟合率$\theta$；

⑩ 模型增量生长：

$F_{{\text{in}}}^{{\text{SU}}}({\boldsymbol{x}}) \leftarrow F_{{\text{pru}}}^{{\text{SU}}}({\boldsymbol{x}}) + {\hat F_M}({\boldsymbol{x}})$；

⑪ else /*发生渐变型概念漂移*/

⑫ 查找累积损失最小学习器${h_d}$；

⑬ 计算学习器剪枝个数：

$k = \mathop {\arg \min }\limits_k {l_{b + 1}}({\boldsymbol{y}},{F_{M - k}}({\boldsymbol{x}}))$；

⑭ 模型剪枝更新：

$F_{{\text{pru}}}^{{\text{GR}}}({\boldsymbol{x}}) \leftarrow {F_{M - k}}({\boldsymbol{x}})$；

⑮ 根据式（12）计算最优拟合率$\theta$；

⑯ 模型增量生长：

$F_{{\text{in}}}^{{\text{GR}}}({\boldsymbol{x}}) \leftarrow F_{{\text{pru}}}^{{\text{GR}}}({\boldsymbol{x}}) + {\hat F_k}({\boldsymbol{x}})$；

⑰ end if

⑱ end if

⑲ 在${D_{t + 1}}$上进行测试，得到实时精度与模型 损失；

⑳ end while

2.5   模型复杂度分析

假设训练一个学习器的时间复杂度为$O(h) = O(en\log (n))$，其中$e$是特征数量，$n$是训练集的大小. 由于梯度提升模型利用之前所有学习器的残差进行后续训练，因此$M$个学习器的梯度提升模型的时间复杂度为$O(Mh)$. 因梯度提升残差在模型训练过程中获取，故流动残差比与残差波动率伴随模型更新计算可得，其时间复杂度均为$O(1)$，因此漂移类型检测过程的时间复杂度为$O(1)$. 当发生突变型概念漂移时，弹性梯度剪枝过程中删除$M$个学习器以及训练新的梯度提升模型的时间复杂度为$O(M + Mh)$，增量梯度生长过程利用滑动采样数据块训练$M$个增量学习器的时间复杂度为$O(Mh')$，其中$O(h') = O(en'\log (n'))$，$n'$为滑动采样数据块的大小. 当发生渐变型概念漂移时，弹性梯度剪枝过程中删除$k$个学习器的时间复杂度为$O(k)$，增量梯度生长过程训练$k$个增量学习器的时间复杂度为$O(kh')$. 由此可得，模型的整体运行时间复杂度可表示为

其中$\;\beta \in \{ 0,1\}$，当发生突变型概念漂移时，$\;\beta = 1$，发生渐变型概念漂移时，$\;\beta = 0$. 经分析可得，与传统在线学习模型发生漂移便重新训练整体模型的概念漂移适应方法相比，本文方法在时间复杂度上具有明显优势. 此外，通过滑动采样技术与增量学习策略，本文方法能够在面对大规模数据流时，保证较高计算效率的同时有效利用数据信息，使模型保持良好的泛化性能.

3.   实验分析

为验证本文提出的EGE_CD方法的有效性，本文在具有不同类型概念漂移的标准数据集和真实数据集上进行实验，并从精度、鲁棒性以及收敛性这3个方面进行评价. 实验平台为Windows10操作系统，CPU为酷睿i7-3，2 GHz内核，内存为8 GB，本方法采用Python 3.7的环境编写和运行.

3.1   实验数据

为了检验算法对不同类型概念漂移的处理能力，本文使用大规模在线分析（massive online analysis，MOA）平台^[31]中的流数据生成器产生了6个具有突变式、渐进式以及增量式的概念漂移数据集，除此之外，本文还选取了3个真实数据集，具体的数据集信息如表1所示.

表  1  数据集信息

Table  1.  Datasets Information

数据集	实例数	维度	类别数量	漂移类型	漂移数量	漂移位点
RBFblips_su	100×103	10	2	突变型	3	25×103, 50×103, 75×103
RBFblips_gr	100×103	10	2	渐变型	3	25×103, 50×103, 75×103
Hyperplane_su	100×103	10	2	突变型	3	25×103, 50×103, 75×103
Hyperplane_gr	100×103	10	2	渐变型	3	25×103, 50×103, 75×103
Sea_su	100×103	3	2	突变型	3	25×103, 50×103, 75×103
Sea_gr	100×103	3	2	渐变型	3	25×103, 50×103, 75×103
Electricity	45.3×103	8	2
Spam	9.3×103	500	2
Weather	25.6×103	8	2

下载: 导出CSV 

| 显示表格

3.2   评价指标

为验证所提出的方法EGE_CD的性能，本节从模型的精度、收敛性及鲁棒性等方面进行了分析，具体指标有4个.

1）平均实时精度（average real accuracy，Avgracc）. 表示模型在每个时间步的实时精度的平均值, 该指标用于反映模型的整体分类性能. 其定义为：

其中$T$表示总的时间步数，${n_t}$表示时间步$t$内正确分类的样本数，${D_t}$表示样本块大小.

2）累积精度（cumulative accuracy，Cumacc）. 表示模型到当前时刻的累积预测正确样本数和总样本数的比值，该指标用于反映模型过去所有时刻的整体性能. 其定义为：

其中${T_t}$表示当前累积的时间步数.

3）收敛速度（recovery speed under accuracy，RSA）. 表示模型在概念漂移发生后实时精度恢复到稳定所需要的时间步数$step$与恢复过程中模型平均错误率$avge$的乘积. 其定义为：

由于模型在不同概念漂移类型的数据集上性能波动变化不同，本文采用漂移位点后的$K$个参照点的精度差异来判断该点是否为收敛点. 若$K$个参考点的精度差异小于阈值$\varepsilon$，且$K$个参照点的前半部分和后半部分差异也小于$\varepsilon$，则该位点为收敛位点. 其定义为：

其中$ac{c_t} = \dfrac{{{n_t}}}{{{D_t}}}$，漂移恢复率越小表明模型能越快恢复到漂移前的性能.

4）鲁棒性（robustness，ROB）^[32]. 表示模型的稳定性与泛化性能的好坏. 本文在平均实时精度上分析了不同算法的鲁棒性，其定义为：

其中$Avgrac{c_{{A}}}(D)$表示算法${{A}}$在数据集$D$上的平均实时精度，${\text{min }}Avgracc(D)$表示在数据集$D$上所有算法中的最小平均实时精度. 鲁棒性值越大，说明模型越稳定.

3.3   参数设置

1）模型子树边界$M$. 实验中采用CART回归树作为基学习器来构建梯度提升模型. 由于本文在对模型更新过程中采用增量生长来提高模型适应性，$M$限制了模型增量生长的范围，因此，本文选取$M \in \{500, 1 000,\ 1 500,\ 2 000,\ 2 500\}$进行讨论，得到了在不同$M$下的模型性能差异.

2）数据块大小$w$. 过小的数据块上无法得到足够多数据的样本特征，训练的基学习器稳定性较差，而过大的数据块可能会包含概念漂移，影响模型的分类效果. 因本文采用的数据集实例数存在较大差异，所以将$w$统一设置为100.

3）漂移位点探测参数$\tau$与漂移稳定性探测参数$\delta$. 通过对实验中梯度提升残差的统计可以发现，不同漂移类型下残差波动率差异较为明显而流动残差比的最大值差异较小，因此结合实验所得残差数据，本文设置$\tau = 1.25$，$\delta = 0.01$.

3.4   实验结果与分析

为有效衡量EGE_CD方法的分类性能，本文选取OnlineBoosting^[26]，OneNet^[29]，DWM^[33]，Learn++.NSE^[34]，LeverageBag^[35]，OzaBaggingADWIN^[36]，OnlineRUSBoost^[37]在精度、收敛性和鲁棒性3个方面进行对比实验和结果分析.

3.4.1   精度结果和分析

本节首先分析了在不同模型子树边界$M$下模型的表现性能. 表2展示了EGE_CD方法在不同参数下的平均实时精度. 可以看出，当模型子树边界达到1 000时，模型的平均实时精度相对较高. 当$M$继续增加时，模型在复杂度增加的同时，也因为较大集成模型的过拟合问题导致模型性能出现一定程度的下降. 而当模型子树边界降低时，模型复杂度减小，模型易出现欠拟合问题，进而无法更好地适应概念漂移数据. 因此，在后续的对比实验中，本文方法的模型子树边界$M$设置为1 000.

表  2  不同M下的平均实时精度

Table  2.  Average Real-Time Accuracy Under Different M

数据集	平均实时精度（排名）
	M=500	M=1 000	M=1 500	M=2 000	M=2 500
RBFblips_su	0.8382(3)	0.8389(1)	0.8386(2)	0.8375(4)	0.8369(5)
RBFblips_gr	0.7813(2)	0.7750(5)	0.7791(4)	0.7839(1)	0.7804(3)
Hyperplane_su	0.9164(3)	0.9174(1)	0.9157(4)	0.9154(5)	0.9167(2)
Hyperplane_gr	0.8815(4)	0.8825(2)	0.8833(1)	0.8822(3)	0.8808(5)
Sea_su	0.8396(3)	0.8397(2)	0.8392(4)	0.8378(5)	0.8404(1)
Sea_gr	0.8249(4)	0.8251(3)	0.8249(5)	0.8252(2)	0.8256(1)
Electricity	0.8851(5)	0.8883(1)	0.8874(3)	0.8858(4)	0.8875(2)
Spam	0.9166(3)	0.9169(2)	0.9172(1)	0.9157(4)	0.9156(5)
Weather	0.8315(3)	0.8292(5)	0.8334(1)	0.8327(2)	0.8297(4)
平均排名	3.33	2.44	2.78	3.33	3.11
注：黑体数值表示最高平均实时精度.

下载: 导出CSV 

| 显示表格

表3展示了不同方法在各个数据集上的平均实时精度以及平均排名情况. 可以看出，在所有数据集上EGE_CD方法均能取得最好的模型性能. 在标准数据集与Electricity数据集上，EGE_CD方法与其他方法的性能差异较为明显，这是因为该方法将梯度提升模型的残差拟合与学习器的增量更新结合，使模型在数据量较大时能保持较好的预测性能. 结合整体排名来看，EGE_CD方法排名最高，这说明该方法能够提高模型在流数据中的适应性，具有较好处理不同类型概念漂移的能力.

表  3  不同方法在各数据集上的平均实时精度

Table  3.  Average Real-Time Accuracy of Different Methods on Each Dataset

数据集	平均实时精度（排名）
	OneNet	DWM	Learn++.NSE	LeverageBag	OnlineBoosting	OzaBaggingADWIN	OnlineRUSBoost	EGE_CD（本文）
RBFblips_su	0.8035(3)	0.5958(8)	0.6716(7)	0.7670(4)	0.7266(6)	0.8283(2)	0.7557(5)	0.8389(1)
RBFblips_gr	0.7509(3)	0.5749(8)	0.6477(7)	0.7193(5)	0.6860(6)	0.7567(2)	0.7086(4)	0.7750(1)
Hyperplane_su	0.8764(3)	0.8781(2)	0.8068(7)	0.7746(8)	0.8126(6)	0.8548(4)	0.8147(5)	0.9175(1)
Hyperplane_gr	0.8360(2)	0.8179(3)	0.7548(7)	0.7327(8)	0.7623(6)	0.8171(4)	0.7673(5)	0.8825(1)
Sea_su	0.8332(2)	0.7782(4)	0.7619(7)	0.7629(6)	0.7617(8)	0.8139(3)	0.7673(5)	0.8397(1)
Sea_gr	0.8232(2)	0.7722(4)	0.7523(8)	0.7545(6)	0.7543(7)	0.8086(3)	0.7610(5)	0.8251(1)
Electricity	0.8552(2)	0.8109(4)	0.8158(3)	0.6950(8)	0.7080(7)	0.7319(5)	0.7113(6)	0.8883(1)
Spam	0.9578(3)	0.9682(2)	0.9241(4)	0.8857(8)	0.8858(7)	0.9137(5)	0.8907(6)	0.9699(1)
Weather	0.8193(2)	0.8132(4)	0.7879(5)	0.7644(8)	0.7669(7)	0.8184(3)	0.7782(6)	0.8292(1)
平均排名	2.44	4.33	6.11	6.78	6.67	3.44	5.22	1
注：黑体数值表示最高平均实时精度.

下载: 导出CSV 

| 显示表格

图5展示了各个方法在所有数据集上的累积精度. 可以看出，在所有数据集上，EGE_CD方法的累积精度均高于其他方法. 这是由于该方法结合不同漂移类型对梯度提升模型进行适当剪枝与增量更新，使模型具有较强的稳定性与适应性.

图  5  不同方法在各数据集上的累积精度比较

Figure  5.  Comparison of cumulative accuracy of different methods on each dataset

下载: 全尺寸图片 幻灯片

本文利用Bonferroni-Dunn测试^[38]计算了所有方法两者之间的显著性差异. 若2种方法的秩和平均差值大于临界差$CD$，则这2种方法的性能存在显著差异.

其中${q_\alpha }$为显著水平$\alpha$下的临界值，$S$为方法个数，$N$为数据集个数，经计算可得，当$\alpha = 0.05$时，$CD = {\text{3}}{\text{.106\;1}}$. 不同方法的平均实时精度和最终累积精度的统计分析结果如图6所示. 其中，平均序值在一个临近值域内的方法用黑线连接. 结果表明，在统计意义上，本文所提的EGE_CD方法排名最好且具有明显优势.

图  6  不同方法平均实时精度和最终累积精度的Bonferroni-Dunn 检验结果

Figure  6.  Bonferroni-Dunn test results of average real-time accuracy and final cumulative accuracy of different methods

下载: 全尺寸图片 幻灯片

3.4.2   消融实验

为验证本文方法中弹性梯度剪枝与增量梯度生长结合的有效性，实验比较了EGE_CD在模型子树边界$M \in \{ 1{\text{ }}000,\ 1{\text{ }}500,\ 2{\text{ }}500\}$时采用弹性梯度剪枝（EGP）、增量梯度生长（IGG）和结合2种方法（EGP+IGG）的实时精度与累积精度. 由图7可以看出，在不同的模型子树边界下，若单独采用弹性梯度剪枝，模型在大部分数据集上表现最差，这是由于在模型剪枝后未能及时增加学习器，提高模型适应性，若单独采用增量梯度生长，模型表现虽有所提升但仍明显弱于EGE_CD. 结果表明，在不同的模型子树边界下，EGE_CD均取得了良好的泛化性能，有效验证了该方法的合理性.

图  7  不同M下3种方法的实时精度与累积精度比较

Figure  7.  Comparison of real-time accuracy and cumulative accuracy of three methods under different M

下载: 全尺寸图片 幻灯片

3.4.3   模型收敛性分析

当流数据发生概念漂移后，在线学习模型能否快速收敛到新的数据分布是衡量算法的重要指标. 表4展示了不同方法在已知漂移位点的6个数据集上的对应漂移位点处的收敛速度. 表4中每个方法对应数据集的3个值分别代表前、中、后3个位点的收敛速度. 从表4中可以看出，EGE_CD方法在多数情况下都具有较快的收敛速度，这是由于该方法在概念漂移发生后及时对模型进行弹性剪枝与增量生长，使模型能够在漂移发生后拥有较好的适应能力. 在整体排名中EGE_CD方法处于第1，说明该方法具有较快的收敛速度，收敛性能较好.

表  4  不同方法在各数据集上的收敛速度

Table  4.  Recovery Speed Under Accuracy of Different Methods on Each Dataset

数据集	OneNet	DWM	Learn++.NSE	LeverageBag
RBFBlips_su	2.73/1.77/3.06	3.39/24.89/18.52	6.27/1.99/4.43	2.76/4.02/8.62
RBFBlips_gr	2.09/1.18/1.79	6.28/1.56/3.57	2.49/9.82/5.18	1.08/1.38/2.73
Hyperplane_su	3.70/3.08/2.48	3.29/3.36/2.00	2.40/2.75/2.56	4.61/3.58/3.53
Hyperplane_gr	1.16/1.83/2.76	18.26/17.88/7.33	2.05/4.60/3.33	3.82/4.17/2.11
Sea_su	2.46/3.07/2.94	4.42/7.46/4.12	2.13/4.18/5.76	2.70/7.99/2.76
Sea_gr	1.15/1.67/1.96	1.75/2.31/2.67	0.96/3.86/2.69	3.75/5.93/2.39
平均排名	3.33	6.33	5.28	5.56
数据集	OnlineBoosting	OzaBaggingADWIN	OnlineRUSBoost	EGE_CD（本文）
RBFBlips_su	1.84/1.80/6.57	2.23/3.40/5.08	1.74/2.19/1.84	7.56/1.68/1.42
RBFBlips_gr	1.88/3.57/2.18	1.67/1.83/2.24	2.36/3.42/7.62	2.41/1.14/0.91
Hyperplane_su	1.61/1.49/1.79	8.10/8.59/1.98	2.59/2.54/2.82	0.96/2.05/2.46
Hyperplane_gr	3.26/3.45/4.64	3.35/1.05/5.26	2.58/3.86/2.72	1.56/0.51/0.34
Sea_su	2.84/2.80/6.33	3.88/2.80/4.17	1.43/2.48/2.34	2.74/2.46/0.93
Sea_gr	3.02/1.86/3.56	1.52/1.55/1.81	1.25/2.45/2.05	0.84/2.10/1.64
平均排名	4.33	4.56	4	2.33
注：数据集均包含前、中、后3个漂移位点，对应3个收敛速度；黑体数值表示最高收敛速度.

下载: 导出CSV 

| 显示表格

3.4.4   模型鲁棒性分析

为了衡量各个方法的算法稳定性，本节计算每个方法在各个数据集上的鲁棒性. 图8展示了计算结果，不同的小矩形高度代表的是算法在不同数据集上的鲁棒性值大小，每一列上的数值代表算法在所有数据集上的鲁棒性值总和，即该算法的整体鲁棒性. 可以看出，在多数情况下，EGE_CD方法的鲁棒性都能取得较好的排名，且整体鲁棒性最高，这说明该方法在含概念漂移的流数据中具有更强的鲁棒性，能够提高模型整体的稳定性.

图  8  不同方法的鲁棒性比较

Figure  8.  Comparison of robustness of different methods

下载: 全尺寸图片 幻灯片

4.   结束语

针对流数据中的不同类型概念漂移导致模型性能存在差异的问题，本文提出一种弹性梯度集成的概念漂移适应方法. 该方法利用流动残差比与残差波动率来检测不同类型概念漂移的发生；随后根据梯度损失变化提取漂移学习器，再结合不同漂移类型与残差分布，实现弹性梯度剪枝，提高模型稳定性；最后，结合增量学习方法，通过滑动采样数据计算最优拟合率，并根据残差变化实现增量梯度生长，提高模型适应性. 本文在9个具有不同漂移类型的数据集上进行了实验. 实验结果表明，与其他方法相比，本文方法在适应不同类型概念漂移方面具有显著优势，但可以发现，在发生剧烈的概念漂移时，本文方法的漂移恢复速度较慢，因此在未来工作中，将进一步研究提高在线学习模型收敛速度的方法，并探讨模型的可解释性，将其应用于存在多种概念漂移类型的实际问题中. 这将有利于解决概念漂移问题中在线学习模型收敛慢的问题，实现在线学习模型在更多漂移类型上的应用.

作者贡献声明：郭虎升提出思想，负责方法设计、论文写作及修改；张羽桐负责论文写作、代码实现、数据测试及论文修改；王文剑负责写作指导、论文的修改审定.