面向概念漂移数据流的自适应增量集成分类算法

吕艳霞,刘波男,王翠荣,王 聪,万 聪

1(东北大学 计算机科学与工程学院,沈阳 110004)2(东北大学 秦皇岛分校 计算机与通信工程学院,河北 秦皇岛 066004)

1 引 言

在大数据时代,互联网应用的普及、移动通信网络的发展,使得数据的获取速度与数据量迅速增加,数据成为了重要的生产资料.由于数据中蕴含着大量有价值的信息,且很多信息具有很强的时效性,如医疗诊断[1]、社交网络[2]、推荐系统以及异常检测等众多领域都需要对数据进行实时分析从而及时获取其中蕴含的有价值的知识.为了快速处理如此庞大的数据,我们需要快速有效的方法,使用合理的资源来完成实时处理分析[3].

实时数据分析是大数据分析场景中的一种特定情况.对于特定应用场景来说,重要的不仅仅是及时获得查询的结果,还要能够根据刚刚产生的最新数据获得查询结果.数据流是一种支持实时分析的算法抽象,抽象为无限的样本序列,每个样本都有一个时间戳,因此样本是有时序的.样本一个接一个的到达,需要对这些样本实时的构建和维护表示它们的模型.本文主要研究的是数据流在分类问题中的算法及相应的模型构建.

数据流分为稳定的数据流和动态的数据流,稳定的数据流具有稳定独立同分布的特点,易于预测和控制;而动态数据流则是非独立同分布的,并且可能随着时间变化而发生改变,使得在之前数据集上建立的预测模型不再适用于当前的数据分布,这种现象称之为概念漂移[4].例如大型商场中顾客的购物倾向会随着时间变化、网络安全中的入侵检测[5]也随着用户不同而变化等.在进行流数据分类时,有两个主要的算法挑战:数据流庞大且速度快,并且我们需要实时从中提取信息.这意味着为了节省时间和内存,通常需要接受近似的解决方案;此外,数据可能正在演变即发生概念漂移,模型必须能够适应概念漂移的情况.

解决概念漂移是数据流分类面对的最重要的问题之一.通常的解决办法是:首先,检测到数据流中概念漂移的发生;然后,通过对概念漂移的衡量来使得模型进行自适应.利用集成学习的灵活特性可以通过对模型进行集成应对概念漂移.数据流的特点之一就是数据的源源不断的特点,在不考虑数据快速到来这一特点,数据量的巨大则要求整个模型的自适应的调整不能让模型随着数据量的增大速度逐渐变慢.在许多经典的集成学习算法中,通过对单模型的集成来解决数据流产生的概念漂移问题以及可能会出现的数据不平衡现象[6,7],但是没有很好的机制去合理的使得所有基模型仅利用当前的一部分数据建立,因此存在一些基模型从数据流的开始就一直存在.虽然利用替换策略等方法可以使得整体模型的性能保持在一个合理的范围,但是如何使得整体模型随着数据不断到达,适应不同的样本窗口也是一个需要解决的问题.

在集成学习中公认的在适当的组合方案下,基模型之间的多样性是必不可少的[8].集成模型通常利用特征的采样或者样本的采样来制造基模型之间的多样性,并且整体模型针对预测的准确率或者其他针对当前模型的衡量指标进行自适应调整.然而,在数据流环境下,通常集成模型中每一个基模型都是建立在过去所有或者大部分数据的基础上的,即使有自适应的调整,也需要依赖对概念漂移检测算法以及不同的策略去修改或者删除在过去概念上已经建立好的基模型.这中间就会产生这样一个问题:如何使得对数据变化敏感又不至于太过敏感且在当前数据窗口上分类性能良好的模型不被删掉.

