基于LDTW距离的序列相似度量方法研究及应用

发布时间：2020-07-17 16:37

【摘要】：相似度量是机器学习的重要研究内容,广泛应用于自然语言处理、计算机视觉等领域。动态时间弯曲距离(Dynamic Time Warping,DTW)作为一种重要的相似度量方法,能够有效解决序列发生扭曲变形而无法匹配的难题,但存在数据点之间的一对多问题(病理性对齐),导致其精确度不高。受限动态时间弯曲距离(Dynamic Time Warping under limited warping path length,LDTW)是在DTW基础上的改进算法,通过限制数据点的连接数量避免了病理性对齐问题,使算法精确度有较高的提升。本文从LDTW的推广实践入手,面向不同的数据场景扩展其应用领域。同时,针对其计算时间成本很高的问题,采用基于启发式搜索机制的蚁群算法对算法进行优化设计,在确保精确度的情况下降低其算法时间。本文主要研究工作如下:1.LDTW在小数据、贫信息系统中的应用研究。相对于大数据分析,小数据由于样本数量较小,更注重精确度要求。本文从小数据研究的重要工具—灰关联模型入手,展开LDTW的应用实践研究。经典灰关联模型局限于等长序列,面对不等长序列通常采用删除、均值、预测等方法进行补齐,而人工干预会引入新的不确定性。针对此问题,本文将LDTW引入经典灰关联度模型中,提出一种基于LDTW的灰关联度模型,分别对等长和不等长序列数据进行分析,并在灰关联聚类中进行实践。LDTW表现出更高的准确率及较好的鲁棒性,实现在小数据不确定性系统中的应用。2.面向大样本数据的LDTW优化算法研究。论文以降低算法时间开销为核心,在保证算法精确性的前提下,构建了一种基于蚁群算法的动态时间弯曲距离优化算法(An Optimized Dynamic Time Warping Distance Based on Ant Colony Optimisation Algorithm,ACO_LDTW)。由于LDTW是通过弯曲路径长度来限制最佳弯曲路径的长度,使得整个算法计算时间过长,不适用于数据量较大的样本情况。基于此分析,本文引入具有并行计算能力的启发式搜索机制,采用基于栅格地图的蚁群算法来代替LDTW的递归线性计算,并对蚁群算法中状态转移概率、信息素机制等进行修正。实验结果表明,新方法在确保分类准确率的前提下,有效提升了算法效率。将其应用在机械故障诊断领域中,ACO_LDTW表现出较高的故障分类精度性能。
【学位授予单位】：重庆邮电大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP181
【图文】：

病理性,附加因素,概念,距离矩阵

DTW 的病理性对齐问题进行了改进。该一个附加因素，有效地抑制了病理性对齐究工作的理论基础进行介绍，主要包括：生了动态时间弯曲的概念，Berndt 和 Cl的研究中。图 2.1 就是一个典型的动态的距离矩阵；然后，根据动态规划的思想两序列进行匹配；最后，这条最短弯曲路法的最佳路径是通过了局部最优化概念，效度量一些不易处理的数据序列间的相似

路径图,路径,观测数据,计算方法

1 1 1 2 1 2 1 2 2 2 1 21 2, , ... , , , ... , .. ... ... ... , , ... , .. ... ... ... , , ... ,n n m m m n M M M nX Y dist X Y dist X Y Y dist X Y dist X Y Y dist X Y dist X Y Y dist X Y dist X Y列 X 中第 m 个观测数据和序列Y 中的计算方法。本文中， ( ,) | m n mdist X Y X 定义为 { },max( ) 1 2 kW w ,w ,...,w m,n k 2.2 所示。其中W 的第 k 个元素定义一个元素( m,n )一一对应。

序列,欧式距离

图 2.3 欧式距离.2 LDTWDTW 作为有效解决不等长序列的相似度量方法，却存在病理性对齐的问图 2.4 展示出了由 DTW 产生的一个典型病理性对齐的例子，其中可以观察几异点（如图 2.4 中标注的红色三角形）[48]。可以解释为一条序列中的一个点连外一条序列中的多个点，产生了奇异点，导致弯曲路径偏离对角线太远，造成态的匹配。显然，这样的对准不是“正确的”，这种对齐极大地影响了相似性的准确性。

【相似文献】