新兴技术的迅猛发展使得海量数据不断涌现, 如新闻媒体、物联网和云计算等不同行业产生的业务数据在一般场景中均可视为动态流数据^[1].这些数据中包含大量有效信息亟待进行挖掘, 然而, 丰富的数据用于训练虽然能够降低风险, 但在训练阶段将有大量时间损耗, 且使计算复杂化.理想情况下, 将每个样本都用于模型训练对分类性能会有很大提高, 然而大量可用数据将会使训练集非常大以至于无法全部加载到内存中^[2].针对传统数据挖掘方法在解决流数据挖掘问题时存在学习时间长、学习效率低等问题, 一个有效的解决方式是使用在线学习技术, 即每次训练都只将批量的流数据子集作为训练集^[3].一般来说, 按时间依次产生的时间序列数据, 因数据量太大无法全部加载到内存中的大数据集都可用在线学习技术来进行处理.

就流数据的实时、多变性而言, 并不能保证每次到达的新样本与前一次到达的样本完全保持独立同分布, 因此不能每次都将由历史数据训练得到的分类模型作为后续样本的基准分类器^{[4, 5]}.在训练模型阶段的每个新步骤中, 当训练子集分布发生改变时, 数据空间的底层结构也随之发生变化, 从而导致概念漂移的发生^[6].而当前由历史数据训练得到的分类器不符合新样本的分布规律, 因此会引起分类精度下降^[7].另外, 流数据中存在噪声样本是不可避免的, 尤其是当噪声规模较大时, 造成分类器准确率大幅下降, 其表现形式类似于发生真实的概念漂移, 这种由噪声引起的伪概念漂移将严重干扰真实概念漂移的准确检测, 即检测模型容易混淆真伪概念漂移而发生误判, 从而导致模型对真实概念漂移或噪声引起的伪概念漂移做出错误的应对和处理.此外, 在流数据学习过程中, 若当前步骤中保留的训练样本信息有限, 即当前所包含的训练样本信息无法代表全部样本的分布时, 模型也会产生较大幅度的性能波动, 此时, 也会引起概念漂移的误检.

本文针对混杂噪声或训练样本规模过小而产生的伪概念漂移会引起与真实概念漂移混淆的问题, 提出一种基于在线性能测试的概念漂移检测方法.该方法首先对当前得到的最新数据集进行分组学习, 跟踪模型分类准确率并计算相邻时间单元之间的精度落差, 通过衡量测试精度落差向量不同分量的大小, 动态得到不同学习阶段每组数据流中的有效波动位点.然后根据不同分组中有效波动位点的同步情况, 整合不同分组中的有效波动位点, 即寻找一致波动位点.最后通过实时监测一致波动位点的邻域参考点精度变化及收敛趋势, 比较一致波动位点的测试精度降幅及其邻域参考点的精度与收敛性, 以有效检测一致波动位点中真实的概念漂移位点.本文主要提出了一种精确检测并辨识真伪概念漂移的方法, 能够有效去除数据流中噪声数据以及训练集过小等问题对正常概念漂移检测的干扰, 适用于常见的流数据在线学习及其概念漂移检测问题.

1 相关工作

在实际数据挖掘问题中, 经常会遇到具有很长时间周期跨度的流数据, 对于这类数据, 其不同时刻的数据不能保证符合独立同分布的特性, 特别是在复杂多变的环境中, 样本实例随时间发生分布变化而引发概念漂移的概率很高.现实中, 概念漂移的发生可能由多种原因引起, 如在垃圾邮件过滤问题中, 一方面, 垃圾邮件的特征范畴可能随时间发生变化, 另一方面, 用户对垃圾邮件的定义也可能根据其喜好而有所改变, 这两方面均可视为数据流发生了概念漂移^[8].再如天气或水温监测、传感器数据监测^[9]、设备故障诊断等^{[10, 11]}, 这些现实问题产生的数据流何时发生漂移或是否发生漂移往往是提前未知的, 因此准确检测概念漂移是否发生对处理许多现实问题具有重要的意义和价值^[12].

除流数据本身可能发生的概念漂移外, 其他因素也可能导致流数据在线学习过程中测试性能的波动.一方面, 真实数据流中噪声是客观存在且不可避免的, 噪声样本因偏离正常样本分布太多, 会干扰流数据在线学习过程中的模型调整, 导致对一些正常分布的数据分类错误, 准确率降低.另一方面, 在线学习过程中, 当前的学习模型所包含的训练样本规模过小, 得到的分类器不能稳定地表示数据的整体空间特征分布, 因此, 每次训练都可能会使模型发生较大改变, 导致分类结果产生不稳定波动.这两者虽然不是概念漂移, 但却与发生概念漂移产生了类似的测试精度波动的结果.与流数据中真实概念漂移相对应, 这种非数据分布改变而导致的分类器波动称为伪概念漂移.流数据中由噪声或训练样本规模过小而导致的伪概念漂移将直接威胁到真实概念漂移的检测, 降低在线学习模型的分类质量.尤其是当噪声样本含量较大或包含有效样本信息过少时, 模型测试精度下降幅度增加, 更容易误判为发生真实概念漂移, 严重干扰了对真实概念漂移的检测结果.

目前, 在处理流数据概念漂移问题中已经取得了很多研究成果.已有的处理方法大致可以分为两类:一是基于滑动窗口方法, 二是自适应集成学习方法.滑动窗口方法通过时间窗口将当前训练数据限制在最新进入模型的样本中, 并利用当前窗口中的新数据训练新的分类器, 在预测时直接使用该分类器进行分类.在处理流数据概念漂移时, 启发式地动态调整窗口大小, 提高分类器适应能力.常见的方法有基于单窗口的概念漂移检测方法(SWCDS)^[5].该算法通过周期性地检测滑动窗口中的分类错误率变化检测数据分布的变化.Du等人在2014年提出依据信息熵判定窗口新旧实例分布调整窗口方法(ADDM)^[13], Ali等人于2016年提出了加速Hoeffding漂移检测方法(FHDDM)^[14]等.虽然以窗口为对象的检测方法在一定程度上提高了概念漂移检测的性能, 但窗口大小直接决定了分类器的性能.较小的窗口敏感度较高, 能够迅速对概念漂移做出反应, 但在检测到漂移位点的同时也会对噪声等引起的不稳定波动做出反应.而较大窗口则难以及时检测到概念漂移, 导致漂移检测滞后.

