基于Hellinger距离的不平衡漂移数据流Boosting分类算法*

张喜龙，韩 萌，陈志强，武红鑫，李慕航

(北方民族大学计算机科学与工程学院，宁夏 银川 750021)

1 引言

从非平稳数据流中学习仍然是目前数据挖掘领域研究的重点，决策算法应该考虑到类别之间数量的不平衡性。真实的数据流还会表现出不断变化的类不平衡比率，从而进一步影响分类性能。在数据流处理中，不平衡数据现象变得至关重要，因为它出现在各个领域，例如天气数据预测、异常检测和社交媒体挖掘等[1]。具有多数类数据的类别称为多数类，而其它类别称为少数类。

近些年随着研究人员对不平衡数据的深入研究，集成学习与重采样技术的结合屡见不鲜。Wang等[2]改进了基于在线的Bagging集成的过采样OOB(Oversampling based Online Bagging)和欠采样UOB(Undersampling based Online Bagging)算法。作者利用时间衰减度量对OOB和UOB 2种集成学习方法进行改进，以克服在线类不平衡问题。Wu等[3]提出了一个重要性采样方法，即动态特征组加权框架用于对不平衡数据进行分类DFGW-IS(Dynamic Feature Group Weighting framework for classifying data Streams of Imbalanced distribution)。通过使用带有子分类器的特征组进行加权集成去处理不断变化的数据概念，其中子分类器通过它自身的分类性能和稳定性进行加权。为了解决概念漂移和类不平衡问题，Chen等[4]提出了递归集成方法REA(Recursive Ensemble Approach)。该方法有选择地挑选以前的少数类实例加入当前训练的块，以平衡类分布，同时使用动态加权适应概念漂移。同时,Lu等[5]提出了一种基于块的增量方法,称为动态多数加权不平衡学习DWMIL(Dynamic Weighted Majority for Imbalance Learning)算法。该算法使用集成框架对基分类器动态加权，以处理带有概念漂移和类的数据流不平衡问题。

尽管现有的集成分类算法能够很好地处理类不平衡问题，但在不平衡数据流的集成分类中还存在很多问题有待解决。例如,如何解决带有概念漂移的不平衡数据,基分类器如何分配合适的权值等。针对以上问题，本文提出了一种新的集成分类算法，主要工作如下所示：

(1)提出了一种新的基于Hellinger距离的Boosting集成加权算法BCA-HD(Boosting Classification Algorithm for imbalanced drift data stream based on Hellinger Distance)。算法采用实例权重和分类器权重组合的方法进行分类，首先使用Hellinger距离计算实例之间的权重，然后使用分类误差计算分类器的权重，通过分类器的动态更新方式去适应不平衡数据流中的概念漂移。

(2)提出的BCA-HD算法在底层使用了集成算法SMOTEBoost(Synthetic Minority Oversampling TEchnique Boost)[6]作为动态更新的基分类器，该集成分类器通过重采样的方式处理不平衡的数据，同时集成分类器在适应概念漂移方面比单分类器有着更好的鲁棒性。

实验表明，BCA-HD算法与典型的9种对比算法相比，它能更好地适应突变型和渐变型的概念漂移，同时对不平衡数据流分类性能也更好。

2 相关工作

2.1 不平衡数据流分类

随着研究人员对不平衡数据研究的深入，它的解决方案也变得更加多元化。目前不平衡数据分类研究主要涉及数据重采样和算法创新。

数据重采样是通过丢弃一些多数类样本(即欠采样技术)或添加新的少数类样本(即过采样技术)来重新平衡类的分布[7]。在欠采样技术方面，随机欠采样是最简单的方法，它使用随机方式丢弃多数类样本。鉴于可能会去除一些有用的多数类样本，研究人员设计了很多有效的欠采样方法。在数据过采样方面，最直接的方法是随机过采样，它随机复制原始少数类样本以引入少数类样本。过采样的一个显著缺点是它会增加过度拟合的风险，为此研究人员提出了合成少数类样本的过采样技术即SMOTE[8]。在特征空间中生成合成样本，通过在2个相邻的原始少数类样本之间进行插值，创建的新少数类样本将不同于现有的少数类样本。

