基于深度信念网络的高维传感器数据异常检测算法*

金 鹏,夏晓峰,乔 焰,3*,崔信红

(1.安徽农业大学信息与计算机学院,合肥 230036;2.国家开发银行信息科技局,北京 100000; 3.北京邮电大学网络与交换技术国家重点实验室,北京 100876)

随着物联网的普及,无线传感器网络WSNs(Wireless Sensor Networks)已经被广泛地应用于各个领域,通过分析与挖掘传感器所采集上报的数据,能够为各个行业提供极具价值的有效信息。然而复杂的部署环境以及传感器自身的内存、CPU以及能源的条件非常容易使传感器发生软硬件故障,从而产生异常数据,而对掺杂异常数据集合的分析会严重影响有效信息的挖掘及关键决策的制定。因此实时准确地检测出无线传感器网络所采集的异常数据变得愈发重要。及时检测出异常数据一方面可以更好的保证传感器所采集数据的安全性和可靠性;另一方面,异常数据在某些监测环境下能够发挥重要的作用,例如,可通过采集到的异常数据来判断是否发生了某种突发事件(如火灾、空气污染、洪水及人为破坏等)[1-3]。然而,随着传感器网络规模的不断扩大,及所采集数据的日趋复杂,对传感器数据异常的检测变得越来越困难,主要表现为以下几个方面:①无论是分布式还是集中式的数据处理,均要求对异常数据的检测要具备较低的时间和空间复杂度,从而应对海量的采集数据;②由于传感器通常实时地采集并上传数据,因此要求数据的异常检测需要具备在线检测的能力;③现如今,越来越多的数据呈现高维的特征(一个数据项包含温度,湿度,光照,坐标,位移等诸多维度),高维数据一方面会增加异常检测的计算时间,另一方面若异常仅出现在少部分维度上,则这些异常数据很难与正常数据相区分。

过去的几年中,已经有不少学者提出了无线传感器网络的异常数据检测方法,主要可以分为以下四类:基于近邻的方法[4-9]、基于聚类的方法[10-11]、基于统计的方法[12-13]以及基于分类的方法[14-16]。基于近邻的方法通过计算自身数据与相邻节点数据之间的距离来确定自身数据是否异常,如果某个数据与邻居节点采集的数据存在较大差异则称为异常数据,但是计算每个数据之间的距离会花费较长的时间,无法应用在大规模传感器网络中;基于聚类的方法通过对数据分簇来孤立异常数据,但此方法需要在得到全部数据后再进行分簇,不能在线式地检测异常数据。基于统计的方法是利用历史数据分布,建立数据的统计模型,不符合该模型的数据视为异常数据。但对于维度较大的数据集合,该方法很难建立较准确的统计模型。基于分类的方法通过历史数据训练得到一个分类模型,再将待检测数据分类到所属的模型之中,不属于任何类型的数据,将视为异常数据。该方法能够在保证检测准确度的情况下满足在线检测的需求,并可应用于高维数据集合的异常检测,是近几年较为主流的异常检测方法。其中基于单类支持向量机OCSVM(One-Class Support Vector Machine)的异常检测方法是目前应用最广泛的基于分类的异常检测方法之一,它能在无监督模式下高效实时地检测所采集数据中的异常数据。但OCSVM也存在重要的缺陷,由于在训练过程中需要求解非线性规划问题,当数据维度增加时,训练时间会呈指数级增加。为了解决以上问题,文献[17-18]提出了可利用深度信念网络DBN(Deep Belief Network)对采集到的数据做降维处理,再对降维后的数据进行异常分类,这样能够大大降低OCSVM的训练时间。但经过降维后,仅有较明显的(即出现异常维度较多的)异常数据能够保持与正常数据的较大差异,而不明显的(出现异常维度较少的)异常数据经过降维后,OCSVM无法再将其与正常数据区分,从而导致较低的检测准确度。

其中文献[4]提出一种预测模型,对依据传感器节点的以往数据进行分析并对给出预测值,将实测值与预测值之间的差距来发现其中的异常数据,实现了传感器数据的实时检测,提高了算法的效率;但是预测模型不适合处理高维的数据。文献[12]提出了一种基于数学统计的算法,利用核函数对收集的数据进行异常检测,从而找出异常数据;但是该方法需要大量的数据,无法实现实时监测。文献[8]中提出了一种基于距离的数据流异常检测算法,该算法使用滑动窗口来实现数据截取检测,从而实现实时的检测,该方法比前面的嵌套循环算法有较大的改进,但是没有考虑到从窗口离开的数据对新检测的数据的影响。文献[14]提出了一种基于超球面的单类支持向量机,通过得到最小半径的超球面来实现数据异常的检测,超出计算得知的超球面,并被视为异常值。但是这个算法需要高的二次优化。文献[15]提出了一种基于四分之一球面的支持向量机,通过计算得到以原点为中心的四分之一超球面,该方法将原本单类支持向量机中二次优化问题转化为线性问题,从来减少复杂度,但是不能实现实时检测,并且建模过程复杂。