具体来说,在含有概念漂移的数据流分类模型的构建过程中,设计增量集成学习模型需要解决两个研究问题:保留哪些之前训练的历史模型用来对新到达的样本进行预测以及如何利用保留的历史模型更好的适应发生概念漂移时的学习.为此,本文中提出了一种用于数据流分类的增量集成模型,基模型之间的多样性不再仅仅通过样本的采样来实现,而是通过引入用于集成学习的多样性策略[9]来保持基模型之间的多样性最大化.在数据流分类研究中,大多采用增量集成模型的算法都采用决策树作为基模型,本文选择自适应霍夫丁决策树[10]作为基模型,结合模型迁移的思想使历史模型高效的适应最新数据.并且利用基于当前数据的基模型的适应性更新集成模型,使其保持对当前数据的性能最优.

2 相关研究

当前针对具有概念漂移的数据流分类方法,可分为增量分类模型和集成分类模型.集成模型是数据流研究领域中普遍使用的方法之一,它可以同时处理机器学习问题和数据流中的概念漂移,并且能够取得很好的效果.由于在数据流中数据不断到达,不能一次性获得全部数据,需要不断训练模型以适应最新数据分布,因此增量模型也是数据流分类研究中经常使用的方法之一.

在增量学习中,常用的处理概念漂移的策略包括:滑动窗口、概念漂移检测和集成方法.滑动窗口方法[11]主要应用于在线学习场景,保留部分最近到达的数据,并用保留的数据和新到达的训练样本更新当前模型.另外一些模型[12]在学习算法中使用概念漂移检测模块.如果未检测到概念漂移,则使用新到达的数据更新当前模型.否则,当前模型(可能是单个模型[12]或集成模型[13])将被丢弃,并从头开始构建新模型.以上两种策略都不需要保留先前获得的知识/模型.然而,在概念重复出现的情况下,保留历史模型将是有益的,可以直接使用历史模型进行预测.在更一般的情况下,如果两个概念是相关的,但是出现的时间并不连续,则调整历史模型可能比优化当前模型或构建新模型更容易.因此,保留历史模型的集成方法近年来越来越受欢迎[14].

Leverage Bagging[15]在模型的输入和输出中引入随机性进一步使集成模型具有更好的多样性.该模型主要是通过对样本采样,并且根据模型对样本预测的准确率的变化对输出进行随机化的改变,来应对概念漂移.通过对模型在当前样本的表现能力进行监测,当预测准确率下降时,进行被动调整.自适应随机森林[16](ARF)是基于随机森林提出的处理数据流分类的集成模型,ARF通过对概念漂移的检测并设立警告机制,通过训练替换树加速概念漂移发生时集成模型的更新.Online Smooth Boosting[17]是处理概念漂移的另外一种常用集成方法,通过对已经到达的数据进行评估得到其权重以及每个基模型的权重,实现集成模型的多样性.以上集成方法都是通过对数据进行采样或者通过对样本和基模型赋予不同的权重实现集成模型中基模型的多样性,提升模型对当前数据的泛化能力.当数据流中相同或相似的概念重复出现时,利用已经建立的历史模型对当前数据进行准确预测可以节省资源同时加速模型的概念漂移适应性.在基于增量学习的基础上提出了DTEL[18],在集成模型的更新策略上采用最大化模型多样性的更新策略,同时利用模型迁移的思想使历史模型快速适应当前数据窗口.为了使得模型可以更好的应对概念漂移,不仅可以利用部分的历史信息,而且可以不通过样本采样或者属性采样实现模型多样性,利用自适应霍夫丁决策树作为基模型,本文提出了基于历史模型的自适应集成分类算法HAEL算法.

3 基模型自适应集成分类算法

本文主要在增量学习的基础上将迁移学习融入到集成模型的更新过程,提出了新的更新策略,并且采用自适应霍夫丁决策树作为基模型,从而得到更加适合含有概念漂移的数据流分类模型.该模型在保存必要的历史信息的前提下可以针对当前的数据,并且不需要采样来得到单模型之间的差异性.在面对概念漂移的时候具有更好的适应能力.

3.1 集成框架