对于分类器建模过程, 构造多个简单分类器比建立一个复杂单分类器更简单、易行.因此, 许多研究者采用自适应集成学习方法处理流数据中的概念漂移问题.这种方法利用新到达的数据块训练一个基分类器, 采用不断更替模型中性能较差的基分类器以保证系统中保存固定数目的较优基分类器, 并使分类器能够适应概念漂移数据流.但这种方法只保证了分类器能够较好地适应最新的数据分布, 却不能准确地检测到概念漂移何时发生.SEA算法^[15]通过分类器精度的阈值不断更新基分类器, 以此保证分类器能够适应概念漂移.算法AWE^[16]在算法SEA的基础上进行改进, 根据各个基分类器对当前数据块的分类精度为它们设置权值, 更新分类器时直接替换权重最小的基分类器.CDOL算法^[17]由两个带权基分类器组成, 检测到概念漂移后用新样本训练新的基分类器并移除原有基分类器中权重较小者.自适应集成学习方法仅根据各基分类器对当前数据块的分类精度来评估要删除哪些基分类器, 忽略了基分类器的历史重要性.另外, 一次小的概念波动可能导致历史上重要的基分类器被误删, 造成保留的基分类器不是全局占优, 难以获得好的预测结果^[18].

检测概念漂移的一种主流思想是依据分类模型测试精度变化趋势判断漂移是否发生^{[19, 20]}.一般来说, 这种思想需要保证分类模型必须对新增样本做出决策之后才能继续进行下一次训练, 以便检测器及时分析分类精度的变化趋势^[21].通过监视分类模型的表现并结合某些决策方法以判断数据分布的变化情况, 设置适当的置信水平控制预警信号, 预测可能发生漂移的位点.然而, 若预警信号着重关注于模型测试准确率的下降幅度, 则一旦满足预先设置的临界值条件就会触发预警信号.如果没有进一步追溯下降原因, 就会导致当训练集中噪声数据量足够多或者训练样本信息明显缺失时引起的伪概念漂移现象也被当作真实概念漂移来处理.而实际上, 伪概念漂移与真实概念漂移存在本质上的差异, 对应处理机制也不相同.真实概念漂移处理侧重于新样本分析及分类模型的实时更新, 并通过摒弃历史数据来减少原始样本对模型更新的抑制作用, 或者保存由历史数据训练所得到的分类器, 以免当前数据分布形式再次出现^[22].相反地, 伪概念漂移处理方法需要利用历史数据并引进新的更多的样本, 以降低训练集中噪声或样本规模过小对模型检测性能的负面效应, 进而保证训练样本空间中数据分布及概念的纯洁性和有效性.将真实概念漂移处理机制作用于伪概念漂移会严重影响模型的收敛, 降低模型的性能, 因此有必要在概念漂移检测的过程中对伪概念漂移进行辨识和区分.

针对概念漂移检测机制中容易混淆真伪概念漂移的问题, 本文提出一种有效检测概念漂移方法.主要工作如下.

1) 给出发生真伪概念漂移的特征描述, 将引起分类模型准确率的不稳定波动原因分为数据发生概念漂移和数据中存在噪声或训练数据规模过小而引起的伪概念漂移, 明确发生真实概念漂移与伪概念漂移之间的本质差异.

2) 以给出的真伪概念漂移特征描述为基础, 提出基于在线性能测试的流数据概念漂移检测方法, 包括有效波动位点检测、一致波动位点提取和概念漂移位点判定.该方法对当前获得的最新数据进行均匀的分组学习, 然后根据相邻时刻模型精度差异来检测流数据中发生的有效波动位点, 并通过交叉检验的方式提取其中的一致波动位点, 最后跟踪一致波动位点的邻域参考点精度变化趋势, 比较精度收敛偏差以准确检测概念漂移.

2 真伪概念漂移描述及分析

假设存在流数据序列$ \boldsymbol{S} = {\rm{\{ (}}{x_t}, {y_t}{\rm{)\} }}_{t = 0}^T, $其中, x_t∈Rⁿ和y_t∈{–1, +1}, 流数据学习过程中样本可以逐个进入, 也可分批到达, 为简化问题描述, 不妨将每次到达的样本集表示为S_t={X_t, Y_t}.对于真实的概念漂移, 漂移发生后新进入的样本与历史数据分布不一致, 其在线学习样本序列为S={{X₀, Y₀}, {X₁, Y₁}, …, {X_t–1, Y_t–1}, {X_t, Y_t}, …, {X_T, Y_T}}, 其中, {X₀, Y₀}为初始离线样本, ${\rm{\{ }}{ \boldsymbol{X}_i}, { \boldsymbol{Y}_i}{\rm{\} }}_{i = 0}^{t - 1} \in P, {\rm{\{ }}{ \boldsymbol{X}_j}, {\boldsymbol{Y}_j}{\rm{\} }}_{j = t}^T \in \mathcal {P}, $且P和$\mathcal{P}$分别代表原始数据分布和发生概念漂移后的数据分布.伪概念漂移区别于真实概念漂移, 并未发生数据分布改变, 而是由于数据中存在噪声或训练样本包含有效信息过少等其他因素的存在导致分类器测试精度出现不稳定波动.以噪声引起的伪概念漂移为例, 其对应的在线学习样本序列可以表示为$ \boldsymbol{S} = \{ \{ { \boldsymbol{X}_0}, { \boldsymbol{Y}_0}\} , \{ { \boldsymbol{X}_1}, { \boldsymbol{Y}_1}\} , ..., \{ { \boldsymbol{X}_{t - 1}}, { \boldsymbol{Y}_{t - 1}}\} , {\rm{\{ }}{ \boldsymbol{X}_t}, { \boldsymbol{Y}_t}{\rm{\} , }}\{ { \boldsymbol{X}_{t + 1}}, { \boldsymbol{Y}_{t + 1}}\} , ..., \{ { \boldsymbol{X}_T}, { \boldsymbol{Y}_T}\} \} , $其中, ${\rm{\{ }}{ \boldsymbol{X}_i}, { \boldsymbol{Y}_i}{\rm{\} }}_{i = 0}^{t - 1} \in P$且${\rm{\{ }}{\boldsymbol{X}_j}, {\boldsymbol{Y}_j}{\rm{\} }}_{j = t + 1}^T \in P, $而{X_t, Y_t}表示偏离原始数据分布的噪声样本.为方便描述, 将噪声样本表示为数据分布为$\mathcal P$的样本, 即{X_t, Y_t}∈$\mathcal P, $两种流数据模式可用图 1表示.