本文在以上研究的基础上,针对OCSVM进行优化,提出了一种基于DBN的1/4超球面支持向量机QSSVM(Quarter-Sphere Support Vector Machine)异常检测模型,并在此模型基础上提出一种在线式的异常检测算法。首先将高维数据利用DBN进行降维处理,再针对降维后的数据通过QSSVM结合滑动窗口模型实现高效实时的异常检测。经实验表明,新算法可以更好地处理大规模高维传感器数据,在降低了时间复杂度的同时,提高了异常检测的准确度。总结来说,本文主要在传感器数据异常检测领域做出以下贡献:

①提出了DBN-QSSVM异常检测模型。实验表明,经过DBN的降维,原数据集合中的异常数据呈线性不对称的分布,而传统的更适用于对称分布的单分类支持向量机在处理不对称分布数据时,容易得到有偏的超球面半径。因此,当待检测数据仅有部分维度异常时,异常数据与正常数据虽在高维映射空间存在少量差异,但对于单分类支持向量机却难以区分。而本文提出的新模型所训练得到的QSSVM更适用于区分不对称分布的异常数据,在仅有部分维度异常的情况下,仍具备较高的检测准确度;

②提出了基于滑动窗口的在线式异常检测算法。由于传感器所采集的数据具备一定的时间相关性,因此,所采集数据的分布会根据时间的推移而发生变化,根据当前窗口数据所训练的模型相比单一历史数据所训练的模型更具实时性。本文在新模型基础上提出基于滑动窗口的在线异常检测算法,一方面能满足在线式检测的需求,另一方面能利用数据的时间相关性提高在线检测的检测准确度;

③实验采用真实传感器数据验证了新算法的有效性。本文实验收集了UCI机器学习库中的四个真实的高维传感器数据集合(Forest数据,GAS数据,DSA数据和HAR数据),并与先前基于单分类支持向量机的异常检测方法做了对比,实验结果表明,平均情况下,新方法能够将检测准确度提高17.57%,误检率降低20.02%。此外,本文提出的新模型将原有模型中的非线性规划问题转换为线性规划问题,相比原有方法,新方法将训练时间和检测时间之和降低了约50%。

1 背景知识及问题描述

本节首先介绍单分类支持向量机(OCSVM),1/4超球面支持向量机(QSSVM)及深度信念网络(DBN)的基本概念和原理,然后通过实验数据说明QSSVM相比传统OCSVM在处理DBN降维后的数据时更具优越性。

图1 OCSVM超球面分类模型

1.1 单分类支持向量机(OCSVM)

OCSVM按照大部分输入数据在高维空间中的相互距离将输入数据进行单分类,并将待检测数据中不属于该分类的数据视为异常[19]。TAX等人[20]提出的基于超球面的支持向量机将在低维空间中不可分的数据映射到高维特征空间,并找到一个可以包围绝大部分样本点的超球面,将排除在超球面之外的样本点作为异常样本。图1为超球面OCSVM异常检测模型,图1中位于球面边缘的白色样本点表示边界支持向量,球面内部的灰色样本节点是正常数据,球面以外的黑色样本节点是异常样本数据,其中超球面的半径R表示球心到边界支持向量之间的距离,由边界支持向量机与球心的距离决定。

假设X={xi,1≤i≤n}为n个训练样本数据,特征空间中训练样本球面半径的计算可规划为以下问题的求解:

(1)

s.t. ‖Φ(xi)-C‖2-R2≤ξiξi≥0,i=1,2,…,n

其中Φ(·)为样本到高维特征空间的映射函数,R和C分别为高维空间中超球面的半径和球心,ξi是松弛变量,允许部分样本在球面之外,v∈(0,1)为在球面之外样本的比率。式(1)的对偶形式可表示为:

(2)

其中k(xi,xj)=Φ(xi)·Φ(xj)是核函数,表示xi和xj在高维特征空间的距离。在特征空间中,任意样本x与球心的距离可通过以下公示计算:

