【学术论文】概念漂移数据流分类研究综述

第8卷第2期 智能系统学报 Vol.8 No.2 2013年4月 CAAI Transactions on Intelligent Systems Apr.2013 D0I:10.3969/i.i8sn.1673-4785.201208012 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20121116.1701.004.html 概念漂移数据流分类研究综述 文益民，强保华，范志刚2 (1.桂林电子科技大学计算机科学与工程学院，广西桂林541004；2.中国科学院上海高等研究院，上海201203) 摘要：由于现有各种机器学习算法本质上都基于一个静态学习环境，而以尽量保证学习系统泛化能力为目标的寻 优过程，概念漂移数据流分类给机器学习带来了巨大挑战.从数据流与概念漂移、概念漂移数据流分类研究的发展 与趋势、概念漂移数据流分类的主要研究领域、概念漂移数据流分类研究的新动态4个方面展开了文献综述，并分 析了当前概念漂移数据流分类算法存在的问题. 关键词：大数据；概念漂移；增量学习；适应学习；数据流：机器学习 中图分类号：TP391.4文献标志码：A文章编号：16734785(2012)020095-10 A survey of the classification of data streams with concept drift WEN Yimin',QIANG Baohua',FAN Zhigang? (1.College of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China;2.Shanghai Advanced Research Institute,Chinese Academy of Sciences,Shanghai 201203,China) Abstract:Because the current machine learning algorithms all are essentially an optimization procedure that aims to ensure the generalization ability based on static learning environment,the classification data streams with concept drift has brought severe challenges to machine learning.In order to address these concerns,a survey was developed consisting of four aspects:the introduction to data streams and concept drift,the development process and future trends,the main research fields,and the new developments in the study field of the classification data streams with concept drift.The existing problems relating to classification data streams with concept drift were discussed at last. Keywords:big data;concept drift;incremental learning;adaptive learning;data stream;machine learning 在社会生产和生活实践中，有一类问题是数据地检测到概念漂移，并对自身进行适应概念漂移的调 所包含的概念可能随时间而变化.自动化生产线 整，以对不断到来的数据尽可能地正确判断。 上，相近原因的问题产品会连续出现，然后问题产品 概念漂移问题给机器学习带来了巨大的挑战. 的特征也随之发生变化；商务活动中，顾客的购买兴 目前各种人工学习系统的构造算法在本质上都是基 趣随时间而变化；网络安全中，网络的访问模式随用 于一个静态的学习环境，而以尽量保证学习系统泛 户不同而变化；社交媒体上，用户的实际行为随其注 化能力为目标的寻优过程，所以现有的各种机器学 册位置而变化这些问题的共同特点是：不断产生数 习算法在本质上都不适应进行概念漂移数据流学 据形成流；数据流没有终点；数据流中数据包含的概 习.这种不适应体现在：计算模型或者缺乏获取新知 念随时可能产生变化.数据流中这种概念的变化在文 识的能力，或者不能保持原本学到的知识3) 中被称为概念漂移21.概念漂移要求学习系统能尽早 自“概念漂移”(concept drift)在1986年由 Schlimmer和Granger2首次提出后，国内外众多研 收稿日期：2012-0807.网络出版日期：2012-11-16 基金项目：湖南省自然科学基金资助项目(10J5067):湖南省科技计 究人员对概念漂移数据流分类展开了深入研 划资助项目(2010GK3047);广西省可信软件重点实验室 究.Kuncheva4、Tsymbalt3)、王涛[6]、Zliobaite (桂林电子科技大学)开放课题资助项目(KX201118). 通信作者：文益民.E-mail:ymwen2004@yahoo.com.cm. Hoens8]和Gama9]等先后从各自的角度对概念漂 移数据流分类研究进行了很好的文献综述.与以上

·104 智能系统学报 第8卷 [C]//Proceedings of the Eighth Australian Joint Confer- 其中被SC1、E以检索18篇，翻译译著1部. ence on Artificial Intelligence.Canberra,Australia,1995: 91-98. 强保华，男，1972年生，教授，硕士 [96]MOVELLAN J R,MINEIRO P.Robust sensor fusion:a- 生导师，博士，主要研究方向为Wb信 nalysis and application to audio visual speech recognition 息处理、智能搜索、海量信息处理、网络 [J].Machine Learning,1998,32(2):85-100. 信息集成.获西南大学教学成果奖果三 [97]BERNSTEIN A,VORBURGER P,EGGER P.A scenario- 等奖1项，主持国家自然科学基金及省 based approach for direct interruptability prediction on 部级科研项目共8项.发表学术论文20 wearable devices[J].Interational Journal of Pervasive 余篇，其中被I检索12篇，翻译译著1部. Computing and Communications,2008,3(4):426-438. 作者简介： 范志刚，男，1978年生，副研究员， 文益民，男，1969年生，教授，硕士 博士，主要研究方向为大规模数据挖掘 生导师，博士，CCF高级会员，主要研究 和机器学习及其高性能分布式计算.曾 方向为机器学习与数据挖掘、极化SAR 主持中科院重点部署项目等科研项目 图像处理、社会计算获得省部级教学、 发表学术论文14篇，其中被SCI、EI检 科研奖励5项，主持省部级科研项目8 索10篇. 项，发表学术论文30余篇， 高级数据挖掘与应用国际学术会议 The 9th International Conference on Advanced Data Mining and Applications (ADMA 2013) ADMA 2013 will take place in Zhejiang University,Hangzhou,14th-16th December 2013.It is our pleasure to invite you to contribute papers,register and participate at ADMA 2013.The conference aims at bringing together the experts on data mining from around the world,and providing a leading intemational forum for the dissemination of original research find- ings in data mining,spanning applications,algorithms,software and systems,as well as different applied disciplines with potential in data mining. Topics of interest include but not limited to: Advanced data ming Mass data mining Web mining Social network mining Document mining High performance data mining Economic data mining Image mining Data mining visualization Parallel and distributed data mining Multimedia mining Security and privacy issues Data stream mining Biomedical data mining Other issues on data mining Graph mining Complex data mining Applications Social network application E-commerce and Web service Data mining systems in finance,economic,e-commerce Medical informatics Emerging applications of mass data mining Disaster prediction Empirical study of data mining algorithm Financial market analysis Parallel data mining application Data mining for education DNA sequencing,Bioinformatics Intelligent systems Genomics and biometrics Website:http://www.adma2013.org/

