2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于主动−被动增量集成的概念漂移适应方法

祁晓博 陈佳明 史颖 亓慧 郭虎升 王文剑

祁晓博, 陈佳明, 史颖, 亓慧, 郭虎升, 王文剑. 基于主动−被动增量集成的概念漂移适应方法. 自动化学报, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c240503
引用本文: 祁晓博, 陈佳明, 史颖, 亓慧, 郭虎升, 王文剑. 基于主动−被动增量集成的概念漂移适应方法. 自动化学报, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c240503
Qi Xiao-Bo, Chen Jia-Ming, Shi Ying, Qi Hui, Guo Hu-Sheng, Wang Wen-Jian. Concept drift adaptive method based on active-passive incremental ensemble. Acta Automatica Sinica, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c240503
Citation: Qi Xiao-Bo, Chen Jia-Ming, Shi Ying, Qi Hui, Guo Hu-Sheng, Wang Wen-Jian. Concept drift adaptive method based on active-passive incremental ensemble. Acta Automatica Sinica, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c240503

基于主动−被动增量集成的概念漂移适应方法

doi: 10.16383/j.aas.c240503 cstr: 32138.14.j.aas.c240503
基金项目: 国家自然科学基金(62476157, U21A20513, 62076154, 62276157), 山西省专利转化专项计划项目(202302009, 202302012), 山西省基础研究计划(自由探索类)项目(20210302123334), 太原师范学院成果转化与技术转移基地(2023P003) 资助
详细信息
    作者简介:

    祁晓博:太原师范学院计算机科学与技术学院副教授. 主要研究方向为数据挖掘与机器学习. E-mail: xbqi@tynu.edu.cn

    陈佳明:太原师范学院计算机科学与技术学院硕士研究生. 主要研究方向为数据挖掘与机器学习. E-mail: chenjiaming1023@163.com

    史颖:山西大学计算机与信息技术学院博士研究生. 主要研究方向为图像处理与机器学习. E-mail: sy@tynu.edu.cn

    亓慧:太原师范学院计算机科学与技术学院教授. 主要研究方向为数据挖掘与机器学习. E-mail: qihui@tynu.edu.cn

    郭虎升:山西大学计算机与信息技术学院教授. 主要研究方向为数据挖掘与计算智能. E-mail: guohusheng@sxu.edu.cn

    王文剑:山西大学计算智能与中文信息处理教育部重点实验室教授. 主要研究方向为数据挖掘与机器学习. 本文通信作者. E-mail: wjwang@sxu.edu.cn

Concept Drift Adaptive Method Based on Active-passive Incremental Ensemble

