一种数据流突变点快速探测算法的研究与实现

发布时间：2020-06-18 17:18

【摘要】：数据已经成为与自然资源、人力资源一样重要的战略资源,数据中隐藏着巨大的价值。大数据具有体量浩大、模态繁多、生成快速和价值巨大等特点。数据流中的时序数据分析是大数据研究的重要分支。数据流分析技术就是从各种类型繁多的数据中快速获得有价值的信息。数据流及其应用的迅速发展不仅促进基础科学的发展,更是许多行业技术进步、国家创新和产业发展的重要机遇和挑战。数据流的突变指的是当前时刻数据流的值相比于之前的数据流的值或者是数据流的平均值差值比较大。目前的数据流中突变点检测的分析方法大多很耗时,且对两端的突变点检测不准确等问题。本文引入了HWKS算法,该方法能够快速的检测到数据中的突变点,并做了对比验证。在该算法的基础上,引入了滑动窗口,以实现数据的在线检测,并通过模拟的数据验证了该方法的有效性。此外,通过实际火灾发生时的温度、烟雾浓度、CO和CO_2数据验证了该方法能够及时的检测到火灾的发生。HWKS算法是在Haar小波变换理论和改进的KS统计检验理论的基础上提出的。HWKS算法主要针对的是数据流中的时序模型数据,该算法的主要步骤是先应用多级Haar小波变换分解待检测的数据流,同时构建均值二叉树和差值二叉树。然后,在改进的KS统计的基础上,构建两种突变点检测的两个搜索规则,规则一是基于差值二叉搜索树,规则二是基于均值二叉搜索树,当规则一搜索不到突变点时,则采用规则二进行搜索,所以这两种规则是相互补充。最后,根据此规则进行突变点的检测。该算法采用自顶向下的搜索策略,并且以折半的思想进行查找,大大提高了检测的效率。本文通过仿真数据,将HWKS算法与KS检验、Haar小波和t检验三种方法从耗时、命中率、误差以及准确度四个方面进行了比较,验证了HWKS算法在算法效率、准确性和敏感性方面有明显的优势。为了应对数据流实时的特性,本文在HWKS算法的基础上,引入滑动窗口模型。通过仿真分析,探讨数据流的大小不变,滑动窗口尺寸的改变的情况下对数据流上突变点检测的影响。实验结果表明,滑动窗口越大检测到的突变点的位置越准确,但是滑动窗口也不是越大越好,还应考虑数据流的流速问题和数据流中有多个突变点的情况,为了验证HWKS算法对数据流中两端突变点的敏感性,本次仿真将突变点设置在数据流的起始位置和结束位置。实验结果表明,引入滑动窗口模型后,HWKS算法不仅对于数据边缘的突变点的检测仍然有很好的效果,同时也能够准确的探测出数据流中的所有的突变的。最后,本文通过模拟真实的火灾发生时的温度数据、烟雾浓度数据、CO浓度数据和CO_2浓度数据,运用带滑动窗口的HWKS算法和不带滑动窗口的HWKS算法进行了对比试验。实验结果表明引入滑动窗口后的HWKS算法不仅能够检测到火灾发生时的特征变化,同时也能检测出火灾后,这些特征的变化。此外,对于加入滑动窗口模型的HWKS算法比没有引入滑动窗口的HWKS算法要准确,所以该算法对火灾的探测有很好实际意义。
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13
【图文】：

示意图,Haar小波,示意图,快速探测

一种数据流突变点快速探测算法的研究与实1,2 1,2 1, 2, 2,3,..., log2k j k jk jcA cAcA k N (1,2 1,2 1, 2-, 2,3,..., log2k j k jk jcA cAcD k N (过 k 级 Haar 分解后可以获得 k 级近似分量kcA 和 k 级细节分2 3, ,...,k cD cD ，2k 1, 2,3,..., logN，即1 2 1Z (cA cD cD ... cD cD )kH k k k (中，cA 和 cD 分别为均值和差值参数。时序数据 Z 进行多级小波变换下图所示。

示意图,搜索规则,突变点,示意图

序数据会带来不同，那么其累积经验 ) ( ))j C 也同时成节点对应数据里存在据中存在突变点，那个选出来，并选择该结点起向下逐层选索路径。而且，这使一选择突变点路径孩子结点对应的时值的那条支路。其中规则一失效则 A_p ,

【相似文献】