面向概念漂移数据流的在线集成自适应算法

doi:10.13232/j.cnki.jnju.2023.01.013

面向概念漂移数据流的在线集成自适应算法

崔瑞华¹, 綦小龙¹, 刘艳芳²^,³, 林玲^,¹

1.伊犁师范大学网络安全与信息技术学院, 伊宁, 835000

2.龙岩学院数学与信息工程学院, 龙岩, 364012

3.计算机软件国家重点实验室, 南京大学计算机科学与技术系, 南京, 210023

Online ensemble adaptive algorithm for concept drift of streaming data

Cui Ruihua¹, Qi Xiaolong¹, Liu Yanfang²^,³, Lin Ling^,¹

1.Department of Network Security and Information Technology，Yili Normal University，Yining，835000，China

2.College of Mathematics and Information Engineering，Longyan University，Longyan，364012，China

3.State Key Laboratory for Novel Software Technology，Department of Computer Science and Technology，Nanjing University，Nanjing，210023，China

通讯作者: E⁃mail：linling_xj@163.com

收稿日期: 2022-10-06

基金资助:

新疆维吾尔自治区自然科学基金. 2021D01C466. 2021D01C467

Received: 2022-10-06

摘要

概念漂移是流数据的主要特征之一，如何检测概念漂移的发生以及调整预测模型去适应概念漂移现象备受研究者的关注.目前有关概念漂移的大多数算法仅仅针对单一类型的概念漂移检测，并且需限制输入数据服从某一分布，所以在检测多种类型概念漂移时效果不理想.提出一种在线集成自适应算法（KSHPR），在自适应随机森林（Adaptive Random Forests，ARF）算法和流随机补丁（Streaming Random Patch，SRP）算法的基础上进行优化改进，采用非参数检验与滑动窗口相结合的策略进行概念漂移检测，降低窗口平均值对算法性能的影响，并以此为基础建立四个基学习者的集成学习模型，根据基学习者预测准确率，动态分配权值，有效解决流式数据中学习模型精度低的问题.实验证明，提出的算法在真实数据集和合成数据集中均表现优良，与其他算法相比，该算法的稳定性、分类准确性与多类型概念漂移适应能力均有所提升.

关键词： 流数据 ; 概念漂移 ; 在线学习 ; 集成

Abstract

Concept drift is one of the main characteristics of stream data. How to detect the occurrence of concept drift and adjust the prediction model to adapt to the phenomenon of concept drift has attracted attention of researchers. At present，most algorithms about concept drift only aim at single type of concept drift detection，and need to restrict input data to obey a certain distribution，which makes the effect of detecting multiple types of concept drift unsatisfactory. An online ensemble adaptive algorithm (KSHPR) is proposed，which is optimized and improved on the basis of Adaptive Random Forest (ARF) and Streaming Random Patch (SRP) algorithms，adopting the strategy of combining non⁃parametric test and sliding window for concept drift detection，and reducing the influence of the window average on the performance of the algorithm. Based on this，we establish an ensemble learning model of four basic learners，which dynamically allocates weights according to the prediction accuracy of the basic learners，and effectively solves the problem of low accuracy of the learning model in streaming data. Experimental results show that the proposed algorithm performs well in both real datasets and synthetic datasets. Compared with other algorithms，the stability，classification accuracy and multi⁃type concept drift adaptability of the algorithm are improved.

Keywords： stream data ; concept drift ; online learning ; ensemble learning

