基于函数的时间序列分段线性表示方法

考虑到时间序列的时间特性对不同区段的影响以及时间序列数据动态增长的实际情况,在RPAA ( Reversed Piecewise Aggregate Approximation)和PAA(Piecewise Aggregate Approximation)方法的基础上,提出了一种新的时间序列分段线性表示方法FPAA(Founction Piecewise Aggregate Approximation)。FPAA方法通过定义函数影响因子,克服了RPAA和PAA方法的不足。该方法具有线性时间复杂度,满足下界定理,并且支持时间序列的在线划分。实验表明,与PAA方法和RPAA方法相比,所提出的方法可以较有效地进行时间序列的在线查询。     

RPAA：一种基于时间特性的时间序列建模表示

滑动聚集平均近似PAA（Piecewise Aggregate Approximation）是一种表示时间序列的方法，它通过时间序列上滑动一个等宽的滑动窗口将时间序列分成小的区段。考虑到时间序列的时间特性q-不同区段的影响，本文提出了一种改进表示RPAA（Reversed Piecewise Aggregate Approximation）。RPAA表示对处于不同时间段的序列赋以不同的影响因子，具有线性时间复杂度，并且证明了RPAA满足下界定理，因而能够进行实际的查询。最后的实验表明该表示是有效的。     

高效的时间序列下界技术

针对时间序列数据,提出一种新的基于动态时间弯曲的下界技术,该技术首先基于分段聚集近似的线性表示对原始序列进行降维,同时生成查询序列的网格最小边界矩形近似表示,然后利用基于动态时间弯曲距离对两者下界距离度量。实验结果表明,该下界技术与以往相关技术相比,能够产生更大的下界距离,具有更强的紧凑度、裁剪搜索空间能力以及更短的运行时间,有利于时间序列数据挖掘。     

大规模时间序列数据库降维及相似搜索

提出一种基于分段多项式表示（PPR）的时间序列数据库相似查询的系统化方法．PPR是一类基于线性多项式回归的正交变换．用PPR变换索引时间序列数据在理论上具备非漏报性质．文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标．与基于离散傅立叶变换（DFT）和离散小波变换（DWT）的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率．     

基于符号化表示的时间序列频繁子序列挖掘

提出一种新的基于符号化表示的时间序列频繁子序列的挖掘算法。利用基于PAA的分段线性表示法进行降维,通过在高斯分布下设置断点,实现时间序列符号化表示,利用投影数据库挖掘频繁子序列。该算法简单、新颖,运行快速,简化了子序列支持数的计算。     

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

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

SubSpace Projection: A unified framework for a class of partition-based dimension reduction techniques

Similarity search in high dimensional space is a nontrivial problem due to the so-called curse of dimensionality. Recent techniques such as Piecewise Aggregate Approximation (PAA), Segmented Means (SMEAN) and Mean-Standard deviation (MS) prove to be very effective in reducing data dimensionality by partitioning dimensions into subsets and extracting aggregate values from each dimension subset. These partition-based techniques have many advantages including very efficient multi-phased approximation while being simple to implement. They, however, are not adaptive to the different characteristics of data in diverse applications.We propose SubSpace Projection (SSP) as a unified framework for these partition-based techniques. SSP projects data onto subspaces and computes a fixed number of salient features with respect to a reference vector. A study of the relationships between query selectivity and the corresponding space partitioning schemes uncovers indicators that can be used to predict the performance of the partitioning configuration. Accordingly, we design a greedy algorithm to efficiently determine a good partitioning of the data dimensions. The results of our extensive experiments indicate that the proposed method consistently outperforms state-of-the-art techniques.     

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

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

An on-line SAX and HMM-based anomaly detection and visualization tool for early disturbance discovery in a dynamic industrial process

In order to achieve an optimum and successful operation of an industrial process, it is important firstly to detect upsets, equipment malfunctions or other abnormal events as early as possible and secondly to identify and remove the cause of those events. Univariate and multivariate statistical process control methods have been widely applied in process industries for early fault detection and localization.The primary objective of the proposed research is the design of an anomaly detection and visualization tool that is able to present to the shift operator – and to the various levels of plant operation and company management – an early, global, accurate and consolidated presentation of the operation of major subgroups or of the whole plant, aided by a graphical form.Piecewise Aggregate Approximation (PAA) and Symbolic Aggregate Approximation (SAX) are considered as two of the most popular representations for time series data mining, including clustering, classification, pattern discovery and visualization in time series datasets. However SAX is preferred since it is able to transform a time series into a set of discrete symbols, e.g. into alphabet letters, being thus far more appropriate for a graphical representation of the corresponding information, especially for the shift operator. The methods are applied on individual time records of each process variable, as well as on entire groups of time records of process variables in combination with Hidden Markov Models. In this way, the proposed visualization tool is not only associated with a process defect, but it allows also identifying which specific abnormal situation occurred and if this has also occurred in the past. Case studies based on the benchmark Tennessee Eastman process demonstrate the effectiveness of the proposed approach. The results indicate that the proposed visualization tool captures meaningful information hidden in the observations and shows superior monitoring performance.     

Novel Online Methods for Time Series Segmentation

To efficiently and effectively mine massive amounts of data in the time series, approximate representation of the data is one of the most commonly used strategies. Piecewise Linear Approximation is such an approach, which represents a time series by dividing it into segments and approximating each segment with a straight line. In this paper, we first propose a new segmentation criterion that improves computing efficiency. Based on this criterion, two novel online piecewise linear segmentation methods are developed, the feasible space window method and the stepwise feasible space window method. The former usually produces much fewer segments and is faster and more reliable in the running time than other methods. The latter can reduce the representation error with fewer segments. It achieves the best overall performance on the segmentation results compared with other methods. Extensive experiments on a variety of real-world time series have been conducted to demonstrate the advantages of our methods.     