在算法创新上集成学习是目前研究较多的方向之一，集成学习旨在通过组合多个基分类器来提高分类性能。由于其面向准确性的设计，标准集成学习算法不适合类不平衡学习。研究人员经常结合重采样方法来开发基于集成的解决方案，以处理类不平衡问题。SMOTEBoost是第1个基于Boosting解决类不平衡问题的算法。在该算法中，SMOTE被嵌入AdaBoost.M2[9]的学习框架中，通过生成新的合成样本来隐式增加少数类样本的权重。最近Zyblewski等[10]提出结合动态集成和预处理技术的框架来处理高度不平衡的数据流，提出了使用分层Bagging分类器对少数类和多数类进行替换抽样的方法。

2.2 概念漂移问题

在真实世界中，数据流的生成通常是在非平稳环境中进行，这意味着数据的底层分布可以随时间任意更改。在这样的非平稳环境中，数据流的概念和数据分布随时间而变化，这种现象被称为概念漂移[11]。下面从概率的角度来定义概念漂移，当2个时间点t0和t1的联合概率发生变化时就会出现概念漂移，即pto(X,yi)≠pt1(X,yi)。

根据漂移变化的速度,概念漂移可分为突变、渐近、重复和增量漂移，如图1所示。如果一种数据分布的来源被另一种数据分布的来源代替，称为突变型。当开始观察到两种数据分布混合时，这种漂移被称为增量型。当旧数据分布的数据实例开始减少，新数据分布的数据实例开始增加时，这种漂移被称为渐变型。重复漂移是指新概念的实例或旧概念的实例在特定时间之后开始重复出现的情况[12]。在不平衡数据流中，概念漂移的体现已经简化到了不平衡比率的变化随着时间变化少数类或多数类转变为多数类或少数类。

Figure 2 Illustration of BCA-HD图2 BCA-HD示意图

3 BCA-HD算法

通过对文献的分析可以看出，不平衡数据流分类算法表现不佳，而且大多数工作没有解决分类模型运行过程中可能出现的概念漂移问题。因此，所提出的解决方案应该对分类任务的参数变化具有很高的适应性，基于分类器集成方法是目前最受关注和研究较多的方向之一。同时，提出的解决方案应该考虑数据分布的局部特征和类之间的不平衡。

3.1 BCA-HD集成算法框架

在目前新的理论方面，Du等[13]提出了在线学习处理不平衡数据流的方法，通过改进在线Bagging技术来进一步提高分类性能。作者对少数类样本和多数类样本采用不同的泊松分布参数λ来区分样本之间的采样概率，以进一步平衡数据。在计算分类器的权重时，不是采用分类器的分类误差而是用泛化误差计算权重。该算法没有考虑带有概念漂移的不平衡数据流的处理，同时加权的方式是以分类器为主，在分类器的更新方面也没有以动态的方式去实现整体更新。基于以上算法的启发和分析，本文提出的算法考虑了概念漂移的存在，同时在加权方面引进了实例加权和分类器加权，以实现分类器的动态更新。

为了解决带有概念漂移的不平衡数据流问题，本文提出了基于Hellinger距离的Boosting集成分类算法BCA-HD。该算法主要解决2大核心问题：概念漂移和不平衡，该集成算法框架处理数据的全部过程如图2所示。算法在训练阶段，数据流以块的形式输入内存中，表示为S={D(1),…,D(t-1),D(t)},输入的数据块依次分配给当前集成分类算法SMOTEBoost，该算法将作为BCA-HD算法的基分类器来训练数据。分类器内部采用经典的重采样技术SMOTE，它使用差值方法来合成新的少数类样本，以平衡当前的不平衡数据集生成新的平衡后的数据块S′，然后使用当前分类器进行训练。在概念漂移的处理方面，算法采用实例级和分类器级的加权组合方式，权重大小代表对当前概念的重视程度。算法的集成过程是一种分类器的动态更新方式，这个过程可以让分类器更好地学习。随着分类器的创建，如果当前分类器的权重没有低于用户设置的阈值将直接加入分类器池π，否则当前基分类器会被删除，同时这个分类器会一直处于一种动态更新的过程。在测试阶段，生成的集成分类器根据多数投票原则对输入的数据进行预测分类。

