基于提前终止的加速时间序列弯曲算法

动态时间弯曲(DTW)距离是时间序列相似搜索的一种重要距离度量,但其精确计算是一个性能瓶颈。针对此问题,提出一种名为EA_DTW的方法用于加速DTW距离的精确计算,该方法在计算累积距离矩阵中每个方格的距离时都判断其是否超过阈值,一旦超过则提前终止其余相关方格的距离计算;并对EA_DTW的过程进行了理论分析。实验对比表明,EA_DTW能够提高DTW的计算效率,在阈值与DTW距离相比较小时更加明显。     

基于分段极值DTW距离的时间序列相似性度量

在时间序列相似性的研究中,通常采用的欧氏距离及其变形无法对在时间轴上发生伸缩或弯曲的序列进行相似性度量,本文提出了一种基于分段极值DTW距离的时间序列相似性度量方法可以解决这一问题。在动态时间弯曲(DTW)距离的基础上,本文定义了序列的分段极值DTW距离,并阐述了其完整的算法实现。与传统的DTW距离相比,分段极值DTW距离在保证度量准确性的同时大大提高了相似性计算的效率。文中最后运用MATLAB作对比实验,并给出实验结果数据,验证了该度量方法的有效性与准确性。     

一种新的DTW最佳弯曲窗口学习方法

时间序列相似性查询中,DTW(Dynamic Time Warping)距离是支持时间弯曲的经典度量,约束弯曲窗口的DTW是DTW最常见的实用形式。分析了传统DTW最佳弯曲窗口学习方法存在的问题,并在此基础上引入时间距离的概念,提出了新的DTW最佳弯曲窗口学习方法。由于时间距离是DTW计算的附属产物,因此该方法可以在几乎不增加运算量的情况下提高DTW的分类精度。实验证明,采用了新的学习方法后,具有最佳弯曲窗口的DTW分类精度得到明显改善,分类精度优于ERP(Edit Distance with Real Penalty)和LCSS(Longest Common SubSequence),接近TWED(Time Warp Edit Distance)的水平。     

基于弯曲距离三支决策的时序相似性算法

动态时间弯曲距离算法(DTW)是目前公认的最有效的时间序列相似性计算方法之一,但是较高的时间复杂度一直是其主要缺点。快速弯曲距离算法(FTW)能有效提高DTW的计算速度,但是该算法对不同粒度时间序列剪枝的行为是典型的二支决策,与人类处理不确定问题时普遍采用的三支判断不同。因此,通过将三支决策理论引入到DTW算法的优化工作中,建立了DTW三支决策模型;然后对DTW三支决策模型中的决策阈值α和β进行了基于误识别率的推导,并且给出了具体求解阈值α和β的模拟退火算法;最后基于上述理论提出了基于弯曲距离三支决策的时序相似性算法(3WD-DTW)。通过对比实验表明,与FTW算法相比,3WD-DTW算法在保持较快的计算速度的前提下明显提升了计算准确度,使其接近DTW的水平。     

DTW距离的过滤搜索方法

动态时间弯曲(DTW)距离支持时间序列的多种形变,具有较高的匹配精度,是一种重要的相似性度量方法.然而,该方法计算复杂度较高,制约了其在相似性搜索中的应用.为了平衡匹配精度与计算效率之间的矛盾,提出一种过滤搜索方法.首先,构造一种计算代价较低的DTW下界距离,用其进行粗略过滤,得到候选集;然后,利用提前终止策略,优化计算候选集中序列的DTW距离,得到搜索结果;最后,对所提出方法进行实验验证,结果表明,该方法能够提高DTW距离的相似性搜索效率,且具有非漏报性.     

飞机牵引车语音识别的动态时间规整优化算法

为研究飞机牵引车智能语音控制,实现机场环境下牵引车对飞行员语音命令的精确、高效识别,同时针对传统动态时间规整（DTW）算法计算量大、时间复杂度高、算法识别效率低的问题,提出了一种车辆语音识别的六边形弯曲窗口约束DTW优化算法。首先,从DTW算法原理、牵引车指令的语音特性和机场环境三方面,分析了弯曲窗口对DTW算法识别精度、效率的影响;然后,在Itakura Parallelogram菱形弯曲窗口约束DTW优化算法的基础上,进一步提出了六边形弯曲窗口约束的DTW全局优化算法;最后,通过改变优化系数,实现了最优六边形弯曲窗口约束的DTW算法方案。基于孤立词识别的实验结果表明,所提最优算法与传统DTW算法、菱形弯曲窗口约束的DTW算法相比,识别错误率分别降低77.14%和69.27%,识别效率分别提高48.92%和27.90%。该最优算法更具鲁棒性、时效性,可以作为飞机牵引车智能控制的理想指令输入端口。     