在基于Bagging的集成模型当中,基模型的训练数据集是通过各种不同的采样技术得到的.在发生概念漂移的时候多是利用概念漂移检测机制来确定模型是否更新.在基于Boosting的集成模型当中,通过利用样本的真实标签对预测标签进行评估,从而对集成模型中的基模型和每一条样本赋予一个权值来得到.当数据变化足够强烈的时候,如发生突变漂移,以上两种模型均能很快的做出应对,但是在渐进漂移的时候,数据的分布缓慢发生变化,导致两种模型不能及时的适应这类概念漂移的发生.不同于传统的增量模型的集成策略,利用历史知识进行概念漂移自适应的DTEL集成模型,基模型的训练基于每一个最新到达的窗口数据,并且集成模型的更新是以基于多样性的标准来代替基于准确率的标准.本文提出的HAEL采用基于准确率的模型更新策略,使用当前最新数据对历史模型进行迁移更新,并且保留更新之后的基模型,使得集成模型更加专注于当前的数据.通过参数的控制可以灵活的选择对历史知识的保留,同时,在基模型的选择上也选择了更适合数据流分类的自适应霍夫丁决策树,相比于DTEL利用普通决策树作为基模型更适用于数据流分类的环境.HAEL的整体框架如算法1所示.

算法1.HAEL集成框架

输入:(D1,D2,…,Dt,…)代表数据流在t时刻的窗口数据,S代表的是集成模型中基模型的集合.

输出:在每一个时刻t的集成模型St

1.Whilet时刻的窗口数据Dt可用时 do

2. 基于数据Dt训练一棵新的霍夫丁决策树st;

5. 根据集成模型的规模更新S使其准确率最大化;

6.end

与传统的基于窗口的集成模型相比,首先,HAEL并没有直接利用集成模型中的历史模型进行预测,也没有重新训练集成模型,而是对历史模型进行迁移以快速适应当前最新窗口的数据,如图1所示.然后使用基于最新窗口的数据训练得到的基模型替换掉迁移之后的基模型中准确率最低的基模型(如图1(b)中虚线圆圈代表的基模型),得到新的集成模型St.其次,新的集成模型会根据准确率对集成模型以固定的规模进行更新,使得预测准确率最低的某个历史模型被最新窗口的数据训练得到的基模型替换掉.

图1 数据流分类集成模型说明Fig.1 Ensembled model of data stream classification

(1)

其中,Ε(·)表示一个随机变量的期望值,l是损失函数.假设数据流的底层数据分布式以Ft(x,y)序列来表示,整个增量数据流分类过程的目标如公式(2)所示.

(2)

3.2 自适应霍夫丁决策树

适当的数据窗口大小对概念漂移有一定的应对能力,然而当概念漂移出发生在窗口中间位置附近时,即基于当前窗口数据训练的基模型是在两种不同底层数据分布下建立的,则集成模型的准确率会受到影响.由于窗口大小固定,实际的数据流随时都有可能发生概念漂移,所以这种情况难以避免.为了解决该问题,本文选择自适应霍夫丁决策树作为HAEL的基模型.自适应霍夫丁决策树会在每一条样本数据到来时对其所有子节点进行重新评估,当检测到概念漂移时对子节点进行替换或者删除.这种针对概念漂移的处理方式可以在概念漂移发生在数据窗口中时,对基模型有一定的调节能力,使其适应新的概念.相比于DTEL中的普通决策树或者是针对数据流处理的霍夫丁决策树,自适应霍夫丁决策树可以更好的应对在同一窗口数据内发生概念漂移带来的模型准确率降低的问题.

3.3 注意力增量学习

数据流的一个特点就是数据是源源不断到达,利用所有的数据建立模型是不可能的.并且数据流经常伴随着概念漂移发生,如何使模型更快更好的适应当前数据流中的概念是需要解决的问题.本文将注意力集中在最新窗口的数据上,在数据流发生概念漂移时,使得模型能够快速的适应且保证较高的准确率.

在构造集成模型的初始阶段,基模型的数量还没有达到规定的阈值.每次到达一个窗口的数据,训练一个最新的基模型,之前训练得到的基模型也会利用当前的窗口数据进行更新.当基模型的数量达到了集成模型规定的阈值,在当前窗口的数据上训练得到的基模型会替换掉之前的某一个历史基模型.因此,在整个集成模型当中始终存在着在不同窗口的数据上建立的基模型,与基于Bagging,Boosting的集成模型采用对数据进行采样或者增加权重等方式相比,HAEL的模型构建方式更加直接,并且可以利用到所有的数据样本而不需要采样.

