面向不平衡数据流的动态权重集成分类算法

董明刚，张 伟，敬 超

1(桂林理工大学 信息科学与工程学院,广西 桂林 541004)

2(嵌入式技术与智能系统重点实验室,广西 桂林 541004)E-mail:jingchao@glut.edu.cn

1 引 言

近年来随着信息技术在交通管制、垃圾邮件检测等领域的应用，产生了大量具有动态变化的数据流[1].这些动态的数据流中存在着大量类分布不均衡问题.同时相比于静态数据流的数据分布，该类型数据流中的数据分布会随着真实环境实时发生变化，从而导致概念漂移问题[2-4].目前，国内外很多研究者针对这类问题做了深入的研究，他们的研究重点主要是围绕：数据预处理、分类算法以及采用集成分类器三个层面来进行.

对于数据的预处理方法，Gao[5]等人设计了一个估计后验概率的采样模型，以此来使小类样本与大类样本达到平衡.Wang[6]等人提出通过下采样技术，从大类样本中按照Bootstrap方法随机挑选相当于正类样本数量的样本形成平衡的数据对，以此解决不平衡问题.Chen[7]等人提出SERA算法，通过选择性的将先前的接收到的正类样本放到当前数据块中，这样可以较好的解决数据不平衡问题.对于分类器层面的改进方法，Yu[8]等人提出一种层次假设检验框架-HHT去识别概念漂移类型，后又基于此框架提出HLFR算法.该算法使用自适应训练策略代替常用的重训练策略在应对不同的概念漂移类型的适应性方面有良好的表现.Wang[9]等人通过下采样技术来处理不平衡数据流问题，通过动态修改分类器的权重使分类器具有良好的准确性.使用下采样技术能够减少运行时间，提高效率，同时动态修改分类器的权重能够很好的适应新的数据概念，使得分类器具有很强的鲁棒性.

相比之下，集成分类算法由于集成多个基分类器共同决策，因此能很好地处理概念漂移问题[10]：Ditzler[11]等人提出Learn++.CDS和Learn++.NIE，他们采用将数据流中到达一定数量的数据封装成数据块的方法，并为每个数据块单独创建一个子分类器，通过基分类器的组合集成来预测新传入的数据的标签.基分类的权重随时间的增加和分类性能的降低而减少.Kolter[12]等人提出DWM算法，提出了一种基于基分类器加权求和算法的通用框架，DWM在分类过程中保持基分类器不变，其权重在不同的数据块上不断地修改，并通过权重与分类器的加权求和进行样本预测，通过使用动态训练分类器权重解决概念漂移问题.Wu[13]等人提出了DFGW-IS算法，该算法通过在基分类器中运用采样技术来解决数据不平衡问题，然后对基分类器加权来解决数据概念动态变化的问题.Ghazikhani[14]等人通过使用递归最小二乘(RLS)误差模型来处理数据流的概念漂移问题，通过调整基分类器的加权误差解决类不平衡问题.当前数据流分类算法主要聚焦在集成分类算法[15-18]，该类型算法使用便捷，容易部署，且效果比单分类器更突出，能很好地解决概念漂移问题.

综上所述，在数据流的分类中，通常有两方面的困难，第一数据流中类分布不平衡，需要一种机制来克服类不平衡，以提高总体性能，第二需要动态调整学习机制来适应类概念的转变，即概念漂移问题.为了能够同时处理这两类问题，Yang[19]等人提出了一种动态加权的集成分类算法(Dynamic Weighted Majority for Incremental Learning，简称DWMIL)，该算法能同时较好地处理数据流分类中存在的概念漂移和数据不平衡问题，但该方法在处理数据流时每个样本只处理一次，这样做虽然节省了数据运算空间，但会丢失很多关于小类样本的信息，影响了小类样本的识别精度，Chen[20]等人提出REA算法，通过实验验证将小类样本收集起来根据某种规则再次应用能很好地提高分类器对小类样本的识别度，因此采用某种机制牺牲一部分运算空间，将之前的小类样本保存下来应用于分类器的训练能提高对小类样本的识别度.