图 1中样本数据$ \boldsymbol{S} = {\rm{\{ (}}{ \boldsymbol{X}_t}, { \boldsymbol{Y}_t}{\rm{)\} }}_{t = 0}^T$沿时间轴按序到达并用于训练模型, 其中, 每个圆代表某一时间单元内到达的一批新样本S_t={X_t, Y_t}, 网格圆形和点阵圆形分别表示符合两种不同分布P和$\mathcal P$的数据.假定在t时刻发生概念漂移, 图 1(a)展示了流数据发生真实概念漂移的情况, 从t时刻开始每个批次的数据均发生改变, 即从分布P改变至分布$\mathcal P$且短时间内不可逆, 在分布变化发生后原始模型不再适用于新数据分布, 此时必须利用新样本重新训练分类模型, 以便尽快恢复模型分类性能^[23].图 1(b)展示了含噪声的流数据产生伪概念漂移的形式, 假定在t时刻到达的新样本${\rm{\{ }}{ \boldsymbol{X}_t}, { \boldsymbol{Y}_t}{\rm{\} }} \in \mathcal P$与原始数据分布P产生偏差, 给学习器带来干扰性波动, 但在t+1时刻数据{X_t+1, Y_t+1}∈P恢复原始分布状态, 当在线学习的数据单元S={X_t, Y_t}包含样本规模较小时, t时刻到达的样本在训练集中只占较小比例, 因此学习器能够在后续时间单元内尽快恢复, 但当噪声量较大时, 这些异常数据将作为代表性样本大幅度更新模型, 因此需要经过后续多步在线学习过程中新进入的样本对模型进行持续性校正, 模型收敛速度较慢.

另一方面, 在流数据在线学习初始阶段, 训练样本规模较小, 训练集未能覆盖完整的数据分布信息, 因此, 模型测试精度会产生不稳定波动.但这种情况与真实概念漂移及噪声引起的伪概念漂移存在明显不同, 如在同一数据流中, 假定该数据流在特定位置发生概念漂移, 则由于训练数据规模过小而产生的波动位置会随着数据流特征随机产生, 而真实概念漂移所引发的测试精度波动位点是固定的.例如, 图 2所示为将UCI上的数据集Image均匀划分为5组, 两个子图分别对应随机取其中4组进行训练, 剩余样本进行测试得到的结果(参数设置:惩罚参数C=1000, 在线学习步长O=10).图中横轴表示在线学习的每个学习步骤, 其中, 初始点t=0代表在初始的离线数据集上训练及测试得到的模型精度, 在线学习的过程从t=1时刻开始, 纵轴表示分类模型的测试精度.

图 2中, 在(0, 400)步为初始学习阶段, 这个阶段内模型因训练样本规模较小, 学习状态不稳定, 不同分组数据得到的测试精度波动位点差别较大, 如图 2(a)中t=140, 图 2(b)中t=53处分别存在有效波动位点且两者不一致.而在(400, 800)的在线学习步内某个时刻(如t=500)加入噪声, 图 2(a)和图 2(b)中显示模型测试精度在t=500时刻均发生了突然下降.而在(800, 915)内模拟真实概念漂移, 并在某个时刻(如t=819)突然改变新增样本分布, 两次模拟结果均在t=819处检测到真实的概念漂移位点.因此可以看到, 图 2中由于训练样本规模小而引起的分类器测试精度波动在不同分组中会在不同位点被检测到.基于此, 本文采用分组交叉检验的方法, 消除由于训练样本规模过小而导致的分类器测试性能波动给概念漂移检测带来的负面影响, 同时又不影响模型对于真伪概念漂移的检测过程.

3 基于在线性能测试的概念漂移检测

本文以流数据在线学习中由数据源分布变化引起的真实概念漂移以及由噪声样本或训练集规模过小而引起的伪概念漂移为研究对象, 提出了基于在线性能测试的概念漂移检测方法(CDPT), 包括有效波动位点检测、一致波动位点提取和概念漂移位点判定.有效波动位点检测环节通过监测在线学习分类器测试性能的变化, 采用分段动态提取的方式获得测试精度波动较大的位点作为有效波动位点; 一致波动位点提取环节通过对当前步骤中已获得的数据进行均匀分组, 并检测每组数据集上的有效波动位点, 然后取不同分组中的相同有效波动位点作为一致波动位点; 概念漂移位点判定环节通过跟踪检测到的一致波动位点之后近邻参考点的精度变化及收敛趋势, 比较漂移位点精度收敛偏差以判别概念漂移位点.本文中涉及到的有效波动位点、一致波动位点以及概念漂移位点之间的关系如图 3所示.

3.1 有效波动位点检测

在流数据在线学习过程中, 数据分布的改变可能导致分类器测试精度产生波动, 即发生概念漂移; 反之, 当数据分布一致时, 模型会稳步更新, 即分类器测试精度会保持相对稳定.假设第t步训练测试得到的模型精度为α_t, 则第t–1步训练测试得到的模型精度为α_t–1, 那么第t步与第t–1步的模型测试精度落差为

${d_t} = {\alpha _t} - {\alpha _{t - 1}}$

(1)

则一个完整的流数据在线学习过程中得到的一系列模型测试精度落差可表示为一个向量:

$ \boldsymbol{D} = {\rm{\{ }}{d_t}{\rm{\} }}_{t = 1}^T$

(2)

图 4展示了第2节中Image数据集上两次模拟流数据在线学习的测试精度落差.

