面向概念漂移和类不平衡数据流的在线分类算法

陆克中，陈超凡，蔡桓，吴定明

1 引言

随着信息技术的发展，各行各业中的数据出现爆炸性的增长，产生了海量数据，并且还在不断增加. 电子邮件、网络监控、股票预测、交通控制、传感器检测、信用卡交易和网络点击流等应用程序产生的数据流是一种新型的数据形式，具有快速、连续、多变、无限等特性［1］. 而且数据流的数据分布可能随时间发生改变，即存在概念漂移，因此模型需要不断地更新以适应新的数据流环境［2］. 概念漂移最早由Jeffrey 在文献［3］中提出，近年来，对概念漂移数据流进行在线学习、实时分析吸引了研究人员的兴趣［4］. 而类不平衡问题则加剧了对概念漂移数据流进行学习分类的困难，并且可能导致在线学习（包括概念漂移检测）的性能严重降低［5］.类不平衡在真实数据流中很常见，例如癌症诊断、垃圾邮件过滤、欺诈检测、计算机安全、图像识别、风险管理和故障诊断等往往存在多数类和少数类［6］. 由于数据的偏斜分布，传统的机器学习算法无法正确预测可能携带有用信息的少数类示例［7］. 因此，必须开发一种新的算法来解决概念漂移和类不平衡同时存在的问题.

近些年来，随着神经网络的迅速发展，研究人员已开始开发基于神经网络的数据流分类方法. 由新加坡南洋理工大学黄广斌教授团队提出的在线顺序极限学习机（Online Sequential Extreme Learning Machine，OS‑ELM）［8］是一种增量学习神经网络算法，是黄教授之前提出的极限学习机（Extreme Learning Machine，ELM）算法［9］的在线学习方法. 该算法可以逐步更新分类模型而无需重新训练，相对于其他算法具有速度快、分类性能好的优势，完美满足数据流分类的要求. 因此，基于OSELM 算法进行优化成为解决数据流分类问题的一个热门方向. 针对数据流的类不平衡问题，Mirza 等人于2013 年提出加权在线顺序极限学习机算法WOSELM（Weight Online Sequential Extreme Learning Ma‑chine）［10］，该算法基于代价敏感学习方法，根据不平衡率IR（Imbalance Rate）对少数类进行加权，从而使分类器具有类不平衡适应能力.2015年Mirza等人进一步提出基于投票的加权在线顺序极限学习机算法VWOSELM［11］，该算法以WOSELM 算法为基分类器，同时可以应用于多分类问题，实验表明相比原始的WOSELM 算法分类性能更好. 除了基于优化OSELM 更新公式和集成方法外，也有一些研究使用数据采样、进化算法优化等. 由Klikowski等人于2019年提出的多采样随机子空间集合算法MSRS（Multi Sampling Random Subspace）［12］是一种可以用于类不平衡非平稳数据流分类的基于块的集成方法. 2020 年Zhu 等人则使用三种进化算法优化加权极限学习机来解决类不平衡问题［13］，但仍是传统的批学习方式.

现有的基于数据采样的顺序学习方法通常以块的形式学习数据，即所谓的逐块学习，它们以类似于批处理学习方法的方式来处理类不平衡问题. 数据采样方法的局限性在于需要访问旧数据而不能轻松直接应用于一对一学习［14］. 因此，通常需要延迟分类模型的更新，直到接收到完整的数据块为止. 此外，在面对类不平衡数据流时，传统分类器的决策边界容易过度靠近少数类，在学习过程中容易忽略少数类的分类误差，而错分类一个少数类的代价往往高于错分类一个多数类的代价［15］. 大多数针对类不平衡的研究都只关注类不平衡问题，而忽略了类不平衡和概念漂移往往同时存在. 而且在进行分类任务前我们一般无法提前获知数据流不平衡率大小，不平衡率也可能发生改变. 特别是在复杂的真实数据集中，这大大增加了分类的难度. 因此如何提高复杂数据流的分类性能是论文的研究重点.

针对上面提到的问题，在FROSELM（Extreme Learn‑ing Machine based on Regularization and Forgetting fac‑tor）［16］和WOSELM［10］等算法的启发下，本文首先提出了一种具有遗忘因子的加权在线顺序极限学习机算法FWOSELM（Weighted Online Sequential Extreme Learn‑ing Machine with Forgetting Factor），该算 法融 合了WOSELM 算法的加权机制和FOSELM 算法的遗忘机制，从而能够同时具备概念漂移和类不平衡适应能力.集成学习往往能在复杂分布的数据流上取得更优秀的分类性能［17］，因此本文进一步提出了一种具有自适应遗忘因子的加权在线顺序极限学习机集成算法（Ensem‑ble of Weighted Online Sequential Extreme Learning Ma‑chine with Adaptive Forgetting Factor，EAFWOSELM）.

