概念漂移复杂数据流分类方法综述.docx

    概念漂移复杂数据流分类方法综述    穆栋梁，韩 萌，李 昂，刘淑娟，高智慧（北方民族大学 计算机科学与工程学院，银川 750021）0 引言在信息时代，数据不断高速产生且随时间的推移不断变化、增长，量是无限的，含有这些特征的数据被称为数据流，如网络数据、金融数据、传感数据和电网数据等研究发现，在真实的数据流环境中，还存在着多种复杂数据流类型，如不平衡、多标签、概念演化和含噪声的数据流随着时间的推移，流数据的数据分布发生了不可预见的变化，这些变化被认为是概念漂移［1］概念漂移指目标类的底层分布的变化，具体地，概念漂移就是在一组有序实例到达后，之前的目标概念发生了改变概念漂移使前后数据的分布发生变化，影响了数据流的稳定性，使得之前的分类模型不再适用于漂移后的数据，导致传统的机器学习模型在发生了概念漂移时分类性能显著下降含有漂移特征的数据流，称为可变数据流或概念漂移数据流［1］当概念漂移问题出现在复杂类型数据流中，这一问题就会随着底层数据的演变更加难以处理例如：顾客的网上购物偏好，由于内部或外部原因，不常购买物品转变成了常购买物品；某地天气预报由于特殊原因出现了极端天气的情况；网络攻击检测中，首次出现新类型的攻击方式等。

目前多种数据流分类方法大多都仅处理复杂类型数据流的分类问题，没有考虑复杂数据流类型和概念漂移联合条件下的数据流分类问题Wu 等［2］提出基于不平衡数据集重采样的集成学习模型Tao 等［3］提出基于自适应代价权重的支持向量机代价敏感集成方法用于不平衡数据流分类Nguyen 等［4］介绍了一种可扩展的基于可变推理的多标签数据分类集成方法，其中使用随机投影创建集成系统Xia 等［5］利用标签相关性和集成成员的权值学习过程解决分类器选择的问题，并处理成对标签相关性与多标签分类性能之间的关系以上方法是高效的数据流分类方法，然而这些方法的分类器在概念漂移复杂数据流中受到概念漂移的干扰，从而出现类不平衡、标签转换、新类出现以及噪声干扰的问题，使得性能严重下降，因此这些方法并不适应于概念漂移复杂数据流分类在现有的数据流分类综述中，杜诗语等［6］对突变、渐变、重复和增量四种类型的漂移数据流的分类方法进行综述，主要从集成学习的策略角度进行了分析；Hu 等［7］仅从概念漂移的类型方面进行了综述，对漂移检测方法进行了分类，没有将漂移处理方法与集成方法联合进行阐述；Zhang 等［8］对不平衡数据流、非标准数据流等复杂数据流集成分类进行了综述，但未对含概念漂移的复杂数据流分类进行介绍。

以上研究没有专门从概念漂移复杂数据流分类的角度展开阐述本文根据不同的数据流特征，在包含概念漂移的情况下，将其划分为4 类最常见的类型：不平衡概念漂移数据流、概念演化概念漂移数据流、多标签概念漂移数据流和含噪声概念漂移数据流，并对相应的分类方法进行了分类本文框架如图1 所示图1 本文框架Fig.1 Framework of this paper本文的主要工作有：1）对不平衡概念漂移、概念演化概念漂移、多标签概念漂移和含噪声概念漂移这4 个方面数据流分类方法进行介绍，并从学习方式的角度对分类方法进行了分析总结2）从基于块和基于学习方式的角度对不平衡概念漂移数据流分类算法进行分析；从基于聚类和基于模型学习方式的角度对概念演化概念漂移数据流分类算法进行分析；从基于问题转换和算法适应的角度对多标签漂移数据流分类算法进行分析，对使用同一数据集的算法，在实验结果方面进行了详细的分析对比3）对目前存在于概念漂移复杂数据流中所面临的挑战，如在复杂数据流类型中的概念漂移类型检测及方法、多类不平衡概念漂移数据流的分类问题和在特征演化数据流中的新颖类检测问题，进行了总结并提出下一步研究方向1 不平衡概念漂移数据流分类在数据流环境下，数据流样本中存在类失衡情况，出现了多数类和少数类的区别，在此过程中同时受到概念漂移的影响，多数类和少数类之间发生转变，从而大幅降低了分类器的分类效果，需要动态化的学习框架以适应不稳定类概念的演化（概念漂移）是不平衡概念漂移数据流中面临的一个重要难题。

基于块和基于的学习方式是数据流分类中有效的方法，在概念漂移和类不平衡同时存在的条件下，将现有处理不平衡概念漂移数据流方法从学习方式的角度进行划分1.1 基于块的学习方式基于块的学习方式，实例以数据块的形式连续出现，数据块的大小通常相等，基于数据块完成对分类器的构造、评估和更新，基于块的方法是数据流分类常用的训练方式UCB（UnCorrelated Bagging）［9］是解决概念漂移和类失衡最早的算法之一，它基于一个Bagging 框架，通过重采样平衡数据集，基于平衡的数据集训练分类器，并根据基分类器的鉴别能力对其进行加权，被动克服概念漂移Chen 等［10］提出了一种选择性递归算法SERA（SElectively Recursive Approach），通过引入马氏距离衡量少数类概念漂移的严重程度，增加少数类数据的采样权重来解决少数类漂移的问题，对发生概念漂移的少数类给予更多的关注，及时修正分类器之后，Chen 等［11］又提出了一个递归集成算法REA（REcursive Approach），以动态加权的方式结合所有随时间建立的假设，对测试数据集进行预测，在时间上解决概念漂移基于旧实例和新的少数类是同一分布概率的实例选择策 略，Hoens 等［12］提出了HUWRS.IP（Heuristic Updatable Weighted Random Subspaces IP），从类不平衡中获得鲁棒性，使用海林格距离（式（1））作为概念漂移检测的加权测度，漂移检测的海林格权重计算为两个特征分布之间的少数类和多数类海林格距离的平均值（式（2））。

