一种新的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)的水平。     

Hierarchical clustering of time series data with parametric derivative dynamic time warping

Dynamic Time Warping (DTW) is a popular and efficient distance measure used in classification and clustering algorithms applied to time series data. By computing the DTW distance not on raw data but on the time series of the (first, discrete) derivative of the data, we obtain the so-called Derivative Dynamic Time Warping (DDTW) distance measure. DDTW, used alone, is usually inefficient, but there exist datasets on which DDTW gives good results, sometimes much better than DTW. To improve the performance of the two distance measures, we can combine them into a new single (parametric) distance function. The literature contains examples of the combining of DTW and DDTW in algorithms for supervised classification of time series data. In this paper, we demonstrate that combination of DTW and DDTW can also be applied in a method of time series clustering (unsupervised classification). In particular, we focus on a hierarchical clustering (with average linkage) of univariate (one-dimensional) time series data. We construct a new parametric distance function, combining DTW and DDTW, where a single real number parameter controls the contribution of each of the two measures to the total value of the combined distances. The parameter is tuned in the initial phase of the clustering algorithm. Using this technique in clustering methods requires a different approach (to address certain specific problems) than for supervised methods. In the clustering process we use three internal cluster validation measures (measures which do not use labels) and three external cluster validation measures (measures which do use clustering data labels). Internal measures are used to select an optimal value of the parameter of the algorithm, where external measures give information about the overall performance of the new method and enable comparison with other distance functions. Computational experiments are performed on a large real-world data base (UCR Time Series Classification Archive: 84 datasets) from a very broad range of fields, including medicine, finance, multimedia and engineering. The experimental results demonstrate the effectiveness of the proposed approach for hierarchical clustering of time series data. The method with the new parametric distance function outperforms DTW (and DDTW) on the data base used. The results are confirmed by graphical and statistical comparison.     

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.     

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.     

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

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

辅助信息自动生成的时间序列距离度量学习

对于时间序列聚类任务而言,一个有效的距离度量至关重要.为了提高时间序列聚类的性能,考虑借助度量学习方法,从数据中学习一种适用于时序聚类的距离度量.然而,现有的度量学习未注意到时序的特性,且时间序列数据存在成对约束等辅助信息不易获取的问题.提出一种辅助信息自动生成的时间序列距离度量学习(distancemetric learning based on side information autogeneration for time series,简称SIADML)方法.该方法利用动态时间弯曲(dynamic time warping,简称DTW)距离在捕捉时序特性上的优势,自动生成成对约束信息,使习得的度量尽可能地保持时序之间固有的近邻关系.在一系列时间序列标准数据集上的实验结果表明,采用该方法得到的度量能够有效改善时间序列聚类的性能.     

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

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

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

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

基于时间加权改进的LDTW算法

在时间序列相似性度量研究中,动态时间弯曲（dynamic time warping,DTW）是最为常用的算法之一,但其存在病态对齐问题且未考虑时间属性影响。限制对齐路径长度DTW（DTW under limited warping path length,LDTW）和时间加权DTW（time-weighed DTW,TDTW）分别尝试解决上述两个问题中的一个,但未能同时解决DTW两方面的不足。为此提出一种综合时间权重的LDTW（time-weighting LDTW,TLDTW）算法。首先通过测量两个时间序列中时间点对的距离构建时间权值矩阵;然后在LDTW累计成本矩阵递归填充过程中融合对应的时间权值,以实现在考虑时间因素影响的同时保留有效抑制病态对齐特性。基于UCR数据集进行1-NN分类实验,实验结果显示基于TLDTW相似度量的分类准确率优于其他对比算法,且进一步对比验证了其可靠性。     

交通流时间序列分离方法

采用聚类分析方法对交通流时间序列进行分析可以发现典型的交通流变化模式。通常 可采用欧式距离及K均值算法进行时间序列聚类,但经分析发现单凭此方法还难以实现不同变化趋 势的交通流时间序列的有效分离。针对此问题,提出了将动态时间弯曲及灰色关联度引入交通流时 间序列相似性度量,且结合层次化聚类方法对交通流时间序列进一步分离的方法。通过实验研究,发 现基于灰色关联度的层次化聚类方法能较好地实现交通流时间序列的进一步有效分离。     

一种多元台风时间序列的相似性度量方法

台风相似性度量方法的研究对防灾减灾、辅助决策等具有重要意义。目前,台风相似性的研究大多集中在台风路径的相似性度量上。首先,梳理影响台风相似性度量的多个要素,提出了基于多元时间序列的台风数据描述方法;其次,提出了台风时间序列完整性、一致性评估与修复方法;最后,针对台风时间序列的不等长问题,设计了一种基于主成分分析和动态时间弯曲距离的相似性度量方法。通过实验验证,该方法能够实现台风相似性的有效度量。     

Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations

