改进的符号化时间序列处理方法

符号化聚集近似是一种有效的时间序列数据离散化降维方法,为了扩展非等维符号化时间序列相似性度量的解决方案,提出了一种新方法。首先将关键点提取技术应用在符号化算法中对时间序列进行降维处理,然后利用文中提出的方法对非等长的时间序列进行局部等维处理,再符号化;最后采用不同的方法进行相似度对比计算。实验结果表明,这种方法是简单而有效的,并且使非等长符号化时间序列的相似性度量及聚类方法得到了拓展。     

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

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

基于符号化聚合近似的时间序列相似性复合度量方法

基于关键点的符号化聚合近似(SAX)改进算法(KP_SAX)在SAX的基础上利用关键点对时间序列进行点距离度量,能更有效地计算时间序列的相似性,但对时间序列的模式信息体现不足,仍不能合理地度量时间序列的相似性。针对SAX与KP_SAX存在的缺陷,提出了一种基于SAX的时间序列相似性复合度量方法。综合了点距离和模式距离两种度量,先利用关键点将分段累积近似(PAA)法平均分段进一步细分成各个子分段;再用一个包含此两种距离信息的三元组表示每个子分段;最后利用定义的复合距离度量公式计算时间序列间的相似性,计算结果能更有效地反映时间序列间的差异。实验结果显示,改进方法的时间效率比KP_SAX算法仅降低了0.96%,而在时间序列区分度性能上优于KP_SAX算法和SAX算法。     

基于特征点分段的多元时间序列相似性搜索

现有的各种多元时间序列相似性搜索方法难以准确高效地完成搜索任务。提出了一种基于特征点分段的多元时间序列相似性搜索算法,提取所定义的用于分段的特征点,分段后将原时间序列转化为模式序列,该模式序列能够很好地保留原序列的全局形状特征,再用分层匹配的方法进行相似性搜索。实验结果表明,该方法能够有效刻画序列的全局形状特征,通过分层匹配保留局部的相似性,同时提高搜索准确率。     

基于滑动窗口及局部特征的时间序列符号化方法

针对时间序列的数据挖掘将时间序列数据转换为离散的符号序列, 提出了一种基于滑动窗口及局部特征的时间序列符号化方法。该方法采用了滑动窗口的方法将时间序列分割, 每个分段采用多个斜率表示, 最后采用K-均值聚类算法对斜率表示的分段进行聚类, 实现时间序列的符号化。实验证明了该方法的有效性与准确性。     

基于三角不等式的时间序列相似性搜索算法

由于传统的时序相似性度量方式不满足距离三角不等式关系,影响后续的相似性搜索及关联规则的获取,在时序符号化的基础上,提出一种满足三角不等式的符号化距离度量方式。与MINDIST_PAA_SAX和Sym_PAA_SAX度量方式进行比较,其结果表明,该度量方式在异常检测和相似性查询上具有较好的优越性。实验结果表明,该方法在相似性搜索及关联规则的获取方面具有更高的可信度。     

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

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

基于分段时间弯曲距离的时间序列挖掘

在时间序列库中的数据挖掘是个重要的课题,为了在挖掘的过程中比较序列的相似性,大量的研究都采用了欧氏距离度量或者其变形,但是欧氏距离及其变形对序列在时间轴上的偏移非常敏感．因此,采用了更鲁棒的动态时间弯曲距离,允许序列在时间轴上的弯曲,并且提出了一种新的序列分段方法,在此基础上定义了特征点分段时间弯曲距离．与经典时间弯曲距离相比,大大提高了效率,而且保证了近似的准确性．     

基于角点弯曲度的时间序列相似性搜索算法

针对基于点距离的时间序列相似性搜索算法鲁棒性较差的问题,提出一种面向形态的时间序列近似表示方法和相似性度量算法。算法不依赖于时间序列长度和领域知识。在充分利用时间序列时变特征的基础上,以角点为分界点,利用角点处的弯曲度提取时间序列的特征,近似表示时间序列。实验结果表明,该算法具有良好的平移和伸缩不变性及较好的鲁棒性,搜索能力更强。     

