在开放环境下, 数据流具有数据高速生成、数据量无限和概念漂移等特性. 在数据流分类任务中, 利用人工标注产生大量训练数据的方式昂贵且不切实际. 包含少量有标记样本和大量无标记样本且还带概念漂移的数据流给机器学习带来了极大挑战. 然而, 现有研究主要关注有监督的数据流分类, 针对带概念漂移的数据流的半监督分类的研究尚未引起足够的重视. 因此, 在全面收集数据流半监督分类研究工作的基础上, 对现有带概念漂移的数据流的半监督分类算法进行了多角度划分; 并以算法采用的分类器类型为线索, 对已有的多个算法进行了介绍与总结, 包括现有数据流半监督分类采用的概念漂移检测方法; 在一些被广泛使用的真实数据集和人工数据集上, 对部分代表性数据流半监督分类算法进行了多方面的比较与分析; 最后, 提出了当前概念漂移数据流半监督分类中一些值得进一步深入探讨的问题. 实验结果表明: 数据流半监督分类算法的分类准确率与众多因素有关, 但与数据分布的变化关系最大. 本综述将有助于感兴趣的研究者快速进入数据流半监督分类问题领域.
In the open environment, data streams have the characteristics of high-speed data generation, unlimited data volume, and concept drift. In the task of data stream classification, it is expensive and impractical to generate a large amount of training data by manual annotation. A data stream with a small number of samples labeled and a large number of samples unlabeled and with concept drifts presents a great challenge to machine learning. However, the existing research mainly focuses on supervised classification of data streams, while semi-supervised classification of data streams with concept drifts has not yet attracted attention enough. Therefore, based on the comprehensive collection of the work of semi-supervised classification of data streams, this study sorts the existing semi-supervised data stream classification algorithms into several types from several aspects, describes and summarizes many existing algorithms based on the types of classifiers used in the algorithms and the concept drift detection methods utilized. On some widely employed real and synthetic datasets, several representative semi-supervised classification algorithms for data streams are chosen to be compared and analyzed in many aspects. Finally, this study proposes some issues that are worthy to be further discussed in future for semi-supervised classification of data streams with concept drifts. The experimental results show that the classification accuracy of the algorithms for semi-supervised data stream classification is related to many factors, but it has the greatest relationship with the changes of data distribution. This review will help the interested researchers quickly enter into the field of semi-supervised classification of data streams.
传统的机器学习算法得在静态封闭环境[
数据流分类[
在实际数据流分类场景中, 受标注成本、数据产生速度和数据量巨大等因素的影响, 可用于学习的标记样通常比较少, 从而大部分样本无标记. 比如在网络入侵检测系统中, 网络连接数据必须被有效地处理以维护安全的网络环境. 由于网络连接的数量巨大、速度非常快, 对所有连接数据进行人工标注昂贵且不现实, 系统必须在半监督条件下准确且高效地完成检测和模型更新. 仅利用少量标记样本学习得到的模型的泛化能力会比较差, 而且会造成大量无标记样本的浪费. 近年来, 数据流半监督分类[
在数据流半监督分类情形下, 通常假定有少量样本在被分类后其标记可以获得, 而大量样本未被标记. 因此, 与监督数据流分类相比, 数据流的半监督分类存在一些额外挑战: 首先, 用少量标记样本训练的分类模型的泛化能力会比较差, 如何利用大量无标记样本的内在结构和分布来辅助训练? 其次, 基于准确率的概念漂移检测方法不能很好地适应半监督条件的概念漂移检测, 如何同时检查
自Schlimmer等人[
尽管已经存在许多关于数据流半监督分类的理论和应用研究工作, 但是在上述综述中, 数据流半监督分类算法仅在部分综述中被提及[
据作者所知, 本文应该是带概念漂移的数据流半监督分类的第一篇综述. 本文的贡献主要包括4个方面.
(1) 对数据流半监督分类算法进行了多角度划分, 便于根据研究与应用的要求选择算法;
(2) 以分类模型为主线, 对现有的多个针对带概念漂移的数据流的半监督分类算法进行了总结与介绍, 有利于感兴趣者快速了解各算法特点;
(3) 对数据流半监督分类问题的概念漂移检测方法进行了归纳与总结;
(4) 基于真实数据集和人工数据集, 对部分有代表性的数据流半监督分类算法进行了多方面的比较与分析.
本文第1节介绍概念漂移的定义和类型. 第2节介绍数据流半监督分类的研究概况, 对数据流半监督分类算法进行了多角度划分. 第3节以分类模型为线索, 介绍数据流半监督分类的研究进展. 第4节介绍现有数据流半监督分类算法涉及的概念漂移检测方法. 第5节对部分数据流半监督分类算法进行了多方面的比较与分析. 第6节提出当前数据流半监督分类中一些值得深入探讨的问题. 最后是总结.
在很多数据流分类的应用场景中, 只能获得少量有标记的样本. 根据被标记样本在整个数据流中的位置, 可以划分为3种情形.
(1) 部分样本被随机标记. 这种情形更加符合实际应用场景;
(2) 有标记样本仅在模型初始化时给出, 后续样本全部为无标记样本. 这种情形被称为Initially Labeled Streaming Environment (ILSE)[
(3) 在分块处理数据流中, 部分数据块上样本的都有标记[
根据数据源产生的数据是否服从独立同分布假设, 可以将数据流分为两类: 静态数据流[
根据贝叶斯决策理论, 一个分类器可以被描述为: 给定样本
其中,
(1) 类的先验概率
(2) 类的条件概率
(3) 后验概率
根据概念漂移的定义, 可以将概念漂移分为两种类型: 真实漂移和虚漂移[
根据数据分布随时间变化的形式, 可以将概念漂移分为突变、渐变、增量和重现这4种形式[
概念漂移的4种类型
类型 Ⅰ(突变概念漂移(abrupt)): 一个概念在某一时刻突然切换到另一个概念;
类型 Ⅱ(渐变概念漂移(gradual)): 数据在一个过渡阶段内, 通过从两个不同分布中动态采样而产生. 在该阶段内, 随着时间的推移, 从一个分布中采样的概率减少, 从另一个分布中采样的概率增加;
类型 Ⅲ(增量概念漂移(incremental)): 数据分布随时间变化, 这些分布之间存在细微的差异. 只有考虑更长的观察时间时, 才会表现出明显的漂移现象;
类型 Ⅳ(重现概念漂移(reoccurring)): 相同的数据分布在未来一段时间内再次出现.
在数据流分类领域, 除了前面所述的概念漂移, 其实还包括样本特征的动态变化、样本所属类别的数量的动态变化. 样本类别数量的变化在文献中通常被称为概念进化[
半监督情形下的数据流分类降低了数据的标注成本, 适应了数据的高速产生, 更加适合众多实际应用场景的需求. 因此, 该领域相关的研究工作正在逐年增加. 本节根据分类模型对现有数据流半监督分类算法进行了归类, 给出了如
算法的不同划分
分类模型 | 参考文献 | 年份 | 算法名字 | 模型更新 | 模型数量 | 主动检测 | ||
在线 | 分块 | 单模型 | 多模型 | |||||
聚类 | 55 | 2008 | SmSCluster | − | √ | − | √ | − |
57 | 2009 | LabelStream | − | √ | − | √ | − | |
56 | 2012 | ReaSC | − | √ | − | √ | − | |
16 | 2012 | SEClass | − | √ | − | √ | − | |
15 | 2016 | SPASC | − | √ | − | √ | √ | |
58 | 2018 | SSCLCR | − | √ | − | √ | √ | |
59 | 2018 | DISSFCM | − | √ | √ | − | − | |
60 | 2020 | SCBELS | − | √ | − | √ | √ | |
61 | 2020 | ORSSL-MC | √ | − | √ | − | − | |
62 | 2021 | ESCR | − | √ | − | √ | √ | |
决策树 | 63 | 2010 | REDLLA | √ | − | √ | − | √ |
65 | 2011 | CSL-Stream | √ | − | √ | − | − | |
64 | 2012 | SUN | √ | − | √ | − | √ | |
67 | 2017 | TriTDS | − | √ | − | √ | − | |
17 | 2018 | SCo-Forest | − | √ | − | √ | √ | |
68 | 2020 | CAPLRD | − | √ | − | √ | √ | |
69 | 2020 | SSCADP | − | − | − | − | − | |
图 | 70 | 2012 | KAOGINCSSL | − | √ | √ | − | − |
SVM | 72 | 2009 | RK-TS3VM | − | √ | √ | − | − |
71 | 2009 | SSL-E | − | √ | √ | − | − | |
22 | 2017 | 4SFD | − | √ | √ | − | √ | |
神经网络 | 75 | 2019 | ISLSD | − | √ | √ | − | − |
76 | 2019 | SSOE-FP-ELM | − | √ | √ | − | − | |
其他 | 47 | 2010 | ECU | − | √ | − | √ | − |
52 | 2016 | IS3RS | − | √ | √ | − | − | |
44 | 2012 | COMPOSE | − | √ | √ | − | − | |
45 | 2013 | |||||||
53 | 2015 | SluiceBox | √ | − | − | √ | − | |
46 | 2019 | AMANDA | − | √ | √ | − | − | |
54 | 2021 | SSE-PBS | − | √ | − | √ | − |
根据算法使用的分类模型, 可以将现有算法划分为基于聚类、决策树、图、支持向量机(support vector machine, SVM)、神经网络和其他等6种. 基于聚类的算法主要通过半监督聚类算法得到聚簇集合, 这些簇保存了用于分类的统计信息(比如簇的质心、簇中类的分布等). 基于图的算法维持着一个图结构, 监督信息存储在部分顶点上用于分类, 顶点之间通过具有权值的边连接, 通过图中新旧顶点的替换和权值的更新, 使模型适应动态的数据流环境. 基于决策树的算法通常利用半监督学习算法标记更多样本进而完成模型更新, 比如: REDLLA和SUN算法分别在决策树的叶子节点中使用
算法使用的模型更新方式包括两种: 在线和分块. 在线更新是分类模型逐个学习新样本, 当条件满足时对分类模型进行更新; 分块更新是指分类模型逐块学习新样本, 利用新样本块对分类模型进行更新. 相对于在线模型更新方式, 分块更新模型具有可用于更新模型和检测概念漂移的样本更多、学习得到的模型更强、更加适用于集成模型等优势. 因此, 分块更新模型占据了主要部分.
算法分类模型中使用的分类器的数量包括单模型和多模型. 在单模型的算法中, 单个分类器在数据流的整个处理阶段被维持, 通过分类器的替换或更新等方式来使模型适应新的数据流环境. 集成模型通常维持着一个固定大小、由多个单分类器组成的分类器池, 池中每个基分类器可以是相同模型(比如基于簇的分类模型)或不同模型(比如基于决策树和聚簇的分类模型). 通过分类器池中单个分类器的替换、更新或各个分类的权值调整等方式来使模型适应新的数据流环境.
算法对概念漂移的适应分两种情形: 一种是不检测, 分类模型被动持续更新, 被动适应新概念; 第2种是主动检测概念漂移, 主动适应更新模型适应新概念. 不检测指没有显式的概念漂移检测过程, 该类算法主要通过单模型的在线更新/分块更新、多模型中基分类器的替换和更新、基分类器的权值调整等方式来使模型适应新的概念. 在主动检测方法中, 算法周期性地检测数据流中是否出现新概念或重现概念. 该方法作为一个独立部分, 将在第4节被详细的介绍. 相比于不检测, 主动检测需要额外的参数, 而参数的确定比较困难, 往往取决于不同的应用环境, 而且需要特殊的背景知识. 因此, 不检测的方法在参数数量上具有明显优势, 但是不能很好地处理包含重现概念漂移的数据.
本节以算法的分类模型为线索, 对现有的数据流半监督分类的研究进展进行了综述. 为体现数据流半监督分类研究综述的完整性, 在该领域中, 与主动学习相关的一些研究工作也将被简单介绍.
该类算法的分类模型包括单模型和集成模型. 该类算法利用各种聚类算法获得聚簇集合(有时这些聚簇会被进一步划分为微簇), 每个聚簇中保存了簇中样本的统计信息(比如质心、类分布或半径), 这些信息可被用于分类. 聚类能较好地体现数据分布的局部和全局特征, 也很容易被更新, 很适合处理无标记, 因此聚类常被用于数据流的半监督分类, 其中, 半监督聚类比监督聚类更常见. 但是, 聚类并不能保证所有的簇包含有标记样本. 对于不包含标记样本的簇, 算法需要额外的一些操作(比如标记传播)为其指派一个合适的标记, 这会影响算法的效率. 该类算法需要预先指定聚簇数量, 且在整个数据流处理过程中保持聚簇数量不变. 考虑到有概念漂移的数据流环境中新旧概念簇的出现或消失, 簇的数量对算法性能会有很大影响.
Masud等人分别于2008年和2012年提出了基于半监督聚类的数据流集成分类算法SmSCluster[
SmSCluster算法分别在前
与SmSCluster算法不同, LabelStream和ReaSC算法对聚类得到的每个簇进一步划分得到更纯的微簇, 并利用标记传播算法给无标记的微簇分配一个伪标记. 每个微簇存储了该微簇中样本的统计信息. 这些微簇的集合构成一个基于簇的分类器而存储在大小为
徐文华等人[
Hosseini等人[
Qin等人[
Casalino等人[
Wen等人[
Din等人[
Zheng等人[
● 若是“例外”, 则将其存入缓存
● 若不是“例外”且
● 若不是“例外”且
总结起来: 从算法流程来看, SmSCluster[
该类算法以决策树作为分类模型或者是集成模型的基分类器, 主要通过对树结构的调整或者是集成模型的更新来显式或者隐式地适应带概念漂移的数据流环境. 因为数据流中只有部分样本有标记, 不少算法结合半监督学习策略来扩展有标记样本的数量, 以提高分类模型的泛化能力或使得概念漂移的检测更准确.
李培培等人[
Nguye等人[
胡学钢等人[
Wang等人[
Wen等人[
Liu等人[
总结起来: REDLLA[
基于图的算法在整个数据流处理过程中维持着一个图结构. 一个节点表示一个样本, 有边的样本之间很相似. 图的更新主要通过添加/删除顶点和边以及更新边的权值来完成, 以适应数据流的不断变化.
Bertini等人[
用图来表示样本及样本的相似关系, 可以比较好地发现样本分布的局部特征, 也便于更新. 因此, 基于图的方法与基于聚类的方法有着很多类似之处, 可以相互借鉴而产生新的算法. 该类算法也面临两难——当顶点较多时, 图操作比较费时; 但顶点过少时, 图结构又很难准确地体现样本的分布. 从目前来看, 此类算法较少见.
基于SVM的分类模型都是以分块方式来处理数据流. SSL-E[
针对演化数据流分类, Jia等人[
Zhang等人[
Hu等人[
基于神经网络的算法主要通过调整网络参数来更新模型以适应新的概念. 由于神经网络的训练需要大量的样本, 因此, 基于神经网络的方法对于渐变或者增量的概念漂移以及类别增量会有比较好的效果. 据作者所知, 目前还未见到有将神经网络用于突变概念漂移的数据流分类.
Li等人[
Silva等人[
本节介绍基于其他分类模型的算法, 这些分类模型包括
Dyer等人[
Ferreira等人[
Zhang等人[
Parker等人[
Feng等人[
Khezri等人[
● 第1步, 当获得
● 第2步, 利用池中的分类器计算
在基于主动学习的数据流半监督分类算法中, 需要查询标记的样本通过选择性一些低置信度[
Haque等人提出的SAND[
Sriwatanasakdi等人[
Masud等人[
Arabmakki等人[
Zhu等人提出的MV[
在开放环境下, 数据的分布常因环境变化、设备损耗等多种因素的影响而随时间发生变化(概念漂移现象), 有效地检测出这种变化进而及时调整模型, 将使模型更好地适应新的数据流环境. 显式的概念检测使得学习过的历史概念得到保留, 还能使得分类模型更新更有针对性, 从而避免一些无意义的模型更新, 提高了数据的管理效率. 针对带概念漂移的数据流的半监督分类中的概念漂移检测, 学界已经提出了两类方法. 一类办法是利用有标记样本使用监督情形下的检测方法来检测概念漂移, 但这种方法忽略了数量众多的无标记样本. 同时, 在半监督条件下, 由于标注样本不多, 使得使用分类准确率来检测概念漂移这一通常做法也变得不太可行; 第2类办法是将标记样本和无标记样本都利用起来, 因此, 数据流半监督分类时大多都是采用第2类检测方法.
在Wang等人[
在Hu等人[
李培培等人[
王海燕等人[
Hosseini等人[
Kim等人[
Tan等人[
总结起来: 第2类办法中, 有的利用空间距离[
第3节以分类器类型为线索对数据流半监督分类的研究进展进行了详细的归类、分析和总结, 概括了各类算法的特点. 为了对概念漂移数据流半监督分类算法的其他归类(在线和分块、有无概念漂移以及模型数量)的特点有更加全面的认识和理解. 本节给出了具体的实验方案, 依据实验方案生成包含不同概念类型的数据集, 并对多个算法在这些数据集上的实验结果进行全面分析.
由于数据流半监督分类领域涉及到的算法比较多, 本文无法对所有算法进行对比实验. 因此, 本节将在一些被广泛使用的真实和人工数据集上对部分算法: SPASC, ReaSC, SmSCluster, SEClass, SUN和REDLLA进行多方面的实验和分析. 这些算法涵盖了在线和分块处理数据流的算法、主动概念漂移检测(包括重现概念漂移检测)和不进行概念漂移检测的算法、基于单模型和多模型的算法.
不同应用场景下产生的数据流中, 数据的分布随时间变化的方式不同. 为分析算法对各种概念漂移数据流分类场景的适应能力, 本次实验分别使用4个被广泛使用的真实数据集和8个人工数据集. 这些数据集已经在综述文献[
在本次实验中, 为了模拟半监督环境, 假定部分样本被分类结束后, 其真实标记可以被算法获得. 有标记样本的比例对算法的性能具有一定影响, 因此, 本文设置了不同的样本标记比例[5%, 10%, 20%, 30%].
在基于多模型的算法中, 分类器池中基分类器的数量对样本分类所做的贡献因算法不同而存在差异. 分类器池越大, 包含不同概念的基分类器可能越多. 采用集成投票表决进行分类的ReaSC和SmSCluster算法可能会受到非当前概念的分类器的影响而表现出较差的分类性能. 采用加权集成投票表决的SEClass算法利用权值削弱了非当前概念的分类器的影响, 可能呈现较好的性能. 采用最大权值进行分类的SAPSC算法在权值调整正确的情况下可能会完全避免非当前概念的分类器的影响. 因此, 本文对分类器池的不同大小进行了实验, 用于分析其产生的影响.
不同的算法具有不同的参数. SPASC, ReaSC, SmSCluster和SEClass等算法都属于基于聚簇的数据流半监督分类算法, 且都属于多模型算法. 该类算法的主要参数是分类器池的大小和簇的数量. 簇参数的设置因数据集的不同而不同. 在样本的标记比例默认值设置为20%条件下, 为了公平比较, 对于每个数据集, 在[1−100]取值区间内, 以5为步长分别设置簇的参数为[5, 10, …, 95, 100], 在所有簇参数下获得的最高准确率对应的簇参数值作为这4个算法在该数据集上各自的簇参数设置. 为了尽可能使分类器池能够容下每一个概念对应的分类器, 对于Agrawal/Sea/Sine-(abr/gra)数据集, 分类器池的大小默认设置为概念数量的2倍, 算法在其他数据集上的分类器池的大小默认设置为10. SUN和REDLLA算法属于基于决策树的数据流半监督分类算法, 且都属于单模型算法, 该类算法的性能主要受有标记样本的比例的影响. 其他参数(SEClass中的同质性参数
数据集和参数设置
数据集 | 数量 | 维度 | 类别 | 块的大小 | 簇的数量 | 池的大小 | |
真实 | Weather | 18 159 | 8 | 2 | 360 | 95 | 10 |
Electricity | 45 312 | 8 | 2 | 1 000 | 75 | 10 | |
Forest Cover type | 581 012 | 54 | 7 | 1 000 | 95 | 10 | |
Poker Hand | 829 201 | 10 | 10 | 1 000 | 100 | 10 | |
人工 | Sea-abr/gra | 80 000 / 115 000 | 3 | 2 | 1 000 | 50 | 8 |
Sine-abr/gra | 80 000 / 115 000 | 4 | 2 | 1 000 | 100 | 8 | |
Agrawal-abr/gra | 80 000 / 115 000 | 9 | 2 | 1 000 | 45 | 8 | |
Hyperplane | 80 000 | 10 | 2 | 1 000 | 85 | 10 | |
Gaussian | 6 000 | 2 | 4 | 300 | 100 | 10 |
在真实数据集中,
● Nebraska Weather数据集来源于Bellevue, Nebraska的Offutt空军基地, 由于其具有50年(1949−1999)的时间跨度和多样化的天气模式, 使其成为长期降水分类/预测漂移问题, 目标是预测是否会在某一天下雨. 由于时间跨度大, 肯定存在概念漂移;
● Electricity是一个被广泛使用的真实数据集, 是从澳大利亚新南威尔士州电力市场收集而来. 类标记表示这一天相对于过去24小时移动平均值的价格变化(UP或DOWN);
● Forest Cover type数据集包含位于科罗拉多州北部罗斯福国家森林的4个较宽区域内的森林覆盖类型信息, 用于描述7种可能的森林覆盖类型之一, 是数据流分类领域中使用最广泛的数据之一;
● Poker Hand数据集包含829 201个样本, 每个样本(hand)由从52张标准牌组中抽出的5张扑克牌组成, 每张扑克牌由两个属性描述(花色和牌的大小)描述. 该数据集包含10个类别(0−9), 分别对应Nothing in hand, One pair, Two pairs, Three of a kind, Straight, Flush, Full house, Four of a kind, Straight flush和Royal flush.
在人工数据集中,
● Sea数据集包含3个属性, 其中只有前两个属性相关, 这3个属性的值都在0−10之间. 数据集被划分为4个具有不同概念的块, 在每个块中, 分类函数为
● Sine数据集在二维空间中的决策面为
➢ 当
➢ 当
生成的数据流中, 概念变化顺序为:
● Agrawal生成器生成一个包含9个属性的数据流, 6个数值属性和3个分类属性的不同组合产生了10个不同类型的分类函数, 这些函数决定了贷款是否应该获得批准. 10个函数对应于10个概念(
● Hyperplane数据集用于模拟增量概念漂移.
● Gaussian Drift数据集是一个包含4个高斯分布的人工数据集, 这4个高斯分布的均值和方差根据参数方程不断变化[
算法随机标注一些样本的标记来模拟半监督环境, 为了缓解这种随机性对算法的分类结果产生特殊性和不稳定性等影响, 本次实验使用MOA生成的每个人工数据集都包含相同概念顺序的10份数据, 在真实数据集上则随机改变有标记样本的位置10次. 各取10次结果的平均值作为各自的最终分类结果.
为了对算法进行全面地分析和比较, 本节从分块准确率、累计准确率、标记比例和分类器池大小的影响等4个方面对各算法进行实验, 并给出了详细的对比分析.
为了比较各个算法的性能, 基于每个数据集上的10次随机实验, 本文统计了10次随机实验中算法累计准确率的标准差(Std), 以比较各算法的稳定性, 并对各算法的累计准确率(Acc)进行了95%置信水平的成对t检验, 以比较各算法在累计准确率上的高低. 如
累计准确率、标准差和统计监测结果
ReaSC (◆/◇) | SmSCluster (●/○) | SEClass (★/☆) | ||||
注: 粗体表示在对应数据集上6个算法中分类准确率的最大者 | ||||||
Agrawal-abr | 60.11±0.45 | 60.76±0.3 | ◇ | 57.72±0.31 | ◆● | |
Agrawal-gra | 62.02±0.29 | ◆ | 57.28±0.27 | ◆● | ||
Sea-abr | 87.58±0.45 | 87.83±0.34 | ◇ | ◇○ | ||
Sea-gra | 88.13±0.26 | 88.14±0.3 | − | ◇○ | ||
Sine-abr | 58.71±0.28 | 58.88±0.29 | − | ◇○ | ||
Sine-gra | 67.19±0.58 | 67.34±0.28 | − | ◇○ | ||
Hyperplane | 79.13±2.83 | ◆ | 70.22±1.11 | ◆● | ||
Gaussian | 37.95±1.5 | 38.96±1.34 | − | ◇○ | ||
Poker hand | 52.78±0.2 | 52.92±0.21 | − | 58.53±0.16 | ◇○ | |
Weather | 74.07±0.5 | − | 69.27±0.7 | ◆● | ||
Electricity | 66.06±0.41 | 66.3±0.56 | − | 63.84±0.44 | ◆● | |
Forest cover type | 77.01±0.26 | ◇ | 58.58±0.11 | ◆● | ||
Win-tie-loss ( |
32-10-18 | 32-11-17 | 32-9-19 | |||
Win-loss ( |
43-17 | 48-12 | 53-7 | |||
SPASC (■/□) | REDLLA (▲/△) | SUN | ||||
Agrawal-abr | ◇○☆ | 56.71±2.1 | ◆●■ | 56.19±3.61 | ◆●■ | |
Agrawal-gra | 61.94±0.62 | ☆ | 58.73±2.03 | ◆●■ | 59.0±2.26 | ◆●☆■ |
Sea-abr | 79.96±1.83 | ◆●★ | 82.88±0.6 | ◆●★□ | 81.33±0.57 | ◆●★▲ |
Sea-gra | 79.41±1.62 | ◆●★ | 84.01±0.82 | ◆●★□ | 82.38±1.25 | ◆●★□▲ |
Sine-abr | 75.87±0.94 | ◇○★ | 48.98±1.15 | ◆●★■ | 52.97±2.0 | ◆●★■△ |
Sine-gra | 69.62±0.73 | ◇○★ | 50.6±2.6 | ◆●★■ | 55.13±2.06 | ◆●★■△ |
Hyperplane | 62.48±4.6 | ◆●★ | 76.79±4.74 | ◆●★□ | 77.48±4.12 | ◆●☆□ |
Gaussian | 60.37±1.76 | ◇○★ | 44.73±2.1 | ◇○★■ | 38.01±3.44 | ★■▲ |
Poker hand | 54.78±1.29 | ◇○★ | ◇○□ | 60.6±4.47 | ◇○□ | |
Weather | 67.25±1.96 | ◆●★ | 68.94±1.02 | ◆●□ | 68.52±1.34 | ◆● |
Electricity | 57.68±1.24 | ◆●★ | ◇○☆□ | 68.91±3.86 | ◇☆□ | |
Forest cover type | 58.51±1.27 | ◆● | 57.42±1.98 | ◆● | 55.08±4.78 | ◆●★ |
Win-tie-loss ( |
22-13-25 | 12-13-35 | 16-12-32 | |||
Win-loss ( |
17-43 | 11-49 | 8-52 |
从
从
另外, 从Hyperplane数据集的实验结果中可以发现: ReaSC, SmSCluster, REDLLA和SUN算法的分类准确率较高, SEClass和SPASC算法分类准确率较差. 这种现象的原因在于: 在增量概念漂移数据流上, 由于数据分布的变化不显著, SEClass和SPASC算法根据检测到的概念挑选分类器的做法并不奏效; 而对于Gaussian数据集情况相反, SEClass和SPASC算法则表现出较好的分类准确率. 这主要是由于数据块的分布变化比较大, 适合SEClass和SPASC算法挑选分类器.
对于真实数据集, 从
为了分析各算法在各种数据流分类场景下更细致的差异, 本文给出了所有算法的准确率随数据块变化的趋势图. 数据包括3个具有突变概念漂移的数据集、3个具有渐变概念漂移的数据集、2个具有增量概念漂移的数据集以及4个真实数据集. 实验结果如
准确率随数据块的变化趋势图
从包含突变或渐变概念漂移的数据流对应的准确率变化趋势图中可以发现: 除SPASC外, 几乎所有算法都能跟踪数据流中概念的变化, 在数据块上的准确率有明显的下降、恢复和增长过程. 对于SPASC, 主要的原因在于其概念漂移检测方法在部分数据集上还不够准确, 以及当分类器池满时, 强行更新最大相似性对应的分类器. 对于有增量概念漂移的数据, 各个算法的分类准确率都在持续的变化, 没有明显的下降、恢复和增长过程. 对于实际数据, 概念漂移的情况比较复杂, 因此各算法的准确率变化比较频繁, 但也能大致看出, 数据流中概念变化导致了分类准确率的变化.
为了更清楚地分析各算法准确率的变化情况, 本文跟踪了突变概念漂移情形下, 各算法在新概念第1个和第2个数据块上的分类准确率. 实验结果见
新概念的第1个数据块上各算法的准确率
Dataset | Algorithm | ||||||
ReaSC | SmSCluster | SEClass | SPASC | REDLLA | SUN | ||
注: 粗体表示在对应数据块上6个算法中分类准确率的最大者 | |||||||
Agrawal-abr | 11 | 0.424 6 | 0.420 4 | 0.426 4 | 0.435 5 | 0.440 8 | 0.469 |
21 | 0.521 | 0.510 8 | 0.536 9 | 0.546 4 | 0.474 4 | ||
31 | 0.509 3 | 0.523 7 | 0.526 2 | 0.517 2 | 0.463 9 | ||
41 | 0.490 6 | 0.478 | 0.415 5 | 0.513 3 | 0.548 9 | ||
51 | 0.4 | 0.431 6 | 0.431 2 | 0.526 6 | 0.522 | ||
61 | 0.526 6 | 0.512 8 | 0.557 | 0.575 5 | 0.483 | ||
71 | 0.498 4 | 0.528 3 | 0.518 1 | 0.535 6 | 0.45 | ||
Sea-abr | 11 | 0.874 4 | 0.861 2 | 0.797 8 | 0.799 2 | 0.741 7 | |
21 | 0.812 7 | 0.812 5 | 0.805 5 | 0.816 2 | 0.795 3 | ||
31 | 0.773 8 | 0.787 1 | 0.761 3 | 0.779 1 | 0.771 1 | ||
41 | 0.822 7 | 0.837 3 | 0.846 3 | 0.826 8 | 0.833 5 | ||
51 | 0.878 8 | 0.869 6 | 0.801 7 | 0.845 8 | 0.846 9 | ||
61 | 0.806 5 | 0.819 4 | 0.825 5 | 0.811 4 | 0.837 2 | ||
71 | 0.773 2 | 0.791 9 | 0.762 2 | 0.771 4 | 0.826 8 | ||
Sine-abr | 11 | 0.066 2 | 0.061 4 | 0.067 8 | 0.105 4 | 0.193 2 | |
21 | 0.267 3 | 0.266 1 | 0.272 4 | 0.469 6 | 0.339 1 | ||
31 | 0.099 5 | 0.097 2 | 0.107 4 | 0.248 7 | 0.259 4 | ||
41 | 0.261 5 | 0.248 5 | 0.250 8 | 0.507 7 | 0.336 9 | ||
51 | 0.071 1 | 0.057 9 | 0.072 5 | 0.299 5 | 0.292 9 | ||
61 | 0.272 9 | 0.271 1 | 0.278 5 | 0.548 5 | 0.425 6 | ||
71 | 0.098 6 | 0.095 7 | 0.115 5 | 0.311 4 | 0.414 5 | ||
win-loss ( |
33-72 | 35-70 | 46-59 | 74-31 | 71-34 | 56-49 |
概念漂移发生后各算法准确率的恢复
Dataset | Algorithm | ||||||
ReaSC | SmSCluster | SEClass | SPASC | REDLLA | SUN | ||
注: 粗体表示在对应数据块上6个算法中分类准确率的最大者 | |||||||
Agrawal-abr | 12 | 0.460 1 | 0.449 | 0.434 8 | 0.434 8 | 0.462 5 | |
22 | 0.554 5 | 0.547 7 | 0.626 9 | 0.550 3 | 0.483 | ||
32 | 0.517 7 | 0.543 1 | 0.534 4 | 0.517 1 | 0.475 | ||
42 | 0.487 9 | 0.485 2 | 0.611 4 | 0.493 1 | 0.557 4 | ||
52 | 0.401 6 | 0.472 5 | 0.540 5 | 0.515 9 | 0.511 6 | ||
62 | 0.568 4 | 0.559 1 | 0.667 9 | 0.568 2 | 0.491 7 | ||
72 | 0.511 4 | 0.544 5 | 0.542 4 | 0.530 8 | 0.465 3 | ||
Sea-abr | 12 | 0.884 9 | 0.883 6 | 0.800 3 | 0.803 2 | 0.771 8 | |
22 | 0.830 4 | 0.837 5 | 0.814 5 | 0.81 | 0.797 8 | ||
32 | 0.807 7 | 0.819 3 | 0.784 8 | 0.780 4 | 0.793 6 | ||
42 | 0.842 5 | 0.860 7 | 0.827 2 | 0.837 8 | 0.842 8 | ||
52 | 0.890 6 | 0.888 4 | 0.805 4 | 0.849 6 | 0.848 7 | ||
62 | 0.824 7 | 0.832 7 | 0.811 | 0.847 4 | 0.835 5 | ||
72 | 0.811 2 | 0.821 | 0.845 2 | 0.782 3 | 0.837 7 | ||
Sine-abr | 12 | 0.083 4 | 0.078 9 | 0.860 3 | 0.217 3 | 0.428 6 | |
22 | 0.283 | 0.291 5 | 0.700 1 | 0.467 6 | 0.393 2 | ||
32 | 0.113 6 | 0.116 3 | 0.680 5 | 0.255 3 | 0.297 8 | ||
42 | 0.297 8 | 0.281 2 | 0.837 1 | 0.519 6 | 0.338 8 | ||
52 | 0.088 6 | 0.073 6 | 0.838 | 0.291 2 | 0.276 3 | ||
62 | 0.297 | 0.294 7 | 0.685 1 | 0.558 | 0.425 4 | ||
72 | 0.120 5 | 0.111 2 | 0.676 | 0.308 8 | 0.401 8 | ||
win-loss ( |
38-67 | 39-66 | 93-12 | 61-44 | 46-59 | 38-67 |
从
从
为了分析标记比例的大小(即有标记样本的数量)对算法分类准确率产生的影响, 我们将标记比例的大小分别设置为0.05, 0.1, 0.2和0.3. 实验结果见
在包含突变或者渐变概念漂移的数据集上, 不同标记比例下各算法的累计分类准确率
Dataset | Ratio | SPASC | ReaSC | SmSCluster | SEClass | REDLLA | SUN |
XX-abr | |||||||
Agrawal | 0.05 | 0.582 5 | 0.594 3 | 0.596 3 | 0.558 8 | 0.536 2 | 0.528 5 |
0.1 | 0.589 1 | 0.597 3 | 0.601 1 | 0.565 9 | 0.564 8 | 0.535 9 | |
0.2 | 0.624 4 | 0.601 1 | 0.607 7 | 0.577 2 | 0.567 1 | 0.561 9 | |
0.3 | 0.631 2 | 0.6023 | 0.609 6 | 0.586 6 | 0.572 5 | 0.588 8 | |
Sea | 0.05 | 0.799 9 | 0.872 1 | 0.870 3 | 0.839 | 0.811 7 | 0.776 1 |
0.1 | 0.794 4 | 0.875 7 | 0.874 9 | 0.866 1 | 0.828 2 | 0.796 | |
0.2 | 0.799 6 | 0.875 8 | 0.878 3 | 0.883 7 | 0.828 8 | 0.813 3 | |
0.3 | 0.795 8 | 0.878 8 | 0.879 2 | 0.885 9 | 0.836 3 | 0.819 3 | |
Sine | 0.05 | 0.494 | 0.580 9 | 0.579 6 | 0.748 7 | 0.489 3 | 0.521 2 |
0.1 | 0.497 8 | 0.585 6 | 0.583 2 | 0.778 7 | 0.497 8 | 0.520 4 | |
0.2 | 0.758 7 | 0.587 1 | 0.588 8 | 0.804 8 | 0.489 9 | 0.529 7 | |
0.3 | 0.765 2 | 0.587 3 | 0.589 6 | 0.815 1 | 0.508 2 | 0.54 | |
XX-gra | |||||||
Agrawal | 0.05 | 0.589 1 | 0.611 3 | 0.607 8 | 0.552 8 | 0.565 6 | 0.533 3 |
0.1 | 0.594 1 | 0.616 9 | 0.614 3 | 0.560 1 | 0.576 1 | 0.569 6 | |
0.2 | 0.619 4 | 0.622 3 | 0.620 2 | 0.572 8 | 0.587 2 | 0.59 | |
0.3 | 0.626 3 | 0.625 1 | 0.626 4 | 0.582 | 0.579 8 | 0.594 3 | |
Sea | 0.05 | 0.792 4 | 0.873 6 | 0.872 2 | 0.830 8 | 0.826 9 | 0.725 8 |
0.1 | 0.789 7 | 0.878 1 | 0.876 9 | 0.871 4 | 0.834 | 0.816 3 | |
0.2 | 0.794 1 | 0.881 3 | 0.881 4 | 0.884 5 | 0.840 1 | 0.823 8 | |
0.3 | 0.785 4 | 0.885 2 | 0.884 4 | 0.886 8 | 0.841 3 | 0.829 2 | |
Sine | 0.05 | 0.492 8 | 0.665 8 | 0.664 5 | 0.704 7 | 0.49 | 0.520 1 |
0.1 | 0.495 9 | 0.674 2 | 0.669 9 | 0.728 8 | 0.498 7 | 0.531 8 | |
0.2 | 0.696 2 | 0.671 9 | 0.673 5 | 0.754 2 | 0.505 9 | 0.551 3 | |
0.3 | 0.694 5 | 0.672 3 | 0.676 4 | 0.767 6 | 0.512 9 | 0.556 9 |
在包含增量概念漂移的数据集上, 不同标记比例下各算法的累计分类准确率
Ratio | Incremental | |||||
SPASC | ReaSC | SmSCluster | SEClass | REDLLA | SUN | |
Hyperplane | ||||||
0.05 | 0.528 3 | 0.783 1 | 0.767 5 | 0.646 6 | 0.683 1 | 0.688 9 |
0.1 | 0.537 1 | 0.794 1 | 0.779 3 | 0.671 9 | 0.731 | 0.759 8 |
0.2 | 0.624 8 | 0.795 6 | 0.791 3 | 0.702 1 | 0.767 9 | 0.774 8 |
0.3 | 0.680 7 | 0.799 2 | 0.800 8 | 0.728 7 | 0.763 2 | 0.783 3 |
Gaussian | ||||||
0.05 | 0.485 6 | 0.371 | 0.383 3 | 0.662 | 0.404 2 | 0.314 1 |
0.1 | 0.508 6 | 0.369 3 | 0.380 4 | 0.680 9 | 0.425 7 | 0.354 1 |
0.2 | 0.603 7 | 0.379 5 | 0.389 6 | 0.698 7 | 0.447 3 | 0.380 1 |
0.3 | 0.661 | 0.376 6 | 0.387 1 | 0.701 1 | 0.438 8 | 0.385 4 |
在真实数据集上, 不同标记比例下各算法的累计分类准确率
Ratio | SPASC | ReaSC | SmSCluster | SEClass | REDLLA | SUN |
Poker hand | ||||||
0.05 | 0.257 | 0.507 9 | 0.504 4 | 0.580 4 | 0.568 9 | 0.571 6 |
0.1 | 0.251 | 0.521 9 | 0.516 1 | 0.583 2 | 0.575 3 | 0.563 6 |
0.2 | 0.547 8 | 0.527 8 | 0.529 2 | 0.585 3 | 0.606 8 | 0.606 |
0.3 | 0.547 5 | 0.529 6 | 0.538 4 | 0.585 | 0.585 3 | 0.594 |
Electricity | ||||||
0.05 | 0.550 9 | 0.640 1 | 0.646 6 | 0.605 1 | 0.557 1 | 0.546 1 |
0.1 | 0.573 1 | 0.655 4 | 0.658 7 | 0.625 5 | 0.618 5 | 0.568 2 |
0.2 | 0.576 8 | 0.660 6 | 0.663 | 0.638 5 | 0.703 3 | 0.689 1 |
0.3 | 0.617 6 | 0.665 4 | 0.665 | 0.645 1 | 0.715 6 | 0.720 7 |
Weather | ||||||
0.05 | 0.655 2 | 0.715 2 | 0.719 7 | 0.648 7 | 0.677 5 | 0.673 5 |
0.1 | 0.651 4 | 0.728 7 | 0.731 5 | 0.672 | 0.678 5 | 0.679 3 |
0.2 | 0.672 5 | 0.741 | 0.740 7 | 0.692 8 | 0.689 4 | 0.685 2 |
0.3 | 0.689 7 | 0.743 1 | 0.747 2 | 0.701 9 | 0.686 4 | 0.684 8 |
Forest cover type | ||||||
0.05 | 0.387 6 | 0.747 6 | 0.750 8 | 0.581 1 | 0.545 5 | 0.537 9 |
0.1 | 0.363 4 | 0.764 6 | 0.764 7 | 0.584 6 | 0.572 9 | 0.555 4 |
0.2 | 0.585 1 | 0.770 1 | 0.773 | 0.585 8 | 0.574 2 | 0.550 8 |
0.3 | 0.604 3 | 0.770 1 | 0.775 3 | 0.586 5 | 0.576 8 | 0.545 6 |
从
对于多模型算法, 为了分析分类器池大小(即池中最多能维持的分类器数量)对算法分类准确率产生的影响, 本文将分类器池的大小分别设置为1, 3, 5和7, 标记比例的大小设置为0.2. 实验结果见
在包含突变或者渐变概念漂移的数据集上, 分类器池的大小对分类准确率的影响
Dataset | Concept Num | Size | XX-abr | XX-gra | ||||||
SPASC | ReaSC | SmSCluster | SEClass | SPASC | ReaSC | SmSCluster | SEClass | |||
Agrawal | 4 | 1 | 0.591 | 0.608 2 | 0.605 7 | 0.579 2 | 0.597 6 | 0.599 6 | 0.596 4 | 0.574 2 |
4 | 3 | 0.612 8 | 0.622 2 | 0.621 | 0.579 | 0.612 2 | 0.621 4 | 0.619 7 | 0.574 | |
4 | 5 | 0.617 5 | 0.619 6 | 0.619 3 | 0.578 4 | 0.614 2 | 0.627 5 | 0.623 5 | 0.573 5 | |
4 | 7 | 0.623 6 | 0.610 3 | 0.613 4 | 0.577 6 | 0.615 9 | 0.626 4 | 0.622 9 | 0.573 | |
Sea | 4 | 1 | 0.784 2 | 0.816 2 | 0.808 | 0.846 2 | 0.781 3 | 0.810 3 | 0.805 1 | 0.845 3 |
4 | 3 | 0.797 7 | 0.870 2 | 0.867 3 | 0.873 6 | 0.794 1 | 0.869 1 | 0.866 5 | 0.874 3 | |
4 | 5 | 0.799 6 | 0.877 9 | 0.877 3 | 0.879 8 | 0.794 1 | 0.879 1 | 0.878 4 | 0.881 8 | |
4 | 7 | 0.799 6 | 0.877 | 0.878 3 | 0.882 6 | 0.794 1 | 0.881 7 | 0.881 1 | 0.884 1 | |
Sine | 4 | 1 | 0.499 9 | 0.791 9 | 0.790 9 | 0.783 4 | 0.497 9 | 0.733 6 | 0.734 8 | 0.740 1 |
4 | 3 | 0.750 7 | 0.762 9 | 0.763 8 | 0.802 4 | 0.653 7 | 0.755 3 | 0.758 1 | 0.751 1 | |
4 | 5 | 0.755 | 0.701 8 | 0.701 7 | 0.807 4 | 0.683 5 | 0.734 5 | 0.735 1 | 0.755 7 | |
4 | 7 | 0.758 1 | 0.628 7 | 0.629 2 | 0.806 3 | 0.693 5 | 0.697 3 | 0.697 1 | 0.755 2 |
在包含增量概念漂移的数据集上, 分类器池的大小对分类准确率的影响
Size | Incremental | |||||||
Hyperplane | Gaussian | |||||||
SPASC | ReaSC | SmSCluster | SEClass | SPASC | ReaSC | SmSCluster | SEClass | |
1 | 0.546 9 | 0.690 3 | 0.680 8 | 0.696 3 | 0.521 8 | 0.766 9 | 0.775 5 | 0.762 9 |
3 | 0.618 9 | 0.749 7 | 0.741 1 | 0.699 1 | 0.560 5 | 0.706 8 | 0.712 8 | 0.762 1 |
5 | 0.621 2 | 0.776 1 | 0.767 | 0.700 2 | 0.592 2 | 0.634 7 | 0.642 5 | 0.748 4 |
7 | 0.623 8 | 0.788 8 | 0.781 7 | 0.700 8 | 0.602 8 | 0.541 8 | 0.550 2 | 0.721 |
在真实数据集上, 分类器池的大小对分类准确率的影响
Size | Poker hand | Weather | ||||||
SPASC | ReaSC | SmSCluster | SEClass | SPASC | ReaSC | SmSCluster | SEClass | |
1 | 0.247 6 | 0.525 6 | 0.521 8 | 0.585 5 | 0.672 5 | 0.687 8 | 0.678 8 | 0.696 6 |
3 | 0.517 4 | 0.542 8 | 0.535 6 | 0.585 8 | 0.672 5 | 0.720 5 | 0.722 5 | 0.696 9 |
5 | 0.528 7 | 0.536 4 | 0.530 7 | 0.585 6 | 0.672 5 | 0.731 7 | 0.734 8 | 0.696 2 |
7 | 0.537 8 | 0.530 4 | 0.528 7 | 0.585 5 | 0.672 5 | 0.737 | 0.738 6 | 0.695 7 |
Electricity | Forest cover type | |||||||
1 | 0.568 4 | 0.635 3 | 0.631 8 | 0.628 9 | 0.412 1 | 0.835 8 | 0.837 6 | 0.581 |
3 | 0.576 7 | 0.651 2 | 0.651 | 0.631 1 | 0.467 3 | 0.819 6 | 0.821 3 | 0.582 2 |
5 | 0.576 8 | 0.653 6 | 0.655 6 | 0.636 4 | 0.512 3 | 0.803 | 0.805 | 0.583 1 |
7 | 0.576 8 | 0.655 7 | 0.654 3 | 0.635 7 | 0.545 4 | 0.788 2 | 0.79 | 0.584 1 |
从
从
对于SPASC, 分类器池中的基分类器通常对应着不同概念. 随着分类器池的扩大, 算法可保存的已经学到的概念数量也随之增大, 使得概念漂移的检测能更准确. 因此理论上, 准确率应随着分类器池大小的增加而增大, 这一点在大多数数据集的实验结果上得到了验证. 而对于ReaSC和SmSCluster算法, 它们的分类器池更新规则是: 在当前数据块
由于开放环境下数据的产生受到众多因素的影响, 数据分布的变化更加复杂. 这将导致更加复杂的机器学习问题. 通过对现有带概念漂移的数据流的半监督分类算法的归类、总结以及对部分算法的实验结果的详细分析, 数据流半监督分类算法有以下几个方面的问题值得去做进一步的探讨.
(1) 概念漂移检测问题. 根据概念漂移产生的本质, 一个好的概念漂移检测方法应该同时检测分布
(2) 重现概念学习问题. 在开放环境下, 数据的分布可能呈现周期性的变化. 当历史概念重复出现时, 相应的历史模型应被重新调用来对即将到来的样本实施分类和增量学习, 以避免重新学习. 在半监督环境下, 在一个数据块上重新学得的模型由于可学习的有标记样本量少而导致模型泛化能力比较差, 这又会导致对后续概念漂移检测的不准. 因此, 当检测到重现概念时, 如何利用当前获得的数据更新已学习的模型, 使得已学习的分类器的泛化能力不断提高? 然而, 大部分数据流半监督算法没有考虑重现概念的增量学习问题. 更进一步, 如何能在概念漂移检测不太准确的条件下, 使得增量学习能不断提高对重现概念的检测能力和泛化能力?
(3) 类别不平衡问题. 类别不平衡在监督环境下的数据流分类领域是一个具有挑战性的问题, 已有数据流分类综述中对该问题进行了总结和展望. 然而在半监督环境下, 类别不平衡现象将会使问题变得更加严重, 极端情况下可能导致某一类的样本不存在以至于无法学习该类样本中的知识, 概念漂移检测更会受到影响;
(4) 噪声数据问题. 受环境的变化、设备的损耗和人工错误地标注等因素的影响, 数据中往往存在噪声.在半监督环境下, 有标记样本数量比较少, 模型会对噪声数据的适应性比较差, 可能因学习噪声数据而导致局部无标记样本的错误利用. 比如: 在局部聚簇中, 通过打标记的方式来利用无标记样本进行模型训练的方法中, 如果该聚簇中有标记的噪声数据占多数, 那么该簇中的无标记样本将被打上错误标记, 将放大噪声数据带来的负面影响;
(5) 标记稀缺问题. 在数据流半监督分类的实际应用中, 从标注成本来看, 样本被标记的比率越低越好.但是从本文的实验中也看出: 标记比率过低, 算法的分类准确率不会太好. 因此, 在标记稀缺条件下, 如何利用半监督分类、迁移学习、增量学习、主动学习的方法来提高算法的分类准确率, 也是非常紧迫的问题.
开放环境下的数据流半监督分类给机器学习带来了极大挑战. 本文对现有带概念漂移的数据流的半监督分类算法进行了介绍, 按照各算法采用的分类器类型, 对已有的多个算法逐个进行了介绍与总结; 归纳并总结了现有数据流半监督分类中采用的概念漂移检测方法; 在一些被广泛使用的真实数据集和人工数据集上, 对部分数据流半监督分类算法进行了多方面的比较与分析. 实验结果表明: 数据流半监督分类算法的分类准确率与分类策略、概念漂移检测方法、分类模型更新策略等众多因素有关, 但与数据分布本身关系最大. 在具体的研究与应用中, 最好能根据数据分布的特点选择数据流半监督分类算法以及样本标注比率与标注方式. 最后, 本文还提出了带概念漂移的数据流的半监督分类一些值得进一步深入探讨的问题.
尽管带概念漂移的数据流的半监督分类已经取得了很多研究成果, 并被应用于实际场景中. 但是该方面的研究仍然处于发展初期, 远还没有成熟, 期待学界进一步的研究和突破.
本文由“面向开放场景的鲁棒机器学习”专刊特约编辑陈恩红教授、李宇峰副教授、邹权教授推荐.
Lian D, Xie X, Chen E. Discrete matrix factorization and extension for fast item recommendation. IEEE Trans. on Knowledge and Data Engineering (TKDE), 2021, 33(5): 1919-1933. [doi: 10.1109/TKDE.2019.2951386]
et al. A united approach to learning sparse attributed network embedding. In: Proc. of the IEEE Int'l Conf. on Data Mining. Piscataway: IEEE, 2018. 557-566. [doi: 10.1109/ICDM.2018.00071]]]>
Zhang ML, Li YK, Liu XY,
Guo GD, Chen LF, Ye YF,
Zhao XW, Liang JY. An attribute weighted clustering algorithm for mixed data based on information entropy. Journal of Computer Research and Development, 2016, 53(5): 1018-1028 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2016.20150131]
赵兴旺, 梁吉业. 一种基于信息熵的混合数据属性加权聚类算法. 计算机研究与发展, 2016, 53(5): 1018-1028. [doi: 10.7544/issn1000-1239.2016.20150131]
Huai BX, Chen EH, Zhu HS,
Zhang ML, Zhou ZH. Exploiting unlabeled data to enhance ensemble diversity. Data Mining and Knowledge Discovery, 2013, 26(1): 98-129. [doi: 10.1007/s10618-011-0243-9]
Guo GD, Li N, Chen LF. Concept drift detection for data streams based on mixture model. Journal of Computer Research and Development, 2014, 51(4): 731-742 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2014.20120582]
郭躬德, 李南, 陈黎飞. 一种基于混合模型的数据流概念漂移检测算法. 计算机研究与发展, 2014, 51(4): 731-742. [doi: 10.7544/issn1000-1239.2014.20120582]
Bai L, Cheng XQ, Liang JY,
Zhang X, Liu C, Suen C. Towards robust pattern recognition: A review. Proc. of the IEEE, 2020, 108(6): 894-922. [doi: 10.1109/JPROC.2020.2989782]
et al. Generalizing to unseen domains: A survey on domain generalization. In: Proc. of the 30th Int'l Joint Conf. on Artificial Intelligence. New York: ACM, 2021. 4627-4635. [doi: 10.24963/ijcai.2021/628]]]>
Sayed-Mouchaweh M, Lughofer E. Learning in Non-stationary Environments: Methods and Applications. Germany: Springer, 2013. [doi: 10.1007/978-1-4419-8020-5]
Gama J, Ganguly A, Omitaomu O,
Zhao P, Zhou ZH. Learning from distribution-changing data streams via decision tree model reuse. Scientia Sinica Informationis, 2021, 51(1): 1-12. (in Chinese with English abstract). [doi: 10.1360/SSI-2020-0170]
赵鹏, 周志华. 基于决策树模型重用的分布变化流数据学习. 中国科学: 信息科学, 2021, 51(1): 1-12. [doi: 10.1360/SSI-2020-0170]
Hosseini MJ, Gholipour A, Beigy H. An ensemble of cluster-based classifiers for semi-supervised classification of non-stationary data streams. Knowledge and Information Systems, 2016, 46(3): 567-597. [doi: 10.1007/s10115-015-0837-4]
Xu WH, Qin Z, Chang Y. Semi-supervised learning based ensemble classifier for stream data. Pattern Recognition and Artificial Intelligence, 2012, 25(2): 292-299 (in Chinese with English abstract). [doi: 10.16451/j.cnki.issn1003-6059.2012.02.010]
徐文华, 覃征, 常扬. 基于半监督学习的数据流集成分类算法. 模式识别与人工智能, 2012, 25(2): 292-299. [doi: 10.16451/j.cnki.issn1003-6059.2012.02.010]
Wang Y, Li T. Improving semi-supervised co-forest algorithm in evolving data streams. Applied Intelligence, 2018, 48(10): 3248-3262. [doi: 10.1007/s10489-018-1149-7]
doi: 10.1007/978-3-642-28931-6_50]]]>
Krawczyk B, Minku LL, Gama J,
doi: 10.1609/aaai.v34i04.6186]]]>
Noorbehbahani F, Fanian A, Mousavi R,
Hu Y, Baraldi P, Maio F,
Sedhai S, Sun A. Semi-supervised spam detection in Twitter stream. IEEE Trans. on Computational Social Systems, 2017, 5(1): 169-175. [doi: 10.1109/TCSS.2017.2773581]
Matuszyk P, Spiliopoulou M. Stream-based semi-supervised learning for recommender systems. Machine Learning, 2017, 106(6): 771-798. [doi: 10.1007/s10994-016-5614-4]
Grzenda M, Bustillo A. Semi-supervised roughness prediction with partly unlabeled vibration data streams. Journal of Intelligent Manufacturing, 2019, 30(2): 933-945. [doi: 10.1007/s10845-018-1413-z]
Schlimmer JC, Granger RH. Incremental learning from noisy data. Machine Learning, 1986, 1(3): 317-354. [doi: 10.1007/BF00116895]
doi: 10.1007/978-3-540-25966-4_1]]]>
Tsymbal A. The problem of concept drift: Definitions and related work. Technical Report, Department of Computer Science Trinity College Dublin, 2004.
Wang T, Li ZJ, Yan YJ,
王涛, 李舟军, 颜跃进, 等. 数据流挖掘分类技术综述. 计算机研究与发展, 2007, 44(11): 1809-1815. [doi: 10.1038/onc.2012.370]
Žliobaitė I. Learning under Concept Drift: An Overview. Computer Science, 2010.
Gama J. A survey on learning from data streams: Current and future trends. Progress in Artificial Intelligence, 2012, 1(1): 45-55. [doi: 10.1007/s13748-011-0002-6]
Hoens TR, Polikar R, Chawla NV. Learning from streaming data with concept drift and imbalance: An overview. Progress in Artificial Intelligence, 2012, 1(1): 89-101. [doi: 10.1007/s13748-011-0008-0]
Wen YM, Qiang BH, Fan ZG. A survey of the classification of data streams with concept drift. CAAI Trans. on Intelligent Systems, 2013, 8(2): 95-104 (in Chinese with English abstract). [doi: 10.3969/j.issn.1673-4785.201208012]
文益民, 强保华, 范志刚. 概念漂移数据流分类研究综述. 智能系统学报, 2013, 8(2): 95-104. [doi: 10.3969/j.issn.1673-4785.201208012]
Gama J, Žliobaitė I, Bifet A,
Krempl G, Žliobaite I, Brzeziński D,
Gonçalves JPM, de Carvalho Santos SGT, de Barros RSM,
Ditzler G, Roveri M, Alippi C,
Nguyen HL, Woon YK, Ng WK. A survey on data stream clustering and classification. Knowledge and Information Systems, 2015, 45(3): 535-569. [doi: 10.1007/s10115-014-0808-1]
Ding J, Han M, Li J. Review of concept drift data streams mining techniques. Computer Science, 2016, 43(12): 24-29, 62 (in Chinese with English abstract). [doi: 10.11896/j.issn.1002-137x.2016.12.004]
丁剑, 韩萌, 李娟. 概念漂移数据流挖掘算法综述. 计算机科学, 2016, 43(12): 24-29, 62. [doi: 10.11896/j.issn.1002-137x.2016.12.004]
Webb GI, Hyde R, Cao H,
Iwashita AS, Papa JP. An overview on concept drift learning. IEEE Access, 2018, 7: 1532-1547. [doi: 10.1109/ACCESS.2018.2886026]
Khamassi I, Sayed-Mouchaweh M, Hammami M,
Lu J, Liu A, Dong F,
doi: 10.1109/IJCNN.2012.6252541]]]>
Dyer KB, Capo R, Polikar R. Compose: A semi-supervised learning framework for initially labeled nonstationary streaming data. IEEE Trans. on Neural Networks and Learning Systems, 2013, 25(1): 12-26. [doi: 10.1109/TNNLS.2013.2277712]
Ferreira RS, Zimbrão G, Alvim LGM. AMANDA: Semi-supervised density-based adaptive model for non-stationary data with extreme verification latency. Information Sciences, 2019, 488: 219-237. [doi: 10.1016/j.ins.2019.03.025]
et al. Classifier and cluster ensembles for mining concept drifting data streams. In: Proc. of the 2010 IEEE Int'l Conf. on Data Mining. Piscataway: IEEE, 2010. 1175-1180. [doi: 10.1109/ICDM.2010.125]]]>
doi: 10.1145/347090.347107]]]>
doi: 10.1145/502512.502529]]]>
Žliobaitė I. Adaptive training set formation [Ph. D. Thesis]. Vilniaus: Vilnius University, 2010.
doi: 10.1145/312129.312285]]]>
Feng ZX, Wang M, Yang SY,
doi: 10.5555/2888116.2888121]]]>
Khezri S, Tanha J, Ahmadi A,
et al. A practical approach to classify evolving data streams: Training with limited amount of labeled data. In: Proc. of the 8th IEEE Int'l Conf. on Data Mining. Piscataway: IEEE, 2008. 929-934. [doi: 10.1109/ICDM.2008.152]]]>
Masud MM, Woolam C, Gao J,
doi: 10.1007/978-3-642-04125-9_58]]]>
doi: 10.1007/978-981-13-2122-1_8]]]>
doi: 10.1109/EAIS.2018.8397172]]]>
Wen YM, Liu S. Semi-supervised classification of data streams by BIRCH ensemble and local structure mapping. Journal of Computer Science and Technology, 2020, 35(2): 295-304. [doi: 10.1007/s11390-020-9999-y]
Din SU, Shao J, Kumar J,
Zheng X, Li P, Hu X,
Li PP, Wu XD, Hu XG. Mining recurring concept drifts with limited labeled streaming data. ACM Trans. on Intelligent Systems and Technology, 2012, 13(2): 241-252. [doi: 10.1145/2089094.2089105]
Wu XD, Li PP, Hu XG. Learning from concept drifting data streams with unlabeled data. Neurocomputing, 2012, 92: 145-155. [doi: 10.1016/j.neucom.2011.08.041]
et al. Concurrent semi-supervised learning of data streams. In: Proc. of the 13th Int'l Conf. on Data Warehousing and Knowledge Discovery. Berlin, Heidelberg: Springer, 2011. 445-459. [doi: 10.1007/978-3-642-23544-3_34]]]>
doi: 10.1109/SERE-C.2014.31]]]>
Hu XG, Ma LW, Li PP. Data stream ensemble classification algorithm based on tri-training. Journal on Data Acquisition and Processing, 2017, 32(5): 853-860 (in Chinese with English abstract). [doi: 10.16337/j.1004-9037.2017.05.001]
胡学钢, 马利伟, 李培培. 一种基于Tri-training的数据流集成分类算法. 数据采集与处理, 2017, 32(5): 853-860. [doi: 10.16337/j.1004-9037.2017.05.001]
et al. Transfer learning for semi-supervised classification of non-stationary data streams. In: Proc. of the 27th Int'l Conf. on Neural Information Processing. Berlin: Springer, 2020. 468-477. [doi: 10.13140/2.1.3891.2644]]]>
doi: 10.1007/978-3-030-63833-7_54]]]>
Jr JRB, Lopes A, Liang Z. Partially labeled data stream classification with the semi-supervised
Jia Y, Yan S, Zhang C. Semi-supervised classification on evolutionary data. In: Proc. of the 21st Int'l Joint Conf. on Artificial Intelligence. New York: ACM, 2009. 1083-1088.
doi: 10.1109/ICDM.2009.76]]]>
Zhu X, Jin R. Multiple information sources cooperative learning. In: Proc. of the 21sth Int'l Joint Conf. on Artificial Intelligence. New York: ACM, 2009. 1369-1375.
Guo B, Menon J, Willette B. Surface reconstruction using alpha shapes. Computer Graphics Forum, 2010, 16(4): 177-190. [doi: 10.1111/1467-8659.00178]
Li Y, Wang Y, Liu Q,
doi: 10.1109/IJCNN.2019.8852361]]]>
Widyantoro DH, Yen J. Relevant data expansion for learning concept drift from sparsely labeled data. IEEE Trans. on Knowledge and Data Engineering, 2005, 17(3): 401-412. [doi: 10.1109/TKDE.2005.48]
Haque A, Khan L, Baron M. Sand: Semi-supervised adaptive novel class detection and classification over data stream. In: Proc. of the 30th AAAI Conf. on Artificial Intelligence. New York: ACM, 2016. 1652-1658.
et al. Efficient handling of concept drift and concept evolution over stream data. In: Proc. of the IEEE 32nd Int'l Conf. on Data Engineering. Piscataway: IEEE, 2016. 481-492. [doi: 10.1109/ICDE.2016.7498264]]]>
doi: 10.1109/ICTAI.2017.00077]]]>
Li N. Clustering assumption based classification algorithm for stream data. Pattern Recognition and Artificial Intelligence, 2017, 30(1): 1-10 (in Chinese with English abstract). [doi: 10.16451/j.cnki.issn1003-6059.201701001]
李南. 基于聚类假设的数据流分类算法. 模式识别与人工智能, 2017, 30(1): 1-10. [doi: 10.16451/j.cnki.issn1003-6059.201701001]
et al. Classification and novel class detection in data streams with active mining. In: Proc. of the Pacific-Asia Conf. on Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2010. 311-324. [doi: 10.1007/978-3-642-13672-6_31]]]>
Žliobaitė I, Bifet A, Pfahringer B,
Arabmakki E, Kantardzic M. SOM-based partial labeling of imbalanced data stream. Neurocomputing, 2017, 262: 120-133. [doi: 10.1016/j.neucom.2016.11.088]
Zhu X, Zhang P, Lin X,
doi: 10.1137/1.9781611972771.42]]]>
Wang HY, Hu XG, Li PP. Semi-supervised short text stream classification based on vector representation and label propagation. Pattern Recognition and Artificial Intelligence, 2018, 31(7): 634-642 (in Chinese with English abstract). [doi: 10.16451/j.cnki.issn1003-6059.201807006]
王海燕, 胡学钢, 李培培. 基于向量表示和标签传播的半监督短文本数据流分类算法. 模式识别与人工智能, 2018, 31(7): 634-642. [doi: 10.16451/j.cnki.issn1003-6059.201807006]
et al. Knowledge transfer via multiple model local structure mapping. In: Proc. of the 14th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. New York: ACM, 2008. 283-291. [doi: 10.1145/1401890.1401928]]]>
Kim Y, Park CH. An efficient concept drift detection method for streaming data under limited labeling. IEICE Trans. on Information and Systems, 2017, 100(10): 2537-2546. [doi: 10.1587/transinf.2017EDP7091]
Tan CH, Lee V, Salehi M. Online semi-supervised concept drift detection with density estimation. arXiv: 1909.11251, 2019.
Bifet A, Holmes G, Kirkby R,
Elwell R, Polikar R. Incremental learning of concept drift in nonstationary environments. IEEE Trans. on Neural Networks, 2011, 22(10): 1517-1531. [doi: 10.1109/TNN.2011.2160459]