(3)

当d≤R时,x为正常节点,当d>R时,其为异常节点。

图2 QSSVM分类模型

1.2 1/4超球面支持向量机(QSSVM)

由于OCSVM需要在模型训练时求解二次规划问题(式(2)),时间复杂度较高,P Laskov在文献[15]中提出单类QSSVM,将二次规划问题转化为线性规划问题,从而降低了时间复杂度。QSSVM将输入样本映射到高维特征空间,并将特征空间中样本的圆心移到坐标轴的原点,以正坐标轴为方向,得到一个1/4超球面,在球面内部的数据,为正常样本数据,球面外部的数据为异常样本数据,图2为QSSVM分类模型。

训练样本X={xi,1≤i≤n}在特征空间的1/4球面可通过求解以下问题得到:

(4)

s.t. ‖Φ(xi)‖2≤R2+ξi

ξi≥0,i=1,2,…,n

式(4)的对偶问题可表示为:.

(5)

相比球面OCSVM的非线性规划问题(式(2)),式(5)的线性规划问题将计算复杂度大大降低。

但由于基于距离的核函数k(xi,xi)对于任何样本节点均相等,因此式(5)无法求得有意义的解。以上问题可以通过将核函数中心化的方法得到解决[21],即定义中心化后的核函数为:

kc=k-1nk-k1n+1nk1n

(6)

其中1n为n×n的矩阵,矩阵元素均为1/n。此时式(5)可转换为:

(7)

对于新到的样本节点x,其在高维特征空间中与原点的距离无法通过简单公式得到,因此QSSVM目前仅能作为离线式的异常检测技术。在2.2小节本文将通过滑动窗口模型实现QSSVM的在线检测。

图3 RBM模型

1.3 深度信念网络(DBN)模型

1.3.1 受限玻尔兹曼机(RBM)

受限玻尔兹曼机[22]RBM(Restricted Boltzmann Machine)是一种概率神经网络,主要由两层神经元构成,分别称为隐藏层和可见层。如图3所示,h为隐藏层神经元状态向量,v为可见层神经元状态向量,向量b是隐藏层的偏执系数,向量a为可见层的偏执系数,每一层之间的神经元相互独立,隐藏层与可见层之间是全连接关系。

1.3.2 深度信念网络(DBN)

深度信念网络[23]是由多个RBM叠加合成的深度学习网络。如图4所示,该网络通过对RBM一层一层的训练,下层RBM的输出作为上层RBM的输入,在 DBN 的最后一层设置 BP神经网络,用来接收RBM训练后的特征数据。由于每一层RBM的训练都只能保证自身的最优,因此一层一层训练也无法保证全局最优,BP神经网络能够将得到的数据与期望数据比对,并进行自顶层向下的调整从而优化训练结果。

图4 DBN模型

此外,DBN还可作为数据的降维工具,将高维的输入向量X∈Rn×d通过DBN进行压缩提取后,输出低维的特征向量Y∈Rn×s,其中s

1.4 降维后传感器数据特征

通过DBN对高维数据降维后,正常数据与异常数据的分布呈现较明显差异,并且异常数据不对称地分布在正常数据一边。本文从UCI机器学习库网站下载了四组真实传感器数据,分别为Forest(森林环境监测数据,54维),GAS(基于传感器检测的气体种类集,128维),DSA(日常活动集,315维)和HAR(基于智能设备穿戴的人类活动集,561维),并在这些数据中随机地加入了少量异常(具体实现方法见3.1节),降维后的数据分布如图5所示(为了易于呈现,统一把数据降到3维)。从图中可以看出,在四张图中异常数据(圆点)分布在正常数据(方点)的一侧,而非对称地分布在其周围。而传统的单分类支持向量机所得到的球面以输入数据在高维空间的中点为圆心,能够较好地分割相对圆心对称分布的异常数据。在数据呈单侧分布时,圆心的定位会存在少量偏差,因此无法保证异常数据的检测准确度。QSSVM将输入数据在高维空间中平移,并以原点为圆心确定1/4球面,更适用于异常数据分布于单侧的异常检测问题,相比传统的OCSVM具有更高的检测准确度。

图5 DBN降维后的数据分布特征

2 基于深度信念网络的传感器数据异常检测算法

本节首先建立DBN与QSSVM混合模型(包括训练模型和测试模型),再利用滑动窗口模型实现在线式地异常检测。

