面向信息系统推荐与决策的高阶张量分析方法

王贝伦; 张嘉琦; 蔡英豪; 王兆阳; 谈笑; 沈典

doi:10.7544/issn1000-1239.202330624

面向信息系统推荐与决策的高阶张量分析方法

东南大学计算机科学与工程学院　南京　210096

基金项目: 国家自然科学基金项目（61906040，61972085，62276063, 6227072991）；江苏省自然科学基金项目（BK20190345，BK20190335，BK20221457）；国家重点研发计划项目（2022YFF0712400）；中央高校基本科研业务费专项资金（2242021R41177）

详细信息

作者简介:
王贝伦: 1990年生. 博士，副教授. 主要研究方向为大规模机器学习、图模型、多任务学习

张嘉琦: 1997年生. 博士研究生. 主要研究方向为图模型、大规模优化

蔡英豪: 2002年生. 本科生. 主要研究方向为图神经网络、知识图谱、机器学习

王兆阳: 2000年生. 硕士研究生. 主要研究方向为机器学习、软硬件算法加速

谈笑: 2000年生. 博士研究生. 主要研究方向为图模型、大规模机器学习、元学习

沈典: 1988年生. 博士，副教授. 主要研究方向为云（边缘）计算、网络智能、智能算法及应用

通讯作者:
沈典（dshen@seu.edu.cn）

中图分类号: TP391
计量
- 文章访问数: 118
- HTML全文浏览量: 46
- PDF下载量: 45
出版历程
- 收稿日期: 2023-07-30
- 修回日期: 2024-02-01
- 网络出版日期: 2024-05-16
- 刊出日期: 2024-06-30

High-Order Tensor Analysis Method for Information System Recommendations and Decisions

School of Computer Science and Engineering, Southeast University, Nanjing 210096

Funds: This work was supported by the National Natural Science Foundation of China (61906040, 61972085, 62276063, 6227072991), the Natural Science Foundation of Jiangsu Province (BK20190345, BK20190335, BK20221457), the National Key Research and Development Program of China (2022YFF0712400), and the Fundamental Research Funds for the Central Universities (2242021R41177).

More Information

Author Bio:
Wang Beilun: born in 1990. PhD, associate professor. His main research interests include large-scale machine learning, graphical model, and multi-task learning

Zhang Jiaqi: born in 1997. PhD candidate. His main research interests include graphical model and large-scale optimization

Cai Yinghao: born in 2002. Undergraduate. His main research interests include graph neural network, knowledge graph, and machine learning

Wang Zhaoyang: born in 2000. Master candidate. His main research interests include machine learning and software-hardware algorithm acceleration

Tan Xiao: born in 2000. PhD candidate. Her main research interests include graphical model, large-scale machine learning, and meta-learning

Shen Dian: born in 1988. PhD, associate professor. His main research interests include cloud (edge) computing, network intelligence, and intelligent algorithms and applications

摘要

摘要:
张量数据（或多维数组）在各个行业的信息系统中广泛存在，例如医疗系统中的功能性磁共振成像（fMRI）数据和商品数据信息系统中的用户-产品数据. 将这些数据用以预测张量特征与单变量响应之间的关系，可以实现数据赋能，提供更精准的服务或解决方案，例如疾病决策诊断或商品推荐. 然而，现有的张量回归方法存在2个主要问题：一是可能丢失了张量的空间信息，导致预测结果不准确；二是计算成本过高，导致服务或解决方案不及时. 对于具有高阶结构的大规模数据而言，这2点则显得更为突出. 因此为了实现数据赋能，即利用张量数据来提高信息服务或解决方案的质量和效率，提出了稀疏低秩张量回归模型（sparse and low-rank tensor regression model，SLTR）. 该模型通过对张量系数应用 ${\mathscr{l}}_{1}$ 范数和张量核范数使得张量系数具有稀疏性和低秩性两大特点，这样既保留了张量的结构信息又可以方便地解释数据. 利用近端梯度方法优化了混合正则化器，使得求解过程可扩展且高效. 除此之外证明了SLTR的严格误差界. 在多个模拟数据集和一个视频数据集上的实验结果表明，SLTR相比于之前的方法，在更短的时间内获得了更好的预测性能.
- 张量回归 /
- 并行近端法 /
- 数据可解释性 /
- 张量范数 /
- 分类
Abstract:
Tensor data (or multi-dimensional array data) are often generated in information systems of various industries, such as functional magnetic resonance imaging (fMRI) data in medicine systems and user-product data in product information systems. By using these data to predict the relationship between tensor features and univariate responses, data empowerment can be achieved, providing more accurate services or solutions, such as disease decision diagnosis or product recommendations. Currently available tensor regression methods, however, present two major shortcomings: the spatial information of tensors may be lost in these models, resulting in inaccurate prediction results; the calculation cost is too high, which results in untimely solutions or services. The two problems are more severe for large-scale data with high-order structures. Therefore, in order to achieve data empowerment, that is, to use tensor data to improve the quality and efficiency of information services or solutions, we propose sparse and low-rank tensor regression model (SLTR). This model enforces sparsity and low-rankness of the tensor coefficient by directly applying ${\mathscr{l}}_{1}$ norm and tensor nuclear norm on it respectively, such that not only the structural information of the tensor is preserved but also the data interpretation is convenient. To make the solving procedure scalable and efficient, SLTR makes use of the proximal gradient method to optimize the hybrid regularizer, which can be easily implemented parallelly. Additionally, a tight error bound of SLTR is theoretically proved. We evaluate SLTR on several simulated datasets and one video dataset. Experimental results show that, compared with previous models, SLTR is capable to obtain a better solution with much fewer time costs.
- tensor regression /
- parallel proximal method /
- data interpretation /
- tensor norm /
- classification
此处没有直接将这些范数函数应用于张量数据. 请注意， ${\mathscr{l}}_{1}$ 范数和张量核范数都可以轻松地重新表示为多个矩阵范数的组合，可以直接定义它们以及张量上相应的双范数，参见式（7）. 关于对偶范数的详细内容见附录C.

HTML全文

近些年来，流数据在网络安全、智慧城市、气象预测等多个领域大量涌现. 流数据作为一种重要的数据类型，具有持续产生、实时性强、规模巨大且数据分布动态变化等复杂特性，这给流数据挖掘任务带来了极大挑战^[1-5]. 概念漂移是指随着时间推移或数据分布发生变化，样本的输入特征和输出标签之间的关系也发生改变的现象^[6-9]. 此时集成模型由于没有及时学习到新的数据分布特征从而导致性能会下降.

基于集成学习的方法^[10-12]利用历史数据构建基学习器，并借助特定的投票机制（如加权平均、组合投票等）进行集成决策，以此得到比单一基学习器更好的效果，解决了单一基学习器在流数据挖掘中不能把握全局信息的问题，因此利用集成学习处理概念漂移是一种有效可行的手段. 然而，传统集成学习方法在漂移发生后不能对新数据分布及时做出响应，且通常认为历史数据不再适用，如果这些数据中含有对当前模型学习有帮助的样本知识，直接丢弃则会造成已有资源的浪费. 此外，流数据分布变化方式的多样性易产生不同类型的概念漂移（如突变型和渐变型），不同类型漂移的数据分布变化跨度、变化快慢、变化方式等都不相同^[13]，然而多数在线集成模型只关注单一类型，不能针对漂移类型进行自适应建模.

为解决上述问题，本文提出一种面向不同类型概念漂移的两阶段自适应集成学习方法（two-stage adaptive ensemble learning method for different types of concept drift，TAEL）. 该方法从解决不同类型的概念漂移问题入手，检测漂移跨度以确定漂移类型，并构建了针对类型的“过滤-扩充”两阶段样本处理机制. 一方面在样本过滤过程中，根据漂移类型创建非关键样本过滤器，过滤掉历史样本中的非关键因素，保证剩余的历史关键样本块的数据分布更加接近当前数据分布；另一方面在样本扩充过程中，根据漂移类型确定合适的抽样规模，由当前数据块中各个类别的规模占比设置历史关键样本的抽样优先级，并确定抽样概率，按照抽样概率进行分块优先抽样，以扩充当前样本块，为当前样本块补充样本特征的同时缓解了块内类分布不平衡. 本文工作的主要贡献有3方面：

1）通过检测漂移跨度确定概念漂移类型，为不同类型漂移的自适应集成建模提供了一种可行方案；