基于滑动平均与分段线性回归的时间序列相似性

针对时间序列相似性度量中欧氏距离对异常数据敏感以及DTW距离算法效率低的问题,提出基于滑动平均与分段线性回归的时间序列相似性方法。首先,使用初始可变滑动平均算法以及分段线性回归对原始时间序列进行数据变换,并将分段线性回归的参数(截距与距离)集作为时间序列的特征,以实现时间序列的特征提取和数据降维;然后,利用动态时间弯曲距离进行距离计算。该方法在时间序列相似性上与DTW算法的性能相近,但是在算法效率上几乎提高了96%。实验结果验证了该方法的有效性与准确性。     

基于Hadoop的异常传感数据时间序列检测

无线传感器网络中,异常时间序列的研究具有十分重要的意义。针对传统研究在海量数据环境中时间效率低下的问题,提出了基于Hadoop的异常时间序列检测算法。首先对时间序列进行预处理,然后在Hadoop的MapReduce操作中调用动态时间弯曲距离计算算法,实现了DTW距离计算的并行化,从而大大提高检测速度。同时针对传统DTW算法计算复杂度瓶颈问题以及传统约束方法准确率较低问题,提出了基于显著特征匹配的局部约束算法,对弯曲路径进行局部限制,在确保准确性的同时进一步降低了时间、空间复杂度。Hadoop平台下实验结果表明,该方法既提高了检测速度,又保证了检测准确率。     

基于分段特征及自适应加权的DTW相似性度量

利用动态时间弯曲（DTW）技术在原始多元时间序列进行相似性度量时时间复杂度较高,且DTW在追求最小弯曲距离的过程中可能会出现过渡拉伸和压缩的问题。提出一种基于分段特征及自适应加权的DTW多元时间序列相似性度量方法。对原始时间序列在各个变量维度上进行统一分段,选取分段后拟合线段的斜率、分段区间的最大值和最小值以及时间跨度作为每一段的特征,实现对原始序列的大幅降维,提高计算效率。在DTW计算最佳弯曲路径的过程中为每个点设置自适应代价权重,限制弯曲路径中点列的重复使用次数,改善时间序列因过度拉伸或压缩所导致的度量精度低的问题,以得到最优路径路线。实验结果表明,该方法能很好地度量多元时间序列之间的相似性,在多个数据集上都能取得较好的度量结果。     

基于分段降维和路径修正DTW的时序特征分类器设计

针对传统的动态时间弯曲（DTW）度量方法易出现过度弯曲现象且计算复杂度高、算法效率低等问题,提出一种基于路径修正的动态时间弯曲（UDTW）度量方法。首先通过分段降维方法——分段局部最大值平滑法（PLM）有效提取序列特征信息,减少UDTW的计算代价;其次,考虑了时间序列形态特征的相似性要求,给过度弯曲路径设置动态惩罚系数,以此修正路径的弯曲程度;最后,在改进度量距离基础上,采用1-近邻分类算法对时序数据进行分类,以提高时间序列相似性度量的准确率和效率。实验结果表明,在15个UCR数据集上,UDTW度量方法与传统DTW度量方法相比具有更高的分类准确率,UDTW在其中3个数据集上能实现100%分类正确;与导数DTW（DDTW）度量方法相比,UDTW分类准确率最多提高了71.8%,而PLM-UDTW在不影响分类准确率的前提下执行时间减小了99%。     

基于适应性分段估计的数据流相似性搜索

相似性搜索在股票交易行情、网络安全、传感器网络等众多领域应用广泛.由于这些领域中产生的数据具有无限的、连续的、快速的、实时的特性,所以需要适合数据流上的在线相似性搜索算法.首先,在具有或不具有全局约束条件下,分别提出了没有索引结构的DTW(dynamic time warping)下限函数LB_seg_WF_global和LB_seg_WF,它们是一种分段DTW技术,能够处理数据流上的非等长序列间在线相似性匹配问题.然后,为了进一步提高LB_seg_WF_global和LB_seg_WF的近似程度,提出了一系列的改进方法.最后,针对流上使用LB_seg_WF_global或LB_seg_WF可能会出现连续失效的情况,分别提出了DTW的下限函数LB_WF_global(具有全局约束条件)和上限函数UB_WF、下限函数LB_WF(不具有全局约束条件).通过增量方式快速估计DTW,极大地减少了估计DTW的冗余计算量.通过理论分析和统计实验,验证了该方法的有效性.     

