面向复杂数据流的集成分类综述

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

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

传统的机器学习算法主要处理静态数据，但现有的数据多数以数据流的形式出现，这改变了人们存储、通信和处理数据的方式。在许多新的应用中，人们面临着不断变化的数据流。例如Web点击流分析、网络日志、交通流量监控与管理、电信数据管理等[1]。随着研究人员对数据流的研究，展开了对复杂数据流类型的钻研。但是，在处理不平衡、高维、有噪声数据时还是无法获得令人满意的性能。在这种背景下，如何有效地构建一个高效的知识发现和挖掘模型成为数据挖掘领域的一个重要课题。

集成学习是目前的一个研究热点内容，旨在将数据融合、数据建模和数据挖掘整合到一个统一的框架。经典的数据流集成分类算法有在线精度更新集成(online accuracy updated ensemble algorithm, OAUE)[2]、杠杆装袋(leveraging bagging，LevBag)[3]等。其中有处理概念漂移的流集成算法(streaming ensemble algorithm，SEA)[4]、动态加权多数算法(accuracy weighted ensemble，AWE)[5]等;处理不平衡数据集的SRE[6]、RE-DI[7]算法等；处理多标签流的分类器链集成模型(ensemble of classifier chains，ECC)[8]和处理多实例数据流的OMB(online MIL boosting)[9]算法等。这些都是一些经典的复杂数据流集成算法。

之前已有研究人员对数据流分类研究的综述。如：Lemaire等[10]从数据流的学习方式入手，以单分类器处理数据流为主要方法，简要介绍了常见的数据集以及评估方法；Gomes等[11]对数据流集成分类进行了全面综述，涉及到分类多样性以及动态更新，主要是针对概念漂移数据流；Iwashita等[12]从稳态到动态数据流进行展开，从分类到回归进行详细介绍，还对数据流的一些高级问题进行了探讨。以上数据流的综述，虽然介绍了常见数据流的处理方法，但是没有细分数据流的种类，大多数还是以处理单类型数据流为主要研究对象，同时数据流的评估技术、指标只是简要提及，没有归纳总结。本文的综述框架如图1所示，主要贡献如下：

图1 复杂数据流分类框架

1)全面归纳近些年集成学习研究稳态、概念漂移、不平衡、多标签、多实例数据流，并对提出的集成算法进行对比。

2)首次归纳近些年集成学习处理文本、图、传感器领域数据流的算法研究进展。

3)对复杂数据流用到的验证技术、评估指标进行全面总结。

1 复杂数据流集成分类

训练过程经过基分类器的组合，然后使用组合策略(例如经典的多数投票)得出最终的预测结果。单分类器在快速到来的数据流中无法很好适应变化，但是集成结构可以使分类模型更加高效[14]。集成学习对不同的复杂数据流会有不同的实施策略，使用在线学习、块学习以及增量学习等关键技术使模型拟合效果更好。本章将在最后总结集成学习处理复杂数据流算法性能的对比，从集成方式以及优劣势等方面进行概括。

数据流类型中稳态数据流最平稳，它不需要考虑复杂情况，逐渐淡出人们的研究热点。但是一些经典的算法值得大家去探讨，它是人们早期研究数据流的一种探索。在稳态数据流中，使用块的算法相对于在线学习研究得不多。早期经典的Learn++[15]是一种神经网络分类器集成算法，在很多实验的对比算法中被提及。该算法对到来的数据块构建新的神经网络模型进行增量训练，然后采用多数投票的决策机制进行预测。研究人员在分析了Learn++优缺点的基础上，提出了异构Bagging++算法[16]，它使用Bagging为每个数据块生成一个增量集成算法，该算法利用Bagging从传入的数据块中构建新的模型。

在线学习是集成学习中常用的技术，在线学习算法对到达的实例进行一次处理，可以对数据流分类做出更快速的反应。OzaBag算法[17]要求整个训练集立即可用，它使每个基分类器都用新到达数据的k个副本进行更新，其中k服从k～Possion(1)分布，在精度方面与批处理分类的版本相当。而OzaBoost集成算法[17]维护一个固定大小的集成，这些分类器根据收到的实例进行训练,每个新实例都按顺序更新分类器。如果实例被前一个分类器误分类则会更新其权重，以供后一个分类器更加重视错误分类的实例。另外，Bifet等[3]提出了LevBag算法，该算法将Bagging技术的简单性与分类器输入和输出中添加更多随机化相结合，通过对输入实例的权值进行随机化来提高集成的精度。

1.1 概念漂移数据流

在动态环境中处理数据流的一个最大挑战就是概念漂移[18]，当被收集的数据所涉及的概念经过一段时间的稳定后发生变化，概念漂移就会发生。如今的概念漂移数据流主要采用主动和被动2种方式来进行处理，图2展示了概念漂移处理的常规过程。本节主要讨论基于块学习和基于在线学习的集成学习方法角度去处理概念漂移数据流。

图2 概念漂移处理过程

1.1.1 基于块学习的集成

基于块学习集成的思想是将到来的数据流划分为数据块去更新基分类器，如果分类器数目超过设定的集成大小，则用新构建的分类器替换效果差的分类器，之后采用组合策略预测结果。动态替换分类器的思想是适应概念漂移常用的办法。

Wang等[5]提出一种精度加权集成分类(accuracy weighted ensemble, AWE)算法，它能适应潜在的概念漂移，但在渐变漂移方面效果并不佳。为了改进算法，Deckert等[19]提出一种新的概念漂移处理算法，即批处理加权集成分类算法(batch weighted ensemble, BWE)，用于处理带有突变性和渐变性漂移的数据。该算法将数据流实例处理成相同大小的块，并将漂移检测器引入集成框架，比AWE算法有着更好的精度。为了更好应对各种漂移类型的数据流，Brzezinski等[20]提出一个基于块的流集成分类模型AUE2(accuracy updated ensemble)，旨在对不同类型的概念漂移做出反应。该算法的主要新颖之处在于将集成加权机制与基分类器的增量训练相结合，与AWE中使用的线性函数不同，其加权函数采用非线性加权函数，计算公式为：