基于分层动态时间弯曲的序列相似性度量方法研究

为了更好地体现时间序列的形态特征,并探索更适合于较长时间序列之间相似性度量的方法,在动态时间弯曲算法的基础上进行改进,提出了基于分层动态时间弯曲的序列相似性度量方法。对时间序列进行多层次分段,并从分段中均匀抽取相对应的层次分段子序列,然后将层次分段子序列抽象为三维空间的点（反映了分段子序列的均值、长度和趋势）进行相似性度量,最后综合各个层次的相似性度量作为结果。实验表明,在参数设置合理的情况下,此方法能获得较高的序列相似性度量准确度和效率。     

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

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

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

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

结合形状特征及其上下文的多维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相似性度量

利用动态时间弯曲(DTW)技术在原始多元时间序列进行相似性度量时时间复杂度较高,且DTW在追求最小弯曲距离的过程中可能会出现过渡拉伸和压缩的问题.提出一种基于分段特征及自适应加权的DTW多元时间序列相似性度量方法.对原始时间序列在各个变量维度上进行统一分段,选取分段后拟合线段的斜率、分段区间的最大值和最小值以及时间跨度...     

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

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

基于分布式架构的时间序列局部相似检测算法

基于动态时间规整算法思想的CrossMatch算法可以用来解决序列间的部分相似问题,但是由于算法时间空间复杂度过高,需要消耗大量的计算资源,因此无法应用于长序列之间的计算。针对以上问题,提出了一个基于分布式平台上的时间序列局部相似性检测算法。将CrossMatch算法实现在了分布式框架上,解决了计算资源不足的问题。首先需要对序列进行切分,分别放置在不同的节点上;其次,各节点分别处理各自序列的相似部分;最后,通过对结果进行汇总并拼接,找出序列间的局部相似。实验结果表明,该算法在准确性上和CrossMatch相近,在时间上也有提升。改进后的分布式算法不仅解决了单机无法处理的长序列计算问题,而且可以通过增加并行计算节点数提高运行速度。     

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

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

基于LDTW的动态时间规整改进算法

限制对齐路径长度的动态时间规整（LDTW）算法存在时间复杂度高和计算量大的问题。基于LDTW算法提出固定对齐路径长度的动态时间规整（FDTW）算法。通过调整LDTW算法中对齐路径长度的控制策略,由控制在某个区间改为固定到某个具体值,相应缩减累计代价矩阵中元素的计算范围。在UCR时间序列数据集上的实验结果表明,FDTW与LDTW算法的分类准确率持平,但FDTW算法在分类过程中的时间开销更小,并且能有效降低累计代价矩阵元素的计算量,提高计算效率。     

时间序列周期模式挖掘的周期检测方法

周期是时间序列的重要特征之一,用于精确描述时间序列并预测其发展趋势。在现有周期模式挖掘算法中,周期长度由用户事先定义,忽略了噪声的存在。在ERP度量和时间弯曲算法的基础上,提出一种新的周期长度检测方法。该方法可以在时间轴上实现弯曲,包括延伸和平移。它受噪声干扰的影响较小,实验结果表明其性能优于原有周期检测算法。     

时间序列趋势相似性度量方法研究

为了进一步改善和提高基于模式的时间序列趋势相似性度量效果,在时间序列分段线性表示的基础上,依据分段子序列的均值及其线性拟合函数的导数符号,实现时间序列的分段模式化,以模式之间的异同性定义模式匹配距离,借鉴动态时间弯曲（Dynamic Time Warping,DTW）的动态规划原理,提出一种动态模式匹配方法（Dynamic Pattern Matching,DPM）。实验结果表明,该方法能够在不同压缩率条件下,准确度量等长时间序列的趋势相似性,而且时间消耗较低。时间序列不等长作为存在数据缺失的一种表现形式,该方法的度量效果与数据缺失比例之间的关系值得进一步的深入研究。