为了将注意力始终聚焦在当前窗口数据上,当新的窗口数据到达完毕,HAEL集成模型并不直接使用历史模型与当前窗口数据训练得到的模型进行组合来对样本进行预测,而是采用一种知识迁移的方法,将历史基模型进行迁移以适应当前窗口数据的分布.决策树的构建过程是递归的把特征空间划分为更小的子空间的过程,每一个子空间对应一个叶子节点且拥有一个类标签.决策树的这种结构天然包含了历史知识片段,本文为了将注意力迁移到当前窗口数据中,使用当前窗口的数据对历史基模型进行更新,然后使用更新后的基模型与当前窗口数据训练得到的基模型进行组合构建集成模型.主要包括以下两个过程:

1)将最新窗口中的样本在历史基模型中执行到叶子节点,并按照样本的标签更新历史基模型叶子节点的类标签.这种知识迁移的思想可以利用历史知识快速适应新知识.

2)为了对最新窗口的数据正确分类,需要在历史基模型的叶子节点继续训练一棵子树,直到达到决策树的停止生长标准.

选择更新之后的历史基模型中性能最差的一个被基于当前窗口数据训练得到的基模型替换掉.保证模型中始终存在某个单模型建立在最新的窗口数据上,并且随着时间的推移,建立在历史窗口数据上的基模型逐渐被替换掉,模型的注意力将持续关注于当前的数据.针对不同的数据集,对当前的数据的关注程度也是需要调整的,所以添加比较范围参数来确定在哪些样本上进行更新后的历史基模型的评价.通过该参数可以调整评价历史基模型的数据范围,调整关注当前数据的程度.合理的比较范围也可以适当的保留过去的信息.所以建立的模型始终都是将整体的注意力放在当前窗口的数据上,而对当前窗口数据的注意程度则由参数控制.和非增量式的集成模型相比,HAEL不需要概念漂移的检测来决定集成模型何时更新,也不需要采样保证基模型的多样性,每一个基模型都是建立在不同的窗口数据上的.加入比较范围参数更可以使得集成模型更加的灵活,在应对不同的数据流的时候都有更好的应对能力.如果将比较的范围参数较大,则历史窗口数据的结果会更重要,当前窗口数据的注意力相对较小;相反,如果设定较小的范围参数,则注意力更加关注当前窗口数据,历史知识的影响较小.

3.4 预测策略

在进行预测阶段,HAEL集成模型中的每一个基模型对窗口数据Dt进行预测.将每一个模型中预测过的所有的数据的历史准确率进行归一化处理,之后得到每一个模型的预测的权重作为每一个基模型的预测权重,根据其预测结果得到最终的预测数值,根据预测数值和0.5进行比较得到最终的预测结果.这种预测策略是比较常见的加权投票,在一般的集成模型中每一个基模型预测的样本的数量是相同的,所以每一个基模型在计算历史数据准确率时是具有相同的地位的.在HAEL的整体集成策略中,每一个基模型进行预测的样本的数量是不同的,集成模型中存在时间越长的模型其预测过的样本就越多,如果在平稳非概念漂移的情况下,该模型因为通过大量数据训练所以拥有较好的准确率,从而不易被替换,然而在概念漂移的情况下,也是因为在过去数据上建立的模型可能由于对过去数据的拟合效果比较好所以在面对当前发生概念漂移的数据流上泛化能力较弱,准确率会下降,从而在替换策略中会被优先替换.

3.5 HAEL算法实现

HAEL的实现过程见算法2,假设t个窗口数据D1,D2,…,Dt不断到达,HAEL首先基于第一个窗口数据训练一棵霍夫丁自适应决策树s1,当新的窗口数据Dt样本全部到达,之前的决策树要基于Dt进行迁移以适应最新数据,同时,基于Dt重新训练一棵新的决策树st.然后将两者使用AUE2中使用的加权投票策略进行组合,因为该策略在增量集成模型中展示了最好的总体准确性[11].之前的决策树更新后的权值计算如公式(3)所示,基于当前窗口数据重新训练得到的决策树的权值计算如公式(4)所示.