96 智能系统学报 第8卷 这些综述相比，本综述具有如下特色之处：1)剖析 人认为是一种概念漂移191，有人则认为属于概念进 了概念漂移数据流分类研究产生和发展的脉络：2) 化[2 包含了概念漂移数据流分类的最新研究动向—概 总之，学术界对概念漂移的认识日渐清晰，但目 念漂移数据流分类中的类别不平衡学习、重复概念 前还缺少对概念漂移的统一描述.Moreno-Torres等 学习及半监督学习和主动学习问题；3)深入分析了 试图利用数据漂移(data shif)的概念来统一已有各 当前概念漂移数据流分类算法存在的问题 种概念漂移的描述2 1数据流与概念漂移 2概念漂移数据流分类研究的发展与趋势 数据流分类问题引起研究人员关注的原因主要 自“概念漂移”首次提出后，得到了学术界的日 有2个：1)因为自动数据获取技术的飞速发展使得 益重视.从1986一2000年左右这段时间的研究主要 人类获得了大量的数据.数据量太大时，数据不能被 围绕单分类器展开一使用单个分类器实现概念漂 一次性装入内存；2)由于传感器技术的发展，使得 移数据流分类.Kilander等提出了COBBIT2i;Wid- 人类获得了大量与时间和环境相关的数据「o).Ga mer和Kbat提出了FLORAU];Hulten等提出了 ma1和Street!山讨论了数据流分类问题的顺序处 CVFDT4;Black等提出了CD3s];同时研究人员开 理、单向通过、内存有限等特点.数据流分类通常被 始关注概念漂移数据流分类的理论问题24.为深入 描述为在线分类模型2]，也就是分类器每次只对一 探讨数据产生的情境(context)与概念漂移的关系， 个样本分类，在完成对该样本的分类后，分类器将得 l98年由Dietterich、Widmer和Kubat发起，Machine 到由专家给出的该样本的真实类别，该样本及其类 Learning出版了研究概念漂移数据流的专刊2] 别标志被用于分类器更新，当分类器完成更新后，将 由于使用单分类器处理概念漂移数据流时需要 对下一个接收到的样本实施分类.在线分类模型通 不断更新分类模型且分类器泛化能力不高，Street 常又被扩展为分类器每次分类或学习一批样本。 等首次将集成学习引入概念漂移数据流分类，提 数据流分为2种：1)数据源产生的数据独立同 出了SEA算法.因此，从2000年左右开始，研究人 分布，研究人员称为稳定数据流]：2)数据源产生 员对概念漂移数据流分类的研究开始转移到分类器 的数据不独立同分布，研究人员认为在数据产生过 集成上来.通过多分类器集成，实现对历史样本的选 程中发生了“概念漂移”21，称其为动态数据流4。 择，提高分类器泛化能力.Wang等提出的AWE[]、 研究人员对概念漂移的深入理解是通过分析概念漂 Kolter等提出的DWM和AddExp[293o]和Bifet等提 移的种类及产生的原因逐步得到的. 出的ADWIN和ASHT[31]是这个领域里非常有影响 Widmer等5]认为数据产生环境的变化导致了 的成果。 概念漂移，并将概念漂移区分为虚概念漂移和实概 2000年左右，概念漂移数据流分类研究进人了 念漂移.Kly等16认为概念漂移是样本与其类别 快速发展期，研究人员开始考虑更加接近实际状况 的联合概率随时间变化而产生，其产生原因分3种： 的概念漂移数据流.Klinkenberg和Lanquillon比较 1)某类的先验概率发生变化；2)某类的类概率发生 早地研究了在检测概念漂移时只有部分样本获得用 变化；3)样本后验概率发生变化.Kuncheva4]引用 户反馈或者没有反馈的情形234].2004年由Intelli- 时间序列分析方法将概念漂移分为4种：随机噪声、 gent Data Analysis期刊出版的概念漂移数据流专 随机趋势、随机替换和系统趋势.其中，随机趋势中 刊35]主要探讨了如何利用增量学习方法以较小的 包含渐变性概念漂移，随机替换中包含突变性概念 代价使已有分类器适应概念漂移；之后概念漂移数 漂移，系统趋势中包含着重复性概念漂移.Narasim- 据流分类中的类别不平衡学习362]、概念重复学 hamurthy等I)根据数据产生的多源性提出了概念 习345]、半监督学习68]、主动学习[94]等问题开 漂移的产生模型.Zliobaite把概念漂移分为4种：突 始得到较多关注.2010年IOS还出版了《Adaptive 变性概念漂移、渐变性概念漂移、增量性概念漂移和 Stream Mining:Pattern Learning and Mining from E- 重复性概念漂移].Minku等8]在总结他人工作的 volving Data Streams》.从近年机器学习与数据挖掘 基础上，选择了纯度、速度、可预测度、频度、重复度 领域的一些国际权威期刊和国际顶级会议上发表的 5个维度，将概念漂移分成14种.对数据流中增加 论文来看，概念漂移数据流分类的研究正日益成为 了类别的情形，学术界还没有达成一致认识一有 学术界关注的焦点，对概念漂移数据流的研究已经