2）通过对历史数据中非关键样本的过滤，使更新后的历史数据分布更接近最新数据分布，提高了历史基学习器的有效性；

3）通过对当前数据的扩充，缓解了当前基学习器的欠拟合问题，提高了基学习器的稳定性.

1. 相关工作

目前，对含概念漂移的流数据挖掘的处理策略主要包括基于实例选择的方法和基于集成学习的方法. 基于实例选择的方法通常使用滑动窗口技术来实现，其基本思想是将数据流分成固定大小的窗口，通过窗口的向前滑动来实现对概念漂移的检测和处理. ADWIN^[14]通过计算子窗口之间的均值差异来判断是否发生了概念漂移. DDM^[15]通过持续监视窗口内的数据样本分类错误率来检测概念漂移. STEPD^[16]通过比较最近窗口和整个窗口来检测错误率变化. DWCDS^[17]提出一种双窗口机制来周期性地检测概念漂移，并对模型进行动态更新以适应概念漂移. CD-TW^[18]首先创建2个分别加载历史数据和当前数据的基础节点时序窗口，通过比较二者包含数据的分布变化情况来检测概念漂移. CDT_MSW^[19]由单个基本滑动窗口和单个基本静态窗口来检测概念漂移.

使用集成学习处理含概念漂移流数据的研究已经取得了很多成果和进展，基于集成学习的方法大体可分为2类：在线集成和基于数据块的集成.

在线集成是一种对样本进行逐一处理的增量学习方法. 基于单样本的增量模型方法^[20]首先初始化一组基分类器，使用每个时间戳下到达的单个样本更新集成模型，然后对基分类器进行加权组合. DOED^[21]通过维护低多样性和高多样性的在线加权集成，从而准确地处理各种类型的漂移. 基于混合标记策略的在线主动学习集成框架^[22]由一个长期固定分类器和多个动态分类器组成来适应概念漂移. CBCE^[23]为每个类维护一个基学习器，并在有新样本时更新基学习器. 在线集成学习方法能够有效提高模型的实时泛化性能，但由于需要逐一处理样本，增加了计算资源，易导致学习效率较低.

基于数据块的集成是一种对固定数量的输入实例进行处理的方法. SEA^[24]在连续的数据块上构建基分类器，并且使用启发式替换策略组合成固定大小的集成模型. DWMIL^[25]，ACDWM^[26]为每个数据块创建一个基学习器，通过根据基学习器在当前数据块上的分类性能进行动态加权集成. SRE^[27]在基于块的框架中保留一部分先前少数样本以平衡当前块的类分布. DUE^[28]为每个数据块创建若干候选分类器，对其进行分段加权，并通过动态调整分类器权重来解决概念漂移问题. SEOA^[29]将神经网络的不同层次作为基分类器进行集成，根据各基分类器在当前数据块上的决策损失进行动态加权，以实现稳定性与适应性的平衡. 然而，划分的数据块的大小通常会影响模型的性能和训练速度，因此，选择合适的数据块大小很重要.

与传统方法相比，本文提出的TAEL方法能够充分利用新旧样本信息，根据漂移类型针对性地采用两阶段样本处理机制更新历史样本块和当前样本块，实现了集成模型在概念漂移发生后对新数据分布的快速响应.

2. 面向不同类型概念漂移的两阶段自适应集成

本文提出的TAEL方法的模型总体结构如图1所示. 在漂移类型检测阶段，通过检测漂移跨度span确定漂移类型. 在两阶段自适应集成阶段，首先根据漂移类型创建非关键样本过滤器F，过滤掉历史样本集D上的非关键样本，然后对剩余的历史关键样本 $\hat D$ 进行分块优先抽样Sampling，根据漂移类型确定合适的抽样规模M，并根据样本所属类在当前样本块的规模占比设置抽样优先级α，由α获得抽样概率P，按照P抽取一定规模的关键样本子集 $\widetilde D$ 来扩充当前数据集D_t. 在更新后的历史样本集和当前样本集中训练得到具有更高有效性的基学习器，提升了集成模型的实时泛化性能.

图 1 TAEL模型总体结构图

Figure 1. The overall structure of the TAEL model

下载: 全尺寸图片幻灯片

2.1 漂移类型检测

流数据是指实时、连续、无限、随时间不断变化的数据序列，时刻t到达的样本由具有联合概率分布 ${P_t}({\boldsymbol {x}},y)$ 的数据源产生. 在流数据挖掘任务中，样本分布的不稳定和动态变化等因素导致流数据中隐含的目标概念发生改变，即概念漂移，其本质可看作流数据的联合概率分布发生变化：

${P_{t - 1}}({\boldsymbol{x}},y) \ne {P_t}({{\boldsymbol {x}}},y) .$

(1)

为了根据不同类型漂移有针对性地更新集成模型，首先在概念漂移位点处进行漂移类型检测. 本文通过计算span来检测漂移类型. span由漂移开始位点和漂移结束位点间相距的时间跨度确定. 本文判断漂移是否结束的依据是后序数据分布是否已经稳定. 已知漂移开始位点a，选取该位点后序的L个连续数据块 ${D_{{{a}} + 1}},{D_{{{a}} + 2}}, … ,{D_{a + L}}$ ，在这些数据块上训练得到基学习器 ${f_{{{a}} + 1}},{f_{{{a}} + 2}}, … ,{f_{a + L}}$ ，并得到在当前数据块上的实时预测精度 $ac{c_{{{a}} + 1}},ac{c_{{{a}} + 2}}, … , ac{c_{a + L}}$ . 计算实时预测精度的方差：

${s^2} = \frac{{\sum\limits_{l = 1}^L {{{(ac{c_{a + {{l}}}} - \overline {acc} )}^2}} }}{L} ,$

(2)

其中 $\overline {acc}$ 为实时预测精度的平均值. s²反映了L个基学习器的预测差异，同时反映出位点 $a$ 的后序数据分布的稳定程度. 若 ${s^2} < \delta$ （ $\delta$ 为漂移稳定性参数），则认为位点 $a + 1$ 为漂移结束位点， $span = 1$ ；若s²≥ $\delta$ ，则认为漂移仍未结束，接着从位点 $a + 1$ 开始继续上述操作，直到得到漂移结束位点b， $span = b - a$ ；若 $span > \theta$ （θ为漂移类型参数），则判定此次漂移为渐变型，否则判定此次漂移为突变型. 漂移类型检测过程如图2所示.

图 2 漂移类型检测过程

Figure 2. Drift type detection process

下载: 全尺寸图片幻灯片

2.2 “过滤-扩充”两阶段自适应集成学习

为充分利用当前漂移场景的样本信息和有选择地利用历史样本信息以提高集成模型在概念漂移发生后对新数据分布的适应性，本文提出“过滤-扩充”两阶段自适应集成学习方法. 过滤阶段通过过滤非关键样本以帮助历史样本块筛选接近当前数据分布的关键样本，扩充阶段通过向当前数据集补充过滤后保留的历史关键样本以弥补其缺少的样本特征.

2.2.1 样本过滤策略

由于历史样本中含有大量样本信息，而非关键样本会导致该数据集上模型的有效性降低. 为“筛掉”这些无用信息，提高样本质量，使历史数据分布更接近当前数据分布，本文提出一种样本过滤策略，通过创建非关键样本过滤器F过滤掉历史非关键样本. 考虑到不同类型的概念漂移场景下数据分布的变化方式和特点不同，因此需创建不同的F.

假设有历史数据块 $D = \{ {D_1},{D_2}, … ,{D_{{n}}}\}$ ，第i个数据块为 ${D_i} = \{ ({{\boldsymbol {x}}_{ij}},{y_{ij}})|j = 1,2, … ,k\}$ （k为数据块大小），由D_i训练得到历史基学习器f_i. 当前数据块 ${D_t} = \{ ({{\boldsymbol {x}}_{tj}},{y_{tj}})|j = 1,2, … ,k\}$ ，在D_t上训练得到当前基学习器f_t. 候选基学习器池Q用来存储参与集成的候选基学习器，最大容量s=15.

当发生突变型概念漂移时，数据分布急速变化，历史数据分布和当前数据分布差异较大，大量历史样本成为阻碍模型学习的负面因素，导致历史基学习器的性能快速下降. 由于当前基学习器f_t在最新数据块D_t上训练得到，反映了流数据的最新分布，因此，为了快速过滤掉历史非关键样本，本文针对这种类型的概念漂移采用一种直接式过滤器，将f_t作为每个历史数据块的非关键样本过滤器F，即 $F = {f_t}$ . 以f_t对D_i的预测观察结果作为样本过滤条件C_i，表达式为：