3.2 BCA-HD算法训练过程

(1)

由于Hellinger距离公式对不平衡状态下的数据具有不敏感性，BCA-HD算法使用该公式作为实例之间相似度的度量。这种相似度的度量对时刻发生概念变化的数据来说是一种友好的检测方法，通过计算实例之间的距离权重然后分配给分类器来体现其对当前数据的重视程度。在分类器级，使用分类器的误差来体现当前学习数据的好坏程度，从而能进一步更新分类器的权重，如式(2)所示：

(2)

(3)

(4)

其中，α为比例参数，当分类器池中的基分类器的更新权重低于阈值θ时，则进行删除操作。如果要删除分类器，一个原因可能是分类器是在一个非常早的时间上进行的训练，先前训练的基分类器无法对当前的数据概念进行拟合，它的误差变大导致其权重会减小，表现在式(3)中总的求和权重降低。另一个原因是最近块上数据的概念发生变化，使得分类器的测试误差很大 ，导致权重变小被删除。如果数据流非常长，则BCA-HD仅在集合中保留有限数量的分类器，而不会遇到存储不够的问题。分类器使用式(5)最终预测输入的数据分布D(t)上的实例xi的分类结果。

(5)

其中，sign(·)为符号函数。

算法1是本文提出的BCA-HD集成分类算法的伪代码，该算法是基于块学习的方法,对于概念漂移有很好的适应性。

算法1BCA-HD

步骤1传入数据流S;

步骤3创建基分类器C；//(call算法2)

C←SMOTEBoost(D(t))，π←{C};

步骤4fori←1 toNdo//遍历实例

步骤5使用当前集成分类器C(t)预测实例xi;

步骤9else取所有实例权重的平均值

步骤10forj←1 tomdo//遍历分类器

步骤16m←|C(t)|；

步骤17创建新的基分类器：

C←SMOTEBoost(D(t))//call算法2

步骤18m←m+1;

步骤19π←π∪{C};

步骤21endif

步骤22endfor

步骤23 endfor

3.3 不平衡数据的处理

在分类器的创建上使用了集成分类算法作为BCA-HD算法的基分类器。SMOTEBoost算法是一个很健壮的算法，该算法数据采样部分使用SMOTE重采样技术处理不平衡数据。SMOTEBoost的伪代码如算法2所示。

算法2SMOTEBoost

输出：输出集成分类器C。

步骤1D1(i)=1/N,i=1,…,N;//初始数据分布。

步骤2 forj←1 tomdo//遍历分类器

步骤3采用SMOTE算法合成少数类，生成新的训练集S′；

步骤6fori←1 toNdo

步骤7遍历实例来更新分类器误差：

步骤8endfor

步骤9endfor

步骤10输出最终的集成分类器C。

4 实验设置

4.1 实验数据集

在实验中，本文采用了6个人工数据集和2个真实数据集来验证本文算法。其中Drifting Gaussian、Moving Gaussian、SEA、Hyper Plane、Spiral和Checkboard人工数据集使用概念漂移生成器生成;2个真实数据集为Electricity[15]和Weather[15]。Electricity数据集包含了澳大利亚新南威尔士州时间和需求的电价，类标签是通过过去24小时的价格变化情况来确定。Weather数据集包含美国贝尔维尤和内布拉斯加州超过50年的天气信息，任务是预测某一天是否会下雨。具体的数据集特征如表1和表2所示。本文算法主要以二元分类为主，为了更好地研究带有概念漂移的不平衡数据流，数据集会分为突变型(Abrupt)和渐变型(Gradual)2种漂移类型的数据,如表1和表2所示。

Table 1 Abrupt datasets表1 突变型数据集

Table 2 Gradual datasets表2 渐变型数据集

为了模拟真实的数据流中概念漂移变化的情况，实验通过不平衡比率的动态变化来模拟漂移的发生。

(1)突变型概念漂移：不平衡比率初始设置为0.01,数据流产生过半时，不平衡比率突变成0.99,也就是多数类变成了比率只有0.01的少数类。

(2)渐变型概念漂移：不平衡比率初始设置为0.01,在产生1/3的数据流后，不平衡比率不断增大，直至数据流量到达最大时，不平衡比率达到了0.99。