第2期 文益民，等：概念漂移数据流分类研究综述 ·97· 开始与转移学习5s6、进化计算758]、特征选择s9] 一个类似SEA的AWE(accuracy-weighted ensem- 聚类1、时间复杂度分析611、社会计算1等结合 bles)算法，该算法根据最新采集的训练样本集计算 起来.由于运动是物质的本质，概念漂移也是数据的 各基分类器的权值.Kyosuke]提出了ACE(adap 本质.因此，从趋势上来讲，已有各种模式分类的理 tive classifier-ensemble)算法，该算法在集成分类器 论和算法都可与概念漂移相结合而引出更多新的研 的基础上增加了一个能进行在线学习的分类器，以 究问题 提高算法对概念漂移的反应速度.Muhlbaier 等[9,4提出了Leam+NSE,该算法根据已训练的 3 概念漂移数据流分类的主要研究领域 基分类器和集成分类器在最新采集训练样本集上的 3.1概念漂移数据流学习器的构建 分类性能，来调整各样本对应的权值和各基分类器 对已有各种学习器进行调整使之适应概念漂移 的权值.文益民等5]提出了基于分类置信度的概念 数据流学习是目前主要的研究方向.这些算法可分 漂移检测方法，根据分类置信度实现分类器的选择 为2类：1)通过单分类器实现；2)通过多分类器集 集成，使得集成分类器能快速适应新概念.关菁华 成实现 等6提出了一种选择性集成方法，该算法根据各基 利用单分类器进行概念漂移数据流学习的方法 分类器在验证数据集上的输出结果与参考向量之间 有4种：1)选择训练样本.该类方法的主要思路是： 的角度来选择参与集成的分类器.朱群等)提出了 从采集的训练样本中选择一部分最合适对未来数据 一种基于双层窗口方法，该算法将滑动窗口分解成多 实施准确分类的样本训练分类器，其主要做法有滑 个基本窗口，以基本窗口为单位进行概念漂移检测 动窗口法、自适应滑动窗口调整法[64]以及动态样 以上这些算法还有一个共同点，即假定一个数据块中 本选择法[66].2)给训练样本赋以权值.该类方法 没有概念漂移，因此需要事先了解数据流的结构 的主要思路是对最新的训练样本赋以最大的权值， 基于在线学习模型对整个数据流实施集成学习 以提高对新概念的反应速度[1.3)调整学习器的 的思路与Adaboosting算法的思路类似.Kolter等提 结构.该类方法的特点是动态调整分类器的内部结 出了基于动态带权多数投票(DWM)的学习算法[29] 构，以适应概念漂移检测的要求.Hulten等提出的 和Add正xp3o,该算法能根据集成分类器的分类性 CVTI4用适合新概念的子树替换旧子树；Nunez等 能动态地增加或者删除基分类器；孙岳等[78]提出了 提出了OlineTree2,该算法中决策树的每个叶子节 一种基于多分类器的概念漂移挖掘算法，该算法的 点都维护一个时间窗口和局部性能测度，当测度下 思路与AddExp类似，只是基分类器的权值设置不 降时，时间窗口将减小21.4)是各种方法的组 同；辛轶等[9提出了IKnnM-DHecoc算法，该算法根 合6,14 据新到样本的概念漂移度调整编码矩阵，然后根据 多分类器集成是机器学习的研究热点之一.国 调整后的编码矩阵更新训练基分类器， 内外学者在利用集成学习策略实施概念漂移数据流 3.2概念漂移数据流学习理论的研究 学习方面已经做了许多探索，具体的研究内容主要 概念漂移数据学习理论主要是基于在线学习模 分2个方面：1)利用集成学习策略对数据流实施分 型展开研究.Ku[24]给出了在前一个概念是可能近 块学习；2)基于在线学习模型对整个数据流实施集 似正确学习(PAC)的条件下，实现对下一个概念的 成学习，即所有基分类器采用相同的学习算法，它们 PAC学习所需的最多样本数的上界；Helmbold等2s] 各自的训练样本来自同一数据流。 在稳定渐变概念漂移和确保未来样本错误率下界的 利用集成学习策略对数据流实施分块学习，使 条件下，给出了概念漂移程度的上界；Bave等[26]研 用了滑动窗口技术.这类算法通常假定最近获得的 究了在确保分类器泛化能力的条件下，数据流中相 训练样本与即将要采集的样本同分布.Street等Iu四 邻2个样本概念漂移的最大幅度；Wag等2给出 提出了SEA(streaming ensemble algorithm)算法，该 了使用带权多数投票进行概念漂移学习的理论证 算法根据一个预设的质量标准使用新分类器替代不 明；Kolter等0]证明了AddExp的错误率的界； 必要的旧分类器，而保持分类器总数不变，而实现对 Kuncheva等Iso]试图建立确定滑动窗口大小的理论 新概念的学习.然而当概念漂移突然发生时，体现新 根据，给出了分类错误率与滑动窗口大小的关系： 概念的分类器不足以跟旧分类器相抗衡，因此SEA Minku等1a,8]分析了分类器之间多样度(Diversity) 在一段时间内不能识别新概念.Wang等2]提出了 对概念漂移检测的影响

