摘要: 1．本文的创新点
1）针对概率数据流，本文提出了基于距离的离群点的新定义。不同于传统的面向确定数据，离群点的定义是基于距离的基础上引入了概率。本文给出新的离群点定义，即在滑动窗口中基于距离的离群点为在当前窗口内拥有的相邻数据点的数量不大于给定阀值的某个数据点。
2）本文提出了一种动态规划的方法（DPA），可以在线性时间内完成对每个数据点的检测，避免访问每个数据点对应的所有可能世界的实例，从而极大地改善了检测效率。同时，提出一种基于剪枝的过滤方法，称为PBA，用于有效地检测滑动窗口中的离群点。
3）在滑动窗口模型中，采用了增量检测方法。每滑动一次窗口，会导致一些数据过期，同时，一些新的数据加入到滑动窗口中。本文提出的方法可以避免重复检测那些既没有过期也不是新进入窗口的数据。提出剪枝策略加速动态检测的效率，涉及到设计和维护好的数据结构，以及在滑动窗口中动态插入和删除数据的维护问题。
2．实现方法
1）对滑动窗口中单一数据的检测
首先，本文揭示具有概率值的非离群点数据的一个性质：一个数据拥有k个以上相邻数据的概率等于该数据每个邻居成为第k个数据的概率。可以采用任何方式决定数据的排名，即数据的排列规则不影响最终的概率值。
上述性质为有效地进行离群点检测提供很好地帮助。基于此性质，提出了动态规划DPA方法，其时间复杂度为O(kn)，其中n为被检测数据点的邻居数据的平均数量。
2）对滑动窗口中全体数据的增量检测
一个滑动窗口可以容纳m个数据，如何挑选检测数据点，即对m个数据的检测顺序直接影响检测效率，具有关键性的作用。理想情况下，当一个数据被认定为不是离群点时，希望能同时说明它的部分相邻数据也不是离群点，反之亦然。因此，本文利用基于距离三角不等式的过滤思想，给出离群点检测中的过滤策略。
针对滑动窗口的滑动特性，每时每刻都产生新到数据和过期数据。提出增量检测方法，分析过期数据和新到数据对于滑动窗口中的其他数据的影响，并给出相应的解决方案。
3．结论及未来待解决的问题
本文研究了面向概率数据流的离群点检测技术，定义了新的概念，即面向概率数据的基于距离的离群点。提出了有效的基于动态规划的DPA方法和基于剪枝的PBA检测方法。大量的实验测试与分析显示所提出的技术具有很好的执行效率和扩展性能。未来主要工作包括多维概率数据流的离群点检测问题，以及数据间存在互斥关系时的离群点检测等问题。
4．实用价值或应用前景
离群点检测用于寻找数据集中的噪声数据，是数据挖掘、数据分析和数据管理等领域的重要技术。基于距离的离群点检测被广泛应用于网络入侵检测、银行信贷等应用。现有的基于距离的离群点检测技术目前主要应用于在传统数据库中，其数据的存在性和可信性确凿无疑。但在很多现实的应用领域中，数据的收集和处理受到多种因素的影响，数据的不确定性逐渐受到了人们的关注，比如在传感器网络中，数据准确性和可信性会受到感知器件精度、感知结点能量和网络传输质量等因素的制约；在数据集成领域，由于数据源的不一致性和模式映射的复杂多样，集成后的数据不可避免的会引入不确定性。由于数据项引入了概率维度（或称可信性维度），应用于传统数据的技术无法直接应用于不确定数据。