一种基于随机空间树的数据流异常检测算法
2017-10-12覃伟荣王宁
覃伟荣+王宁
摘 要： 针对现有的数据流异常检测算法的不足，提出一种基于随机空间树的数据流异常检测算法。首先，采取统计策略对数据流特征范围进行估计，分割得到多棵随机空间树（RS?Tree），形成RS森林（RS?Forest）。然后，RS?Forest采用单窗口策略对数据流进行处理，通过打分和模型更新来实现异常检测。针对实例落入的树节点，定义分段恒定密度，求取密度估计值相对于森林中所有树的平均值，并将其作为数据流中每个新来实例的得分。利用相对于森林中所有树的平均得分对每个新来实例进行排序。窗口满后则采用对偶式节点剖度技术进行模型更新，并利用采集的节点尺寸信息对下一轮到达窗口的数据进行打分。利用多种基准数据集进行仿真实验，结果表明RS?Forest算法在大部分数据集下的AUC得分和运行时间性能均优于当前其他基准算法。
关键词： 数据流； 异常检测； 随机空间树； 单窗口策略； AUC得分； 运行时间
中图分类号： TN915.08?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）19?0056?06
A data stream anomaly detection algorithm based on randomized space tree
QIN Weirong1， WANG Ning2
（1. School of Electronics and Information Engineering， Qinzhou University， Qinzhou 535000， China；
2. School of Information Engineering， Zhengzhou University， Zhengzhou 450001， China）
Abstract： Aiming at the shortcomings of the available data stream anomaly detection algorithms， a data stream anomaly detection algorithm based on randomized space tree （RS?Tree） is proposed. The statistical strategy is adopted to estimate the characteristic range of data stream， by which several randomized space trees are obtained by means of segmentation to form RS?Forest. The single window policy is used by RS?Forest to process the data stream， and realize anomaly detection by means of scoring and model updating. According to the tree node that an instance falls in， the piecewise constant density is defined to get the average value of the density estimation values relative to all the trees in forest， which is taken as the score of each new instance in data stream. The average score of all the trees relative to forest is employed to sort each new instance. When the windows are occupied， the antithetic node dissection technology is used to update the model， and the acquired node size information is used to mark the data arriving at the window in the next round. The simulation experiments were carried out with variety of benchmark datasets. Its results show that the AUC scoring and run time performance of RS?Forest algorithm for most datasets are superior to those of other benchmark algorithms.
Keywords： data stream； anomaly detection； randomized space tree； single window policy； AUC scoring； run time
0 引 言
异常或离群点是指与正常点或预期点不吻合或偏离正常点的罕见事件或罕见点。对于军事侦查、网络安全管理、工业系统监控等众多领域，如果不能立即检测出这些异常事件，便有可能造成严重后果。随着近些年硬件技术的迅速发展，上述领域的持续性数据采集能力获得显著提升，采集到的大部分数据不再是有限的或静态数据，而是无限制的大容量高速实时数据，称其为数据流。
异常检测一直是数据挖掘领域的研究热点[1?3]。然而，数据流的内在特点对当前大部分异常检测技术（如HSTa[4]，LOADED[5]，Hoeffding Trees（HT）[6]以及BoostHT[7]等）构成严重挑战。首先，数据流的生成速度前所未有，因此需要迅速处理。这便要求检测模型的更新速度快于数据率，而且检测器必须能够适应数据流信息生成速度较快这一特点。其次，传统的异常检测算法[8?9]在构建模型时需要将数据保存于内存中。由于数据流的数据量极大，容易将内存耗尽，所以传统方法将会失效。再次，对数据流来说，无论是正常事件还是异常事件均处于不断变化之中，容易使利用老旧数据学习而得到的检测模型过时。因此，检测算法应该能够适应于正常行为随时间不断变化这一特点。最后，实践中数据流的异常实例非常罕见，甚至无法获得。这就要求异常检测技术即使只利用正常事件进行训练，也应该能够准确地检测出可疑行为。针对以上方法的不足，本文提出一种基于随机空间树（Randomized Space Tree，RS?Tree）的数据流异常检测算法，并通过理论分析和仿真实验验证了该算法的有效性。
1 本文算法
1.1 基本定义
定义1：随机空间树，它是一种完全二叉树，可通过随机选择一种属性及被选属性的割点来构建。
深度为[HH≥0]的RS?Tree共有[2H+1-1]个节点，其中叶节点的深度均为[H]。RS?Tree起源于随机决策树[10]，不用数据便可构建出树结构。在构建RS?Tree时，算法不断从特征集中选择一种属性，然后随机确定这种属性的分割点来实现树的分割，直至到达树深[H]。
定义2：RS?Tree中的节点剖度，已知数据样本后，该节点表示相应区域中落入的实例数量。
定义3：基于随机空间树[T]的分段恒定密度估计，其表达式为：
[fx；T=?x，TNV?x，T] （1）
式中：[?x，T]表示终止节点；[?]表示节点尺寸或节点剖度；[V?]为节点所表示的超矩形的容积。在RS?Tree中，终止节点是指用于密度估计的节点，它可为叶节点，或者是首个满足节点尺寸约束（即小于等于）的节点。
定义4：基于RS森林[F]的密度估计，其表达式为：
[fx；F=1Mt=1Mfx；Tt] （2）
式中：[fx；Tt]表示第[t]棵树的密度估计；[M]表示RS树的数量。
1.2 RS树的构建
（1） 树节点的初始化。深度为[H]的RS树包含[2H+1-1]个节点。在部署时，每个节点包含如下元素：
① 变量[ml]和[mr]，用于交替记录预测模型或窗口内数据流的节点剖度；
② 3个节点指针，分别指向当前节点的左子节点，右子节点及母节点；
③ 变量[v，]用于存储当前节点容积与整个特征空间容积之比的对数。
（2） 属性范围估计。确定每个属性的正确范围是构建RS树结构的重要步骤。如果范围过紧（比如从数据样本中直接确定的范围），则无法适应整个数据流的潜在变化。另一方面，如果范围过宽，则会引入不必要的噪声及没有意义的空间分割。因此，本文采用如下的统计策略来估计每个属性的合理范围：首先，针对属性[i]的均值，计算90%的最高后验密度（Highest Posterior Density，HPD）置信区间[LMi，UMi]。然后，根据[3σ]准则扩大上述置信区间。即将下界设置为[LBi=LMi-3σ，]将上界设置为[UBi=UMi+3σ，]其中[σ]表示属性[i]的标准差。这种方式生成的下界和上界值（即LB和UB）作为算法1的输入，进而生成单个RS树的结构。
算法1 BuildRS?TreeStructure[LBs，UBs，e，H]
输入：[LBsUBs]：属性的下（上）界列表，
[e：]当前树的深度，[H：]树深界限；
输出：一棵RS樹
1：if [e≥H] then
2： Return [leaf（ml←0，mr←0）]；
3：else
4： 对非叶节点[root]初始化；
5： 随机选择一个属性[q∈Q]；
6： 在0～1之间随机选择一个数[r]；
7： 割点[p=LBsq+r?UBsq-LBsq]；
8： [t←UBsq]；[UBsq←p]；
9： left[←]BuildTreeStructure[LBs，UBs，e+1，H]；
10： [left.v←r]；[left.parent←root]；
11： [UBsq←t]；[LBsq←p]；
12： [right←]BuildTreeStructure[LBs，UBs，e+1，H]；
13： [right.v←1-r]；[right.parent←root]；
14： return
[root（leftChild←left，rightChild←right，splitAtt←q，cutPoint←p，][ml←0，mr←0）]
15：end if
（3）节点容积的计算。节点容积的计算对RS树的密度估计具有重要作用。只要RS树构建完毕，每个节点的容积便已固定。RS树可对空间[Ω]进行分割。每个节点表示有[2d]个不等式（[eTx 引理1 设[δij]表示形成由节点[i]表示的超矩形时属性[j]的长度，有[δij=ljk=1hijrijk，]其中[lj]表示属性[j]的长度，[rijk∈0，1]表示属性[j]第[k]个分支在从根节点到节点[i]路径上随机选择的数值，[hij]表示属性[j]在从根节点到节点[i]路径上进行分割的分支总量，且[k=10rijk=1]。 引理2 [Vi]表示由节点[i]表示的超矩形区域的容积，于是有[Vi=V?k=1hirik，]其中[rik∈0，1，]表示内部节点在从根节点到节点[i]的路径上随机选择的数值，[V=j=1dlj，][hi=j=1dhij]且[k=10rik=1]。 限于篇幅，证明过程略。上述引理表明，利用内部节点在从根节点到节点[i]的路径上随机选择的数值，可计算出节点[i]的容积。为了计算出节点容积，只需记录构建RS树时随机选择的这些数值即可。算法2给出了部署详情。 算法2 ComputeNodeVolRatio （T） 1：对队列node_queue初始化； 2：nodeQueue.Enqueue（T）；
3：while ！ nodeQueue.empty（） do
4： curNode ← nodeQueue.Dequeue（）；
5： parentNode ← curNode.parent；
6： if parentNode is NULL then
7： curNode.v ← 0；
8： else
9： curNode.v ← parentNode.v+ log（curNode.v）；
10： end if
11： if curNode为内部节点 then
12： nodeQueue.Enqueue（curNode.leftChild）；
13： nodeQueue.Enqueue（curNode.rightChild）；
14： end if
15：end while
1.3 数据流异常检测算法（RS?Forest）
本文提出的数据流异常检测算法是利用多棵RS树形成RS?Forest，然后RS?Forest对数据流采用单窗口策略对新到达实例进行打分，并与一种周期性快速更新模型方法相结合。算法在具体部署时，需要将数据流分割为多个窗口。每个窗口的尺寸可以相同，也可以不同，具体视应用要求而定。算法在运行时只针对一个窗口，该窗口称为最新窗口。在异常检测方法的初始阶段，系统在构建树（模型）结构的同时，利用正常数据样本记录节点剖度。然后，系统对最新窗口内的新来实例进行打分，同时记录从这些实例中获得的节点剖度。窗口满后，触发模型更新过程，利用对偶节点剖度實现快速模型更新。模型更新完毕后，删除原来的节点剖度，将最新窗口清空，为新来数据做好准备。上述过程一直持续至数据流结束为止。
根据RS森林的密度估计对新来实例[x]进行打分。一个实例的密度越低，该实例异常的程度越高。结合定义3和定义4，可将[x]的异常得分定义如下：
[1Mt=1M?x，TtNV?x，Tt] （3）
利用引理2，可将式（3）重写为：
[1MVt=1MScorex，Tt] （4）
式中：[Scorex，Tt=explog?x，Tt-?x，Tt?v-logN；][V=j=1dlj]。在实践中，由于[M]和[V]为常数，所以在对异常排序时只需利用[t=1MScorex，Tt]即可。为了避免计算时出现下溢现象，对数值采用对数标度。
算法3 StreamingRS?Forest[X，M，H，ψ，ζ]
输入：[M]：RS树的数量；[H]：树深界限；[ψ]：窗口大小；[ζ]：节点尺寸界限
输出：[s]：每个新来实例[x]的异常得分；
1：[F=BuildForestX，M，H]；
2：利用[X]对[F]中每个RS树的节点剖度[ml]进行更新；
3：[B←]；
4：[LR←False]；
5： while 数据流持续 do
6： 接收到新的数据点[x：b.X=x]，[b.nodeList=]；
7： [s←0]
8： for [F]中的每个树[T] do //预测阶段
9： [s←s+Scorex，T]；
10： [b.nodeList.Enqueue][?x，T]；
11： end for
12： [B.Enqueue（b）]；
13： 给出数据点[x]的异常得分[s]；
14： if [B==ψ] then //模型更新阶段
15： UpdateModel[F，B，LR，ζ]；
16： [LR←！LR]；
17： [B.clear]；
18： 对[F]中每个树[T]的非零节点，[LR？node.ml←0：]
[node.mr←0]；
19： end if
20： end while
算法3给出了数据流RS?Forest方法的详情。第1行负责对RS?Forest初始化。在初始化时（算法4），obtainRange（[X]）的作用是利用样本[X]获得每个属性[qi]的范围估计值。[X]既可以是正常实例样本，也可以是数据流的前[ψ]个正常实例。算法在对节点剖度初始化的同时，构建每个RS树的结构。算法3的第2行利用[X]更新森林中每个树的节点剖度[ml]。在本文模型中，估计（或打分）步骤与模型更新步骤交替进行。在整个运行期间，每个树的结构保持不变，数据打分后获得的节点剖度可用于下一轮的模型更新。因此，这两个步骤有部分操作重合。于是，采用一种对偶式节点剖度技术来保存预测阶段已经执行过、模型更新阶段同样需要执行的相同操作。具体来说，交替使用节点剖度[ml]和[mr]来存储当前模型（用于存储新来数据）的节点剖度，以及从最新窗口内新来数据获得的节点剖度（用于下一轮更新模型）。[ψ]个数据点处理过后，[ml]和[mr]的角色变化，并利用变量LR作为这一变化的标志。
算法4 BuildForest[X，M，H]
1：[LBs，UBs=obtainRange（X）]；
2：初始化：[F=]
3：for [t=1]to[M] do
4： [T=BuildTreeStructureLBs，UBs，0，H]；
5： ComputeNodeVol[T]；
6： [F=F?T]；
7： end for
8：return [F]
如上文所示，模型更新是RS?Forest方法的关键步骤之一，模型更新的内容见算法5。总体来说，模型更新算法分为两部分：第一部分针对异常实例（第3～9行），另一部分针对正常实例（第10～19行）。在异常实例部分，通过沿着从终止节点到根节点的路径使所有节点的剖度下降1来更新各个RS树。在正常实例部分，如果终止节点不是叶节点且节点尺寸约束未被满足，则通过沿着从终止节点到叶节点（或满足节点尺寸约束的首个节点）的路径使所有节点的剖度上升1来更新各个RS树。此时，[NextChildchild，x]表示[x]落入的下个子节点。
算法5 UpdateModel[F，B，LR，ζ]
输入：[F]：RS森林；[B]：每个实例的缓冲；LR：关于哪个剖度将被更新的指示器；[ζ]：节点尺寸界限
输出：无
1： 根据标签信息将[B]分割为[N]和[A]；//[NA]包含最新窗口内正常（异常）实例的相关信息；
2： for [i=1]to[M]do
3： for [A]中[nodeList]列表的每个[x] do
4： [ancestor=nodeList[i]]；
5： while （不存在ancestor） do
6： [LR？ancestor.ml--：ancestor.mr--]；
7： [ancestor←ancestor.parent]；
8： end while
9： end for
10： for [N]中[nodeList]列表的每个[x] do
11： [LR？n=nodeList[i].ml：n=nodeList[i].mr]；
12： if [n>ζ]&&[nodeList[i]]不是叶节点 then
13： [Child=NextChild（child，x）]；
14： while [child]不为空 do
15： [LR？child.ml++：child.mr++]；
16： [child=NextChild（child，x）]；
17： end while
18： end if
19： end for
20： end for
2 理论分析
2.1 范围估计的可靠性
数据流的各个属性的范围是构建RS树结构的重要输入之一。如果RS树构建于[d]维空间且该[d]维空间的边界即为属性范围，则RS树需要适应整个待学习数据流的潜在特征变化。因此，引入如下定理来分析本文采用的范围估计策略的可靠性。
定理1 当分布未知时，有：
[pL 式中：[Z]表示随机变量；[L]和[U]为常量，[L<μ 上述定理为变量均值满足[μ-LU-μ>σ2]条件的范围提供了概率保证。此时，变量可服从任何分布。在本文算法中定义属性的范围为[LMi-3σ，UMi+3σ]。对于正态分布，均值的90% HPD置信区间大约为[μ-1.645σ，μ+1.645σ。]在本文中，[L=μ-4.645σ， U=μ+][4.645σ。]根据[3σ]准则，[pμ-4.645σ 2.2 复杂度分析 本文提出的数据流异常检测算法的主循环涉及三大操作（如算法3所示），分别是第9行的预测或打分，第15行的模型更新，以及第18行的节点剖度重置。在基于当前模型的预测步骤中，每个实例均需对各个树中从根节点到终止节点的所有节点进行遍历。在模型更新时，针对各个异常实例或正常实例采取两种不同步骤。因为异常实例比较罕见，所以对于每个实例而言，用于打分和模型更新的时间应该相等，或低于[MH。]于是，最坏情况下的运行时间为[OnMH]，其中[n]表示数据流中数据点的数量。每次触发模型更新步骤时，节点剖度重置最多在[M?2H+1]时间内完成，所以其最差运行时间为[OnψM?2H+1]。考虑到运行期间[M，][H]和[ψ]固定，所以可以将数据流RS森林方法的最差复杂度看成[On]。 对于空间复杂度，RS?Forest本身占据空间[OM2H]。最新窗口内的数据缓存[B]最多占用[OψM]。因为[ψ]和[M]均是常数且数值较小，所以占用的空间可以忽略。因此，空间复杂度为[O2H]。在运行期间，[H]固定，于是数据流RS森林方法的内存消耗量恒定。 3 仿真实验 3.1 实验设置 利用如表1所示的6种合成基准数据集 [11?12]和7种真实基准数据集[4，13]作为测试对象，将本文提出的RS?Forest方法与如下基准方法：HSTa[4]，LOADED[5]，Hoeffding Trees（HT）[6]及基于HT的在线协作加速算法（BoostHT）进行性能比较。利用机器学习和数据挖掘中最为常见的AUC（ROC曲線下的面积） [14]作为各种算法的评估指标。每个算法对各个数据集单独运行30次，然后取平均值作为最终结果。所有实验的实验平台均为2.6 GHz Intel Core i7 MacBook Pro，8 GB内存。 表1 基准数据集 3.2 实验结果
表2给出了各种算法对各个基准数据集的平均AUC面积。很显然，从统计学角度讲，RS?Forest方法对大部分数据集表现出来的性能均优于其他算法。根据置信度为95%的成对[t]检验，RS?Forest与HSTa，LOADED，HT和BoostHT的成对win?loss?tie统计数据分别为10?0?3，10?3?0，13?0?0，11?1?1。这是因为本文方法对数据流的异常检测效果更优。HSTa无疑也是一种高性能检测算法，对所有数据的AUC平均值在各种算法中排名第二。BoostHT对大部分真实数据集也展现出优异性能，但它对Syn_cond和Syn_dual等合成數据集的AUC得分要低于HT算法。BoostHT算法的性能出现下降，表明有条件类别分布发生变化时BoostHT很容易发生过拟合。LOADED和HT是两种单模型算法，在AUC面积方面的排名垫底。与BoostHT不同，LOADED对服从高斯分布的多个合成数据集展现出优异性能。这是因为LOADED的模型假设非常严格。
图1给出了不同算法在3种数据集的数据流发生变化时的AUC性能比较。总体来说，随着时间的推进以及各个数据流的演变，RS?Forest方法对Mulcross和HyperP1数据集的AUC面积总是优于HSTa和BoostHT。不同算法在Covertype数据集上的性能波动较大。具体来说，当异常实例发生于Covertype演变过程的中间阶段时（用虚线表示），RS?Forest和HSTa的性能趋于下降，而BoostHT的性能迅速上升。HSTa的下降趋势大于RS?Forest方法。
（HT）必须计算Hoeffding才能确定分割树的最佳属性，因此消耗的时间最多。HSTa的运行速度快于BoostHT，但其平均运行时间仍然是RS?Forest方法的5倍左右。RS?Forest方法中的数据结构与HSTa类似。然而，与HSTa不同的是，RS?Forest方法从预测过程和模型更新过程的共同操作入手，进一步降低了模型更新时间。因此，RS?Forest方法的运行时间在各种算法中是最低的，甚至还要低于单模型方法。
4 结 语
本文提出一种新的数据流异常检测算法RS?Forest。该算法满足了持续演变数据流对异常检测算法的关键要求：
（1） 该算法为一次通过型检测算法，具有恒定的空间复杂度和线性时间复杂度；
（2） 该算法作为一种极具多样性的系统算法，作用于统计估计特征空间，可提供较高的概率保证，对漂移概念具有显著效果；
（3） 采用一种对偶节点剖度技术，响应时间极快；
（4） 训练时只需要正常实例即可，可实现高效有序的异常检测和模型更新。
另外，还进行了严格的理论分析，为本文算法提供了坚实的理论基础。基于多个基准数据集的实验仿真评估结果表明，与当前其他最新算法相比，RS?Forest方法的AUC得分较高，运行时间较短。下一步的主要工作包括：对RS?Forest方法适当改进后，适用于部分数据丢失的混合特征空间；在保持检测率的同时降低算法的空间消耗。
参考文献
[1] 彭勇，向憧，张淼，等.工业控制系统场景指纹及异常检测[J].清华大学学报（自然科学版），2016，56（1）：14?21.
[2] 严英杰，盛戈皞，陈玉峰，等.基于大数据分析的输变电设备状态数据异常检测方法[J].中国电机工程学报，2015，35（1）：52?59.
[3] 蔡瑞初，谢伟浩，郝志峰，等.基于多尺度时间递归神经网络的人群异常检测[J].软件学报，2015，26（11）：2884?2896.
[4] TAN S C， TING K M， LIU T F. Fast anomaly detection for streaming data [C]// Proceedings of 2011 International Joint Conference on Artificial Intelligence. Barcelona， Spain： IEEE， 2011： 1511?1516.
[5] GHOTING A， OTEY M E， PARTHASARATHY S. LOADED： link?basedoutlier and anomaly detection in evolving data sets [C]// Proceedings of the 4th IEEE International Conference on Data Mining. Orlando， USA： IEEE， 2014： 387?390.
[6] DOMINGOS P， HULTEN G. Mining high?speed data streams [C]// Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington， DC， USA： ACM， 2010： 71?80.
[7] BIFET A， HOLMES G， PFAHRINGER B， et al. New ensemble methods for evolving data streams [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris， France： ACM， 2009： 139?148.
[8] NIKOLOVA E， JECHEVA V. Some similarity coefficients and application of data mining techniques to the anomaly?based IDS [J]. Telecommunication systems， 2012， 50（2）： 127?135.
[9] DHAKAR M， TIWARI A. A novel data mining based hybrid intrusion detection framework [J]. Journal of information and computing science， 2014， 9（1）： 37?48.
[10] ZHANG K， FAN W. Forecasting skewed biased stochastic ozone days： analyses， solutions and beyond [J]. Knowledge and information systems， 2008， 14（3）： 299?326.
[11] FILZMOSER P. Identification of multivariate outliers： a performance study [J]. Austrian journal of statistics， 2016， 34（2）： 127?138.
[12] WU K， EDWARDS A， FAN W， et al. Classifying imba?lanced data streams via dynamic feature group weighting with importance sampling [C]// Proceedings of 2014 SIAM International Conference on Data Mining （SDM）. Philadelphia， USA： SIAM， 2014： 722?730.
[13] DITZLER G， POLIKAR R. Incremental learning of concept drift from streaming imbalanced data [J]. IEEE transactions on knowledge and data engineering， 2013， 25（10）： 2283?2301.
[14] HUANG J， LING C X. Using AUC and accuracy in evalua?ting learning algorithms [J]. IEEE transactions on knowledge and data engineering， 2005， 17（3）： 299?310.