PDF (1233KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

崔瑞华, 綦小龙, 刘艳芳, 林玲. 面向概念漂移数据流的在线集成自适应算法. 南京大学学报（自然科学）[J], 2023, 59(1): 134-144 doi:10.13232/j.cnki.jnju.2023.01.013

Cui Ruihua, Qi Xiaolong, Liu Yanfang, Lin Ling. Online ensemble adaptive algorithm for concept drift of streaming data. Journal of nanjing University[J], 2023, 59(1): 134-144 doi:10.13232/j.cnki.jnju.2023.01.013

大数据时代，流式数据已经成为机器学习的热点问题之一，其高速、连续、多变、无限、概念漂移等特性给机器学习算法带来了巨大挑战.实际生活中流式数据^［1-2］无处不在，例如网络监控、气象、工业、交通等均会产生大量的流式数据.流式数据分稳定的数据流和动态的数据流，动态数据流具有较强的实时性，且数据不独立分布，使数据分布容易发生变化，出现概念漂移的现象^［3-4］.

机器学习模型中若出现概念漂移，预测目标变量的统计特性会随时间发生不可预测的变化，导致原有模型的性能急剧下降，无法得到正确的结果.例如，在医学领域，病毒随时可能发生变异，若一直用初始模型检测病毒，很难发现变异后的病毒；在诈骗检测领域，诈骗方式会随着社会发展、流行趋势等因素影响发生变化，使模型无法准确检测是否为诈骗信息.因此，概念漂移是机器学习中模型预测准确率下降的根本原因，如何检测概念漂移、模型如何适应概念漂移现象已成为学术界的关注热点.

近年来有关概念漂移的研究不少，但现有的概念漂移检测适应算法更侧重于单一类型的概念漂移.例如，DDM （Drift Detection Method）^［5］通过分类错误率来判断是否发生概念漂移，适用于突变型概念漂移.EDDM （Early Drift Detection Method）^［6］改进了DDM，通过分类错误率间的距离来判断是否发生概念漂移，适用于渐变类型概念漂移.HDDM_W和HDDM_A^［7］均根据Hoeff⁃ding不等式识别概念漂移，前者适用于渐变型概念漂移，后者对突变型概念漂移效果很好.自适应随机森林（Adaptive Random Forests，ARF）^［8］和流随机补丁（Streaming Random Patch，SRP）^［9］算法在检测概念漂移后，模型会进行自适应调整，但在面对多种复杂的概念漂移时效果不理想.基于以上，本文改进了ARF和SRP算法，并以此为基础提出一种适应流式数据概念漂移的在线集成自适应算法（KSHPR），实验验证该算法能有效地提高学习模型预测的准确率.与其他算法相比，本文的主要贡献如下：

（1）采用非参数型概念漂移检测算法，无须对输入数据流分布作出限制，能提高算法的应用范围.

（2）改进了ARF和SRP算法的概念漂移检测过程，采用非参数检验与滑动窗口相结合的策略，能改进窗口平均值对算法性能的影响，提高算法的准确率.

（3）采用在线集成学习策略，根据基学习者预测准确率实时更新权值，提升算法自适应能力.

1 相关工作

概念漂移是数据分布随时间发生变化的一种现象.不同的文献将概念漂移分为不同的类别，陈志强等^［10］将概念漂移分为突变型、渐变型、增量型和重复型四类.De Barros and Santos^［11］将概念漂移分为突变型、渐变型和重复型三类，但根据其发生变化的时间来看，主要是数据分布的突然变化和持续一段时间后再变化两种情况.因此，本文将概念漂移分为突变类概念漂移^［12］和渐变类概念漂移^［13］两大类进行研究.

有关概念漂移的研究主要分两个重点研究方向：一是主动检测数据是否发生概念漂移，二是在检测到概念漂移以后模型如何做自适应的调整.基于此，可将有关概念漂移的算法分为主动方法^［14-16］和被动适应^［17-18］.主动方法通过检测数据分布是否发生变化、分类器的性能是否降低来判断概念漂移，主要针对急促的分布改变，重点在迅速检测到概念漂移的发生以及发生的具体时间点，主要分为基于模型性能、基于窗口机制和假设检验算法.DDM是第一个定义概念漂移检测警告级别和漂移级别的算法，通过检测分类错误率是否降低来判断是否发生概念漂移，在检测突变类概念漂移时效果很好，但对渐变类概念漂移的检测效果不理想.Baena⁃Garc et al^［6］在DDM的基础上提出早期漂移检测方法（EDDM），对DDM算法进行改进，使其在渐变类概念漂移中有很好的效果.在此基础上，Frias⁃Blanco et al^［7］提出基于Hoeffding不等式识别漂移临界区域的HDDM_A和HDDM_W算法.Bifet and Gavaldà^［19］提出自适应滑动窗口算法（Adaptive Sliding Window，ADWIN），采用滑动窗口机制，根据时间和数据分布的改变进行自适应改变，但算法性能取决于窗口的大小，如何选择窗口大小是决定算法性能的关键.

被动适应方法不判断数据分布是否发生变化，而是通过不断地更新分类器来适应概念漂移.被动适应方法主要有基于决策树、增量学习和基于集成的算法.霍夫丁树（Hoeffding Tree，HT）算法^［20］是一种基于决策树的算法，使用霍夫丁界来计算选择分割节点所需的样本数量，可以更新其节点以适应新传入的样本，但没有机制来解决特定类型的漂移.Gomes et al^［8］提出ARF算法，使用Hoeffding作为基学习者，通过重采样和随机选择节点分裂的特征子集来诱导多样性，但该算法采用局部子空间随机化策略，容易陷入局部最优.在此基础上，Gomes et al^［9］提出一种新的自适应集成算法SRP用于流数据分析，使用全局子空间随机化策略以提升算法精确度.ARF和SRP算法均选择ADWIN作为概念漂移检测器，算法性能取决于窗口的大小.

集成学习算法^［21-22］通过历史数据构建一系列基分类器，将多个基分类器组合起来形成集成分类器，借助投票加权机制进行集成决策，若发生概念漂移就进行权值调整，以此适应概念漂移现象.集成学习具有性能好、易融合、鲁棒性更强、适用于不同样本容量的优点，能解决流式数据中的概念漂移问题.集成学习根据其处理数据流的输入形式可以分为基于数据块的集成方式和在线集成两类.流式数据具有实时性强的特点，ARF和SRP算法选择在线集成的方式来构建集成模型，可以适应多种类型的概念漂移.

2 在线集成自适应算法

2.1　改进的ARF和SRP算法

ARF是一种新的用于演化数据流分类的随机森林算法，类似动态流随机森林，使用Hoeffding作为基学习者，通过重采样和随机选择节点分裂的特征子集来诱导多样性，所以必须结合漂移检测器.算法检测到漂移警告时，以新到来的数据训练每棵树的背景树，检测到漂移时就用背景树替换之前的树来适应新概念，但它使用的局部子空间随机化策略可能陷入局部最优.在此基础上，SRP结合随机子空间和Online Bagging算法进行预测，它采用类似ARF的技术，使用的是全局子空间随机化策略，全局子空间随机化是一种提高基础学习者多样性的方法.SRP的预测精度往往略好于ARF，但执行时间较长，并且SRP也需要结合漂移检测器才能适应分类中出现的概念漂移问题.

ARF和SRP算法均选择ADWIN作为概念漂移检测器来执行检测过程.ADWIN算法是基于滑动窗口策略的概念漂移检测，算法性能受窗口大小的影响，通过比较两个滑动窗口平均值的变化作为检测概念漂移的标准，但在真实世界中，平均值不能准确代表潜在的数据分布确实发生了变化，所以存在很大的局限性.本文改进了ARF和SRP算法的概念漂移检测过程，采用KS⁃test与滑动窗口相结合的算法策略作为概念漂移的检测机制.

KSWIN算法^［23］通过KS⁃test监控数据或性能分布变化.定义滑动窗口 $ψ$ ， $ψ$ 中保存数据流中最近的 $n$ 个数据，在滑动窗口 $ψ$ 中创建两个窗口 $R$ 和 $W$ .窗口 $R = {\{x_{i} \in ψ\}}_{i = n - r + 1}^{n}$ ，其中， $R$ 有来自 $ψ$ 的最新数据，将 $r$ 定义为最新到达的数据点.窗口 $W$ 的表示如式（1）所示：

W = \{x_{i} \in ψ| i < n - r + 1 \land p (x) = u (x_{i}| 1, n - r)\}

(1)

其中，窗口 $W$ 的数据是对 $ψ$ 历史数据的均匀采样， $|W| = |R| = r$ ， $u (x_{i}| 1, n - r) = \frac{1}{n - r}$ 为均匀分布.

KS⁃test是一种统计测试，不限制基础数据分布，它比较了两种经验累积分布 $F_{W}$ 和 $F_{R}$ 之间的绝对距离 $d i s t_{w, r}$ ，如式（2）所示：

d i s t_{w, r} = \underset{x}{s u p} |F_{W} (x) - F_{R} (x)|

(2)

其中， $F_{(\cdot)} (x) = \frac{1}{n} \sum_{j = 1}^{n} I_{[- \infty, x]} (X_{j})$ 为经验分布， $I_{[- \infty, x]} (X_{j})$ 是一个指示函数，若 $X_{i} \geq x$ 则 $I_{[- \infty, x]} (X_{j})$ 为1，否则为零； $s u p (x)$ 是条件有效所需的最小 $x$ .如果这个最大距离的下界，即 $d i s t_{w, r}$ 大于检验统计量，则两数据分布不一致，显著性水平为 $α$ .若出现如式（3）所示的情况，KSWIN就会检测到概念漂移：

d i s t_{w, r} > \sqrt[]{- \frac{l n α}{r}}

(3)

基于以上，选择KS⁃test与滑动窗口相结合的算法策略对ARF和SRP算法检测过程进行优化有助于提高预测模型的正确度，增大预测模型的适用范围，使其更能适用于复杂多变的现实世界.

2.2　算法的基本思想

现有的概念漂移检测算法大多假设输入数据的固定大小来估计分布变化，但现实生活中的数据流具有未知性强、实时性强、易发生改变等复杂多样的特点，选择非参数的概念漂移检测算法有助于提高概念漂移检测模型的适用范围，更适用于复杂多变的实际应用领域.HDDM_A和HDDM_W算法是经典的非参数概念漂移检测算法.

HDDM_A算法是一种基于Hoeffding不等式的漂移检测算法，使用基于Hoeffding不等式边界的A⁃test进行样本统计检验，采用移动平均统计量作为估计量.A⁃test包括零假设和拒绝零假设，零假设 $H_{0} : E [\bar{X}] \geq E [\bar{Y}]$ ，拒绝零假设 $H_{1} : E [\bar{X}] < E [\bar{Y}]$ ， $\bar{Y} - \bar{X} \geq ε_{α}$ 是拒绝零假设的条件.其中， $\bar{X}$ 和 $\bar{Y}$ 为统计量， $ε_{α}$ 为误差边界，HDDM_A通过监测A⁃test的移动平均数之间的差异来检测总体均值的变化.

HDDM_W使用基于McDiarmid边界的W⁃test进行样本统计检验，采用指数加权移动平均（EWMA）统计量作为估计量.W⁃test包括零假设和拒绝零假设，零假设 $H_{0} : E [{\hat{X}}_{n}] \leq E [{\hat{Y}}_{m}]$ ，拒绝零假设 $H_{1} : E [{\hat{X}}_{n}] > E [{\hat{Y}}_{m}]$ ，拒绝零假设条件为 ${\hat{X}}_{n} - {\hat{Y}}_{m} > {\hat{ε}}_{α}$ ，其中， $α$ 是显著性水平， ${\hat{ε}}_{α}$ 是错误边界， ${\hat{X}}_{n}$ 和 ${\hat{Y}}_{m}$ 是指数加权平均移动函数， $m$ 和 $n$ 是随机变量 $X$ 和 $Y$ 的数量.HDDM_W采用监测W⁃test的指数加权移动平均数之间的差异来检测总体均值的变化.

HDDM_W和HDDM_A定义两个不同的置信值 $α$ ，一个对应警告级别 $α_{W}$ ，另一个对应漂移级别 $α_{D}$ ，以此区别三个状态：稳定、警告或漂移.如果拒绝零假设的 $α_{W} = 0.005$ ，则当前状态被设置为警告；如果拒绝零假设的 $α_{D} = 0.001$ ，那么变化检测器达到漂移水平，否则接受零假设，并将当前状态设置为稳定.HDDM_W算法采用指数加权移动平均数，检测渐变式概念漂移效果很好，突变式概念漂移算法性能差.HDDM_A算法采用移动平均统计量作为估计量，更适用于检测突变式概念漂移，检测渐变式概念漂移不理想.以上概念漂移检测算法均不依赖于学习算法，可以应用任何分类器，有很强的适应性.现有的研究在线检测变化的参数方案均假设存在一个潜在的概率密度函数，但真实数据很少遵循这些众所周知的参数分布，参数型算法不能满足在线变化检测对数据输入的限制，不能保证算法性能.本文提出的算法选择HDDM_W和HDDM_A作为概念漂移检测机制.

虽然现有的概念漂移自适应算法很多，但在预测精度和漂移反应速度方面存在性能限制.增量学习算法^［24］由于其模型复杂度低和有限的漂移适应性，往往表现不佳，而漂移反应速度和块大小的确定是基于块的集成算法面临的两个主要挑战.在线集成，如ARF和SRP，通常比增量学习和基于块的集成算法表现得更好，但由于它们的随机化策略，在模型构建过程中引入了额外的随机性，导致学习模型存在不稳定性.本文提出一种面向流数据概念漂移的在线集成自适应KSHPR算法，其算法流程如图1所示.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 算法流程图

Fig.1 The flowchart of our algorithm

KSHPR算法在优化改进ARF和SRP算法的基础上进行了大量的实验测试，采用HDDM_A，HDDM_W和KSWIN作为概念漂移检测机制.与改进之前的概念漂移检测过程相比，KSHPR采用非参数检验，适用范围更广，适用于突变类概念漂移，也适用于渐变类概念漂移，还适用于存在多种概念漂移的情况.将非参数型概念漂移检测机制与自适应分类器结合，建立集成学习自适应算法，其稳定性和准确性均有所提升，并可适应多种样本容量.算法主要通过不同概念漂移检测机制改进ARF和SRP算法，以此为基础构建了四个基学习者ARF⁃HDDM_A，ARF⁃KSWIN，SRP⁃HDDM_W和SRP⁃KSWIN，通过计算基学习者的实时准确率动态分配权值，再将权值进行集成加权平均.算法伪代码如下所示.

算法在线集成自适应算法

输入：测试集 $N_{t e s t}$ 中的实例 $N_{0}$ ， $i = 0$

输出：集成新到达实例 $i$ 的预测准确率

初始化：输入数据流 $D (x, y)$ ，采用聚类的方法创建一个占总数据流10%的代表子集作为训练数据集 $N_{t r a i n}$ 来训练模型，剩余90%的数据作为测试集 $N_{t e s t}$

1.for四个基学习者学习训练数据集 $N_{t r a i n}$

2. for预测试集 $N_{t e s t}$

3. 四个基学习者预测标签

4. 读取实时准确率

5. 根据式（4），动态调整基学习者权重 $w_{j}$

6. 根据分类概率进行集合预测

7. 计算0类和1类的最终概率并进行预测

8. 更新集合模型的实时精度

9. $i = i + 1$

10. end for

11.end for

根据基学习者的实时性能分配动态权值.假设一个数据流 $D = \{(x_{1}, y_{1}), \dots, (x_{n}, y_{n})\}$ ，目标变量有 $c$ 个不同的类， $y \in (1, \dots, c)$ .对于每个输入数据 $x$ ，集成模型估计的目标类可以表示为：

\hat{y} = \underset{i \in \{1, \dots, c\}}{a r g m a x} \frac{\sum_{j = 1}^{k} w_{j} p_{j} (y = i |L_{j}, x)}{k}

(4)

其中， $L_{j}$ 为基学习者， $k = 4$ ， $p_{j} (y = i |L_{j}, x)$ 表示使用第 $j$ 个基学习者 $L_{j}$ 对数据样本 $x$ 上类值 $i$ 的预测概率， $w_{j}$ 为每个基学习者 $L_{j}$ 的权重.

每个数据样本处理后，将正确分类的样本总数除以处理后的样本总数来计算当前的实时分类准确率.每个基学习者的权重 $w_{j}$ 用其实时准确率来计算，可表示为：

w_{j} = 1 - \frac{1}{c o r r e c t_{r t} + ε}

(5)

其中， $ε$ 是一个很小的常数，一般设为0.001，避免分母为零.

虽然ARF和SRP均使用霍夫丁树作为基学习者，但它们的构建方法有很大的不同.ARF采用局部子空间随机化，而SRP使用全局子空间随机化，这增加了模型构建过程中的随机性和多样性，由此可以得到一个鲁棒性强且具有多样性的集成模型.集成模型由于其基学习者的多样性，增加了性能提高的机会.通过大量实验验证，HDDM_A作为漂移检测机制面对突变式概念漂移时有很好的效果，HDDM_W对渐变式概念漂移更敏感，KSWIN的平均效果最好，因此，本文提出的在线集成自适应KSHPR算法可以更好地适应流数据中存在多种类型概念漂移的情况.

2.3　模型的评价指标

选择准确率、精确率、召回率和F1⁃Score作为算法对比的评价标准.

（1）准确率（Accuracy）：反映分类器对整个样本的判定能力，将正的判定为正，负的判定为负.

a c c = \frac{T N + T P}{T P + T N + F N + F P}

(6)

（2）精确率（Precision）：所得数值与真实值之间的精确程度，是预测正确的正例数占预测为正例总量的比率.

p r e c i s i o n = \frac{T P}{T P + F P}

(7)

（3）召回率（Recall）：又称查全率，反映预测对的正例数占真正的正例数的比率.

r e c a l l = \frac{T P}{T P + F N}

(8)

（4）F1⁃Score：精确率与召回率的调和平均值，更接近精确率与召回率中较小的值.

F 1 - S c o r e = \frac{2 \times p r e c i s i o n \times r e c a l l}{p r e c i s i o n + r e c a l l}

(9)

其中， $T P$ 指实际为正预测也为正， $F P$ 指实际为负但预测为正， $T N$ 指实际为负预测也为负， $F N$ 指实际为正但预测为负.

2.4　实验数据集

实验数据集信息如表1所示.

表1 实验数据集

Table 1 Datasets used in experiments

数据集	实例数	特征	类值	漂移类型
electricity	45312	6	2	真实数据集
phishing	11055	46	2	真实数据集
spam	6213	499	2	真实数据集
SEA stream	40000	3	2	突变类
SEA Big	100000	3	2	突变类
Rotating Hyperplane	200000	10	2	渐变类
Sin incremental	20000	5	2	渐变类
Mixed paper	20000	6	2	混合型

新窗口打开| 下载CSV

真实世界数据集：

（1） electricity数据集是电力信息数据集，有六个属性和45312个实例.

（2） phishing数据集是网络钓鱼数据集，有46个属性和11055个实例.

（3） spam数据集是垃圾邮件数据集，有499个属性和6213个实例.

人工合成数据集：

（1） SEA stream数据集：由40000个样本组成，具有三个属性，其中只有两个相关，两个类别的决策边界由 $f_{1} + f_{2} = b$ 给出， $f_{1}$ ， $f_{2}$ 是两个相关特征， $b$ 是预定义阈值，通过每12500个样本更改 $b$ 的值.使用四种不同的概念来模拟突变漂移，包括10%的噪声.

（2） SEA Big数据集：增大了SEA stream数据集的数据规模，由100000个样本组成.

（3） Rotating Hyperplane数据集：包含概念渐变的特性， $d$ 维空间中的超平面在位置和方向上连续不断变化，其中， $d = 10$ ，两个类别，200000个样本.

（4） Sin incremental数据集：含有渐变式概念漂移，五个属性和20000个样本.

（5） Mixed paper数据集：包含突变类和渐变类概念漂移，六个特征，20000个样本.

3 实验与结果

3.1　改进ARF和SRP算法的实验对比

为了验证改进后的ARF和SRP算法的性能，使用Python 3.8，在i5⁃8700处理器和20 GB内存的电脑上扩展Scikit⁃多流框架来实现.

图2显示了在两个真实数据集和一个合成的混合概念漂移数据集上，ARF，SRP和改进算法的准确率对比，其中，SRP⁃KSWIN和ARF⁃KSWIN是改进后的算法.由图可见，使用KS⁃test与滑动窗口相结合的概念漂移检测机制，预测模型的准确率均有所提升，实验验证了改进算法的有效性.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 ARF，SRP与改进后算法准确率的对比

Fig.2 Accuracy of ARF，SRP and the improved algorithm

表2是ARF，SRP和改进算法模型评价指标的对比，表中黑体字为算法改进后的性能.由表可见，改进后的算法，其准确率、精确率、召回率和F1⁃Score均有所提升，进一步证明使用非参数算法改进算法后，算法的整体稳定性和准确率均有所提升，进一步扩大了算法的适用范围.

表2 ARF，SRP与改进后算法模型的性能对比

Table 2 Performance of ARF，SRP and improved algorithm model

	算法	ARF⁃ ADWIN	ARF⁃KSWIN	SRP⁃ ADWIN	SRP⁃KSWIN
electricity	Accuracy	81.84%	83.76%	82.68%	84.27%
	Precision	81.12%	82.08%	79.51%	81.95%
	Recall	74.07%	77.74%	73.50%	76.75%
	F1⁃Score	77.43%	79.85%	76.39%	79.21%
phishing	Accuracy	91.91%	93.06%	92.31%	93.02%
	Precision	91.26%	92.39%	92.76%	93.15%
	Recall	92.37%	93.63%	91.67%	92.79%
	F1⁃Score	91.30%	92.01%	92.71%	92.96%
Mixed paper	Accuracy	95.76%	98.38%	96.73%	98.21%
	Precision	98.86%	99.07%	96.35%	96.61%
	Recall	98.07%	98.11%	97.87%	98.17%
	F1⁃Score	97.97%	98.59%	97.15%	97.39%

新窗口打开| 下载CSV

3.2　在线集成自适应算法对比实验结果

为了验证本文在线集成自适应算法的性能以及其对概念漂移的适应性，选择在三个真实数据集和五个合成数据集上进行实验，实验环境同3.1.

3.2.1 KSHPR集成算法与单个算法的实验对比

为了验证KSHPR集成算法在面对多种类型概念漂移时的有效性，与基学习者ARF⁃HDDM_A，SRP⁃HDDM_W，ARF⁃KSWIN，SRP⁃KSWIN算法进行对比实验，以准确率为主要评价指标，同时比较精确率、召回率和F1⁃Score.KSHPR集成算法在面对概念漂移的情况下，在三个真实数据集中的预测准确度如图3所示，其中红色线条为提出算法的准确率.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 各对比算法在真实数据集上的准确率对比

Fig.3 Accuracy of different algorithms on real datasets

由图可见，在三个真实世界数据集中，和其他四个算法相比，本文提出模型的准确率均有所提升，证明该算法可以运用到真实世界中.预测电力价格时，供需变化或意外事件的影响会使电力价格发生变化，使用本文提出的算法可以有效地发现电力价格的变化，调整预测模型.在垃圾邮件分类问题中，垃圾邮件到达的时间和数量均是不确定的，若训练好的初始模型与之后到达的数据分布不匹配，预测模型的准确率就会降低，模型就会失效.本文提出的算法可以有效地提高概念漂移下垃圾邮件分类模型的准确率，也可以应用于判断钓鱼网站的模型中.

表3为提出的方法在三个真实数据集中与现有算法的准确率、精确率、召回率和F1⁃Score指标的实验对比结果，表中黑体字表示最优的性能.由表可见，提出的算法的每个评价指标都优于其他算法.

表3 各对比算法在真实数据集上的实验结果对比

Table 3 Experimental results of different algorithms on real datasets

	算法	ARF⁃HDDM_A	SRP⁃HDDM_W	SRP⁃KSWIN	ARF⁃KSWIN	KSHPR
electricity	Accuracy	85.21%	85.65%	83.24%	84.15%	87.69%
	Precision	83.36%	85.29%	82.25%	84.52%	86.52%
	Recall	83.73%	85.03%	82.67%	84.09%	85.18%
	F1⁃Score	83.93%	85.14%	82.80%	84.29%	85.76%
phishing	Accuracy	92.79%	93.18%	92.21%	92.40%	94.32%
	Precision	92.36%	92.33%	92.13%	93.15%	94.56%
	Recall	92.38%	92.20%	91.96%	93.09%	95.38%
	F1⁃Score	92.54%	92.29%	92.04%	93.09%	94.97%
spam	Accuracy	88.73%	88.04%	85.66%	87.27%	91.42%
	Precision	88.73%	87.42%	88.75%	88.63%	90.02%
	Recall	82.88%	82.42%	84.62%	81.53%	85.54%
	F1⁃Score	84.61%	83.43%	85.21%	83.24%	84.71%

新窗口打开| 下载CSV

图4为提出的方法在五个合成数据集上与其他算法的准确率对比.图4a和图4b是含有突变型概念漂移的数据集，图4a有40000个样本，图4b有100000个样本，证明该算法在数据量增大时仍然有很好的表现.图4c和图4d是含有渐变型概念漂移的数据集，图4d的数据量和特征值均远大于图4c.图4e是含有多种类型概念漂移的混合数据集.由图可见，提出的算法不管是面对突变型、渐变型，还是面对多种类型混合的概念漂移时，模型预测的准确率均有所提高.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 在合成数据集上各对比算法的准确率

Fig.4 Accuracy of different algorithms on synthetic datasets

表4是各对比算法在五个合成数据集上的实验结果，表中黑体字表示最优的性能.由表可见，提出的KSHPR算法不仅主要评价指标准确率高于其他算法，其精确率、召回率以及F1⁃Score也都有优势.实验结果证明，KSHPR算法能够很好地面对流数据中存在多种类型概念漂移的情况，提高了预测模型的准确率.实验结果也进一步证明，多个基分类器结合的集成模型比单个模型的性能更加优越，提出的集成模型适应度更广，可以适应更复杂的应用场景.

表4 各对比算法在合成数据集上的实验结果对比

Table 4 Experimental results of different algorithms on synthetic datasets

		ARF⁃HDDM_A	SRP⁃HDDM_W	ARF⁃KSWIN	SRP⁃KSWIN	KSHPR
SEA stream	Accuracy	88.37%	86.93%	88.41%	87.62%	89.28%
	Precision	88.33%	88.03%	85.37%	87.23%	89.24%
	Recall	87.77%	87.47%	84.85%	86.77%	92.49%
	F1⁃Score	88.02%	87.71%	85.05%	87.02%	90.83%
SEA Big	Accuracy	88.50%	88.59%	88.56%	88.73%	89.51%
	Precision	88.58%	88.32%	88.43%	87.44%	89.43%
	Recall	88.03%	87.89%	87.88%	89.47%	92.69%
	F1⁃Score	88.28%	88.12%	88.09%	87.15%	91.03%
Sin incremental	Accuracy	97.59%	96.18%	97.31%	96.67%	98.52%
	Precision	97.43%	97.01%	95.49%	98.11%	98.79%
	Recall	96.91%	96.19%	93.98%	97.98%	99.29%
	F1⁃Score	97.08%	96.35%	94.75%	97.96%	99.03%
Rotating Hyperplane	Accuracy	78.27%	78.68%	79.00%	76.00%	83.75%
	Precision	78.37%	78.56%	78.53%	75.32%	83.39%
	Recall	78.97%	78.97%	78.66%	75.21%	83.66%
	F1⁃Score	78.93%	78.48%	78.58%	75.27%	83.52%
Mixed paper	Accuracy	98.54%	96.70%	97.91%	96.73%	99.11%
	Precision	97.76%	97.27%	96.52%	96.53%	98.48%
	Recall	97.91%	88.76%	85.84%	96.32%	99.32%
	F1⁃Score	97.19%	97.19%	96.45%	96.48%	98.89%

新窗口打开| 下载CSV

3.2.2　KSHPR集成算法与现有其他集成算法的实验对比

将KSHPR算法与LB（Leverage Bagging）^［25］，LightGBM^［26］以及霍夫丁树（HT）算法进行对比实验.

图5给出了KSHPR在线集成自适应算法与现有其他集成算法的实验结果对比.选择三个真实数据集进行验证，实验结果证明KSHPR算法的准确率和LB，LightGBM以及HT算法相比均有所提升，说明该算法能够很好地适用于现实世界，应用场景的范围更广，能更好地适应现实中复杂多变的环境，也进一步验证了KSHPR算法在复杂多样环境中的有效性.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 KSHPR，LB，LightGBM，HT算法在真实数据集上的准确率对比

Fig.5 Accuracy of KSHPR，LB，LightGBM and HT algorithms on real datasets

3.3　算法复杂度分析

比较KSHPR，LB，LightGBM以及HT算法在三个真实数据集上的算法复杂度.LB的算法复杂度为 $O (l g W) + O (n \cdot m)$ ，HT的算法复杂度为 $O (n \cdot m)$ ，LightGBM的算法复杂度为 $O (l \cdot m)$ ，KSHPR的算法复杂度为 $O (n \cdot c \cdot k)$ ，其中， $n$ 是样本的数量， $c$ 是目标变量中类值的数量， $k$ 是基学习者的数量， $m$ 是特征数， $l$ 是常数.虽然KSHPR算法的时间复杂度高于其他算法，但KSHPR算法在三个真实数据集上的准确率均有提升，在electricity数据集上准确率提升2%，在spam数据集上准确率提升4%，在phishing数据集上准确率提升3%.另外，精确率、召回率以及F1⁃Score也都有所提升，算法整体性能更稳定，可适用于多种类型概念漂移或现实复杂场景.下一步将考虑如何在保证准确率的前提下降低时间成本.

4 结论

针对流数据中存在多种类型概念漂移的情况，提出一种在线集成自适应KSHPR算法.对ARF和SRP算法的概念漂移检测机制进行了优化和改进，并集成四个基学习者，根据基学习者的实时性能动态地分配权值，再将权值进行加权集成.实验证明了该算法在面对流式数据中存在多种类型概念漂移时的有效性，提高了机器学习预测模型的准确率；同时，也证明该集成模型在适用范围和性能上均优于单一模型，可以应用到产品价格预测、垃圾邮件分类、钓鱼网站预测等实际场景.但在面对单一类型概念漂移或简单地预测模型时，算法的时间成本较高，因此，该算法更适用于存在多种类型概念漂移的复杂场景.

未来将考虑在减少基学习者数量的情况下维持算法现有的效果，进一步优化算法，降低时间成本，扩大算法的适应范围.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

聂秀山，林熙明.

流数据概念漂移检测研究进展

山东建筑大学学报，2022，37(3)：90-100.