为了有效处理带有概念漂移的不平衡数据流，基于DWMIL模型，提出了基于采样技术的集成分类算法DWES(Dynamic Weight Ensemble Learning Method Based on Sampling Technology).本文的主要贡献为：

1)采用上采样技术与下采样技术结合的方式来平衡数据块：假设数据流以数据块的方式到达，在对当前数据训练分类器的时候，上采样将之前的小类样本收集起来，筛选满足一定条件的样本加上当前小类样本形成当前数据块的合成小类样本，然后大类样本采用下采样技术每次抽取等同于当前数据块合成小类样本数量的样本，以此来形成一个平衡的数据对，用这个平衡的数据块来训练分类器.

2)调整了基分类器的权重计算方式，通过熵值计算能影响综合性能的评价指标，使用这个评价指标来计算该分类器的权重，这样做能使分类效果好的分类器有更高的权重，淘汰效果差的分类器.

3)通过马氏距离计算先前小类样本集与当前小类样本的相似性，挑选相似性高的样本，样本数量由计算得到的马氏距离集合的均方差来确定.

2 相关工作

2.1 DWMIL集成分类器

图1 DWMIL集成分类器流程图

2.2 数据流的采样方法

采样技术是处理不平衡数据流的有效方法，一般分为上采样方法跟下采样方法.上采样方法SMOTE[22]或者DataBoost-IM[23]基于存在的实例样本来合成新的实例样本点.这种合成新样本的方式有可能产生噪声样本，影响分类的精度.为了改善这个缺陷，REA算法不通过产生新样本来平衡数据，而是根据一定的规则选取历史样本中的点，以此达到样本平衡的效果.REA这种方式减少了噪声点的影响，加强了对小类样本的识别能力，在实际应用中取得了很好的效果.下采样方法一般采用UOB或者OOB，其基本思想是从大类样本中按照Bootstrap方法随机挑选相当于正类样本数量的样本形成平衡的数据对，以此解决不平衡问题.

2.3 马氏距离

马氏距离[24]是一种无量纲的计算两个未知样本之间相似度的度量，他考虑了样本各个属性之间的联系，能很好地反映样本的之间的关联程度.设样本集合u，其中μ是样本总体的均值，Σ为样本的协方差矩阵，则样本x到u的马氏距离计算公式如公式(1)所示：

(1)

综上，采用上采样技术增加小类样本的数量，同时根据小类样本的数量对大类样本进行下采样，减少大类样本的数量可以很好的解决不平衡数据问题.对生成的基分类器进行动态权重调整能使最终的分类器很快的适应新的数据流样本，解决概念漂移问题.

3 基于采样技术的集成分类算法DWES设计与分析

在对不带标签的数据流进行分类的时候，DWMIL集成分类器既能保持较高的分类精度，也能保证在数据流发生概念漂移的时候有较好的分类效果，但是在处理数据块的时候DWMIL集成分类器将之前的用过的数据块中小类样本全部抛弃，这样做虽然节省了计算的存储空间但是会损失一部分小类样本的数据特征，影响分类精度.并且在其进行分类器筛选的时候仅用到一个评价指标(G-mean/F-Value)，其不能合理地决定分类器的权重.基于DWMIL集成分类器，充分利用之前用过的小类样本，本文提出了一种集成分类算法--DWES算法.该算法上采样历史中存储的小类样本，下采样该数据块中的大类样本形成平衡的样本对，然后根据训练的分类器的表现不断调整分类器权重以适应新的样本.

3.1 DWES的采样策略

假设数据流以块的方式到达，将当前整个数据块看作是训练集，将下一个将要到达的数据块整体看作是测试集，数据流中只有正类、负类两种类标识，正类样本在每个数据块中相较于负类样本占比例较少，令t表示某一时间戳，D(t-1)表示在时间戳为t-1时到达的数据块，下一时刻到达的数据块为D(t)，则数据流为{…,D(t-1),D(t),D(t+1),…}.DWES集成分类器的采样过程如下(采样框架如图2所示).