${C_{{i}}}:{y_{ij}} \ne F({{\boldsymbol {x}}_{ij}}) ,$

(3)

真实标签与f_t预测结果不同的样本将被直接过滤掉.

当发生渐变型概念漂移时，数据分布变化较缓慢，历史数据分布与当前数据分布虽有差异但仍相似，历史数据块中可能只有少量样本变得非关键，因此与突变型概念漂移的直接过滤方式不同，渐变型概念漂移采用一种叠加式过滤器，即通过历史数据块的后序基学习器和f_t的加权组合来叠加过滤效果，确保充分利用历史样本知识和当前样本知识帮助进行更加准确的过滤操作. 为了实现对样本知识的有效利用，首先需要区分每个基学习器的重要程度，本文将基学习器在D_t上的实时预测精度作为其权重. 在此基础上，D_i的叠加过滤器F_i为：

${F_{{i}}} = \sum\limits_{p = i + 1}^n {\frac{{{w_p}}}{{\sum\limits_{q = i + 1}^n {{w_q}} + {w_t}}}} {f_p} + \frac{{{w_t}}}{{\sum\limits_{q = i + 1}^n {{w_q}} + {w_t}}}{f_t} ,$

(4)

${w_g} =\frac{1}{k}{{\sum\limits_{j = 1}^k { \llbracket {{f_g}({{\boldsymbol {x}}_{tj}}) = {y_{tj}}} \rrbracket} }} , \quad g =1,2,…,n,$

(5)

${w_t} = \frac{1}{k}{{\sum\limits_{j = 1}^k {\llbracket {{f_t}({{\boldsymbol {x}}_{tj}}) = {y_{tj}}} \rrbracket} }},$

(6)

其中当 $\left[\kern-0.15em\left[ \cdot \right]\kern-0.15em\right]$ 中的条件成立时值为1，否则为0. 以F_i对历史样本的预测观察结果作为样本过滤条件，表达式为：

${C_i}:{y_{ij}} \ne {F_{\text{i}}}({{\boldsymbol {x}}_{ij}}) ,$

(7)

真实标签与F_i预测结果不同的样本将被过滤掉.

经过上述操作，符合过滤条件的样本被丢弃，剩下更符合当前数据分布的历史关键样本块 ${\hat D_1},{\hat D_2}, … ,{\hat D_{{n}}}$ . 由于在突变型概念漂移发生后，过滤的样本通常较多，训练样本不足易导致模型训练不充分，因此本文向过滤后的每个历史样本块中补充D_t. 最后，在更新后的历史关键样本块上训练得到 ${\hat f_1},{\hat f_2}, … ,{\hat f_{{n}}}$ ，提高了基学习器的有效性.

2.2.2 样本扩充策略

概念漂移发生后，当前基学习器往往欠拟合，而历史样本恰恰可以帮助当前样本集弥补其缺少的样本知识. 因此，本文提出一种样本扩充策略，将过滤后保留的历史关键样本块 ${\hat D_1},{\hat D_2}, … ,{\hat D_{{n}}}$ 用来扩充D_t. 然而，即使历史样本集已过滤掉部分样本，全部扩充到D_t所花费的时间代价仍较大，为解决这个问题，本文从各个历史数据块中抽取子集 ${\widetilde D_1},{\widetilde D_2}, … ,{\widetilde D_n}$ 用来扩充D_t. 由于扩充后的D_t可能存在类别不平衡，造成这种情况的原因有2种：一种原因是D_t本身就存在类别不平衡的问题，而抽取的样本子集没有改善甚至加重了这种不平衡；另一种原因是D_t本身类分布平衡，但扩充导致了类别不平衡. 因此本文从抽取方式入手，为了降低扩充后的D_t的类不平衡率，提出一种分块优先抽样方法，该方法根据样本所属类在D_t中总类别的规模占比确定抽样优先级α，由此计算得到抽样概率P，按照抽样概率P依次从各个历史关键样本块中不放回地抽取一定数量的关键样本子集用于扩充.

抽样规模的设置直接关系实验结果的好坏. 如果抽样规模太小，将会导致抽样样本不足以提供足够的关键信息；如果抽样规模太大，将会浪费时间和资源，从而降低效率. 由于突变型漂移前后数据分布的差异较大，历史关键样本往往较少，设置总抽样规模M为较小值；渐变型漂移前后数据分布间虽有差异但仍相似，历史关键样本往往较多，设置M为较大值. 因此，可将总抽样规模M和漂移跨度span联系起来，表达式为：

${{M = }}\lambda \times \frac{{span}}{{span + 1}} \times \sum\limits_{i = 1}^n {{z_i}} ,$

(8)

其中λ为样本规模因子，z_i为历史数据块 ${\hat D_i}$ 的大小. 在确定M后， ${\hat D_i}$ 的抽样规模M_i由其大小确定，同时为了保证有相对足够的采样样本，限制最小的块抽样规模，表达式为：

${M}_{{i}}\text=\mathrm{max}\left\{\lambda \times \frac{span}{span+1}\times {z}_{i}\text{，}\frac{1}{10n}{{\displaystyle \sum _{j=1}^{n}{z}_{j}}}\right \} .$

(9)

