面向多维流数据的离群点检测算法研究与实现
发布时间：2021-03-04 20:26
流数据的离群点检测在信用卡欺诈检测、股票投资计划等许多现代应用中都发挥着重要作用,是数据管理领域中的一项重要问题。应用最为广泛的基于距离的离群点检测现已被广泛研究。但现有技术无法支持面向多维流数据的离群点高效检测,其根本原因是高昂的范围查询和候选对象维护代价。针对上述问题,本文提出了查询处理框架PIOD（Partition-Index based Outlier Detection）和ISOD（Index based Slide-query Outlier Detection）。本文首先研究了滑动窗口模型下基于kNN的离群点检测问题。针对此类问题,本文提出查询处理框架PIOD。PIOD首先利用分片技术对滑动窗口进行划分,基于此,PIOD以Z曲线为基础提出ZPH-Tree索引管理流数据,同时本文增加缓冲区更新机制提高索引的适用性。再次,PIOD基于ZPH-Tree提出候选离群维护算法,该算法通过分片技术和索引空间过滤,避免维护所有对象的k近邻。此外,本文提出基于EM-tree索引的CSM（Candidate-Set Maintain）算法通过维护候选对象间的位置关系和分值关系,降低候选对...
【文章来源】：沈阳航空航天大学辽宁省
【文章页数】：56 页
【学位级别】：硕士
【部分图文】：
不同窗口大小下算法的CPU运行时间
(a) Tao (b) Stock (c) HPC图 5.2 不同窗口大小下算法的内存峰值随着滑动对象个数的增加，本文有以下发现：CPU 时间. 1)kNN_PIOD 算法的性能更好，在最好情况下，它的运行时间是kNN_LEAP 的 0.01 倍；2)两种算法的运行时间基本上都随滑动对象个数的增加而增加，当 s/N 达到 50%时 kNN_PIOD 与 kNN_LEAP 运行时间逐渐接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法利用索引维护了流数据间的位置关系，支持高效范围查询，降低了计算代价；②kNN_PIOD 算法采用分片技术维护算法的稳定性，但当 s/N达到 50%及其以上时，与 kNN_LEAP 的基于滑动对象个数划分相同，因此运行时间逐渐接近。内存峰值. 1)kNN_LEAP 的内存峰值是 kNN_PIOD 的 1 到 3 倍；2)随着滑动对象个数的增加，kNN_LEAP 内存峰值的增长速度更快。其原因是：滑动对象个数的增长会导致 kNN_LEAP 中对象邻居信息的频繁更新，需要重复计算非候选对象邻居信息，而kNN_PIOD 通过候选集合维护候选对象间的分值关系，避免了非潜在离群点的空间维护代价。
(a) Tao (b) Stock (c) HPC图 5.3 不同滑动对象个数下算法的 CPU 运行时间(a) Tao (b) Stock (c) HPC图 5.4 不同滑动对象个数下算法的内存峰值CPU 时间. 1)kNN_PIOD 算法的性能更好，在最好情况下，它的运行时间是kNN_LEAP 的 0.01 倍；2)两种算法的运行时间都随离群点个数的增加而增加，当 n/W 增长到接近 20%时，kNN_PIOD 与 kNN_LEAP 运行时间逐渐接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法维护了潜在离群点，避免了对象间距离的重复计算代价和扫描窗口代价；②同样地，正是由于 kNN_PIOD 维护了至少 1 倍的潜在离群点，当
【参考文献】：
期刊论文
[1]VDOD:一种基于KD树的分布式离群点检测算法[J]. 李子茂,骆庆,刘晶. 计算机与数字工程. 2018(03)
[2]一种分布式计算的空间离群点挖掘算法[J]. 张卫平,刘纪平,仇阿根,张用川,赵阳阳. 测绘科学. 2017(08)
[3]无线传感网离群点检测技术研究综述[J]. 叶冬芬,杨明霞,范伟,邵鹏飞. 计算机应用研究. 2015(07)
[4]BOD:一种高效的分布式离群点检测算法[J]. 王习特,申德荣,白梅,聂铁铮,寇月,于戈. 计算机学报. 2016(01)
[5]一种基于密度的不确定数据离群点检测算法[J]. 姜元凯,郑洪源,丁秋林. 计算机科学. 2015(04)
[6]基于密度划分的离群点检测算法[J]. 魏龙,王勇. 计算机与现代化. 2015(03)
[7]基于层次聚类的离群点分析方法[J]. 张俊溪,杨海粟. 计算机技术与发展. 2014(08)
[8]NLOF:一种新的基于密度的局部离群点检测算法[J]. 王敬华,赵新想,张国燕,刘建银. 计算机科学. 2013(08)
硕士论文
[1]QAR数据集离群点检测及故障定位算法研究[D]. 王丽婧.中国民航大学 2015
[2]基于密度的局部离群点检测算法的研究与改进[D]. 赵新想.华中师范大学 2014
本文编号：3063863
【文章来源】：沈阳航空航天大学辽宁省
【文章页数】：56 页
【学位级别】：硕士
【部分图文】：
不同窗口大小下算法的CPU运行时间
(a) Tao (b) Stock (c) HPC图 5.2 不同窗口大小下算法的内存峰值随着滑动对象个数的增加，本文有以下发现：CPU 时间. 1)kNN_PIOD 算法的性能更好，在最好情况下，它的运行时间是kNN_LEAP 的 0.01 倍；2)两种算法的运行时间基本上都随滑动对象个数的增加而增加，当 s/N 达到 50%时 kNN_PIOD 与 kNN_LEAP 运行时间逐渐接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法利用索引维护了流数据间的位置关系，支持高效范围查询，降低了计算代价；②kNN_PIOD 算法采用分片技术维护算法的稳定性，但当 s/N达到 50%及其以上时，与 kNN_LEAP 的基于滑动对象个数划分相同，因此运行时间逐渐接近。内存峰值. 1)kNN_LEAP 的内存峰值是 kNN_PIOD 的 1 到 3 倍；2)随着滑动对象个数的增加，kNN_LEAP 内存峰值的增长速度更快。其原因是：滑动对象个数的增长会导致 kNN_LEAP 中对象邻居信息的频繁更新，需要重复计算非候选对象邻居信息，而kNN_PIOD 通过候选集合维护候选对象间的分值关系，避免了非潜在离群点的空间维护代价。
(a) Tao (b) Stock (c) HPC图 5.3 不同滑动对象个数下算法的 CPU 运行时间(a) Tao (b) Stock (c) HPC图 5.4 不同滑动对象个数下算法的内存峰值CPU 时间. 1)kNN_PIOD 算法的性能更好，在最好情况下，它的运行时间是kNN_LEAP 的 0.01 倍；2)两种算法的运行时间都随离群点个数的增加而增加，当 n/W 增长到接近 20%时，kNN_PIOD 与 kNN_LEAP 运行时间逐渐接近。其原因是：①和kNN_LEAP 相比，kNN_PIOD 算法维护了潜在离群点，避免了对象间距离的重复计算代价和扫描窗口代价；②同样地，正是由于 kNN_PIOD 维护了至少 1 倍的潜在离群点，当
【参考文献】：
期刊论文
[1]VDOD:一种基于KD树的分布式离群点检测算法[J]. 李子茂,骆庆,刘晶. 计算机与数字工程. 2018(03)
[2]一种分布式计算的空间离群点挖掘算法[J]. 张卫平,刘纪平,仇阿根,张用川,赵阳阳. 测绘科学. 2017(08)
[3]无线传感网离群点检测技术研究综述[J]. 叶冬芬,杨明霞,范伟,邵鹏飞. 计算机应用研究. 2015(07)
[4]BOD:一种高效的分布式离群点检测算法[J]. 王习特,申德荣,白梅,聂铁铮,寇月,于戈. 计算机学报. 2016(01)
[5]一种基于密度的不确定数据离群点检测算法[J]. 姜元凯,郑洪源,丁秋林. 计算机科学. 2015(04)
[6]基于密度划分的离群点检测算法[J]. 魏龙,王勇. 计算机与现代化. 2015(03)
[7]基于层次聚类的离群点分析方法[J]. 张俊溪,杨海粟. 计算机技术与发展. 2014(08)
[8]NLOF:一种新的基于密度的局部离群点检测算法[J]. 王敬华,赵新想,张国燕,刘建银. 计算机科学. 2013(08)
硕士论文
[1]QAR数据集离群点检测及故障定位算法研究[D]. 王丽婧.中国民航大学 2015
[2]基于密度的局部离群点检测算法的研究与改进[D]. 赵新想.华中师范大学 2014
本文编号：3063863
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3063863.html
