新型含噪数据流集成分类的算法

袁 泉，郭江帆

(1.重庆邮电大学通信新技术应用研究中心，重庆400065; 2.重庆信科设计有限公司，重庆401121)(*通信作者电子邮箱502420381@qq.com)

0 引言

随着大数据、云计算的深入发展，每个行业都产生了海量的数据，这些数据的形式发生了变化，从传统的静态数据演变成动态数据。现实中的数据流不仅具有海量性、实时性、动态变化等特征，通常还伴随着噪声和概念漂移，这些特征无形中加大了对数据流挖掘的难度。所谓概念漂移指的是随着数据流的不断增加，隐含在数据流中的知识随着时间的变化而发生变化［1］，另外，真实环境中的数据流噪声问题也是无法避免的。虽然传统的静态数据挖掘技术对概念漂移和噪声问题也有所研究，但效果不佳。为了能更快速、有效地利用数据流，目前有单一和集成两种形式的分类算法，集成模型算法分类精度要比单一模型算法高，因此集成模型成为主流研究方向之一。

1 相关工作

在数据流分类中关于概念漂移和噪声问题的研究，国外比国内要早。其中在数据流概念漂移问题研究中:Street等［2］在2001年提出适应概念漂移的集成分类(Streaming Ensemble Algorithm，SEA)算法，该算法采用集成决策树方法检测概念漂移;Kolter等［3］在2003年提出了weighted-bagging算法，该算法引入集成分类器思想，采用投票方式检测概念漂移;Kuncheva等［4］在2009年提出了基于窗口机制的分类算法，该算法能够有效区分概念漂移，但只适用于突变式概念漂移。在关于数据流中渐进式概念漂移问题中:Domingos等［5］在2001年提出了基于快速决策树(Very Fast Decision Tree，VFDT)算法，该算法利用给定的空间和时间可以训练出一个渐进于传统算法的学习器，但是它只能处理范畴型的属性;Liu等［6］在 2009年提出以自适应快速决策树(Conceptadapting Very Fast Decision Tree，cVFDT)算法为基础的基于模糊决策树的数据流分类算法，该算法可以很好地解决数据流中的概念漂移问题，但分类精度并不是很高。

在数据流中的噪声处理中:Chu等［7］在2004年提出集成数据流分类算法是一种期望最大化(Expectation Maximization，EM)框架，该算法是求解极大似然估计的迭代算法，精度提高的同时增加了时间代价;Gama等［8］在2006年提出的分类算法是基于伯努利数据分布，该算法适合于处理突变型概念漂移，而对于渐变型漂移效果并不明显;Baena-García等［9］在2006年根据分类错误率设计了一种数据流分类算法，该方法依据模型错误率变化和错误率之间的距离来判断概念漂移;Hashemi等［10］在2009年根据模糊逻辑理论设计了一种分类算法，该算法克服了传统噪声清理方法需要多次扫描的缺点，避免了噪声对分类的影响;琚春华等［11］在2015年提出基于信息熵差异性度量的数据流增量集成分类算法，该算法引入信息熵差异性度量对分类模型进行优化，但系统开销较大;Mirza等［12］在2015年提出极限学习机集成算法，该算法分类精度较低，泛化能力较差;吕艳霞等［13］在2016年提出了不确定数据流在线分类算法，该算法采用Hoeffding分解定理构造决策树模型，但主要针对不确定数据流有较高的精度;陈煜等［14］在2017年提出基于红黑树的连续属性数据流快速决策树分类算法，该算法利用红黑树有效地处理样本的插入，主要处理连续属性数据流，但对离散属性效果并不好。

以往研究中提出了大量集成分类算法，但是在对数据流中的概念漂移检测和噪声过滤，以及分类精度的提高等方面的研究不足。针对以上问题，本文提出了一种新型的过滤噪声和检测概念漂移数据流集成分类算法。该算法集成分类模型中的基分类器选择增量式C4.5决策树，噪声过滤机制采用贝叶斯分类器，用μ检验方法检测数据流中的概念漂移。本文进行了大量实验和算法仿真，验证了本文算法的分类精度 比 传 统 算 法 ( 如 OzaBag［15］、OzaBoost［15］、Weightbagging［16］)有较大的提升。

2 数据流分类算法

本文提出了一种新型的面向噪声和概念漂移数据流的集成分类算法(Ensemble Classification Algorithm for data streams with Noise and Concept Drifts，ECANCD)。该算法首先将数据流分成M个数据块，根据M个数据块建立M个增量式C4.5决策树基分类器并进行水平集成，然后对M个数据块建立一个噪声过滤机制，采用贝叶斯分类器用来过滤噪声数据的影响，利用μ检验方法进行概念漂移的检测，此时模型中共有M+1个分类器。对每个增量式C4.5决策树基分类器进行动态的加权，基分类器加权策略是将分类器的分类精度设置为权值，将分类精度最小的基分类器舍弃，以完成分类模型的更新和分类器性能的提升。

