时态数据的趋势序列分析及其子序列匹配算法研究

Trend Sequences Analysis of Temporal Data and a Subsequence Matching Algorithm

针对时态数据挖掘中传统趋势序列分析的缺点,提出了数字趋势序列、趋势序列展开等概念.根据数字趋势序列的特点,使用片段斜率所对应的弧度值来度量片段的趋势.针对数字趋势序列的子序列匹配问题,设计了“DTW双约束快速搜索算法”.算法分为3个部分:DTW顺序搜索、双约束机制、冗余消除机制,其中DTW顺序搜索构成了算法的基本框架,双约束机制加快了DTW距离的计算过程,冗余消除机制消除了最终结果集中的冗余.

In current trend sequences nominal scale and edit distance are used to measure trend values, distance between trend sequences respectively. The analysis of this kind of trend sequences essentially belongs to the domain of character string analysis. These traditional trend sequences are called character trend sequence （CTS） in this paper. The largest problem about analysis of CTSs is to use very few indexes to depict trends of sequences which have a very large range of variety, so little information included in temporal data sequences is preserved in CTSs. To overcome demerits of traditional trend sequences＇ analysis in temporal data mining, two concepts which are number trend sequence （NTS） and trend sequences unwrapping are put forward. According to features of NTSs, radians which slopes correspond to are used to represent trends of line segments. Dynamic time warping double restrictions quick searching （DTW-DRQS） algorithm is designed to solve the problem of subsequence matching between NTSs. The algorithm includes three parts： DTW sequential searching, the mechanism of double restrictions and the mechanism of redundancy control. DTW sequential searching is the basic framework of the algorithm, and; the mechanism of double restrictions can accelerate the calculation process of DTW distance; the mechanism of redundancy control can eliminate redundant subsequences in the result set.