基于异时间窗划分的时间序列聚类

针对相同时间窗对时间序列进行子序列划分的缺点,提出一种异时间窗的子序列划分方法。为解决划分得到的子序列长度不同,而使用动态时间弯曲算法进行子序列相似性度量的计算速度慢的问题,给出一种不规则时间序列距离度量算法。对异时间窗的子序列划分方法和不规则时间序列距离度量算法进行了实验,结果证明了二者的优越性。     

基于数学形态学的时间序列相似性度量研究

时间序列相似性度量在挖掘时间序列模式,提取时间序列关联关系上发挥着重要作用。分析了当前主流的时间序列相似性度量算法,分别指出了各度量算法在度量时序数据相似性时存在的缺陷,并提出了基于数学形态学的时间序列相似性度量算法。通过将归一化的时间序列二值图像化表示,再引入了图像处理领域中的膨胀、腐蚀操作对时序数据进行形态变换分析,提高相似时序数据部分的抗噪性,同时又不降低时序数据非相似部分间的差异度,实现时序数据相似性度量分类精度的提高。在八种时间序列测试数据集合上进行分类实验,实验结果表明提出的基于数学形态学的时间序列相似性度量算法在时间序列分类精度上得到有效改善,相比于DTW相似性度量算法,分类精度平均水平提升了8.74%,最高提升20%。     

时间序列序列模式的相似性研究

时间序列序列模式相似性的度量是从时间序列中获取时序关联规则的重要环节。一般情况下,距离度量法只能度量相同长度序列模式的相似性。借用动态时间弯曲距离的思想,这种基于非线性弯曲技术的算法可以获得很高的识别、匹配精度。在定义元模式相似性的基础上,定义了序列模式的动态时间弯曲距离,最后用两个不同时间序列进行仿真实验,可以得到不同长度的序列的相似度。     

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

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

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

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

交通流时间序列模式相似性度量法

针对交通流时间序列具有高维、高噪声的特性,设计了基于趋势变动、拟合优度和最小距离和百分比原则的联机分割算法用于时间序列维约简。对分割后的时间序列进行5元组分段线性表示,并据此定义五种常见的时间序列形状相似性距离。使用分层聚类算法分析它们在不同的交通流状态辨识中的效果,以此确定交通流时间序列的模式相似性度量方法。以上海南北高架东侧间部分路段固定线圈检测数据为例进行了实证分析,最终确定模式距离与欧氏距离组合方式为交通时序模式相似性度量的最佳方法。     

不同粒度时间序列相似性度量

现有的时间序列的相似性度量大多基于欧氏距离,并不适用于不同粒度时间序列的相似性匹配,无法直接对其相似性进行有效的度量,为此,提出一种基于对应差值比样本的相似性度量,用于不同粒度时间序列的相似性匹配.首先对不同时间粒度的时序数据进行阐述,并定义了对应差值比样本与相似度计算方法;接着提出基于它们的相似性匹配算法;最后实验证...     

面向相似性查询的时间序列距离度量方法述评

从一元时间序列和多元时间序列两个方面对当前提出的主要时间序列距离度量方法进行了述评.深入分析了各种算法的原理和特点,比较了算法对时间序列形变的支持情况以及时间复杂度.从客观上讲,各种算法之间并不具有绝对的优劣关系,每种算法的原理和特点各异,适用的问题领域也不一样.对于工程应用中选择时间序列距离度量方法具有指导意义,同时对于设计新的距离度量方法也具有参考价值.     

数字趋势序列及其全序列匹配算法研究

针对基于点距离的时序数据分析和传统趋势序列分析的缺点,提出了数字趋势序列、序列的Lp距离、序列分段向量等概念,证明了包括“序列分段均值定理”在内的3个重要定理,设计了专门用于数字趋势序列的“基于序列分段向量（SSV）的全序列匹配算法”。算法使用片段斜率所对应的弧度值来度量片段的趋势,同时用趋势的保持时间来对趋势值进行加权,实现了数字趋势序列之间快速的全序列相似性搜索。     

基于二分迭代SAX的时序相似性度量算法

时序降维是解决时间序列高维问题的关键技术。符号聚集近似表示(SAX表示法)作为一种时序降维技术,具有良好的维度约简能力与性能稳定的下界距离算法,但算法中分段数的选取需根据当前时序数据的特征而人为设定。针对这一问题,引入了滑动窗口算法与统计学方法,提出了基于二分迭代SAX的时序相似性度量算法。实验结果表明,该算法不仅解决了分段数设定困难的问题,而且降低了时序降维表示的复杂度,提高了SAX算法在多种时序数据上的分类准确性。     

基于RSSI测距的DV-Hop算法

由于DV-Hop算法在不均匀网络中节点定位精度不高,以及RSSI算法受环境因素影响较大,将RSSI算法与DV-Hop算法相结合,提出一种利用RSSI测距技术改进DV-Hop的算法-----BRDV-Hop算法.该算法应用RSSI测距技术,定义信标节点的平均跳距误差,并利用信标节点的平均跳距误差对未知节点与信标节点之间的距离进行修正,从而达到减小定位误差的目的.仿真结果表明,与标准的DV-Hop算法相比,在不增加传感器节点硬件的基础上,改进算法能有效降低定位误差.     

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

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

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

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

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.     

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

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

基于平均跳距估计的改进DV-Hop定位算法

传统DV—Hop定位算法只考虑了最近一个锚节点估计的平均每跳距离,而单个锚节点估计的平均每跳距离值无法准确地反映网络的实际平均跳距,导致定位误差较大。针对这一问题,提出一种基于平均跳距估计的改进DV—Hop定位算法。改进算法在计算未知节点到各个锚节点距离时,考虑到离该未知节点最近的锚节点到其它锚节点的距离及跳数的不同,计算出不同的平均跳距,使其更接近于实际平均跳距。仿真结果表明,与传统DV—Hop算法相比,改进算法在不需要增加节点的硬件开销的基础上能更有效地提高定位精度,并且算法简单,计算量小,是无线传感器网络中节点定位的一种实用方案。     

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

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

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

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