序列数据相似搜索技术研究

发布时间：2020-09-11 22:51

　　序列数据广泛存在于医学、经济学等学科中,对其的数据挖掘在医疗诊断、金融数据分析等领域已有较为成功应用。序列数据是典型的海量、高维数据,如何对海量的序列数据进行高效的分析,对于揭示事物发展规律、为科学决策提供依据具有重要的意义。本文针对序列数据挖掘中的两项核心技术:序列相似度量及相似搜索技术进行了研究。本文的具体工作和贡献包括:(1)基于自适应搜索窗口的序列相似比对算法本文提出基于自适应搜索窗口的序列相似比对算法(Adaptive Searching WindowDTW,ADTW),算法利用分段聚集平均(Piecewise Aggregate Approximation,PAA)策略进行序列抽样,得到低精度序列,然后计算低精度序列下的比对路径,并根据低精度距离矩阵上的梯度变化预测路径偏差,限制路径搜索窗口的拓展范围;随后依次提高序列精度,并在搜索窗口内修正路径、计算新的搜索窗口,最终,实现DTW距离和相似比对路径的快速求解。对比FastDTW,ADTW算法在同等度量准确率下计算效率提升约20%,其时间复杂度为O(n)。(2)基于多级下界过滤的时序相似搜索算法针对时序数据相似搜索效率较低的问题,本文提出基于多级下界过滤的相似搜索算法(Multi_LB),算法挑选多个下界距离函数组成多级过滤器,对候选集中的无效序列进行分级过滤,同时根据实时过滤成功率对下界函数的过滤顺序进行动态调整,从而保持较高的过滤效率。Multi_LB避免了对部分差异明显的无效序列进行耗时的下界度量,并降低了过滤失败产生的额外计算开销。实验表明,相较基于单一下界过滤的搜索算法,本文算法在保证搜索完备性的同时,搜索效率提升15%左右。
【学位单位】：沈阳航空航天大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP301.6
【部分图文】：

过程图,函数计算,过程,短列

大量多维的索引结果能够被应用，如 R-tr将首尾之差作为特征值，则算法的时间复杂在搜索同起点的随机游走数据时，它展现了出的一种紧致度更高的 DTW 下界距离[43]。= (min( ),max( ))，那么 LB_Yi 可以定义( , ) = ∑∑ | ( ) max( ( ) ( )∑ | ( ) max( ( ) ( )程如图 4.3 所示，函数累加其中一条序列所然其时间复杂度为 O(n)，这个函数的计算远也意味着，整个相似搜索过程可以在很短列。

时间序列,函数,下界,特征值

图 4.2 LB_Kim 函数的四个特征值之和作为下界距离。这四个两条时间序列间的 LB_Kim 下界距离值为。LB_Kim函数的时间复杂度为O(n)。在得很高效，因为特征向量是四维的，所以每大量多维的索引结果能够被应用，如 R-将首尾之差作为特征值，则算法的时间复搜索同起点的随机游走数据时，它展现的一种紧致度更高的 DTW 下界距离[43] (min( ),max( ))，那么 LB_Yi 可以定( , ) = ∑∑ | ( ) max(( ) ( )∑ | ( ) max(( ) ( )

过程图,函数计算,过程,搜索窗口

图 4.4 LB_Keogh 函数计算过程对搜索窗口的限制，但也导致无法应为序列长度，R 为搜索窗口的半径。需( , ) ≠ LB ( , )；但两者都向计算候选序列 S 的包络线，得到下距离，我们取其最大值作为紧致度更图 4.5 LB_Keogh 的反向度量数的过滤能力，我们采用多个数据集

【参考文献】