-
摘要: 数据流分类是数据流挖掘领域一项重要研究任务, 目标是从不断变化的海量数据中捕获变化的类结构. 目前, 几乎没有框架可以同时处理数据流中常见的多类非平衡、概念漂移、异常点和标记样本成本高昂问题. 基于此, 提出一种非平衡数据流在线主动学习方法(Online active learning method for imbalanced data stream, OALM-IDS). AdaBoost是一种将多个弱分类器经过迭代生成强分类器的集成分类方法, AdaBoost.M2引入了弱分类器的置信度, 此类方法常用于静态数据. 定义了基于非平衡比率和自适应遗忘因子的训练样本重要性度量, 从而使AdaBoost.M2方法适用于非平衡数据流, 提升了非平衡数据流集成分类器的性能. 提出了边际阈值矩阵的自适应调整方法, 优化了标签请求策略. 将概念漂移程度融入模型构建过程中, 定义了基于概念漂移指数的自适应遗忘因子, 实现了漂移后的模型重构. 在6个人工数据流和4个真实数据流上的对比实验表明, 提出的非平衡数据流在线主动学习方法的分类性能优于其他5种非平衡数据流学习方法.Abstract: Data stream classification is an important research task in the field of data stream mining, which aims to capture changing class structures from the ever-changing massive data. At present, almost no frameworks can simultaneously address the common problems in data stream, such as multi-class imbalance, concept drift, outlier and the exorbitant costs associated with labeling the unlabeled samples. In this paper, we propose an online active learning method for imbalanced data stream (OALM-IDS). AdaBoost is an ensemble classification method that iteratively generates a strong classifier from multiple weak classifiers. AdaBoost.M2 further introduces the confidence degree of weak classifiers, which is suitable for static data. In the method, we firstly define an importance measure of training sample based on imbalanced ratio and adaptive forgetting factor, which makes the AdaBoost.M2 method applying for imbalanced data stream and improves the performance of ensemble classifier. Then, we propose an adaptive adjustment method of marginal threshold matrix, which optimizes the label request strategy. Finally, we define an adaptive forgetting factor based on the concept drift index by bringing the degree of concept drift into the construction process of model, which realizes the model reconstruction after drift. Comparative experiments on six artificial data streams and four real data streams show that the classification performance of the online active learning method is better than those of the existing five learning methods for imbalance data stream.
-
Key words:
- Active learning /
- data stream classification /
- multi-class imbalance /
- concept drift
-
随着信息行业的高速发展, 大量数据以数据流的形式呈现, 如超市交易记录、网络搜索请求、电信呼叫记录和传感器网络数据等[1]. 在这些数据流中, 有许多需要处理的重要信息. 因此, 从这些海量数据流中发现和挖掘有价值信息已成为一项重要且艰巨的任务[2]. 与传统数据相比, 数据流具有实时性、连续性、时序性、变化性和无限性等特点. 因此, 数据流分类问题更为复杂[3].
数据流通常可以分为静态数据流和动态数据流, 静态数据流以固定数据分布形式出现, 动态数据流数据分布会随着时间变化而变化[4]. 不同数据分布称为不同概念, 这种概念的变化称为概念漂移[5]. 概念漂移将导致之前训练好的分类模型不再适用于目前数据流环境, 从而严重影响数据流分类的准确率. 同时, 在数据流中, 还会存在一些异常点, 这些异常点的出现会导致分类模型的决策边界受到影响. 因此, 数据流分类模型中概念漂移和异常点的处理成为数据流分类研究的重要内容.
非平衡数据流分类研究包括二类非平衡分类(即存在一个多数类和一个少数类)和多类非平衡分类[6]. 目前, 多数研究工作只关注二类非平衡分类[7-12]. 多类非平衡分类有2种研究思路, 第1种是直接处理, 第2种是将其转换成多个二类非平衡数据来研究. 采用第1种方法时, 由于分类取决于它与哪类进行比较, 因此类与类间关系更为复杂; 采用第2种方法时, 由于多个类间是相互联系的, 这种转换方法将丢失有价值信息[12]. 因此, 多类非平衡数据流分类的研究更具挑战性.
由此可见, 多类非平衡、概念漂移和异常点都会影响数据流分类模型性能, 当它们同时发生时, 会互相影响[13], 使数据流分类更为复杂. 例如, 随着时间的推移, 数据流的非平衡比率有可能会发生变化, 与之相应的采样机制应该随非平衡比率的变化而改变[14]. 目前, 众多学者对非平衡数据流的分类问题进行了研究. 如Bifet等[15]提出的LB (Leverage bagging)方法是解决概念漂移和多类非平衡问题的经典算法之一, 该方法通过被动适应来应对概念漂移; Mirza等[16]提出基于极限学习机的多类非平衡数据流分类算法(Meta-cognitive online seq-uential extreme learning machine, MOS-ELM), 是首次用于解决概念漂移和多类非平衡问题的方法; Barros等[17]提出一种在线学习集成算法(Boosting-like online learning ensemble, BOLE)将AdaBoost[18]引入数据流分类问题中, 用于解决多类非平衡问题. 此后, Ferreira等[19]提出自适应重采样随机森林算法(Adaptive random forests with resampling, ${\rm{ARF}}_{RE}$), 用于解决概念漂移和非平衡比率变化的非平衡数据流在线分类的问题.
然而, 上述方法都是有监督的学习方法(即假定在训练期间不受限制地访问类标签), 而在真实数据流中获取所有样本的真实标签非常困难或者代价很高. 因此, 近年来主动学习方法[20]备受关注, 原因是其有望用最少样本标签构建预测模型. 目前, 将主动学习方法与在线分类技术相结合, 已成为数据流分类的有效方法之一.
本文提出一种非平衡数据流在线主动学习方法(Online active learning method for imbalanced data stream, OALM-IDS). 该方法由初始化阶段、在线学习阶段和概念漂移检测阶段构成. 在初始化阶段, 提出一种基于非平衡比率和自适应遗忘因子的样本初始权重定义方法, 使AdaBoost.M2方法适用于非平衡数据流, 提升了非平衡数据流集成分类器的性能; 在在线学习阶段, 为了适应数据分布的变化, 提出了边际阈值矩阵的自适应调整方法, 使标签请求策略可以选出难分和少数类的样本, 用于概念漂移后重新训练分类器; 在概念漂移检测阶段, 定义了基于集成分类器分类偏差的概念漂移指数, 并基于概念漂移指数, 定义了自适应遗忘因子, 从而将概念漂移程度融入模型重构.
本文主要贡献有以下3点:
1)针对非平衡漂移数据流分类任务, 提出一个在线主动学习框架;
2)提出含有自适应遗忘因子的样本初始权重定义方法, 使AdaBoost.M2方法适用于非平衡数据流, 并可以根据概念漂移程度实现分类模型的重构;
3)提出基于样本分类不确定程度的边际阈值矩阵自适应调整方法, 构建了基于混合标签请求策略的主动学习模型.
1. 相关工作
本文主要研究非平衡数据流的自适应分类方法, 该方法是一种主动学习方法. 下面对非平衡数据流分类方法和数据流主动学习方法的研究现状进行回顾.
1.1 非平衡数据流分类方法
目前, 面向具有概念漂移的非平衡数据流分类方法主要有基于数据块的分类方法和非基于数据块的分类方法2种研究思路.
1)基于数据块的分类方法. 首先, 将数据流划分为长度等长的数据块; 然后, 通过对历史数据块和当前数据块的欠采样得到平衡的训练集, 训练样本大多数采样自当前数据块, 少数采样自历史数据块; 最后, 训练集成分类器, 并且在分类过程对概念漂移进行检测. MOS-ELM是首次用于解决概念漂移和多类非平衡问题的方法, 该方法采用了基于块的研究思路. 这类方法研究思路简单, 但由于数据流被分割为等长的数据块, 会导致一个概念被划分到多个数据块中, 或一个数据块中包含多个概念, 而目前尚没有有效确定块长的方法.
2)非基于数据块的分类方法可以避免上述提到的块长难以确定问题. 这类方法多采用集成分类模型, 主要包括基于bagging[21]的方法和基于boosting[22]的方法. 基于bagging的方法, 随着非平衡数据的到来, 不断对样本采样, 从而得到平衡的训练集, 然后训练集成分类器, 并在分类过程对概念漂移进行检测. 但对异常点较多的数据流, 该类方法极易造成过拟合和准确率降低. 2010年, Bifet等[15]在bagging方法基础上提出了LB方法, 该方法通过对预测准确率的检测, 来应对概念漂移, 当预测准确率下降时, 模型进行被动调整. 针对非平衡数据流的二分类问题, 自适应随机森林(Adaptive random forest, ARF)[23]是将随机森林应用到数据流上的一种改进方法. 该方法在概念漂移检测阶段设立警告阈值, 当达到警告值时, 分类模型开始训练新树; 当漂移发生时, 训练好的新树替换掉森林中最差的旧树, 从而提升了模型的更新速度. Ferreira等[19]提出${\rm{ARF}}_{RE}$方法, 旨在解决多类非平衡和概念漂移的混合问题. ${\rm{ARF}}_{RE}$继承了ARF中的概念漂移检测机制, 该方法在采样过程中, 通过记录样本到达时间来估算非平衡比率, 并将泊松分布的输出作为训练样本的权值, 以反映样本被训练的不同可能性.
目前, 有少数研究工作是基于boosting的方法, 其中最具代表性的是基于AdaBoost的方法[18]. AdaBoost算法最初是基于静态数据提出的, 其核心思想在于将弱分类器经过多次迭代形成强分类器, 并且在迭代过程中, 样本权重由上次迭代该样本的分类难度来确定. 与基于bagging的方法相比, 基于AdaBoost的方法将AdaBoost作为集成分类器, 充分考虑了每个基分类器的权重, 提高了集成分类器的分类精度. Barros等[17]提出一种在线学习集成算法用于解决多类非平衡问题, 该方法一方面降低了AdaBoost中只保留准确率高于50% 的分类器限制, 另一方面使用了基于分类错误率及标准差变化的概念漂移检测方法[24].
为了检测概念漂移, 在分类过程中, 以上方法需要利用真实标签计算准确率, 因此都是有监督的学习方法.
1.2 数据流主动学习方法
在样本标签有限情况下, 主动学习方法可通过少量的样本标签构建预测模型, 从而有效节约标签成本[25]. 然而, 主动学习方法的性能很大程度上依赖于标签请求策略的优劣. 典型的标签请求策略包括不确定性策略、随机策略和混合策略[20]. 不确定性策略根据模型对样本的预测不确定性程度选择样本, 而随机策略从数据流中随机选择样本, 混合策略则是结合了随机策略和不确定性策略的一种综合方法.
对于多类非平衡、概念漂移和异常点并存的数据流, 主动学习任务将更具挑战性. 一种简单方法是将标签请求策略添加到上述监督学习算法中. 但是, 这对有些方法(如MOS-ELM)是不适用的, 因为方法要求已知所有样本标签, 另外一些方法(如LB、BOLE和${\rm{ARF}}_{RE}$)由于没有综合考虑标签请求策略与分类方法, 使分类性能受到影响.
另一种更为有效的方法是结合分类方法设计标签请求策略, 即针对在线学习、多类非平衡、异常点和概念漂移这些分类问题设计标签请求策略. Shekhar等[26]提出二类非平衡数据流分类的集成分类器综合框架, 此框架采用根据非平衡比率请求标签的策略. Shan等[27]提出一种漂移数据流的在线主动学习集成(Online active learning ensemble, OALE)方法, 该方法采用不确定性策略和随机策略组成的混合标签请求策略. 当检测到概念漂移时, 优先请求最不确定的样本标签, 以减少标签请求的数量. 但该方法并没有考虑类非平衡比率可变问题. 之后, Liu等[28]提出一种基于概念漂移的多类非平衡数据流综合在线主动学习(Comprehensive active learning method for multi-class imbalanced streaming data with concept drift, CALMID)方法. 该方法采用基于非对称边际阈值矩阵的不确定性策略和随机策略相结合的混合策略作为标签请求策略, 在调整边际阈值矩阵时, 采用固定比率, 而没有区分样本分类的不确定程度.
本文综合考虑在线学习、多类非平衡、概念漂移和异常点这些分类问题来设计标签请求策略, 从而提高主动学习方法的性能.
2. 问题的形式化定义
将所处理的非平衡数据流记作${{DS}}= \{({{x}_{1}},{{y}_{1}}), ({{x}_{2}},{{y}_{2}}),\cdots,({{x}_{t}},{{y}_{t}}),\cdots \}$, 其中$ ({{x}_{t}},{{y}_{t}}) $为 $ t $时刻的数据样本$ {{x}_{t}} $及其类别标签$ {{y}_{t}} $, $ {{x}_{t}} $为$ d $维特征向量, $ {{y}_{t}}\in \{{{C}_{1}},{{C}_{2}},\cdots,{{C}_{k}}\} $, $ k $为数据流中样本的类别数. 本文采用滑动窗口技术处理非平衡数据流的分类问题, 滑动窗口的大小反映了在多大粒度上对数据流进行分析. 在初始化阶段, 滑动窗口$ {{S}_{1}}[size] $用于存放数据流最初的$ size $个样本及其类别标签用于训练集成分类器$ E $, 标签滑动窗口$ {{S}_{2}}[size] $仅存放数据流最初的$ size $个样本的类别标签, 用于计算当前数据流的非平衡比率${ {im{{b}}}}_{t}=(imb_{t}^{1},imb_{t}^{2},\cdots, imb_{t}^{k})$. 在线学习过程中, 基于标签请求策略可得到部分样本的真实标签, 将这些样本及其真实标签通过先进先出的方式更新滑动窗口$ {{S}_{1}} $. $ {{S}_{1}} $中的样本用于概念漂移时重新训练集成分类器; 滑动窗口$ {{S}_{2}} $用于保存最近的$ size $个样本的标签(如采用随机样本标签请求策略对应的样本保存其真实标签; 采用不确定性样本标签请求策略对应的样本保存$ Null $标签; 未请求标签的样本也保存$ Null $标签). 基于$ {{S}_{2}} $, 可计算当前数据流的非平衡比率${ {im{{b}}}}_{t}$.
3. 本文方法
3.1 训练样本的重要性度量
AdaBoost算法是通过将弱分类器多次迭代训练形成强分类器, 在静态数据的二分类问题上具有很高的精度. AdaBoost.M2算法是AdaBoost算法的改进, 将二分类问题扩展到多分类问题, 并充分考虑每个弱分类器的权重, 以提高模型的学习和泛化能力, 较AdaBoost算法, 取得了更好的分类效果[18]. AdaBoost.M2算法适用于静态数据分类, 具体步骤[29]如下.
算法1. AdaBoost.M2
输入. $ k $类$ n $个样本, 记为$({{x}_{i}},{{y}_{i}})\ (i=1, 2, \cdots, n)$, 其中$ {{x}_{i}} $表示第$ i $个样本, $ {{y}_{i}} $表示第$ i $个样本对应的类别.
输出. 集成分类器${{h}_{f(x)}}= \arg{\mathop{\max }}_{y\in Y}\sum_{t=1}^{T}{\lg \{({1}/{{{\eta }_{t}}}})\;\times {{h}_{t}}(x,y)\}$, $Y=\{1,2, \cdots,k\}$.
1)初始化第$ i $个样本的权重$ {{O}_{1}}(i)=1/n $, 初始化样本$ i $的某个错误标签$ y $的权重$ \omega _{i,y}^{1}={{O}_{1}}(i)/(k-1) $.
2)循环迭代$ T $次, $ t=1,2,\cdots,T $.
a)计算第$ t $次迭代中的标签权重和样本权重. 样本权重为$ {{O}_{t}}(i)={M_{i}^{t}}/{\sum_{i=1}^{n}{M_{i}^{t}}} $. 标签权重为$ {{q}_{t}}(i,y)= {\omega _{i,y}^{t}}/{M_{i}^{t}} $, 其中$ M_{i}^{t}=\sum_{y}{\omega _{i,y}^{t}} $, $ y $表示除正确标签$ {{y}_{i}} $以外的其他类别标签.
b)基于$ {{O}_{t}}(i) $和$ {{q}_{t}}(i,y) $, 训练弱分类器$ {{h}_{t}} $.
c)计算$ {{h}_{t}} $的伪损失${{\varepsilon }_{t}} = (1/2)\sum_{i=1}^{n}{{{O}_{t}}(i)}[1 - {{h}_{t}}({{x}_{i}}, {{y}_{i}})\;+ \sum_{y}{{{q}_{t}}(i,y)}\times {{h}_{t}}({{x}_{i}},y)]$, 其中$ {{h}_{t}}({{x}_{i}},{{y}_{i}}) $表示样本$ {{x}_{i}} $属于类别$ {{y}_{i}} $的概率.
d)重置权重更新系数$ {{\eta }_{t}}={{{\varepsilon }_{t}}}/(1-{{\varepsilon }_{t}}) $.
e)计算新的权重$\omega _{i,y}^{t+1} = \omega _{i,y}^{t} \times {{\eta}_{t}}^{(1/2)[1-{{h}_{t}}({{x}_{i}},{{y}_{i}})+{{h}_{t}}({{x}_{i}},y)]}$, 该权重用于第$ t+1 $次训练.
由AdaBoost.M2算法步骤可知, 训练样本的初始权重是相同的. 在多类非平衡数据流环境下使用AdaBoost.M2算法, 为了提高算法分类性能, 需要为样本赋予不同的初始权重, 本文在度量训练样本的重要性时考虑以下2个因素$: $
1)根据非平衡比率对不同类别的训练样本赋予不同的初始权重(非平衡比率高的类别相应的样本权重较小, 反之应该较大);
2)检测到概念漂移时需要重新训练分类器, 此时需要区分样本滑动窗口中样本的到达时间和概念漂移指数(见式(1)), 后到达的样本应该具有较高权重, 概念漂移指数大的样本应该具有较高的权重.
因此, 本文将训练样本的重要性, 即初始权重定义如下:
$$ \begin{equation} W(x)=\alpha (x)\times \lg \left\{1+\frac{1} {{{{imb}}}_{t}^{j}}\right\} \end{equation} $$ (1) 式中, $ \alpha $为自适应遗忘因子, 定义如下:
$$ \alpha(x)=\left\{\begin{aligned} &1 ,& 初始训练 \\ &\exp\left\{-\frac{t-t{'}}{I(x)+1}\right\} ,& 重训练 \quad \end{aligned}\right. $$ (2) 本文将概念漂移指数$ I $引入时间衰减机制, 提出了自适应遗忘因子$ \alpha $. 式(2)中, $ t $表示当前时刻, $t'$表示窗口$ {{S}_{1}} $中样本到达窗口的时间, $ I $表示该样本的概念漂移指数. 式(2)表明自适应遗忘因子在概念漂移后, 取决于概念漂移指数和样本到达窗口的时间2个因素. 因此, 概念漂移指数越大, 样本到达窗口的时间和当前时刻越近, 自适应遗忘因子越大.
${{imb}}_{t}^{j}$是数据流中$ {{C}_{j}} $类在$ t $时刻的非平衡比率, 通过滑动窗口$ {{S}_{2}} $中积累的标签计算:
$$ \begin{equation} {{imb}}_{t}^{j}=\frac{labelnu{{m}_{j}}}{\frac{size-Nullnum}{k}} \end{equation} $$ (3) 式中, $ labelnu{{m}_{j}} $是标签滑动窗口中$ {{C}_{j}} $类的标签个数, $Nullnum$是标签滑动窗口中空标签$Null$的个数, $Null$是在标签请求过程中存放的.
3.2 自适应标签请求算法
本文提出一种基于边际阈值矩阵的自适应标签请求(Label request base on adaptive threshold matrix, LR-ATM)算法, 基于样本分类的不确定程度, 对边际阈值矩阵进行自适应调整, 并根据分类难度请求样本的真实标签.
设$ P({{y}_{{{c}_{1}}}}|{{x}_{t}}) $为集成分类器$ E $对样本$ {{x}_{t}} $的第1预测概率; $ P({{y}_{{{c}_{2}}}}|{{x}_{t}}) $为集成分类器$ E $对样本$ {{x}_{t}} $的第2预测概率. 边际阈值矩阵$ {{({{m}_{ij}})}_{k\times k}} $, 记为${{M}}$, 其中$ {{m}_{ij}} $表示 $Margin({{x}_{t}})=P({{y}_{{{c}_{1}}}}|{{x}_{t}})-P({{y}_{{{c}_{2}}}}|{{x}_{t}})$的阈值, 初值均为$ \theta $. 在线学习过程中, $M$是不断调整的, 具体方式如下:
1)当$Margin({{x}_{t}}) > {M}[{{y}_{{{c}_{1}}}}][{{y}_{{{c}_{2}}}}]$时, 表明$ {{x}_{t}} $的第1预测概率和第2预测概率的差值在限定范围内, 即分类器对$ {{x}_{t}} $的分类是有效的, 此时不请求$ {{x}_{t}} $的标签, 也不调整$M$中相应的阈值.
2)当$Margin({{x}_{t}})\le {M}[{{y}_{{{c}_{1}}}}][{{y}_{{{c}_{2}}}}]$时, 表明分类器对$ {{x}_{t}} $的分类是不确定的, 需要请求$ {{x}_{t}} $的真实标签$ {{y}_{t}} $进一步验证, 若$ {{y}_{{{c}_{1}}}}={{y}_{t}} $, 表明阈值$ {{m}_{{{c}_{1}}{{c}_{2}}}} $对$ {{x}_{t}} $过于严格, 需要减小. 又因为在样本标签请求时, 应该给少数类更多机会, 与之相应的多数类应该有较少机会. 因此若${{{imb}}_{t}^{{{y}_{t}}}} > 0.5$时, 需进一步减小阈值$ {{m}_{{{c}_{1}}{{c}_{2}}}} $.
由于阈值$ {{m}_{{{c}_{1}}{{c}_{2}}}} $减小的程度应与$ {{x}_{t}} $的分类不确定程度成正比, 因此本文提出边际阈值矩阵的自适应调整方法如下:
$$ \begin{equation} {{m}_{{{c}_{1}}{{c}_{2}}}}={{m}_{{{c}_{1}}{{c}_{2}}}}\times (1-\beta \times Margin({{x}_{t}})) \end{equation} $$ (4) 式中, $ Margin({{x}_{t}}) $为$ {{x}_{t}} $的分类不确定程度, $ \beta \in [0, 1] $.
本文提出的自适应标签请求策略基于样本的分类不确定性和类非平衡比率实现对难分类样本筛选, 由人工对这些样本进行确认, 并将人工标注得到的数据保存在样本滑动窗口中, 用于概念漂移后新的集成分类器的训练, 从而提升分类模型性能.
此外, 本文还使用随机标签请求策略, 随机从数据流中选取样本, 并请求其真实标签. 这些被随机选取的样本被认为是有代表性的样本, 反映了某时刻数据流的状态.
3.3 概念漂移检测机制
概念漂移指的是随时间推移, 数据流中的数据分布发生不可预测的变化. 假设目标概念可表示为联合概率分布, 即样本在$ t $时刻的概率分布为$ {{P}_{t}}(x,y) $, 如果在$ t+1 $时刻, 分布发生变化, 即${{P}_{t+1}}(x,y)\;\ne {{P}_{t}}(x,y)$, 则认为发生了概念漂移. 概念漂移可分为虚拟、真实和混合3种类型. 令${{P}_{t}}(x,y)={{P}_{t}}(x)\;\times {{P}_{t}}(y|x)$.
1)虚拟概念漂移是指决策边界未变化, 即$ {{P}_{t}}(y|x)={{P}_{t+1}}(y|x) $, 而样本空间分布变化, 即${{P}_{t}}(x)\;\ne {{P}_{t+1}}(x)$.
2)真实概念漂移是指决策边界变化, 即${{P}_{t}}(y|x)\;\ne {{P}_{t+1}}(y|x)$, 而样本空间分布未变化, 即$ {{P}_{t}}(x)={{P}_{t+1}}(x) $.
3)混合概念漂移是指决策边界和样本空间分布都发生变化, 即$ {{P}_{t}}(y|x)\ne {{P}_{t+1}}(y|x) $, 且${{P}_{t}}(x)\;\ne$ $ {{P}_{t+1}}(x) $.
如果进一步考虑数据流非平衡比率的变化, 即$ {{P}_{t}}(y) $的变化, 可令$ {{P}_{t}}(x,y)={{P}_{t}}(y)\times {{P}_{t}}(x|y) $. 此时的概念漂移可分为以下2种情况:
1) $ {{P}_{t}}(y)={{P}_{t+1}}(y) $、$ {{P}_{t}}(x|y)\ne {{P}_{t+1}}(x|y) $, 此时类非平衡比率并未发生变化.
2) $ {{P}_{t}}(y)\ne {{P}_{t+1}}(y) $、$ {{P}_{t}}(x|y)\ne $$ {{P}_{t+1}}(x|y) $, 此时类非平衡比率发生变化, 因此在检测概念漂移时需要综合考虑非平衡比率的影响.
样本空间分布的变化并不会影响决策边界, 因此, 对数据流中的这类变化无需检测和处理, 只需检测由决策边界变化引起的概念漂移和数据流中非平衡比率的变化. 为此, 本文基于边际阈值矩阵和标签滑动窗口实现概念漂移检测, 通过度量当前样本的预测概率与标签滑动窗口中样本的平均预测概率的不相似性来判断是否发生了概念漂移.
边际阈值矩阵用于表示集成分类器对样本第1预测概率和第2预测概率的差异程度. 当$Margin({{x}_{t}}) \le {M}[{{y}_{{{c}_{1}}}}][{{y}_{{{c}_{2}}}}]$时, 表示对于当前分类器, $ {{x}_{t}} $是一个难分的样本, 这种难分可能是由决策边界的变化或者非平衡比率变化引起的. 因此, 需要请求这些难分样本的标签, 并将其保存在$ {{S}_{1}} $中, 用于分类器的更新.
当数据流中的新样本$ {{x}_{t}} $进入分类器后, 得到一个预测标签$ {{y}_{{{c}_{1}}}} $, 如果满足样本标签请求机制的条件, 就会得到$ {{x}_{t}} $的真实标签$ {{y}_{t}} $. 若$ {{y}_{t}} $属于集合(即$ {{x}_{t}} $不是异常点), 此时需要判断数据流中是否出现概念漂移.
由于$ {{S}_{1}} $中累积了难分或有代表性样本, 如果$ {{x}_{t}} $预测概率与$ {{S}_{1}} $中样本的平均预测概率相差较大, 则认为$ t $时刻发生概念漂移的可能性较大. 因此, 本文定义了如下的概念漂移指数$ I $:
$$ \begin{equation} I({{x}_{t}})=\frac{{{P}_{{\rm{max}}}}-({{P}_{t}}-{{V}_{t}})}{{{V}_{{\rm{min}}}}}-1 \end{equation} $$ (5) 式中, ${{P}_{{\rm{max}}}}$是$ {{S}_{1}} $中样本预测概率的最大值; $ {{P}_{t}} $和$ {{V}_{t}} $分别表示$ {{x}_{t}} $的预测概率和标准差; ${{V}_{{\rm{min}}}}$是$ {{S}_{1}} $中样本预测概率的最小标准差. 标准差$ V $的计算如下:
$$ \begin{equation} V=\sqrt{P\times (1-P)} \end{equation} $$ (6) 基于概念漂移指数$ I $, 可判断是否发生了概念漂移. 当$ I\le 0 $时, 表明未检测到概念漂移; 当$ I\ge 1 $时, 表明发生概念漂移, 需要使用$ {{S}_{1}} $中的样本重新训练集成分类器$ E $; 当$ 1>I>0 $时, 表明数据流处于漂移警告状态, 需要使用$ {{x}_{t}} $在线更新集成分类器$ E $. 在线更新集成分类器的过程是对基分类器自下而上的“剪枝”过程, 对基分类器上的每个非叶子树$ Tr $, 依次用$ Tr $上深度从大到小的叶子尝试替代$ Tr $. 如果$ Tr $被某个叶子替代后得到的基分类器对$ {{x}_{t}} $的误差不变或变小, 则用该叶子替代$ Tr $.
3.4 算法框架
本文提出一种非平衡漂移数据流在线主动学习方法OALM-IDS, 该方法分为3个阶段, 如图1所示. 第1阶段为初始化阶段, 为了训练集成分类器, 首先请求数据流前$ size $个样本的真实标签, 并将带有真实标签$ {{y}_{t}} $的样本$ {{x}_{t}} $存入$ {{S}_{1}} $中, 将真实标签存入$ {{S}_{2}} $中. 然后, 利用$ {{S}_{2}} $中的标签计算类非平衡率${{imb}}_{t}$, 并通过式(1)计算$ {{S}_{1}} $中每个样本的初始权重. 最后, 将$ {{S}_{1}} $中加权的样本作为训练集, 训练集成分类器$ E $.
第2阶段为在线学习阶段, 首先利用集成分类器$ E $对当前样本$ {{x}_{t}} $预测. 然后, 基于随机标签请求策略判断是否需要请求$ {{x}_{t}} $的标签, 如果需要, 则请求; 否则, 进一步基于不确定标签请求策略再次判断是否需要请求$ {{x}_{t}} $的标签. 如果需要, 则请求, 更新边际阈值矩阵内的阈值; 若不需要, 则对下一个样本进行预测.
第3阶段为概念漂移检测阶段, 对于请求了真实标签的样本, 判断是否为异常点, 若是, 则继续预测下一个样本; 若不是, 则基于式(5)计算概念漂移指数$ I({{x}_{t}}) $. 若$ I\le 0 $说明没有检测到概念漂移, 继续对下个样本进行预测; 若$ 1>I>0 $表明进入警告状态, 在线更新集成分类器$ E $; 若$ I\ge 1 $表明检测到概念漂移, 更新$ {{S}_{1}} $中样本的权重并重新训练集成分类器$ E $.
3.5 算法伪代码
本节给出完整的学习算法OALM-IDS和LR-ATM的伪代码.
算法2. OALM-IDS的伪代码
输入. 数据流$ DS $, 已经处理的样本数$ g $, 带标签的样本数$ l $, 标签预算$ b\ (b<\varepsilon) $, 随机选择比率$ \varepsilon $, 滑动窗口大小$ size $, 样本滑动窗口$ {{S}_{1}}[size] $, 标签滑动窗口$ {{S}_{2}}[size] $.
输出. 集成分类器$ E $的预测结果.
1) while (输入一个样本$ {{x}_{t}} $) do;
2)集成分类器$ E $对当前样本$ {{x}_{t}} $预测;
3) $ g=g+1 $;
4) $labelling={\rm{False}}$;
5)生成一个随机变量$ \zeta $, $ \zeta \in [0, 1] $;
6) if ($ \zeta <\varepsilon $或$ g<size $) then;
7) $labelling={\rm{Ture}}$;
8)将真实标签$ {{y}_{t}} $赋予样本$ {{x}_{t}} $;
9)将$ {{y}_{t}} $推入$ {{S}_{2}} $;
10) else if (LR-ATM() and $ (l/g)<b $) then;
11)将$ Null $推入$ {{S}_{2}} $;
12)$labelling={\rm{Ture }}$;
13) else;
14)将$ Null $推入$ {{S}_{2}} $;
15)输出样本$ {{x}_{t}} $的预测结果;
16) end if;
17) if ($labelling={\rm{Ture }}$) then;
18) $ l=l+1 $;
19) if ($ {{y}_{{{c}_{1}}}}\notin \{{{C}_{1}},{{C}_{2}},\cdots,{{C}_{k}}\} $) then;
20)则该点为异常点, 继续对下一个样本进行预测;
21) else;
22)将带标签的样本推入$ {{S}_{1}} $;
23)根据式(5), 计算概念漂移指数$ I $;
24) if ($ I>0 $) then;
25) if ($ I\ge 1 $) then;
26)根据式(2), 计算$ \alpha $;
27)利用$ {{S}_{2}} $中的样本, 重新训练集成分类器$ E $;
28) end if;
29)在线更新集成分类器$ E $;
30) end if;
31) end if;
32) end if;
33) end while.
算法3. LR-ATM的伪代码
输入. 集成分类器$ E $对样本$ x{}_{t} $的第1预测概率$ P({{y}_{{{c}_{1}}}}|{{x}_{t}}) $, 集成分类器$ E $对样本$ {{x}_{t}} $的第2预测概率$ P({{y}_{{{c}_{2}}}}|{{x}_{t}}) $, 自适应阈值矩阵${ M}[k][k]$, 矩阵内阈值的初始值$ \theta $.
输出. $labelling\in \{{\rm{Ture,False}}\}$.
1)计算样本预测难度$ Margin({{x}_{t}}) $;
2) if ($Margin({{x}_{t}})\le {M}[{{y}_{c_1}}][{{y}_{c_2}}]$) then;
3) $labelling={\rm{Ture}}$;
4)计算$ {{y}_{t}} $的类非平衡比率;
5) if ($ {{y}_{{{c}_{1}}}}={{y}_{t}} $) then;
6)根据式(4), 调整矩阵参数;
7) if (${{imb}}_{t}^{{{y}_{t}}} > 0.5$) then;
8)根据式(4), 调整矩阵参数;
9) end if;
10) else
11)不做调整;
12) end if;
13) else
14)不做调整;
15) end if.
3.6 算法复杂度分析
由于初始化阶段和概念漂移检测阶段的时间成本和空间成本取决于AdaBoost.M2算法, 因此只分析在线学习阶段的复杂度.
由算法2可知, 假设目前数据流中有$ N $个样本, 混合标签请求算法的时间复杂度是O$ (N) $; 含有$ D $个基分类器的集成分类器$ E $预测的时间复杂度为O$(D\cdot N\log_2 N)$, 因此$ N $个样本在线学习的时间复杂度为O$(N+D\cdot N\log_2 N)$.
在线学习阶段需要2个滑动窗口$ {{S}_{1}}[size] $和$ {{S}_{2}}[size] $. 因此, 算法的空间复杂度为O$ (size) $.
4. 实验结果与分析
4.1 实验环境及数据
本文实验环境为Windows10操作系统, CPU为Intel Core i7-10750H 2.6 GHz, 内存16 GB. 本文实验均在大规模在线分析平台MOA (Massive online analysis)[30]上实现, 开发软件使用IntelliJ IDEA.
实验使用6个人工数据流和4个真实数据流, 数据流的特征如表1所示. 人工数据流均通过MOA平台生成, 其中${\rm{DS}}_{1}$和${\rm{DS}}_{2}$为平衡数据流, ${\rm{DS}}_{3}$和 ${\rm{DS}}_{4}$为非平衡比率固定的非平衡数据流, ${\rm{DS}}_{5}$和${\rm{DS}}_{6}$为非平衡比率可变的非平衡数据流. 在${\rm{DS}}_{1}$、${\rm{DS}}_{3}$和${\rm{DS}}_{5}$中没有设置概念漂移和异常点, 在${\rm{DS}}_{2}$、${\rm{DS}} _{4} $和$ {\rm{DS}}_{6} $中设置了3次概念漂移和10个异常点. 真实数据流Kddcup$ 99\_10\% $、Statlog (Shuttle)、IoT (IoT botnet attack)和HAR (Human acti-vity recognition)来源于公开数据集UCIs (University of California at irvine), 在这4个数据流中, 概念漂移的类型和异常点的数量是未知的.
表 1 数据流的特征Table 1 Data stream feature数据流 样本数 特征数 类别数 类分布 漂移次数 异常点 ${\rm{DS} }_{1}$ 200000 21 5 (0.2, 0.2, 0.2, 0.2, 0.2) 0 0 ${\rm{DS}}_{2}$ 200000 21 5 (0.2, 0.2, 0.2, 0.2, 0.2) 3 10 ${\rm{DS}}_{3}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1) 0 0 ${\rm{DS}}_{4}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1) 3 10 ${\rm{DS}}_{5}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1), (0.4, 0.2, 0.1, 0.1, 0.2) 0 0 ${\rm{DS}}_{6}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1), (0.4, 0.2, 0.1, 0.1, 0.2) 3 10 Kddcup$99\_10\%$ 494000 42 23 — — — Statlog 570000 10 7 — — — IoT 663000 115 11 — — — HAR 10299 561 6 — — — 4.2 OALM-IDS算法分类性能评价
本节将本文提出的分类算法OALM-IDS与LB、BOLE、${\rm{ARF}} _{RE}$、OALE、CALMID五个分类算法在6个人工数据流和4个真实数据流上进行性能比较, 其中LB、BOLE和${\rm{ARF}}_{RE}$是监督学习算法, OALE和CALMID是主动学习算法. 使用准确率、召回率、F1值、Kappa系数值和接受者操作特征(Receiver operating characteristic, ROC)曲线作为评价指标.
为了确保实验的公平性, 除了${\rm{ARF}}_{RE}$使用其构造的ARFHoeffding树作为基分类器之外, 其他算法均使用Hoeffding树作为基分类器; OALE中数据块大小和CALMID中滑动窗口的大小都设置为500; OALE根据学习条件按需使用真实标签. 此外所有主动学习算法的标签预算均设置为20%. 所有算法在同一数据集上均重复实验10次.
由表2可知, OALM-IDS的准确率在5个人工数据流和4个真实数据流上均为最高, 仅在$ {\rm{DS} }_{1} $上比BOLE低0.1, 这是由于BOLE为监督学习算法, 需要使用所有样本的标签信息, 并且使用了先进的集成分类器AdaBoost.M2.
表 2 6种算法的准确率Table 2 Precision values of six algorithms数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm {DS} }_{1}$ $94.56\pm0.12$ $\boldsymbol{95.61} \;\pm \boldsymbol {0.11} $ $93.54\pm0.13$ $89.78\pm0.21$ $94.76\pm0.16$ $95.48\pm0.15$ ${\rm {DS}}_{2}$ $92.27\pm0.17$ $92.44\pm0.14$ $91.04\pm0.19$ $88.31\pm0.23$ $92.81\pm0.13$ ${\boldsymbol{93.94} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm {DS}}_{3}$ $88.39\pm0.22$ $89.52\pm0.14$ $90.95\pm0.13$ $88.83\pm0.16$ $92.57\pm0.13$ ${\boldsymbol{93.72} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm {DS}}_{4}$ $86.55\pm0.31$ $88.68\pm0.26$ $89.89\pm0.23$ $86.29\pm0.29$ $91.31\pm0.18$ ${\boldsymbol{92.18} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ ${\rm {DS}}_{5}$ $85.64\pm0.29$ $87.04\pm0.34$ $89.61\pm0.51$ $88.83\pm0.21$ $91.13\pm0.21$ ${\boldsymbol{92.92} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.16} }$ ${\rm {DS}}_{6}$ $82.10\pm0.69$ $83.15\pm0.73$ $86.54\pm0.72$ $83.42\pm0.55$ $90.64\pm0.42$ ${\boldsymbol{92.41} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ Kddcup$99\_10\%$ $83.87\pm0.43$ $81.09\pm0.56$ $85.48\pm0.65$ $81.01\pm0.36$ $92.06\pm0.19$ ${\boldsymbol{92.07} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ Statlog $64.55\pm0.31$ $63.78\pm0.61$ $79.97\pm0.39$ $73.78\pm0.43$ $85.40\pm0.34$ ${\boldsymbol{85.68} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.33} }$ IoT $64.03\pm0.48$ $61.54\pm0.43$ $66.66\pm0.53$ $55.81\pm0.51$ $70.85\pm0.54$ ${\boldsymbol{73.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.38} }$ HAR $61.63\pm0.53$ $59.76\pm0.46$ $63.22\pm0.49$ $55.16\pm0.69$ $68.64\pm0.71$ ${\boldsymbol{69.98} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.51} }$ 由表3 ~ 5可知, OALM-IDS的召回率、 F1 值和Kappa系数值在6个人工数据流和4个真实数据流上都优于对比算法, 且F1值有明显提高.
表 3 6种算法的召回率Table 3 Recall values of six algorithms数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $95.37\pm0.18$ $95.96\pm0.13$ $93.39\pm0.11$ $90.13\pm0.13$ $95.91\pm0.11$ ${\boldsymbol{96.14} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm{DS}}_{2}$ $92.39\pm0.21$ $92.28\pm0.35$ $91.35\pm0.26$ $89.45\pm0.18$ $92.51\pm0.15$ ${\boldsymbol{94.08} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14} }$ ${\rm{DS}}_{3}$ $87.55\pm0.19$ $88.19\pm0.22$ $86.14\pm0.21$ $88.52\pm0.22$ $90.55\pm0.13$ ${\boldsymbol{92.52} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm{DS}}_{4}$ $84.57\pm0.36$ $86.73\pm0.29$ $87.47\pm0.28$ $83.05\pm0.31$ $89.89\pm0.21$ ${\boldsymbol{92.44} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ ${\rm{DS}}_{5}$ $84.14\pm0.43$ $86.44\pm0.49$ $87.26\pm0.69$ $83.26\pm0.36$ $90.25\pm0.18$ ${\boldsymbol{91.16} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm{DS}}_{6}$ $83.98\pm1.13$ $81.87\pm0.91$ $84.56\pm1.31$ $78.87\pm0.69$ $90.46\pm0.13$ ${\boldsymbol{90.71} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ Kddcup$99\_10\%$ $60.82\pm0.71$ $62.75\pm0.64$ $58.17\pm1.32$ $58.44\pm1.63$ $61.88\pm0.43$ ${\boldsymbol{63.71} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.37} }$ Statlog $61.39\pm0.91$ $50.92\pm1.32$ $54.36\pm1.11$ $51.20\pm1.34$ $59.52\pm0.63$ ${\boldsymbol{63.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.39} }$ IoT $40.73\pm2.14$ $42.29\pm1.58$ $39.35\pm1.89$ $40.42\pm2.15$ $48.04\pm1.04$ ${\boldsymbol{51.26} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.81} }$ HAR $61.64\pm1.18$ $60.57\pm0.97$ $57.91\pm1.43$ $54.11\pm1.36$ $65.53\pm0.76$ ${\boldsymbol{66.57} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.46} }$ 表 4 6种算法的F1值Table 4 F1 values of six algorithms数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $94.96\pm0.11$ ${\boldsymbol{95.80} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10} }$ $93.42\pm0.13$ $89.93\pm0.15$ $95.33\pm0.11$ ${\boldsymbol{95.80} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10} }$ ${\rm{DS}}_{2}$ $92.32\pm0.16$ $92.34\pm0.13$ $91.18\pm0.15$ $88.85\pm0.21$ $92.65\pm0.13$ ${\boldsymbol{94.01} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm{DS}}_{3}$ $87.91\pm0.20$ $88.81\pm0.24$ $88.11\pm0.36$ $88.67\pm0.20$ $91.50\pm0.16$ ${\boldsymbol{93.07} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14} }$ ${\rm{DS}}_{4}$ $85.35\pm0.42$ $87.38\pm0.36$ $88.42\pm0.51$ $84.50\pm0.33$ $90.51\pm0.21$ ${\boldsymbol{92.29} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20} }$ ${\rm{DS}}_{5}$ $84.85\pm0.41$ $86.67\pm0.43$ $88.30\pm0.46$ $85.36\pm0.48$ $90.62\pm0.21$ ${\boldsymbol{91.93} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ ${\rm{DS}}_{6}$ $82.97\pm0.87$ $82.43\pm0.71$ $85.35\pm0.91$ $80.59\pm0.63$ $90.46\pm0.39$ ${\boldsymbol{91.53} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31} }$ Kddcup$99\_10\%$ $73.12\pm0.55$ $72.47\pm0.63$ $72.01\pm0.46$ $72.81\pm0.51$ $73.56\pm0.33$ ${\boldsymbol{74.65} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20} }$ Statlog $66.18\pm0.83$ $54.32\pm1.91$ $63.85\pm1.03$ $63.42\pm0.98$ $74.42\pm0.36$ ${\boldsymbol{75.19} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31} }$ IoT $47.01\pm1.24$ $48.40\pm0.96$ $47.34\pm1.89$ $44.94\pm1.36$ $54.26\pm0.65$ ${\boldsymbol{56.73} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.67} }$ HAR $59.93\pm0.91$ $58.81\pm1.21$ $58.52\pm0.79$ $54.43\pm1.13$ $65.43\pm0.63$ ${\boldsymbol{67.76} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.58} }$ 表 5 6种算法的Kappa系数值Table 5 Kappa coefficient values of six algorithms数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $90.17\pm0.12$ $91.18\pm0.14$ $90.59\pm0.16$ $85.47\pm0.21$ $90.48\pm0.19$ $\boldsymbol{91.31\pm0.12}$ ${\rm{DS}}_{2}$ $88.85\pm0.19$ $88.14\pm0.23$ $87.91\pm0.39$ $83.18\pm0.56$ $89.97\pm0.31$ ${\boldsymbol{90.66} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.23} }$ ${\rm{DS}}_{3}$ $85.25\pm0.22$ $85.86\pm0.38$ $86.68\pm0.29$ $83.91\pm0.39$ $88.91\pm0.26$ ${\boldsymbol{89.93} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ ${\rm{DS}}_{4}$ $84.15\pm0.55$ $86.04\pm0.63$ $87.14\pm0.66$ $83.42\pm0.71$ $88.92\pm0.33$ ${\boldsymbol{89.33} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.36} }$ ${\rm{DS} }_{5}$ $83.85\pm0.77$ $85.83\pm0.69$ $86.45\pm0.81$ $86.67\pm0.70$ $88.57\pm0.31$ ${\boldsymbol{89.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.29} }$ ${\rm{DS} }_{6} $ $81.49\pm1.12$ $82.98\pm1.69$ $84.15\pm1.87$ $79.92\pm1.48$ $89.01\pm0.41$ ${\boldsymbol{89.73} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.28} }$ Kddcup$99\_10\% $ $80.93\pm0.67$ $75.62\pm1.13$ $79.32\pm1.32$ $78.31\pm0.91$ $83.32\pm0.26$ ${\boldsymbol{85.83} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ Statlog $58.71\pm1.42$ $61.43\pm1.18$ $73.72\pm0.93$ $71.21\pm1.24$ $79.39\pm0.46$ ${\boldsymbol{80.11} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.19} }$ IoT $67.53\pm1.54$ $65.02\pm1.89$ $68.99\pm2.14$ $59.53\pm2.12$ $71.65\pm0.71$ ${\boldsymbol{73.29} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.68} }$ HAR $60.49\pm1.12$ $60.01\pm1.38$ $61.86\pm1.13$ $56.75\pm2.03$ $68.52\pm0.76$ ${\boldsymbol{69.64} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.71} }$ 通过对表2 ~ 5实验结果分析可知, 主动学习算法OALE、CALMID和OALM-IDS的分类性能整体优于监督学习算法LB、BOLE和${\rm{ARF}}_{RE}$; 所有算法在平衡数据流上的分类性能优于非平衡比率固定的非平衡数据流, 且在非平衡比率固定的非平衡数据流上的分类性能优于非平衡比率可变的非平衡数据流; 所有算法在不包含概念漂移和异常点的数据流上的分类性能优于包含概念漂移和异常点的数据流; 所有算法在高维数据流上的分类性能均有不同程度的下降.
ROC曲线可以直观地通过图示分析算法分类性能的优劣, 实验结果如图2所示. ROC曲线下区域的面积可以反映算法分类性能的优劣, 面积越大, 表示分类性能越好. 由图2可知, OALM-IDS算法的ROC曲线下区域的面积在4个人工数据流(${\rm{DS}}_{3}$ ~ ${\rm{DS}}_{6}$)和4个真实数据流中均为最大. 仅在数据流$ {\rm{DS}}_{1} $和$ {\rm{DS}}_{2} $上的面积比$ {\rm{ARF}}_{RE} $略小, 但也极为接近. 这是由于$ {\rm{ARF}}_{RE} $算法为监督学习算法, 即需要使用所有样本的标签信息, 并且该算法仅在对平衡数据流分类时ROC曲线下区域的面积最大. 所有算法在高维数据流上的ROC曲线下区域面积均偏小.
图3 ~ 5展示了主动学习算法OALM-IDS、OALE和CALMID在3个较为复杂的数据流(${\rm DS}_{6} $、Kddcup$ 99\_10\% $和Statlog)上的准确率随样本规模增加的变化曲线. 由图3可知, OALM-IDS算法在处理非平衡比率可变、含有异常点和概念漂移的数据流$ {\rm DS}_{6} $时, 可以用最少的标记样本获得最高的准确率, 明显优于算法OALE和CALMID, 并且优于监督学习算法LB、BOLE和$ {\rm{ARF}}_{RE} $. 由图4和图5可知, OALM-IDS算法优于主动学习算法OALE和3种监督学习算法, 与CALMID算法性能较为接近, 但当数据流中出现概念漂移时, 本文提出的OALM-IDS算法可以用更少的标记样本获取更高准确率, 优于CALMID算法.
基于上述实验结果可知, 本文提出的OALM-IDS算法在3个主动学习算法中分类性能是最优的, 这是由于OALM-IDS算法在以下3个方面做了改进: 1)将AdaBoost.M2方法用于非平衡数据流的分类; 2)引入基于边际阈值矩阵的自适应标签请求策略, 用于解决训练过程中由数据分布改变引起的非平衡比率的变化; 3)基于概念漂移指数定义了自适应遗忘因子, 使得分类模型可以更快地适应新数据.
4.3 消融实验
为了测试OALM-IDS中引入AdaBoost.M2集成分类算法、自适应遗忘因子$ \alpha $和异常点检测机制的作用, 进行了以下3种消融实验: 1)从OALM-IDS中去掉异常点检测机制, 得到OALM-IDS-o算法; 2)在OALM-IDS-o算法的基础上, 去除自适应遗忘因子$ \alpha $, 形成OALM-IDS-oa算法; 3)将OALM-IDS-oa算法中的AdaBoost.M2, 替换成普通的决策树集成分类器, 形成OALM-IDS-oab.
本文实验使用非平衡比率可变的且包含概念漂移和异常点的人工数据流$ {\rm DS}_{6} $, 实验结果如图6所示. 可见, 去掉异常点检测机制后的OALM-IDS-o算法比OALM-IDS算法的准确率有所降低, 进一步去掉自适应遗忘因子$ \alpha $后的OALM-IDS-oa算法的准确率继续下降. 而将OALM-IDS-oa算法中的AdaBoost.M2替换成普通的决策树集成分类器后, 算法OALM-IDS-oab的准确率下降明显, 可见AdaBoost.M2的引入对整个算法准确率的提升贡献很大.
4.4 参数$ \theta $对OALM-IDS算法的影响
边际阈值矩阵的阈值$ \theta $对应请求样本标签的可能性, 下面测试初始阈值$ \theta $对OALM-IDS算法分类性能的影响, 重复实验10次, 实验结果如表6所示. 可见当初始阈值$ \theta =0.5$时, 算法的准确率、召回率、F1值和Kappa系数值最高.
表 6 参数$\theta $对OALM-IDS的影响Table 6 Effect of parameter $\theta $ to OALM-IDS数据流 $\theta $ $b$ 准确率 召回率 F1值 Kappa系数值 0.4 0.17143 $94.21\pm0.16 $ $93.18\pm0.12$ $94.13\pm0.11$ $90.11\pm0.12$ $\rm{DS}_{1}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.180\,26} }$ ${\boldsymbol{95.48} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.15} }$ ${\boldsymbol{96.14}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{95.80}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10}}$ ${\boldsymbol{91.31}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ 0.6 0.19782 $95.03\pm0.15 $ $93.19\pm0.12$ $95.16\pm0.10$ $91.01\pm0.12$ 0.4 0.17136 $93.01\pm0.12 $ $92.81\pm0.16$ $93.04\pm0.13$ $89.09\pm0.26$ $\rm{DS}_{2}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.191\,78} }$ ${\boldsymbol{93.94}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{94.08}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14}}$ ${\boldsymbol{94.01}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{90.66}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.23}}$ 0.6 0.20000 $93.18\pm0.13 $ $93.16\pm0.14$ $93.75\pm0.12$ $90.07\pm0.23$ 0.4 0.17821 $93.24\pm0.13 $ $92.05\pm0.13$ $92.54\pm0.16$ $88.56\pm0.22$ $\rm{DS}_{3}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.195\,12} }$ ${\boldsymbol{93.72}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{92.52}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{93.07}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14}}$ ${\boldsymbol{89.93}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ 0.6 0.20000 $93.43\pm0.13 $ $92.24\pm0.13$ $92.10\pm0.14$ $88.71\pm0.21$ 0.4 0.18423 $91.63\pm0.21 $ $91.34\pm0.18$ $91.76\pm0.20$ $88.54\pm0.38$ $\rm{DS}_{4}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.198\,77} }$ ${\boldsymbol{92.18}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{92.44}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{92.29}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20}}$ ${\boldsymbol{89.33}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.36}}$ 0.6 0.20000 $91.06\pm0.21 $ $91.56\pm0.19$ $91.80\pm0.21$ $88.63\pm0.36$ 0.4 0.18002 $92.01\pm0.16 $ $90.46\pm0.13$ $90.76\pm0.18$ $88.42\pm0.29$ $\rm{DS}_{5}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.197\,22} }$ ${\boldsymbol{92.92} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.16} }$ ${\boldsymbol{91.16}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{91.93}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{89.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.29}}$ 0.6 0.20000 $92.50\pm0.16 $ $90.76\pm0.13$ $91.21\pm0.19$ $88.56\pm0.30$ 0.4 0.18331 $91.02\pm0.21 $ $89.03\pm0.22$ $90.32\pm0.31$ $88.12\pm0.28$ $\rm{DS}_{6}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,23} }$ ${\boldsymbol{92.41}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{90.71}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{91.53}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31}}$ ${\boldsymbol{89.73}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.28}}$ 0.6 0.20000 $91.01\pm0.21 $ $89.92\pm0.22$ $90.12\pm0.31$ $89.13\pm0.28$ 0.4 0.18188 $90.59\pm0.18 $ $63.51\pm0.37$ $73.35\pm0.20$ $83.14\pm0.18$ Kddcup$99\_10\%$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,61} }$ ${\boldsymbol{92.07}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{63.71}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.37}}$ ${\boldsymbol{74.65}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20}}$ ${\boldsymbol{85.83}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ 0.6 0.20000 $91.63\pm0.18 $ $63.63\pm0.37$ $74.43\pm0.21$ $85.61\pm0.18$ 0.4 0.19022 $84.75\pm0.33 $ $62.19\pm0.39$ $74.85\pm0.31$ $78.86\pm0.19$ Statlog ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,94} }$ ${\boldsymbol{85.68}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.33}}$ ${\boldsymbol{63.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.39}}$ ${\boldsymbol{75.19}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31}}$ ${\boldsymbol{80.11}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.19}}$ 0.6 0.20000 $85.66\pm0.33 $ $63.01\pm0.39$ $75.19\pm0.31$ $79.89\pm0.19$ 0.4 0.19113 $71.21\pm0.38 $ $49.86\pm0.81$ $51.21\pm0.67$ $71.61\pm0.68$ IoT ${\boldsymbol{0.5}}$ ${\boldsymbol{0.196\,84} }$ ${\boldsymbol{73.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.38}}$ ${\boldsymbol{51.26}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.81}}$ ${\boldsymbol{56.73}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.67}}$ ${\boldsymbol{73.29}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.68}}$ 0.6 0.20000 $72.11\pm0.39 $ $50.06\pm0.81$ $54.33\pm0.67$ $71.34\pm0.68$ 0.4 0.18634 $66.54\pm0.52 $ $64.32\pm0.48$ $65.05\pm0.59$ $66.81\pm0.72$ HAR ${\boldsymbol{0.5}}$ ${\boldsymbol{0.195\,47} }$ ${\boldsymbol{69.98}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.51}}$ ${\boldsymbol{66.57}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.46}}$ ${\boldsymbol{67.76}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.58}}$ ${\boldsymbol{69.64}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.71}}$ 0.6 0.20000 $64.32\pm0.52 $ $65.14\pm0.46$ $66.11\pm0.58$ $64.32\pm0.71$ 当$\theta =0.4$时, 请求样本标签的可能性减小, 这会导致那些难分、少数类样本请求不到真实标签, 最终使得OALM-IDS算法性能下降; 当$\theta =0.6$时, 请求样本标签的可能性增大, 但由于标签预算$ b $是一定的, 这也会导致难分、少数类样本请求不到足够标签, 也会使得OALM-IDS算法性能下降.
5. 结束语
本文研究多类非平衡、概念漂移和异常点并存的数据流在少量真实标签情况下的在线分类问题, 提出一种非平衡漂移数据流在线主动学习方法. 定义了基于非平衡比率和自适应遗忘因子的训练样本重要性度量, 使得AdaBoost.M2适用于非平衡数据流环境; 提出基于样本分类不确定程度的自适应标签请求策略, 使得难分和少数类样本可以获得更多的训练机会; 定义了基于分类偏差的概念漂移指数, 并将其引入时间衰减机制, 用于模型的重构.
为了增强非平衡数据流在线主动学习方法的鲁棒性, 在未来工作中, 将关注以下问题. 首先, 在有新类的流数据中, 要考虑如何评估异常点的分布情况. 其次, 除了通过主动学习解决样本标签稀缺问题外, 还可以尝试结合迁移学习研究更有效的方法.
-
表 1 数据流的特征
Table 1 Data stream feature
数据流 样本数 特征数 类别数 类分布 漂移次数 异常点 ${\rm{DS} }_{1}$ 200000 21 5 (0.2, 0.2, 0.2, 0.2, 0.2) 0 0 ${\rm{DS}}_{2}$ 200000 21 5 (0.2, 0.2, 0.2, 0.2, 0.2) 3 10 ${\rm{DS}}_{3}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1) 0 0 ${\rm{DS}}_{4}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1) 3 10 ${\rm{DS}}_{5}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1), (0.4, 0.2, 0.1, 0.1, 0.2) 0 0 ${\rm{DS}}_{6}$ 200000 21 5 (0.1, 0.3, 0.4, 0.2, 0.1), (0.4, 0.2, 0.1, 0.1, 0.2) 3 10 Kddcup$99\_10\%$ 494000 42 23 — — — Statlog 570000 10 7 — — — IoT 663000 115 11 — — — HAR 10299 561 6 — — — 
下载: 导出CSV
表 2 6种算法的准确率
Table 2 Precision values of six algorithms
数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm {DS} }_{1}$ $94.56\pm0.12$ $\boldsymbol{95.61} \;\pm \boldsymbol {0.11} $ $93.54\pm0.13$ $89.78\pm0.21$ $94.76\pm0.16$ $95.48\pm0.15$ ${\rm {DS}}_{2}$ $92.27\pm0.17$ $92.44\pm0.14$ $91.04\pm0.19$ $88.31\pm0.23$ $92.81\pm0.13$ ${\boldsymbol{93.94} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm {DS}}_{3}$ $88.39\pm0.22$ $89.52\pm0.14$ $90.95\pm0.13$ $88.83\pm0.16$ $92.57\pm0.13$ ${\boldsymbol{93.72} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm {DS}}_{4}$ $86.55\pm0.31$ $88.68\pm0.26$ $89.89\pm0.23$ $86.29\pm0.29$ $91.31\pm0.18$ ${\boldsymbol{92.18} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ ${\rm {DS}}_{5}$ $85.64\pm0.29$ $87.04\pm0.34$ $89.61\pm0.51$ $88.83\pm0.21$ $91.13\pm0.21$ ${\boldsymbol{92.92} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.16} }$ ${\rm {DS}}_{6}$ $82.10\pm0.69$ $83.15\pm0.73$ $86.54\pm0.72$ $83.42\pm0.55$ $90.64\pm0.42$ ${\boldsymbol{92.41} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ Kddcup$99\_10\%$ $83.87\pm0.43$ $81.09\pm0.56$ $85.48\pm0.65$ $81.01\pm0.36$ $92.06\pm0.19$ ${\boldsymbol{92.07} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ Statlog $64.55\pm0.31$ $63.78\pm0.61$ $79.97\pm0.39$ $73.78\pm0.43$ $85.40\pm0.34$ ${\boldsymbol{85.68} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.33} }$ IoT $64.03\pm0.48$ $61.54\pm0.43$ $66.66\pm0.53$ $55.81\pm0.51$ $70.85\pm0.54$ ${\boldsymbol{73.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.38} }$ HAR $61.63\pm0.53$ $59.76\pm0.46$ $63.22\pm0.49$ $55.16\pm0.69$ $68.64\pm0.71$ ${\boldsymbol{69.98} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.51} }$
下载: 导出CSV
表 3 6种算法的召回率
Table 3 Recall values of six algorithms
数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $95.37\pm0.18$ $95.96\pm0.13$ $93.39\pm0.11$ $90.13\pm0.13$ $95.91\pm0.11$ ${\boldsymbol{96.14} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm{DS}}_{2}$ $92.39\pm0.21$ $92.28\pm0.35$ $91.35\pm0.26$ $89.45\pm0.18$ $92.51\pm0.15$ ${\boldsymbol{94.08} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14} }$ ${\rm{DS}}_{3}$ $87.55\pm0.19$ $88.19\pm0.22$ $86.14\pm0.21$ $88.52\pm0.22$ $90.55\pm0.13$ ${\boldsymbol{92.52} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm{DS}}_{4}$ $84.57\pm0.36$ $86.73\pm0.29$ $87.47\pm0.28$ $83.05\pm0.31$ $89.89\pm0.21$ ${\boldsymbol{92.44} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ ${\rm{DS}}_{5}$ $84.14\pm0.43$ $86.44\pm0.49$ $87.26\pm0.69$ $83.26\pm0.36$ $90.25\pm0.18$ ${\boldsymbol{91.16} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13} }$ ${\rm{DS}}_{6}$ $83.98\pm1.13$ $81.87\pm0.91$ $84.56\pm1.31$ $78.87\pm0.69$ $90.46\pm0.13$ ${\boldsymbol{90.71} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ Kddcup$99\_10\%$ $60.82\pm0.71$ $62.75\pm0.64$ $58.17\pm1.32$ $58.44\pm1.63$ $61.88\pm0.43$ ${\boldsymbol{63.71} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.37} }$ Statlog $61.39\pm0.91$ $50.92\pm1.32$ $54.36\pm1.11$ $51.20\pm1.34$ $59.52\pm0.63$ ${\boldsymbol{63.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.39} }$ IoT $40.73\pm2.14$ $42.29\pm1.58$ $39.35\pm1.89$ $40.42\pm2.15$ $48.04\pm1.04$ ${\boldsymbol{51.26} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.81} }$ HAR $61.64\pm1.18$ $60.57\pm0.97$ $57.91\pm1.43$ $54.11\pm1.36$ $65.53\pm0.76$ ${\boldsymbol{66.57} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.46} }$
下载: 导出CSV
表 4 6种算法的F1值
Table 4 F1 values of six algorithms
数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $94.96\pm0.11$ ${\boldsymbol{95.80} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10} }$ $93.42\pm0.13$ $89.93\pm0.15$ $95.33\pm0.11$ ${\boldsymbol{95.80} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10} }$ ${\rm{DS}}_{2}$ $92.32\pm0.16$ $92.34\pm0.13$ $91.18\pm0.15$ $88.85\pm0.21$ $92.65\pm0.13$ ${\boldsymbol{94.01} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12} }$ ${\rm{DS}}_{3}$ $87.91\pm0.20$ $88.81\pm0.24$ $88.11\pm0.36$ $88.67\pm0.20$ $91.50\pm0.16$ ${\boldsymbol{93.07} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14} }$ ${\rm{DS}}_{4}$ $85.35\pm0.42$ $87.38\pm0.36$ $88.42\pm0.51$ $84.50\pm0.33$ $90.51\pm0.21$ ${\boldsymbol{92.29} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20} }$ ${\rm{DS}}_{5}$ $84.85\pm0.41$ $86.67\pm0.43$ $88.30\pm0.46$ $85.36\pm0.48$ $90.62\pm0.21$ ${\boldsymbol{91.93} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ ${\rm{DS}}_{6}$ $82.97\pm0.87$ $82.43\pm0.71$ $85.35\pm0.91$ $80.59\pm0.63$ $90.46\pm0.39$ ${\boldsymbol{91.53} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31} }$ Kddcup$99\_10\%$ $73.12\pm0.55$ $72.47\pm0.63$ $72.01\pm0.46$ $72.81\pm0.51$ $73.56\pm0.33$ ${\boldsymbol{74.65} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20} }$ Statlog $66.18\pm0.83$ $54.32\pm1.91$ $63.85\pm1.03$ $63.42\pm0.98$ $74.42\pm0.36$ ${\boldsymbol{75.19} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31} }$ IoT $47.01\pm1.24$ $48.40\pm0.96$ $47.34\pm1.89$ $44.94\pm1.36$ $54.26\pm0.65$ ${\boldsymbol{56.73} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.67} }$ HAR $59.93\pm0.91$ $58.81\pm1.21$ $58.52\pm0.79$ $54.43\pm1.13$ $65.43\pm0.63$ ${\boldsymbol{67.76} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.58} }$
下载: 导出CSV
表 5 6种算法的Kappa系数值
Table 5 Kappa coefficient values of six algorithms
数据流 LB BOLE ${\rm{ARF}}_{RE}$ OALE CALMID OALM-IDS ${\rm{DS}}_{1}$ $90.17\pm0.12$ $91.18\pm0.14$ $90.59\pm0.16$ $85.47\pm0.21$ $90.48\pm0.19$ $\boldsymbol{91.31\pm0.12}$ ${\rm{DS}}_{2}$ $88.85\pm0.19$ $88.14\pm0.23$ $87.91\pm0.39$ $83.18\pm0.56$ $89.97\pm0.31$ ${\boldsymbol{90.66} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.23} }$ ${\rm{DS}}_{3}$ $85.25\pm0.22$ $85.86\pm0.38$ $86.68\pm0.29$ $83.91\pm0.39$ $88.91\pm0.26$ ${\boldsymbol{89.93} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21} }$ ${\rm{DS}}_{4}$ $84.15\pm0.55$ $86.04\pm0.63$ $87.14\pm0.66$ $83.42\pm0.71$ $88.92\pm0.33$ ${\boldsymbol{89.33} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.36} }$ ${\rm{DS} }_{5}$ $83.85\pm0.77$ $85.83\pm0.69$ $86.45\pm0.81$ $86.67\pm0.70$ $88.57\pm0.31$ ${\boldsymbol{89.12} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.29} }$ ${\rm{DS} }_{6} $ $81.49\pm1.12$ $82.98\pm1.69$ $84.15\pm1.87$ $79.92\pm1.48$ $89.01\pm0.41$ ${\boldsymbol{89.73} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.28} }$ Kddcup$99\_10\% $ $80.93\pm0.67$ $75.62\pm1.13$ $79.32\pm1.32$ $78.31\pm0.91$ $83.32\pm0.26$ ${\boldsymbol{85.83} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18} }$ Statlog $58.71\pm1.42$ $61.43\pm1.18$ $73.72\pm0.93$ $71.21\pm1.24$ $79.39\pm0.46$ ${\boldsymbol{80.11} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.19} }$ IoT $67.53\pm1.54$ $65.02\pm1.89$ $68.99\pm2.14$ $59.53\pm2.12$ $71.65\pm0.71$ ${\boldsymbol{73.29} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.68} }$ HAR $60.49\pm1.12$ $60.01\pm1.38$ $61.86\pm1.13$ $56.75\pm2.03$ $68.52\pm0.76$ ${\boldsymbol{69.64} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.71} }$
下载: 导出CSV
表 6 参数$\theta $对OALM-IDS的影响
Table 6 Effect of parameter $\theta $ to OALM-IDS
数据流 $\theta $ $b$ 准确率 召回率 F1值 Kappa系数值 0.4 0.17143 $94.21\pm0.16 $ $93.18\pm0.12$ $94.13\pm0.11$ $90.11\pm0.12$ $\rm{DS}_{1}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.180\,26} }$ ${\boldsymbol{95.48} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.15} }$ ${\boldsymbol{96.14}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{95.80}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.10}}$ ${\boldsymbol{91.31}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ 0.6 0.19782 $95.03\pm0.15 $ $93.19\pm0.12$ $95.16\pm0.10$ $91.01\pm0.12$ 0.4 0.17136 $93.01\pm0.12 $ $92.81\pm0.16$ $93.04\pm0.13$ $89.09\pm0.26$ $\rm{DS}_{2}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.191\,78} }$ ${\boldsymbol{93.94}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{94.08}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14}}$ ${\boldsymbol{94.01}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.12}}$ ${\boldsymbol{90.66}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.23}}$ 0.6 0.20000 $93.18\pm0.13 $ $93.16\pm0.14$ $93.75\pm0.12$ $90.07\pm0.23$ 0.4 0.17821 $93.24\pm0.13 $ $92.05\pm0.13$ $92.54\pm0.16$ $88.56\pm0.22$ $\rm{DS}_{3}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.195\,12} }$ ${\boldsymbol{93.72}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{92.52}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{93.07}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.14}}$ ${\boldsymbol{89.93}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ 0.6 0.20000 $93.43\pm0.13 $ $92.24\pm0.13$ $92.10\pm0.14$ $88.71\pm0.21$ 0.4 0.18423 $91.63\pm0.21 $ $91.34\pm0.18$ $91.76\pm0.20$ $88.54\pm0.38$ $\rm{DS}_{4}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.198\,77} }$ ${\boldsymbol{92.18}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{92.44}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{92.29}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20}}$ ${\boldsymbol{89.33}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.36}}$ 0.6 0.20000 $91.06\pm0.21 $ $91.56\pm0.19$ $91.80\pm0.21$ $88.63\pm0.36$ 0.4 0.18002 $92.01\pm0.16 $ $90.46\pm0.13$ $90.76\pm0.18$ $88.42\pm0.29$ $\rm{DS}_{5}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.197\,22} }$ ${\boldsymbol{92.92} }\;{\boldsymbol{\pm}}\;{\boldsymbol{0.16} }$ ${\boldsymbol{91.16}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.13}}$ ${\boldsymbol{91.93}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{89.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.29}}$ 0.6 0.20000 $92.50\pm0.16 $ $90.76\pm0.13$ $91.21\pm0.19$ $88.56\pm0.30$ 0.4 0.18331 $91.02\pm0.21 $ $89.03\pm0.22$ $90.32\pm0.31$ $88.12\pm0.28$ $\rm{DS}_{6}$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,23} }$ ${\boldsymbol{92.41}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{90.71}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.21}}$ ${\boldsymbol{91.53}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31}}$ ${\boldsymbol{89.73}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.28}}$ 0.6 0.20000 $91.01\pm0.21 $ $89.92\pm0.22$ $90.12\pm0.31$ $89.13\pm0.28$ 0.4 0.18188 $90.59\pm0.18 $ $63.51\pm0.37$ $73.35\pm0.20$ $83.14\pm0.18$ Kddcup$99\_10\%$ ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,61} }$ ${\boldsymbol{92.07}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ ${\boldsymbol{63.71}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.37}}$ ${\boldsymbol{74.65}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.20}}$ ${\boldsymbol{85.83}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.18}}$ 0.6 0.20000 $91.63\pm0.18 $ $63.63\pm0.37$ $74.43\pm0.21$ $85.61\pm0.18$ 0.4 0.19022 $84.75\pm0.33 $ $62.19\pm0.39$ $74.85\pm0.31$ $78.86\pm0.19$ Statlog ${\boldsymbol{0.5}}$ ${\boldsymbol{0.199\,94} }$ ${\boldsymbol{85.68}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.33}}$ ${\boldsymbol{63.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.39}}$ ${\boldsymbol{75.19}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.31}}$ ${\boldsymbol{80.11}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.19}}$ 0.6 0.20000 $85.66\pm0.33 $ $63.01\pm0.39$ $75.19\pm0.31$ $79.89\pm0.19$ 0.4 0.19113 $71.21\pm0.38 $ $49.86\pm0.81$ $51.21\pm0.67$ $71.61\pm0.68$ IoT ${\boldsymbol{0.5}}$ ${\boldsymbol{0.196\,84} }$ ${\boldsymbol{73.12}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.38}}$ ${\boldsymbol{51.26}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.81}}$ ${\boldsymbol{56.73}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.67}}$ ${\boldsymbol{73.29}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.68}}$ 0.6 0.20000 $72.11\pm0.39 $ $50.06\pm0.81$ $54.33\pm0.67$ $71.34\pm0.68$ 0.4 0.18634 $66.54\pm0.52 $ $64.32\pm0.48$ $65.05\pm0.59$ $66.81\pm0.72$ HAR ${\boldsymbol{0.5}}$ ${\boldsymbol{0.195\,47} }$ ${\boldsymbol{69.98}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.51}}$ ${\boldsymbol{66.57}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.46}}$ ${\boldsymbol{67.76}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.58}}$ ${\boldsymbol{69.64}}\;{\boldsymbol{\pm}}\;{\boldsymbol{0.71}}$ 0.6 0.20000 $64.32\pm0.52 $ $65.14\pm0.46$ $66.11\pm0.58$ $64.32\pm0.71$
下载: 导出CSV
-
[1] 于洪, 何德牛, 王国胤, 李劼, 谢永芳. 大数据智能决策. 自动化学报, 2020, 46(5): 878−896Yu Hong, He De-Niu, Wang Guo-Yin, Li Jie, Xie Yong-Fang. Big data for intelligent decision making. Acta Automatica Sinica, 2020, 46(5): 878−896 [2] Lu J, Liu A, Dong F, Gu F, Gama J, Zhang G. Learning under concept drift: A review. IEEE Transactions on Knowledge and Data Engineering, 2020, 31(12): 2346−2363 [3] Liu W, Zhang H, Liu Q. An air quality grade forecasting approach based on ensemble learning. In: Proceedings of the International Conference on Artificial Intelligence and Advanced Manufacturing. Dublin, Ireland: AIAM, 2019. 87−91 [4] Cano A, Krawczyk B. Kappa updated ensemble for drifting data stream mining. Machine Learning, 2020, 109(1): 175−218 doi: 10.1007/s10994-019-05840-z [5] Liu A, Lu J, Zhang G. Concept drift detection via equal intensity k-means space partitioning. IEEE Transactions on Cybernetics, 2020, 51(6): 3198−3211 [6] 王金甲, 张玉珍, 夏静, 王凤嫔. 多层局部块坐标下降法及其驱动的分类重构网络. 自动化学报, 2020, 46(12): 2647−2661Wang Jin-Jia, Zhang Yu-Zhen, Xia Jing, Wang Feng-Pin. Multi-layer local block coordinate descent algorithm and unfolding classification and reconstruction networks. Acta Automatica Sinica, 2020, 46(12): 2647−2661 [7] Lu Y, Cheung M Y, Tang Y Y. Adaptive chunk-based dynamic weighted majority for imbalanced data stream with concept drift. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(8): 2764−2778 doi: 10.1109/TNNLS.2019.2951814 [8] Grzyb J, Klikowski J, Woźniak M. Hellinger distance weighted ensemble for imbalanced data stream classification. Journal of Computational Science, 2021, 51: Article No. 101314 doi: 10.1016/j.jocs.2021.101314 [9] Kim T, Park C H. Anomaly pattern detection for streaming data. Expert Systems With Applications, 2020, 149: Article No. 113252 doi: 10.1016/j.eswa.2020.113252 [10] Wankhade K K, Dongre S S, Jondhale K C. Data stream classification: A review. Iran Journal of Computer Science, 2020, 3: 239−260 doi: 10.1007/s42044-020-00061-3 [11] Bahri M, Bifet A, Gama J, Gomes H M, Maniu S. Data stream analysis: Foundations, major tasks and tools. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2021, 11(3): Article No. e1405 [12] Kontopoulos I, Chatzikokolakis K, Tserpes K, Zissis D. Classification of vessel activity in streaming data. In: Proceedings of the 14th ACM International Conference on Distributed and Event-based Systems. Jerusalem, Israel: ACM, 2020. 153−164 [13] Wang S, Minku L L. Auc estimation and concept drift detection for imbalanced data streams with multiple classes. In: Proceedings of the International Joint Conference on Neural Networks. Glasgow, UK: IJCNN, 2020. 1−8 [14] Fan S, Zhang X, Song Z. Reinforced knowledge distillation: Multi-class imbalanced classifier based on policy gradient reinforcement learning. Neurocomputing, 2021, 463: 422−436 doi: 10.1016/j.neucom.2021.08.040 [15] Bifet A, Holmes G, Pfahringer B. Leveraging bagging for evolving data stream. In: Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Barcelona, Spain: PKDD, 2010. 135−150 [16] Mirza B, Lin Z. Meta-cognitive online sequential extreme learning machine for imbalanced and concept drifting data classification. Neural Networks, 2016, 80: 79−94 doi: 10.1016/j.neunet.2016.04.008 [17] Barros R S M, Carvalho-Santos S G T, Júnior P M G. A boosting-like online learning ensemble. In: Proceedings of the International Joint Conference on Neural Networks. Vancouver, Canada: IJCNN, 2016. 1871−1878 [18] Carvalho-Santos S G T, Barros R S M. Online AdaBoost-based methods for multi-class problems. Artificial Intelligence Review, 2020, 53(2): 1293−1322 doi: 10.1007/s10462-019-09696-6 [19] Ferreira L E B, Gomes H M, Bifet A, Oliveira L S. Adaptive random forests with resampling for imbalanced data stream. In: Proceedings of the International Joint Conference on Neural Networks. Budapest, Hungary: IJCNN, 2019. 1−6 [20] Ren P Z, Xiao Y, Chang X J, Huang P Y, Li Z, Gupta B B, et al. A survey of deep active learning. ACM Computing Surveys, 2021, 54(9): 1−40 [21] Yousaf M S, Ahmad I, Khurshid A, Ikram M. Machine assisted classification of chicken, beef and mutton tissues using optical polarimetry and bagging model. Photodiagnosis and Photodyna-mic Therapy, 2020, 31: Article No. 101779 doi: 10.1016/j.pdpdt.2020.101779 [22] Wang Y, Feng L. An adaptive boosting algorithm based on weighted feature selection and category classification confidence. Applied Intelligence, 2021, 51(10): 1−22 [23] Gomes H M, Bifet A, Read J, Barddal J P, Enembreck F, Pfharinger B, et al. Adaptive random forests for evolving data stream classification. Machine Learning, 2017, 106(9): 1469−1495 [24] Babüroǧlu E S, Durmuşoǧlu A, Dereli T. Novel hybrid pair recommendations based on a large-scale comparative study of concept drift detection. Expert Systems With Applications, 2021, 163: Article No. 113786 doi: 10.1016/j.eswa.2020.113786 [25] 刘子昂, 蒋雪, 伍冬睿. 基于池的无监督线性回归主动学习. 自动化学报, 2021, 47(12): 2771−2783Liu Zi-Ang, Jiang Xue, Wu Dong-Rui. Unsupervised pool-based active learning for linear regression. Acta Automatica Sinica, 2021, 47(12): 2771−2783 [26] Shekhar S, Ghavamzadeh M, Javidi T. Active learning for classification with abstention. IEEE Journal on Selected Areas in Information Theory, 2021, 2(2): 705−719 doi: 10.1109/JSAIT.2021.3081433 [27] Shan J, Zhang H, Liu W, Liu Q. Online active learning ensemble framework for drifted data stream. IEEE Transactions on Neural Networks and Learning Systems, 2018, 30(2): 486−498 [28] Liu W, Zhang H, Ding Z, Liu Q, Zhu C. A comprehensive active learning method for multi-class imbalanced data stream with concept drift. Knowledge-based Systems, 2021, 215: Article No. 106778 doi: 10.1016/j.knosys.2021.106778 [29] Gu X, Angelov P P. Multi-class fuzzily weighted adaptive boosting-based self-organising fuzzy inference ensemble systems for classification. IEEE Transactions on Fuzzy Systems, 2021, 30(9): 3722−3735 [30] Bifet A, Holmes G, Kirkby R, Pfahringer B. MOA: Massive online analysis. Journal of Machine Learning Research, 2010, 11: 1601−1604 doi: 10.21105/joss.01970 期刊类型引用(1)
1. 朱诗能，韩萌，杨书蓉，代震龙，杨文艳，丁剑. 不平衡数据流的集成分类方法综述. 计算机工程与应用. 2025(02): 59-72 . 
百度学术其他类型引用(0)
-
下载:
计量
- 文章访问数: 296
- HTML全文浏览量: 68
- PDF下载量: 108
- 被引次数: 1