m子序列的密码学性质研究*

文中所提m子序列是根据m序列的状态转换特征,通过交叉改变状态转换次序而形成新的序列。通过随机性测试软件（NIST）验证m子序列具有和m序列相似的随机性,使用BM算法可以得出这种伪随机序列具有非常高的线性复杂度,同时验证了其补序列也具有非常高的线性复杂度,并说明m子序列具有良好的线性复杂度谱,抗线性攻击能力强。m子序列的数量庞大,一个周期为 的m序列,改变反馈函数就可以至少产生 个m子序列。产生m子序列的反馈函数经证明具有良好的代数免疫度,抗代数攻击能力较强。m子序列具有良好的密码学性质,应用前景良好。     

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

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     

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

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

时间序列的快速相似性搜索改进算法

This paper introduces a new method for finding all subsequences similar to a given time series sequence.The method takes into account noise ,offset translation and amplitude scaling. Based on a piecewise linear representa-tion, the speed is exceptionally fast.     

基于频繁模式发现的时间序列异常检测方法

针对传统异常片段检测方法在处理增量式时间序列时效率低的问题,提出一种基于频繁模式发现的时间序列异常检测（TSAD）方法。首先,将历史输入的时间序列数据进行符号转化;其次,利用符号化特征找出历史序列数据集中的频繁模式;最后,结合最长公共子序列匹配方法度量频繁模式与当前新增加时间序列数据之间的相似度,从而发现新增加数据中的异常模式。与基于滑动窗口预测的水文时间序列异常检测方法（TSOD）和基于扩展符号聚集近似的水文时间序列异常挖掘方法（ESAA）相比,对于实验选择的三种类型的时间序列数据,TSAD的检测率都超过90%;TSOD对规则性较强的序列检测率较高,能达到99%,但对噪声干扰较大的序列检测率较低,对数据偏向性较强;ESAA对三种类型的数据检测率均不超过70%。实验结果表明,TSAD在时间序列异常检测中能够较好地发现异常片段。     

Algorithms for subsequence combinatorics

A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above.     

Performance bottleneck of subsequence matching in time-series databases: Observation, solution, and performance evaluation

Subsequence matching is an operation that finds subsequences whose changing patterns are similar to a given query sequence from time-series databases. This paper identifies a performance bottleneck in subsequence matching, and then proposes an effective method that substantially improves the performance of entire subsequence matching by resolving the performance bottleneck. First, we analyze the disk access and CPU processing times required during the index searching and post-processing steps of subsequence matching through preliminary experiments. Based on these results, we show that the post-processing step is a main performance bottleneck in subsequence matching. Then, we argue that the optimization of the post-processing step is a crucial issue overlooked in previous approaches. In order to resolve the performance bottleneck, we propose a simple yet highly effective method for expediting the post-processing step. By rearranging the order of candidate subsequences to be compared with a query sequence, our method completely eliminates the redundancies of disk accesses and CPU processing that occur in the post-processing step. Our method is fairly efficient, and does not incur any false dismissal. We quantitatively demonstrate the superiority of our method through extensive experimentation. The results show that our method produces a significantly faster post-processing step; When using a data set of real-world stock sequences, our method was 43.36-96.75 times faster than previous methods, and when using data sets of large numbers of synthetic sequences, our method was 12.48-26.95 times faster than previous methods. Also, the results show that our method reduces the weight of the post-processing step over entire subsequence matching from more than 97% to less than 67%. This implies that our method successfully resolves the performance bottleneck in subsequence matching. As a result, our method provides excellent performance in entire subsequence matching. Compared with previous methods, our method is 16.17-32.64 times faster when using a data set of real-world stock sequences and 8.64-14.29 times faster when using data sets of large numbers of synthetic sequences.     

Searching for variable-speed motions in long sequences of motion capture data

Motion capture data digitally represent human movements by sequences of body configurations in time. Subsequence searching in long sequences of such spatio-temporal data is difficult as query-relevant motions can vary in execution speeds and styles and can occur anywhere in a very long data sequence. To deal with these problems, we employ a fast and effective similarity measure that is elastic. The property of elasticity enables matching of two overlapping but slightly misaligned subsequences with a high confidence. Based on the elasticity, the long data sequence is partitioned into overlapping segments that are organized in multiple levels. The number of levels and sizes of overlaps are optimized to generate a modest number of segments while being able to trace an arbitrary query. In a retrieval phase, a query is always represented as a single segment and fast matched against segments within a relevant level without any costly post-processing. Moreover, visiting adjacent levels makes possible subsequence searching of time-warped (i.e., faster or slower executed) queries. To efficiently search on a large scale, segment features can be binarized and segmentation levels independently indexed. We experimentally demonstrate effectiveness and efficiency of the proposed approach for subsequence searching on a real-life dataset.     

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

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

一种基于重要点的时间序列分割方法

分段线性表示是时间序列降维的有效方法,其关键在于分割点的确定。在时间序列分段线性表示的基础上,提出一种新的基于重要点的时间序列分割方法。与一般方法比较相邻三点关系不同的是,将时间窗扩展为前一重要点、待考察点和一个指定时间窗组成的区间,再通过比较数据点前后模式变化来确定重要点。通过与其他7种分割方法进行实验比较,证明该方法适应能力强,不但分割结果总体质量高,在压缩率相同时具有更小的拟合误差,而且能够有效滤除噪声,发现时间序列的模式特征。