Online signature verification using a new extreme points warping technique

There are two common methodologies to verify signatures: the functional approach and the parametric approach. In this paper, we propose a new warping technique for the functional approach in signature verification. The commonly used warping technique is dynamic time warping (DTW). It was originally used in speech recognition and has been applied in the field of signature verification with some success since two decades ago. The new warping technique we propose is named as extreme points warping (EPW). It proves to be more adaptive in the field of signature verification than DTW, given the presence of the forgeries. Instead of warping the whole signal as DTW does, EPW warps a set of selected important points. With the use of EPW, the equal error rate is improved by a factor of 1.3 and the computation time is reduced by a factor of 11.     

Faster retrieval with a two-pass dynamic-time-warping lower bound

The dynamic time warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB_Keogh). We compare LB_Keogh with a tighter lower bound (LB_Improved). We find that LB_Improved-based search is faster. As an example, our approach is 2-3 times faster over random-walk and shape time series.     

Recognising online spatial activities using a bioinformatics inspired sequence alignment approach

In this paper we address the problem of recognising embedded activities within continuous spatial sequences obtained from an online video tracking system. Traditionally, continuous data streams such as video tracking data are buffered with a sliding window applied to the buffered data stream for activity detection. We introduce an algorithm based on Smith-Waterman (SW) local alignment from the field of bioinformatics that can locate and accurately quantify embedded activities within a windowed sequence. The modified SW approach utilises dynamic programming with two dimensional spatial data to quantify sequence similarity and is capable of recognising sequences containing gaps and significant amounts of noise. A more efficient SW formulation for online recognition, called Online SW (OSW), is also developed. Through experimentation we show that the OSW algorithm can accurately and robustly recognise manually segmented activity sequences as well as embedded sequences from an online tracking system. To benchmark the classification performance of OSW we compare the approach to dynamic time warping (DTW) and the discrete hidden Markov model (HMM). Results demonstrate that OSW produces higher precision and recall than both DTW and the HMM in an online recognition context. With accurately segmented sequences the SW approach produces results comparable to DTW and superior to the HMM. Finally, we confirm the robust property of the SW approach by evaluating it with sequences containing artificially incorporated noise.     

基于局部梯度和二进制模式的时间序列分类算法

时间序列分类问题是时间序列数据挖掘中的一项重要任务, 近些年受到了越来越广泛的关注. 该问题的一个重要组成部分就是时间序列间的相似性度量. 在众多相似性度量算法中, 动态时间规整是一种非常有效的算法,目前已经被广泛应用到视频、音频、手写体识别以及生物信息处理等众多领域. 动态时间规整本质上是一种在边界及时间一致性约束下...     

改进DTW下界函数的距离度量方法研究

动态时间弯曲算法（DTW）是一种常见的时间序列相似性度量方法,对数据挖掘任务起着至关重要的作用。针对现有DTW算法的时间复杂度高、度量精确度一般的特征,提出一种DTW下界函数的提前终止算法（LB＿ESDTW）。引入提前终止思想,提高算法的执行效率;再在提前终止算法思想的基础上,与DTW下界函数相结合,提出一种基于提前终止DTW的下界函数算法（LB＿ESDTW）。该算法在保证高效的运行时间效率的同时,也使得算法的度量准确率得到了提升。实验结果表明,LB＿ESDTW在绝大部分时间序列数据集中,都表现出良好的适应性,针对不同类别的时间序列,都能有良好的度量性能。     

Exact indexing of dynamic time warping

The problem of indexing time series has attracted much interest. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However, it has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic time warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately, however, DTW does not obey the triangular inequality and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques or abandoned the idea of indexing and concentrated on speeding up sequential searches. In this work, we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.     

Merge-Weighted Dynamic Time Warping for Speech Recognition

Obtaining training material for rarely used English words and common given names from countries where English is not spoken is di?cult due to excessive time, storage and cost factors. By considering pe...     

Dynamic time warping constraint learning for large margin nearest neighbor classification

Nearest neighbor (NN) classifier with dynamic time warping (DTW) is considered to be an effective method for time series classification. The performance of NN-DTW is dependent on the DTW constraints because the NN classifier is sensitive to the used distance function. For time series classification, the global path constraint of DTW is learned for optimization of the alignment of time series by maximizing the nearest neighbor hypothesis margin. In addition, a reduction technique is combined with a search process to condense the prototypes. The approach is implemented and tested on UCR datasets. Experimental results show the effectiveness of the proposed method.