噪声鲁棒的动态时间规整算法

动态时间规整（DTW）算法通过寻找两个时间序列的最佳匹配衡量序列之间的相似性。针对序列中存在的噪声容易导致时间序列匹配时局部出现过度拉伸和压缩问题,提出了一种噪声鲁棒的动态时间规整（NoiseDTW）算法。首先,在原始的信号中引入额外噪声,解决序列对齐中存在的一个点对齐多个点的问题;然后,通过在两个时间序列之间多条可能的匹配路径中找到一条最优的匹配路径,减少噪声的随机性对时间序列相似性度量的影响;最后,将匹配路径映射到原始序列上。实验结果表明,相较于欧氏距离（ED）、DTW、Sakoe-Chiba窗口动态时间规整（Sakoe-Chiba DTW）和加权动态时间规整（WDTW）算法,所提算法结合K-近邻（KNN）分类器得到的分类准确率在8个时间序列数据集上分别比次优算法提高了1～15个百分点。可见所提算法具有较好的分类性能,且对噪声具有鲁棒性。     

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

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

结合形状特征及其上下文的多维DTW

传统动态时间规整算法（Dynamic Time Warping,DTW）及其变种算法被广泛应用于多维时间序列的相似性分析,但它们通常只关注单个时间点的信息而忽略了上下文信息,从而很可能匹配两个形状完全不同的点。因此提出一种结合形状特征及其上下文的多维DTW算法（Multi-Dimensional Contextual Dynamic Time Warping,MDC-DTW）。该算法首先计算多维时间序列的一阶梯度,然后对其进行采样处理,并以多维梯度矩阵表示当前时间点的形状信息及其上下文信息,最后利用DTW求解多维时间序列间的最短匹配路径。为检测算法设计的合理性,对算法进行了定性分析和定量分析,实验结果表明MDC-DTW算法设计是合理的;为检测MDC-DTW的性能,选用5个多维时间序列数据集,并与4个优异的多维DTW算法进行对比实验,实验结果表明MDC-DTW具有较高的准确率和运行效率。     

基于门控递归神经网络的电网日峰值负荷预测

日峰值负荷作为非线性、非平稳且波动的时间序列,难以准确预测。提出了一种结合动态时间规整（DTW）的门控递归神经网络（GRNN）用于准确预测日峰值负荷。利用DTW距离用于匹配最相似的负荷曲线,可以捕捉负荷变化趋势。采用热编码方案对离散变量进行编码,扩展其特征从而表征对负荷曲线的影响。提出了一种基于DTW的门控递归单元（DTW-GRU）算法用于日峰值负荷预测,并在欧洲智能技术网络（EUNITE）数据集上进行了测试。仿真结果表明,与其他算法相比,该算法的MAPE仅为1.01%。     

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

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

基于DLT-Kmedoids算法的用电负荷聚类分析

针对高校用电负荷中传统聚类算法直接应用于时间序列聚类效果准确性较低的问题,提出一种融合DTW距离、LB＿Keogh距离以及时间窗口的DLT-Kmedoids算法,以提高聚类算法应用于时间序列的准确性以及算法效率。DLT-Kmedoids算法使用DTW计算时序数据之间的距离取代传统的欧氏距离度量方式,提高了相似性度量算法精度,同时也提高了聚类算法的准确性和复杂度,引入LB＿Keogh距离在计算DTW距离之前过滤掉大部分不可能是最优匹配序列的序列,对于剩下的序列再使用DTW逐个比较,进一步降低算法的复杂度。最后结合高校建筑用电负荷时间序列数据进行分析,通过与主流聚类算法进行比较,表明该算法对于高校用电负荷数据的聚类任务,能够更准确地识别相似的负荷模式,并以更高的效率进行聚类分析。     

基于时间加权改进的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相似度量的分类准确率优于其他对比算法,且进一步对比验证了其可靠性。     

基于MDTW的飞行动作识别算法

科学评估飞行训练质量,对提高飞行员的飞行驾驶技术以及保障飞行安全具有重要意义。动作识别是飞行评估的一项基本内容,许多评估内容都是建立在获取动作序列的基础上的。在动态时间规整（DTW）的基础上提出了一种多元动态时间规整算法（MDTW）,通过多维融合的方法进行多元时间序列相似性运算。经实际应用验证,该算法有效提升了传统DTW动作识别的效率和准确性。     

基于自适应搜索窗口的序列相似比对算法

DTW（Dynamic Time Warping）算法被广泛应用于序列数据比对,以度量序列间距离,但算法较高的时间复杂度限制了其在长序列比对上的应用。提出基于自适应搜索窗口的序列相似比对算法（ADTW）,算法利用分段聚集平均（Piecewise Aggregate Approximation,PAA）策略进行序列抽样得到低精度序列,然后计算低精度序列下的比对路径,并根据低精度距离矩阵上的梯度变化预测路径偏差,限制路径搜索窗口的拓展范围;随后算法逐步提高序列精度,并在搜索窗口内修正路径、计算新的搜索窗口,最终,实现DTW距离和相似比对路径的快速求解。对比FastDTW,ADTW算法在同等度量准确率下提高计算效率约20%,其时间复杂度为[O(n)]。     

基于孪生神经网络的时间序列相似性度量