·98 智能系统学报 第8卷 3.3概念漂移的检测 提醒29)、电价预测29,31,39,4,52，，7201、TREC[32,3,921 检测概念漂移大致有3种方法：性能法、距离法 垃圾邮件过滤5s,,、Netflix电影等级数据集【®] 和性质法。 Yahoo购物数据，m)、邮件链表、集群计算机负 1)性能法.跟踪当前分类器对最新采集训练集 载均衡[3)、传感网数据4]、交通数据41、金融时间 的分类性能，如分类性能出现较大下降，这说明最新 序列5]、视听说话识别6]、可穿戴设备7]、航班延 采集训练集中包含有概念漂移.Widmer和Kubatis] 误2]和电影标注数据集52] 提出的LORA系列算法，根据分类器对正类样本覆 使用频率比较高的人工概念漂移数据集包括： 盖量以及分类准确率调整滑动窗口；Klinkenberg STAGCER数据集2,5,29,010,7，，m,M5、SEA数据 等[2]使用对训练集的分类准确率、训练集中某类的 集，，9,7，n,1、高斯数据，1,45、旋转平面 分类准确率和召回率(recall)来实施概念漂移检测， 数据集[4,8,3L,24,9,,6,769,31,56 以调整窗口大小；他们还通过估算各个滑动窗口上 另外，UCI中的一些数据集也常用于概念漂移 得到的支持向量机的泛化能力来确定滑动窗口的大 数据流分类[40,4243,4546,52,6162,6,72,7.21 小T64;Last等[3]提出了OLN,该算法通过比较分类 器在训练集与验证集上的错误率来判断是否产生了 4概念漂移数据流分类研究的新动态 概念漂移；Gama84)通过计算一个训练样本被错误 4.1 概念漂移数据流中的类别不平衡学习问题 分类的概率和其变化的范围来检测训练集中概，念漂 类别不平衡使得概念漂移数据流问题更加复 移的起点和终点；Nishida等[51使用分类器对最新 杂，因此直到最近学术界才开始关注这方面的研究， 采集训练样本的分类准确率和对全部训练样本的分 总的思路是将已有处理类别不平衡的算法加以改 类准确率来检测概念漂移；罗秀等]提出了基于误 进，以适应概念漂移数据流中的类别不平衡问题！ 差率的检测方法.性能法是最常用的概念漂移检测 Ga0等36研究了概念漂移数据流学习中的类别不 方法，但当数据流中存在类别不平衡时或只有部分 平衡问题，对最新采集训练集中的多类（样本数量 训练样本具有类别标志时，性能法将不适合用于概 多的类)样本采取多轮“下采样”，将所有已学习过 念漂移检测 的少类（样本数量少的类）样本和最新采集训练集 2)距离法.Katakis等7]将一个数据块映射成 中的少类样本合并成一个子集，然后将该子集分别 一个“概念向量”，然后对多个概念向量实施聚类， 与属于多类每轮“下采样”得到的子集合并训练分 由一个聚类代表一个概念.当采集到一个数据集时， 类器，以实现对最新采集样本集的集成学习；Chen 计算该数据集对应的概念向量与各个聚类中心的距 等[79]利用Mahalanobie距离从已学习过的所有少 离，以检测是否产生概念漂移.Katakis用该方法实 类样本中选择一部分样本与最新采集的不平衡样本 现了对重复概念的检测，但该方法有一个前提：一个 集合并，以减轻类别不平衡；Lichtenwalter等[o]对属 数据块中的各数据属于同一个概念。 于多类的样本进行下采样，将多类中被错误分类的 3)性质法.分析最近获得圳练集的一些统计特 样本与全部少类样本构成训练集；Gregory等[4]采 性：各类的分布、各特征值的分布等来实现对概念漂 用Gao采取的方法，实现对最新采集样本集的集成 移的检测.Alippi等[so利用中心极限定理，设计了 学习，然后通过修改Leam++NSE中的权值使其偏 不依赖数据分布模型的，不需要任何先验信息的概 向多类和少类的查全率，实现其与已训练好分类器 念漂移检测算法；Peter等91j提出了基于熵的概念 的集成：Zhang等2]将分类错误的少类样本加入训 漂移检测方法，通过一种熵的计算来评测训练集之 练集并使用F,值控制分类器更新频率.由于存在概 间样本分布的区别；Kuncheva2]在KL距离和T平 念漂移，这些方法都不能取得在数据分布不改变情 方测试的基础上通过假定数据服从组合正态分布导 形下类别不平衡学习算法所能达到的性能 出了SPLL概念漂移检测方法 4.2概念漂移数据流中的概念重复学习问题 3.4概念漂移数据流分类研究使用的数据集 Widmer比较早地注意到了概念会重复出 到目前为止，概念漂移数据流分类技术被用于 现5]，但是概念漂移数据流中的概念重复学习问题 以下实际问题的解决：Web数据B41、英国银行数 直到最近才得到学术界的广泛关注.Widmer等将已 据16、天气预报9、Reuters语料4,21、KDDCup数 经学习过的概念描述保存起来，当已学习过的概念 据0,0,58,9，刀、信用卡欺诈数据8、日程 重新出现时，保存的分类器被重新激活；Ramamur-