(3)

(4)

(5)

(6)

(7)

算法2.HAEL算法

输入:(D1,D2,…,Dt,…)代表数据流在t时刻的窗口数据,S代表的是集成模型中基模型的集合.M代表指定的集成模型中的基模型的数量.Rel代表指定的准确率比较范围.

输出:在每一个时刻t的集成模型St

1.whilet时刻的窗口数据Dt可用时do

2. 基于数据Dt训练一棵新的霍夫丁决策树st;

4.if模型的数量少于Mthen

6.if当前时刻的模型数量大于Mthen

10. 如公式(4)计算st的权重;

11. 如公式(7)所示得到此时刻的集成模型St;

12.returnSt;

3.6 复杂性分析

4.1 实验平台

实验使用大规模在线分析平台MOA[19],MOA是最流行的数据流挖掘开源框架.

4.2 实验数据

实验使用了三个人工数据集,其详细信息如表1所示.其中SEA200G表示在SEA数据集上,窗口大小为200条样本,R表示是循环漂移,G表示是渐进漂移,A表示是突变漂移,SEA-R;SEA-G表示在SEA数据流中同时存在循环概念漂移和渐进概念漂移.

LED Generator:生成一个预测在7段LED显示屏上的数字的问题.其中的每个属性有10%的几率被倒置.它的贝叶斯分类率为74%.用于实验的生成模型的特殊配置产生了24个二进制属性,其中17个是无关的.

SEA Generator[22]:此数据集包含突变概念漂移.他一般使用三个属性,所有的属性值都在0和10之间.其中只有两个属性是相关的(如x1和x2),x3则只是含随机值的噪声属性.数据集被分为四个不同概念的块.在每个块中,使用f1+f2≤θ分类,其中f1、f2是前两个属性,θ是阈值.在数据块中9,8.7,9.5是常见的值.类标签由公式决定:ax1+bx2≤/≥θ.

Sine Generator[20]:在二维特征空间中,通过正弦曲线来确定数据的标签,定义如下:asin(bx1+θ)+c≤/≥x2.在实验中,两个维度和的所有数据都在范围(-5,5)中.θ是均匀变化的价值生成数据分布的变化.

STAGGER Boolean Concepts(STA)[20,21]:生成具有分类特征的数据使用一组规则来确定类标签.根据文献[10,19],特征值为:颜色{红色(R)、蓝色(B)、绿色(G)}、形状{圆形(C)、正方形(S)、三角形(T)}、大小{小(S)、中(M)、大(L)}.决策规则可以表述为:y=((color=1/≠1a)∨1/∧1(shape=2/≠2b))∨2/∧2(size=3/≠3c)通过改变规则项来模拟概念漂移.

表1 数据集
Table 1 Data sets

数据集特征数样本数量类别概念漂移类型LED40024160002LED-R;LED-GLED5024160002LED-R;LED-ASEA2003160002SEA-R;SEA-GSEA503160002SEA-R;SEA-ASTA4003160002STA-R;STA-G

4.3 实验结果分析

整个实验主要是在四种不同的人工数据集上进行测试.分别与目前经典的和最新的数据流分类算法:自适应随机森林(Adaptive Random Forest,ARF)、Leverage Bagging(LB)、Online Smooth Boosting(SMOOTH)、OzaBoost(BOOST)以及OzaBag(OB)进行对比.

其中表2和表3是在LED数据集上,分别存在循环出现的渐进概念漂移和循环出现的突变概念漂移时,算法在执行时间和准确率上的结果对比.表4和表5是在SEA数据集上,分别存在循环出现的渐进概念漂移和循环出现的突变概念漂移时,算法在执行时间和准确率上的结果对比.表6是在STA数据集上,存在循环出现的渐进概念漂移,算法在执行时间和准确率上的结果对比.可以看出在大部分情况下HAEL都具有更高的准确率,但是执行时间只有在SEA数据集上循环突变概念漂移的情况下是最快的,其余虽然不是最快的,但是与其它模型的执行时间相差不大.