在时间序列分类等数据挖掘工作中，不同数据集基于类别的相似性表现有明显不同，因此一个合理有效的相似性度量对数据挖掘非常关键。传统的欧氏距离、余弦距离和动态时间弯曲等方法仅针对数据自身进行相似度公式计算，忽略了不同数据集所包含的知识标注对于相似性度量的影响。为了解决这一问题，提出基于孪生神经网络（SNN）的时间序列相似性度量学习方法。该方法从样例标签的监督信息中学习数据之间的邻域关系，建立时间序列之间的高效距离度量。在UCR提供的时间序列数据集上进行的相似性度量和验证性分类实验的结果表明，与ED/DTW-1NN相比SNN在分类质量总体上有明显的提升。虽然基于动态时间弯曲（DTW）的1近邻（1NN）分类方法在部分数据上表现优于基于SNN的1NN分类方法，但在分类过程的相似度计算复杂度和速度上SNN优于DTW。可见所提方法能明显提高分类数据集相似性的度量效率，在高维、复杂的时间序列的数据分类上有不错的表现。     

Weighted dynamic time warping for time series classification

Dynamic time warping (DTW), which finds the minimum path by providing non-linear alignments between two time series, has been widely used as a distance measure for time series classification and clustering. However, DTW does not account for the relative importance regarding the phase difference between a reference point and a testing point. This may lead to misclassification especially in applications where the shape similarity between two sequences is a major consideration for an accurate recognition. Therefore, we propose a novel distance measure, called a weighted DTW (WDTW), which is a penalty-based DTW. Our approach penalizes points with higher phase difference between a reference point and a testing point in order to prevent minimum distance distortion caused by outliers. The rationale underlying the proposed distance measure is demonstrated with some illustrative examples. A new weight function, called the modified logistic weight function (MLWF), is also proposed to systematically assign weights as a function of the phase difference between a reference point and a testing point. By applying different weights to adjacent points, the proposed algorithm can enhance the detection of similarity between two time series. We show that some popular distance measures such as DTW and Euclidean distance are special cases of our proposed WDTW measure. We extend the proposed idea to other variants of DTW such as derivative dynamic time warping (DDTW) and propose the weighted version of DDTW. We have compared the performances of our proposed procedures with other popular approaches using public data sets available through the UCR Time Series Data Mining Archive for both time series classification and clustering problems. The experimental results indicate that the proposed approaches can achieve improved accuracy for time series classification and clustering problems.     

一种支持DTW距离的多元时间序列索引结构

现有的索引结构难以有效地支持DTW距离度量下的多元时间序列相似性搜索.首先给出一种将不等长多元时间序列转换为等长一元时间序列的方法,并证明这种转换满足下界距离引理;以此为基础,提出一种多元时间序列的DTW下界距离,并对其性质进行分析;然后,针对给出的下界距离,提出一种支持DTW距离度量的多元时间序列索引结构,对多元时间序列数据库进行有效组织;再给出多元时间序列相似模式搜索算法及流程,并证明该搜索方法具有非漏报性;最后,通过实验对所提方法的有效性进行验证.     

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

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

一种基于DTW聚类的水文时间序列相似性挖掘方法

水文时间序列相似性挖掘是水文时间序列挖掘的重要方面,对洪水预报、防洪调度等具有重要意义。针对水文数据的特点,提出了一种基于DTW聚类的水文时间序列相似性挖掘方法。该方法先对数据进行小波去噪、特征点分段以及语义划分,再基于DTW距离对划分后的子序列做层次聚类并符号化;然后根据符号序列间的编辑距离筛选候选集;最后通过序列间的DTW距离进行精确匹配,获取相似水文时间序列。以滁河六合站的日水位数据进行实验,结果表明,所提方法能够有效地缩小候选集,提高查找语义相似的水文时间序列的效率。     

基于动态时间弯曲的时序数据聚类算法的研究

时间序列是一类重要的复杂类型数据，时间序列知识发现正成为知识发现的研究热点之一。欧几里的距离及其扩展作为相似测度被广泛应用于时间序列的比较中，但是这种距离测度对数据没有好的鲁棒性。动态时间弯曲技术是基于非线性动态编程的一种模式匹配算法。该文提出了基于动态时间弯曲技术的相似搜索算法，通过计算时序数据之间的最短弯曲路径来获得序列的匹配。对综合控制时序数据进行基于不同距离测度的聚类分析对比结果表明该文提出的算法有很高的精度和对振幅差异、噪声和线性漂移有强的鲁棒性，具有良好的应用价值。     

基于关节角度和DTW的太极拳视频配准方法

太极拳视频配准是实现太极拳线上教学的首要问题。为实现太极拳视频的自动配准,提出了一种基于关节角度和DTW算法的太极拳视频配准方法。该方法主要利用人体关节角度消除太极拳视频背景的干扰和不同太极拳视频中人体大小不同的影响,并利用动态时间规整(DTW)算法对不同时间点的视频帧进行配准。在该方法中,首先计算出练习者动作视频中关节角度的时间序列,并使用指数平滑法消除时间序列中存在的误差;然后利用上下帧之间的人体关节角度差分割时间序列;最后利用DTW算法求分割后得到的时间序列与标准动作视频中对应的时间序列之间的距离,即可得到练习者与标准动作之间的匹配度。实验结果表明:该方法中的指数平滑法对太极拳视频配准的精度有较大影响,以及如果用欧几里得距离替换DTW算法将会较大的降低配准精度。并且该方法在太极拳视频配准上与基于SIFT特征的方法相比,配准精度更高,达到81.21%。