4.2 算法评估指标

在类不平衡数据流中，传统的指标已经不适用不平衡的场景，分类器总倾向多数类别，因此针对不平衡分类性能评估，相关学者提出了常用的F-measure和G-mean等以评价分类器对于多数类和少数类样本的分类性能。G-mean是由Kubat等[16]提出的几何均值，常被应用于不平衡类标签属性的数据流所在的领域。G-mean用表3所示的混淆矩阵来定义,其计算如式(6)所示：

(6)

Table 3 Confusion matrix表3 混淆矩阵

受试者工作特征曲线ROC(Receiver Operating Characteristic)和AUC(Area Under ROC Curve)是常用的评估分类器性能的指标。其中AUC是ROC曲线下的面积，AUC越接近1，表示该分类器性能越好。本文采用G-mean和AUC作为BCA-HD算法的性能评价指标。

4.3 实验环境

为了验证BCA-HD算法的性能，本文将BCA-HD算法与9种对比算法应用于突变型和渐变型数据集，然后比较其G-mean和AUC。本次实验的硬件环境是Intel Core i5 1T+128 MB RAM的PC机，操作系统是Windows 10专业版，编程语言为Python3.6。

5 实验结果分析

5.1 块大小对BCA-HD算法的影响

BCA-HD是基于块实现的集成分类算法，因此块的大小直接影响算法的执行效果。为了验证块大小对算法的影响，实验分别将数据块大小设置为d=500，750，1 000，1 250，1 500，1 750和2 000。其中d表示一个块所包含实例的数目。算法在Abrupt和Gradual 2种类型数据集上运行，实验结果使用G-mean指标展示，如表4和表5所示。

表4给出了在突变型数据集上不同块大小算法的G-mean性能。整体看初始随着块大小的增长G-mean值也在不断增长，当d=1 000时除了Spiral数据集外其余7个数据集上的G-mean都开始下降,说明随着块大小的增大，不平衡比率也都在不断变化，使得分类器适应它的能力变差。但是,在d=1 750时,G-mean开始缓慢增长，Drifting Gaussian和Hyper Plane在d取值为1 750和2 000时分别增长了2.14%和1.54%,说明分类器开始适应突变数据流，其中SMOTEBoost算法作为基分类器由于采用了SMOTE的重采样技术可以很好地平衡数据流。

表5是渐变型数据集上的运行结果，从整体看除了Drifting Gaussian和Moving Gaussian数据集上G-mean的性能下降较快外，其余的保持了平稳的增长状态。其中在真实数据集Weather上，在d取值为1 000和1 500时指标增长了7.63%，在Spiral数据集上,在d取值为1 000和1 250时指标增长了6.66%,说明数据流的块大小在缓慢变化情况下并不影响分类器的训练。其中在2种类型数据集上d=2 000时，分类器的表现均出现了下滑，说明块大小不能无限度地增大。在2种类型数据集上表现最好的G-mean使用粗体标了出来。

5.2 基分类器数量对BCA-HD算法的影响

本文提出的BCA-HD是集成分类算法，它是由基分类器组合形成的，因此很有必要探究基分类器的数量对算法的影响。实验设置分类器的数量在[1,15]内变化，BCA-HD算法在突变型和渐变型数据集上的G-mean如表6和表7所示。为了更好地展现数据的变化情况，给出了如图3和图4所示的箱线图，其纵坐标是G-mean值的均方差。例如,在Electricity数据集上在分类器数量在[1,15]内的G-mean平均值为0.674 2，当分类器为1时均方差为+0.003 9。

Table 4 G-mean of different algorithms on abrupt datasets with different chunk sizes 表4 不同数据块大小时不同算法在突变型数据集上的G-mean

Table 5 G-mean of different algorithms on gradual datasets with different chunk sizes表5 不同数据块大小时不同算法在渐变型数据集上的G-mean

Table 6 G-mean of different algorithms on abrupt datasets when the number of base classifiers varies表6 不同基分类器数量时不同算法在突变型数据集上的G-mean

Table 7 G-mean of different algorithms on gradual datasets when the number of base classifiers varies表7 不同基分类器数量时不同算法在渐变型数据集上的G-mean

