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

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

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

DTW语音识别算法研究与分析

研究动态时间规整(Dynamic Time Warping)语音识别算法问题,传统动态时间规整方法需要存储较大的矩阵,直接计算将会占据较大的空间,计算量也比较大,对系统硬件要求比较高。为了减小DTW算法的运算量,提高识别速度,对DTW语音识别算法进行优化改进。将局部路径约束和整体路径约束相结合,仅在一个规定的宽度内搜索动态规划路径,计算累积匹配距离。仿真实验结果表明该方法不仅可以降低运算负载,提高识别速度,而且能在一定程度上提高语音识别率。     

基于DTW算法的旁路功耗信号动态伸缩对齐*

将动态时间规整(DTW)技术用于解决差分功耗分析(DPA)攻击中旁路信号的对齐问题。在分析DTW算法原理的基础上,得出旁路信号规整路径,给出依据规整路径对信号轨迹进行伸缩重组对齐的方法。对运行于微控制器(AT89C52)中的DES密码算法插入随机时延来模拟信号的未对齐,用该方式进行旁路攻击实验,结果表明,当各信号在相同操作时间点未对齐程度略有增加时,敌手直接进行DPA攻击破解算法密钥时所需的信号样本量将成倍增加,对信号进行动态伸缩对齐后实施DPA攻击,其所需样本量几乎不受信号未对齐程度的影响,实验验证了本方法的有效性。     

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

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

基于增量动态时间弯曲的时间序列相似性度量方法

针对动态时间弯曲方法计算时间过长的问题,提出增量动态时间弯曲来度量较长时间序列之间的相似性。首先利用动态时间弯曲方法对历史时间序列数据进行相似性度量,得到相应的历史最优弯曲路径和路径中各元素的累积距离代价。其次,通过逆向弯曲度量方法完成当前序列数据 的相似性度量,结合历史数据信息找到与历史弯曲路径相交且度量时间序列距离为当前最小值的新路径,进而实现增量动态时间弯曲的相似性度量。该方法不仅具有良好的度量质量,还具有较高的时间效率。数值实验表明,对于大部分时间序列数据集,新方法的分类准确率和计算性能要优于经典动态时间弯曲。     

一种环境音频数据分类方法

为了实现对环境音频信号及其相关数据的自动分析,提出了一种环境音频数据分类方法。分类过程中,首先用短时平均幅度对音频数据进行有效分段;然后,计算分段音频数据的长度和平均过零率;最后,计算并生成一个分段音频数据的Mel频率倒谱系数（MFCC）和一阶差分Mel频率倒谱系数（△MFCC）特征参数。分类操作上,根据有效分段的长度和平均过零率确定分类搜索的范围,并在局部范围内采用DTW（Dynamic Time Warping,动态时间规整）分类算法。实验结果验证了该方法对各种环境音频数据分类的有效性。     

基于控制点和RGB向量差联合梯度Census变换的立体匹配算法

为了解决立体匹配算法在弱纹理区域及边界区域匹配精度较低的问题,文中提出基于控制点和RGB向量差联合梯度Census变换的立体匹配算法.首先,使用基于动态时间归整的行匹配算法,寻找最优匹配路径,经过扭曲对齐选取匹配特征点作为控制点.再使用基于RGB向量差代价联合基于梯度Census变换代价作为非控制点的匹配代价,基于梯度...     

基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法

Wi-Fi网络中常规的基于指纹匹配室内定位算法面临信号时变现象或人为干扰的影响,导致定位精度不高。为此,提出基于动态时间规整（DTW）距离相似性指纹匹配的Wi-Fi网络室内定位算法。首先,该算法将定位区域的Wi-Fi信号特征按照采样的先后顺序转化为时间序列类型指纹,通过计算Wi-Fi信号指纹动态时间规整距离的大小来获取定位点与样本点的相似性;然后,根据采样区域结构特征,将Wi-Fi信号指纹采集问题划分为三类基本的动态路径采样方式;最后,结合多种动态路径采样方式增加指纹特征信息的准确性和完整性,从而提高指纹匹配的准确性和定位精度。大量实验结果表明,较瞬时指纹匹配定位算法,所提算法误差范围在3m以内定位的累积错误率：路径区域匀速运动提高了10%,变速运动提高了13%;开放区域交叉曲线运动提高了9%,S型曲线运动提高了3%。所提算法在实际室内定位应用中能有效提高指纹匹配的准确性和定位精度。     