(1)

(2)

(3)

目前一些方法认为，在连续处理数据流的同时更新集成的方法是不合适的，会面临一些问题，例如无限增长的集成大小或在处理概念漂移时删除其所有的基分类器的情况。Bertini Junior等[21]提出迭代Boosting流集成(iterative boosting streaming ensemble, IBS)算法，它将集成算法Boosting应用于数据块，通过添加一定数量的基分类器来维持集成结构。潘吴斌等[22]提出一种基于信息熵的自适应网络流概念漂移分类方法，根据特征属性的信息熵变化检测概念漂移，使用增量集成学习策略引入新样本建立的分类器，这是一种新颖的训练分类器方式。

传统数据流挖掘阶段中概念漂移的检测需要标记样本的可用性，在实际情况中就时间和资源利用率而言，获取带标签的样本成本比较高。Abdualrhman等[23]提出基于集成分类器的确定性概念漂移检测(DCDD)方法，集成算法选用经典的AdaBoost算法，该漂移检测方法可以检测概念漂移的存在，但它与分配给样本的标签无关。该方法具有较高的漂移检测率和较小的虚假警告率及漏失率，可以扩展检测概念漂移，然后通过集成分类器进行预测。

1.1.2 基于在线学习的集成

在线学习集成算法采用一种实时处理数据的思路，它不是以存储到一定量数据的块方式学习。随着类标签的在线到达，在线算法可以比在处理数据块的环境中更快地对概念漂移做出反应，是一种按照时间顺序学习并不断修正的模型，能更好地拟合数据[24]。

分类器或实例加权的思想一直是大家研究的重点内容，通过不断创新加权方式来适应概念漂移是一种常见的被动式方法。OAUE[2]是一种经典的算法，该方法将基于块的集成优点和在线集成优点相结合，对存入的每个实例进行训练以及对分类器进行加权，创新之处是提出高效的基分类器加权函数。Ancy等[25]提出一种基于自适应在线学习规则(stream data mining on the fly using an adaptive online learning rule, SOAR)挖掘方法。SOAR综合了基于块和网络集成的基本特征，并根据其分类效果更新每个基分类器的权重。它使用了自适应窗口以处理渐进和突然的概念漂移。Feitosa等[26]提出一种处理概念漂移的集成优化分类算法(ensemble optimization approach for concept drift，EOCD)。它使用基于优化技术的显式自适应机制来为检测到的概念漂移定义最合适的集成结构，主要优点是通过已构建的集成结构去处理反复出现的漂移。

多样性处理概念漂移是一种很新颖的技术。Liu等[27]提出一种多样性实例加权集成算法(diverse instance weighting ensemble, DiwE)，同时还提出一种新的多样性度量方法。该方法对区域分布变化的评估概率被用作实例权值，通过不同的方案构造不同的区域集，会导致不同的漂移估计结果，从而产生子集。该研究新颖之处在于根据集成之间区域漂移概率的不同来测量多样性。Sidhu等[28]提出多样化在线集成检测(diversified online ensembles detection, DOED)，该方法保留了2个加权分类器集成结构，一个是低多样性的集成，另一个是高多样性的集成，并根据其对新数据实例的分类精度进行更新。近些年也有研究将动态加权和多样性相结合来提高精度。Sidhu等[29]提出多样化动态加权多数(diversity dynamic weighted majority，DDWM)算法,对具有不同概念分布的新实例进行分类。该方法维持了2组在多样性水平上不同的加权集成结构，根据分类精度更新或删除一个集成中的基分类器，并根据算法的最终全局预测和任何实例集成的全局预测添加一个新的基分类器。

1.2 不平衡数据流

非平稳数据流除了要考虑概念漂移问题外，还受数据复杂性的影响。经常遇到的类不平衡，主要特点是某一类别的样本数量明显多于其他类别的样本数量。类不平衡甚至对静态数据学习也是一个障碍，因为分类器偏向的是大多数类，并倾向于对少数类实例进行错误分类[30]。使用集成学习处理不平衡问题是一种有效的方法，本节将从数据预处理和代价敏感算法结合集成学习来处理不平衡数据流展开讨论。

1.2.1 基于预处理的集成

在不平衡数据中，研究人员希望能从数据层面降低少数类与多数类样本的不平衡程度，其中数据的重采样是代表性的方法，它可以获得均匀的类分布。基于重采样的方法主要有欠采样、过采样以及两者结合的混合采样。欠采样从多数类样本中删除一些实例，过采样则增加少数类样本的实例。集成学习与预处理的技术结合是目前处理不平衡问题的主要研究方向之一，它可以极大地提高算法的预测性能。

近些年随着研究人员对不平衡数据的研究深入，集成学习与重采样技术结合屡见不鲜。Wang等[31]改进了基于在线Bagging的过采样(oversampling based online bagging, OOB)和欠采样(under-sampling based online bagging, UOB)技术，利用重采样和时间衰减度量对OOB和UOB集成学习方法进行改进，以克服在线类不平衡问题，最后结合各自优点提出加权集成方法WEOB1和WEOB2，两者的准确性优于OOB和UOB。肖梁等[32]采用Bagging集成框架，算法采用多集构建和特征提取与多集融合模块构成，通过改进重采样构建多个不平衡训练集，有效缓解数据分布不平衡、噪声和样本重叠问题。最近，Zyblewski等[33]提出结合动态集成和预处理技术的框架来处理高度不平衡的数据流，利用分层Bagging分类器对少数类和多数类分类进行替换抽样的方法。Ren等[6]提出一种选择的重采样集成(selection-based resampling ensemble, SRE)算法，用于学习复杂数据分布下的不平衡数据流中的概念漂移。SRE结合重采样和定期更新的结构来处理联合问题。在基于块的集成框架中，首先采用基于选择的重采样机制来重新平衡最新块的类分布，然后，使用最新的样本定期更新先前的集成成员，并确定更新权值同时对错误分类的分类器给予惩罚。段化娟等[34]采用Tomek link欠采样技术和集成方法结合的策略来获得多个平衡后的子集，每个子集使用决策树训练，最后集成多个决策树。