Figure 3 G-mean of different algorithms on abrupt datasets when the number of base classifiers varies图3 不同基分类器数量时不同算法在突变型数据集上的G-mean

Figure 4 G-mean of different algorithms on gradual datasets when the number of base classifiers varies图4 不同基分类器数量时不同算法在渐变型数据集上的G-mean

图3展示了在突变型数据集上分类器数量由1～15的变化情形。分类器数量在[1,3]时，均方差的变化是±0.01；在[6,12]时，随着分类器数量的增加均方差的变化在±0.04。均方差整体处于一种正增长，说明分类器数量的增多可以更好地适应突变型概念漂移。图3中的圆点是异常点，在表6中用黑体字标示了。

图4展示了渐变型数据集上的实验结果。从图4中可以看到,随着分类器数量的增加，整体的G-mean值均方差变化控制在±0.02左右,说明随着分类器数量的增加，分类器的性能趋于一种稳定的状态。渐变型数据集对分类器的影响较小，图4中的圆点是异常点,在表7中用黑体字标示了。

5.3 BCA-HD算法性能对比分析

为了验证BCA-HD的分类性能，本文使用基于块和在线的9种算法进行比较。基于块的算法有ACDWM(Adaptive Chunk-Based Dynamic Weighted Majority)[15](采用了块大小不固定的形式适应概念漂移同时采用重采样技术平衡数据集)、Learn++.NIE[16](在每个块上创建分类器进行训练)、DWMIL[5]、REA[4]和DFGW-IS[3]。基于在线的算法有：HLFR (Hierarchical Liner Four Rates)[18]、DDM-OCI (Drift Detection Method-Online Class Imbalance learning)[19]、PAUC-PH (Prequential Area Under the ROC curve Page-Hinkley)[20]和OOB[2]算法,前3个算法是不平衡数据的漂移检测算法。以上算法的数据块大小d=1 000，基分类器个数设为12，损失函数为G-mean。实验结果如表8～表11所示。其中对比算法在每个数据集上的性能指标大小进行了排名(括号里面进行了标注)，最好的指标使用黑体字进行了标注，同时Average Rank展示了每个算法的平均排名。

表8和表9列出了对比算法在突变型数据集和渐变型数据集上的G-mean值。由表8可知，BCA-HD算法在5个突变型数据集上的G-mean值高于其他对比算法的。其中在Drifting Gaussian数据集上本文算法的G-mean值分别比DMWIL、OOB算法高2.99%,10.12%;BCA-HD算法在Checkboard数据集上位于第2名，与DWMIL算法相差0.08%。在表9中，BCA-HD算法在7个渐变型数据集上取得了第1名，其中在Hyper Plane数据集上高于ACDWM算法3.92%。

Table 8 G-mean of different algorithms on abrupt datasets表8 不同算法在突变型数据集上的G-mean值

Table 9 G-mean of different algorithms on gradual datasets表9 不同算法在渐变型数据集上的G-mean值

表10和表11展现的是各算法在2种类型数据集上的AUC。从表10可知，本文算法在5个突变型数据集上的AUC高于其它对比算法的，其中在Drifting Gaussian数据集上，BCA-HD的AUC是91.96%,高于所有对比算法的；在Moving Gaussian和Checkboard数据集上取得了第2名和第3名，并且在这2个数据集上的结果与第1名分别仅相差1.35%和0.96%。在表11中，BCA-HD在6个渐变数据集上的AUC取得了第1名，其中在Moving Gaussian与第2名相差最大,为2.36%，而在Sea数据集上低于第1名0.73%。

为了更详细地对比不同算法的性能，图5和图6给出了不同算法的G-mean和AUC对比情况。在图5a中给出的是在8个突变型数据集上的G-mean和AUC平均值的对比情况，BCA-HD在2种评估指标上都是趋于持平状态,说明随着不平衡比例的不断变化本文提出的算法可以很快适应概念漂移的发生。而HLFR算法的G-mean和AUC平均值相差较大，虽然该算法可以检测概念漂移的存在，但是又无法快速处理变化的不平衡数据流。在图5b中BCA-HD算法的平均排名是第1名，紧跟其后的便是DWMIL算法,这是由于其底层使用了处理不平衡的欠采样算法和动态更新机制，因此能很好地适应数据流的变化。图6a和图6b是渐变型数据集上各算法2种指标的平均值和平均排名，可以看到BCA-HD是10种算法中分类性能最好的，具体表现为其G-mean和AUC值高，排名也最高，这表明在渐变状态下的不平衡数据流集成算法依然可以很好地处理变化微小的数据。同时,基于块的ACDWM、Learn++.NIE、DFGW-IS和DWMIL算法也有很平稳的适应性，这与它们各自使用的平衡数据流机制有关。

