基于AUC方差的变点检测算法及其并行化研究

论文摘要

变点检测是统计分析的一个热门研究方向,在经济学、生物遗传学、地质学和气象学等许多领域都有着重要的应用。变点可以描述为时间序列中发生结构性突变的时刻或位置,这种突变体现在变点前和变点后的时间序列遵循两个不同的分布。在实际应用中,准确地检测出序列中的变点,既可获取序列中的蕴含的丰富的信息,也能及时地规避因异常带来的风险。故而,对变点问题进行深入研究极为重要。本文在已有研究将曲线下面积(Area Under the Curve,AUC)用于变点检测的基础上,考虑到AUC其他的统计特性,提出了一种基于AUC方差的非参数变点检测算法。新算法检测变点的过程由两个阶段构成,即数据预处理阶段和检测阶段。第一阶段,采用双滑动窗口法对时间序列数据进行预处理,在每个滑动位置提取与窗口中数据相对应的AUC方差;第二阶段,将放大一定倍数后的AUC方差作为统计量,利用统计假设检验方法来确定变点的存在性,在变点存在的前提下,进一步通过寻找统计量的局部极小值来估计变点发生的位置或时刻。这种非参数方法充分利用了AUC优越的统计特性,在时间序列分布形式未知的情况下也能有效地检测出变点。通过对比实验得知,AUC方差用于变点检测比AUC能更好地控制假设检验中的虚警率,在噪声干扰的环境下表现出更强的稳定性,在线检测延时也更短。与此同时,随着大数据时代的到来,越来越多的研究领域需要面对与日俱增的数据量,变点检测领域亦是如此。在实际的检测环境中,待检测数据的容量往往会很大,仅依靠CPU串行处理方式实现变点检测,需要消耗大量的时间。针对这一问题,并考虑到基于AUC方差的变点检测算法在处理单变点问题时效果最好,本文采用统一计算设备架构(Compute Unified Device Architecture,CUDA)技术对AUC方差实现单变点检测过程做并行化处理,尽可能让更多的计算任务在GPU上并行完成。其中,采用了两种不同的存储器优化策略来实现数据预处理阶段的并行处理,而检测阶段的并行处理直接借助于CUDA内部集成的高性能函数库Thrust,同时也基于共享存储器优化策略,设计了一种用于单变点检测的GPU通用计算(GPGPU)框架。通过对比实验得知,本文所提的变点检测算法在CUDA上的检测效率要明显高于CPU,而数据预处理阶段通过共享存储器优化实现效果最佳。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 课题研究的背景和意义
•   1.2 国内外研究现状
•     1.2.1 变点检测技术的研究现状
•     1.2.2 并行计算技术的研究现状
•   1.3 论文的主要研究内容
•   1.4 本章小结
• 第二章 非参数的变点检测算法研究
•   2.1 变点检测概述
•   2.2 变点检测算法的分类准则
•   2.3 变点检测的非参数方法
•     2.3.1 基于Mann-Whitney统计量的变点检测
•     2.3.2 基于KS和 CvM统计量的变点检测
•   2.4 本章小结
• 第三章 AUC算法的研究
•   3.1 AUC概述
•   3.2 AUC均值和方差的基本算法
•   3.3 不同母体分布下AUC的均值和方差
•   3.4 基于秩统计量的快速算法
•   3.5 本章小结
• 第四章 基于AUC方差的变点检测算法分析
•   4.1 基于AUC方差的单变点检测
•     4.1.1 数据预处理阶段
•     4.1.2 检测阶段
•   4.2 两种变点检测算法对比分析
•   4.3 不同母体分布下AUC方差用于变点检测的实验仿真
•   4.4 基于AUC方差的多变点检测
•   4.5 本章小结
• 第五章 基于AUC方差的变点检测算法并行化实现
•   5.1 CUDA简介
•     5.1.1 CPU-GPU异构系统
•     5.1.2 CUDA软件体系
•     5.1.3 CUDA编程模型
•     5.1.4 CUDA内存结构
•   5.2 AUC方差实现单变点检测的过程CUDA加速
•     5.2.1 CUDA计算任务分配
•     5.2.2 变点检测算法的并行优化策略
•     5.2.3 一种用于单变点检测的GPGPU计算框架
•   5.3 实验设计与仿真
•     5.3.1 实验准备工作
•     5.3.2 测试变点检测算法并行实现性能
•     5.3.3 测试线程块尺寸对检测性能的影响
•   5.4 本章小结
• 总结与展望
• 参考文献
• 攻读硕士学位期间发表论文
• 致谢

文章来源

类型: 硕士论文

作者: 李香银

导师: 徐维超,雷刚

关键词: 变点检测,非参数方法,并行计算

来源: 广东工业大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 广东工业大学

分类号: TP311.13;O211.61

DOI: 10.27029/d.cnki.ggdgu.2019.000808

总页数: 67

文件大小: 2209K

下载量: 23