2.1 增量式C4.5决策树

2.1.1 增量式学习方式

因C4.5算法不具有增量学习的能力，当C4.5利用当前数据块学习训练好模型后，如果有新到来数据块，C4.5必须利用上一数据块和当前数据块重新训练模型，因此必须对C4.5算法进行改进才能具有增量学习能力。所谓增量学习即在有新数据块到来时，会在已有分类器的基础上对新数据块训练并更新分类器，得到增量式C4.5决策树分类器。在这个学习过程中增量式C4.5决策树算法大幅减少了时空开销，并且在一个集成分类器投入使用之前，很难得到所有学习训练实例。因此，一个集成分类器具有增量学习能力是非常重要的。

2.1.2 对 C4.5 算法的改进

乔增伟等［17］在C4.5决策树算法的增量式改进方法中曾提到，C4.5决策树算法是单向链表，可以通过两点结构改动实现增量学习过程:第一，将单向链表修改为双向链表，在结构体里添加一个指针变量FatherNode指向父节(FatherNode=NULL时为根节点)，以实现在增量学习过程中更新某些节点属性值;第二，通过记录叶节点包含的实例，实现增量学习功能，即叶节点知识更新，可以添加一个动态数组DynaArray，只有NodeType=0时动态数组才分配内存。

但改进后的C4.5决策树算法在单分类器中分类精度并不是很理想，因此本文采用集成分类算法，选择增量式C4.5决策树算法作为基分类器，以提高分类精度。

2.1.3 增量式C4.5算法流程

C4.5算法改进后就可以实现增量式学习，具体算法流程如图1所示。

图1 增量式C4.5算法流程Fig.1 Flow chart of incremental C4.5 algorithm

从图1中分析可知:当数据流输入时在当前模型下进行增量学习，通过决策节点判决后，当决策类别与实例类别相同时更新判决节点、实例数以及类别分布，并在动态数组中添加实例;否则，重新寻找最优属性和分割阈值，然后生成叶节点并将其父指针指向判决节点，最后更新判决节点，删除原节点包含的实例数。通过上述过程实现增量学习。

2.2 概念漂移检测方法

本文检测概念漂移的方法是大样本检验母体平均数的μ检验方法。该检测方法是判断某一随机变量的数学期望是否等于已知值的假设验证法。

μ检验定义:设母体X分布是任意的，且一、二阶距存在，记 EX=u，DX= δ2(δ2未知)，在母体上作假设H0:u=u0(u0是已知数)［18］。用x珋作检验，当无限大时，统计量U=(x珋－μ0)/(S/)近似服从标准正态分布N(0，1)，其中:x珋表示样本平均数，S表示样本标准差。

假设给定显著水平 α，则存在 uα/2，使 P{|U|≥ uα/2} ≈α，即P{(X珔－ μ0)/(S/)≥ uα/2} ≈ α。

假设单个样本被误分类概率P{X=1}=p，正确分类的概率为P{X=0}=1－p，则可知X服从两点分布B(1，p)。设样本数为n，被错误分类数为m，则 X=m/n，S2=X(1－X)。

以上原理可以判断数据流是否发生概念漂移。假如设当前数据块的分类错误率为 error，当uα/2(其中uα/2为前M个数据块的平均分类错误率)时，当前数据块的分类错误率大于前M个数据块的平均错误率，从而说明数据流发生了概念漂移;反之认为概念分布平稳。

2.3 ECANCD 描述

对算法中要使用的符号进行说明，设数据流中当前数据块为S，当前数据块S中的第i个实例为Ei，基分类器的集合为Ec，Ec基分类器的总数为M，Ec中第i个实例为Ci，Ec中当前分类器的个数为num，一个数据块包含的实例的个数为n。

ECANCD的具体构建过程流程如下:

1)构建集成分类器。新的数据块S通过滑动窗口到达后，判断基分类器个数num是否小于基分类器总数M，如果num ＜M，则在S上建立一个新基分类器，并把其放入基分类器的集合Ec中;否则，在缓冲区最新的M*n条实例上建立一个噪声过滤机制，即贝叶斯分类器。

2)过滤噪声。当集成分类器建立完成后，使用M个基分类器和噪声过滤机制对S中的实例进行分类，若此实例被半数以上的基分类器和贝叶斯分类器误分类，则将这个实例放置到误分类缓冲区。

3)检验概念漂移。计算Ec在数据块S上的分类错误率均值error，利用μ值检验法对概念漂移进行检测。

