1、97407154本专科电子信息科学与技术天津师范大学数据流中概念漂移检测与分类方法研究数据流中概念漂移检测与分类方法研究摘要由于现有各种机器学习算法本质上都是基于一个静态学习环境而以尽量保证学习系统泛化能力为目标的一个寻优过程，概念漂移数据流分类给机器学习带来了巨大挑战。从数据流与概念漂移、概念漂移数据流分类研究的发展与趋势、概念漂移数据流分类的主要研究领域、概念漂移数据流分类研究的新动态四个方面展开了分析，并分析了当前概念漂移数据流分类算法存在的问题。关键词：大数据；概念漂移；增量学习；适应学习；数据流目 录引言 11 数据流与概念漂移 22 概念漂移数据流分类研究的发展与趋势 43 概念漂
2、移数据流分类的主要研究方法 53.1 概念漂移数据流学习器的构建 53.2 概念漂移数据流学习理论的研究 73.3 概念漂移的检测 83.4 概念漂移数据流分类研究使用的数据集 94 概念漂移数据流分类研究的新动态 104.1概念漂移数据流中的类别不平衡学习问题 104.2 概念漂移数据流中的概念重复学习问题 114.3 概念漂移数据流中的半监督学习与主动学习问题 115 存在的问题 136 结束语 14参考文献 15引言在社会生产和生活实践中，有一类问题是数据所包含的概念1可能随时间而变化。自动化生产线上，相近原因的问题产品会连续出现，然后问题产品的特征也随之发生变化；商务活动中，顾客的购买
3、兴趣随时间而变化；网络安全中，网络的访问模式随用户不同而变化；社交媒体上，用户的实际行为随其注册位置而变化。这些问题的共同特点是：不断产生的数据形成流；数据流没有终点；数据流中数据包含的概念随时可能产生变化。数据流中这种概念的变化在本文中被称为概念漂移2。概念漂移要求学习系统能尽早地检测到概念漂移，并对自身进行适应概念漂移的调整，以对不断到来的数据尽可能地正确判断。概念漂移问题给机器学习带来了巨大的挑战。目前各种人工学习系统的构造算法在本质上都是基于一个静态学习环境而以尽量保证学习系统泛化能力为目标的一个寻优过程，所以现有各种机器学习算法本质上都不适应进行概念漂移数据流学习。这种不适应体现在：
4、计算模型或者缺乏获取新知识的能力，或者不能保持原本学到的知识3。自“概念漂移”(concept drift)在1986年由Schlimmer和Granger首次提出后2，国内外众多研究人员对概念漂移数据流分类展开了深入研究。Kuncheva4、Tsymbal5、王涛6、Zliobaite7 、Hoens8 和Gama9等先后从各自角度对概念漂移数据流分类研究进行了很好的文献综述。与已上这些综述相比，本综述具有如下特色之处：剖析了概念漂移数据流分类研究产生并发展的脉络；包含了概念漂移数据流分类的最新研究动向概念漂移数据流分类中的类别不平衡学习、重复概念学习及半监督学习和主动学习问题；深入分析了当
5、前概念漂移数据流分类算法存在的问题。考虑到概念漂移数据流分类研究的文献量很大，本文将从数据流与概念漂移、概念漂移数据流分类研究的发展与趋势、概念漂移数据流分类的主要研究领域、概念漂移数据流分类研究的新动态等四个方面展开文献分析和整理，试图总结概念漂移数据流分类已有的研究成果，把握其研究展开的脉络，分析其存在的问题。1 数据流与概念漂移数据流分类问题引起研究人员关注的原因主要有两个：一是因为自动数据获取技术的飞速发展使得人类获得了大量的数据。数据量太大时，数据不能被一次性装入内存；二是由于传感器技术的发展使得人类获得了大量与时间和环境相关的数据10。Gama9和Street11讨论了数据流分类问
6、题的特点：顺序处理、单向通过、内存有限等。数据流分类通常被描述为在线分类模型12也就是分类器每次只对一个样本分类，在完成对该样本的分类后，分类器将得到由专家给出的该样本的真实类别；该样本及其类别标志被用于分类器更新；当分类器完成更新后，将对下一个接收到的样本实施分类。在线分类模型通常又被扩展为分类器每次分类或学习一批样本。数据流分为两种：一种是数据源产生的数据独立同分布，研究人员称为稳定数据流13；另一种是数据源产生的数据不独立同分布，研究人员认为在数据产生过程中发生了“概念漂移”2，称其为动态数据流14。研究人员对概念漂移的深入理解是通过分析概念漂移的种类及产生的原因逐步得到的。Widmer
7、等认为数据产生环境的变化导致了概念漂移，并将概念漂移区分为虚概念漂移和实概念漂移15；Kelly认为概念漂移是样本与其类别的联合概率随时间变化而产生，其产生原因分三种：一是某类的先验概率发生变化；二是某类的类概率发生变化；三是样本后验概率发生变化16；Kuncheva引用时间序列分析方法将概念漂移分为四种：随机噪声、随机趋势、随机替换、系统趋势4。其中，随机趋势中包含渐变性概念漂移，随机替换中包含突变性概念漂移，系统趋势中包含着重复性概念漂移；Narasimhamurthy等根据数据产生的多源性提出了概念漂移的产生模型17； Zliobaite把概念漂移分为四种：突变性概念漂移、渐变性概念漂移
8、、增量性概念漂移、重复性概念漂移7。Minku等在总结他人工作的基础上，选择了纯度、速度、可预测度、频度、重复度五个维度，将概念漂移分成14种18。对数据流中增加了类别的情形，学术界还没有达成一致认识有人认为是一种概念漂移19，有人则认为属于概念进化20。总的来讲，学术界对概念漂移的认识日渐清晰，但目前还缺少对概念漂移的统一描述。Moreno-Torres等试图利用数据漂移（Data Shift）的概念来统一已有各种概念漂移的描述21。2 概念漂移数据流分类研究的发展与趋势自“概念漂移”在1986年由Schlimmer和Granger首次提出后2，概念漂移得到了学术界的日益重视。STAGGER
9、是他们首次提出的解决概念漂移问题的算法。从1986年到2000年左右这段时间的研究主要围绕单分类器展开使用单个分类器实现概念漂移数据流分类。Kilander等提出了COBBIT22；Widmer 和Kubat提出了FLORA15；Hulten等提出了CVFDT14；Black等提出了CD323；同时研究人员开始关注概念漂移数据流分类的理论问题24-26。为深入探讨数据产生的情境（context）与概念漂移的关系，1998年由Dietterich、Widmer和Kubat发起由Machine Learning出版了研究概念漂移数据流的专刊27。由于使用单分类器处理概念漂移数据流时需要不断更新分类
10、模型且分类器泛化能力不高，Street等首次将集成学习引入概念漂移数据流分类提出了SEA算法11。因此，从2000年左右开始，研究人员对概念漂移数据流分类的研究开始转移到分类器集成上来。通过多分类器集成，实现对历史样本的选择，提高分类器泛化能力。Wang等提出的AWE28、Kolter等提出的DWM和AddExp29,30和Bifet等提出的ADWIN和ASHT31是这个领域里非常有影响的工作。大约从2000年开始，概念漂移数据流分类研究进入了快速发展期，研究人员开始考虑更加接近实际状况的概念漂移数据流。Klinkenberg和 Lanquillon比较早地研究了在检测概念漂移时只有部分样本获
11、得用户反馈或者没有反馈的情形32-34。2004年由Intelligent Data Analysis期刊出版的概念漂移数据流专刊35主要探讨了如何利用增量学习方法以较小的代价使已有分类器适应概念漂移；之后概念漂移数据流分类中的类别不平衡学习79-85、概念重复学习86-88、半监督学习89-91、主动学习92-97等问题开始得到较多关注。2010年IOS还出版了Adaptive Stream Mining: Pattern Learning and Mining from Evolving Data Streams。从近年机器学习与数据挖掘领域的一些国际权威期刊和国际顶级会议上发表的论文来看
12、，概念漂移数据流分类的研究正日益成为学术界关注的焦点，对概念漂移数据流的研究已经开始与转移学习36,37、进化计算38,39、特征选择40、聚类41、时间复杂度分析42,43、社会计算44等结合起来。由于运动是物质的本质，概念漂移也是数据的本质。因此，从趋势上来讲，已有各种模式分类的理论和算法都可与概念漂移相结合而引出更多新的研究问题。3 概念漂移数据流分类的主要研究方法3.1 概念漂移数据流学习器的构建对已有各种学习器进行调整使之适应概念漂移数据流学习是目前主要的研究方向。这些算法可分为两类：一类通过单分类器实现，另一类通过多分类器集成实现。利用单分类器进行概念漂移数据流学习的方法有四种：选
13、择训练样本该类方法的主要思路是从开始到目前为止采集的训练样本中选择一部分最合适对未来数据实施准确分类的样本训练分类器，其主要做法有滑动窗口法、自适应滑动窗口调整法45-47以及动态样本选择法48，49；给训练样本赋以权值该类方法的主要思路是对最新的训练样本赋以最大的权值，以提高对新概念的反应速度50-52；调整学习器的结构该类方法的特点是动态调整分类器的内部结构，以适应概念漂移检测的要求。Hulten等提出的CVFT14用适合新概念的子树替换旧子树；Nunez等提出了OlineTree2，该算法中决策树的每个叶子节点都维护一个时间窗口和局部性能测度，当测度下降时，时间窗口将减小53；第四种是各
14、种方法的组合614。多分类器集成是机器学习的研究热点之一。国内外学者在利用集成学习策略实施概念漂移数据流学习方面已经做了许多探索，具体的研究内容主要分两个方面：一是利用集成学习策略对数据流实施分块学习；二是基于在线学习模型对整个数据流实施集成学习所有基分类器采用相同的学习算法，它们各自的训练样本来自同一数据流。利用集成学习策略对数据流实施分块学习，使用了滑动窗口技术。这类算法通常假定最近获得的训练样本与即将要采集的样本同分布。Street等提出了SEA算法11，该算法根据一个预设的质量标准使用新分类器替代不必要的旧分类器而保持分类器总数不变而实现对新概念的学习。然而当概念漂移突然发生时，体现新
15、概念的分类器不足以跟旧分类器相抗衡，因此SEA在一段时间内不能识别新概念；Wang等提出了一个类似SEA的AWE算法28，该算法根据最新采集的训练样本集计算各基分类器的权值；Kyosuke提出了ACE算法54，该算法在集成分类器的基础上增加了一个能进行在线学习的分类器，以提高算法对概念漂移的反应速度； Muhlbaier等提出了Learn+.NSE1955，该算法根据已训练基分类器和集成分类器在最新采集训练样本集上的分类性能来调整各样本对应的权值和各基分类器的权值；文益民等提出了基于分类置信度的概念漂移检测方法56，根据分类置信度实现分类器的选择集成，使得集成分类器能快速适应新概念；关菁华等提
16、出了一种选择性集成方法57，该算法根据各基分类器在验证数据集上的输出结果与参考向量之间的角度来选择参与集成的分类器；朱群等提出了一种基于双层窗口方法58，该算法将滑动窗口分解成多个基本窗口，以基本窗口为单位进行概念漂移检测。以上这些算法还有一个共同点是假定一个数据块中没有概念漂移，因此需要事先了解数据流的结构。基于在线学习模型对整个数据流实施集成学习的思路与Adaboosting算法的思路类似。Kolter等提出了基于动态带权多数投票（DWM）的学习算法29和AddExp30，该算法能根据集成分类器的分类性能动态地增加或者删除基分类器；孙岳等提出了一种基于多分类器的概念漂移挖掘算法59，该算法
17、的思路与AddExp类似，只是基分类器的权值设置不同；辛轶等提出了IKnnM-DHecoc算法60，该算法根据新到样本的概念漂移度调整编码矩阵，然后根据调整后的编码矩阵更新训练基分类器。3.2 概念漂移数据流学习理论的研究概念漂移数据学习理论主要是基于在线学习模型展开研究。Kun给出了在前一个概念是可能近似正确学习（PAC）的条件下，实现对下个概念的PAC学习所需的最多样本数的上界24；Helmbold等在稳定渐变概念漂移和确保对未来样本错误率下界的条件下，给出了概念漂移程度的上界25；Barve等研究了在确保分类器泛化能力的条件下，数据流中相邻两个样本概念漂移的最大幅度26；Wang等给出了
18、使用带权多数投票进行概念漂移学习的理论证明28；Kolter等证明了AddExp的错误率的界30；Kuncheva等试图建立确定滑动窗口大小的理论根据，给出了分类错误率与滑动窗口大小的关系61；Minku等分析了分类器之间多样度（Diversity）对概念漂移检测的影响1862。3.3 概念漂移的检测检测概念漂移大致有三种方法：性能法、距离法、性质法。性能法跟踪当前分类器对最新采集训练集的分类性能，如分类性能出现较大下降，这说明最新采集训练集中包含有概念漂移。Widmer和Kubat提出的FLORA系列算法，根据分类器对正类样本覆盖量以及分类准确率调整滑动窗口15；Klinkenberg等使用
19、对训练集的分类准确率、对训练集中某类的分类准确率和召回率（recall）来实施概念漂移检测，以调整窗口大小63；他们还通过估算各个滑动窗口上得到的支持向量机的泛化能力来确定滑动窗口的大小45；Last等提出了OLIN64，该算法通过比较分类器在训练集与验证集上的错误率来判断是否产生了概念漂移；Gama通过计算一个训练样本被错误分类的概率和其变化的范围来检测训练集中概念漂移的起点和终点65。Nishida等使用分类器对最新采集训练样本的分类准确率和对全部训练样本的分类准确率来检测概念漂移 66。罗秀等提出了基于误差率的检测方法67。性能法是最常用的概念漂移检测方法，但当数据流中存在类别不平衡时或
20、只有部分训练样本具有类别标志时，性能法将不适合用于概念漂移检测。距离法Katakis等将一个数据块映射成一个“概念向量”，然后对多个概念向量实施聚类，由一个聚类代表一个概念。当采集到一个数据集时，计算该数据集对应的概念向量与各个聚类中心的距离，以检测是否产生概念漂移。Katakis用该方法实现了对重复概念的检测68。但该方法有两个前提：一个数据块中的各数据同属同一个概念；连续的两个数据块属于同一个概念。性质法分析最近获得训练集的一些统计特性：各类的分布、各特征的值的分布等来实现对概念漂移的检测。Alippi等利用中心极限定理，设计了不依赖数据分布模型的，不需要任何先验信息的概念漂移检测算法69
21、-71；Peter等提出了基于熵的概念漂移检测方法72，通过一种熵的计算来评测训练集之间样本分布的区别；Kuncheva在KL距离和T平方测试的基础上通过假定数据服从组合正态分布导出了SPLL概念漂移检测方法73。3.4 概念漂移数据流分类研究使用的数据集到目前为止，概念漂移数据流分类技术被用于以下实际问题的解决：Web数据13,14、英国银行数据16、信用卡欺诈数据28，47、Reuters语料34，95、电影标注数据集95、Netflix电影等级数据集44、集群计算机负载均衡74、传感网数据75、金融时间序列76、日程提醒29、电价预测29,31,49,53,61,82,87,95、TRE
22、C32,33,50,63、视听说话识别77、垃圾邮件过滤43，67，96、可穿戴设备78、航班延误95、天气预报19、KDDCup数据20，40，41，42，43，47，58,60,83,88，91和Yahoo购物数据58,91、邮件链表68、交通数据75。使用频率比较高的人工概念漂移数据集包括：SEA数据集、STAGGER数据集、旋转平面数据集、高斯数据。另外，UCI中的一些数据集也常用于概念漂移数据流分类。4 概念漂移数据流分类研究的新动态4.1概念漂移数据流中的类别不平衡学习问题类别不平衡使得概念漂移数据流问题更加复杂，因此直到最近学术界才开始关注这方面的研究，总的思路是将已有处理类别不
23、平衡的算法加以改进，以适应概念漂移数据流中的类别不平衡问题。Gao等研究了概念漂移数据流学习中的类别不平衡问题79，算法对最新采集训练集中的多类（样本数量多的类）样本采取多轮“下采样”，将所有已学习过的少类（样本数量少的类）样本和最新采集训练集中的少类样本合并成一个子集，然后将该子集分别与属于多类每轮“下采样”得到的子集合并训练分类器，以实现对最新采集样本集的集成学习；Chen等利用Mahalanobie距离从已学习过的所有少类样本中选择一部分样本与最新采集的不平衡样本集合并，以减轻类别不平衡80-82；Lichtenwalter等对属于多类的样本进行下采样，将多类中被错误分类的样本与全部少类
24、样本构成训练集83；Gregory等采用Gao采取的方法，实现对最新采集样本集的集成学习，然后通过修改Learn+.NSE中的权值使其偏向多类和少类的查全率，实现其与已训练好分类器的集成84；Zhang等将被分类错误的少类样本加入训练集并使用F1值控制分类器更新频率85。由于存在概念漂移，这些方法都不能取得在数据分布不改变情形下类别不平衡学习算法所能达到的性能。4.2 概念漂移数据流中的概念重复学习问题Widmer较早地注意到了概念会重复出现15，但是概念漂移数据流中的概念重复学习问题直到最近才得到学术界的广泛关注。Widmer等将已经学习过的概念描述保存起来，当已学习过的概念重新出现时，保存
25、的分类器被重新激活；Ramamurthy提出将得到的分类器放到全局集中，当采集到新数据块时，通过评测全局集中的分类器在新数据块上的分类准确率来判断新到数据块是否属于新概念。如果不是新概念则从全局集中挑选部分分类器组成集成分类器去检测新到数据块是否属于原来出现过的概念86；Katakis将一个数据块转化成一个概念向量，然后通过数据流聚类方法将不断到来的数据块聚类成多个概念向量的集合，每个概念向量的集合通过增量学习得到一个分类器。最新采集数据块用最新分类器分类68；Li等提出了通过概念聚类，形成概念列表的方式检测新到样本是否是属于已有概念87；Masud等使用主集成和辅集成来检测新到样本是否属于已
26、学习概念88。以上这些算法的主要不足在于数据块的大小不容易确定（太大可能包含多个概念，太小则数据的分布不够体现概念本身）。4.3 概念漂移数据流中的半监督学习与主动学习问题Klinkenberg较早地关注到了概念漂移数据流分类中的半监督学习问题。在假定当前最新训练集与最新测试集同分布的条件下，他提出使用没有类别标志的样本估计滑动窗口的大小32；Xue等针对某类的先验概率发生变化以及最新采集的训练样本无类别标志的情形，探讨了如何利用无类别标志样本估计各类别样本的数量及实施半监督学习89；Zhang等提出了RK-TS3VM算法，该算法根据最新采集训练集中的样本是否具有类别标志和是否产生了概念漂移而
27、分为4个子集，然后根据子集的特点选择TS3VM或RK算法实现学习和分类90；Li等提出了SUN算法，该算法使用基于k-Modes的聚类方法来实现无类别标志样本的标注和重用，进而使用概念聚类方法实现概念漂移检测91。 Fan等提出了不需要事先获得样本类别标志就可以计算的两个检测概念漂移的指标：基于叶子节点的分布统计指标以及验证错误率与期望错误率的差。当检测到概念漂移后，根据样本类别标注代价，选择性地给出一部分样本的类别标志92；Zhu等选择使得集成分类器能产生最大方差的不确定样本给出类别标志，并通过分类器的加权集成，使得集成分类器能适应概念漂移93；Masud等使用主动学习策略去分辨数据流中是否
28、产生了新的类别以及挑选需要标注的样本94；Zliobaite等针对概念漂移发生的位置有的在分类面附近而有的远离分类面的特点，提出了可变不确定性策略和随机不确定性策略以主动选择无类别标志样本，尽量使得主动标注的样本能体现概念漂移95；Chu等提出了基于贝叶斯概率的在线主动学习算法，该算法利用重要性采样方法实现对无类别标志样本的主动无偏选择，使得主动选择的样本符合当前概念的概率分布96。以上这些算法或使用半监督学习策略尽量发挥没有类别标志样本的作用，或使用主动学习策略选择能体现概念漂移的样本进行标注，但半监督学习和主动学习并没有很好地结合起来。Kholghi提出了一个将半监督和主动学习相结合进行概
29、念漂移数据流分类的算法框架97。5 存在的问题通过以上分析发现，已有的各种概念漂移数据流学习算法在处理概念漂移数据流分类时存在以下五个方面的问题：1）冷启动。由于在一段时间里概念漂移的次数无法预知，学习系统只有在发生分类错误后才能得到调整，这导致了属于新概念的样本在刚开始出现时被分类错误。而且在只有部分样本具有类别标志的情形下，学习系统将很难知道是否产生了错误分类。如果将这样的分类器应用于工业流水线生产，将带来巨大的损失。2）只能实施单概念学习。目前主要使用滑动窗口、训练样本赋权、分类器自适应调整等方法实现对新概念的学习。这些方法只能跟踪学习一个概念，这导致了已学习知识难以保持。由于某些概念不
30、定期重复出现，其产生的时刻和延续时间未知，导致现有的单概念学习模式无法适应。对概念漂移中重复概念的关注说明多概念学习问题刚得开始到学术界的关注。3）概念漂移检测难以准确实施。现有的各种概念漂移算法主要依靠最近获得的训练样本集。当最近获得的训练样本集中存在类别不平衡时会导致对少类的忽视；当其中只有部分样本具有类别标志时已有概念漂移检测方法将无法实施。4）最新采集样本与最近获得训练样本同分布的假设不正确。从某一时刻开始最新采集样本中可能包含有跟最近获得训练样本不同分布的新概念，甚至于既包含有属于新概念的样本又包含属于旧概念的样本。如果最新采集样本与最近获得训练样本总是不同分布，现有概念漂移学习算法
31、将无法实施。5）理论基础研究缺乏。尽管概念漂移数据流研究已经取得丰硕的研究成果，然而到目前为止，概念漂移的定义、概念漂移的速度与幅度、概念漂移数据流分类器的错误率的界、概念的容量、概念漂移检测等都还没有得到严格的数学描述；已取得的一些理论上的结果也有待验证和深化。6 结束语概念漂移数据流分类给机器学习带来了巨大的挑战，本论文从数据流与概念漂移、概念漂移数据流分类研究的发展与趋势、概念漂移数据流分类的主要研究领域、概念漂移数据流分类研究的新动态四个方面分析总结了学者们在概念漂移数据流分类问题上杰出的研究工作，并分析了当前概念漂移数据流分类存在的问题。尽管概念漂移数据流分类已经取得了丰硕的研究成果，且已经成为机器学习研究的热点之一，然而其研究远还没有成熟，还存在着众多挑战，期待着学术界能有更大的突破。参考文献1Mitchell T M. Machine learningM. New York City: McGraw-Hill, 1997.2Schlimmer J and Granger R. Incremental learning from noisy dataJ. Machine Learning, 1986, 1(3): 317-354.3Grossberg S. Nonlinear n
