基于概率模型的离群点检测近似算法的研究与实现

发布时间：2021-09-06 07:49

　　随着信息技术的不断发展,流数据逐渐成为当今主要数据类型,它具有数据规模大、传输速度快等特征,这些特征给高效管理流数据带来巨大挑战。离群点检测是数据挖掘领域一种重要数据挖掘技术,在流环境下有着广泛的应用。现有算法普遍存在计算和空间代价大等问题,无法在高速流环境下高效工作,用户的实时性要求无法满足。本文研究面向流数据的离群点近似检测问题,以降低精度为代价换取计算代价的大幅降低,满足用户实时性需求。本文贡献点总结如下:本文首先研究了滑动窗口模型下基于距离阈值的离群点近似检测问题。针对此类问题,本文提出查询处理框架PBOAD（Partition-Based Outlier Approximate Detection）。PBOAD首先利用分片技术对滑动窗口进行划分,以此为基础,提出基于M-Tree的索引PMT（Partition based M-Tree）管理各分片数据。再次,PBOAD使用带概率误差保证的离群点预测算法过滤安全对象,降低算法复杂性。本文随后研究了滑动窗口模型下基于kNN平均距离的离群点近似检测问题。针对此问题,本文提出查询处理框架GAOAD（Grid-based Average... 

【文章来源】：沈阳航空航天大学辽宁省

【文章页数】：52 页

【学位级别】：硕士

【部分图文】：

PBOAD与其它算法在不同窗口N下的CPU时间比较

PBOAD 的增长速度最慢，且消耗的计算代价最低。其原因在于，窗口长度越长，查询范围内邻居的数目越多。然而，PBOAD 只在最后一个分片内进行查询，这导致该框架对窗口长度的增加不敏感。因此，PBOAD 的效率最高。与此同时，PBOAD 拥有较好的空间效率，它消耗的内存最小。其原因在于，该算法只维护少量对象的 k 近邻列表，而其它对象需要维护所有安全对象的 k 近邻列表。由此可见，PBOAD 适合在内存受限的环境下使用。(a) 数据集 Tao (b) 数据集 Stock (c) 数据集 HPC图 5.1 PBOAD 与其它算法在不同窗口 N 下的 CPU 时间比较

(a) 数据集 Tao (b) 数据集 Stock (c) 数据集 HPC图 5.3 PBOAD 与其它算法在不同滑动 s 下的 CPU 时间比较(a) 数据集 Tao (b) 数据集 Stock (c) 数据集 HPC图 5.4 PBOAD 与其它算法在不同滑动 s 下的 MEMORY 比较第三组实验测试参数 k 对算法性能的影响，k 从 5 变化到 100，其它参数使用默认参数。如图所示，三个算法的运行时间均随 k 的增加而增加，但是 PBOAD 的增长速度最慢，其原因在于，随着 k 的增加，算法需要维护的 k 邻居数目也会相应增加，但是，PBOAD 只需维护少量非安全对象的 k 近邻列表。因此，当 k 增加时，PBOAD 计算时间

【参考文献】：
期刊论文
[1]VDOD:一种基于KD树的分布式离群点检测算法[J]. 李子茂,骆庆,刘晶.  计算机与数字工程. 2018(03)
[2]基于K-means的数据流离群点检测算法[J]. 韩崇,袁颖珊,梅焘,耿慧玲.  计算机工程与应用. 2017(03)
[3]BOD:一种高效的分布式离群点检测算法[J]. 王习特,申德荣,白梅,聂铁铮,寇月,于戈.  计算机学报. 2016(01)
[4]基于密度的不确定数据离群点检测研究[J]. 洪沙,林佳丽,张月良.  计算机科学. 2015(05)
[5]一种基于密度的不确定数据离群点检测算法[J]. 姜元凯,郑洪源,丁秋林.  计算机科学. 2015(04)
[6]不确定数据流上Top-k异常点查询算法[J]. 曹科研,王国仁,韩东红,李硕儒.  计算机科学与探索. 2015(02)

硕士论文
[1]不确定数据挖掘技术研究及应用[D]. 张颖.南京航空航天大学 2016



本文编号：3387062