在不平衡数据流中也面临着概念漂移的问题，是目前研究的一个新兴内容。Ancy等[35]提出动态采样和集成学习技术相结合处理带有概念漂移的不平衡数据流分类算法(handling imbalanced data with concept drift, HIDC)。当面临类不平衡的情况则采用过采样和欠采样技术，其中不平衡率θ的检测使用公式(4)，

(4)

式中Amaj和Amin分别代表多数类和少类数的初始分类精度。HIDC采样模型训练候选分类器，并用候选分类器替换最差的集成成员。Zhang等[7]提出基于重采样的处理概念漂移不平衡数据流的集成分类框架(resembling-based ensemble framework for drifting imbalanced stream, RE-DI)。该集成框架由处理渐变概念漂移的长期静态分类器和处理突变概念漂移的多个动态分类器组成。集成分类器的权重从2个方面进行调整：首先，时间衰减策略降低动态分类器的权重，使集成分类器更加关注数据流的新概念；其次，提出一种新的强化机制来增加在少数类上表现更好的基分类器权重，并降低表现较差的分类器权重。

1.2.2 基于代价敏感的集成

除了通过改变数据的分布来降低类别不平衡对分类的影响，还可以从算法层面去考虑，设计适应于不平衡数据特征的模型。代价敏感[30]考虑不同误分类类型的代价，代价矩阵将样本从一个类别分类为另一个类别的惩罚进行编码。针对二分类定义一个代价矩阵，如表1，C(i,j)表示将类别i中的一个实例预测为类别j的代价。在处理类别不平衡问题时，辨别正实例的重要性高于负实例，因此，误分类一个正实例的代价大于误分类一个负实例的代价,即C(+,-)>C(-,+)。做出正确的分类通常不会带来任何惩罚，代价敏感学习过程寻求最大限度地减少高代价错误的数量和总错误分类代价。

表1 代价矩阵

Sun等[36]将代价敏感与集成算法Boosting进行结合，综合分析AdaBoost算法在解决类不平衡问题上的优势和不足，探索了3种代价敏感的Boosting算法，即AdaC1、AdaC2、AdaC3，将代价项引入到AdaBoost学习框架中，进一步分析所提出的算法符合统计中的阶段性加法建模，以减少代价指数损失。Tao等[37]提出一种基于代价权重的支持向量机的代价敏感集成算法。该方法为了保证基分类器优化目标与Boosting方案的一致性，不仅将带有代价敏感的支持向量机作为基分类器，同时将标准的Boosting方案修改为代价敏感。为了保证连续分类器有更多的训练实例，特别是分布在边界的少数分类实例，其提出一种自适应顺序误分类代价权重确定方法。

神经网络的集成也被应用到处理不平衡数据过程中。Wong等[38]提出2种新的代价敏感方法——代价敏感深度神经网络(CSDNN)和代价敏感深度神经网络集成(CSDE)来解决类不平衡问题。其中CSDE是CSDNN的集成学习版本。为了提高CSDNN的泛化性能，在CSDE中采用随机欠采样和深度神经网络隐含层的分层特征提取。另外，Loezer等[39]提出代价敏感的自适应随机森林(cost-sensitive adaptive random forest, CSARF)算法，并与自适应随机森林(ARF)和带重采样的随机森林(ARFRE)进行比较，结果表明CSARF在平均召回率和平均F1值上均优于ARF。

1.3 多标签数据流

在形式上，多标签流分类(multi-label classification, MLC)[40]问题就是在高速数据流中对每个实例(带有子标签Y⊆L，L是标签集)训练一个模型。虽然在传统的数据挖掘场景中已经对多标签分类进行了研究，但多标签数据流分类是一个比较新的概念，还没有得到充分解决。本节将从二元相关的集成和算法自适应的集成分类展开探讨。

1.3.1 基于二元相关的集成

解决多标签分类最直接的方案就是将多标签转换为熟知的单标签分类，其中二元相关(binary relevance, BR)[8]方法是这种问题转换中最常用的技术，它将多标签问题转化为一些不同的二元单标签分类问题。

多标签分类器的层次结构(hierarchy of multilabel classifiers, HOMER)[41]是一种为具有大量标签域设计的方法。它将多标签分类问题转换为更简单的树形层次结构。为了对新实例进行分类，HOMER从根分类器开始，并且仅当父分类器预测其任何标签时才将实例传递给每个子分类器。叶子分类器的预测标签的联合即为给定实例的输出。Zhang等[42]也提出一种用于HMC(hierarchical multi-label classification)的局部层次集成分类框架,即全关联集成学习。其在所有节点的全局预测和局部预测之间建立了一个多变量回归模型，将基本模型扩展为稀疏模型、核模型和二值约束模型。二元相关性为多标签数据的每个不同标签学习单个二元模型。它相对于标签数量具有线性复杂度，但没有考虑标签相关性，可能无法准确预测标签组合并根据与新实例的相关性对标签进行排序。Tsoumakas等[43]使用集成Stacking结构BR的模型，以学习将其输出与每个标签的真实值相关联的模型是缓解此问题的一种方法。其通过使用phi系数显式地测量标签相关程度，并对参与Stacking过程的模型进行修剪。