图6 训练模型

2.1 DBN与QSSVM混合模型

DBN与QSSVM混合模型分为训练模型和测试模型,如图6和图7所示。训练模型用于DBN降维模型的训练及训练数据中异常数据的剔除,测试模型用于实时检测新到数据是否为异常。

图7 测试模型

在训练模型中,将训练数据输入给DBN底层节点,训练DBN中各层之间权值W,显层节点偏执和隐层节点偏执(a,b,c),并将降维后的训练数据输入给QSSVM并输出训练数据中的异常数据,在训练数据集中将异常数据剔除,如图6所示。

在测试模型中,将新采集到的待检测数据输入给训练好的DBN模型,输出降维后的测试数据,并加入到滑动窗口中,最后将窗口数据输入到QSSVM,检测新到数据是否为异常,如图7所示。

2.2 滑动窗口模型实现在线检测

由于传感器所采集的数据具备一定的时间相关性,所采集数据的分布会根据时间的推移而发生变化,因此采用滑动窗口模型将新采集的数据与最近时间数据放在同一窗口中,输入给QSSVM进行异常检测。一方面,通过窗口的滑动能够实现实时地在线数据检测,另一方面,利用数据的时间相关性,能够提高异常检测的准确度。

滑动窗口模型如图8所示,m为滑动窗口大小,窗口1和窗口2分别t-1时刻和t时刻的窗口,白色点表示已检测样本,黑色点为待检测样本。在下一个时刻采集到新数据时,窗口向右滑动,将待检测样本滑入窗口中,并将部分已检测样本滑出窗口。最后将新窗口中的样本数据输入到QSSVM模型中检测样本是否为异常。

图8 滑动窗口模型

2.3 基于深度信念网络异常检测算法

表1 算法伪代码

3 实验

本节将本文提出的新算法QSSVM与文献[17]提出的基于DBN降维的OCSVM方法、文献[11]提出的K-Means算法以及文献[4]提出的DBSCAN算法作了对比,其中本文针对K-Means算法和DBCSAN算法,结合本文中提及的滑动窗口加以改进。实验结果从不同性能角度证明了QSSVM算法的优越性。

3.1 数据集与实验设置

实验数据是从UCI机器学习库网站下载的四组真实传感器数据集,分别为:54维的Forest(森林环境监测数据)、128维的GAS(基于传感器检测的气体种类集)、315维的DSA(日常活动集)和561维的HAR(基于智能设备穿戴的人类活动集)。从每个数据集中挑选连续时间的1000个样本数据,并将前80%数据(即800个样本)作为训练数据,随机加入5%的异常数据,将后20%的数据作为测试数据(即200个样本),随机加入10%的异常数据,并假设每个时间间隔有10个测试样本被采集。所有样本数据归一化到[0,1]区间上,所有加入的异常数据从[0,1]区间的均匀分布随机产生。

为达到最佳算法性能,通过多次实验对比,本文选取了两层的DBN结构,将输入数据降到6维,QSSVM与OCSVM均选用RBF核函数。所有算法用MATLAB R2017a实现,并在1.9 GHz双核CPU,32GB内存的专用服务器上运行,每个实验结果均为10次独立实验的平均值。

3.2 算法性能指标

表2 算法性能指标

实验测量的算法运行时间是从输入训练数据和测试数据开始,到算法输出所有异常数据为止。

3.3 实验结果与评价

本小节以图表的形式比较了QSSVM与OCSVM、K-Means及DBSCAN的检测准确度(检测率,误判率和召回率)及计算时间,同时评价了滑动窗口大小对QSSVM性能的影响。

3.3.1 算法效率及窗口大小影响

表3比较了两个算法训练模型及检测异常的运行时间总和,及不同大小窗口下QSSVM的准确度变化。由于不同数据集合,不同异常维度比率对算法时间几乎没有影响,本小节所记录的时间为所有异常维度比率情况下,在四个数据集合中算法运行时间的平均值。从表3中可看出,随着窗口的增大,QSSVM的准确度是逐渐增加的(即检测率与召回率逐渐增加,误判率逐渐下降),这是因为窗口越大,窗口内包含样本数据越多,每次在计算球面半径时能参照的正常样本数也会越多,得到的半径也更加精确。