图 4中所标注的模型出现明显测试精度落差现象的位置, 均已在图 2中被标注.另外, 流数据在线学习过程中不同时间段模型波动情况不同, 在初始学习阶段, 样本信息积累较少, 模型测试精度波动较大, 但是随着在线学习进程的推进, 在样本信息规模较大时, 模型变得相对稳定.因此, 为了能够更有效地挖掘不同学习阶段内的漂移现象, 本文将测试精度落差向量根据学习时间步骤平均分为3个子向量, 即D=[D_f; D_m; D_l](即分别对应在线学习过程的初期、中期和后期).在每个子向量中, 采用动态替换的方式选择n个有效波动位点, 即随着流数据挖掘的推进, 首先依次提取n个测试精度下降位点构成初始波动位点集, 并记录初始波动位点集中对应的测试精度下降幅度的最小值d_min, 然后继续选择后续的测试精度下降位点, 若后续位点的测试精度下降幅度大于当前波动位点集合中的最小下降幅度d_min, 则采用对应的后续位点代替当前波动位点集中的最小下降幅度对应的波动位点, 并更新波动位点集中对应的最小下降幅度d_min, 即更新波动位点集, 如此循环往复, 即可提取得到每个子向量上对应的n个下降幅度最大的波动位点, 构成相应的有效波动位点集.当数据集规模较大时, 由于每个下降位点都需要进行比较, 因此这种动态比较次数会较大, 位点的替换次数可能较多.此时, 可以设置一个精度落差临界阈值ε > 0, 只有当精度落差超过ε时, 才认为概念处于非稳定状态, 即当前位点作为波动位点参与比较和动态替换的过程, 反之, 则认为概念处于稳定状态, 不作为波动位点处理(当然, 虽然这种增加约束的动态调整替换方式提高了有效波动位点的提取效率, 但有可能导致某些区间上提取到的有效波动位点个数小于n, 此时, 一方面可以通过减小精度落差临界阈值ε来增加提取的波动位点个数, 也可以直接取实际提取的波动位点).记有效波动位点集合为E, 可知, 若满足式(3)的条件, 则认为概念处于非稳定状态, 且模型测试精度落差位点为波动位点.