Similarity search is a core module of many data analysis tasks, including search by example, classification, and clustering. For time series data, Dynamic Time Warping (DTW) has been proven a very effective similarity measure, since it minimizes the effects of shifting and distortion in time. However, the quadratic cost of DTW computation to the length of the matched sequences makes its direct application on databases of long time series very expensive. We propose a technique that decomposes the sequences into a number of segments and uses cheap approximations thereof to compute fast lower bounds for their warping distances. We present several, progressively tighter bounds, relying on the existence or not of warping constraints. Finally, we develop an index and a multi-step technique that uses the proposed bounds and performs two levels of filtering to efficiently process similarity queries. A thorough experimental study suggests that our method consistently outperforms state-of-the-art methods for DTW similarity search.     

CSDTW: 一种时间序列流上的受限动态弯曲距离

针对SPRING提出的使用精确DTW距离造成弯曲矩阵中有许多无用的计算数据格的不足,提出一种受限的动态时间弯曲距离CSDTW。通过限制某时刻弯曲路径的弯曲程度,同时结合DTW上的提前终止算法,以减少无用数据格的出现。实验对比表明,CSDTW能够避免大量冗余数据格的计算,加快流环境下精确DTW处理的效率。     

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.     

基于特征点界标过滤的时间序列模式匹配方法

动态时间弯曲距离能度量不等长的时间序列、且具有较高的匹配精度,因此广泛应用在时间序列模式匹配中。但其计算复杂度较高,制约了在大规模数据集上的应用。为了实现时间序列模式度量结果和计算复杂度的平衡,提出一种基于特征点界标过滤的时间序列模式匹配方法。首先,提出一种特征点界标过滤的特征提取方法,保留时间序列主要特征,压缩时间维度;然后,利用动态时间弯曲距离对特征序列进行相似性度量;最后,在应用数据集上对所提方法进行有效性验证。实验结果表明,所提方法在保证高精度的前提下,能有效降低计算复杂度。     

基于DTW距离的伪周期数据流异常检测

伪周期数据流是一类常见的数据流,广泛出现于各种监测应用中.在这类数据流中出现的异常可能蕴涵了感兴趣的领域知识,因此有必要检测异常的发生以作为进一步深入分析的基础.DTW距离较之欧氏距离具有更好的鲁棒性,采用DTW距离作为伪周期数据流不同波段间相似性的度量可以有效检测出有较少历史相似波段的异常波段,继而在此基础上提出了一种基于聚类索引的快速近似异常波段检测方法用以加速检测过程,在真实数据集上的实验表明了所提方法的有效性.     

Speeding up dynamic time warping distance for sparse time series data

Dynamic time warping (DTW) distance has been effectively used in mining time series data in a multitude of domains. However, in its original formulation DTW is extremely inefficient in comparing long sparse time series, containing mostly zeros and some unevenly spaced nonzero observations. Original DTW distance does not take advantage of this sparsity, leading to redundant calculations and a prohibitively large computational cost for long time series. We derive a new time warping similarity measure (AWarp) for sparse time series that works on the run-length encoded representation of sparse time series. The complexity of AWarp is quadratic on the number of observations as opposed to the range of time of the time series. Therefore, AWarp can be several orders of magnitude faster than DTW on sparse time series. AWarp is exact for binary-valued time series and a close approximation of the original DTW distance for any-valued series. We discuss useful variants of AWarp: bounded (both upper and lower), constrained, and multidimensional. We show applications of AWarp to three data mining tasks including clustering, classification, and outlier detection, which are otherwise not feasible using classic DTW, while producing equivalent results. Potential areas of application include bot detection, human activity classification, search trend analysis, seismic analysis, and unusual review pattern mining.     

Scaling and time warping in time series querying

The last few years have seen an increasing understanding that dynamic time warping (DTW), a technique that allows local flexibility in aligning time series, is superior to the ubiquitous Euclidean distance for time series classification, clustering, and indexing. More recently, it has been shown that for some problems, uniform scaling (US), a technique that allows global scaling of time series, may just be as important for some problems. In this work, we note that for many real world problems, it is necessary to combine both DTW and US to achieve meaningful results. This is particularly true in domains where we must account for the natural variability of human actions, including biometrics, query by humming, motion-capture/animation, and handwriting recognition. We introduce the first technique which can handle both DTW and US simultaneously, our techniques involve search pruning by means of a lower bounding technique and multi-dimensional indexing to speed up the search. We demonstrate the utility and effectiveness of our method on a wide range of problems in industry, medicine, and entertainment.     

风电机组齿轮箱的多变量时间序列故障预警

针对风电机组故障预警中，原始动态时间规整（DTW）算法无法有效度量风电机组多变量时间序列数据之间距离的问题，提出一种基于犹豫模糊集的动态时间规整（HFS-DTW）算法。该算法是原始DTW算法的一种扩展算法，可对单变量和多变量时间序列数据进行距离度量，且精度与速度较原始DTW算法更优。以子时间序列相似度距离为目标函数，使用帝国竞争算法（ICA）优化了HFS-DTW算法中的子序列长度和步距参数。算例研究表明与仅DTW算法和非参数最优的HFS-DTW算法相对比，参数最优的HFS-DTW可挖掘更多的多维特征点信息，输出的多维特征点相似序列具有更丰富细节；且基于所提算法可提前10天预警风电机组齿轮箱故障。