在分类器链方法中，每个二元分类器以有序链的方式排列和连接。Read等[8]提出分类器链集成分类模型(ensembles of classifier chains, ECC)来处理多标签分类。该方法是在二元相关方法的基础上发展而来，与目前使用的更复杂的方法相比降低了计算复杂度，通过将标签相关信息沿着分类器链传递，克服了二元关联方法的缺点，在保持较低计算复杂度的同时获得了较好的预测性能。近年来，文本分类、Web、社交媒体挖掘等应用对多标签分类算法的要求越来越高。Nguyen等[44]提出一种可扩展的基于在线可变推理的多标签数据集成分类方法(MVI)，其使用随机投影创建集成系统。作为一种二阶生成方法，该分类器在学习过程中可以有效地利用数据的底层结构。

1.3.2 基于算法自适应的集成

多标签算法中自适应方法通常是基于考虑相似性或目标函数，对某一子集的特征和学习其部分的联合标签分布。Wang等[45]提出一种无缝融合多模态特征和多标签相关性的超图学习算法。新的特征融合策略将多模态特征集成到一个统一的超图中，构造一种高效的多模态超图，解决了该融合方案计算复杂度高的问题。采用自适应学习算法，结合两超图同时学习标签分数和超边权值，实验表明，与具有代表性的算法相比，该文提出的方法具有优越性。Wang等[46]提出 SWMEC(streaming weighting ML-KNN based ensemble classifier)算法，该算法是基于ML-KNN的多标签数据流分类方法的集成模型。其提出的加权集成模型，利用多标签数据流对模型进行有效更新。现有的多标签分类方法很少采用Stacking集成结构，Xia等[47]提出一种新的多标签加权分类器选择和Stacking集成算法(weighted classifier selection and stacked ensemble, MLWSE)，利用稀疏性进行正则化，促进分类器选择和集成构建，同时利用分类器权值和标签相关性提高分类性能。另一方面，集成方法不仅提供一种标签元特定特征的选择方法，而且可以兼容任何现有的多标签分类算法作为其基分类器。

多数多标签分类方法侧重于对现有的二值和多类学习方法的有效适应或转换，但未能对标签的联合概率建模。为了解决这些问题，Szymański等[48]提出一种新的多标签分类方案LNEMLC(label network embedding for multi-label classification)。该方案嵌入了标签网络，并将其用于扩展任意多标签分类器的学习和推理的输入空间。LNEMLC改进了算法自适应方法，为它们提供额外的输入特征以供区分，增加了关于特征数量的复杂度。另外，多标签受到概念漂移挑战驱使，Sun等[49]提出MLAW(multi-label ensemble with adaptive windowing)算法，为多标签数据流分类设计一种有效的集成范例。该算法基于Jensen-Shannon散度部署一种新颖的变化检测，以识别数据流中不同类型的概念漂移。Wang等[50]提出一种主动k标签集集成范式(activek-labelsets ensemble for multi-label，ACKEL)，借鉴主动学习的思想，提出一个标签选择标准来评估从标签子集转换而来的类的可分离性和平衡水平。ACKEL可以在不相交和重叠2种模式下实现，分别采用基于池和基于流的框架。

1.4 多实例数据流

在流挖掘任务中，多实例学习(multi instance learning, MIL)[51]是一个较少被研究的领域。在传统的监督学习中，只有单一的实例，该实例只会被一个标签识别，如图3(a)。然而在多实例学习中，数据结构更加复杂，每个对象或者目标变量都是被不确定数量特征向量所定义，如图3(b)所示。MIL是一种对一组实例进行分类的方法，每个实例组都表示为一个包。它的主要任务是根据实例的标签和特征来生成预测测试包标签的模型。使用集成学习的方法处理多实例数据流是研究的新兴方向，本节将从神经网络的集成和在线学习的集成处理多实例数据进行介绍。

图3 单实例学习和多实例学习

1.4.1 基于在线的集成

大多数传统MIL算法由于需要进行参数调整，需要花费大量时间进行训练。研究者针对学习时间问题，提出基于极限学习机的多实例学习方法。Sastrawaha 等[52]提出一种基于集成多数投票方法的多实例学习集成极限学习机(E-ELM-MIL)方法来提高泛化性能，结合几个单一的隐含层神经网络，并使用多数投票机制预测最终的标签，性能优于其他先进的MIL算法。近年来，基于神经网络的多实例分类算法BP-MIP和多实例回归算法BP-MIR相继被提出。图像可以获得多个实例，这使得图像分类成为一个MIL问题。Kocyigit等[53]开发一种利用稀疏特征表示和分类器集成技术的多实例主动学习方法，即字典集成多实例主动学习(dictionary ensembles multiple instance active learning, DEMIAL)。在提出的主动学习框架中采用字典学习，对比了基于不确定性和基于熵的实例选择技术，实验结果表明，分类器集成受益于主动学习，DEMIAL算法性能优于基于核的多实例主动学习框架。

集成学习的主要目标是将多个学习模型结合起来，并从这些模型的所有输出中获得决策。基于此动机，Taer等[54]提出一种基于集成的多实例学习方法，将标准算法MIWrapper、SimpleMI与集成学习方法Bagging、AdaBoost相结合，以提高分类能力。实验结果表明，基于集成的方法比传统方法具有更高的分类能力。Tu等[55]提出一种新的基于端到端的图神经网络(GNN)的包嵌入算法，将每个包作为一个图，使用GNN学习包嵌入，以探索包实例之间有用的结构信息，最终的图表示被送入分类器用于标签预测。该算法是第一次尝试将GNN用于MIL。

1.4.2 基于神经网络的集成

