采用分段特征表示的异常序列检测算法

时间序列的有监督异常检测方法通常依赖于数据的标签，不仅会消耗大量时间进行数据标注，而且难以适用于无法给定标签的数据集。为解决异常序列检测中的标注问题，提出一种采用分段特征表示的异常序列检测方法。该方法采用分段聚合思想对时间序列进行标准化计算，并得到时序数据的特征表示，可提高无标签时间序列异常检测的可靠性。将表示后的特征划分为异常序列相关特征和无关特征，剪枝异常序列无关特征，可减少这些特征对检测结果的不利影响。为有效量化不同序列之间的差异性，提出一种面向时间权重分析的时间序列相似性度量方法，并构建时间序列的相似度矩阵，用于计算序列之间的相似度，可适用于无标签的时间序列中。在此基础上，根据相似度矩阵来计算每个子序列的异常分数，将其用于异常子序列的判定。通过合成数据集和真实数据集的实验对比表明：该方法节省了计算开销，提高了算法运行的时间效率和异常序列检测的准确率。     

基于线性形态的时间序列异常模式挖掘

对于子序列长度相等的时间序列数据，文章提出了一种基于序列偏离度的异常模式发现方法。与传统的基于某一特定模型的方法不同，该方法首先对子序列进行线性分段，对每一分段计算其斜率，并将斜率进行离散化，离散化后的符号构成的特征序列就代表了原时间子序列的变化趋势，在此基础上，序列偏离度被定义和计算。这种方法不需预先定义模型，同时避免了通过序列间的两两比较来查找异常所带来的时间消耗。     

时间序列中快速模式发现算法的研究

针对长时间序列,该文提出了一种新的能快速发现序列中时序模式的检索方法。首先将时间序列分成若干等长的子序列;接着从每个子序列中提取特征序列,该特征序列能够反映子序列中数据的变化趋势;然后根据每个特征序列将相应的子序列分配到一系列盒子中,使得不同盒子中的子序列因数据变化趋势不同而不相似,而在同一盒子中的序列由于数据变化趋势相同而有可能相似;最后通过计算每个盒子中任意两个子序列间的欧几里德距离来发现所有的模式。有关实验证明该算法是行之有效的。     

基于序变换的时间序列快速匹配搜索方法

分析了时间序列相似匹配搜索的研究现状,提出了基于序变换的时间序列相似匹配搜索方法。该方法能够实现趋势相似的不同长度子序列的快速匹配搜索,同时具有对匹配序列的平移、时间轴的伸缩不敏感、误警率低,以及易于建立索引等优点。实验结果证明了该方法的有效性。     

MapReduce并行加速数据流多模式相似性搜索

设计时间序列数据在Hadoop分布式文件系统（HDFS）中的有效存储方式,利用分布式缓存工具Distributed Cache将各子序列分发到Hadoop集群的计算节点上,将动态时间弯曲距离矩阵划分成多个子矩阵,采取并行迭代计算每条反对角线上子矩阵的方法,基于MapReduce编程模型,实现高效并行计算时间序列动态弯曲距离,通过改进剪裁冗余计算方法,设计实现一种数据流多模式相似性搜索并行算法。中国雪深长时间序列数据集的实验结果表明,当每条时间序列的长度达到5000以上时,并行计算动态弯曲距离所需时间少于串行计算所需时间,当每条时间序列的长度达到9000以上时,参与计算的集群节点越多,并行计算所需时间越少;当模式长度达到4000、参与计算的集群节点数达5个以上时,从数据流中并行搜索出与模式匹配的相似子序列所需时间约为串行搜索所需时间的20%。     

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

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

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

基于形状特征k-d树的多维时间序列相似搜索

多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.     

基于边缘算子的有效子序列分割方法

在深入分析时间序列中边缘算子的特点后,以划分不等长子、具有相对完整变化趋势的时间序列为目的,提出基于边缘算子的有效子序列分割方法。该方法能有效分割出具有相对完整变化趋势的、不同长度的子序列,同时具有高效、实现方法简便、效果直观的优点,对于不同领域的数据适应性良好。     

时间序列的模糊匹配方法

