共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
一种有效的时间序列维数约简方法 总被引:2,自引:0,他引:2
提出了一种用于相似性查询的时间序列维数约简的有效方法,该方法采用快速小波变换将时间序列分解成不同频率的子带,用经过多分辨分解后得到的低频逼近信号重新表示原始序列,这样将一个高维的时间序列映射到一个低维空间,这种方法支持欧几理德距离标准和L-平移欧几理德距离标准,该算法的时间复杂性为O(n)。 相似文献
3.
4.
序列数据在文本、Web访问日志文件、生物数据库中普遍存在,对其进行相似性查找是一种重要的获取和分析知识的手段.基于参考集索引技术是一类解决序列相似性查找的有效方法,主要思想是找到序列数据库中的少数序列作为参考集,通过参考集过滤掉数据库中与查询序列不相关的数据,从而高效地回答查询.在现有基于参考集索引技术的基础上,提出一种过滤能力更强的序列相似性查询算法IRI(improved reference indexing).首先,充分利用了先前的查询结果集来加速当前的查询,其次考虑了基于序列特征的上界和下界,使得应用参考集进行过滤的上下界更紧,过滤能力进一步加强.最后,为了避免候选集中费时的编辑距离计算,则只计算前缀序列间的编辑距离,从而进一步加速算法运行.实验采用真实的DNA序列和蛋白质序列数据,结果表明,算法IRI在查询性能上明显优于现有的基于参考集索引方法RI(reference indexing). 相似文献
5.
一种有效的的时间序列维数约简方法 总被引:3,自引:0,他引:3
提出了一种用于相似性查询的时间序列维数约简的有效方法 .该方法采用快速小波变换将时间序列分解成不同频率的子带 ,用经过多分辨分解后得到的低频逼近信号重新表示原始序列 .这样将一个高维的时间序列映射到一个低维空间 .这种方法支持欧几理德距离标准和 L -平移欧几理德距离标准 .该算法的时间复杂性为 O(n) . 相似文献
6.
在时间序列相似性研究领域已经发展了多种方法用于时间序列的表示,以达到降低序列维度的目的.作为一种经典的时域-频域转换方法,离散余弦变换目前已经在图形图像处理等领域得到了广泛的应用.将此方法应用于时间序列的表示上,在变换后的数据上进行相似性查询等操作.实验表明,相对以前的方法,这种方法具有明显的性能提升. 相似文献
7.
在时间序列相似性问题中滑动窗口的确定 总被引:1,自引:0,他引:1
作为一个非平凡命题,大多数时间序列相似性查找方法都涉及到了对原数据的维度简约.在保持原序列中有效信息量的同时,尽量降低计算复杂度是这些算法的关键.讨论滑动窗口在时间序列相似性降维技术中的实际应用,从中发现确定自适应滑动窗口大小的一种新方法.通过对时序特征值分布函数的挖掘,发现时间序列中的若干有效点,从而确定一组合适的滑动窗口大小,并根据序列变化的来决定最佳的滑动窗口. 相似文献
8.
时间序列相似性查找作为一种非平凡问题,大多数有效的求解方法都涉及到对原数据维度的简约。在有效地保持原序列中信息量的前提下,尽可能降低计算复杂度是算法的关键所在。通过讨论滑动窗口在时间序列相似性降维算法中的实际应用情况,从中发现一种自适应确定滑动窗口宽度的新方法。通过对时序特征值分布函数挖掘,发现时间序列中的有效特征点,进而确定一组合适的滑动窗口宽度;最后根据序列的变化情况来决定最优的滑动窗口宽度,对原数据维度进行简约。 相似文献
9.
10.
面向相似性搜索的时间序列表示方法述评 总被引:6,自引:0,他引:6
时间序列作为一种数据形式,广泛存在于各种商业、医学、工程、自然科学和社会科学等数据库中。近年来,时间序列的相似性搜索问题正得到越来越多的重视。该问题可描述为给定某个的时间序列,要求从一个大型时间序列数据库中找出与之最相似的序列。该问题的有效求解涉及到两个关键难点,即相似性度量的定义和搜索算法的时间复杂度,而这两者都依赖于时间序列的近似表示方法。因此,通过详细评述面向相似性搜索的各种时间序列近似表示方法,对这些方法进行分析和比较,总结了这些方法的优点和不足,并对进一步的研究方向作出了预测。 相似文献
11.
12.
该文提出了一种基于二进制压缩(BC)的时间序列相似搜索的方法。该方法是把时间序列分段,提取每段上面的关键点把这些点转换成一个比特流,这些关键点是把每一段分成子段取这些子段的中间点,记录下比特流达到压缩的目的。该文证明了该方法在理论上具备非漏报的性质。然后使用天际线对时间序列进行索引。实验表明,该文提出的基于BC的方法比PAA方法有更小的边界,在相似度搜索的时候基于天际线索引的BC方法比基于R*树的PPA方法更有效率。 相似文献
13.
大规模时间序列数据库降维及相似搜索 总被引:4,自引:0,他引:4
提出一种基于分段多项式表示(PPR)的时间序列数据库相似查询的系统化方法.PPR是一类基于线性多项式回归的正交变换.用PPR变换索引时间序列数据在理论上具备非漏报性质.文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标.与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率. 相似文献
14.
Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases 总被引:36,自引:3,他引:33
Eamonn Keogh Kaushik Chakrabarti Michael Pazzani Sharad Mehrotra 《Knowledge and Information Systems》2001,3(3):263-286
The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial
problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality
reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction
techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently
the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise
Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority.
In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is
simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and
the index can be built in linear time.
Received 16 May 2000 / Revised 18 December 2000 / Accepted in revised form 2 January 2001 相似文献
15.
16.
针对时间序列相似性度量中欧氏距离对异常数据敏感以及DTW距离算法效率低的问题,提出基于滑动平均与分段线性回归的时间序列相似性方法。首先,使用初始可变滑动平均算法以及分段线性回归对原始时间序列进行数据变换,并将分段线性回归的参数(截距与距离)集作为时间序列的特征,以实现时间序列的特征提取和数据降维;然后,利用动态时间弯曲距离进行距离计算。该方法在时间序列相似性上与DTW算法的性能相近,但是在算法效率上几乎提高了96%。实验结果验证了该方法的有效性与准确性。 相似文献
17.
18.
19.