Table 10 AUC of different algorithms on abrupt datasets表10 不同算法在突变型数据集上的AUC值

Table 11 AUC of different algorithms on gradual datasets表11 不同算法在渐变型数据集上的AUC值

Figure 5 Comparison of G-mean and AUC of different algorithms on abrupt datasets图5 不同算法在突变型数据集上的G-mean和AUC对比

5.4 BCA-HD算法参数与时间效率分析

本文提出的BCA-HD算法是基于Hellinger距离的集成加权算法，由于算法是基于实例级和分类器级的组合加权，因此主要使用2种参数，即权重组合参数α和删除分类器的阈值参数θ。实验中2种参数的取值分别在[0.1,0.5]内，实验的结果如表12和表13所示。

表12和表13是在5个突变型数据集上的实验结果。从图7中可以看到，整体随着α的增加均方差的变化范围在±0.02，其中α=0.2时均方差变化超过±0.03，说明α的取值为0.02较为合适。图7中圆点是异常点,在表12用黑体字标注出来了。在图8的箱线图中，整体θ的增加使均方差变化在±0.02内，但是负增长的比较多。说明随着阈值θ的增大无法删除更多的分类器，动态更新变得缓慢，适应概念漂移的能力开始下降。

Table 12 G-mean of BCA-HD when α=0.1～0.5表12 α=0.1～0.5时BCA-HD 的G-mean

Table 13 G-mean of BCA-HD when θ=0.1～0.5表13 θ=0.1～0.5时BCA-HD 的G-mean

Figure 7 Comparison of deviation from average G-mean of BCA-HD when α=0.1～0.5图7 α=0.1～0.5时BCA-HD的G-mean均方差比较

Figure 8 Comparison of deviation from average G-mean of BCA-HD when θ=0.1～0.5图8 θ=0.1～0.5时BCA-HD的G-mean均方差比较

为了实验的完整性，本文还在真实数据集上分析了BCA-HD算法的时间效率,结果如图9和10所示。从图9和图10中可以看到,BCA-HD算法的运行时间是在不断地上升，这是由于算法使用了实例级和分类器级的加权,增加了计算复杂度。其中DWMIL和HLFR算法的时间也处于一种线性增长态势，这是因为它们分别使用了动态加权和概念漂移的检测机制，从而增加了计算时间。

Figure 9 Comparison of algorithm running time on Weather图9 Weather上的算法运行时间对比

Figure 10 Comparison of algorithm running time on Electricity图10 Electricity上的算法运行时间对比

6 结束语

本文首先阐述了不平衡数据流分类和概念漂移的基本概念,并对已有算法进行了概述；随后提出了一种新的基于Hellinger距离的集成加权分类算法BCA-HD用于处理带有概念漂移和不平衡问题的数据。对比分析实验显示，本文所提出的算法具有较好的优势，并得出了以下结论：

在突变型和渐变型数据集上，随着块的增大算法性能会先下降然后再逐渐回升，说明该算法可以较好地适应块大小的变化。在基分类器数量的实验中，算法在渐变型数据集上随着分类器数量的增加变化趋于稳定，而在突变型数据集上有明显变化，说明在突变情况下受分类器数量影响较大。在对比实验中，相比经典的不平衡算法,本文提出的算法取得了更优的性能，说明BCA-HD算法能很好地适应渐变型和突变型概念漂移和不平衡的发生。

本文所提出的算法为二元不平衡分类问题提供了有效的解决方案。但是,组合加权的方式增加了计算复杂度,消耗了更多的时间。后续的研究将会在算法的基分类器数量的剪枝策略入手以降低时空复杂度。