在图像的目标检测中，Babenko等[9]提出一种在线Boosting改进方案(online MILBoost，OMB)。该算法认为一旦将一个包标记为阳性包，那么其中的所有实例也是阳性的，因此可以用于训练，可使用与集成算法Boosting类似的训练过程，用新模型更新该集成结构。同样的目标检测任务，Wang等[56]提出半监督的在线加权多实例学习集成方法(semi-weighted multi instance learning，Semi-WMIL)。为了充分利用目标及其周围背景信息，结合半监督学习、多实例学习和贝叶斯定理，其提出一种新的单目标检测跟踪器，在每一帧的参数更新阶段，跟踪器在选择最优基分类器时，使用基于块的标记和未标记训练样本的不一致性函数。多视图学习结合了来自多个异构源的数据，由于不同的多实例视图具有不同的基数和特征空间，因此不能将不同的多实例视图数据融合简单地连接到一组特征中。Cano[57]提出一种结合视点学习器并寻求加权类预测一致性的集成方法，以利用多个视点的互补信息，重要的是集成必须处理来自每个视图的不同特征空间，而包的数据可能在视图中部分表示。

一种称为“检测跟踪”的跟踪技术已经被证明具有较好的跟踪效果和实时速度，该方法以在线的方式训练一个分类器来从背景中分离物体。Babenko等[9]提出一种新的在线MIL目标跟踪算法，该算法使用多实例学习而不是传统的监督学习，跟踪器更具鲁棒性且参数调整较少，具有较好的实时性。集合分类器的一种众所周知的策略是随机化，其中学习算法被随机化，以便从同一数据集中获得不同的分类模型。Bjerring等[58]提出一种随机化集成方法MIRI(multi-instance rule induction)。该方法基于MITI算法进行改进，是一个决策树的单学习器，专门为多实例分类而设计。但是该算法的分裂准则对精度有显著影响，通过修改，将算法变为规则的学习器，最终该随机化方法生成随机森林集成模型。

1.5 算法复杂度分析

验证一个算法性能的好坏，除了通过实验数据分析其运行时间、精度等指标外，研究人员还应该通过理论计算来分析算法的时空效率，时空效率分析可以直观地了解算法性能，从而促使研究者通过各种优化策略(例如剪枝、优化算法等)来提高算法的效率，因此时空效率分析是必要的。本节将对以上经典算法的时空效率进行详细分析来进一步深入了解算法，表2罗列了一些代表性算法的复杂度数据分析。

在概念漂移数据流算法中，算法的主要时间消耗来自处理概念漂移的情况，算法需要进行加权来不断更新分类器。AWE算法[5]使用精度加权集成来挖掘带有概念漂移的数据流，该算法的复杂度为O(n×f(s/n)+Ks)，其中s代表数据块的大小，K是分类器的数目，它的复杂度主要在于训练每个基分类器。比较经典的OAUE[2]算法是结合在线和块训练技术的方法，它的复杂度是O(kpvl+k(d+c))，其中p代表数据的数目，v代表数值的数目。由于算法中K、d、c为常数，因此与没有加权的集成相比，该加权方案并没有增加空间复杂度。EOCD[26]算法的复杂度为O(KCVP)，其中C为类数目，K为分类器数量，采用了复杂度为O(1)的RDDM漂移检测器，为了优化模块的复杂性，其使用了遗传算法。

在不平衡数据流算法中，算法的时间消耗主要来自处理不平衡数据和对不平衡数据进行分类。DES[33]算法的复杂度主要由用于动态选择方法的分类器池中的模型数量，以及预处理技术中单个数据块中的实例数量决定，其中动态选择方法的复杂度是O(n),预处理技术复杂度为O(nlogn)。SRE是基于重采样的集成方法，复杂度为O(N|M|log(|M|+s)+sNlogs+3|M|N)，其中M为块数量，N为数据流实例的数量。SRE复杂度的一部分是为了处理不平衡状态下的概念漂移，另一部分是使用重采样技术来平衡数据流。

多标签数据流目前在图像和目标检测领域应用较多，它的时空效率相对于其他数据流较复杂。这由它本身的复杂性决定，一个目标具有多个标签，这时分类的范围也增大。ACKEL[50]算法的复杂度为O(N2n)，其中N为样本数量，n为特征数量，主要计算代价来自算法中核函数的计算。LNEMLC算法[48]的复杂度是嵌入方法、分类器和回归计算过程的总和，其复杂度不会高于O(ld+2n(m+d)+2mn+ln)，算法的复杂度主要来自KNN分类器采样的数目。经典算法ECC[8]分类器链的复杂度为O(LV×f(1,N))，其中L为额外属性的数目。

近些年集成学习在各种场景下使用，虽然在评估指标(如精度等)上有极大的提高，但是总体来说其时空复杂度还是比较高，这是由于它不断增加的集成大小以及集成结构所致。为了提高效率，研究人员需要从它的剪枝策略进行入手研究。表3列举了集成学习处理复杂数据流算法性能的对比。

表 2 代表性算法复杂度分析

表3 复杂数据流集成分类算法性能比较

2 领域数据流集成分类

数据流分类已经被研究人员拓展到很多领域进行挖掘，提取有用的信息进行该领域的研究。随着现在互联网不断触及各行各业，人们对于分类任务的需求也在不断扩展。在流挖掘任务中，文本数据、图数据以及传感器数据，这些领域是研究人员钻研的数据流分类的高级问题。由于数据的表示、结构以及数据的量级发生了重大变化，分析起来需要更加复杂的算法来进行处理，本章将对这些数据流近些年的研究成果进行分析。

2.1 文本数据流

在自然语言处理(nature language processing, NLP)[59]领域，文本分类一直都是一个热门的研究方向，像Twitter和微博这样受欢迎的社交平台，会涉及到新闻内容、社交、广告等方面进行分析。然而文本流分类还是目前文本分类的一个新兴方向，涉及数据流的及时到达以及一次处理等特点都需要研究人员进行考虑。目前文本数据流分类集成学习方法是应用最广泛的方法之一。

