第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-