Funds: Supported by National Natural Science Foundation of China (62476157, U21A20513, 62076154, 62276157), the Shanxi Province Patent Transformation Special Programs (202302009, 202302012), the Basic Research Program (Free Exploration) of Shanxi Province (20210302123334), and Taiyuan Normal University Achievement Transformation and Technology Transfer Base (2023P003)
More Information
    Author Bio:

    QI Xiao-Bo Associate professor at the School of Computer Science and Technology, Taiyuan Normal University. Her research interest covers data mining and machine learning

    CHEN Jia-Ming Master student at the School of Computer Science and Technology, Taiyuan Normal University. His research interest covers data mining and machine learning

    SHI Ying Ph.D. candidate at the School of Computer and Information Technology, Shanxi University. Her research interest covers image processing and machine learning

    QI Hui Professor at the School of Computer Science and Technology, Taiyuan Normal University. Her research interest covers data mining and machine learning

    GUO Hu-Sheng Professor at the School of Computer and Information Technology, Shanxi University. His research interest covers data mining and computational intelligence

    WANG Wen-Jian Professor at the Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University. Her research interest covers data mining and machine learning. Corresponding author of this paper

  • 摘要: 数据流是一组随时间无限到来的数据序列, 在数据流不断产生过程中, 由于各种因素的影响, 数据分布随时间推移可能以不可预测的方式发生变化, 这种现象被称为概念漂移. 在漂移发生后, 当前学习模型需要及时响应数据流中的实时分布变化, 并有效处理不同类型的概念漂移, 从而避免模型泛化性能下降. 针对这一问题, 提出了一种基于主动-被动增量集成的概念漂移适应方法(Concept drift adaptation method based on active-passive incremental ensemble, CDAM-APIE). 该方法首先使用在线增量集成策略构建被动集成模型, 对新样本进行实时预测以动态更新基模型权重, 有利于快速响应数据分布的瞬时变化, 并增强模型适应概念漂移的能力. 在此基础上, 利用增量学习和概念漂移检测技术构建主动基模型, 提升模型在平稳数据流状态下的鲁棒性和漂移后的泛化性能. 实验结果表明, CDAM-APIE能够对概念漂移做出及时响应, 同时有效提高模型的泛化性能.
  • 大数据时代, 数据流在医疗诊断、欺诈监测、气象预测等多个领域大量涌现[13]. 相较于传统的静态数据, 数据流通常以流的形式按时间顺序依次到达, 具有时序性、动态性、无限性、不可重现性等特点[46]. 数据流挖掘研究是为了使在线学习模型更好地应对实时数据流中的动态变化, 提高模型的适应性和泛化性能[7]. 概念漂移是数据流挖掘中常见的一种现象, 其典型特征是样本的输入特征和输出标签之间的关系会随时间发生不可预见的变化[811].

    概念漂移会使基于历史数据训练的学习模型难以适应当前的实时数据变化[1213]. 例如在信用卡欺诈检测中, 欺诈者更新一些伪装技术, 使欺诈特征随时间推移发生变化, 导致过去归为正常的交易记录可能在未来变成欺诈交易[14]; 在气象预测中, 相似的气温、压强、空气湿度等因素可能随季节变化造成不同的天气状况, 若模型更新不及时, 就会使当前的天气预测情况发生滞后[15]. 在工业生产及故障诊断领域, 工况或环境变化可能导致故障特征改变. 若故障诊断模型未能实时更新, 误诊和漏诊问题随时间累积, 可能引发生产中断、经济损失等问题. 因此, 在数据流挖掘中, 提高学习模型对概念漂移的适应能力, 维持其在数据变化下的准确性和有效性, 对于实际应用具有重要意义.

    目前, 处理概念漂移数据流的方法大致分为主动检测方法和被动自适应方法两类[16]. 主动检测方法通过监测模型的性能表现或数据变化判断概念漂移, 能够及时发现数据分布的变化, 迅速做出响应以保持模型的准确性, 但是可能会错误地将随机波动识别为概念漂移, 导致不必要的模型调整. 被动适应方法通过对模型的不断调整来适应概念漂移, 即使在数据分布缓慢变化的情况下也能保持较好的性能, 但可能会忽略重要信息, 并且鲁棒性较差. 集成学习是常用的被动适应方法, 通过特定的结合策略, 将基于不同时序数据的多个基模型集成为一个泛化能力更强、性能更优的模型, 并通过灵活的指标调整以有效适应概念漂移[1718]. 然而, 现有集成方法大多只能解决某一类型的概念漂移, 泛化能力不强, 对其他类型的概念漂移效果较差. 并且由于替换策略, 过拟合的基模型可能会替换掉泛化性能较好的基模型, 从而导致模型不稳定. 此外, 在概念漂移刚发生时, 集成模型中存在较多携带历史数据的基模型, 使模型难以迅速适应概念漂移.

    为了应对上述问题, 本文提出了一种基于主动−被动增量集成的概念漂移适应方法 (Concept drift adaptation method based on active-passive incremental ensemble, CDAM-APIE). 该方法采用在线增量集成策略和漂移检测方法, 构建了被动集成模型和主动基模型. 被动集成模型通过对数据块中的单一训练样本进行预测并动态调整基模型权重, 有利于对数据分布变化进行快速响应. 同时, 利用增量学习和概念漂移检测技术构建主动基模型, 提升模型在平稳数据流状态下的鲁棒性和漂移以后的泛化性能. 本文的主要贡献如下:

    1)通过实时调整权值, 周期性更新模型, 提高模型适应不同类型概念漂移的能力.

    2)主动方法与被动方法相结合, 提高模型对概念漂移的适应能力和泛化性能.

    3)使用增量学习方法, 缓解数据块大小对基模型性能的影响, 提高基模型的稳定性.

    针对数据流分类中的概念漂移问题, 目前已有很多研究成果, 常见的概念漂移方法可以分为两类, 即主动检测方法和被动适应方法. 在主动检测方法中, 通常使用概念漂移检测器监测分类器性能或窗口中数据分布的变化情况, 从而判断数据流是否处于稳定状态. 当检测指标超出设定阈值时, 则判断数据流不稳定, 模型做出相应调整以适应概念漂移. 例如Gama等[19]提出的概念漂移检测算法 (Drift detection method, DDM) 认为在稳定的数据流状态下, 随着训练数据增多, 学习模型的错误率会逐渐下降, 该方法通过检测当前总体错误率的增长情况判断概念漂移的发生. Hinder等[20]提出了动态适应窗口独立性漂移检测 (Dynamic adapting window independence drift detection, DAWIDD), DAWIDD通过滑动窗口管理数据样本, 并结合独立性测试来识别数据分布的变化, 从而检测概念漂移. Wen等[21]提出了自适应树状神经网络 (Adaptive tree-like neural network, ATNN), ATNN是一种多分支结构的自适应神经网络, 其通过概念漂移检测对网络进行调整, 确定何时添加新分支或激活旧分支, 以此适应概念漂移. 主动检测方法虽然在数据流平稳状态下效率较高, 但是在检测过程中可能会出现漏检、误检的情况, 导致模型错误更新.

    与主动检测方法相比, 被动适应方法不需要进行概念漂移检测, 而是通过对模型的不断调整来适应概念漂移[22]. 集成学习是常见的被动适应方法, 根据处理策略的不同分为两类: 一类是基于数据块的集成, 另一类是基于单样本的在线集成. 基于数据块的集成方式是每次对一整块数据进行批量学习和模型更新. 例如Street等[23]提出的一种基于数据块的数据流集成分类算法 (Streaming ensemble algorithm, SEA), SEA使用最新数据块构造基模型, 并依据特定的启发性规则, 对集成模型中表现最差的基模型进行替换, 从而适应概念漂移. 该方法中新训练的基模型在整个集成中可能被旧的基模型压制, 导致无法及时适应概念漂移. 基于此, Wang等[24]提出了一种基于准确率加权集成算法 (Accuracy weighted ensemble, AWE), AWE对基模型赋予权重, 根据基模型在最新数据块上的误差率对其加权, 提升了模型适应漂移的能力. Weinberg等[25]提出了一种结合霍夫丁自适应树的集成方法 (Ensemble combined with hoeffding adaptive tree, EnHAT), EnHAT结合了霍夫丁自适应树算法与基于数据块生成的决策树集成, 实现了对概念漂移的快速适应. 通过周期性更新模型, 基于数据块的集成方式虽然能够有效应对渐变漂移, 但是不能及时应对突变漂移, 并且其性能受限于数据块的大小. 数据块较小虽能应对部分突变漂移, 但可能导致过拟合; 数据块较大虽有机会获得更好的基模型, 但可能出现一个数据块蕴涵多种概念的情况. 基于单样本的在线集成方式是每次只对一个数据进行学习和模型更新. 例如Oza等[26]提出的Oza Bagging, 该算法对最新的数据进行$ k $次抽样, 并以此模拟数据流中的数据, $ k $的取值服从参数为1的泊松分布. Kolter等[27]提出一种动态加权多数投票算法 (Dynamic weighted majority, DWM). DWM依据基模型在最新样本上的分类结果动态调整其权值, 以提高应对突变漂移的能力. Guo等[28]提出了一种基于在线集成的概念漂移自适应分类方法 (Adaptive classification method for concept drift based on online ensemble, AC_OE), AC_OE将在线集成与增量学习结合, 提高了模型的整体泛化性能. 基于单样本的在线集成方式虽然能够及时应对突变漂移, 但是由于没有周期性更新, 对渐变漂移适应能力较差.

    本文结合在线集成、周期性更新策略以及概念漂移检测方法, 提出了CDAM-APIE. 该方法既利用在线集成方式更新权重, 使模型能够有效应对突变漂移, 又利用周期性更新策略提升模型对渐变漂移的适应能力. 此外, CDAM-APIE使用结合了概念漂移检测方法的增量基模型, 避免在平稳的数据流状态下持续更新基分类器造成的性能下降, 提升模型在平稳数据流状态下的鲁棒性和漂移以后的泛化性能.

    本文提出一种主动-被动增量集成的概念漂移适应方法, 整体框架如图1所示. 该方法首先通过连续捕获实例将数据流转换为一系列数据块, 然后分别采用被动集成模型和主动基模型进行训练更新, 被动集成模型通过在线集成策略进行构建, 主动基模型利用概念漂移检测方法进行增量训练, 最后将模型的两部分加权结合得到当前时刻的最终模型输出预测结果.

    图 1  CDAM-APIE整体框架图
    Fig. 1  The overall framework of CDAM-APIE

    数据流是指随时间不断变化、样本一个接一个到来, 具有实时性、连续性、不稳定性的数据序列[29], 可以表示为: $ S = \{s_1,\;s_2,\;\cdots,\;s_t,\;\cdots\} $, 其中, $ s_t = (x_t,\;y_t) $表示$ t $时刻的样本, $ x_t $表示$ t $时刻样本的特征向量, $ y_t $表示$ t $时刻样本的标签. 概念漂移是指底层数据分布发生变化, 假设数据流中的底层数据分布用联合概率分布, 表示为$ P(x,\;y) $, 若在时刻$ t $, 数据流发生了概念漂移, 可以表示为:

    $$ \begin{equation} \exists x:\quad P_{t-1}(x,\;y)\neq P_t(x,\;y) \end{equation} $$ (1)

    目前, 研究人员根据变化率将概念漂移分为四种类型: 突变漂移、渐变漂移、重复漂移和增量漂移[29]. 四种类型的概念漂移如图2所示.

    图 2  四种类型的概念漂移
    Fig. 2  Four types of concept drift

    数据流具有时序特性, 这与集成学习根据不同训练集构建基模型的机制高度契合, 且集成学习能够有效克服单一分类器在数据流挖掘中学习过多驳杂数据分布的问题. 因此, 在不同时间节点构建基模型并将其加入集成, 是数据流挖掘的一种有效方法. 在线学习方法能够实时更新模型参数, 具备良好的适应性, 通过不断对单一样本进行处理, 可以迅速适应动态变化的数据分布, 因此, 在线集成策略可以实现对概念漂移的快速响应. 此外, 增量学习可以解决由固定数据单元训练的基模型泛化性能差的问题. 因此, 本文使用在线集成策略先对单一样本进行预测, 然后根据预测结果更新基模型权重并进行增量学习, 以快速适应数据流变化.

    事实上, 在线集成策略中的权值更新能及时应对突变漂移, 但是对渐变漂移不太敏感. 因此本文采用实时更新权重, 周期性更新模型的方式应对突变和渐变类型的概念漂移, 一方面, 通过实时更新基模型权重快速适应突变漂移; 另一方面, 在固定的学习单元后替换性能较差的基模型, 使集成模型对渐变漂移有较好的效果, 同时也能在一定程度上替换因增量学习而获取到驳杂概念的基模型, 保持模型的稳定性. 具体地, 假设被动集成模型为$ H_P = \{(h_1,\;w_1),\;(h_2,\;w_2),\;\cdots,\;(h_s,\;w_s)\} $, 其中, $ s $表示集成模型中最大分类器数量, $ h_i $表示第$ i $个基模型, $ w_i $表示其对应的权重, 初始情况下, 每个基模型对应权重$ w_i = 1/s $. 假设数据流为$ SD = \{D_1,\;D_2, \;\cdots, D_t,\;\cdots\} $, 固定数据单元为数据块$ D_t $, 当时刻$ t $的新样本$ x^t_j\in D_t $输入后, 使用当前的被动集成模型中所有的基模型对其预测:

    $$ \begin{equation} \tilde{y_j^t} = h_i(x^t_j) \end{equation} $$ (2)

    若$ \tilde{y_j^t}\ne y_j^t $, 则将该分类器的权重根据式(3)作更新, 反之基模型权重保持不变.

    $$ \begin{equation} w_i = \beta\cdot w_i,\;\quad \beta\in(0,\;1) \end{equation} $$ (3)

    其中, $ \beta $表示权重衰退率, 若某个基模型预测错误, 那么其权重按照一定比率下降.

    在数据流中一旦发生概念漂移, 短时间内被动集成中大多数历史基模型的性能会显著下降, 导致其对应的权重急剧降低. 因此, 在所有基模型的权重更新完成后, 按照式(4)对权重进行标准化.

    $$ \begin{equation} w_i = \frac{w_i}{\sum\limits_{i = 1}^sw_i} \end{equation} $$ (4)

    当数据块$ D_t $中的全部样本处理完毕后, 进行基模型的替换更新. 具体来说, 在固定数据单元$ k $ = 100的数据块$ D_t $上训练构建新的基模型$ h_t $, 同时依照式(5)的选择标准, 查找在数据块$ D_t $上表现最差的基模型$ h_{\mathrm{bad}} $, 并用$ h_t $进行替换.

    $$ \begin{equation} h_{\mathrm{bad}} = \arg\max\limits_{h_i\in H_P}\frac{\sum\limits_{j = 1}^k h_i(x_j^t)\neq y_j^t}{k} \end{equation} $$ (5)

    由于$ h_t $基于最新数据块$ D_t $训练构建, 代表目前数据流中的最新数据分布, 所以我们赋予其最高的权重, 计算方法见式(6):

    $$ \begin{equation} w_t = \arg\max\limits_{w_i\in H_P}(w_i) \end{equation} $$ (6)

    被动集成模型的构建过程如图3所示.

    图 3  被动集成模型的过程
    Fig. 3  Process of passive incremental ensemble

    在被动集成模型中, 增量学习虽可以解决由固定数据单元训练基模型引起的泛化性能差的问题, 但也导致某些基模型在概念漂移期间学习到混合分布, 影响集成性能. 此外, 当数据流处于稳定状态时, 频繁替换基模型会导致部分代表性特征缺失, 使得模型的鲁棒性和泛化性能下降.

    针对以上问题, 本文构建了带有概念漂移检测方法的主动基模型. 当检测器发出警告信号时, 表示概念可能发生变化, 但还未达到漂移水平, 创建备用分类器并从当前数据位点开始学习, 同时让之前的历史模型也开始增量学习, 保证漂移发生时当前模型可以更快适应概念漂移. 当检测器发出漂移信号时, 表示此时已经达到漂移水平, 备用模型替代历史模型. 本文借鉴了DDM[19] 的思想, 假设数据是符合独立同分布的, 随着数据的输入和学习, 模型错误率不断下降. 警告阈值和漂移阈值分别如式(7)和式(8) 所示:

    $$ \begin{equation} p_i+s_i\geq\min(p)+2\cdot\min(s) \end{equation} $$ (7)
    $$ \begin{equation} p_i+s_i\geq\min(p)+3\cdot\min(s) \end{equation} $$ (8)

    其中$ p_i $为第$ i $个数据进入后的整体错误率, $ s_i $为第$ i $个数据进入后的整体标准差. $ \min(p) $和$ \min(s) $动态更新, 在$ t $时刻时, 若$ p_t+s_t $的值比当前的$ \min(p)+ \min(s) $小, 则使用$ p_t $和$ s_t $替换$ \min(p) $和$ \min(s) $; 当检测到概念漂移发生后, $ \min(p) $和$ \min(s) $重新取值. 主动基模型具体构建过程如图4所示.

    图 4  主动基模型的过程
    Fig. 4  Process of active base model

    当新样本进入时, 将上述两个模型集成为当前时刻的测试模型. 对新样本进行加权投票得到预测结果:

    $$ \begin{equation} H_t(x_j^t) = W_P\cdot H_P(x_j^t)+W_A\cdot H_A(x_j^t) \end{equation} $$ (9)

    设置两个模型的权重为$ W_P $和$ W_A $, 初始权重设置为0.5. 具体地, 当新样本进入时, 同时使用两种模型进行预测, 当使用被动集成模型$ H_P $进行预测时:

    $$ \begin{equation} H_P(x_j^t) = \sum\limits_{i = 1}^sw_i\cdot h_i(x_j^t) \end{equation} $$ (10)

    若$ H_P(x_j^t)\neq y_j^t $, 将当前的被动集成模型权重按式(3)作更新, 否则不作更新. 当使用主动基模型$ H_A $预测时, 若预测错误, 也按式(3)更新权重, 否则不作更新. CDAM-APIE如算法1所示.

      算法1. CDAM-APIE

    输入. 数据流$ SD = \{D_1,\;D_2,\;\cdots,\;D_t,\;\cdots\} $, 主动基模型$ H_A = \{H_a,\;W_A\} $, 权重衰减系数$ \beta $, 被动集成模型$ H_P = \{(h_1,\;w_1),\;(h_2,\;w_2)\cdots,\;(h_s,\;w_s),\;W_P\} $

    输出. 当前时刻的测试模型$ H_t = \{H_P,\;H_A\} $

    1) While (数据流$ SD $中$ t $时刻对应的数据块$ D_t $进入) do

    2)  While ($ D_t $中第$ j $个样本$ x^t_j $进入) do

    3)   $ H_t(x_j^t) = W_P\cdot H_P(x_j^t)+W_A\cdot H_A(x_j^t) $ // 使用当前时刻的集成模型预测

    4)    If ($ H_A(x_j^t)\neq y_j^t $)then

    5)    $ W_A = \beta\cdot W_A,\;\quad \beta\in(0,\;1) $ // 更新权重

    6)    End if

    7)   If ($ H_P( x_j^t)\neq y_j^t $) then

    8)     $ W_p = \beta\cdot W_p,\;\quad \beta\in(0,\;1) $ // 更新权重

    9)    End if

    10)    For ($ {h_i\subseteq H_P} $) do

    11)     If ($ H_i(x_j^t)\neq y_j^t $) then

    12)     $ w_i = \beta\cdot w_i,\;\quad \beta\in(0,\;1) $ // 更新权重

    13)    End if

    14)    $ h_i\gets x_j^t $ // 基于$ x_j^t $对$ h_i $增量学习

    15)    End for

    16)    $ w_i = w_i/\sum_{i = 1}^s w_i $ // 权重标准化

    17)    $ H_a\gets x_j^t $ // 基于$ x_j^t $对$ H_a $增量学习

    18)    If (发出概念漂移警告信号且没有备用模型$ H_b $) then

    19)    创建备用模型$ H_b $

    20)    $ H_b\gets x_j^t $ // 基于$ x_j^t $对$ H_b $增量学习

    21)   End if

    22)   If (发出概念漂移信号) then

    23)    使用$ H_b $替换$ H_a $

    24)   End if

    25)  End while

    26)  基于$ D_t $训练最新的基模型$ h_t $

    27)  If ($ H_P $中的基模型数量$ <s $) then

    28)   将最新的基模型$ h_t $加入$ H_P $

    29)  Else 使用$ h_t $替换$ h_{bad} $, 权重设置$w_t = $ $ \arg\max \nolimits_{w_i\in H_P}(w_i) $

    30)  End if

    31) End while

    CDAM-APIE的计算成本主要集中在基模型训练更新, 概念漂移检测和权重更新上.

    假设在大小为$ m $的数据集上训练1个基模型的时间复杂度为$ \mathrm{O}(f(m)) $, 在被动集成模型中, 训练并更新$ s $个基模型的时间复杂度为$ \mathrm{O}(sf(m)) $. 对数据集进行分类以调整其权重的时间复杂度与数据集大小呈线性关系, 即$ \mathrm{O}(ms) $. 将数据集划分为$ m/k $个大小为$ k $的固定数据单元时, 替换基模型的时间复杂度为$ \mathrm{O}(m/k) $, 这在计算总的时间复杂度时可以忽略不计.

    在主动基模型中, 概念漂移检测的时间复杂度为$ \mathrm{O}(m) $, 训练并更新模型的时间复杂度为$ \mathrm{O}(f(m)) $, 由于替换基模型需要经过概念漂移检测, 其发生的频率远小于$ \mathrm{O}(m) $, 因此可以忽略不计. 对两个模块进行加权集成的时间复杂度为$ \mathrm{O}(m) $.

    综上所述, CDAM-APIE的时间复杂度为$ \mathrm{O}(sf(m)+ms+m+f(m)+m) = \mathrm{O}(sf(m)+m) $.

    本文在包含不同类型的概念漂移数据集上进行实验, 实验方法采用python3.9编写和运行. 对比方法选取经典的基于数据块的分类算法、基于单样本的在线集成算法以及深度学习算法, 包括准确率加权集成算法 (Accuracy weighted ensemble, AWE)[24]、Oza Bagging算法[26]、动态加权多数投票算法 (Dynamic weighted majority, DWM)[27]、在线欠装袋算法 (Online under over bagging, OOB)[30]、基于在线集成的概念漂移自适应分类方法 (Adaptive classification method for concept drift based on online ensemble, AC_OE)[28]以及自适应树状神经网络 (Adaptive tree-like neural network, ATNN)[21].

    为了评估算法适应各种类型概念漂移的能力, 本文共使用了12个数据集, 其中10个数据集来源于文献[28], 包含了6个带有渐变、突变和增量类型概念漂移的合成数据集[28]和4个真实数据集[28], 另外, 本文还使用python3.9生成了2个具有重复漂移的合成数据集, 生成方式如下.

    Sea-re[23]: 每个样本的基本结构为$ \{ f_1,\;f_2,\;f_3,\; $ $ C\} $, 其中$ \{ f_1,\;f_2,\;f_3\} $为特征, 类别$ C $仅与$ \left \{ f_1,\;f_2\right \} $两个特征相关, 当满足分类函数$ f_1+f_2<\theta $时, 类别$ C $为正类, 反之为负类. 在生成过程中, 我们首先置$ \theta = 8 $, 之后变化为$ \theta = 9 $, 周期变化2次生成重复漂移.

    Sine[19]: 每个样本的基本结构为$ \{ f_1,\;f_2,\;f_3,\; f_4, $ $ C\} $, 其中$ \{ f_1,\;f_2,\;f_3,\;f_4\} $为特征, 每个特征的值均匀分布在 [0, 1] 中, 类别$ C $仅与$ \{ f_1,\;f_2\} $两个特征相关. 当满足分类函数$ f_1<\sin(f_2) $时, 类别$ C $为正类, 反之为负类. 在生成过程中, 我们首先选择分类函数$ f_1<\sin(f_2) $, 之后将分类函数反转为$ f_1> \sin(f_2) $, 周期变化2次生成重复漂移.

    数据集的具体信息如表1所示.

    表 1  实验所用数据集
    Table 1  Datasets used in experiment
    数据集特征个数类别个数样本个数漂移类型漂移次数漂移位点
    Hyperplane102100k增量
    Sea32100k渐变325k,50k,75k
    Sea-re32100k重复325k,50k,75k
    LED-gradual2410100k渐变325k,50k,75k
    LED-abrupt2410100k突变150k
    RBFblips204100k突变325k,50k,75k
    Tree3010100k突变325k,50k,75k
    Sine42100k重复325k,50k,75k
    KDDcup994123494k
    Electricity6245k
    Covertype547581k
    Weather9395k
    下载: 导出CSV 
    | 显示表格

    1)固定数据单元$ k $ : 选择一个合适的数据大小替换基模型是非常重要的. 数据单元过小可能会导致基模型过拟合, 对集成性能造成影响; 数据单元过大可能会导致适应渐变漂移较慢, 对适应速度有所影响. 本文实验采取数据单元$ k = 100 $.

    2)权重衰退率$ \beta $ : 权重衰退率$ \beta $是影响算法集成性能的关键. 衰退率大时, 虽然在漂移发生后能够更快适应新的数据分布, 但是模型性能极其不稳定; 反之, 虽然模型相较稳定, 但是在漂移发生后无法快速适应新的数据分布. 本文实验采用的衰退率$ \beta = 0.95 $.

    3)基模型: AC_OE方法沿用参考文献[28]中的参数和LIBSVM, 其余所有集成方法均使用Hoffding树, 基模型数量$ s $设置为10.

    为验证所提CDAM-APIE的合理性, 本文从精度, 恢复速率和鲁棒性方面对算法进行了分析, 具体指标如下.

    1)平均实时精度$ Avgracc $(Average real-time accuracy)[28] 表示模型在每个时间步数下实时精度的均值, 定义如下:

    $$ \begin{equation} Avgracc = \frac{1}{T}\sum_{t = 1}^Tracc_t \end{equation} $$ (11)

    其中$ T $表示总的时间步数, $ racc_t $表示模型在时间步数$ t $下的实时精度, 公式如下:

    $$ \begin{equation} racc_t = \frac{n_t}{n} \end{equation} $$ (12)

    其中$ n_t $表示在时间步数$ t $下分类正确的样本数量, $ n $表示在一个时间步数内处理的样本总数, $ Avgracc $数值越大表明模型的实时性能越好.

    2)累积精度$ Cumacc $(Cumulative accuracy)[28] 反映了模型从开始时刻到当前时刻的性能, 定义如下:

    $$ \begin{equation} Cumacc = \frac{1}{T_t\cdot n}\sum\limits_{t = 1}^T{n_t} \end{equation} $$ (13)

    其中$ T_t $表示当前的累积步数. $ Cumacc $数值越大表明模型的整体性能越好.

    3)恢复速率$ RSA $(Recovery speed under accuracy)[28] 是评价模型在数据流发生概念漂移后实时精度稳定到新概念所需的步数, 定义如下:

    $$ \begin{equation} RSA = Step\cdot(1-racc_t) \end{equation} $$ (14)

    其中$ Step $表示模型从漂移点到收敛点所需要的时间步数, $ racc_t $表示收敛点后一个时间节点的实时精度. 本文根据数据集漂移位点后的实时精度变化确定当前时间节点是否为收敛点, 若当前时间节点以及后一个时间节点的精度变化均小于阈值, 则判断其为收敛点, 定义如式(15)所示:

    $$ \begin{split} &|racc_t-racc_{t-1}|\leq Threshold\&\\ &|racc_{t+1}-racc_t|\leq Threshold \end{split} $$ (15)

    由于模型在不同数据集上的波动不同, 阈值设置为各数据集在收敛期间实时精度变化的均值加上其三倍标准差, 如式(16)所示:

    $$ \begin{equation} Threshold = \frac{1}{T}\sum_{t = 1}^T(racc_{t+1}-racc_t)+3\sigma \end{equation} $$ (16)

    $ RSA $数值越小表明模型的恢复速率越快.

    4)鲁棒性$ R $(Robustness)[30] 是评价模型稳定性能的重要指标, 能够在一定程度上评价模型的泛化性能, 通过平均实时精度分析不同算法的鲁棒性, $ A $算法在数据集$ D $上的鲁棒性定义如下:

    $$ \begin{equation} R_A(D) = \frac{Avgracc_A(D)}{\min Avgracc_\alpha(D)} \end{equation} $$ (17)

    其中$ Avgracc_A(D) $表示$ A $算法在数据集$ D $上的平均实时精度, $ \min Avgracc_\alpha(D) $表示在数据集$ D $上所有算法中的最小平均实时精度. $ A $算法的整体鲁棒性为$ A $算法在所有数据集上的鲁棒性之和, 假设有$ N $个数据集, 具体定义如下:

    $$ \begin{equation} R_A = \sum\limits_{i = 1}^NR_A(D_i) \end{equation} $$ (18)

    $ R_A $数值越大表明$ A $算法的整体鲁棒性越好.

    为有效评估CDAM-APIE的分类效果、概念漂移发生后适应漂移的能力以及模型的稳定性, 从模型精度、恢复速率、鲁棒性、消融效果以及参数敏感性方面进行了实验分析.

    3.4.1   模型精度评估

    不同方法在每个数据集上的平均实时精度和平均排名如表2所示. 从表中可以看出, CDAM-APIE的准确率最高, 平均排名第1, ATNN、Oza Bagging和DWM紧随其后, OOB、AWE和AC_OE比较接近. CDAM-APIE充分发挥了被动集成模型和主动基模型的作用, 在平稳的数据流环境下保持较高精度, 在数据流发生概念漂移后能够有效学习最新数据分布, 提高模型的整体性能. CDAM-APIE在大多数数据集上的表现都优于其他方法, 与平均排名次优的方法相比, 平均实时精度在12个数据集上平均高出1.3%. 在RBFblips数据集上CDAM-APIE与AC_OE和ATNN方法相差较大, 因为该数据集由随机径向基函数生成, 在LIBSVM上适配性较高. 由于Covertype数据集数据分布倾斜且波动较小, 在该数据集上CDAM-APIE略差于Oza Bagging. 此外, ATNN以神经网络强大的表示能力在RBFblips、Electricity、Covertype、Sine数据集上强于传统集成学习方法. 实验结果表明CDAM-APIE可以有效适应不同类型的概念漂移, 但是对于数据分布倾斜的数据集, 分类性能仍需提升, 这主要是由于被动方法比较容易替换掉泛化性能较好的基模型, 从而影响模型性能.

    表 2  不同方法在各数据集上的平均实时精度
    Table 2  Average real-time accuracy on different methods on every dataset
    数据集AWEOza BaggingDWMOOBAC_OEATNNCDAM-APIE(本文)
    Hyperplane0.8882(4)0.8758(5)0.9029(2)0.8223(6)0.8966(3)0.8195(7)0.9088(1)
    Sea0.8335(3)0.8159(4)0.8410(2)0.7754(7)0.8027(5)0.7871(6)0.8432(1)
    Sea-re0.8564(4)0.8596(2)0.8581(3)0.8030(7)0.8055(6)0.8166(5)0.8605(1)
    LED-gradual0.6055(4)0.5979(5)0.5022(7)0.6163(3)0.5054(6)0.6282(2)0.6330(1)
    LED-abrupt0.5944(5)0.6075(3)0.4918(7)0.5948(4)0.5178(6)0.6147(2)0.6240(1)
    RBFblips0.8208(5)0.8852(3)0.7861(6)0.7811(7)0.9316(2)0.9855(1)0.8309(4)
    Tree0.3630(7)0.4982(6)0.6449(3)0.6938(2)0.5480(5)0.6300(4)0.8072(1)
    Sine0.9331(4)0.7489(7)0.9363(3)0.8595(6)0.9155(5)0.9381(1)0.9374(2)
    KDDcup990.9796(4)0.9920(2)0.9793(5)0.9913(3)0.9446(7)0.9589(6)0.9926(1)
    Electricity0.7678(7)0.7928(5)0.8153(3)0.8110(4)0.7919(6)0.8912(1)0.8300(2)
    Covertype0.2288(7)0.8735(2)0.8135(4)0.8052(5)0.7813(6)0.9362(1)0.8400(3)
    Weather0.8893(7)0.9952(2)0.9941(3)0.9862(4)0.9069(6)0. 9616(5)0.9956(1)
    平均排名5.13.84.04.85.33.41.6
    下载: 导出CSV 
    | 显示表格

    不同方法在各数据集上的累积精度如图5所示. 从图中能够看到, CDAM-APIE在Hyperplane、Sea、Weather数据集上略优于其他方法, 在LED-gradual、LED-abrupt、Tree数据集上优势显著, 在RBFblips、Covertype、Electricity数据集上较Oza bagging、AC_OE、ATNN方法略差. 总体来说, 本文提出的CDAM-APIE在所有数据集上表现较好.

    图 5  不同方法的累积精度
    Fig. 5  Cumulative accuracy of different methods

    不同方法在各数据集上的实时精度如图6所示. 在大部分数据集上, CDAM-APIE的实时精度比其他方法的精度更高且更稳定. 在RBFblips、Electricity、Covertype、Sine数据集上, ATNN在大多数时间都高于CDAM-APIE和其他集成方法, 这得益于神经网络的强大表示能力和多分支结构的动态调整. 当发生概念漂移后, 所有方法的实时精度均明显下降, 但CDAM-APIE在大多数时候比其他方法更稳定, 精度下降幅度更小, 适应新概念更快.

    图 6  不同方法的实时精度
    Fig. 6  Real-time accuracy of different methods

    实验结果表明, CDAM-APIE在数据流平稳状态下能够保持较高的精度, 在概念漂移发生之后能及时捕捉新数据分布, 精度下降幅度较小, 其采用的增量学习和实时模型权重更新能够快速适应概念漂移, 并保证方法的稳定性.

    在性能分析中, 本文使用了非参数检验方法Friedman-test[32] 和Bonferroni-Dunn测试[33]对所提方法与对比方法进行统计分析以验证其差异.

    Friedman-Test可以对上述方法的性能优劣进行统计检验. 针对特定的$ K(7) $种方法和$ N(12) $个数据集, 令$ r_i^j $为第$ j $个方法在第$ i $个数据集上的秩, 则第$ j $个算法的秩和平均为:

    $$ \begin{equation} {R_j} = \frac{1}{N}\sum\limits_{i = 1}^N {r_i^j} \end{equation} $$ (19)

    零假设$ H_0 $假定所有方法的性能相同. 在此前提下, 当$ K $和$ N $足够大时, Friedman统计值$ \tau _F $服从第一自由度$ K-1 $, 第二自由度$ (K-1)(N-1) $的$ F $分布为:

    $$ \begin{split}&{\tau _F} = \frac{{(N-1){\tau _{{X^2}}}}}{{N(K-1)-{\tau _{{X^2}}}}}where\\ &{\tau _{{X^2}}} = \frac{{12N}}{{K(K+1)}}\left[\sum\limits_{j = 1}^K {R_j^2-\frac{{K{{(K+1)}^2}}}{4}}\right] \end{split} $$ (20)

    若计算得到的统计值超过了特定显著水平$ (\alpha) $下$ F $分布的临界值, 则拒绝零假设$ H_0 $, 表示各方法的秩和存在明显差异, 即不同方法性能具有显著差异. 反之, 接受零假设$ H_0 $, 所有方法的性能无明显差异.

    对上述不同方法的平均实时精度进行统计检验, 计算得Friedman统计值$ \tau _F = 6.6210 $, 在显著水平$ \alpha = 0.05 $的情况下, $ F $分布临界值为$ \tau _F^{0.05} = 2.239 $, 因此拒绝零假设$ H_0 $, 表明所有方法性能存在显著差异.

    Bonferroni-Dunn测试用于比较多个方法之间的显著性差异. 如果2种方法的秩和平均差值超过了临界差值$ (CD) $, 就认为它们的性能存在显著差异:

    $$ \begin{equation} CD = {q_\alpha}\sqrt{\frac{{K(K + 1)}}{{6N}}} \end{equation} $$ (21)

    通过计算, 在显著性水平$ \alpha = 0.05 $的情况下, $ CD = 2.3265 $. 不同方法在平均实时精度上的统计分析结果如图7所示. 结果表明, CDAM-APIE明显优于ATNN、Oza Bagging、DWM、OOB、AC_OE和AWE.

    图 7  不同方法平均实时精度的Bonferroni-Dunn检验结果
    Fig. 7  Bonferroni-Dunn test for average real-time accuracy of different methods
    3.4.2   模型适应性评估

    当数据流发生概念漂移之后, 模型能否迅速调整以适应新的概念是衡量算法的一个重要指标. 表3为不同方法在目前已知概念漂移位点的5个合成数据集上进行的模型适应性分析, 其中LED-gradual, RBFblips, Sea, Tree数据集有25k, 50k, 75k三个漂移位点, LED-abrupt数据集只有50k一个漂移位点. 从表中可以看出, CDAM-APIE总体表现最好, 在多数情况下恢复速率较好, 除了在LED-gradual数据集 (25k, 75k)、RBFblips数据集 (25k, 50k, 75k)、LED-abrupt数据集 (50k) 的恢复速率略低于其他方法之外, 其他位点上的恢复速率均优于其他方法. 由于CDAM-APIE通过实时处理最新样本更新基模型, 使模型能够快速适应新的数据分布, 但是在处理一些波化较大或较小的数据集时, 概念漂移检测技术可能会遇到误检或漏检的问题, 影响主动基模型的替换, 从而导致适应较慢.

    表 3  不同方法的恢复速率
    Table 3  Recovery speed under accuracy of different methods
    漂移位点数据集AWEOza BaggingDWMOOBAC_OEATNNCDAM-APIE(本文)
    25kSea0.480.520.460.530.760.560.46
    LED-gradual1.151.200.721.091.331.121.16
    RBFblips0.290.380.280.370.170.070.15
    Tree3.601.771.390.891.291.330.58
    平均排名4.85.82.83.85.03.52.3
    50kSea0.200.530.191.170.450.360.17
    LED-gradual0.580.570.630.580.610.540.53
    LED-abrupt1.631.361.351.361.281.661.47
    RBFblips0.860.361.261.170.520.040.87
    Tree0.891.551.601.161.441.560.89
    平均排名3.63.85.04.63.84.02.6
    75kSea0.520.440.330.610.470.200.33
    LED-gradual1.090.440.511.061.230.990.47
    RBFblips0.110.130.240.190.070.020.08
    Tree2.201.741.042.621.441.180.76
    平均排名5.53.83.56.34.52.32.0
    下载: 导出CSV 
    | 显示表格
    3.4.3   模型鲁棒性评估

    鲁棒性是评价算法稳定性的关键指标. 图8展示了7种方法在12个数据集上的鲁棒性, 每一列表示一种方法的整体鲁棒性, 其中不同颜色的堆叠块代表该方法在不同数据集上的鲁棒性. 由图8可以看到, CDAM-APIE在大多数数据集上的鲁棒性优于其他6种方法, 且整体鲁棒性最高, 总值为17.06.

    图 8  不同方法的鲁棒性比较
    Fig. 8  Comparison of the robustness of different methods

    为进一步说明方法的稳定性和适用性, 图9显示了不同方法的平均排名与标准差. 从图中可以看到, CDAM-APIE不仅平均排名第一, 且标准差最小, 稳定性较高. 实验结果表明, CDAM-APIE有较好的鲁棒性.

    图 9  不同方法的平均排名(平均值±标准差)
    Fig. 9  Average ranking of different methods (mean ± standard deviation)
    3.4.4   消融效果评估

    本文在被动集成模型的基础上加入了带有概念漂移检测的主动基模型. 为了证明其有效性, 分别采用基模型, 被动集成模型、主动基模型和CDAM-APIE进行分析. 表4展示了不同数据集下各方法的平均实时精度. 从表中可以看出CDAM-APIE在除RBFblips以外的11个数据集上性能表现最佳. 在RBFblips数据集上基模型效果最好可能是因为其漂移前存在关键性样本无法在漂移后被保留. 实验结果充分表明CDAM-APIE将被动方法与主动方法结合的有效性以及合理性.

    表 4  消融效果分析
    Table 4  Analysis of ablation effect
    数据集基模型被动集成模型主动基模型CDAM-APIE
    Hyperplane0.86030.89040.87160.9088
    Sea0.81180.83150.83330.8432
    Sea-re0.85540.85050.85170.8605
    LED-gradual0.58590.62660.62170.6330
    LED-abrupt0.60570.61540.61970.6240
    RBFblips0.84300.78250.80970.8309
    Tree0.49020.78730.79170.8072
    Sine0.65620.89410.93720.9374
    KDDcup990.99040.97860.99220.9926
    Electricity0.78280.81170.80920.8300
    Covertype0.82470.81780.82460.8400
    Weather0.99530.97710.99290.9956
    下载: 导出CSV 
    | 显示表格
    3.4.5   参数敏感性评估

    本节对CDAM-APIE在不同固定数据单元$ k $和权重衰退率下$ \beta $的平均实时精度进行了分析. 表5展示了CDAM-APIE在不同参数下的平均实时精度. 结果显示, 在不同的固定数据单元$ k $下, CDAM-APIE在大多数数据集上的性能差异并不显著. 这是由于CDAM-APIE采用增量学习方法, 有效减轻了不同固定数据单元对模型性能的影响.

    表 5  CDAM-APIE在不同参数下的平均实时精度
    Table 5  Average real-time accuracy of CDAM-APIE under different parameters
    固定数据单元$k$$50$$100$$150$
    权重衰退率$\beta$0.800.850.900.950.800.850.900.950.800.850.900.95
    Hyperplane0.90050.90200.90460.90760.90500.90620.90760.90880.90870.90990.91060.9113
    Sea0.83880.84000.84130.84200.84170.84230.84300.84320.84310.84320.84310.8427
    Sea-re0.85730.85840.85910.86000.85960.85990.86030.86050.86040.86070.86090.8606
    LED-gradual0.63090.63130.63170.63200.63140.63190.63280.63300.63480.63530.63580.6362
    LED-abrupt0.62200.62230.62300.62340.62290.62330.62370.62400.62280.62350.62410.6243
    RBFblips0.83660.83690.83780.83680.83080.83140.83120.83090.85030.85030.85050.8500
    Tree0.80730.80790.80860.80890.80660.80680.80710.80720.79600.79610.79630.7970
    Sine0.93720.93720.93720.93720.93710.93730.93710.93740.93780.93790.93810.9381
    KDDcup990.99220.99220.99220.99220.99220.99220.99240.99260.99310.99310.99310.9932
    Electricity0.85480.85150.84820.84160.84010.83850.83580.83000.82050.82050.82070.8204
    Covertype0.85690.85430.85100.84600.84550.84440.84260.84000.84510.84480.84410.8415
    Weather0.99460.99450.99470.99560.99560.99570.99560.99560.99510.99520.99520.9953
    总体标准差$0.1210$0.1208$0.1210$
    下载: 导出CSV 
    | 显示表格

    通过对$ k $的总体标准差分析发现, 随着$ k $值的增加, 平均实时精度的总体标准差呈现出先升后降的趋势. 当$ k $取值较小时, 模型可能在某些数据集上表现较好, 但未能很好地泛化到所有数据集上. 当$ k $取值较大时, 模型在大多数数据集上表现最好, 但在某些数据集上表现欠佳. 当$ k = 100 $时, 尽管精度略有下降, 但总体标准差较小, 表明模型更加稳定可靠. 另外, 现有方法常采用的固定数据单元一般为$ k = 100 $, 为了模型稳定性和便于比较, 故本文选择固定数据单元$ k = 100 $.

    表5可以看出, 随着$ \beta $的增加出现了两种情况, 精度先升后降或持续上升. 这是由于$ \beta $决定了模型权重的变化速度. 较小的$ \beta $使得权重变化过快, 导致暂时效果不佳的基模型难以在后续过程中发挥作用. 而$ \beta $较高时, 权重变化速度减慢, 使得模型无法及时响应概念漂移. 在相同$ k $下的大多数数据集中, $ \beta = 0.95 $时的平均实时精度最好, 因此, 本文选择了权重衰退率$ \beta = 0.95 $.

    现有方法通常只能对某种特定类型的概念漂移做出有效应对, 且无法及时响应数据流, 为此本文提出CDAM-APIE方法. 该方法首先结合了基于块和单样本集成方法的优势, 能够更好地适应不同类型的概念漂移. 其次将被动和主动方法进行动态加权结合, 提高了模型的泛化性能和适应能力. 此外, 增量学习用于缓解数据块大小对基模型性能的影响, 提高模型的鲁棒性. 实验结果表明, CDAM-APIE通过动态加权的方式调节两个模块, 充分利用两个模块在不同数据集上的优势, 使模型在平稳状态下保持较高性能并在数据流发生概念漂移后也能快速适应新的数据分布, 对多种类型的概念漂移都具有较好的效果. 然而, 数据流中通常还伴随着数据不平衡等问题, 我们计划在未来对含有概念漂移的非平衡数据流做一些尝试.

  • 图  1  CDAM-APIE整体框架图

    Fig.  1  The overall framework of CDAM-APIE

    图  2  四种类型的概念漂移

    Fig.  2  Four types of concept drift

    图  3  被动集成模型的过程

    Fig.  3  Process of passive incremental ensemble

    图  4  主动基模型的过程

    Fig.  4  Process of active base model

    图  5  不同方法的累积精度

    Fig.  5  Cumulative accuracy of different methods

    图  6  不同方法的实时精度

    Fig.  6  Real-time accuracy of different methods

    图  7  不同方法平均实时精度的Bonferroni-Dunn检验结果

    Fig.  7  Bonferroni-Dunn test for average real-time accuracy of different methods

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

    Fig.  8  Comparison of the robustness of different methods

    图  9  不同方法的平均排名(平均值±标准差)

    Fig.  9  Average ranking of different methods (mean ± standard deviation)

    表  1  实验所用数据集

    Table  1  Datasets used in experiment

    数据集特征个数类别个数样本个数漂移类型漂移次数漂移位点
    Hyperplane102100k增量
    Sea32100k渐变325k,50k,75k
    Sea-re32100k重复325k,50k,75k
    LED-gradual2410100k渐变325k,50k,75k
    LED-abrupt2410100k突变150k
    RBFblips204100k突变325k,50k,75k
    Tree3010100k突变325k,50k,75k
    Sine42100k重复325k,50k,75k
    KDDcup994123494k
    Electricity6245k
    Covertype547581k
    Weather9395k
    下载: 导出CSV

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

    Table  2  Average real-time accuracy on different methods on every dataset

    数据集AWEOza BaggingDWMOOBAC_OEATNNCDAM-APIE(本文)
    Hyperplane0.8882(4)0.8758(5)0.9029(2)0.8223(6)0.8966(3)0.8195(7)0.9088(1)
    Sea0.8335(3)0.8159(4)0.8410(2)0.7754(7)0.8027(5)0.7871(6)0.8432(1)
    Sea-re0.8564(4)0.8596(2)0.8581(3)0.8030(7)0.8055(6)0.8166(5)0.8605(1)
    LED-gradual0.6055(4)0.5979(5)0.5022(7)0.6163(3)0.5054(6)0.6282(2)0.6330(1)
    LED-abrupt0.5944(5)0.6075(3)0.4918(7)0.5948(4)0.5178(6)0.6147(2)0.6240(1)
    RBFblips0.8208(5)0.8852(3)0.7861(6)0.7811(7)0.9316(2)0.9855(1)0.8309(4)
    Tree0.3630(7)0.4982(6)0.6449(3)0.6938(2)0.5480(5)0.6300(4)0.8072(1)
    Sine0.9331(4)0.7489(7)0.9363(3)0.8595(6)0.9155(5)0.9381(1)0.9374(2)
    KDDcup990.9796(4)0.9920(2)0.9793(5)0.9913(3)0.9446(7)0.9589(6)0.9926(1)
    Electricity0.7678(7)0.7928(5)0.8153(3)0.8110(4)0.7919(6)0.8912(1)0.8300(2)
    Covertype0.2288(7)0.8735(2)0.8135(4)0.8052(5)0.7813(6)0.9362(1)0.8400(3)
    Weather0.8893(7)0.9952(2)0.9941(3)0.9862(4)0.9069(6)0. 9616(5)0.9956(1)
    平均排名5.13.84.04.85.33.41.6
    下载: 导出CSV

    表  3  不同方法的恢复速率

    Table  3  Recovery speed under accuracy of different methods

    漂移位点数据集AWEOza BaggingDWMOOBAC_OEATNNCDAM-APIE(本文)
    25kSea0.480.520.460.530.760.560.46
    LED-gradual1.151.200.721.091.331.121.16
    RBFblips0.290.380.280.370.170.070.15
    Tree3.601.771.390.891.291.330.58
    平均排名4.85.82.83.85.03.52.3
    50kSea0.200.530.191.170.450.360.17
    LED-gradual0.580.570.630.580.610.540.53
    LED-abrupt1.631.361.351.361.281.661.47
    RBFblips0.860.361.261.170.520.040.87
    Tree0.891.551.601.161.441.560.89
    平均排名3.63.85.04.63.84.02.6
    75kSea0.520.440.330.610.470.200.33
    LED-gradual1.090.440.511.061.230.990.47
    RBFblips0.110.130.240.190.070.020.08
    Tree2.201.741.042.621.441.180.76
    平均排名5.53.83.56.34.52.32.0
    下载: 导出CSV

    表  4  消融效果分析

    Table  4  Analysis of ablation effect

    数据集基模型被动集成模型主动基模型CDAM-APIE
    Hyperplane0.86030.89040.87160.9088
    Sea0.81180.83150.83330.8432
    Sea-re0.85540.85050.85170.8605
    LED-gradual0.58590.62660.62170.6330
    LED-abrupt0.60570.61540.61970.6240
    RBFblips0.84300.78250.80970.8309
    Tree0.49020.78730.79170.8072
    Sine0.65620.89410.93720.9374
    KDDcup990.99040.97860.99220.9926
    Electricity0.78280.81170.80920.8300
    Covertype0.82470.81780.82460.8400
    Weather0.99530.97710.99290.9956
    下载: 导出CSV

    表  5  CDAM-APIE在不同参数下的平均实时精度

    Table  5  Average real-time accuracy of CDAM-APIE under different parameters

    固定数据单元$k$$50$$100$$150$
    权重衰退率$\beta$0.800.850.900.950.800.850.900.950.800.850.900.95
    Hyperplane0.90050.90200.90460.90760.90500.90620.90760.90880.90870.90990.91060.9113
    Sea0.83880.84000.84130.84200.84170.84230.84300.84320.84310.84320.84310.8427
    Sea-re0.85730.85840.85910.86000.85960.85990.86030.86050.86040.86070.86090.8606
    LED-gradual0.63090.63130.63170.63200.63140.63190.63280.63300.63480.63530.63580.6362
    LED-abrupt0.62200.62230.62300.62340.62290.62330.62370.62400.62280.62350.62410.6243
    RBFblips0.83660.83690.83780.83680.83080.83140.83120.83090.85030.85030.85050.8500
    Tree0.80730.80790.80860.80890.80660.80680.80710.80720.79600.79610.79630.7970
    Sine0.93720.93720.93720.93720.93710.93730.93710.93740.93780.93790.93810.9381
    KDDcup990.99220.99220.99220.99220.99220.99220.99240.99260.99310.99310.99310.9932
    Electricity0.85480.85150.84820.84160.84010.83850.83580.83000.82050.82050.82070.8204
    Covertype0.85690.85430.85100.84600.84550.84440.84260.84000.84510.84480.84410.8415
    Weather0.99460.99450.99470.99560.99560.99570.99560.99560.99510.99520.99520.9953
    总体标准差$0.1210$0.1208$0.1210$
    下载: 导出CSV
  • [1] Din S, Yang Q, Shao J, Mawuli C, Ullah A, Ali W. Synchronization-based semi-supervised data streams classification with label evolution and extreme verification delay. Information Sciences, 2024, 678: Article No. 120933 doi: 10.1016/j.ins.2024.120933
    [2] Liao G, Zhang P, Yin H, Deng X, Li Y, Zhou H, et al. A novel semi-supervised classification approach for evolving data streams. Expert Systems With Applications, 2023, 215: Article No. 119273 doi: 10.1016/j.eswa.2022.119273
    [3] Zheng X, Li P, Wu X. Data Stream Classification Based on Extreme Learning Machine: A Review. Big Data Research, 2022, 30: Article No. 100356 doi: 10.1016/j.bdr.2022.100356
    [4] Agrahari S, Singh A. Concept drift detection in data stream mining: A literature review. Journal of King Saud University-Computer and Information Sciences, 2021, 34(10): 9523−9540
    [5] Krempl G, Zliobaite I, Brzezinski D, Hullermeier E, Last M, Lemaire V, et al. Open challenges for data stream mining research. ACM SIGKDD Explorations Newsletter, 2014, 16(1): 1−10 doi: 10.1145/2674026.2674028
    [6] Lughofer E, Pratama M. Online active learning in data stream regression using uncertainty sampling based on evolving generalized fuzzy models. IEEE Transactions on Fuzzy Systems, 2018, 26(1): 292−309 doi: 10.1109/TFUZZ.2017.2654504
    [7] 翟婷婷, 高阳, 朱俊武. 面向流数据分类的在线学习综述. 软件学报, 2020, 31(4): 912−931

    Zhai Ting-Ting, Gao Yang, Zhu Jun-Wu. Survey of online learning algorithms for streaming data classification. Journal of Software, 2020, 31(4): 912−931
    [8] Li H, Zhao T. A dynamic similarity weighted evolving fuzzy system for concept drift of data streams. Information Sciences, 2024, 659: Article No. 120062 doi: 10.1016/j.ins.2023.120062
    [9] 杜航原, 王文剑, 白亮. 一种基于优化模型的演化数据流聚类方法. 中国科学: 信息科学, 2017, 47(11): 1464−1482 doi: 10.1360/N112017-00107

    Du Hang-Yuan, Wang Wen-Jian, Bai Liang. A novel evolving data stream clustering method based on optimization model. Scientia Sinica: Informationis, 2017, 47(11): 1464−1482 doi: 10.1360/N112017-00107
    [10] Wang P, Jin N, Davies D, Woo W. Model-centric transfer learning framework for concept drift detection. Knowledge-Based Systems, 2023, 275: Article No. 110705 doi: 10.1016/j.knosys.2023.110705
    [11] 郭虎升, 张爱娟, 王文剑. 基于在线性能测试的概念漂移检测方法. 软件学报, 2020, 31(4): 932−947

    Guo Hu-Sheng, Zhang Ai-Juan, Wang Wen-Jian. Concept drift detection method based on online performance test. Journal of Software, 2020, 31(4): 932−947
    [12] Karimian M, Beigy H. Concept drift handling: A domain adaptation perspective. Expert Systems with Applications, 2023, 224: Article No. 119946 doi: 10.1016/j.eswa.2023.119946
    [13] Wozniak M, Zyblewski P, Ksieniewicz P. Active Weighted Aging Ensemble for drifted data stream classification. Information Sciences, 2023, 630: 286−304 doi: 10.1016/j.ins.2023.02.046
    [14] Cherif A, Badhib A, Ammar H, Alshehri S, Kalkatawi M, Imine A. Credit card fraud detection in the era of disruptive technologies: a systematic review. Journal of King Saud University-Computer and Information Sciences, 2023, 35(1): 145−174 doi: 10.1016/j.jksuci.2022.11.008
    [15] Halstead B, Koh Y, Riddle P, Pears P, Pechenizkiy M, Bifet A, et al. Analyzing and repairing concept drift adaptation in data stream classification. Machine Learning, 2022, 111(10): 3489−3523 doi: 10.1007/s10994-021-05993-w
    [16] Jiao B, Guo Y, Gong D, Chen Q. Dynamic ensemble selection for imbalanced data streams with concept drift. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(1): 1278−1291 doi: 10.1109/TNNLS.2022.3183120
    [17] Liu N, Zhao J. Streaming Data Classification Based on Hierarchical Concept Drift and Online Ensemble. IEEE Access, 2023, 11: 126040−126051 doi: 10.1109/ACCESS.2023.3327637
    [18] Wilson J, Chaudhury S, Lall B. Homogeneous–Heterogeneous Hybrid Ensemble for concept-drift adaptation. Neurocomputing, 2023, 557: Article No. 126741 doi: 10.1016/j.neucom.2023.126741
    [19] Gama J, Medas P, Castillo G, Rodrigues P. Learning with drift detection. In: Proceedings of the 17th Brazilian Symposium on Artificial Intelligence. Maranhao, Brazil: Springer, 2004. 286−295
    [20] Hinder F, Artelt A, Hammer B. Towards non-parametric drift detection via dynamic adapting window independence drift detection (DAWIDD). In: Proceedings of the 37th International Conference on Machine Learning. New York, USA: PMLR, 2020. 4249−4259
    [21] Wen Y, Liu X, Yu H. Adaptive tree-like neural network: Overcoming catastrophic forgetting to classify streaming data with concept drifts. Knowledge-Based Systems, 2024, 293: Article No. 111636 doi: 10.1016/j.knosys.2024.111636
    [22] Pratama M, Pedrycz W, Lughofer E. Evolving ensemble fuzzy classifier. IEEE Transactions on Fuzzy Systems, 2018, 26 (5): 2552−2567
    [23] Street W, Kim Y. A streaming ensemble algorithm (SEA) for large-scale classification. In: Proceedings of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA: ACM, 2001. 377−382
    [24] Wang H, Fan W, Yu P, Han J. Mining Concept-Drifting and Noisy Data Streams Using Ensemble Classifiers. In: Proceedings of the 9th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA: ACM, 2003. 226−235
    [25] Weinberg A, Last M. EnHAT-Synergy of a tree-based Ensemble with Hoeffding Adaptive Tree for dynamic data streams mining. Information Fusion, 2023, 89: 397−404 doi: 10.1016/j.inffus.2022.08.026
    [26] Oza N, Russell S. Experimental comparisons of online and batch versions of bagging and boosting. In: Proceedings of the 7 ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA. ACM, 2001: 359−364
    [27] Kolter J, Maloof M. Dynamic weighted majority: an ensemble method for drifting concepts. Journal of Machine Learning Research, 2007, 8 (12): 2755−2790
    [28] 郭虎升, 丛璐, 高淑花, 王文剑. 基于在线集成的概念漂移自适应分类方法. 计算机研究与发展, 2023, 60(07): 1592−1602

    Guo Hu-Sheng, Cong Lu, Gao Shu-Hua, Wang Wen-Jian. Adaptive classification method for concept drift based on online ensemble. Journal of Computer Research and Development, 2023, 60(07): 1592−1602
    [29] Gama J, Zliobaite I, Bifet A, Pechenizkiy M, Bouchachia A. A survey on concept drift adaptation. ACM Computing Surveys, 2014, 46 (4): 1−37
    [30] Wang B, Pineau J. Online bagging and boosting for imbalanced data streams. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(12): 3353−3366 doi: 10.1109/TKDE.2016.2609424
    [31] 赵鹏, 周志华. 基于决策树模型重用的分布变化流数据学习. 中国科学: 信息科学, 2021, 51(1): 1−12 doi: 10.1360/SSI-2020-0170

    Zhao Peng, Zhou Zhi-Hua. Learning from distribution-changing data streams via decision tree model reuse. Scientia Sinica: Informationis, 2021, 51(1): 1−12 doi: 10.1360/SSI-2020-0170
    [32] Pereira D, Afonso A, Medeiros F. Overview of Friedman's test and post-hoc analysis. Communications in Statistics-Simulation and Computation, 2015, 44(10): 2636−2653 doi: 10.1080/03610918.2014.931971
    [33] Demsar J. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research, 2006, 7: 1−30
  • 加载中
计量
  • 文章访问数:  148
  • HTML全文浏览量:  73
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-07-15
  • 录用日期:  2024-12-13
  • 网络出版日期:  2025-01-07

目录

/

返回文章
返回