基于概念漂移的文本流挖掘是一个非常具有挑战性的研究课题。Song等[60]提出一种新的集成模型——动态聚类森林(dynamic cluster forest, DCF)，用于存在概念漂移的文本流分类。其提出的集成模型是基于多个聚类树(CTs)构建的。特别地，DCF模型有2种新颖的策略：1)根据数据流的固有特性动态选择判别性CTs的自适应集成策略；2)同时考虑分类器可信度和准确性的双投票策略。由于短文本流的稀疏性、高维性和快速变异性，短文本流分类面临着巨大的挑战。Hu等[61]提出一种基于在线的短文本扩展和概念漂移检测的短文本流分类方法，首先从外部资源中扩展短文本流，以弥补数据的稀疏性，并使用在线BTM(bitterm topic model)算法选择具有代表性的主题，而不是用词向量来表示短文本的特征。其次，作者利用多个数据块建立集成模型，并利用最新的数据块和概念漂移检测结果进行更新。实验表明，在分类和概念漂移检测方面取得了更好的性能。

文本分类通过将完成的任务划分为不同的类别，降低了时空复杂度。文本分类的主要问题是从文本数据中提取大量的特征。Khurana等[62]提出一种基于自然启发算法和集成分类器的文本最优分类方法，采用基于生物地理学的优化算法BBO(biogeography based optimization)和集成分类器Bagging进行特征选择，与单独的分类器相比，使用集成分类器进行分类可以提供更好的文本分类性能，从而提高准确率。Upadhyay等[63]提出一种加权分类器集成算法来解决文本分类问题。该算法在组合分类器时，将每个分类器的预测与不同的权重相关联，而不是使用多数投票作为组合方法，并利用粒子群优化算法对训练数据进行损失函数最小化，得到最优权重。Samami等[64]提出一种基于自然启发算法和集成分类器的最优文本分类方法，与单个分类器相比，使用集成分类器进行特征选择可以为最优文本分类提供更好的性能。

2.2 图数据流

图分类的问题出现在许多经典领域，如化学和生物数据、高光通信网络等。近年来，随着互联网应用的出现，人们对动态图数据流应用的兴趣越来越大，这种网络应用程序是在大量节点的基础上定义的。图数据流分类最具挑战性的情况，即数据仅以图形流的形式存在。因此在图数据流分类中要检测到数据流中的变化来进行实时分类，集成学习也逐渐在图结构领域中受到关注。

标签的动态变化可能表明重要事件或活动模式，Aggarwal等[65]研究图数据流中的差分分类问题，其中预测重要的分类事件表现在节点分类标签的变化。与静态的集成分类问题不同，该方法侧重于动态、实时地检测节点分类的变化，而不是对节点进行实际的分类。在许多实际应用中，图可以在一个非常大的节点集合上定义。底层图的许多域大小使得学习分类问题的概要结构信息变得困难，尤其是在数据流的情况下。Tuncer等[66]开发一种新的基于集成局部图结构LGS(local graph structure)的轻量级和认知特征提取框架，并通过使用该框架，提出一种新的脑电图(Electroencephalogram, EEG)信号识别方法，包括预处理、使用基于集成LGS的方法进行特征提取以及使用基准分类器进行分类。结果表明，其成功地利用LGS算法开发了一种更准确、更认知的脑电信号识别方法。

在图数据流的分类任务中也存在不平衡的问题，Pan等[67]提出一种分类模型来处理带有噪声的不平衡图数据流即图集成，使用集成框架来将图数据流划分成包含许多类分布不平衡的噪声图的块。针对每个独立的数据块提出一种基于集成的Boosting算法，将判别子图模式选择和模型学习结合起来作为统一的图分类框架。化工领域经常存在故障分类，Liu等[68]提出一种基于流形保持稀疏图的集成FDA(fisher discriminant analysis)模型。首先，在保持训练样本基本流形结构的前提下，利用保留流形的稀疏图对一些错误标记的样本进行过滤。其次，为了提高模型对错误样本的鲁棒性，利用基于FDA的Bagging算法构建多个子分类器，并将这些子分类器组合形成鲁棒的分类器。Su等[69]提出一种多标签分类的新方法，依赖于多标签上的随机输出图集合的集成学习。对于集成学习，输出图之间的差异提供了所需的基分类器的多样性，并在集成规模不断增加的情况下提高性能。

2.3 传感器数据流

人们的生产生活中，有大量的数据来自智能设备，这些设备自带的传感器时刻传递不同的信息。传感器数据流分析是当前数据挖掘热门的研究领域之一，目前集成学习是挖掘该领域数据流的主要方法。

传感器数据流挖掘方法最近引起了智能家居研究的广泛关注。Shahi等[70]提出一种新的基于自适应聚类的流传感器数据集成学习事件分类方法，包含一些理想的特性，如基于窗口的自适应传感器事件，使用时间衰减函数检测相关传感器事件，在当前窗口保存过去的传感器信息，以及形成在线的流传感器数据集群。该方法改进了流传感器事件的表示，可以使用在线方式学习和识别活动。无线身体传感器网络(BSNs)是一种可穿戴传感器，具有传感、存储、计算和传输能力。当数据来自多个设备时，需要进行多传感器融合，将潜在的错误传感器数据转化为高质量的融合数据。Muzammal等[71]提出一种数据融合的集成方法，用于在雾计算环境下处理BSNs获得的医疗数据。在分类方面，该方法采用一种新的核随机森林集成，其质量显著优于随机森林。