图2 DWES的采样流程

1)上采样：在上采样的过程中我们将数据块{D(1),D(2),…,D(t-1)}中正类样本块{DNp1,DNp2,…,DNp(t-1)}收集起来放入集合PA中，当新的数据块D(t)到达的时候将前面1至t-1时间段内收集的正类样本PA用于当前数据块D(t).当数据块D(t)(t>2)到达的时候，根据马氏距离(公式1)计算当前数据块中正类样本DNp与集合PA中所有样本的马氏距离，挑选出其马氏距离小于马氏距离均方差的样本Pat加入到当前数据块的正类样本中得到当前数据块合成的正类样本Dp=Pat+DNpt.

2)下采样：根据当前数据块中合成的正类样本数量选取当前数据块中等量的负类样本组成平衡的样本对进行分类器的训练.

DWES集成分类算法的基于上采样与下采样结合的分类器构造过程伪代码如算法1所示.

算法 1.

输入：数据块DataD={xi∈X,yi∈Y},i=1,…,N,数据块D中正类样本数量为NP；数据块D中正类样本为DNp,数据块D中大类样本数量为Nn,数据块中D中大类样本为DNn,数据块D训练基分类器的大小为T.

1.t=1;

2.ifNP

3.Ns←NP;PA=DNp;

4.else

5.Ns←Nn;PA=DNn;

6.endif

7.fort← 2toTdo

8.ifNP

9.Ns←NP;Dn=DNp;

10.else

11.Ns←Nn;Dn=DNn;

12.endif

13.di←计算当前小类样本Dn与之前记录的所有小类样本PA之间的马氏距离;

14.DCOV←计算{di}的协方差;

15.(Ne，Dempty)←从之前记录的小类样本PA中挑选{di}小于DCOV的样本，得到样本集Dempty，样本集的数量为Ne;

16.PA={PA,Dn};

17.Dp←从(DNp+Dempty)样本中采用Bootstrap算法随机挑选(Ns+Ne)个样本;

18.Dn←从DNn样本中采用Bootstrap算法随机挑选(Ns+Ne)个样本;

19.Ht←{Dp,Dn}组成最终需要训练的样本集合，之后采用CART算法训练分类规则;

20.endfor

3.2 DWES的权重制定策略

(a)数据归一化公式如公式(2)所示：

(2)

其中i的取值范围是[1,n]，j的取值范围是[1,m].i表示连续到达的第i个数据块，j表示某种评价指标，在这里选取的评价指标P={G-Mean、F-measure、Precision、Recall，NPcost[18]}.

(b)计算评价标准中第j项评价指标所占该类型评价指标的比重，其公式计算如公式(3)所示:

(3)

(c)计算第j项评价指标的熵值如公式(4)所示：

(4)

(d)计算第j项评价指标的权值如公式(5)所示：

(5)

其中gj表示第j项评价标准的差异系数其计算方式为：gj=1-ej，当指标在不同数据块中差异越大代表对评测的最终结果影响越大，熵值越小.

(e)计算各评价标准的综合评分值如公式(6)所示：

(6)

选取综合评价值高的评价标准作为基分类器对样本错分类的代价其计算方式如公式(7)所示：

ε(t)=1-Pj

(7)

权重的计算公式为如公式(8)所示：

(8)

(9)

DWES的具体流程的伪代码如算法2所示.

算法 2.DWES算法

1.fori←1 toNdo;

2.通过基分类器预测Xi的标签：

3.endfor

4.forj←1 tomdo

6.更新分类器的权重：

7.endfor

8.移除权值低于θ的基分类器:

10.创建新的分类器，初始化分类器权重为1;

11.m←m+1;

12.H←将(D(t),T)传给基于上采样与下采样的分类器;

13.H(t)←H(t-1)∪H;