4)分类器更新。若检测到概念漂移，则将误分类区中所有实例读入到数据块S，并建立一个新的基分类器Cnew，更新每个基分类器的权值(均为S上的分类精度)。若Cnew大于基分类器中最小的权值Cmin，作则用Cnew替换Cmin，完成基分类器动态更新。

ECANCD伪代码如下。

输入 数据流DS;

输出 分类模型Ec。

BEGIN

While(new data streams){

通过滑动窗口读入一个包含n个实例的数据块;

if(num＜M)

每个数据块建立一个基分类器;并将其放入Ec中;

else

在读入M个数据块M*n个实例后建立一个噪声过滤机制;}

for(Ei∈S){

if(Ei被Ec和噪声过滤机制误分类)

则把实例Ei放入误分类区;

}

把Ec中基分类器的权值更新为S上的分类精度

if(concept drifts and num==M{

将被误分类的实例和部分新实例构建一个新基分类器Cnew，更

新所有分类器的权值，找出权值最小的基分类器Cmin。

if(Cnew＞Cmin)

用Cnew替换Cmin;

}

}END

3 实验结果与分析

本文实验硬件环境为2.6 GHz处理器、8 GB内存的PC，操作系统为Windows 10，开发环境为Weka3.8和大规模在线分析系统(Massive Online Analysis，MOA)。本文分别从检测概念漂移的准确性、抗噪性、分类精度、基分类器性能等方面在 KDDCup、Hyper Plane、Kaggle 数据集［19］进行了验证，并和OzaBag、OzaBoost、Weight-bagging等其他经典的数据流分类算法进行了严格比较。实验中使用的概念漂移基准数据集均由开源工具MOA中的数据生成器生成。

3.1 实验参数分析

本文提出的ECANCD采用集成框架，其中包括M个基分类器和1个噪声处理机制，数据缓冲块的大小是很难从理论上确定。若缓冲数据块过多，则不可避免地会增加算法的时空开销，甚至降低该算法的分类精度;相反的，如果缓冲数据块过小，则噪声干扰就会难以消除。基于此，本文对数据缓冲块M的取值大小进行了大量的实验验证，结果表明当M=10个缓冲数据块，每个数据块包含500个实例，误分类缓冲区实例个数的阈值为100，μ检验方法中α=0.95时，分类效果较优，算法其他相关参数均采用相应文献中设置的参数值。

3.2 概念漂移检验

对于概念漂移的检测，本次实验选取含噪率在0%～30%(间隔5%递增)的KDDCup数据集，在不同噪声的情况下观察分析ECANCD分类精度来验证对概念漂移的检测效果。图2描述的是对KDDCup数据集进行学习，对该数据集的10% ～100%(间隔10%递增)进行测试的结果，其中测试集百分比为实验数据集占整个数据集的比例。

图2 ECANCD概念漂移检测Fig.2 Concept drift detection with ECANCD

从图2中可以看出，当数据噪声为零时，分类精度基本保持在91%～97%;并且当含噪率从0%增加到30%的过程中，分类器的分类效率在逐渐降低，且波动很大。分析其原因是:当噪声的比例增加，噪声数据在数据集中所占的比例就会增大，则真实数据就会减少，ECANCD的过滤效果就会变弱;但是当集成分类器检测到概念漂移后就会对分类器作出调整以适应于当前概念的数据流，分类精度就会随之提高。如图2所示，随着数据集的增加，该算法的分类精度可以达到95% ～97%。ECANCD能在含噪数据流中检测概念漂移，并能不断更新分类数据模型，提高分类精度。

3.3 抗噪性能检测

为了验证本文所提ECANCD的抗噪声性能，在含噪率为5%、10%、15%、20%、25%、30% 的 Hyper Plane、KDDCup、Kaggle数据集上进行大量的实验，实验结果如图3所示。从图3综合分析可以得出以下结论:

1)从图3(a)中得出，在HyperPlane数据集上随着数据流中噪声比例的逐渐增加，每种算法的分类精度都在逐渐减少。

2)从图3(b)中得出，KDDCup数据集上含噪率相同的情况下，ECANCD比其他三种算法分类精度高。

3)从图3(c)中得出，Kaggle数据集上在含噪率较低的情况下，各算法分类精度差别不大，ECANCD并不比其他算法有明显优势;但随着噪声数据的增长，ECANCD的分类精度明显优于其他算法。

4)从图3中得出，ECANCD的分类精度随着噪声的增加波动并不明显，但其他算法波动较为明显。

图3 不同数据集上分类精度对比Fig.3 Comparison of classification accuracy on different datasets