为了缓解D_t在扩充后的类别不平衡现象，每个样本被抽中的概率与其所属类在D_t中的规模占比密切相关，即越少的类被选中的概率越大，越多的类被选中的概率越小. 因此，为历史样本中类别规模占比较小的样本设置较高的优先级，为类别规模占比较大的样本设置较低的优先级. 如果判断x_ij所属类别为 ${{{c}}'}$ ，设置其抽样优先级为

${\alpha _{ij}} = \left\{ \begin{gathered} \ln \left(\frac{{\sum\limits_{c \in C} {\sum\limits_{x = 1}^k { \llbracket {{y_{tx}} = c} \rrbracket} } }}{{\sum\limits_{x = 1}^k { \llbracket {{y_{tx}} = {c{'}}} \rrbracket} }}\right),{c'} \in C{\text{且 }}\left| C \right|{\text{ > }}1, \\ \ln \left(\frac{{\sum\limits_{c \in C} {\sum\limits_{x = 1}^k { \llbracket {{y_{tx}} = c} \rrbracket} } }}{2}\right),{c'} \in C{\text{且}}\left| C \right| = 1, \\ \ln \left(\sum\limits_{c \in C} {\sum\limits_{x = 1}^k { \llbracket {{y_{tx}} = c} \rrbracket} } \right),{\text{ 其他}},{\text{ }} \\ \end{gathered} \right.$

(10)

其中C为当前样本块中出现的样本类别. 抽样优先级和抽样概率成正比，x_ij的抽样概率可表示为

${P_{ij}} = {{Pr}}(({{\boldsymbol x}_{ij}}{\text{,}}{{{y}}_{ij}}) \in {\widetilde D_i}|({{\boldsymbol x}_{ij}}{\text{,}}{{{y}}_{ij}}) \in {\hat D_i}) = \frac{{{\alpha _{ij}}}}{{\sum\limits_{p = 1}^{z_i} {{\alpha _{ip}}} }} .$

(11)

显然，当 ${\hat D_i}$ 中每个样本的抽样优先级相等时，有

${P_{ij}} = {{Pr}}(({{\boldsymbol x}_{ij}}{\text{,}}{{{y}}_{ij}}) \in {\widetilde D_i}|({{\boldsymbol x}_{ij}}{\text{,}}{{{y}}_{ij}}) \in {\hat D_i}) = \frac{1}{{{z_i}}} ,$

(12)

分块优先抽样过程变为简单随机抽样. 将历史数据块 ${\hat{D}}_{i}$ 的优先抽样函数表示为

${\widetilde D_{{i}}} = S{{ampling}}({\hat D_i},{M_i},{P_i}) .$

(13)

依次从 ${\hat D_1},{\hat D_2}, … ,{\hat D_{{n}}}$ 中抽取数量为 ${M_1},{M_2}, … ,{M_{{n}}}$ 的关键样本子集 ${\widetilde D_1},{\widetilde D_2}, … ,{\widetilde D_n}$ ，将关键样本子集扩充到D_t中，得到扩充后的 ${\hat D_t} = {\widetilde D_1} \cup {\widetilde D_2} \cup … \cup {\widetilde D_n} \cup {D_t}$ . 经过上述操作，向 ${\hat D_t}$ 中补充了历史有用信息并且使类分布更加均衡，在扩充后的 ${\hat D_t}$ 上训练得到的 ${\hat f_t}$ 具有更丰富的样本特征，解决了当前基学习器的欠拟合问题，同时提高了基学习器的稳定性. 突变型和渐变型场景下的两阶段自适应集成过程如图3所示.

图 3 两阶段自适应集成过程

Figure 3. Two-stage adaptive ensemble process

下载: 全尺寸图片幻灯片

在将 ${\hat f_t}$ 存储到Q前，需要判断Q是否达到最大容量s. 如果 $n \geqslant s$ ，那么用 ${\hat f_t}$ 替换掉在D_t上实时预测精度最小的历史基学习器：

${\hat f_t} \to \mathop{\arg{\max }}\limits_{{{\hat f}_i} \in Q} \sum\limits_{j = 1}^k { \llbracket {{{\hat f}_i}({{\boldsymbol x}_{tj}}) \ne {{{y}}_{tj}}} \rrbracket} .$

(14)

最终的强分类器H对于x的预测结果为多数更新后的基学习器预测的结果，即

$H({{\boldsymbol{x}}}) = \mathop {\arg \max }\limits_{ y} \sum\limits_{i = 1}^n { \llbracket {{f_i}({\boldsymbol x}) = y} \rrbracket} .$

(15)

2.3 算法实施流程

TAEL方法首先检测漂移跨度span，判断漂移类型，然后在过滤阶段，设置非关键样本过滤器F，依次对历史样本块进行过滤操作，将剩余的历史关键样本用于训练更新历史基学习器，以提高其有效性；在扩充阶段，采用分块优先抽取策略，根据样本所属类别的规模占比设置抽样优先级，计算得到抽样概率，从历史关键样本块中抽取合适数量的样本子集来扩充当前样本块，缓解了扩充后的类分布不均衡，解决了当前基学习器欠拟合的问题. 算法1展示了TAEL方法的执行流程.

算法1. 面向不同类型概念漂移的两阶段自适应集成算法.

输入：历史数据块 ${D_1},{D_2}, … ,{D_{{n}}}$ ，当前数据块D_t，漂移跨度span，历史基学习器 ${f_1},{f_2}, … ,{f_{{n}}}$ ，当前基学习器f_t，非关键样本过滤器F.

输出：更新后的基学习器 $\hat f_1,\hat f_2,…,\hat f_n,$ 和 $\hat f_t$ .

① 获取D_t上每个类别的样本数 $\displaystyle\sum\limits_{x = 1}^k { \llbracket {{y_{tx}} = c} \rrbracket }$ ；

② if $span \leqslant \theta$

③ ${F_i} = {f_t}$ ；

④ else

⑤ ${F_i} = \displaystyle\sum\limits_{p = i + 1}^n {\frac{{{w_p}}}{{\displaystyle\sum\limits_{q = i + 1}^n {{w_q} + {w_t}} }}{f_p}} + \frac{{{w_t}}}{{\displaystyle\sum\limits_{q = i + 1}^n {{w_q} + {w_t}} }}{f_t}$ ；

⑥ end if

⑦ for $i = 1:n$

⑧ for $j = 1:k$

⑨ if ${F_i}({{\boldsymbol {x}}_{ij}}) \ne {y_{ij}}$

⑩ 从D_i中删除样本x_ij；

⑪ else

⑫ 根据式（10）计算x_ij的抽样优先级α_ij；

⑬ end if

⑭ end for

⑮ 根据式（11）由抽样优先级α_i计算抽样概率P_i；

⑯ 得到过滤后的历史关键数据块 ${\hat D_i}$ ；

⑰ if $span \leqslant \theta$

⑱ 更新历史基学习器 ${\hat f_i} \leftarrow train({\hat D_i} \cup {D_t})$ ；

⑲ else

⑳ 更新历史基学习器 ${\hat f_i} \leftarrow train({\hat D_i})$ ；

㉑ end if

㉒ end for

㉓获取总抽样规模 $M = \lambda \times \dfrac{{span}}{{span + 1}} \times \displaystyle\sum\limits_{i = 1}^n {{z_i}}$ ；

㉔ for $i = 1:n$

㉕根据式（9）计算每个 ${\hat D_i}$ 上的抽样规模M_i；

㉖按照抽样概率P_i从 ${\hat D_i}$ 中抽取大小为M_i的 ${\widetilde D_i} = Sampling({\hat D_i},{M_i},{P_i})$ ；

㉗ $\mathrm{e}\mathrm{n}\mathrm{d}\;\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{f}\mathrm{o}\mathrm{r}$

㉘ ${\hat D_t} = {D_t} \cup {\widetilde D_1} \cup {\widetilde D_2} \cup … \cup {\widetilde D_n}$ ；

㉙更新当前基学习器 ${\hat f_t} \leftarrow train({\hat D_t})$ ；

㉚根据式（15）将最新更新的基学习器参与集成；

㉛在D_t+1上进行测试，得到实时精度.

2.4 模型复杂度分析

TAEL的计算成本主要集中在漂移类型检测、样本过滤、样本扩充和基学习器更新这4个阶段，本文将依次对每个阶段进行时间复杂度分析.

1）漂移类型检测. 预测一个数据块中样本的时间复杂度为O(k)，其中k为数据块的样本数，那么L个历史基学习器在当前数据块上的预测时间复杂度为O(Lk)，计算后序数据分布稳定程度的时间复杂度为O(L). 因此，漂移类型检测过程的时间复杂度为 $O(Lk) + O(L) = O(Lk)$ .

2）样本过滤. 训练一个SVM分类器的时间复杂度为O(p²)，其中p为样本数，因此，在大小为k的数据块上训练基学习器的时间复杂度为O(k²). 当发生突变型概念漂移时，使用直接式过滤器，当前基学习器对所有历史数据的预测时间复杂度为O(sk)，其中s为基学习器的最大存储容量. 该过程的时间复杂度为O(k²)(一般地， $s < k$ ).

当发生渐变型概念漂移时，采用叠加式过滤器，根据历史和最新基学习器在当前数据块上的预测结果得到权值的时间复杂度为O((s+1)k). 对所有历史数据块依次执行基学习器的加权预测，总的时间复杂度为O(s(s+1)k). 因此，样本过滤过程的时间复杂度为 $O({k^2}) + O((s + 1)k) + O(s(s + 1){{k}}) = O({s^2}k)$ .

3）样本扩充. 计算所有历史数据块的抽样规模M_i的时间复杂度为O(s). 计算每个历史数据块中样本的抽样优先级α的时间复杂度为O(sk)，计算每个样本的抽样概率P的时间复杂度为O(sk). 对于每个历史数据块，根据抽样概率P在当前数据块随机抽取M_i个样本的时间复杂度为O(sk). 该过程的时间复杂度为 $O(s) + 3O(sk) = O(sk)$ .

4）更新基学习器. 训练s+1个基学习器的时间复杂度为O((s+1)k²). 替换掉最差基学习器的时间复杂度O((s+1)k)，整个过程的时间复杂度为 $O((s + 1)({k^2} + k)) = O(s{k^2})$ .

3. 实验分析

为验证本文提出的TAEL方法的有效性，本文在具有不同类型概念漂移的标准数据集和真实数据集上进行实验，并从精度、鲁棒性以及收敛性这3个方面进行评价. 实验平台为Windows10操作系统，CPU为酷睿i7-3，2 GHz内核，内存为8 GB，本方法采用MATLAB R2018a编写和运行.

3.1 实验数据

为了检验方法对不同类型概念漂移的处理能力，本文使用大规模在线分析平台MOA^[30]中的流数据生成器产生了6个具有突变式、渐进式以及增量式的概念漂移数据集. 除此之外，本文还选取了4个真实数据集. 具体的数据集信息如表1所示.

表 1 数据集信息

Table 1. Datasets Information

分类	数据集	实例数	维度	类别数量	漂移类型	漂移数量	漂移位点
合成数据集	Sea	100×10³	3	2	渐进式	3	25×10³, 50×10³, 75×10³
	Hyperplane	100×10³	10	2	增量式	-	-
	RBFBlips	100×10³	20	4	突变式	3	25×10³, 50×10³, 75×10³
	LED_abrupt	100×10³	24	10	突变式	1	50×10³
	LED_gradual	100×10³	24	10	渐进式	3	25×10³, 50×10³, 75×10³
	Tree	100×10³	30	10	突变式	3	25×10³, 50×10³, 75×10³
真实数据集	Electricity	45.3×10³	6	2	-	-	-
	Kddcup99	494×10³	41	23	-	-	-
	Covertype	581×10³	54	7	-	-	-
	Weather	95.1×10³	9	3	-	-	-
注：“-”表示未知.

下载: 导出CSV

| 显示表格

3.2 评价指标

为衡量TAEL方法的性能，本节从模型的精度、鲁棒性及收敛性3方面进行了分析.

1) 平均实时精度（average real-time accuracy，Avgracc）表示模型在每个时间步的实时精度的平均值，反映模型的实时性能.

$Avgracc = \frac{1}{T}\sum\limits_{t = 1}^T {\frac{{{n_t}}}{{|{D_t}|}}} ,$

(16)

其中n_t代表时间步t内正确分类的样本数，|D_t|表示样本块大小，T表示总的时间步数. 平均实时精度越高说明模型分类性能越好.

2）累积精度（cumulative accuracy，Cumacc）表示模型在当前时刻的累积预测正确样本数和总样本数的比值，反映模型从开始到当前时刻的整体性能.

$Cumacc = \frac{{\sum\limits_{i = 1}^{{T_t}} {{n_i}} }}{{\sum\limits_{j = 1}^{{T_t}} {|{D_j}|} }} ,$

(17)

其中T_t表示当前累积的时间步数.

3）鲁棒性（robustness，R）^[31]表示模型的稳定性和泛化性能. 本文在平均实时精度上分析了不同方法的鲁棒性，定义为：

$R(Dataset) = \frac{{racc(Dataset)}}{{\min racc(Dataset)}} ,$

(18)

其中 ${{racc}}({{Dataset}})$ 表示某算法在数据集Dataset上的平均实时精度， $\min {{racc}}({{Dataset}})$ 表示在数据集Dataset上所有算法中的最小平均实时精度.

某算法的整体鲁棒性值为该算法在所有数据集上的鲁棒性的总和. 鲁棒性值越大说明算法越稳定，面对数据中存在的干扰也能保持较好的性能.

4）收敛速度（recovery speed under accuracy，RSA）表示模型从概念漂移位点起实时精度恢复到稳定所需要的时间步数step与收敛位点后K个位点平均错误率avge的乘积：

$RSA = step \times avge .$

(19)

如果一个位点的性能表现和其后续K个参照位点的平均性能表现的差异小于阈值 $\gamma$ （当前波动程度较小），同时K个参照位点的前半部分和后半部分的平均性能表现的差异小于 $\dfrac{\gamma }{2}$ （整体波动程度趋近于稳定），那么该位点为收敛位点：

$\begin{gathered} \left |ac{c_t} - \frac{{\sum\limits_{j = 1}^K {ac{c_{t + j}}} }}{K}\right| < \gamma {\text{ 且}} \\ \frac{2}{K}\left|\sum\limits_{j = 1}^{\tfrac{K}{2}} {ac{c_{t + j}}} - \sum\limits_{k = \tfrac{K}{2} + 1}^K {ac{c_{t + k}}} \right| < \frac{\gamma }{2}{\text{. }} \\ \end{gathered}$

(20)

3.3 参数设置

本节对实验模型中的相关参数进行4点讨论：

1）数据块大小k. 过大的数据块中可能包含概念漂移，从而影响模型的分类效果；过小的数据块中可能无法包含足够多的样本特征，从而导致训练的基学习器稳定性较差. 因此，本文统一设置 $k = 500$ .

2）漂移稳定性参数 $\delta$ 和漂移类型参数 $\theta$ . 考虑到流数据本身的复杂性以及概念漂移类型的多样性，本文设置 $\delta = 0.01$ ， $\theta = 1$ .

3）样本规模因子 $\lambda$ . 样本规模控制了整体抽样的数量，直接影响了当前基学习器的训练，从而可能会对整体的模型性能造成影响. 因此，本文选取 $\lambda \in \{ 0.2,0.4,0.6,0.8\}$ 进行讨论，得到了在不同 $\lambda$ 下的分类性能，并使用最优样本规模因子与对比方法进行比较.

4）基学习器f. 本文选择LIBSVM来构建“同质”基学习器，核参数采用默认值 $g = 1/v$ ，（v为数据特征维度），惩罚因子设置为 $C = 10$ .

3.4 实验结果与分析

为评估TAEL的性能，本文选取DWCDS^[17]，HBP^[32]，Resnet^[33]，Highway^[34]以及原始深度神经网络（DNN）在精度、鲁棒性和收敛性3个方面进行对比实验和结果分析.

3.4.1 模型精度结果和分析

本节首先分析了在不同样本规模因子 $\lambda$ 下集成模型的表现性能. 展示了TAEL方法在不同 $\lambda$ 下的平均实时精度. 从可以看出当 $\lambda = 0.4$ 和 $\lambda = 0.6$ 时的平均实时精度值较高，这也反映了 $\lambda$ 会在一定程度上影响当前基学习器的性能，进而影响整个集成模型的实时精度. 分析其原因可能是当 $\lambda$ 取值较大时扩充的历史样本数太多，此时的关键信息冗余，训练得到的基学习器效果较差；当 $\lambda$ 取值较小时扩充的样本数太少，可能丢弃潜在的可用数据，导致训练得到的基学习器处于欠拟合状态. 因此，本文选择适中的扩充规模，又因实验结果中 $\lambda = 0.4$ 时的平均实时精度大于 $\lambda = 0.6$ 时的平均实时精度，最终选择 $\lambda = 0.4$ 的情况下与其他方法进行对比分析.

表 2 不同λ下平均实时精度

Table 2. Average Real-Time Accuracy Under Different λ

数据集	平均实时精度（排名）
数据集	λ=0.2	λ=0.4	λ=0.6	λ=0.8
Sea	0.8389 (1)	0.8378 (3)	0.8378 (3)	0.8378 (3)
Hyperplane	0.9109 (4)	0.9110 (2.5)	0.9111 (1)	0.9110 (2.5)
RBFBlips	0.9549 (2.5)	0.9549 (2.5)	0.9549 (2.5)	0.9549 (2.5)
LED_abrupt	0.6228 (3)	0.6229 (2)	0.6229 (2)	0.6229 (2)
LED_gradual	0.6205 (3)	0.6226 (1)	0.6199 (4)	0.6213 (2)
Tree	0.6671 (1)	0.6669 (2)	0.6660 (3)	0.6656 (4)
Electricity	0.7205 (2)	0.7193 (3)	0.7211 (1)	0.7190 (4)
Kddcup99	0.9384 (4)	0.9449 (2)	0.9455 (1)	0.9448 (3)
Covertype	0.7520 (2)	0.7526 (1)	0.7517 (3.5)	0.7517 (3.5)
Weather	0.8969 (3.5)	0.8970 (1.5)	0.8970 (1.5)	0.8969 (3.5)
平均排名	2.6	2.05	2.25	3.0
注：黑体数字表示最高平均实时精度及其排名.

下载: 导出CSV

| 显示表格

表3展示了不同方法在所有数据集上的平均实时精度及其综合排名. 由表3看出，在合成数据集上，TAEL的实时精度最好；在真实数据集上，TAEL的实时精度排名也都位于前列. TAEL在真实数据集上排名较低的原因可能在于数据集中概念漂移的出现较为密集，而TAEL利用数据块进行处理的方式可能会漏检，导致无法对基学习器进行及时地更新，从而使整个集成模型的性能下降. 在整体排名上TAEL的排名最高，说明了该方法能够提高集成模型的有效性，有较好处理不同类型概念漂移的能力.

表 3 不同方法在各数据集上的平均实时精度

Table 3. Average Real-Time Accuracy of Different Methods on Each Dataset

数据集	平均实时精度（排名）
数据集	DWCDS	DNN-2	DNN-4	DNN-8	DNN-16	HBP	Highway	Resnet	TAEL
Sea	0.7499 (4)	0.7081 (9)	0.7155 (8)	0.7495 (5)	0.7441 (7)	0.7771 (2)	0.7684 (3)	0.7448 (6)	0.8378 (1)
Hyperplane	0.6812 (9)	0.8600 (5)	0.8578 (6)	0.8487 (7)	0.7227 (8)	0.8692 (3)	0.8841 (2)	0.8637 (4)	0.9110 (1)
RBFBlips	0.8214 (8)	0.8256 (7)	0.8716 (2)	0.8655 (3)	0.4718 (9)	0.8350 (5)	0.8482 (4)	0.8300 (6)	0.9549 (1)
LED_abrupt	0.3700 (8)	0.5868 (3)	0.5809 (4)	0.5311 (7)	0.2784 (9)	0.5692 (6)	0.5893 (2)	0.5796 (5)	0.6229 (1)
LED_gradual	0.3804 (8)	0.5773 (4)	0.5898 (2)	0.5350 (7)	0.3031 (9)	0.5650 (6)	0.5839 (3)	0.5700 (5)	0.6199 (1)
Tree	0.5558 (2)	0.1948 (6)	0.2057 (3)	0.1338 (8)	0.1141 (9)	0.1432 (7)	0.2036 (4)	0.1992 (5)	0.6669 (1)
Electricity	0.7346 (1)	0.6228 (6)	0.6231 (5)	0.5635 (8)	0.5154 (9)	0.5676 (7)	0.6317 (4)	0.6343 (3)	0.7193 (2)
Kddcup99	0.9829 (1)	0.8796 (3)	0.7186 (6)	0.4763 (8)	0.3017 (9)	0.7670 (4)	0.7537 (5)	0.6535 (7)	0.9449 (2)
Covertype	0.8486 (1)	0.5251 (9)	0.5739 (8)	0.6243 (6)	0.6269 (5)	0.6465 (3)	0.6354 (4)	0.6183 (7)	0.7526 (2)
Weather	0.9566 (1)	0.8478 (3)	0.8050 (6)	0.8057 (5)	0.8043 (7)	0.8139 (4)	0.7813 (9)	0.8034 (8)	0.8970 (2)
平均排名	4.30	5.50	5.00	6.40	8.10	4.70	4.00	5.60	1.40
注：黑体数字表示最高平均实时精度及其排名.

下载: 导出CSV

| 显示表格

图4为TAEL和各个对比方法在所有数据集上的累积精度，表4为TAEL和各个对比方法的最终累积精度和综合排名. 由图4和表4可知，在标准数据集上TAEL的累积精度最高，在真实数据集上TAEL的累积精度也有较好的排名，分析其原因是该方法针对漂移类型对数据块逐一处理的策略能够使模型对不同类型的概念漂移做出及时响应，保持较高的精度.

图 4 不同方法在各数据集上的累积精度比较

Figure 4. Comparison of cumulative accuracy of different methods on each dataset

下载: 全尺寸图片幻灯片

表 4 不同方法在各数据集上的最终累积精度

Table 4. Final Cumulative Accuracy of Different Methods on Each Dataset

数据集	最终累积精度（排名）
数据集	DWCDS	DNN-2	DNN-4	DNN-8	DNN-16	HBP	Highway	Resnet	TAEL
Sea	0.7500(8)	0.7495(9)	0.7543(7)	0.7861(4)	0.7820(5)	0.8083(2)	0.7977(3)	0.7803(6)	0.8370(1)
Hyperplane	0.6763(9)	0.8600(5)	0.8580(6)	0.8483(7)	0.7230(8)	0.8691(3)	0.8840(2)	0.8636(4)	0.9110(1)
RBFBlips	0.8231(8)	0.8345(7)	0.8828(2)	0.8708(3)	0.5379(9)	0.8476(5)	0.8586(4)	0.8374(6)	0.9481(1)
LED_abrupt	0.3681(8)	0.5869(3)	0.5803(4)	0.5305(7)	0.2786(9)	0.5693(6)	0.5893(2)	0.5796(5)	0.6229(1)
LED_gradual	0.3821(8)	0.5776(4)	0.5898(2)	0.5344(7)	0.3032(9)	0.5650(6)	0.5843(3)	0.5699(5)	0.6199(1)
Tree	0.5558(2)	0.4329(5)	0.4575(3)	0.3330(8)	0.3033(9)	0.3591(7)	0.4472(4)	0.4310(6)	0.6636(1)
Electricity	0.7404(1)	0.6434(6)	0.6450(4)	0.5840(8)	0.5735(9)	0.5969(7)	0.6447(5)	0.6502(3)	0.6674(2)
Kddcup99	0.9833(1)	0.9832(2)	0.9195(7)	0.7813(8)	0.6160(9)	0.9823(3)	0.9614(4)	0.9276(6)	0.9562(5)
Covertype	0.8481(1)	0.6983(9)	0.7336(8)	0.7676(6)	0.7685(5)	0.7919(2)	0.7823(3)	0.7709(4)	0.7463(7)
Weather	0.9571(1)	0.8872(3)	0.8743(6)	0.8754(5)	0.8664(8)	0.8824(4)	0.8362(9)	0.8708(7)	0.8933(2)
平均排名	4.70	5.30	4.90	6.30	8.00	4.50	3.90	5.20	2.20
注：黑体数字表示最高的最终累积精度及其排名.

下载: 导出CSV

| 显示表格

本文使用非参数检验方法Friedman-Test^[35]对TAEL与对比方法相比较的性能优势进行统计检验. 对于给定的K（K=9）种方法和N（N=10）个数据集，令 $r_i^j$ 为第j个方法在第i个数据集上的秩，则第j个算法的秩和平均为

${R_j} = \frac{1}{N}\sum\limits_{i = 1}^N {r_i^j} .$

(21)

零假设H₀假定所有方法的性能是相同的. 在此前提下，当N与 $K$ 足够大时，Friedman统计值 ${\tau _F}$ 服从第一自由度为 $K - 1$ 、第二自由度为 $(K - 1)(N - 1)$ 的F分布：

${\tau _F} = \frac{{(N - 1){\tau _{{\chi ^2}}}}}{{N(K - 1) - {\tau _{{\chi ^2}}}}}, \qquad\qquad\qquad\quad$

(22)

${\tau _{{\chi ^2}}} = \frac{{12N}}{{K(K + 1)}}\left [\sum\limits_{j = 1}^K {R_j^2} - \frac{{K{{(K + 1)}^2}}}{4}\right].$

若计算得到的统计值大于某一显著性水平下F分布临界值，则拒绝零假设H₀，表明各方法的秩和存在显著差异，即测试方法性能存在显著差异；反之则接受零假设H₀，所有方法的性能没有明显差异.

在 $\alpha = 0.05$ 的情况下F分布临界值 $\tau _F^{0.05}(8,72) = 2.069\;8$ ，经计算可得在不同性能指标下的Friedman统计值 ${\tau _F}$ ，如所示. 从可以看出，平均实时精度和最终累积精度下的 ${\tau _F}$ 统计值均大于临界值 $\tau _F^{0.05}(8,72)$ ，拒绝零假设 ${H}_{0}$ ，说明所有方法性能存在显著差异.

表 5 平均实时精度和最终累积精度下的

${\tau _F}$

Table 5.

${\tau _F}$ of Average Real-Time Accuracy and Final Cumulative Accuracy

评价指标	${\tau _F}$	$\tau _F^{0.05}(8,72)$
平均实时精度	7.2260	2.0698
最终累积精度	4.5747	2.0698

下载: 导出CSV

| 显示表格

本文用Bonferroni-Dunn测试^[36]计算了所有方法的显著性差异，用于比较2种方法之间是否存在显著差异. 若2种方法的秩和平均差值大于临界差，则这2种方法的性能存在显著差异：

$CD = {q_\alpha }\sqrt {\frac{{K(K + 1)}}{{6N}}} ,$

(23)

其中当 $K = 9$ ， $N = 10$ 时，可以查表得到 ${q_{\alpha = 0.05}} = 2.724$ ，经计算得到显著性水平 $\alpha = 0.05$ 的情况 $CD = 3.336\;2$ . 不同方法在平均实时精度和最终累积精度上的统计分析结果如图5所示，在图中将没有显著性差异的方法使用黑线连接起来. 结果表明，在统计意义上，TAEL方法排名最好且具有明显的优势.

图 5 不同方法在平均实时精度和最终累积精度上的显著性差异分析

Figure 5. Analysis of critical difference in average real-time accuracy and final cumulative accuracy of different methods

下载: 全尺寸图片幻灯片

3.4.2 模型鲁棒性分析

为了衡量各个方法的算法稳定性，本节计算每个方法在各个数据集上的鲁棒性，图6展示了计算结果. 图6中每个小矩形的面积代表的是算法在某种数据集上的鲁棒性值的大小，每一列上展示的数值代表算法在所有数据集上的鲁棒性值总和，即该算法的整体鲁棒性. 由图6可知，在大多数情况下，TAEL的鲁棒性都能取得较好的排名，且整体鲁棒性最高，这说明该方法对数据的噪声和异常值具有更强的鲁棒性，能提高集成模型的整体泛化性能.

图 6 不同方法的鲁棒性比较

Figure 6. Comparison of robustness of different methods

下载: 全尺寸图片幻灯片

3.4.3 模型收敛性分析

为比较各个方法在概念漂移发生后的收敛性能，本节计算并分析了各个方法在5个合成数据集的概念漂移位点上的收敛速度. 在收敛位点的判定过程中，设定收敛判定阈值 $\gamma = 0.02$ ，参照位点个数 $K = 20$ . 表6展示的为各个方法在数据集上的已知漂移位点上计算得到的收敛速度. 由于个别方法在漂移位点处精度保持平稳波动，因此，对该位点的收敛速度不做统计，用“-”进行表示. 从表6可以看出，TAEL在多数情况下都具有较快的收敛速度，是因为该方法及时更新基学习器使其能尽快适应新的数据分布，集成有效性得到提高. 在整体排名中TAEL处于第一，说明该方法具有较快的收敛速度，收敛性能较好.

表 6 不同方法在各数据集上的收敛速度

Table 6. Recovery Speed Under Accuracy of Different Methods on Each Dataset

数据集	DWCDS		DNN-2		DNN-4		DNN-8		DNN-16
Sea	0.67/0.25/0.45		0.97/2.63/0.70		1.24/1.15/2.18		2.36/1.55/2.78		2.60/1.66/0.20
RBFBlips	0.56/0.85/0.16		1.17/1.56/0.41		0.38/0.61/0.22		0.56/0.94/0.21		-/-/-
LED_abrupt	3.70		9.77		14.92		19.85		17.94
LED_gradual	2.20/1.95/-		10.70/7.43/6.01		10.91/7.89/3.58		14.24/11.48/3.70		14.83/9.61/4.55
Tree	9.29/4.69/4.70		-/23.81/0.87		2.62/15.22/7.69		4.44/0.88/0.88		0.89/0.88/0.88
平均排名	3.54		5.85		4.85		5.54		5.77

数据集		HBP		Highway		Resnet		TAEL
Sea		0.77/0.51/1.82		2.76/0.49/1.81		0.57/0.56/0.73		0.45/1.97/1.50
RBFBlips		1.14/0.83/0.21		0.85/1.14/0.42		1.01/2.02/0.62		0.03/0.29/0.01
LED_abrupt		20.20		9.80		11.65		5.28
LED_gradual		13.12/10.86/7.42		9.66/6.68/5.37		12.80/7.06/5.47		8.25/5.34/3.71
Tree		3.56/0.87/1.75		-/17.56/1.75		-/21.49/1.75		3.85/3.92/3.85
平均排名		5.38		5.23		5.69		3.15
注：“-”表示对当前位点的收敛速度不进行统计；黑体数字表示最高收敛速度；LED_abrupt包含1个漂移位点，收敛速度只有1个；其他数据集包含3个漂移位点，对应3个收敛速度.

下载: 导出CSV

| 显示表格

4. 结束语

针对概念漂移发生后，在线集成模型无法及时响应数据流的变化而导致泛化性能降低、收敛速度减慢的问题，本文提出一种面向不同类型概念漂移的两阶段自适应集成学习方法. 本文通过检测漂移跨度来确定漂移类型，并采用一种针对漂移类型进行自适应调整的两阶段样本处理机制. 在该机制中，一方面通过样本过滤策略过滤历史样本块中的非关键样本，使历史数据分布更接近当前最新数据分布，提高了基学习器的有效性；另一方面通过样本扩充策略为当前样本集补充合适数量的历史关键样本，解决了当前基学习器的欠拟合问题，同时缓解了扩充后的类别不平衡. 更新后的基学习器组成的集成模型的有效性得到了提高，对不同类型的概念漂移能做出更精准及时的响应. 在集成学习中，集成的多样性同样影响了集成模型的性能，在未来的工作中，将进一步研究针对不同漂移类型提升集成多样性的方法.

作者贡献声明：郭虎升负责思想提出、方法设计、论文写作及修改；张洋负责论文写作、代码实现、数据测试及论文修改；王文剑负责写作指导、修改审定.

此处没有直接将这些范数函数应用于张量数据. 请注意，

${\mathscr{l}}_{1}$ 范数和张量核范数都可以轻松地重新表示为多个矩阵范数的组合，可以直接定义它们以及张量上相应的双范数，参见式（7）. 关于对偶范数的详细内容见附录C.

图 1 SLTR的基本思想

注：首先沿每阶展开张量；然后对于每种阶展开，并行估计权重，同时通过正则化保证稀疏性和低秩；最后组合每阶的结果，得到最终结果.

Figure 1. The basic idea of SLTR

下载: 全尺寸图片幻灯片

在稀疏级别 $s=80{\text \%}$ 的模拟数据集上SLTR和基线的对数计算（时间）成本

Logarithmic computational (time) cost of SLTR and baselines on simulated datasets with the sparsity level $s=80{\text \%}$

下载: 全尺寸图片幻灯片

图 3 估计权重的示例

注：选择4个示例视频中的1帧并显示估计权重的热图.

Figure 3. Examples of estimated weights

下载: 全尺寸图片幻灯片

表 1 SLTR与其他张量回归模型的比较

Table 1 Comparison Between SLTR and Other Tensor Regression Models

方法	计算瓶颈	无需指定秩	充分稀疏	结构保留
SLTR（本文）	$O\left({\mathrm{max}}_{m}\left\{{p}_{m}{P}_{\backslash {m}}^{2}\right\}\right)$	✓	✓	✓
Remurs	$O\left(\displaystyle\sum\limits _{m=1}^{M}\{{p}_{m}{P}_{\backslash {m}}^{2}\}\right)$	✓	✓	✓
GLTRM	$O\left(R\displaystyle\sum\limits _{m=1}^{M}{p}_{m}^{3}\right)$	×	✓	✓
orTRR	$O\left(M{P}^{3}\right)$	✓	×	✓
SURF	$O\left(TN\displaystyle\sum\limits _{m=1}^{M}{P}_{\backslash {m}}\right)$	×	✓	✓
LR	$O\left(N{P}^{2}\right)$	×	✓	×
$\mathrm{注}：T$ 表示迭代方法的迭代次数， $N$ 是样本数， $M$ 是数据阶数， $R$ 是CP-rank. $P=\underset{m=1}{\displaystyle\prod\limits ^{M}}{p}_{m}$ 和 ${P}_{\backslash m}=\underset{k\ne m}{\displaystyle\prod\limits ^{M}}{p}_{m}$ . 无需指定秩是指方法能否自动地探索所需要的最佳的张量秩而不是通过超参数提前指定；充分稀疏是指模型权重是否具有充分的稀疏性；结构保留是指方法能否保留数据中的结构信息.

下载: 导出CSV

表 2 各个方法在具有不同数据大小的模拟数据集的MSE

Table 2 MSE of Different Methods on Simulated Dataset with Different Sizes of Data

数据大小	SLTR（本文）	Remurs	SURF	Lasso	ENet
30×30×5	0.9186	0.9190	0.9289	1.9381	1.9377
35×35×5	0.9336	0.9370	0.9527	2.0147	2.0147
40×40×5	0.9073	0.9072	1.0006	2.1059	2.1065
20×20×10×5	0.9150	0.9177		2.1388	2.1373
25×25×10×5	0.9071	0.9101		1.9696	1.9696
30×30×10×5	0.9110	0.9123		1.9754	1.9745
注：粗体数字表示最佳结果，下划线值表示次佳结果.

下载: 导出CSV

表 3 不同方法的交叉验证总时间

Table 3 Total Time of Cross Validation in Different Methods s

数据大小	SLTR（本文）	Remurs
30×30×5	16.793568	510.050226
35×35×5	20.212862	602.292492
40×40×5	6.509343	684.737448
20×20×10×5	10.975796	1474.090235
25×25×10×5	16.936689	3060.085998
30×30×10×5	23.276677	3394.478247
注：粗体数字为最短时间，表示计算成本最小.

下载: 导出CSV

表 4 UCF101 数据集上的时间成本和AUROC值

Table 4 Time Cost and AUROC Value on UCF101 Dataset

标签对	SLTR（本文）		Remurs		SURF		Lasso		ENet
标签对	AUROC	运行时间/s	AUROC	运行时间/s	AUROC	运行时间/s	AUROC	运行时间/s	AUROC	运行时间/s
ApplyEyeMakeup与ApplyLipstick	0.931953	0.002407	0.945266	47.85397	0.64053	0.037561	0.88006	0.435661	0.887556	0.423819
BaseballPitch与Basketball	0.995074	0.000889	0.995074	57.55661	0.78695	0.504165	0.964194	0.147045	0.965473	0.603081
BodyWeightSquats与Bowling	0.97756	0.001211	0.946704	64.6286	0.32258	0.06725	0.919753	0.557569	0.930556	0.48047
注：粗体数字表示最佳结果，下划线值表示次佳结果.

下载: 导出CSV

表 5 UCF101视频数据在交叉验证中的详细时间

Table 5 Detailed Time on UCF101 Video Data in Cross Validation s

标签对	SLTR（本文）	Remurs
ApplyEyeMakeup与ApplyLipstick	6.889112525	692.231181
Archery与BabyCrawling	7.028544625	625.536704
BalanceBeam与BandMarching	7.279161013	633.608475
BaseballPitch与Basketball	6.865089138	678.267903
BasketballDunk与BenchPress	6.952039188	708.65648
Biking与Billiards	6.9308017	698.477735
BlowDryHair与BlowingCandles	6.7497102	839.154294
BodyWeightSquats与Bowling	6.638173225	701.628673
BoxingPunchingBag与BoxingSpeedBag	7.354547413	680.790876
BreastStroke与BrushingTeeth	6.569058275	698.097274

下载: 导出CSV

参考文献(29)

[1]	Zhu Dajiang, Zhang Tuo, Jiang Xi, et al. Fusing DTI and fMRI data: A survey of methods and applications[J]. NeuroImage, 2014, 102: 184−191 doi: 10.1016/j.neuroimage.2013.09.071
[2]	Noroozi A, Rezghi M. A tensor-based framework for rs-fMRI classification and functional connectivity construction[J]. Frontiers in Neuroinformatics, 2020, 14: 581897 doi: 10.3389/fninf.2020.581897
[3]	Wu X, Lai J. Tensor-based projection using ridge regression and its application to action classification[J]. IET Image Processing, 2010, 4(6): 486−493 doi: 10.1049/iet-ipr.2009.0278
[4]	Lui Y M. A least squares regression framework on manifolds and its application to gesture recognition[C]//Proc of 2012 IEEE Computer Society Conf on Computer Vision and Pattern Recognition Workshops. Piscataway, NJ: IEEE, 2012: 13−18
[5]	Yang Yinchong, Krompass D, Tresp V. Tensor-train recurrent neural networks for video classification[C]//Proc of the 34th Int Conf on Machine Learning. New York: PMLR, 2017: 3891−3900
[6]	Sharma L, Gera A. A survey of recommendation system: Research challenges[J]. International Journal of Engineering Trends and Technology, 2013, 4(5): 1989−1992
[7]	Bhargava P, Phan T, Zhou Jiayu, et al. Who, what, when, and where: Multi-dimensional collaborative recommendations using tensor factorization on sparse user-generated data[C]//Proc of the 24th Int Conf on World Wide Web. New York: ACM, 2015: 130−140
[8]	Mitchell T M, Shinkareva S V, Carlson A, et al. Predicting human brain activity associated with the meanings of nouns[J]. Science, 2008, 320(5880): 1191−1195 doi: 10.1126/science.1152876
[9]	Soomro K, Zamir A R, Shah M. UCF101: A dataset of 101 human actions classes from videos in the wild[J]. arXiv preprint, arXiv: 1212.0402, 2012
[10]	Huang Qingqiu, Xiong Yu, Rao Anyi, et al. MovieNet: A holistic dataset for movie understanding[C]//Proc of the 16th European Conf. Berlin: Springer, 2020: 709−727
[11]	Zhou Hua, Li Lexin, Zhu Hongtu. Tensor regression with applications in neuroimaging data analysis[J]. Journal of the American Statistical Association, 2013, 108(502): 540−552 doi: 10.1080/01621459.2013.776499
[12]	He Lifang, Chen Kun, Xu Wanwan, et al. Boosted sparse and low-rank tensor regression[J]. Advances in Neural Information Processing Systems, 2018, 31[2023-07-30].https://proceedings.neurips.cc/paper/2018/hash/8d34201a5b85900908db6cae92723617-Abstract.html
[13]	Li Na, Stefan K, Carmeliza N. Some convergence results on the regularized alternating least-squares method for tensor decomposition[J]. Linear Algebra and Its Applications, 2013, 438(2): 796−812 doi: 10.1016/j.laa.2011.12.002
[14]	Cichocki A, Lee N, Oseledets I, et al. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions[J]. Foundations and Trends® in Machine Learning, 2016, 9(4/5): 249−429
[15]	Song Xiaonan, Lu Haiping. Multi-linear regression for embedded feature selection with application to fMRI analysis[C/OL]//Proc of the 31st AAAI Conf on Artificial Intelligence. 2017[2023-06-30].https://ojs.aaai.org/index.php/AAAI/article/view/10871
[16]	Li Wenwen, Lou Jian, Zhou Shuo, et al. Sturm: Sparse tubal-regularized multilinear regression for fMRI[C]//Proc of 10th Int Workshop on Machine Learning in Medical Imaging. Berlin: Springer, 2019: 256−264
[17]	Yang E, Lozano A, Ravikumar P. Elementary estimators for high-dimensional linear regression[C]//Proc of the 31st Int Conf on Machine Learning. New York: PMLR, 2014: 388−396
[18]	Tucker L R. Some mathematical notes on three-mode factor analysis[J]. Psychometrika, 1966, 31(3): 279−311 doi: 10.1007/BF02289464
[19]	Rabanser S, Shchur O, Günnemann S. Introduction to tensor decompositions and their applications in machine learning[J]. arXiv preprint, arXiv: 1711.10781, 2017
[20]	Hillar C J, Lim L H. Most tensor problems are NP-hard[J]. Journal of the ACM, 2013, 60(6): 1−39
[21]	Tomioka R, Hayashi K, Kashima H. Estimation of low-rank tensors via convex optimization[J]. arXiv preprint, arXiv: 1010.0789, 2010
[22]	Liu Ji, Musialski P, Wonka P, et al. Tensor completion for estimating missing values in visual data[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 35(1): 208−220
[23]	Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® in Machine Learning, 2011, 3(1): 1−122
[24]	Combettes P L, Pesquet J C. Proximal splitting methods in signal processing[J]. Fixed-point Algorithms for Inverse Problems in Science and Engineering, 2011, 49: 185−212
[25]	Negahban S N, Ravikumar P, Wainwright M J, et al. A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers[J/OL]. 2012[2023-07-31].https://projecteuclid.org/journals/statistical-science/volume-27/issue-4/A-Unified-Framework-for-High-Dimensional-Analysis-of-M-Estimators/10.1214/12-STS400.full
[26]	Guo Weiwei, Kotsia I, Patras I. Tensor learning for regression[J]. IEEE Transactions on Image Processing, 2011, 21(2): 816−827
[27]	Zou Hui, Hastie T. Regularization and variable selection via the elastic net[J]. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2005, 67(2): 301−320 doi: 10.1111/j.1467-9868.2005.00503.x
[28]	Panagakis Y, Kossaifi J, Chrysos G G, et al. Tensor methods in computer vision and deep learning[J]. Proceedings of the IEEE, 2021, 109(5): 863−890 doi: 10.1109/JPROC.2021.3074329
[29]	陈珂锐,孟小峰. 机器学习的可解释性[J]. 计算机研究与发展,2020,57(9):1971−1986 doi: 10.7544/issn1000-1239.2020.20190456 Chen Kerui, Meng Xiaofeng. Interpretation and understanding in machine learning[J]. Journal of Computer Research and Development, 2020, 57(9): 1971−1986 (in Chinese) doi: 10.7544/issn1000-1239.2020.20190456