表2 LED中循环渐进概念漂移的时间和准确率
Table 2 Time and accuracy of recurrent and
gradually concept drift in LED

集成模型 时间(s)准确率(%)HAEL3.9871.40ARF2.3366.06LB5.6471.18SMOOTH3.7870.38BOOST2.4570.51OB2.4170.34

表3 LED中循环突变概念漂移的时间和准确率
Table 3 Time and accuracy of recurrent and abrupt concept drift in LED

集成模型时间(s)准确率(%)HAEL3.4471.84ARF2.6666.68LB5.3171.80SMOOTH34.0570.80BOOST2.3970.43

表4 SEA中循环渐进概念漂移的时间和准确率
Table 4 Time and accuracy of recurrent and gradually concept drift in SEA

集成模型时间(s)准确率(%)HAEL3.5585.06ARF10.8883.24LB11.0083.52SMOOTH3.8884.36BOOST2.9883.53OB3.6783.51

图2和图3是在LED数据集上,分别存在循环出现的渐进概念漂移和循环出现的突变概念漂移时,算法执行准确率的结果对比;图4和图5是在SEA数据集上,分别存在循环出现的渐进概念漂移和循环出现的突变概念漂移时,算法执行准确率的结果对比;图6是在STA数据集上,存在循环出现的渐进概念漂移时,算法执行准确率的结果对比.通过观察实验结果图,可以更加直观的看出,多数情况下,在发生概念漂移时,HAEL在模型预测准确率方便表现出色且更加稳定.相比于对具有渐进和循环特点的LED数据进行预测,突变的概念漂移会突然发生,固定的窗口大小下建立模型相比于利用采样的方法Leverage Bagging并不具有优势.虽然采用了自适应霍夫丁决策树来尽量应对这一问题,但是效果还是有限.

模型的整体框架是增量式的集成学习.在初始阶段根据不断到达的样本逐渐构建.在样本没有达到一定数量的时候即模型没有达到规定的集成数量时模型不会依据设定的更新策略进行更新.这也导致在实验中,模型在样本数量较小的时候准确率比较低,此时模型并没有构建完整.

表5 SEA中循环突变概念漂移的时间和准确率
Table 5 Time and accuracy of recurrent and abrupt concept drift in SEA

集成模型时间(s)准确率(%)HAEL1.0985.58ARF11.6783.89LB11.5284.26SMOOTH3.9785.03BOOST3.2384.14OB3.3483.94

表6 STA中循环渐进概念漂移的时间和准确率
Table 6 Time and accuracy of recurrent and gradually concept drift in STA

集成模型时间(s)准确率(%)HAEL0.8892.08ARF0.9891.55LB1.5092.01BOOST0.5390.14SMOOTH0.6984.06OB0.5885.09

图2 LED上循环渐进概念漂移的准确率Fig.2 Accuracy of recurrent and gradually concept drift in LED

图3 LED上循环突变概念漂移的准确率Fig.3 Accuracy of recurrent and abrupt concept drift in LED

图4 SEA上循环渐进概念漂移的准确率Fig.4 Accuracy of recurrent and gradually concept drift in SEA

图5 SEA上循环突变概念漂移的准确率Fig.5 Accuracy of recurrent and abrupt concept drift in SEA

图6 STA上循环渐进概念漂移的准确率Fig.6 Accuracy of recurrent and gradually concept drift in STA

5 总 结

本文针对数据流中的概念漂移问题,提出了在面对不同类型的循环概念漂移时具有更高准确率的HAEL集成模型.在基于增量学习的基础上,利用知识迁移以达到快速的模型更新;同时,添加比较范围参数来进行模型替换,使得模型对历史知识和当前知识的注意力可以调节,在应对概念漂移时有比较灵活的自适应能力;并且采用自适应霍夫丁决策树作为集成模型的基模型,进一步提高整体模型对概念漂移的自适应能力.