$\left\{ {\begin{array}{*{20}{c}} {{d_t} < 0} \\ {\left| {{d_t}} \right| > \varepsilon } \end{array}} \right., {\rm{ }}t = 1, ..., T$

(3)

在实际应用中, 每个区间的有效波动位点个数n应该设置成一个恰当值, n值过大, 则有可能导致提取到的一致波动位点过多, 后续概念漂移检测的过程变得复杂且效率较低.反之, 若n值太小, 则可能检测不到实际存在的概念漂移位点.在处理实际的流数据挖掘问题时, 可以结合问题背景设置合适的有效波动位点提取个数参数, 比如类似于天气预报的流数据、股票检测的流数据, 数据发生概念漂移的模式比较频繁, 则可以设置较大的有效波动位点提取个数参数n值.反之, 在类似于系统故障诊断等一般情况下都比较稳定的流数据挖掘任务中, 则更应设置较小的有效波动位点提取个数参数.假设3个阶段内提取的有效波动位点集合分别表示为E_f、E_m和E_l, 则整个数据集上的有效波动位点集合为

$ \boldsymbol{E} = { \boldsymbol{E}_f} \cup { \boldsymbol{E}_m} \cup { \boldsymbol{E}_l}$

(4)

3.2 一致波动位点提取

由第2节分析可知, 由于训练样本规模过小而引起的模型测试精度波动是随机的, 为消除其对概念漂移检测的影响, 本文采用交叉检验的方式提取一致波动位点, 以减少由训练样本规模过小而导致的模型不稳定波动带来的问题.假设在线的训练样本集为$ \boldsymbol{S} = {\rm{\{ (}}{ \boldsymbol{X}_t}, { \boldsymbol{Y}_t}{\rm{)\} }}_{t = 0}^T, $将该训练集平均划分为k个互不重叠的子序列, 且每组数据集中包含相同规模的不同类别样本, 即:

$ \boldsymbol{S} = \cup _{i = 1}^k{ \boldsymbol{S}^i}$

(5)

采用第3.1节中的有效波动位点提取方法分别提取每个分组中的3n个有效波动位点, 不妨假设子数据流Sⁱ的有效波动位点集合为Eⁱ, 然后整合不同分组中的有效波动位点集合, 以消除训练样本规模过小而带来的精度波动问题, 整合过程为

$ \boldsymbol{W} = \cap _{i = 1}^k{ \boldsymbol{E}^i}$

(6)

其中, W为一致波动位点集.本文采用5折交叉检验的方式进行一致波动位点的提取.另外, 本文的方法尽管在第3.1节提取到的有效波动位点较多, 但经过一致波动位点提取后, 一方面, 避免了训练样本过小导致模型测试性能随机波动带来的概念漂移误检问题, 另一方面, 也大幅度减少了实际处理的波动位点个数, 提高了后续概念漂移检测的效率.

3.3 概念漂移位点判定

流数据发生真实概念漂移表明, 当前由历史数据训练得到的分类模型不再适用于新数据, 假定发生概念漂移后原始数据分布不再出现, 可知旧模型在新样本中得到的测试精度将持续降低, 最终趋于稳定, 如图 2所示中(800, 1000)步内所展示的模型测试精度趋势, 即使在某个时刻精度有所波动, 也很难恢复到最初状态.而噪声数据的表现形式则不同, 其所得到的模型测试精度的下降位点只存在于某一时刻或某一时间段内, 当样本恢复原始分布后, 模型测试精度也会相应提升.

基于上述分析, 概念漂移位点的判定可通过一致波动位点的后续近邻参考点对应的测试精度下降及收敛情况进行判定.这里定义一个模型测试精度的收敛偏差P, 以记录特定的一致波动位点后不同近邻参考点对应的模型测试精度的恢复情况, 以实时地区分当前一致波动位点处概念漂移的真伪性.假设当前检测到的一致波动位点为w, 则在其后续在线学习过程中, 第t步近邻参考点在线学习的测试精度收敛偏差P_t(w)定义为

${P_t}(w) = \frac{{{\alpha _t} - {\alpha _w}}}{{{\alpha _{w - 1}} - {\alpha _w}}}$

(7)

其中, α_t为一致波动位点w的近邻参考点t处模型得到的测试精度, α_w为一致波动位点处模型的测试精度, α_w–1为一致波动位点前一步所得到的测试精度.依据真实概念漂移与噪声引起的伪概念漂移在模型收敛速度上的差异性, 设置一致波动位点的近邻参考点精度收敛偏差临界阈值参数τ, 比较一致波动位点的近邻参考点对应的收敛偏差与临界阈值之间的关系, 若当前近邻参考点的测试精度收敛偏差大于给定阈值, 则从当前近邻参考点来看, 所对应的一致波动位点更趋向于发生了伪概念漂移, 反之, 则认为所对应的一致波动位点更趋向于发生了真实概念漂移.

对于收敛偏差的临界阈值参数设定, 本文采用动态放缩的方法, 且只考虑一致波动位点后续的5个近邻参考点.一致波动位点w的近邻参考点t的测试精度收敛偏差P_t(w)的临界阈值参数τ_t的设定方法可以表示为

${\tau _t} = \left\{ {\begin{array}{*{20}{l}} {0, \qquad \;\; \; t = w + 1{\rm{ }}} \\ {\frac{{{\alpha _{t - 2}} - {\alpha _{t - 1}}}}{{{\alpha _{w - 1}} - {\alpha _w}}}, {\rm{ }}t = w + 2, ..., w + 5} \end{array}} \right.$

(8)

采用这种动态调整的方法进行收敛偏差临界阈值的设定, 有助于进一步提高检测的效能.在概念漂移位点判定过程中, 对于某个一致波动位点w, 若前驱近邻参考点t–1判定其为真实概念漂移, 说明其具有明显的精度下降现象.为了后续近邻参考点t判定w为真实概念漂移的概率有所增加, 则应进一步扩大判定下降幅度, 当精度下降幅度足够大时, 说明真实概念漂移发生.反之, 若前驱近邻参考点t–1判定一致波动位点w为伪概念漂移时, 说明当前位点精度具有明显的回升.为了使得后继近邻参考点t判定w为伪概念漂移的概率有所增加, 则应进一步缩小判定恢复程度, 也即增大临界阈值.当精度仍具有回升趋势时, 可判定为发生伪概念漂移.

对于提取到的一致波动位点w, 依次计算每组子数据流Sⁱ中其近邻参考点的判定结果, 经过5个近邻参考点的判定, 若对于当前的一致波动位点w, k组子数据流得到的概念漂移位点平均判定值Cd(w)大于50%, 则认为当前一致波动位点为真实的概念漂移位点, 否则认为, 当前一致波动位点为由噪声引起的伪概念漂移位点.一致波动位点的平均判定值计算可表示如下:

$Cd(w) = \frac{1}{k}\sum\nolimits_{i = 1}^k {\frac{{\sum\nolimits_{t = w + 1}^{w + 5} {f(P_t^i(w) \leqslant \tau _t^i)} }}{5}} $

(9)

其中, $P_t^i(w)$代表一致波动位点w在子数据流Sⁱ中的近邻参考点t处的测试精度收敛偏差, $\tau _t^i$代表子数据流Sⁱ中近邻参考点t对应的测试精度收敛偏差临界阈值参数, 函数f(X)为条件判别函数, 即当条件X成立时, 该函数取值为1, 否则, 取值为0.这里需要注意区分标号t和i, 其中, 标号t的取值从w+1到w+5代表一致波动位点的近邻参考点, 它们用来判定一致波动位点是否为真实的概念漂移位点; 而标号i的取值从1到k代表对整个流数据集均匀划分为k个子数据流, 即通过采用交叉检验的方法消除由于训练样本规模过小而带来的随机波动.

3.4 CDPT算法

本文提出的基于在线性能测试的概念漂移检测方法通过分析真实概念漂移、由噪声引起的伪概念漂移及由训练样本规模过小导致的伪概念漂移之间的异同, 并充分利用分类模型在相邻在线学习时间单元中预测精度表现出的不同趋势, 对概念漂移进行检测.由于支持向量机(support vector machine, 简称SVM)建立在传统学习理论和结构风险最小化基础之上, 具有良好的泛化性, 较强的鲁棒性等优势^[24], 因此本文在模拟流数据在线学习实验的过程中, 以SVM作为基准分类器, 以SVM增量学习方式进行在线学习.本文所提出的方法构造了模型测试精度波动的落差向量, 通过动态调整替换的方式提取有效波动位点; 通过交叉检验, 比较不同分组波动位点的一致性, 提取一致波动位点; 最后, 通过一致波动位点近邻参考点的模型测试精度恢复情况, 来判别最终的概念漂移位点.具体算法如下.

算法.基于在线性能测试的概念漂移检测.

初始化.流数据序列$ \boldsymbol{S} = {\rm{\{ (}}{ \boldsymbol{X}_t}, { \boldsymbol{Y}_t}{\rm{)\} }}_{t = 0}^T, $其中, {X₀, Y₀}为初始离线样本, X_t∈Rⁿ和Y_t∈{–1, +1}, 测试集TS, 其与初始训练集符合独立同分布;

Step 1.将流数据S按照式(5)划分为k个子序列, 即:$ \boldsymbol{S} = \cup _{i = 1}^k{ \boldsymbol{S}^i};$

Step 2.分别对每个子序列并行进行在线学习, 记录每次学习得到的准确率α;

Step 3.根据式(1)计算得到每个子序列Sⁱ对应的测试精度落差向量Dⁱ, 并将其根据学习时间步骤平均分为3个子向量, 即${ \boldsymbol{D}^i} = [ \boldsymbol{D}_f^i; \boldsymbol{D}_m^i; \boldsymbol{D}_l^i]$, 然后采用第3.1节中动态替换的方式在线提取每个子向量中满足式(3)的n个最大值(不足n个的取实际满足式(3)的所有位点), 然后按照式(4)得到每个子序列Sⁱ上对应的有效波动位点集合Eⁱ;

Step 4.根据式(6)得到整个数据集上的一致波动位点集合W;

Step 5.根据式(7)计算每个一致波动位点w后续5个近邻参考点t的收敛精度偏差P_t(w), 并采用式(8)动态设置精度收敛偏差阈值τ, 对于每个一致波动位点w, 根据每个子数据流中收敛精度偏差和临界值τ的大小关系, 根据式(9)计算一致波动位点对应的平均判定值Cd(w), 若其大于50%, 则该一致波动位点为预测的概念漂移位点, 否则该一致波动位点为噪声引起的伪概念漂移位点;

Step 6.分析数据流中概念漂移的检测情况, 即将检测到的概念漂移位点与数据集中存在的真实概念漂移位点及噪声位点进行对比分析, 这里, 所有在真实概念漂移位点近邻范围内捕获的预测概念漂移位点均被认为准确检测到了概念漂移;

Step 7.算法结束.

4 实验与性能分析

为验证本文所提出的真伪概念漂移检测算法中近邻参考点对于概念漂移位点检测的平均判定值及概念漂移的检测情况(误检、漏检、延时等), 本文分别在7个标准数据集和3个真实数据集上对算法进行了测试.实验平台为Windows 7, CPU为酷睿i5-3210, 内存为8GB, 开发环境为Matlab 2016b.实验中, 将本文提出的基于在线性能测试的概念漂移检测方法与目前主要的两类概念漂移检测方法, 即基于滑动窗口的概念漂移检测方法SWCDS^[5]和基于自适应集成学习的漂移检测算法CDOL^[17]进行了对比.

4.1 数据集

1) UCI标准数据集:选择UCI数据集的目的在于其可以方便地模拟各种存在概念漂移及噪声的环境, 设置真实的概念漂移发生位点及由噪声引起的伪概念漂移位点, 有利于发现算法在不同噪声环境下的概念漂移检测性能.为确保数据环境的稳定, 在训练集中利用正反例互换形式使得每个数据集中存在两种不同概念.具体所用到的7个数据集的详细信息见表 1.

2) 真实数据流:实验选择了真实数据库MITface数据集、Usps数据集^[17]以及KDDCup99^[25]数据集.其中, MITface来自MIT的人脸数据库, Usps来自美国邮政手写数据集, KDDCup99数据集是网络入侵检测竞赛的测试数据, 该数据集常用于模拟漂移数据验证检测漂移算法的有效性, 实验中对该数据集进行抽样压缩, 抽样后各类别数量比例仍与原数据集相同.表 2给出了3个真实数据集的具体信息描述.