第2期 文益民，等：概念漂移数据流分类研究综述 99 thy4]提出将得到的分类器放到全局集中，当采集 定性策略以主动选择无类别标志样本，尽量使得主 到新数据块时，通过评测全局集中的分类器在新数 动标注的样本能体现概念漂移；Chu等s]提出了基 据块上的分类准确率来判断新到数据块是否属于新 于贝叶斯概率的在线主动学习算法，该算法利用重 概念，如果不是新概念则从全局集中挑选部分分类 要性采样方法实现对无类别标志样本的主动无偏选 器组成集成分类器去检测新到数据块是否属于原来 择，使得主动选择的样本符合当前概念的概率分布， 出现过的概念；Katakis]将一个数据块转化成一个 以上这些算法或使用半监督学习策略尽量发挥 概念向量，然后通过数据流聚类方法将不断到来的 没有类别标志样本的作用，或使用主动学习策略选 数据块聚类成多个概念向量的集合，每个概念向量 择能体现概念漂移的样本进行标注，但半监督学习 的集合通过增量学习得到一个分类器，最新采集数 和主动学习并没有很好地结合起来.Kholghi4]提出 据块用于最近获得的训练集所属概念相对应的分类 了一个将半监督和主动学习相结合进行概念漂移数 器分类；L等4提出了通过概念聚类，形成概念列 据流分类的算法框架， 表的方式检测新到样本是否是属于已有概念；Ma- ud等45]使用主集成和辅集成来检测新到样本是否 5存在的问题 属于已学习概念.以上这些算法主要的不足在于数 通过以上分析发现，已有的各种概念漂移数据 据块的大小不容易确定（太大可能包含多个概念， 流学习算法在处理概念漂移数据流分类时存在以下 太小则数据的分布不够体现概念本身) 5个方面的问题： 4.3概念漂移数据流中的半监督学习与主动学习 1)冷启动.由于在一段时间里概念漂移的次数 问题 无法预知，学习系统只有在发生分类错误后才能得 Klinkenberg32]较早地关注到了概念漂移数据 到调整，这导致了属于新概念的样本在刚开始出现 流分类中的半监督学习问题.在假定当前最新训练 时被错误分类.而且在只有部分样本具有类别标志 集与最新测试集同分布的条件下，他提出使用没有 的情形下，学习系统将很难知道是否产生了错误分 类别标志的样本估计滑动窗口的大小；Xue等6]针 类.如果将这样的分类器应用于工业流水线生产，将 对某类的先验概率发生变化以及最新采集的训练样 带来巨大的损失， 本无类别标志的情形，探讨了如何利用无类别标志 2)只能实施单概念学习.目前主要使用滑动窗 样本估计各类别样本的数量及实施半监督学习； 口、训练样本赋权、分类器自适应调整等方法实现对 Z☑hang等提出了RK-TS3VM算法，该算法根据最 新概念的学习，这些方法只能跟踪学习一个概念，这 新采集训练集中的样本是否具有类别标志和是否产 导致了已学习知识难以保特.由于某些概念不定期 生了概念漂移而分为4个子集，然后根据子集的特 重复出现，其产生的时刻和延续时间未知，导致现有 点选择TS3VM或RK算法实现学习和分类；Li 的单概念学习模式无法适应.对概念漂移中重复概 等[1提出了SUN算法，该算法使用基于k-Modes的 念的关注说明多概念学习问题刚得开始到学术界的 聚类方法来实现无类别标志样本的标注和重用，进 关注。 而使用概念聚类方法实现概念漂移检测， 3)概念漂移检测难以准确实施.现有的各种概 Fan等[9]提出了不需要事先获得样本类别标 念漂移算法主要依靠最近获得的训练样本集.且当 志就可以计算的2个检测概念漂移的指标：基于叶 最近获得的训练样本集中存在类别不平衡时会导致 子节点的分布统计指标以及验证错误率与期望错误 对少类的忽视：当其中只有部分样本具有类别标志 率的差，当检测到概念漂移后，根据样本类别标注代 时已有概念漂移检测方法将无法实施： 价，选择性地给出一部分样本的类别标志；Zu 4)最新采集样本与最近获得圳练样本同分布 等0选择使得集成分类器能产生最大方差的不确 的假设不正确.从某一时刻开始最新采集样本中可 定样本，给出类别标志，并通过分类器的加权集成， 能包含有跟最近获得训练样本不同分布的新概念， 使得集成分类器能适应概念漂移；Masud等51]使用 甚至既包含属于新概念的样本又包含属于旧概念的 主动学习策略，去分辨数据流中是否产生了新的类 样本.如果最新采集样本与最近获得训练样本总是 别以及挑选需要标注的样本；Zliobaite等[52]针对概 不同分布，现有概念漂移学习算法将无法实施 念漂移发生的位置有的在分类面附近而有的远离分 5)理论基础研究缺乏·尽管概念漂移数据流研 类面的特点，提出了可变不确定性策略和随机不确 究已经取得丰硕的研究成果，然而到目前为止，概念

·100 智能系统学报 第8卷 漂移的定义、概念漂移的速度与幅度、概念漂移数据 data challenges in the 21st century[J].Science,2011, 流分类器的错误率的界、概念的容量、概念漂移检测 331(6018):700-702 等都还没有得到严格的数学描述，已取得的一些理 [11]STREET W N,KIM Y S.A streaming ensemble algorithm 论上的结果也有待验证和深化， (SEA)for large-scale classification [C]//Proceedings of the Seventh International Conference on Knowledge Discov- 6结束语 ery and Data Mining.San Francisco,USA,2001:377 382. 概念漂移数据流分类给机器学习带来了巨大的 [12]ANGLUIN D.Queries and concept leamning[J].Machine 挑战，本论文从数据流与概念漂移、概念漂移数据流 Learning,1988,2(4):319-342. 分类研究的发展与趋势、概念漂移数据流分类的主 [13 DOMINGOS P,HULTEN G.Mining high-speed data 要研究领域、概念漂移数据流分类研究的新动态4 stream[C]//Proceedings of the Sixth ACM SIGKDD In- 个方面分析总结了学者们在概念漂移数据流分类问 ternational Conference on Knowledge Discovery and Data 题上杰出的研究工作，并分析了当前概念漂移数据 Mining.Boston,USA,2000:71-80. 流分类存在的问题.尽管概念漂移数据流分类已经 [14]HULTEN G,SPENCER L,DOMINGOS P.Mining time- 取得了丰硕的研究成果，且已经成为机器学习研究 changing data streams[C]//Proceedings of the Seventh ACM SIGKDD Intemational Conference on Knowledge Dis- 的热点之一，然而其研究远还没有成熟，还存在着众 covery and Data Mining.San Francisco,USA,2001:97- 多挑战，期待着学术界能有更大的突破： 106. 参考文献： [15 WIDMER G,KUBAT M.Effective learning in dynamic environments by explicit context tracking[C]//Proceed- [1]MITCHELL T M.Machine learning M ]New York: ings of the Sixth European Conference on Machine Leam- McGraw-Hill,1997:15-37. ing.Vienna,Austria,1993:69-101. [2]SCHLIMMER J,GRANGER R.Incremental learning from [16]KELLY M,HAND D,ADAMS N.The impact of changing noisy data[J].Machine Learning,1986,1(3):317-354. populations on classifier performance[C]//Proceedings of [3]GROSSBERG S.Nonlinear neural networks:principles, the Fifth Interational Conference on Knowledge Discovery mechanisms and architecture[J].Neural Network,1988, and Data Mining.San Diego,USA,1999:367-371. 1(1):1761. [17]NARASIMHAMURTHY A,KUNCHEVA L I.A frame- [4]KUNCHEVA L I.Classifier ensembles for changing environ- work for generating data to simulate changing environments ments[C]//Proceedings of the Fifth Workshop on Multiple [C]//Proceedings of the 25th IASTED International Classifier Systems.Cagliari,Italy,2004:1-15 Multi-Conference:Artificial Intelligence and Applications. [5]TSYMBAL A.The problem of concept drift:definitions and Innsbruck,Austria,2007:384-389. related work.TCD-CS-2004-15[R].Dublin:Department [18]MINKU LL,WHITE A P,YAO X.The impact of diversi- of Computer Science Trinity College,2004. ty on online ensemble learning in the presence of concept [6]王涛，李舟军，颜跃进，等。数据流挖掘分类技术综述 drift[J].IEEE Transactions on Knowledge and Data Engi- [J].计算机研究与发展，2007,44(11)：1809-1815. neering,2010,22(5):730-742. WANG Tao,LI Zhoujun,YAN Yuejin,et al.A survey of [19]ELWELL R,POLIKAR R.Incremental leaming of concept classification of data streams[J].Journal of Computer Re- drift in nonstationary environments[J].IEEE Transactions search and Development,2007,44(11):1809-1815. on Neural Networks,2011,22(10):1517-1531. [7]ZLIOBAITE I.Learing under concept drift:an overview [20]MASUD M,GAO J,KHAN L,et al.Integrating novel [EB/OL].[2012-01-12 ]http://zliobaite.googlepages. class detection with classification for concept-drifting data com/Zliobaite_CDoverview.pdf. streams[C]//Proceedings of the European Conference on [8]HOENS T R,POLIKAR R,CHAWLA N V.Learning from Machine Learning and Knowledge Discovery in Databases. streaming data with concept drift and imbalance:an over- Bled,Slovenia,2009:79-94. view[J].Progress in Artificial Intelligence,2012,1(1): 21 MORENO-TORRES J G.RAEDER T,ALAIZ-RODRIGU- 89-101. EZ R.A unifying view on dataset shift in classification [9]GAMA J.A survey on learning from data streams:current [J].Pattemn Recognition,2012,45:521-530. and future trends[J].Progress in Artificial Intelligence, [22]KILANDER F,JANSSON C.COBBIT-a control proce- 2012,1(1):45-55, dure for COBWEB in the presence of concept drift[C]/ [10]OVERPECK J T,MEEHL G A,BONY S,et al.Climate Proceedings of the Sixth European Conference on Machine