记样本数为n,QSSVM算法使用RBF核,其最内层运算次数为n2次,时间复杂度为,核函数中心化方法解决对角线问题,其运算次数为n次,时间复杂度为,滑动窗口循环m次,时间复杂度为,即,则时间复杂度为。另外K-Means算法的时间复杂度为,DBNCAN算法的时间复杂度为,OCSVM算法的时间复杂度为。表3比较了四个算法的计算效率,K-Means、DBSCAN和QSSVM算法的运行时间都随窗口的增大而增加,当窗口大小为100时,QSSVM的计算时间比OCSVM低50%左右,当窗口增大到包含200个样本数据时,QSSVM算法与OCSVM算法的计算时间相近,K-Means和DBSCAN由于其时间复杂度较低,故低于QSSVM。

表3 不同窗口值下算法性能的比较

考虑到当窗口增加到一定程度时,能获得的准确度越来越少,因此为保证算法的计算效率,在以下的准确度实验中,将QSSVM算法的滑动窗口大小固定在100。

3.3.2 检测率(DR)

图9比较了四个算法在不同比率维度出现异常时的检测准确度。从四组数据对应的四张图中可以看出,随着样本维度异常比例的增加,四个算法的检测率均呈上升趋势,这是因为经过DBN的降维,异常数据与正常数据样本偏差会随着异常维度的增加而增大。QSSVM在Forest数据(54维)和GAS数据(128维)时略低于K-Means和DBSCAN,但随着样本维度的增加,QSSVM依旧可以表现出良好的检测性能,K-Means检测结果却越来越差,在HAR数据(561维)时,检测率最高仅有45.68%,而此时QSSVM最高可以达到93.07%,DBSCAN一直保持较高的检测率,在随着样本维度增加时,较低的维度异常比例的异常数据无法被检出,此时,DBSCAN表现出的召回率却很低,表示只检测出了部分的异常数据。QSSVM一直处于OCSVM的上方,大多数情况下,相比OCSVM,QSSVM检测准确率高约20%。

图9 不同异常维度比率下的异常数据检测率

图10 不同异常维度比率下的异常数据误检率

3.3.3 误检率(FPR)

图10呈现了四个算法在不同比率维度出现异常时的误检率。从图中可以看出,随着样本维度异常比例的增加,四个算法的误检率均呈下降趋势。实验结果表明,QSSVM在Forest数据(54维)和GAS数据(128维)时略高于K-Means和DBSCAN,但在随着样本维度增加时,K-Means在HAR数据(561维)时表现出较高的误检率,DBSCAN在低纬度异常时,也表现出高的误检率,此时,DBSCAN表现出的召回率却很低,表示只检测出了部分的异常数据。在所有情况中QSSVM的误检率均远低于OCSVM,一般情况下,相比OCSVM,QSSVM误检率低20%～50%。

3.3.4 召回率(Recall)

图11呈现了四个算法在不同比率维度出现异常时的召回率。随着样本维度异常比例的增加,四个算法的召回率均呈上升趋势。一般情况下,QSSVM的召回率相比其他算法具有明显优势,仅在HAR数据时QSSVM的召回率低于K-Means,此时K-Means表现出较低的检测率和较高的误检率,而此时QSSVM依旧表现现高的检测率和低的误检率。

图11 不同异常维度比率下的异常数据召回率

综上,在QSSVM窗口值为100时,舍弃算法本身的时间复杂度的同时,获得了更好的检测结果,尤其在处理高维数据时,检测结果明显优于其他算法。特别地,当异常数据样本仅有部分维度出现异常时(异常维度比率60%以下),QSSVM仍能表现出较高的检测准确度。

4 总结

本文提出了一种基于深度信念网络的传感器数据异常检测算法。该算法首先使用DBN对高维数据进行降维处理,再利用QSSVM结合滑动窗口模型实现了对降维后数据的在线实时检测,实验结果表明,相比先前异常检测算法,新算法在对高维数据进行异常检测时,舍弃算法自身的时间复杂度的同时,获得了更好的检测结果,尤其在处理高维数据时,检测结果明显优于其他算法。相比ocsvm可将检测准确度提高约20%,误判率降低20%～50%,同时计算时间仅为原有算法的一半。因此,本文提出的新方法为传感器数据的处理与应用提供了重要的参考。

本文利用DBN实现了数据特征的提取从而达到对高维数据降维的目的,但针对不同数据集合特征,所提取特征个数应有不同,而本文实验中对四组数据集合未做区分处理。在未来研究工作中,将继续研究DBN所提取的特征对于异常检测的影响,针对不同数据集合从理论上给出最适合的降维模型,从而使降维后的异常数据与正常数据存在更大的区分度。