一个时间序列可以定义为一系列的数值,每一个数值代表一个时间点的值。在数据库和数据仓库应用中,时间序列数据是一类非常重要的数据类型。时间序列的相似性的判定,有基于欧几里得距离的判定方法和包络线方法。欧几里得距离方法对序列中的噪声很敏感,而且欧几里得距离随着序列长度的增加而变大。Rakesh Agrawal等所提出的方法,是将匹配的子序列按顺序连接来判定两个序列的相似性,如果一个子序列落入另一个子序列的包络线区间内(如图1),那么认为这两个于序列是匹配的,例外的数据被忽略,该方法的本质是在两个序列中包含一定比率的相匹配的子序列。该方法避免了欧几里得距离的缺点,任意长度序列的相似性的判定使用统一的标准。但是相似性的判定在包络线边界处发生了突变。     

基于序列分解的复杂系统的时序预测方法

现实中的时序数据，往往取自于复杂系统，表现出长记忆效应与短时不规则波动同时并存。传统的时序数据的分析和预测方法一般对不同层次的影响不加以区分，而是为其建立一个统一的模型，这使得在对复杂系统建模时需要用大量的参数予以表征，影响预测效率与精度。为此采用新的方法，将序列数据本身进行多平滑因子分解，对分解后的序列进行多尺度的采样并分别建模、预测，最后将结果整合。该方法应用于股票的实验表明，即使对起伏波动很大的时间序列，也能够得到较好的预测结果。     

基于Hadoop的水文时间序列相似性研究与应用

传统DTW算法复杂度高,特别当处理海量数据时,耗时长.为了从算法和实现手段两方面同时入手,提高DTW运算效率,提出基于Hadoop平台,以FastDTW方法实现的水文时间序列相似性查找方法.首先利用小波变换对数据去噪,接着对水文时间序列进行语义化,然后在Hadoop的MapReduce过程中调用FastDTW方法实现DTW距离的云计算,得出与查询序列最相似的匹配序列.通过实验与串行查找进行对比,验证该方法用时短,匹配效果好,能够满足实际应用需求.     

Pattern‐Similarity‐Based Model for Time Series Prediction

This research proposes a pattern/shape‐similarity‐based clustering approach for time series prediction. This article uses single hidden Markov model (HMM) for clustering and combines it with soft computing techniques (fuzzy inference system/artificial neural network) for the prediction of time series. Instead of using distance function as an index of similarity, here shape/pattern of the sequence is used as the similarity index for clustering, which overcomes few of the shortcomings associated with distance‐based clustering approaches. Underlying hidden properties of time series are captured with the help of HMM. The prediction method used here exploits the pattern identification prowess of the HMM for cluster selection and the generalization and nonlinear modeling capabilities of soft computing methods to predict the output of the system. To see the validity of the proposed method in the real‐life scenario, it is tested on four different time series. The first is a benchmark Mackey–Glass time series, which is tested for delay parameters τ = 17 and τ = 30. The remaining time series are monthly sunspot data time series, Laser data time series and the last is Lorenz attractor time series. Simulation results show that the proposed method provide a better prediction performance in comparison with the existing methods.     

时间序列的表示与分类算法综述

时间序列是按照时间排序的一组随机变量,它通常是在相等间隔的时间段内,依照给定的采样率,对某种潜在过程进行观测的结果。时间序列数据广泛地存在于商业、农业、气象、生物科学以及生态学等诸多领域,从时间序列中发现有用的知识已成为数据挖掘领域的研究热点之一。在时间序列表示方面,主要介绍了非数据适应性表示方法、数据适应性表示方法和基于模型的表示方法;针对时间序列的分类方法,着重介绍了基于时域相似性、形状相似性和变化相似性的分类算法,并对未来的研究方向进行了进一步的展望。     

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

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

一种多元台风时间序列的相似性度量方法

台风相似性度量方法的研究对防灾减灾、辅助决策等具有重要意义。目前,台风相似性的研究大多集中在台风路径的相似性度量上。首先,梳理影响台风相似性度量的多个要素,提出了基于多元时间序列的台风数据描述方法;其次,提出了台风时间序列完整性、一致性评估与修复方法;最后,针对台风时间序列的不等长问题,设计了一种基于主成分分析和动态时间弯曲距离的相似性度量方法。通过实验验证,该方法能够实现台风相似性的有效度量。     

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

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

一种基于关键点的时间序列聚类算法

隐私保护数据挖掘是在不精确访问原始数据的基础上,挖掘出准确的规则和知识。针对分布式环境下聚类挖掘算法的隐私保护问题,提出了一种基于完全同态加密的分布式聚类挖掘算法(FHE-DK-MEANS算法)。理论分析和实验结果表明,FHE-DK-MEANS算法不仅具有很好的数据隐私性,而且保持了聚类精度。