第2期 文益民，等：概念漂移数据流分类研究综述 ·101· Learning.Helsinki,Finland,1993:244-261. 1999:41-48. [23]BLACK M,HICKEY R J.Maintaining the performance of [35]KUBAT G,GAMA J,UTGOFF P.Special issue on incre- a learned classifier under concept drift[J].Intelligent Da mental learning systems capable of dealing with concept ta Analys3is,1999,3(6):453474. drift[Z].Amsterdam:Intelligent Data Analysis,2004. [24]KUN A,PETSCHE T,RIVEST R L.Learning time-var- [36]GAO J,DING B,FAN W,et al.Classifying data stream ying concepts[C]//Proceedings of the Conference Neural with skewed class distributions and concept drifts J]. Information Processing Systems.Denver,USA,1990: IEEE Transactions on Internet Computing,2008,12(6): 3749. 183-189. [37]CHEN S,HE H.SERA:selectively recursive approach to- [25]HELMBOLD D P,LONG P M.Tracking drifting concepts wards nonstationary imbalanced stream data mining[C]// by minimizing disagreements [J].Machine Learning, Proceedings of the 2009 International Joint Conference on 1994,14(1):27-45. Neural Networks.Atlanta,USA,2009:522-529. [26]BARVE R D,LONG P M.On the complexity of leaming [38]CHEN S,HE H,LI K,et al.MuSeRA:multiple selec- from drifting distributions C]//Proceedings of the Ninth tively recursive approach towards nonstationary imbalanced Annual Conference on Computational Leaming Theory. stream data mining[C]//Proceedings of the 2010 Intera- Desenzano Sul Garda,Italy,1996:122-130. tional Joint Conference on Neural Networks.Barcelona. [27]DIETTERICH T,WIDMER G,KUBAT M.Special issue Spain,2010:18. on context sensitivity and concept drift[J].Machine [39]CHEN S,HE H.Towards incremental learning of nonsta- Learning,1998,32(2):83-201. tionary imbalanced data stream:a multiple selectively re- [28]WANG H,FAN W,YU P S,et al.Mining concept-drif- cursive approach[J].Evolving Systems,2010,2(1):35- ting data streams using ensemble classifiers[C]//Proceed- 50. ings of the Ninth International Conference on Knowledge [40]LICHTENWALTER R N,CHAWLA N V.Adaptive meth- Discovery and Data Mining.Washington,DC,USA, ods for classification in arbitrarily imbalanced and drifting 2003:226-235. data streams C]//Proceedings of the 13th Pacific-Asia [29]KOLTER J Z,MALOOF M A.Dynamic weighted majori- Conference on Knowledge Discovery and Data Mining. Bangkok,Thailand,2009:53-75. ty:a new ensemble method for tracking concept drift [41]GREGORY D,ROBI P.An ensemble based incremental [C]//Proceedings of the Third IEEE International Confer- leamning framework for concept drift and class imbalance ence on Data Mining.Washington,DC,USA,2003:123- [C]//Proceedings of the 2010 International Joint Confer- 130. ence on Neural Networks.Barcelona,Spain,2010:9-17. [30]KOLTER J Z,MALOOF M A.Using additive expert en- [42]ZHANG J,HU X,ZHANG Y,et al.An efficient ensem- sembles to cope with concept drift[C]//Proceedings of the ble method for classifying skewed data streams[C]//Pro- 22nd International Conference on Machine Learning. ceedings of the 7th International Conference on Intelligent Bonn,Germany,2005:449-456. Computing.Zhengzhou,China,2011:144-151. [31]BIFET A,HOLMES G,PFAHRINGER B,et al.New en- [43 RAMAMURTHY S,BHATNAGAR R.Tracking recurrent semble methods for evolving data streams[C]//Proceed- concept drift in streaming data using ensemble classifiers ings of the 15th ACM SIGKDD International Conference on [C]//Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining.Paris,France, Machine Learing and Applications.Cincinnati,USA, 2009:139-148. 2007:404409. [32]KLINKENBERG R.Using labeled and unlabeled data to [44]LI PP,WU X D,HU X G.Mining recurring concept learning drifting concepts[C]//Proceedings of the Work- drifts with limited labeled streaming data[C]//Proceed- shop Notes of the IJCAI-01 Workshop on Learning from ings of the 2th Asian Conference on Machine Learning.To- Temporal and Spatial Data.Menlo Park,USA 2001:16- kyo,Japan,2010:241-252. 24. [45 ]MASUD MM,AL-KHATEEB T M,KHAN L,et al.De- [33]KLINKENBERG R.Detection concept drift with support tecting recurring and novel classes in concept-drifting data vector machines[C]//Proceedings of the Seventeenth In- streams[C]//Proceedings of the 2011 International Con- temational Conference on Machine Learning.Stanford, ference on Data Mining.Vancouver,Canada,2011:1176- California,USA,2000:487-494. 1181. [34 LANQUILLON C.Information filtering in changing do- [46]XUE J C,WEISS G M.Quantification and semi-super- mains[C]//Proceedings of the 16th International Joint vised classification methods for handling changes in class Conference on Artificial Intelligence.Stockholm,Sweden, distribution[C]//Proceedings of the 15th ACM SIGKDD