4.2 评估指标

本文主要从如下3个方面评价方法的性能.

首先, 对于概念漂移位点判定的步骤中, 采用平均判定值(见式(9))来衡量采用近邻参数法进行真伪概念漂移判定时, 近邻参考点对于概念漂移位点的平均决策值.

其次, 对于最终的概念漂移检测结果, 本文提出漏检率(MDR)和误检率(FDR)两个指标进行度量, 漏检率用于衡量实际的概念漂移位点中没有被检测到的概率; 误检率代表检测到的概念漂移位点中没有发生概念漂移的概率.在概念漂移检测问题中, 大多数模型携带部分旧样本信息, 因此检测到的正确概念漂移位点多数情况下会比实际插入概念漂移的位点有一定延时, 本文把实际插入概念漂移的位点后续5个近邻检测到的概念漂移位点均视为正常检测.假设实验中得到的一致波动位点集合为W, 其中, 根据近邻参考点判定为概念漂移的一致波动位点集合为W^T.假设真实的概念漂移插入位点为$ \boldsymbol{C} = {\rm{\{ }}{c_i}{\rm{\} }}_{i = 1}^3$(其中, c₁、c₂、c₃分别为在流数据前期/中期/后期不同阶段插入的真实概念漂移位点), 则漏检率为

$MDR = \frac{{\left| {{\rm{\{ }}{c_i}\left| {{w^t} \notin { \boldsymbol{C}_i}{\rm{[}}5{\rm{] \& }}{w^t} \in { \boldsymbol{W}^T}} \right.{\rm{\} }}} \right|}}{{\left| \boldsymbol{C} \right|}}$

(10)

其中, C_i[5]代表由实际插入概念漂移位点c_i及其连续后继5个位点构成的集合, 即${ \boldsymbol{C}_i}{\rm{[}}5{\rm{] = \{ }}{c_i}{\rm{ + }}j{\rm{\} }}_{j = 0}^{j = 5}$, 因此漏检率即反映了实际插入概念漂移的位点中在允许的延时范围内均未检测到概念漂移的概率.而误检率则表示为

$FDR = \frac{{\left| {{\rm{\{ }}{w^t}\left| {{w^t} \notin { \boldsymbol{C}_i}{\rm{[}}5{\rm{] \& }}{w^t} \in { \boldsymbol{W}^T}} \right.{\rm{\} }}} \right|}}{{\left| {{ \boldsymbol{W}^T}} \right|}}$

(11)

误检率反映了判定为概念漂移的位点中不在实际插入概念漂移位点允许延时范围内的概率.显然, 检测结果评测中, 得到的漏检率和误检率越低, 说明模型对于概念漂移检测和识别能力越好.

此外, 由于概念漂移检测问题中, 判定为概念漂移的位点多数情况下会比实际插入概念漂移的位点有一定延时, 因此, 实验中还衡量了实际插入概念漂移位点的检测延时, 其定义如下:

$Dela{y_{{\rm{(}}{c_i}{\rm{)}}}} = \left\{ \begin{array}{l} \mathop {{\rm{min}}}\limits_{{w^t} \in { \boldsymbol{C}_i}{\rm{[}}5{\rm{]}}} {\rm{(}}{w^t} - {c_i}{\rm{)}}, \;\;\;{\rm{ }}\exists {w^t} \in { \boldsymbol{W}^T}, {w^t} \in { \boldsymbol{C}_i}{\rm{[}}5{\rm{]}} \\ + \infty , \qquad \; \qquad \; \qquad {\rm{ }}\forall {w^t} \in { \boldsymbol{W}^T}, {w^t} \notin { \boldsymbol{C}_i}{\rm{[}}5{\rm{]}} \\ \end{array} \right.$

(12)

概念漂移检测延时有效评估了在线检测概念漂移发生位点的实时性和精准性, 延时越小, 表明算法对于概念漂移的检测越敏感.由于每个真实的概念漂移位点及其连续后继5个位点中检测到概念漂移, 均视为正确检测到了概念漂移, 因此检测延时的取值范围为[0, 5].

4.3 参数设置

本节对实验模型检测概念漂移影响参数进行讨论, 以研究模型参数对方法性能的影响, 进而实现模型的有效推广.概念漂移检测过程中对于有效波动位点的提取个数n决定着后续一致波动位点的提取数量以及得到的一致波动位点能否覆盖到真实概念漂移位点, 它的设定对模型的检测性能起着重要作用.为了获得最为合适的n值, 针对由不同n值实验后得到的FDR和MDR决策值进行分析讨论.为简洁起见, 本文仅介绍UCI标准数据集German的具体分析过程.图 5给出了不同n值情况下得到的FDR和MDR决策值(参数设置:惩罚参数C=1000, 在线学习步长O=5).图中横轴表示提取有效波动位点个数n, 本文在测试过程中取值为n={5, 10, 15, 20}, 纵轴表示在对应取值情况下得到的FDR和MDR.

从图 5可以看出, 随着有效波动位点提取个数的增加, FDR呈持续上升趋势, 相反地, MDR呈现下降趋势.由上一节分析可知, FDR和MDR结果越小, 则模型对概念漂移检测性能越好.因此, 为了让有效波动位点提取数n对评估结果起到正面作用, 通过权衡n的取值与评估标准之间的变化趋势关系, 将有效波动位点提取个数n值取[10, 20]区间内的整数是较好的选择.考虑到n的取值越大, 检测到的有效波动位点越多, 增加计算时间, 取值太小又不能完全覆盖真实概念漂移位点, 在本文实验中, 将每个学习阶段的有效波动位点提取个数取值为15, 即整个流数据上最大提取到的有效波动位点不超过45个.

因为本文实验采用的是动态替换的方式选择n个有效波动位点, 因此根据第3.1节所给出的描述, 实验中将得到的测试精度下降幅度的最小值d_min赋值给精度落差临界阈值ε, 即ε=|d_min|, 然后继续进行后续的测试.当d_min更新之后, 相应地也将ε进行更新.

为检验本文提出的概念漂移检测方法的性能, 本文对不同大小的在线学习单元、不同概念漂移发生位置以及噪声对概念漂移检测的影响等多个方面进行了测试.首先, 由于在线学习过程中, 每个时间单元内到达的样本数量对于模型有较为明显的影响, 因此, 本文分别对每个时间单元内到达的样本数目为O={1, 5, 10, 20}的各个子数据流进行测试.其次, 由于数据流挖掘过程中, 不同位置分类器所能采集到的样本数量和有效信息有一定差异, 概念漂移位点所反映出来的模型测试性能也会有所不同, 因此, 实验中分别设置G={10, $\left\lceil {T/2} \right\rceil $, T–50}这3个位点作为概念漂移及噪声的插入位点(其中, T为流数据中存在的学习单元个数), 以反映本文方法在流数据分类前期/中期/后期不同阶段概念漂移检测的性能, 后续的实验结果均为3个不同阶段位点测试结果的均值.此外, 为分析噪声引起的伪概念漂移对结果的影响, 以反映本文提出的基于在线性能测试的概念漂移检测方法对于噪声的鲁棒性, 实验中在与概念漂移相同的位置插入噪声的同时进行了检测.实验中SVM采用高斯核, 核参数p取默认值, 即p=1/n(其中, n为样本维度), SVM惩罚参数C取1 000, SVM本身的模型选择不是本文重点研究的问题, 相关方法可参考文献[26].实验中, 采用的概念漂移检测对比方法SWCDS和CDOL的参数选择分别参考文献[5, 17].

4.4 实验结果与分析

由于流数据在线学习过程中噪声是不可避免的, 因此有效区分噪声引起的伪概念漂移和真实概念漂移对在线学习算法的抗噪性具有重要作用.图 6展示了本文提出的CDPT方法中近邻参考点对于概念漂移位点的平均判定值, 用于反映近邻参考点对于真实概念漂移的贡献和对于伪概念漂移的识别情况.图中横轴表示不同的数据集, 纵轴表示近邻参考点对于概念漂移的平均判定值, “^*”表示判定值的平均值.平均判定值越大, 则采用近邻参考点的方法对于概念漂移检测的贡献率越大, 这里需要注意的是, 实验中统计的是真实概念漂移位点及其后续5个近邻位点中的一致波动位点, 因为这些点均被认为是真实概念漂移附近的一致波动位点, 其平均判定值大小才能准确反映近邻参考点对于真实位点的判定情况.

从图 6可以看出, 除了数据集KDDCup之外, 所用到的数据集对应的概念漂移平均判定值的均值都在60%以上, 且最大值与最小值之间的差异不大, 这充分说明在多数数据集上, 近邻参考点对于概念漂移位点具有较好的判定准确性, 同时能够有效区分噪声样本引起的伪概念漂移.而在数据集KDDCup检测结果中, 存在部分真实概念漂移位点邻域内的一致波动位点多数被误判为噪声的情况, 造成这种结果的原因是, 在线处理的数据单元过小, 概念漂移检测不及时所致.另外, 数据集KDDCup为严重非平衡分布的数据集, 个别类别不足其他类别样本规模的百分之一, 因此在概念漂移过程中无法检测到极少数类样本存在的漂移问题.

漏检率用于检验概念漂移检测算法对真实概念漂移位点检测的完备性(类似召回率), 即能否对每一次真实概念漂移的发生都精确地检测到.较低的漏检率能够说明算法可以识别尽可能多的概念漂移位点.图 7记录了本文提出的CDPT概念漂移检测算法在不同规模的数据单元下的概念漂移漏检率, 其中, “CDPT+O”代表本文提出的CDPT方法, 且其对应的在线数据单元规模为x.由于模拟实验中只在前期、中期、后期分别插入了一个真实的概念漂移位点, 因此, 这里概念漂移的漏检率取值只有0、1/3、2/3和1这4个值.

从图 7可以看出, 当在线学习的数据单元规模扩大时, CDPT算法得到的漏检率减小, 即在线学习数据单元规模越大, 概念漂移被检测到的概率就越大.另一方面, 当数据块较小时(如O=1), 每个在线时间单元内到达的数据单元包含的样本数较少, 以至于单次训练不足以引起模型预测结果产生明显波动, 因此, 相应地插入概念漂移的位点也很难被准确检测.实验发现, 其他两种概念漂移检测方法SWCDS与CDOL随着在线数据单元规模的扩大, 漏检率也相应减小(这里没有专门列出), 表 3列出了CDPT算法与其他两种传统概念漂移检测算法在同一数据单元规模参数下(O=20)的漏检率取值结果.

从表 3可以看出, 与传统的SWCDS和CDOL两种概念漂移检测算法相比, 相同条件下本文提出的基于在线性能测试的CDPT算法能够更准确地检测到漂移的发生位点, 且发生漏检的几率更小.

误检率是检验概念漂移检测算法对漂移检测的精准性, 即用于衡量检测到的概念漂移位点中并未真实发生概念漂移的比例.较低的误检率能够说明算法对于由于训练样本规模过小或在线流数据中存在噪声等引起的伪概念漂移有足够的鲁棒性, 即尽可能地不将伪概念漂移位点错误地识别为概念漂移位点.图 8分别给出了不同算法在多个数据集中的误检率实验结果, 图中横轴表示不同在线学习数据单元规模的CDPT算法与其他对比算法(对比算法对应的在线学习数据单元为固定值O=20), 图中灰色虚线条形表示当前方法未检测到概念漂移位点, 因此误检率分母为0.

从图 8可以看出, 对于本文提出的CDPT算法, 当在线学习数据单元为1时, 检测效果并不好, 其中, 在数据集Breast_cancer、Diabetis、German、Spambase以及KDDCup上未检测到概念漂移位点, 而其在数据集Image、Thyroid和USPS上得到的误检率却最小, 这充分说明, 当在线学习数据单元取1时, 每次只有一个样本新加入参与训练, 由于在线学习模型中可能包含较多的历史数据信息, 因此概念漂移发生后过小的在线数据单元有可能不足以引起模型的有效波动, 因此模型表现不稳定.其次, 从实验结果可以看出, 除了在线学习单元过小的情形之外, 本文提出的CDPT方法的概念漂移误检率基本在20%~50%左右浮动, 而对比的两个概念漂移检测算法SWCDS和CDOL, 其概念漂移的误检率一般都达到80%以上, 明显大于本文提出的CDPT算法, 特别是CDOL方法在许多数据集上会存在检测不到概念漂移的现象.因此, 本文提出的CDPT算法能够以较小的代价(检测到的概念漂移位点数少)检测到真实存在的概念漂移位点, 可有效提高概念漂移检测的性能.

从表 4可以看出, 本文提出的CDPT算法在学习单元为1时, 尽管概念漂移平均检测延时小, 但其存在很多检测不到真实概念漂移位点的情况, 即说明很小的学习单元的分布变化不足以使模型分类准确率发生显著改变, 分类器准确率下降缓慢, 无法检测到概念漂移; 但是随着在线学习单元的增大, 尽管概念漂移检测的平均延时略有增加, 但检测不到概念漂移的情况能够被有效避免, 特别地, 当在线学习数据单元规模达到20时, 在所有数据集上, 在线学习的前期、中期、后期的概念漂移位点都能被CDPT方法有效地检测到.表 5列出了在线数据单元为20时, CDPT算法与其他两种对比算法的平均检测时延.

从表 5统计的概念漂移检测方法的漂移平均检测延时对比结果可以看出, 与SWCDS算法相比, 本文提出的CDPT算法平均检测延时要明显更小, 且对比的SWCDS算法在多数情况下都未检测到概念漂移, 这是由于本文把实际插入概念漂移的位点后续5个近邻检测到的概念漂移位点均视为检测正常检测, 而SWCDS算法在流数据学习的中期和后期的平均检测时延都达到20~30个位点, 因此, 在中期和后期插入概念漂移的多数情况下都没有检测到概念漂移.尽管CDOL在部分数据集上的平均检测延时很短, 但其在很多数据集上所有的概念漂移都未检测到, 这说明该方法对数据集分布高度敏感, 缺乏通用性.由此可见, 与其他两种对比方法相比, 本文提出的基于在线性能测试的概念漂移检测方法能够更及时地检测到流数据中不同位置发生概念漂移的位点, 可以广泛地应用于不同分布的数据集.

综上可以看出, 本文提出的基于在线性能测试的概念漂移检测方法通过采用分组交叉检验提取一致波动点的方式去除由于训练样本过小而引起的伪概念漂移, 通过分析一致波动点的近邻参考点测试性能的大小及收敛情况去除了由于噪声引起的伪概念漂移, 检测结果具有较低的误检率和漏检率, 即能够准确、充分地识别流数据中发生的概念漂移, 同时其检测延时较小, 可以更加实时地检测概念漂移的发生, 符合流数据学习中高时效性要求的特点.

5 结束语

针对动态流数据中存在的伪概念漂移混淆引起真实概念漂移检测困难的问题, 本文提出一种基于在线性能测试的概念漂移检测算法, 通过对流数据学习中获得的当前数据分组, 并对每组进行在线学习测试, 根据每个分组相邻测试精度之间的精度落差判断有效波动位点.然后, 采用交叉检验方式, 精度波动的一致性提取一致波动位点.最后通过跟踪一致波动位点的近邻参考点测试精度的下降幅度和收敛速率来进一步减小噪声引起的伪概念漂移对真实概念漂移检测的负面影响, 准确区分概念漂移的真伪性.本文所提出的方法能够在流数据在线学习过程中准确、充分地检测到概念漂移的发生, 具有较低的漏检率和误检率, 且平均检测延时短, 检测结果具有较好的时间效能.同时, 基于在线性能测试的方法对于流数据中存在的伪概念漂移有较高的识别能力, 在真伪概念漂移同时存在且未知的环境下, 能够有效地检测概念漂移并区分其真伪性, 减小噪声及训练样本过小而导致的流数据在线学习及概念漂移检测困难的问题.