由于数据的高维特性，分析生产环境中的传感器数据相当具有挑战性。Iftikhar等[72]提出一种基于滑动窗口的集成方法，以流的方式检测异常值。该方法结合聚类算法构造表示不同数据结构的子集合，模型集成技术通过提供一种合适的聚合机制来有效地解决分类应用。Alippi等[73]提出使用模型集成来在线重建传感器网络的缺失数据。重建缺失数据对于任何数据处理都是至关重要的，必须在线进行以避免利用数据决策或控制行动时引入不必要的延迟。集成的设计利用了构成网络的传感器之间的时间和空间依赖性。Rodríguez等[74]介绍一类k均值随机投影特征算法OCKRA(one-classk-means with randomly-projected features algorithm)。它是根据随机特征子集在数据集的多个投影上构建的一类分类器集成，实验数据通过嵌入在可穿戴手环上的一组传感器获取。

3 数据流评估方法

正确评估分类器或者回归模型是机器学习的一个关键问题。图4为数据流完整的分类过程，其中包含评估的环节。采用正确、适合的评估措施也是实验验证的重要过程，但只有通过科学严谨的数据评估才能展现出算法优势。性能评估是分类的最后一个环节，下面将详细讨论在数据流环境中，研究人员经常使用的数据流分类的验证技术，以及复杂数据流各自特有的性能评估方法。

图4 数据流评估过程

3.1 验证技术

在静态和批处理学习的背景下，最常用的评估措施是交叉验证。由于传统的数据量有限，根据交叉验证来提高数据使用率最大的缺点是耗费时间。然而在具有严格计算要求和概念漂移的数据流环境中，它并不直接适用。尽管流学习算法的数量不断增加，但评估学习模型质量的指标和实验设计仍然是一个开放的问题。评估技术决定哪些实例用于训练，哪些实例用于测试学习模型。本节将总结在数据流实验中广泛使用的验证技术。

Holdout：Holdout是一个独立的测试集，使用这种评估方法需要2个数据子集：训练数据集和独立测试集。在进行模型评估的任何时刻，都有一个模型之前没有使用过的测试集合，通过在不断更新的集合上测试学习模型就得到了模型误差的无偏估计。Gama等[75]在超快速森林树系统UFFT(ultra fast forest tree system)使用该验证技术,同时许多研究人员在综述论文[11-12]中对Holdout评估方法进行了详细介绍，从传统的批处理对Hold的应用拓展到数据流场景。

Prequential：该方法是数据流中最常用的评估技术，其思想是先用实例测试模型，然后再训练模型。每当一个实例经过时，当前的模型就会做出预测，同时会得出模型的损失。为了使误差估计对这种情况更有鲁棒性，必须实现适当的遗忘机制，即结合滑动窗口或衰减因子。Brzezinski等[2]在进行OAUE算法的实验设置时，其Prequential评估方法采用滑动窗口和衰减因子作为遗忘条件，窗口大小d=1 000，衰减因子α=0.01，通过调整这2个变量来验证算法。Bertini Junior等[21]的IBS算法使用了同样的窗口和衰减因子结合的评估方法进行实验。

Cross-validated prequential：当前社会面临的数据流具有来源多样、实时性强、数据量大等特性。Bifet等[76]提出了新的对大数据流评估的分布式K折验证方法。在使用真实数据对分类器进行训练时，优先评估方法相较于交叉验证只能运行一次实验，标准的交叉验证独立地处理数据流的每个折叠，因此可能会错过数据流中发生的概念漂移。为了克服这个挑战，该文提出3种策略：1)交叉验证(cross-validation)；2)分割验证(split-validation)；3)采样验证(bootstrap validation)。理论证明，使用K折方法的误差比优先方法低。在Gomes等[77]提出的自适应随机森林(ARF)算法实验验证中也用到了K折验证方法。

Latency Verification：流式挖掘的很大一部分研究都是在做出预测后，立即对真实标签的可用性进行分类。但是在许多实际情况下，给数据贴标签的延迟不可忽略，这就提出了在这种情况下如何评估分类器的问题。Gomes等[77]在ARF算法的评估中进行了及时设置和延迟设置来模拟实验，提出一种评估分类性能的方法，其假设存在标签不易获得的问题，标识为“延迟标签设置”，并且定义非常简单：根据其正确预测实例的能力来评估，只能在固定的时间单位后使用。Grzenda等[78]提出一种新的对数据流标签延迟的评估方法，即连续重新评估，它应用于参考数据流，并基于新到达实例细化预测的能力来区分流挖掘技术。

3.2 评估指标

随着数据流挖掘不断受到重视，各种复杂数据流的算法也被相继提出。然而一个好的处理数据流分类算法，需要相应的评估指标去验证。本节对广泛研究的复杂数据流的评估指标进行讨论，同时对比总结各种常见数据流算法的评估指标。表4列举了数据流算法实验中各自适配的评估指标。

表4 复杂数据流算法的评估指标

3.2.1 传统分类评估指标

在传统稳态数据流的机器学习分类中，算法的评估指标多集中在准确率(accuracy, Acc)、错误率(error rate)、内存(memory, M)和运行时间(running time, RT)。无论是回归还是分类任务，这4个指标是最优先考虑的。然而，为了全方位评估算法的性能，更加复杂的评估指标，即精准率(precision, P)和召回率(recall, R)被提出,它们能更好地评估传统的分类或者回归任务。Precision用于衡量分类器的查准率，表示辨识为正的正样本占所有辩识为正的样本比重，而Recall用于衡量分类器的查全率，表示辨识为正的正样本占所有正样本的比重。

3.2.2 复杂数据流分类评估指标

在数据流分类场景中会面临各种复杂的情况，如前后分类的概念不一样、标签数量不相同，等等。这些复杂情况的评估需要研究者分门别类研究，下面将总结在非静态分类中，研究者在文献中所使用到的分类评估指标，同时在非静态环境中，传统的分类评估指标依然可以作为通用的评估指标。Bifet等[79]提出在非静态环境中对时间评估的新指标RAM-Hours，它是一种基于云计算服务租赁成本的一维度量。