·102· 智能系统学报 第8卷 International Conference on Knowledge Discovery and Data [59]WENERSTROM B,GIRAUD-CARRIER C.Temporal data Mining.Paris,France,2009:897-906. mining in dynamic feature spaces[C]//Proceedings of the [47]ZHANG P,ZHU X,GUO L.Mining data streams with la- 2006 International Conference on Data Mining.Las Vegas, beled and unlabeled training examples[C]//Proceedings USA,2006:1141-1145. of the Ninth IEEE International Conference on Data Min- [60 ]CHEN H L,CHEN M S,LIN S C.Catching the trend:a ing.Miami,USA,2009:627-636. framework for clustering concept-drifting categorical data [48 ]LI P,WU X D,HU X G.Learning from concept drift data [J].IEEE Transactions on Knowledge and Data Engineer- streams with unlabeled data C//Proceedings of the 24th ing,2009,21(5):652665. AAAI Conference on Artificial Intelligence.Atlanta,USA, [61]MASUD M,GAO J,KHAN L.et al.Classification and 2010:1945-1946. novel class detection in concept-drifting data streams under [49]FAN W,HUANG Y,WANG H,et al.Active mining of time constraints[J].IEEE Transactions on Knowledge and data streams[C]//Proceedings of the 4th SIAM Interna- Data Engineering,2011,23(6):859-874. tional Conference on Data Mining.Lake Buena Vista, [62]ZHANG P,LI J,WANG P,et al.Enabling fast prediction USA,2004:457461. for ensemble models on data streams[C]//Proceedings of [50]ZHU X,ZHANG P,LIN X.Active learning from stream the 17th ACM SIGKDD Interational Conference on Knowl- data using optimal weight classifier ensemble[J].IEEE edge Discovery and Data Mining.San Diego,USA,2011: Transactions on Systems,Man,and Cybernetics,Part B: 177-185. Cybernetics,2010,40(6):1607-1621. [63 KOREN Y.Collaborative filtering with temporal dynamics [51 MASUD M,GAO J,KHAN L,et al.Classification and [J].Communications of the ACM,2010,53(4):89-97. novel class detection in data streams with active mining [64 ]KLINKENBERG R,JOACHIMS T.Detecting concept drift [C]//Proceedings of the 14th Pacific-Asia Conference on with support vector machines[C]//Proceedings of the 17th Knowledge Discovery and Data Mining.Hyderabad,Indi- International Conference on Machine Learning.San Fran- a,2010:311-324. cisc0,USA,2000:487494. 52]ZLIOBAITE I,BIFET A,PFAHRINGER B,et al.Active [65]WIDMER G,KUBAT M.Learing in the presence of con- learning with evolving streaming data[C]//Proceedings of cept drift and hidden contexts[J].Machine Leaming, the European Conference on Machine Leaming and Princi- 1996,23(1):69-101. ples and Practice of Knowledge Discovery in Databases. [66]FAN W.Systematic data selection to mine concept-drifting Athens,Greece,2011,11:597-612. data streams C]//Proceedings of the Tenth International 53]CHU W,ZINKEVICH M,LI L,et al.Unbiased online Conference on Knowledge Discovery and Data Mining.Se active learing in data streams[C]//Proceedings of the attle,USA,2004:128-137. 17th ACM SIGKDD International Conference on Knowledge [67]SALGANICOFF M.Tolerating concept and sampling shift Discovery and Data Mining.San Diego,USA,2011:195- in lazy learning using prediction error context switching 203. [J].Artificial Intelligence Review,1997,11(1/2/3/4/ [54 KHOLGHI M,KEYVANPOUR M R.Active learing 5):133-155. framework combining semi-supervised approach for data [68]ZLIOBAITE I.Combining similarity in time and space for stream mining[].Intelligent Computing and Information training set formation under concept drift[J].Intelligent Science,2011,135:238-243. Data Analysis,2011,15(4):589611. 55]FORMAN G.Tackling concept drift by temporal inductive [69]KLINKENBERG R.Learning drifting concepts:example transfer[C]//Proceedings of the 29th Annual International selection vs.example weighting[J].Intelligent Data A- ACM SIGIR Conference on Research and Development in nalysi9,2004,8(3):200-281. Information Retrieval.Toronto,Canada,2006:252-259. [70]KOYCHEV I.Gradual forgetting for adaption to concept [56]BEN D S,BORBELY R S.A notion of task relatedness drift[C]//Proceedings of the ECAI 2000 Workshop Cur- yielding provable multiple-task leaming guarantees[J]. rent Issue in Spatio-Temporal Reasoning.Berlin,Germa- Machine Learning,2008,73(3):273-287. y,2000:101-106. [57]FOLINO G,PAPUZZO G.Handling different categories of [71]00MMEN J,RUEDA L.Stochastic leaming-based weak concept drifts in data streams using distributed GP[C]/ estimation of multinomial random variables and its applica- Berlin:Springer-Verlag,2010:74-85. tions to pattern recognition in non-stationary environments 58]YANG S,YAO X.Population-based incremental learning [J].Pattern Recognition,2006,39(3):328-341. with associative memory for dynamic environments[J. [72 ]NUNEZ M,FIDALGO R,MORALES R.Leaming in en- IEEE Transactions on Evolutionary Computation,2008,12 vironments with unknown dynamics towards more robust (5):542561. concept learners[J].Journal of Machine Learning Re-