改进DTW算法的心电信号相似性度量

针对时间序列相似性度量中动态时间规整（DTW）算法在序列时间轴偏移较大时易产生病态路径及匹配不准确的问题,根据心电信号自身的特性,提出一种基于心电信号最显著特征的优先匹配法。为减小算法时间复杂度,根据心电信号R波特征点位置自适应地划分弯曲路径的约束窗口。与传统算法比较,在提高准确率的同时,运行时间大幅降低。     

弹性粗粒度动态弯曲时序相似性算法

针对动态时间弯曲(DTW)算法在提高计算速度同时不能兼顾分类正确率的问题,提出了一种基于朴素粒计算思想的弹性粗粒度动态时间弯曲(CG-DTW)算法。首先,通过计算时序方差特征的方法来获取较优的时序粒度,用粒度特征代替原始序列;其次,再代入执行DTW算法,允许动态调整被比较时序粒间的弹性大小,从而获得相对最优的时序对应粒;最后,在对应最优粒的情况下计算DTW距离。同时引入下界函数的提前终止策略进一步提高CG-DTW算法效率。实验结果表明,所提算法要比经典算法运行速率提高21.4%左右,比降维策略算法正确率提高近32.3个百分点,尤其是长序列的分类,CG-DTW能够在保持正确率的情况下兼顾较高的运行效率。CG-DTW在实际应用中能适应不确定长序列分类。     

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

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

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

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

An empirical evaluation of kernels for time series

There exist a variety of distance measures which operate on time series kernels. The objective of this article is to compare those distance measures in a support vector machine setting. A support vector machine is a state-of-the-art classifier for static (non-time series) datasets and usually outperforms k-Nearest Neighbour, however it is often noted that that 1-NN DTW is a robust baseline for time-series classification. Through a collection of experiments we determine that the most effective distance measure is Dynamic Time Warping and the most effective classifier is kNN. However, a surprising result is that the pairing of kNN and DTW is not the most effective model. Instead we have discovered via experimentation that Dynamic Time Warping paired with the Gaussian Support Vector Machine is the most accurate time series classifier. Finally, with good reason we recommend a slightly inferior (in terms of accuracy) model Time Warp Edit Distance paired with the Gaussian Support Vector Machine as it has a better theoretical basis. We also discuss the reduction in computational cost achieved by using a Support Vector Machine, finding that the Negative Kernel paired with the Dynamic Time Warping distance produces the greatest reduction in computational cost.

     

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

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

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

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

Asymptotic Dynamic Time Warping calculation with utilizing value repetition

Dynamic Time Warping (DTW) is a popular method for measuring the similarity of time series. It is widely used in various domains. A major drawback of DTW is that it has a high computational complexity. To address this problem, pruning techniques to calculate the exact DTW distance, as well as DTW approximation methods, have become important approaches. In this paper, we introduce Blocked Dynamic Time Warping (BDTW), a new similarity measure which works on run-length encoded time series representation. BDTW utilizes any repetitive values (zero and nonzero) in time series to reduce DTW computation time. BDTW closely approximates DTW distance, and it is significantly faster than traditional DTW for time series with high levels of value repetition. Moreover, BDTW can be combined with time series representation methods which provide constant segments, to serve as a close approximation method even for the time series without value repetition. Constrained BDTW, BDTW upper bound and BDTW lower bound are discussed as variations of BDTW. BDTW upper bound and BDTW lower bound are presented as a new DTW upper bound and lower bound which can be efficiently applied on time series with high levels of value repetition for pruning unhopeful alignments and matches in the exact DTW calculation. We show the effectiveness of BDTW and its variations on different applications using the following datasets: Almanac of Minutely Power, Refit Smart Homes, as well as the 85 datasets from the University of California, Riverside time series classification archive (UCR archive).