该算法首先使用FWOSELM作为基分类器，然后引入自适应遗忘因子和概念漂移检测机制以及自适应更新权重修正项，并将遗忘因子与混淆矩阵相结合，从而使分类器更关注最近到达的数据流，最后设计了在线集成策略. 算法使用递推公式实时增量更新模型，更符合在线学习的需求.

EAFWOSELM算法的创新性体现在三个方面：

（1）将WOSELM 算法和FOSELM 算法两者相融合，提出FWOSELM 算法，推导出一个简单有效的在线学习阶段更新公式，可以同时处理数据流的概念漂移和类不平衡问题；

（2）将遗忘因子引入混淆矩阵，从而可以更关注最近到达的数据流，防止历史累积数据过度影响分类模型；

（3）引入自适应遗忘因子和概念漂移检测机制，使模型根据分类性能自适应更新遗忘因子以及基分类器的权重修正项、投票权重以及类别权重. 从而能够更少依赖人工干预，可以根据数据流的变化自适应学习.

2 相关工作

在本节中，我们将重点介绍OSELM、FROSELM 和WOSELM三种算法. 为了简单起见，三种算法都考虑用于二分类问题，即只有单个输出节点.

2.1 OSELM 算法

OSELM 算法［8］分为两个阶段，在初始化阶段，假设有N0个训练样本(Xi,yi)，其中Xi=［xi1，xi2，…，xiL］T，L表示数据流特征数，即OSELM 的输入层节点数. 利用极限学习机ELM 算法的思想，希望求得满足||H0β-Y0||最小的输出层权重β0，其中

而Y0=[y1,…,yN0]T. 根据广义逆的计算方法，可以计算得β0