3.3 DWES算法复杂度分析

在上采样过程中，由于计算当前正类样本与之前正类样本集之间的马氏距离是线性的，设其复杂度为O(f(np))，其下采样的算法复杂度为O(f(nn))则DWES在采样过程中时间复杂度为：O(f(np))+O(f(nn))，在训练分类器时计算权重的复杂度为O(n*f(n))，故其分类器计算的复杂度为：m*O(n*f(n)).DWES算法复杂性为：O((f(np)+f(nn))*n*f(n)*m),m为样本中数据块的总个数.

4 实验分析

4.1 实验设置

在本实验中，我们使用了4个合成数据流跟两个真实环境数据流，他们的详细信息如表1所示,小类样本在每个块中所占的百分比固定在块大小的 5%.

表1 六种数据流信息表

本文算法在开源平台MOA[26](Massive Online Analysis)基础下实现，实验程序由matlab编写，实验程序在CPU为2.4GHz,内存为8GB，操作系统为WIN10的PC机上进行实验.为了验证DWES的有效性，我们比较了5种权威的处理带有概念漂移的不平衡数据流的算法：LPN[13]、DWM[14]、DFGW[15]、DWMIL[16]、REA[20]，分析它们与DWES算法在6种不同类型数据流上的表现情况.DWM在使用时，采用Under-sampling Online Bagging(UOB)算法来进行处理.

DWMIL、DWM、LPN、DWES基分类器大小T设置为11.DWMIL、DWES分类器的阈值θ设置为0.001.LPN、DWMIL的误差函数ε(t)=1-(GMean),所有算法都通过CART训练基分类器[19].所有的实验跑10次取平均值.

4.2 实验比对与分析

DWES中利用马氏距离寻找正类样本点时，为了找到合适的均方差的阈值上限值，我们分别对不同的均方差阈值上限(DCOV值)进行实验，实验结果如图3所示.

图3 DCOV值与AUC值的关系

从实验得出在DCOV值取为7的时候多数数据流达到AUC值最优时刻，因此实验中我们选取DCOV值为7.

以AUC、G-Mean、F-measure、Precision为评价指标，采用先测试后训练的策略对各种算法在每个数据块上进行评价.每个数据块的AUC值、G-Mean值、F-measure值如图4-图6所示，根据折线图可以看出，由于是先测试再训练，因此所有的算法的评价指标的初始值是相同的.在AUC评价标准上，DWES算法相较于其他算法，在Moving Gaussian、Hyper Plane、SEA、Electricity、Weather 5个数据流上有更好的性能，在Checkerboard数据流上与Electricity数据流上，跟DWMIL算法平均性能大致相同.相较于DWMIL外的其他算法有更高的精度.在F-Measure评价标准上,由于我们的算法对正类样本有更好的识别度，因此DWES算法在F-Measure评价标准上性能在6个数据流上优于其它所有算法.在G-Mean评价标准上,REA算法在Moving Gaussian数据流上逐渐减少到0，这是由于其在仅采用上采样算法处理存储的小类样本集，对有些数据流的概念漂移问题无法很好地处理.DWES算法在上采样的同时对大类样本进行下采样，以此来解决这种问题，因此DWES在这种情况下发挥更好的性能，相较于其他算法DWES在G-Mean评价标准上表现优异，在Checkerboard数据流上由于对大类样本采用下采样技术，因此降低了对大类样本的识别度，导致G-Mean值提升不明显.

图4 每个数据块的AUC值

图5 每个数据块的F-Measure值

图6 每个数据块的 G-Mean值

各算法的综合性能表现如表2-表6所示，在AUC评价标准上，DWES对比DWMIL算法在6个数据流上平均提升4.07%，其中最好表现在Hyper Plane数据流上，对比DWM算法提升了29.64%.在G-Mean评价标准上，DWES对比DWMIL算法在6个数据流上平均提升1.74%，总体来说，其中最好表现在Moving Gaussian数据流上，对比REA算法提升了44.59%.在F-Measure评价标准上，DWES对比DWMIL算法在6个数据流上平均提升20.85%.最好的表现在Checkerboard数据流上，对比DWM算法提高了58%.在Precision评价标准上，DWES对比DWMIL算法在6个数据流上平均提升29.01%，其中最好表现在Moving Gaussian数据流上，对比DFGW算法提升了58.2%.