其中：P1和P2是概率测度；p（P1，P2）是P1和P2之间的距离系数；D1和D2是独立的概率分布集；f表示特征；n表示特征数；dH表示海林格距离为从批量可用的新数据中学习，且不必访问以前批量中的数据，Ditzler 等［13-14］基于Learn++学习框架提出了集成的增量学习法Learn++.CDS（incremental Learning for Concept Drift from Streaming imbalance data）和Learn++.NIE（incremental Learning for Nonstationary and Imbalanced Environments）Learn++.CDS 使用合成少数类采样技术（Synthetic Minority class Over-sampling TEchnique，SMOTE）减小数据的不平衡比例，然后使用Learn++.NSE（incremental Learning for NonStationary Environments）在重新平衡的数据集中学习概念漂移Learn++.NIE 使用加权召回或几何平均单个类的表现，对概念漂移进行有效的跟踪识别，提高少数类上的分类性能，避免多数类分类性能下降。

在DWSE（Dynamic Weighted Selective Ensemble）算法［15］中，对之前数据块中的少数样本进行重采样，并吸收之前数据块中的信息构建分类器，减少概念漂移的影响DWSE 算法中定义了基分类器动态衰减因子计算方法，根据衰减情况选择子分类器进行消除，使算法更好地处理概念漂移问题基于学习机的方法为解决不平衡和概念漂移的联合问题提供了很好的思路，MOS-ELM（Meta-cognitive Online Sequential Extreme Learning Machine）［16］利用一种基于变化检测器的自适应窗口方法和基于OS-ELM（Online Sequential Extreme Learning Machine）的输出更新方程同时针对类不平衡和概念漂移，通过减小数据块大小提高处理概念漂移的能力ESOS-ELM（Ensemble of Subset Online Sequential Extreme Learning Machine）［17］使用重采样方法进行类的平衡根据基分类器在与当前训练数据验证数据集上的性能均值更新基分类器的投票权重解决概念漂移问题。

利用独立仓库模块处理重复出现的概念漂移，维护一个加权极端学习机器池以保留旧的信息，采用基于阈值技术和假设检验主动检测突然和逐渐的概念漂移基于块的集成会消耗大量的内存，DUE（Dynamic Updated Ensemble）［18］采用基于块的增量动态更新集成方法解决内存消耗问题DUE 使用了一个基于Bagging 的框架获得相对平衡的数据块，通过分量加权机制和分量更新机制对概念漂移作出快速反应，使用最新的实例周期性地更新先前的分类器以应对多种概念漂移ECISD（Ensemble Classifier for mining Imbalanced Streaming Data）［19］利用过采样技术平衡各类样本，并周期更新分类器权重以应对概念漂移在分类器的淘汰过程中考虑了各个分类器对集成分类的影响，从而达到提高分类效果的目的CIDD-ADODNN（Class Imbalance with concept Drift Detection-ADadelta Optimizer-based Deep Neural Network）［20］采用自适应合成技术处理类不平衡数据，此外，应用自适应滑动窗口技术对应用流数据中的概念漂移进行识别，通过应用堆叠自动编码器进行概念漂移分类以增强估计措施。

最后，利用ADODNN 算法进行分类图2 展示了ADODNN 算法框架图2 ADODNN算法框架Fig.2 ADODNN algorithm framework1.2 基于的学习方式学习方法可以应用于数据以块形式到达的问题，学习中，实例不断从数据流中获得并且只能被处理一次，不需要再次存储和再处理在数据连续到达的情况下，算法比典型的批处理算法运行更快、精度更高，因此技术被广泛地应用在数据流分类中基于学习方式的代表 是Wang 等［21］提出的OOB（Oversampling-based Online Bagging）和UOB（Under-sampling-based Online Bagging）Somasundaram 等［22］提出了事务窗口打包（Transaction Window Bagging，TWB）模型，即并行增量学习集成TWB 使用了一种增量学习模型，使用事务窗口在流事务数据上创建包，处理逐渐的概念漂移；采用贝叶斯基础学习器处理噪声和边界数据HIDC（Handling Imbalanced Data with Concept drift）［23］利用差异因子估计多数类和少数类的分类精度之间的差异，对过采样和欠采样过程进行动态决策，解决了类分布不平衡的问题。

通过对候选分类器的效率进行评估，从而替换集合分类器中最差的分类器成员，以此解决概念漂移问题梁斌等［24］结合重采样和自适应滑动窗口技术，提出了一种基于G 均值加权的不平衡数据流分类方法OGUEIL（Online G-mean Update Ensemble for Imbalance Learning），根据当前数据分布及时调整每个成员分类器的权重，解决不平衡数据流中的概念漂移问题Sun 等［25］提出的TSCS（Two-Stage Cost-Sensitive）是一种两阶段代价敏感的数据流分类框架在特征选择阶段，利用成本敏感主成分分析进行特征选择，提高算法的泛化能力，从而适应各种概念漂移；在分类阶段，建立代价敏感加权模型，将代价信息引入学习框架TSCS 框架如图3所示图3 TSCS框。