从图3中可以看出，ECANCD的分类精度始终保持在90%以上，而其他三种算法的分类精度均有所下降，部分已下降到70%以下。分类精度之所以有所下降，是因为数据流中噪声数据逐渐增加，真实数据的比例会逐渐降低，分类器如果不能及时适应于当前概念，则分类精度会越来越低。一旦当分类器检测到概念漂移之后，噪声过滤机制会过滤掉噪声，分类模型进行增量式学习并更新模型，因此分类模型一经更新后会迅速适应于当前数据流环境，进而提高了分类精度。

由上述分析可以得出，ECANCD对概念漂移数据流具有较强的抗噪性。

3.4 分类精度分析

ECANCD 和 OzaBag、Ozaboost、Weight-bagging等经典数据流分类算法在 HyperPlane、KDDCup、Kaggle含噪率为10%的数据集上的实验结果如表1所示。从表1可以得出，ECANCD在分类精度上要比其他三种算法更优:在数据集HyperPlane上，ECANCD的分类精度比OzaBag算法高出5.83个百分点，比 Ozaboost算法高出7.36个百分点，比 Weightbagging算法高 23.25个百分点;在数据集 KDDCup上，ECANCD的分类精度比OzaBag算法高出6.93个百分点，比Ozaboost算法高出6.53个百分点，比Weight-bagging算法高23.6个百分点;在数据集Kaggle上，ECANCD的分类精度比OzaBag算法高出8.92个百分点，比 Ozaboost算法高出7.32个百分点，比Weight-bagging算法高13.23个百分点。

表1 含噪率为10%时，不同算法的分类精度 %Tab.1 Classification accuracy of different algorithms when noise ratio is 10% %

ECANCD 在 HyperPlane、KDDCup、Kaggle三个数据集上都能很好地作出分类，并且明显要优于其他三种算法;OzaBag、Ozaboost算法在 HyperPlane、KDDCup、Kaggle三个数据集上的分类精度相差不大，Weight-bagging算法分类精度较低，其原因可能是这三个数据集的数据分布不平衡，不利于Weight-bagging算法分类能力的提高。由上述分析可得，ECANCD对含有噪声和概念漂移的数据流分类效果更好。

3.5 基分类器性能比较

在本文ECANCD的基础上，将基分类器替换成经典的支持向量机分类器和增量式C4.5决策树分类器在KDDCup数据集10%的子数据集上进行基分类器基本统计量和时间性能上的比较。本节实验使用的实验平台为MOA，该平台是基于WEKA的数据流在线分析平台，可以将KDDCup数据集模拟成数据流，以此达到动态真实数据的效果。实验结果如表2和图4所示。

表2 KDDCup数据集上基本统计量比较Tab.2 Comparison of basic statistics on dataset KDDCup

图4 KDDCup数据集上的时间性能比较Fig.4 Comparison of time performance on dataset KDDCup

从表2中可以看出:在分类正确率上，增量C4.5决策树分类器比支持向量机分类器高了2.67个百分点，分类器性能有所提高;在Kappa统计量上，增量C4.5分类器比支持向量机分类器高了0.0023，Kappa统计量越大则分类器性能越好，反之越差;在误差值上，增量C4.5分类器比支持向量机分类器在平均绝对误差上高0.0184，在均方根误差上低0.0078，在相对均方根误差低3.85个百分点，误差值越低分类模型准确度越高。

从图4中分析出，当基分类器选择支持向量机时，分类算法较基分类器为增量C4.5时运行的时间较长，可以看出基分类器选择增量C4.5时在时间有效性更优越。从时间和空间复杂度上分析，支持向量机并不适合于处理过大的数据。核化后的SVM的时间复杂度为O(mn2)，m为样本数，n为特征数。当数据量过大时，还要面临空间复杂度的问题;而增量C4.5通过剪枝减少空间复杂度。图4中实际实验运行时间可以有效印证增量C4.5在复杂度上的优势。

通过上述分析可以得出:增量C4.5决策树分类器在真实动态数据中的分类时间、分类精度、Kappa统计量、均方根误差和相对均方根误差均比支持向量机分类器优越，因此本文所提的ECANCD分类算法确实在数据流挖掘中效果更好、性能更优。

4 结语

针对数据流中噪声问题和概念漂移问题，本文提出了一种新型的含噪数据流集成分类算法(ECANCD)。为了能够实现对概念漂移检测和噪声过滤，引入噪声过滤机制和假设检验方法，采用增量式学习方式构成集成分类器。通过大量实验的分析与比较，该算法不仅能够检测概念漂移和过滤噪声，并且具有较高的分类精度。但是真实数据流中的大量数据是无标签的实例，因此下一步的主要研究方向是利用半监督学习技术在不完全标记的数据流环境中实现概念漂移的检测与分类。