概念漂移数据流：在含有概念漂移的数据流中，有时需要主动检测漂移是否发生，再根据设计的算法进行处理，以便让分类器更好地进行学习而不用一直降低精度。Abdualrhman等[23]在DCDD算法中使用到漂移检测率(drift detection rate，DDR)、漂移检测错误率(drift detection error rate, DDER)。DDR=正确检测到飘移的数量/检测漂移的总数量；DDER=错误检测漂移的数量/检测漂移的总数量。

不平衡数据流：在不平衡数据流中，传统的指标已经不适用于不平衡的分类场景。分类器总倾向多数类别，因此针对不平衡分类性能评估，相关学者提出F-Measure(F)、G-Mean(G)。F-Measure与召回率(recall)和精确率(precision)相关，它可以正确评价分类器对于多数类和少数类样本的分类性能。G-mean是Kubat等[80]提出的几何均值，它同时考虑了少数类和多数类的精度，常用于评估不平衡数据的分类。Sensitivity是对模型正确预测正例样本的度量，它有时被称为真阳性率(TPR)。Specificity是模型正确预测负类样本的度量，它有时被称为真负率(TNR)。Kappa统计在不平衡数据流中是经常使用的统计方法，其中标准的KappaK(K)也是常用的评估指标，而Bifet等[76]提出广义的KappaM，它比标准的KappaK更适合不平衡数据流。另外，受试者工作特征(receiver operating characteristic, ROC)曲线和曲线下面积(area under ROC curve，AUC)也常用于评估分类器性能。为了表述以上指标，以二分类为主，采用混淆矩阵(见表5)来表示常用的不平衡数据评估的公式(见表6)。

表5 混淆矩阵

表6 评估指标的公式

多标签数据流：在流数据挖掘任务中，多标签数据流相关算法始终是研究较少的一个方向。由于它本身的复杂性对于实验设计有着不同的要求，但是仍然有它特有的分类性能评估方法，许多文献提出相应的评估指标，如汉明损失(hamming loss, HL)、子集精度(subset-accuracy)、排序损失(ranking loss, RL)等[81]。Hamming loss考虑了预测错误和丢失错误，评估的是一个实例标签对被错误分类的频率。Subset-accuracy是一个非常严格的精度度量标准，如果分类器预测的所有标签都是正确的，就认为分类是正确的。

除了以上常用的评估指标外，也有文献提出更复杂的方法来评估算法特性。Shaker等[82]提出恢复分析(recovery analysis)，它提供一个概念学习器快速发现概念漂移的能力，并采取适当的措施来保持模型的质量和泛化性能。不仅考虑模型在新的决策空间中减少误差的效果，而且还考虑所需的时间。

4 展望

虽然现在很多类型的数据流都有各自的解决方案，但是还有很多类型的数据流无论是在算法层面，还是评估方面都需要去探究。例如挖掘延迟的标签流、多种类型并存的数据流、不确定数据流以及数据流的评估方法等，下面将对这些问题进行仔细分析。

4.1 不确定数据流集成分类的挑战

很少有学者进行不确定数据流的挖掘研究，目前可用的数据流分类算法都致力于精确数据的挖掘，但不确定的数据在现实应用中却很常见。如在传感器网络采集和传输过程中，湿度、温度等天气信息含有大量的不确定性。Yu等[83]提出一种的混合增量回归神经网络，能够从大量不确定数据中学习准确的回归模型。近几年对不确定数据的其他研究较多，但对于它的分类研究，尤其是集成分类这个方向的研究仍然稀缺。

4.2 多种数据流并存集成分类的挑战

现在大多数研究的流集成处理的是单个流，然而在一些应用中，例如历史事件分析中涉及数据的审查可能会存在多个流[84]。在这样的多个流中，相同的数据事件可能出现在每个流中的不同时刻，并且可能具有不同的描述。这带来了几个有趣且新的挑战，例如，如何汇总不同流中可用的同一事件的信息，如何预测事件在其中一个流中出现的时刻，等等。在大数据分析中整合不同数据存储库的背景下，这些方面应该特别重要。集成学习在多个数据流中的应用将是一个新的研究和挑战。

4.3 延迟数据流集成分类的挑战

目前大多数框架都假定对目标值的访问是实时的，或者没有太大延迟的，然而现实生活中很多事件是延迟预测的。当不能快速标记所有的实例时，仍然有可能以合理的代价为有限数量的实例获得真正的标签。Žliobaitē等[85]提出数据流中主动学习的理论框架，给出主动学习策略的3个条件：在无限长的时间内平衡标签预算;感知实例空间中的任何位置变化；保持传入数据的分布以检测变化。未来研究可以将主动学习与集成框架相结合来处理延迟的样本标签。

4.4 数据流分类评估方法的挑战

目前各种复杂数据流的实验测量都有各自适配的评估指标，但是也存在相应的问题。在实际算法应用中，研究人员需要根据需求来选择合适的度量指标，有很多方面需要完善：第一，如何综合各类性能度量指标，给出一个更加准确、全面的算法性能评价结果，将是一个非常值得研究的问题；第二，在延迟到来的数据流中应该有延迟率的评估，这样可以采取适当方法提高分类性能；第三，不仅需要提供分类学习算法的AUC度量，还需要提供它的方差或置信区间，以给出更加准确的算法性能度量结果。

5 结语

本文对现有的复杂数据流集成分类的算法进行了综述。首先，从研究背景的概述、复杂数据流集成分类算法、领域数据流、数据流的评估方法以及研究展望进行了详细分析，其中对复杂数据流集成算法和相关评估方法进行了详细讨论，包括基分类器、集成技术和集成策略等。然后，从数据集、集成方式、优缺点、复杂度方面对所提到的算法进行对比，同时对现有数据流的应用领域进行总结。最后，对复杂数据流集成分类所面临的挑战提出未来的研究方向，以便这些问题可以得到解决和研究。