英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
王斌，杨晓春，王国仁等。在滑动窗口中发现概率数据流。计算机科学与技术杂志25（3）：2010年5月389-400
滑动窗口下概率数据流的异常值检测
王斌，CCF成员，杨晓春，CCF高级成员，ACM成员，IEEE成员
王国仁，CCF高级成员,ACM成员，IEEE成员
于戈，CCF高级成员，ACM成员，IEEE成员
中国东北大学信息科学与工程学院，沈阳110004
医学影像计算重点实验室（东北大学），教育部，沈阳110004
电子邮件：{binwang, yangxc, wanggr, yuge}@mail.neu.edu.cn
于2009年6月30日收到，2009年11月16日修订。
摘要
异常值检测在很多应用中是一种非常有用的技术手段，在异常值检测中，数据通常是不确定的，它们因此可以用概率来描述。尽管在确定数据的领域中，异常检测已经被深入地研究过了，但在不确定的数据领域中，异常检测仍是一个新起的检测手段。在这篇文章中，我们基于概率数据流来进行了语意的异常检测的研究，并提出了一种新的滑动窗口下基于距离的异常值的定义。然后我们发现检测存在于一组可能值中的一个异常值的问题，实质上是等同于寻找在它的邻域中找k个元素的问题。基于这个发现，提出了一个动态编程算法（DPA）来减少检测成本从O()到O(|k*R(e,d)|)，这里R(e,d)是e的d邻域。此外，我们提出了一个修减算法（PBA）来在单一窗口中有效地过滤非异常值，并且动态地检测近m个数据增量。最后，详细的分析和整体实验结果证明了我们的方法的有效性和可伸缩性。
关键词：异常检测、不确定数据、概率数据流、滑动窗口
1.介绍
在网络入侵检测、事件检测和领域，确定数据基于距离的异常检测技术已经被深入地研究过了。作为一种新兴的技术，不确定数据可以更好的反应真实世界，也因此越来越在当今社会受到人们的关注。由于不确定和确定性数据之间的内在差异，例如新的引入的概率维度称为置信度，现有的确定性数据技术不能直接应用于不确定数据的异常检测。而且，在滑动窗口计算模型中，当一个新元素到达时，它应该被插入到窗口中，而过期的元素应该从窗口中被删除。
据我们所知，目前还没有一种算法在不确定的数据流中考虑基于距离的异常检测。在这篇文章那种，我们利用滑动窗口计算模型，研究了不确定数据流的基于距离的检测方法，在每一个滑动操作进行后，需要对异常值进行检测。
作为一个例子，图1（a）显示了一个在概率数据流上长度为5的滑动窗口。图1（b）显示了从e1到e6的六个元素的值。对于每一个元素ei来说，我们使用V1和V2来表示它的两个属性和p来表示它的概率，这就反应了它存在的不确定性。图1（c）将这些元素映射到二维坐标中。为简单起见，我们在这里只考虑了两个属性。
我们研究了在概率数据流中检测异常值时自然产生的几个问题。
问题1：基于距离的异常值在不确定的数据流中意味着什么？在考虑确定性数据时，如果在距离d内的相邻元素（包括自身）的数量低于阈值k，那么元素就是一个基于距离的异常值。例如，在图1（c）中，如果所有元素的概率都是1，那么所有元素都可以被视为确定性数据。然后e5有四个相邻的元素，包括e1、e2、e4和e5，在d=50中。因此，当k=5时，e5是一个异常值。然而，在不确定的数据流中，每个元素都有一个概率值，这会导致相邻元素的数量不确定。因此，在不确定的数据流中，基于距离的异常值不能仅根据相邻元素的数量来定义。
图1 在概率数据流上的一个滑动窗口的例子
- 数据流的1-滑动窗口
（b）具有概率的部分元素
（c）将滑动窗口中的元素映射到一个2d空间
我们的成果：在不确定的数据流中，我们提出了一种基于距离的异常值。保留了基于距离的异常值的传统定义的基本思想，我们在这个新定义中使用了概率。在每个滑动步骤之后，如果当前窗口中e的相邻元素的数量小于或等于阈值m，元素e被认为是一个基于距离的异常值。
问题2：如何有效地检测单个窗口中的异常值？我们仍然使用k来表示足够的相邻元素的最小数量。一种简单的方法是按顺序处理当前窗口中的所有元素。每一个都展现了其领域的所有可能的值，并累加了包含至少k个元素的可能世界的概率。如果这个总和不大于lambda;那么这个元素就是一个异常值。
表1显示了在图1（a）所示的窗口中e5（此处d=50）的所有可能的值（pw0-pw15），以及它们的存在概率。我们假设所有的元素都是相互独立的。pw0的概率等于（1-0.6）*(1-0.4）*（1-0.8）*（1-0.6）是0.0192，而pw10的概率是0.6*（1-0.4）*（1-0.8）*0.6是0.0432。让k等于2，概率阈值是lambda;是0.65。我们只能看到可能的值（pw5-pw15）包含足够大的元素个数（ge;k）。然后通过将可能的值从pw5到pw15的概率，我们计算出e5至少k个领域的概率是0.8336。因为它大于lambda;，所以我们说e5不是一个异常值。
表1 e5d邻域的可能值
这种简单的方法在现实中是不可行的，因为以下两个原因：（i）当滑动窗口的大小很大时，处理窗口中包含的所有元素的时间太长了;（ii）每个元素的可能值的数量随着其邻域的数量的增加而呈指数增长，而通过展开所有可能的值来处理元素的成本将会非常高。为了在不确定的数据中检测出这种基于距离的不确定数据流，需要提出一种更有效的方法。
我们的成果：我们提出了一种叫做PBA的基于修正的方法，有效地减少了滑动窗口中的处理元素，并节省了检测成本。此外，我们还提出了一种名为DPA的动态编程算法，它可以在线性时间内处理每一个元素，从而避免不必要地展开其邻域的可能值。
问题3：如何在快速更新数据元素的情况下设计算法来支持在线计算？在针对数据流的滑动窗口计算模型中，我们考虑了最多的m数据元素，也就是说，l滑动窗口中最原始的l元素应该被删除，并且应该插入到达的l元素。
我们的成果：我们利用检测到的元素在动态地滑动窗口时增量地检测异常值。当我们滑动窗口的l步时，前一个窗口中的非过期元素将共享新窗口，例如，e2、e3、e4和e5是图1（a）l滑动窗口中的非过期元素。我们称这些元素为联合元素。我们将证明，使用提出的修剪策略来处理所有的联合元素，我们可以加速检测性能。我们考虑了两个方面：i）数据结构需要良好的设计和维护，以及ii）删除过期元素和插入新到达元素的操作需要巧妙和准确地处理。
论文的其余部分按如下方式组织。在第1部分中，我们回顾了关于不确定数据、不确定的数据流和异常值检测的相关工作。在第2部分中，我们给出了基于距离的离群值在概率数据流上的新定义。在第3部分中，我们分析了具有概率的异常值，并提出了动态规划方法（DPA），准确地检测出单个元素。在第4部分中，我们提出了一个基于删除的方法（PBA），在滑动窗口时处理最近的m元素。在第5部分中，我们报告并分析我们的实验结果。在第6节中，我们将对未来的工作进行总结。
1.1相关工作
到目前为止，在确定性数据上有五种类型的异常检测技术，包括基于统计、密度、深度、距离和偏差的技术，其中基于统计的、基于密度的和基于距离[4-7]的技术被广泛使用。基于统计的技术是最原始的技术之一，用于根据小概率事件检测数据样本的异常情况。基于密度的异常值[4]定义了两个参数，包括不同记录之间的距离和在给定范围内的记录数之间的距离。它决定一个记录是否是一个异常值，或者根据记录的密度来决定。如果在一定距离内的点数量低于给定的阈值，基于距离的异常值检测将一个点视为数据集的一个异常值。由于算法的复杂，基于深度[5]和基于偏差[6-7]比其他三种方法都要少。
上面的技术都是基于确定性数据设计的。然而，在许多应用中，由于各种因素，如设备的限制、传输的延迟或丢失，数据是不确定的。为了处理数据的不确定性，不确定的数据越来越多地得到了越来越多的关注，涵盖了广泛的不同方面[8-12]。概率性的天线[8]的目标是在不确定的数据中找出天际线上的物体。由于在不确定的数据中引入了概率值，传统的顶部k查询被进一步细化为三种不同类型的查询，如U-Topk查询、u-k评级查询[9]和PT-k查询[10]。Aggarwal和Yu[11]提出了一种基于密度的技术，用于在不确定的数据上进行异常检测，在这个技术中，每个对象出现在一个不确定区域的任何地方，并带有一个概率分布函数（PDF）。Kriegel和Pfeifle[12]提出了一种基于密度的聚类算法，该算法适用于[11]的不确定的数据。
与不确定的数据相比，不确定数据流的技术[13-15]主要集中在如何处理不确定的数据，从而使在线查询在滑动窗口中进行调整。一种在不确定的数据流中找出Top-k查询的方法在[13]中被提出。[14]提出了一种实时监测不确定数据流的监控架构。一些工作都设计了聚类概率数据流，其中最具代表性的[15]是由阿加瓦尔和Yu提出的。
据我们所知，在不确定的数据流中，没有专注于于基于距离的异常值检测的工作，在这种情况下，每个元素都有一个概率，暗示着它存在的不确定性。因此，基于对[16]中滑动窗口流数据模型处理的主要思想，我们研究了基于距离的异常值检测方法，通过滑动窗口模型对不确定的数据流进行了研究。
2.概率数据流的异常语义
2.1概率数据的异常值
一个基于距离的异常值是在d-邻域[1]中没有足够元素的元素。对于不确定的数据库，我们需要考虑所有可能的实例来确定d社区是否包含足够的数据。
让D来表示一个可能性数据的数据集在这里每个元素是使用的形式的，其中是的可能性。在d邻域中，一个元素被标注为R(,d)，这表示在D中有一系列的元素，所以R(,d)=。
定义1((k,d,lambda;)-异常值)。给一个不确定的数据集D。对于一个元素eisin;D，使W(e,d,k)作为R(e,d)的所有可能值中的一个子集，那么对于每个可能值wisin;W(e,d,k)，|R(e,w)|ge;k。当且仅当所有W(e,d,k)中的元素的和小于或等于lambda;时，一个元素eisin;D是一个((k,d,lambda;)-异常值)。
注意一点，对于一个元素eisin;D，如果R(,d)包含的元素个数少于k，那么它必须是一个异常值。因为W(e,d,k)是一个空集。对于任一个wisin;W(e,d,k)，我们用来再现w的概率，在这里至少有k个元素。通过定义1，一个数据集的(k,d,lambda;)-异常值检测必须满足式（1）
（1）
2.2概率数据流的滑动窗口异常值
让成为一个概率数据流，在这里i是的时间值。对于每一个都有一个的表示形式，在这个表示形式中，是数据项，是的可能性。在这篇文章中，我们使用一个基于元组的滑动窗口，这是一个固定长度为m的滑动窗口，从位置i开始，在i m-1处结束。我们使用来重现窗口中的元素。我们的方法可以很容易的被拓展到基于时间的滑动窗口中。
问题陈述：给定一个概率数据流，其中并且滑动窗口的长度为m,目标是，当i从1变为n-m 1时，针对每个滑动窗口检测出(k,d,lambda;)-异常值。
3 检测单一元素
在本节中，我们通过在滑动窗口中考虑单个元素e来简化问题。根据在第二节问题的定义,原始的方法是所有可能的值中展开的滑动窗口和累加k邻域可能值的概率。显然,检查的时间复杂度滑动窗口中的所有元素是O(m*)，当m很大时，这是非常耗时的。
3.1 具有概率的异常值
对于每个元素eisin;D，我们感兴趣的是在（1）e中计算。因为流中的数据是根据他们的时间排序的，如果且仅当我们在R（e,d）中找到第k个元素，我们可以说R（e,d）至少包含k个元素。表1中的第二列显示了两个元素的不同可能值。因此，为了得到可能的世界的总和至少有k个元素出现在R（e,d），我们累加了每一个数据都是R（e,d）的第k个元素的概率,用PK(ei;d;k),如(2)所示。
（2）
定理1。对于滑动窗口S[h,h m-1]中的每一个元素来说，（3）保持不变。
（3）
在图一的例子中，假设DS[1,5]=(e1,...e5)。让d等于50 ，k等于2，然后对于e5，我们有R（e5，50)= {e1,e2,e4,e5}，e5是一个非异常值的可能性是表1中w5和w15之间的可能性的总和，也就是0.8336。我们把元素放在R（e5,50）使用他们的时间节点，并且e2,e4和e5可能是第2个元素出现在R（e5,50)。这三个元素的概率分别是0.32，0.336和0.1776。因此，e2,e4和e5的可能性的总和是R中的第2个元素（e5,50）是0.8336，等于w5和w15之间的可能性的总和。
3.2 动态编程方法
为了计算（如（2）所示）来有效监测异常值，我们提出了动态编程算法（DPA），这个可以在多项式时间是使用。
对每个元素ejisin; R（e，d)，给定使用时间的有序元素，我们使用（4）来计算PK（ej,d,k）。
<p
全文共16497字，剩余内容已隐藏，支付完成后下载完整资料</p
资料编号：[16633]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