第2期 文益民，等：概念漂移数据流分类研究综述 ·103· search,2007,8:2595-2628. ceedings of the Workshop of the AAAI-98/ICML-98 on [73]KYOSUKE N,KOICHIRO Y,TAKASHI O.ACE:adap- Learning for Text Categorization.Madison,USA,1998: tive classifier-ensemble system for concept-drifting environ- 33-40. ments[C]//Proceedings of the 6th International Workshop [83 LAST M.Online classification of nonstationary data on Multiple Classifier Systems.Heidelberg,Germany, streams [J].Intelligent Data Analysis,2002,6 (2):1- 2005:176-185. 16. [74]MUHLBAIER M D,POLIKAR R.Multiple classifiers [84 ]GAMA J,MEDAS P,CASTILLO G,et al.Leaming with based incremental leaming algorithm for leaming in non- drift detection[C]//Proceedings of the 17th Brazilian Sym- stationary environments[C]//Proceedings of the 6th IEEE posium on Artificial Intelligence.Sao Lufs,Brazil,2004: Interational Conference on Machine Learning and Cyber- 286-295. netics.Hong Kong,China,2007:3618-3623. [85 NISHIDA K,YAMAUCHI K.Detecting concept drift u- [75]文益民，王耀南，张莹.基于可信多数投票的快速概念 sing statistical testing[C]//Proceedings of the 10th Inter- 漂移检测[J].湖南大学学报：自然科学版，2010,37 national Conference on Discovery Science.Sendai,Japan, (6):3640. 2007:264-269. WEN Yimin,WANG Yaonan,ZHANG Ying.Fast detec- [86]罗秀，王大玲，冯时，等.一种面向周期性概念漂移的 tion of concept drifts based on confident majority voting 数据流分类算法[J].计算机研究与发展，2009,46 J].Joumal of Hunan University:Natural Sciences, (Suppl):400-405. 2010,37(6):3640. LUO Xiu,WANG Daling,FENG Shi,et al.An algorithm [76]关菁华，刘大有.一种挖掘概念漂移数据流的选择性 for classifying data stream with recurrent concept drift[J. 集成算法[J].计算机科学，2010,37(1)：204207. Journal of Computer Research and Development,2009,46 GUAN Jinghua,LIU Dayou.Selected ensemble of classifi- (Suppl.):400405, ers for handling concept-drifting data streams[J.Comput- [87]KATAKIS I,TSOUMAKAS G,VLAHAVAS I.Tracking er Science,2010,37(1):204-207. recurring contexts using ensemble classifiers:an applica- [77]朱群，张玉红，胡学钢，等.一种基于双层窗口的概念 tion to email filtering[J].Knowledge and Information Sys- 漂移数据流分类算法[J].自动化学报，2011,37(9)： tem3,2010,22(3):371-391. 1078-1083 [88]ALIPPI C,ROVERI M.Just-in-time adaptive classifiers- ZHU Qun,ZHANG Yuhong,HU Xuegang,et al.A doub- part I:detecting nonstationary changes[J].IEEE Transac- le-window-based classification algorithm for concept drifting tions on Neural Networks,2008,19(7):1145-1153. data streams[J].Acta Automatica Sinica,2011,37(9): [89]ALIPPI C,ROVERI M.Just-in-time adaptive classifiers- 1078-1083. patⅡ：designing the classifier[J】].EEE Transactions on [78]孙岳，毛国君，刘旭，等.基于多分类器的数据流中的 Neural Networks,2008,19(12):2053-2064. 概念漂移挖掘[J].自动化学报，2008,34(1)：9397. [90]ALIPPI C,BORACCHI G,ROVERI M.An effective just- SUN Yue,MAO Guojun,LIU Xu,et al.Mining concept in-time adaptive classifier for gradual concept drifts[C]// drifts from data streams based on multi-classifiers[J].Ac- Proceedings of the 2011 Intemational Joint Conference on ta Automatica Sinica,2008,34(1):93-97. Neural Networks.San Jose,USA,2011:1675-1681. [79]辛轶，郭躬德，陈黎飞，等.KnnM-DHecoc:一种解决 [91]PETER V,ABRANHAM B.Entropy-based concept drift 概念漂移问题的算法[J].计算机研究与发展，2011， detection[C]//Proceedings of the 6th International Con- 48(4):592601. ference on Data Mining.Hong Kong,China,2006:1113- XIN Yi,GUO Gongde,CHEN Lifei,et al.IKnnM-DHe- 1118. coc:a method for handling the problem of concept drift [92]KUNCHEVA L.Change detection in streaming multivariate [J].Journal of Computer Research and Development, data using likelihood detectors[J].IEEE Transactions on 2011,48(4):592601. Knowledge and Data Engineering,2007,6(1):1-7. [80]KUNCHEVA L I,ZLIOBAITE I.On the window size for [93 ]KUBAT M.To load balancing in computer networks[J]. classification in changing environments[J].Intelligent Da- International Joural of Cybernetics and System,1992,23 ta Analysis,2009,13(6):314-323. (3/4):389400. 81]MINKU LL,YAO X.DDD:a new ensemble approach for [94]COHEN L,AVRAHAMI-BAKISH G,LAST M,et al.Re- dealing with concept drift [J].IEEE Transactions on al-time data mining of non-stationary data streams from Knowledge and Data Engineering,2012,24 (4):619- sensor networks J].Information Fusion,2008,9(3): 633. 344-353. [82]KLINKENBERG R,RENZ I.Adaptive information filte- [95 HARRIES M,HORN K.Detecting concept drift in finan- ring:learning in the presence of concept drifts[C//Pro- cial time series prediction using symbolic machine learning