其中hk+1= [g(a1,b1,Xk+1),…,

OSELM 具备了ELM 的速度和泛化能力上的优点，从式（3）和式（4）可以看出，该模型的输出权重是根据最后一次的结果和新到达的数据进行迭代更新的，并且可以随着新数据的到来不断更新模型，而不是重新训练模型，数据一旦使用完毕即可丢弃；这种数据处理方式可以极大地降低算法的计算开销和内存，十分符合在线学习处理方式的要求. 因此，基于OSELM 算法进行优化成为数据流分类研究的一个热门方向.

2.2 FROSELM 算法

FROSELM 算法［16］是由Du 等人于2015 年提出，该算法将将遗忘因子FF（Forgetting Factor）方法和正则化技术引入OSELM，根据实例的时间顺序分别为每个样本分配不同的权重，为最近到来的数据分配较高的权重，更加关注最近到来的数据，使得算法可以适应数据流的状态变化.

初始化阶段输出层权重β0为

其中，C为惩罚项系数，I为单位矩阵. 在线学习阶段更新递推公式为

其中λ 为遗忘因子，当λ为1 且C为0 时，FROSELM 退化为原始OSELM.

2.3 WOSELM 算法

加权在线顺序极限学习机WOSELM算法［10］是由Mir‑za于2013年提出. 该算法基于代价敏感学习方法，根据不平衡率IR（Imbalance Rate）对少数类进行加权，从而保证分类器不会过度关注多数类. 初始化阶段输出权重β0为

其中，W0=diag([w1,w2,…,wN])，N为训练阶段样本数量. 当yk=0 时，类别权重wk为不平衡率IR. 当yk=1时，wk为1. 在线学习阶段更新递推公式为

其中，当yk+1为0 时，wk+1为更新后计算得到的IR，当yk+1为1 时，wk+1保持为1.

WOSELM 算法给少数类分类更高的权重，从而使分类器能够有效处理类不平衡数据流分类问题.

3 EAFWOSELM 算法

在面对类不平衡数据流时，传统分类器的决策边界容易过度靠近少数类，在学习过程中容易忽略少数类的分类误差，而错分类一个少数类的代价往往高于错分类一个多数类的代价. 此外，大多数针对类不平衡的研究都只关注类不平衡问题，而忽略了类不平衡和概念漂移往往同时存在. 针对这些问题，本文提出了EAFWOSELM 算法. 本节将对EAFWOSELM 算法的基本思想及其实现过程进行详细介绍.

3.1 算法基本思想

针对概念漂移和类不平衡同时存在的问题，首先融合WOSELM 算法的加权机制和FOSELM 算法的遗忘机制，提出了一种具有遗忘因子的加权在线顺序极限学习机算法FWOSELM，从而能够同时具备概念漂移和类不平衡适应能力. 然后以所提出的FWOSELM 算法作为基分类器，引入自适应遗忘因子和概念漂移检测机制，进一步提出了具有自适应遗忘因子的加权在线顺序极限学习机集成分类算法EAFWOSELM. 该算法将遗忘因子与混淆矩阵相结合，集成分类器的混淆矩阵可以用作概念漂移检测和计算类别权重，而基分类器的混淆矩阵可以用来确定基分类器的投票权重和类别权重修正项. 根据类别权重和类别权重修正项可以确定每个基分类器的更新权重W. 图1展示了本文所提出的EAFOSELM算法的整体框架.

3.2 基分类器FWOSELM

针对同时具有概念漂移和类不平衡数据流，首先融合WOSELM 算法的加权机制和FOSELM 算法的遗忘机制提出FWOSELM 算法，推导出一个基于OSELM 的隐含层输出权重β更新公式，从而保证算法能同时处理念漂移和类不平衡问题.

图1 EAFWOSELM算法的整体框架

概

FWOSELM算法的预测公式可以表示为

其中T为隐含层节点数

FWOSELM算法的代价函数可以表示为

其中wi、λ和C分别为更新权重、遗忘因子以及正则化参数.wi用来对类别进行加权，λ用来对新旧样本进行加权，C则是用来提高解的泛化能力. 为了满足在线学习的要求，接下来进一步推导βk的递推公式. 运用递归最小二乘法［18］对式（14）求解，可得

其中，Wk=diag([w1,w2,…,wk]). 因此，初始化阶段输出权重β0为

其中，C为惩罚项系数，W0为初始权重矩阵. 在线学习阶段，当新实例(Xk+1,yk+1)到达时，计算hk+1：

于是输出层权值可以表示为

根据Woodbury 公式，计算过渡矩阵Pk+1的更新递推公式为

则隐含层输出权重的βk+1更新递推公式为

整理式（21）和式（22）可得FWOSELM 算法在线学习阶段更新递推公式为：

其中λ为遗忘因子，wk+1为更新后的类别权重. 当λ为1且正则化参数C为0 时，FWOSELM 退化为原始WOSELM.

FWOSELM 算法为最近的样本分配较高的权重，而为旧的样本分配较低的权重，以表示它们对学习模型的不同贡献，因此使模型能够适应数据流的动态变化.同时，在学习时又为少数类分配更高的权重，提高少数类的分类错误损失，从而避免分类决策边界过度靠近少数类，具有更好的类不平衡适应能力.

虽然理论上FWOSELM 算法可以同时适应概念漂移和类不平衡问题，但仍然存在以下四点不足：（1）固定的遗忘因子无法在遗忘历史数据和学习历史数据之间取得平衡.（2）当不平衡率太大时，简单地按照不平衡率IR进行加权可以无法取得最好的分类性能.（3）当历史数据累积太多时，新到达的数据影响太小.（4）仍然没有解决大多数真实数据集都存在的复杂分布问题.

针对以上问题，本文进一步提出的EAFWOSELM算法将给出对应解决方案：（1）引入自适应遗忘因子和概念漂移检测机制，使遗忘因子能随概念漂移程度升高而自适应变小.（2）基于各类的分类准确率引入类别权重修正项，防止类别加权权值过大或过小.（3）将遗忘因子引入混淆矩阵，降低历史累积数据对现在的影响.（4）将FWOSELM 算法作为基分类器，设计集成学习策略，从而更好地适应复杂数据流.

3.3 自适应遗忘因子和概念漂移检测机制

自适应遗忘因子和概念漂移检测机制采用Gmean作为概念漂移检测的观测值，将遗忘因子引入混淆矩阵，只需保存历史最大的Gmeanmax和当前的Gmean值.

通常，概念漂移检测机制需要检测的概念漂移有两种类型，即突发式漂移和渐进式漂移. 由于OSELM算法能根据最新数据不断更新模型，FROSELM 算法在加入了遗忘因子后也更加关注最近到达的样本，因此具有较好的渐进式漂移适应能力. 但发生突发式漂移时，OSELM 算法和固定遗忘因子的FROSELM 算法适应缓慢，分类性能下降明显，特别是面临概念反转型数据流时，分类模型很难更新成功. 因此在EAFWOSELM 算法中，如果集成分类器的性能下降到某个阈值τ 及以下，则判断发生概念漂移，并自适应地调整遗忘因子.实验表明，将τ 设置为历史最佳Gmean 值的90%，可以使得实时Gmean 值的方差和标准差获得较好的表现，即实时Gmean 值较为稳定，可以较好地适应概念漂移.定义概念漂移指数CDI=Gmean/Gmeanmax.EAFWOSELM算法中默认的遗忘因子λ设置为0.999，当CDI 小于或等于0.9时，将遗忘因子更新为λ=0.9+CDI×0.1 （25）

因此，概念漂移下遗忘因子的取值范围是［0.9，0.99］. 当发生概念漂移导致分类器性能下降时，概念漂移指数CDI 会变小，此时遗忘因子λ 也会自适应地减小，从而加快遗忘历史数据，适应新数据. 使用Gmean代替平均分类准确率作为检测指标的优势是在数据流存在类不平衡时，可能少数类分类性能的显著下降并不会带来分类器整体分类准确率的显著下降，但会引起Gmean 值的显著下降，从而避免概念漂移检测机制由于数据流存在类不平衡而出现漏报问题.

3.4 在线集成算法设计

为了增强FWOSELM 算法的鲁棒性和应对更复杂的真实数据流，我们以FWOSELM 算法为基分类器，引入自适应遗忘因子和概念漂移检测机制，进一步提出了在线集成算法EAFWOSELM. 本节我们将介绍在线集成算法的3 个核心策略，即多样性策略、组件管理策略和结构更新策略［19］.

3.4.1 多样性策略

基分类器的多样性对集成分类器的性能起着至关重要的影响［20］.EAFWOSELM 算法在初始化阶段，首先构建一个存储基分类器FWOSELM的结构体BC_struct.struct of Base Classifiers）然后生成M个（实验中设置为12个）基分类器，通过采用不同模型参数的方式使基分类器之间存在差异，12 个基分类器采用四种隐含层节点数［inputs，2×inputs，3×inputs，4×inputs］和三种激活函数［sigmod，softplus，tanh］的交叉组合方式. 隐含层节点数和激活函数直接影响着模型的复杂度，极大地影响着FWOSELM 算法的学习性能，因此能够具有多样性.

3.4.2 组件管理策略

EAFWOSELM 算法采用加权多数投票来进行分类预测，具体而言，当需要预测新到达样本Xi的类标变量时，EAFWOSELM 算法采用以下公式聚合组件的预测：

其中，M为基分类器个数，Vk为第k个基分类器本轮的投票权重，而fk(Xi)则是第k个基分类器本轮的投票结果，且已经处理为类别标签. 最后选择得分最多的类别标签作为本轮的预测分类结果.

3.4.3 结构更新策略

结构更新策略是对组件进行更新，让集成分类器能够更好地适应数据流的变化，从而在充分利用和快速遗忘旧知识之间取得一个更好的平衡. 在EAF‑WOSELM 算法结构更新策略中，首先在学习过程中更新集成分类器的类别权重CW（Combine Weight）. 然后更新每个基分类器的投票权重V和类别权重修正项CF（Correction Factor），进一步得到基分类器的更新权重W. 最后通过自适应遗忘因子和概念漂移检测机制更新分类模型整体的遗忘因子λ. 其中的核心是将遗忘因子引入混淆矩阵，集成分类器的混淆矩阵EC_CM（Con‑fusion Matrix for Ensemble Classifiers）可以用作概念漂移检测和计算类别权重CW，而基分类器的混淆矩阵BC_CM（Confusion Matrix for Base Classifiers）可以同时用来确定每个基分类器的投票权重V和权重修正项CF，再根据类别权重CW 和权重修正项CF 可以确定每个基分类器的更新权重W. 具体更新机制如图2所示.

其中每一轮学习中混淆矩阵更新公式为

EC_CM=λ×EC_CM （27）

EC_CM[y] [ŷ] +=1 （28）

基于集成分类器的混淆矩阵，可以得到′0′类权重CW的更新公式为

图2 自适应组件更新机制

遗忘因子λ的更新公式为

第k个基分类器的类别权重修正项CFk更新公式为

其中，我们将Spe-Rec的绝对值的界限定义为μ，这里取μ为0.1.

第k个基分类器的更新权重w的计算公式为

将更新后的遗忘因子λ和基分类器的更新权重w代入式（23）和式（24）中，可以得到最新的输出权重βi+1，至此结束本轮学习.

3.5 算法伪代码

EAFWOSELM 算法通过融合加权机制和遗忘机制以及采用在线集成学习方式形成较优分类模型，使其更好地适应概念漂移和类不平衡，算法伪代码见算法1所示.

3.6 复杂度分析

本小节将从时间复杂度与空间复杂度两个层面分析FWOSELM 和EAFWOSELM 算法的计算复杂性. 由于实验中初始化阶段实例数占总实例数的比值均小于3%，且现实中数据流往往不断产生，因此我们更关心在线学习阶段的时间和空间复杂度.

首先对FWOSELM 算法而言，该算法与FROSELM和WOSELM 两种算法类似，都只是对OSELM 算法的更新公式进行了优化. FROSELM 算法的遗忘机制增加了一个额外的遗忘因子λ，在计算时额外消耗的时间和空间可以忽略不计. 而WOSELM 算法的加权机制虽然也只增加了一个权重项w，但每轮都需要对W进行更新，因此需要额外消耗更多的时间，不过这种更新的时间开销对于OSELM 算法本身更新的时间开销而言，仍然可以忽略不计. 因此，FWOSELM、FROSELM、WOSELM 和OSELM 四种算法的时间复杂度基本相同，与数据流的实例数N成正比，假设OS‑ELM 算法每轮的预测和更新时间为T1，则算法整体时间复杂度为O（T1×N）. 而且由于四种算法都属于在线学习方式，即都不需要保留历史数据，因此空间复杂度都为O（1）.

而对于EAFWOSELM 算法而言，由于采用进行集成学习方式，使用M个基分类器进行加权投票作为最终的分类结果. 因此，在时间开销上主要分为三个部分，基分类器FWOSELM 预测和更新的时间开销T1、加权投票的时间开销T2以及更新集成分类器的时间开销T3. 因此，EAFWOSELM 算法的整体时间开销为O（（M×T1+T2+T3）×N），而由于每一轮在线学习的T2+T3远小于M×T1，所以EAFWOSELM 算法的时间复杂度为O（M×T1×N）.EAFWOSELM 算法同样采用在线学习方式，不保留历史数据，只需要额外保留M个存储基分类器的结构体，因此空间复杂度为O（1）.

4 实验与结果

为了验证本文提出的EAFWOSELM 和FWOSELM算法的性能以及其对概念漂移和类不平衡数据流的适应能力，本文在理论研究的基础上进行了大量的实验.本节主要介绍实验环境和数据集、参数敏感性分析、参数选择验证、时间复杂度验证以及算法性能对比.

4.1 实验数据集

本实验运行于单机环境，所有分类算法均基于py‑thon 实现. 为了验证EAFWOSELM 和FWOSELM 算法的性能，实验数据集选取12 个人工合成数据集和2 个真实数据集，为了简单起见，仿真实验只考虑用于二分类问题，实验数据集简要信息如表1. 实验中默认所有算法的训练集实例数为500，惩罚参数C为0.1.

表1 实验数据集信息

（1）Sine_IR 数据集：其中IR 为不平衡率，即数据集中′1′类样本数和′0′类样本数的比值，实验选择了2、4和9 三种. 数据集中含有4 个属性，其中只有两个属性是相关的. 数据集包含20000 个实例，且在5000、10000和15000三个位置发生突变型反转，即概念漂移前后目标值刚好相反.

（2）Sea_s_IR 数据集：其中IR为不平衡率，包含2、4和9 三种.SEA 生成器在SEA 算法［21］中被提出，通过改变阈值，可以模拟概念漂移. 数据集中含有3 个属性，其中只有两个属性是相关的. 通过使用SEA 生成器生成了三个数据集，每个数据集包含20000 个实例，并添加了3%的噪声. 另外，三个数据集均包含2 次概念漂移，且都发生在实例编号为5000 和15000 的位置. 其中，Sea_s_IR数据集包含两次突变型概念漂移.

（3）Sea_g_IR数据集：其中IR为不平衡率，包含2、4和9 三种. 同上，Sea_g_IR 数据集包含两次渐变型概念漂移.

（4）Elec 数据集：是广泛应用于数据流学习中的真实数据集. 该数据集是来自澳大利亚新南威尔士州电力市场1995 年至1998 年的部分数据，包含45312 个实例. 数据集一共包含6 个相关属性，由于那里的电力价格不是固定的，而是根据供求关系而变化，因此目标是预测每天电力价格的变化（1=上升或0=下降）.

（5）Weather 数据集：包含1949 年至1999 年在内布拉斯加州Bellevue 收集的天气信息，包含18159 个实例. 数据集一共包含8 个相关属性，目的是预测给定日期是否下雨.

（6）Sine_N 数据集：其中N 为样本数量，选取了20 k（Sine_4），100 k，1 M，10 M 的数据验证时间复杂度以及算法对大数据集的表现.

4.2 对比算法

实验重点关注基于优化OSELM更新公式和集成方法的在线学习算法，将本文提出的EAFWOSELM 和FWOSELM 两种算法与其他6 种数据流在线分类算法进行性能比较. 它们分别是VWOSELM、WOSELM、FROSELM、OSELM、LPP和SRP，具体介绍如下：

（1）OSELM 算法：在线顺序极限学习机［8］，由新加坡南洋理工大学黄广斌教授团队于2006 年提出. 该算法是黄教授之前提出的极限学习机ELM 的在线学习方法，

（2）FROSELM 算法：具有遗忘机制的正则在线顺序极限学习机［16］，由Du 等人于2015 年提出. 该算法将遗忘因子FF（Forgetting Factor）方法和正则化技术引入OSELM，根据实例的时间顺序分别为每个样本分配不同的权重. 也就是说，为最近的样本分配较高的权重，而为旧的样本分配较低的权重，以表示它们对学习模型的不同贡献.

（3）WOSELM 算法：加权在线顺序极限学习机［10］，由Mirza 等人于2013 年提出. 该算法基于代价敏感学习方法，根据不平衡率IR对少数类进行加权，从而使分类器具有类不平衡适应能力.

（4）VWOSELM 算法：基于投票的加权在线顺序极限学习机［11］，由Mirza 等人于2015 年提出. 该算法以WOSELM 算法为基分类器，同时可以应用于多分类问题，实验表明相比原始的WOSELM算法分类性能更好.

（5）LPP 算法：Learn++.NSE 算法［20］是Learn++系列算法中最受关注的算法之一. 该算法由Elwell 等人于2011年提出，其具有独特的多分类器投票机制，是一种可以从非平稳环境（NSE）中进行增量学习的集成分类器.

（6）SRP 算法：流随机补丁（SRP）集成方法［21］模拟了装袋和随机子空间，由Gomes 等人于2019 年提出.该-算法默认的基分类器是Hoeffding 树，但它可以使用任何其他基分类器，此外算法默认采用ADWIN 方法进行概念漂移检测.

4.3 评价指标

机器学习的主要目标是学习到性能更好的模型，因此用来评估模型性能的评价指标在机器学习过程中起到至关重要的作用. 对于分类任务而言，分类准确率（Accuracy）是使用最广泛的性能评价指标，它可以衡量算法对整体样本的分类性能，但当数据流存在类不平衡问题时，分类准确率并不是最理想的评价指标.Ku‑bat 等人提出的几何均值Gmean［22］指标反映了分类器的总体性能，是衡量类不平衡数据流分类性能最重要的指标. 大多数分类性能评价指标都是从表2 的混淆矩阵中计算得出.

表2 二分类中的混淆矩阵

本文实验使用以下5 种指标来衡量类不平衡数据流的分类性能，具体计算公式如下：

（1）分类准确率（Accuracy，记为Acc）：

（2）召回率（Recall，记为Rec）：

（3）特异度（Specificity，记为Spe）：

（4）几何均值Gmean［22］：

（5）分类距离指标D（Rec，Spe）：

D(Rec,Spe) =abs(Rec-Spe) （37）

4.4 参数敏感性分析

为了解释融合WOSELM 算法的加权机制和FOS‑ELM 算法的遗忘机制以及引入权重修正项CF 的动机，本节设计了参数敏感性分析实验. 首先测试OSELM、FROSELM 和WOSELM 三种算法是否能同时适应概念漂移和类不平衡，此外还测试WOSELM 算法简单地采用不平衡率IR 进行加权的方式在不同IR 下的性能表现.

本次实验主要测试不同IR值下四种算法（包含OS‑ELM、FROSELM、WOSELM 和FWOSELM）在Sine_IR 和Sea_s_IR 数据集上的Gmean 值，实验结果如图3 所示.实验结果表明WOSELM 算法不具备概念漂移适应能力，因此在Sine_IR 数据集上性能表现很差；而FROSELM 算法不具备类不平衡适应能力，因此当不平衡率IR 增大时，Gmean 值严重下降. 原始的OSELM 算法则两种能力都不具备，因此表现最差. 而本文初步提出的融合了WOSELM 加权机制和FROSELM 遗忘机制的FWOSELM 算法，在实验中Gmean值表现是四种对比算法中最好的，而且具有很好的概念漂移和类不平衡适应能力.

接下来进一步测试不同IR 下WOSELM 算法的性能表现，实验结果如图4所示. 结果表明WOSELM 算法简单地采用不平衡率IR 进行加权无法取得最佳的效果. 在Sine_IR 数据集上，分类器按IR 加权后过度关注′0′类，且IR 值越大，倾向程度越高. 而在Sea_s_IR数据集上，当IR 小于8 时，分类器按IR 加权后过度关注′1′类；当IR 大于10 时，分类器按IR 加权后过度关注′0′类；只有当IR为8或9时，WOSELM 算法按IR加权的方式才取得较好的性能. 由于在进行分类任务前我们无法提前获知不平衡率IR，而且不平衡率IR 也可能不是一直固定不变的. 特别是在真实数据集中，在不同时期不平衡率IR 往往一直在改变，甚至多数类和少数类出现反转. 因此，本文提出在分类过程中对权重引入一个自适应的修正项，从而使多数类和少数类分类性能更加平衡.

4.5 参数选择实验

4.5.1τ选择实验

在探究τ值选择的实验中，我们选取了除Sine_N外的数据集进行实验；τ 定义为发生概念漂移的阈值，则意味着选择正确的τ 值可以使得算法在数据集上可以更好地适应概念漂移，即表现为Gmean 的分时变化更为稳定，本实验采取了计算分时变化的Gmean 的方差和标准差来探究τ的选择.

如图5所示，τ在90%左右的时候，方差和标准差都可获得较为良好的表现，意味着算法在τ选值为90%时可以更好地判断概念漂移的数据. 由于本实验采用的数据集涵盖了概念漂移的所有类型，且本算法在使用τ为90%时在所有采用的数据集上都有良好表现，故可认为该选值对所有发生漂移的数据集具有普适性.

4.5.2 临界值μ值选择实验

为了探究类不平衡在什么时候发生，我们将μ值作为判断是否发生类不平衡变化的临界值，并在Sine_IR数据集和其他数据集上进行μ值选择的实验，实验选择范围为［0，0.2］.

由图6 可以看出，μ值过小则会让其过度反应比例的变化，抖动过大；μ值过大则会反馈迟钝，无法正确地反应最近到来数据的比例变化；在μ值为0.1 的时候可以使得D（Rec，Spe）值在各数据集上表现良好，故取μ值为0.1.

图3 不同IR下四种算法在Sine_IR 和Sea_s_IR上的Gmean

图4 不同IR值下WOSELM在Sine_IR和Sea_s_IR上的性能

图5 分时Gmean标准差和方差在各数据集上的表现

图6 不同μ值下D(Rec,Spe)在各数据集上的表现

4.6 时间复杂度验证

为了验证EAFWOSELM 算法的时间复杂度为O（M×T1×N），其中T1为算法每轮的预测和更新时间，M为基分类器的数量，N为数据集大小；因此，我们使用了大小分别为20 k，100 k，1 M，10 M 的数据集进行实验，得到的数据如表3.

从表3可以看出，算法对数量不同的20 k、100 k、1 M、10 M数据集的运算时间与数据集的大小N成正比，故可得出EAFWOSELM算法的时间复杂度为O（M×T1×N）.

表3 算法在不同大小数据集上的表现

与此同时，算法在面对大数据集的时候也有着较为稳定和优异的表现.

4.7 对比实验

在对比实验中，将本文提出的EAFWOSELM 和FWOSELM 两种算法与其他6 种数据流在线分类算法进行性能比较. 其它6 种分别是VWOSELM、WOSELM、FROSELM、OSELM、LPP 和SRP. 其中，LPP和SRP 是当前应用广泛的数据流在线分类算法. 而VWOSELM、WOSELM、FROSELM 以及本文所提出来的EAFWOSELM 和FWOSELM 均是基于OSELM 优化的算法. 实验采用五种性能评价指标——Acc、Rec、Spe、Gmean 和D（Rec，Spe）来综合评估每个算法的分类性能.

图7和图8分别展示了对比算法人工数据集Sine_4上的分时和累计Gmean 以及综合性能指标. 从图7 可以看出，在［5000，1000，15000］这三个概念漂移发生点，EAFWOSELM 算法性能都能最快恢复，具有最好的概念漂移适应能力. 同时从图8 可以看出EAF‑WOSELM 算法全程都具有最佳的Gmean 值，因此具有更好的类不平衡适应能力.

图7 对比算法在Sine_4上的分时Gmean

图8 对比算法在Sine_4上的实时Gmean

数据流分类最大的难题之一是如何应对复杂的真实数据流. 因此，我们更加关注所提算法在Elec 和Weather 两个真实数据集上的表现. 图9、图10 分别展示了对比算法在真实数据集Elec 上的分时和累计Gmean. 从图9 可以看出，VWOSELM、WOSELM 和OS‑ELM 三种算法在［25000，35000］区间内Gmean 表现非常差，无法适应复杂数据流，而EAFWOSELM 可以很好地适应实时复杂数据. 从图9 可以看出，EAFWOSELM算法全程都保持着最佳的Gmean 值. 证明了EAF‑WOSELM 算法在真实数据集上具有更好的分类性能，可以更好地适应复杂的数据流.

图9 对比算法在Elec上的分时Gmean

图10 对比算法在Elec上实时Gmean

表4 展示了八种对比算法在11 个数据集上的综合性能指标. 其中EAFWOSELM 算法在所有数据集上均取得了最佳的Gmean 值，而且在其它指标上也取得了多项领先. 在9 个人工数据集上，可以观察到FROSELM、OSELM、LPP 和SRP 四种算法在Sine_IR、Sea_s_IR 和Sea_g_IR 这三类数据集上，随着数据流不平衡率IR 增大，少数类分类准确率Spe 均出现快速下滑，D（Rec，Spe）明显变大，从而导致Gmean 值也迅速下降，因此可以断定这四种算法不具备类不平衡适应能力. 此外，在Sine_IR 数据集上，EAFWOSELM 算法取得了巨大的领先优势，说明该算法可以快速适应反转型概念漂移，其它算法在面对这种概念漂移时，性能表现不佳. 在Sea_s_IR 和Sea_g_IR 数据集上，EAF‑WOSELM 和本文初步提出的FWOSELM 算法性能相当，都取得了很好的少数类分类准确率，Gmean 值也至少领先其它六种对比算法2 个百分点，说明初步提出的FWOSELM 算法已经具有较好的概念漂移和类不平衡适应能力. 而在最后的2 个真实数据集上，EAF‑WOSELM 算法则取得显著领先的分类性能，Gmean 值相比其它算法均至少提高了5 个百分点，而在平均分类准确率上也提高了2 个百分点左右.

表4 对比算法在不同数据集上的综合性能表现(%)

续表

5 总结

本文首先提出了一种具有遗忘因子的加权在线顺序极限学习机（FWOSELM）算法，该算法融合了WOSELM 算法的加权机制和FOSELM 算法的遗忘机制，从而能够同时具备概念漂移和类不平衡适应能力.此外，为了应对更复杂的真实数据流，本文进一步提出了一种具有自适应遗忘因子的加权在线顺序极限学习机集成算法（EAFWOSELM）. 该算法以FOSELM算法为基分类器，设计包含自适应遗忘因子和概念漂移检测机制的在线集成算法.

在仿真实验部分，通过参数敏感性分析验证了OS‑ELM、FROSELM 和WOSELM 三种算法无法同时适应概念漂移和类不平衡，此外还验证了WOSELM 算法简单地采用样本比例对′0′类进行加权无法在不同IR 下都取得最佳的效果，从而解释了融合WOSELM 和FOS‑ELM 两种算法以及引入权重修正项CF的动机. 然后在对比实验中，通过将EAFWOSELM 和FWOSELM 两种算法与其他6种数据流在线分类算法进行性能比较，验证了EAFWOSELM 算法的有效性，在9个人工数据集和2 个真实数据集上，EAFWOSELM 算法都取得了最优的Gmean 值，且在大多数数据集上也获得了最高的分类准确率. 从分类过程中可以看出，EAFWOSELM 算法具有更好的概念漂移和类不平衡适应能力，表现出了更稳定、更平衡以及更准确的分类效果. 尤其在两个真实数据集上，EAFWOSELM 算法相比其它算法在Gmean和分类准确率都有显著的提高. 另外值得一提的是，本文初步提出的FWOSELM 算法也取得了很好的性能，在大多数情况下分类性能都超过另外六种对比算法. 未来，我们将使用EAFWOSELM 算法应用在多分类数据集上，以此来观察其分类性能的泛化能力.