表2 AUC值

DWES算法采用类似REA算法思想选取小部分之前存储的正类样本参与到当前分类器的训练，并且根据正类样本的数量取相同数量的负类样本形成平衡的样本对，利用多个平衡的样本对训练分类规则组成当前数据块的分类器，这样做相对于仅将部分正类样本拿到当前数据块进行训练的REA算法，或者利用自身样本进行上采样的DFGW算法来讲，能够增加对正类样本的识别度，并且避免产生噪声样本点，DWM、Learn++并没有对不平衡数据进行预处理，使得DWES算法在识别为正类样本的数据中有更多的是真正的正类样本，因此在Precision评价标准上相对于其他算法表现较好；在对新的数据块做测评时，因为新的数据块中有较多之前没出现过的正类样本，或者出现正类样本与负类样本概念互换(即发生概念漂移)的情况，DWES算法采用基于熵值的权重修改策略，动态寻找对综合表现影响最高的评价指标，通过评价指标值动态的更新分类器的权重，并不断淘汰权重较低的分类器，相对于仅采用单一评价指标来更新分类器的DWM算法和DWMIL算法或者通过时间的增加来减小分类器权重方法的Learn++算法能够分别增加正类样本跟负类样本的识别度，使得全部正类样本被识别为正类样本的数量大于其他算法，即Recall值优于其他算法；同时也会提高对负类样本的识别度，全部负类样本中识别为负类样本的数量大于其他算法，又由于Recall值优于其他算法，所以G-Mean值相对于其他算法表现较好；F-measure值与Precision值跟Recall值呈正相关性，由于Precision值跟Recall值均高于其他算法，因此F-measure值也会优于其他算法.AUC值是ROC曲线与坐标轴围成的面积，DWES通过多种机制提高正类样本的识别度，同时也会提升了负类样本的识别度，使得模型的鲁棒性更高，ROC去线下的面积相对于其他算法也会较大，最终使得AUC值优于其他算法.总体来说，DWES算法对比其他算法在处理带有概念漂移的不平衡数据流问题时有更好的性能.总体来说，DWES算法对比其他算法在处理带有概念漂移的不平衡数据流问题时有更好的性能.

表3 G-Mean值

表4 F-Measure值

表5 Precision值

表6 时间(秒)

4.3 算法效率分析

时间复杂度对评价在线学习算法的性能方面发挥重要的作用.表6给出了6种算法在六种数据流中运行时间，综合来看DWES算法在运行时间方面相比其他算法排在第三，这是因为DWMIL算法采用基于下采样的Bagging算法，而DWES在此基础上还增加了上采样算法，因此时间花费要多于DWMIL算法，由于REA算法采用单一的决策树算法，其在某些数据集上速度会更快.LNIE使用所有训练的分类器对每个数据块进行训练，因此预测成本会高一些，DWM是最慢的，这是由于它一对一的学习方法，而其他算法是基于数据块的，处理时间会快于这种一对一的学习方法.

5 总结与展望

类不平衡与概念漂移是数据流处理的两个难点问题.针对带有概念漂移的不平衡数据流问题，本文提出了基于上采样与下采样结合的集成分类算法-DWES，该算法能同时解决数据流的不平衡和概念漂移问题，并能提高对小类样本的辨识度.最后在六个带有概念漂移的不平衡数据流上对比五种权威的算法，综合结果表明DWES算法相比于其他算法在解决带有概念漂移的不平衡数据流上有更高的精度.下一步将探索通过样本的分布去计算数据集的不平衡率，将算法拓展到解决多类数据流不平衡问题上去.