在线分割时间序列数据算法

1、在线分割时间序列数据算法摘要近年来，人们对于时序数据库的发掘的兴趣激增，与大多数的计算机科学 方面的问题一样，数据的呈现是实现高效率解决方案的关键。最常见的数据呈 现方式之一是分段线性近似法。这种方案已被各种研究人员用于辅助聚类，分 类，索引和关联规则挖掘的时间序列数据。各种算法都被提议使用这种呈现方案，也有一部分算法独立地再次发现。 在这篇论文中，我们将进行第一次广泛的审查与考察比较所有推荐的技术，从 数据挖掘的角度展示出这些所有的算法都有一些致命的缺陷。同时，我们将引 入了一个新的算法，并考察表明它优于所有其他在文献中的算法。算法的表现取决于max_error的值。当max_error是0

2、的时候，所有的算法有一样的表现，因为他们会产生n/2个分段而且没有误差。在另一端，当max_error变得非常大时，算法也会有一样表现，因为他们都将T近似化为单 条最适线。所以，我们必须用特定的max_error的值来测试算法相关的表现， 这个值必须要达到压缩和保真的平衡点。因为这个“合理的值”是主观的而且 与数据挖掘运用以及数据本身，我们作如下的工作。我们为每一个数据集选择 一个预想的“合理的值”，然后我们把2种权，用6种值归类。这些值中的最 小值可能会产生一个过渡碎片化的近似结果，而最大值可能会产生非常粗糙的 近似结果。所以总的来说，在6个值中的中间段的值则是最重要的。如下图：因为我们只对

3、相关的表现感兴趣，对每一组数据集，我们正常化了 3种算 法的表现，通过用最差的表现方法区分。Figure 5. A comparison of the three major times series segmentation algorithms, on ten diverse datasets3.2实验结果实验结果总结在下图里。最明显的结果是滑动窗口算法通常产生较低质量 的结果。除了少数的例外，它是表现最差的算法。10自上而下算法有时候能打败自底向上算法，但是只有很少的情况下。另一 方面，自底向上算法经常比自上而下算法优秀，尤其是在心电图、制造业以及 水位数据集上。4 .新的方法仔细思考了

4、几种主要分割算法的缺点，我们研究出了一种新的方法。滑动 窗口算法的主要问题是他不能查看历史数据，对它的离线部分缺乏总体观。自 底向上和自上而下方法能得出较好的结果，但是是离线的，而且需要最整个数 据集进行扫描。这是不切实际。因为在数据挖掘背景下，数据可以达到TB级 别或者以持续不断的数据流形式输入。因此我们提出一种新的方法，它同时保 留了滑动窗口的在线特性以及自底向上算法的优越性。我们给这种算法取名叫 滑动窗口自底向上算法。II4. 1滑动窗口自底向上分割算法滑动窗口自底向上算法保留一个小的缓冲区，缓冲区的大小需要一开始设 定以便有足够的数据来创建大概56个分段。自底向上应用于缓冲区的数据，

5、最左端的分段被报告出来。己经被报告过的数据将从缓冲区删除，然后读入更 多的数据点。数据点读入的数量取决于输入数据的结构。这个过程由基于滑动 窗口算法的Best_Line函数实现。然后在缓冲区中，对这些数据点再使用自底 向上算法。只要有数据到达，就会不断重复上述步骤。这个算法的灵感源于此：Best_line函数找到符合一个使用滑动窗口的分 段并把它放入缓冲区。当数据通过缓冲区时，再对它们使用自底向上算法来改 善这个分割。因为这种报告算法是对整个数据半全局的。当数据从缓冲区离开 的时候，分割点通常和自底向上算法的批处理版本是一样的。算法的伪代码如 下表Algorithm Seg_TS = SWAB

6、 (max_error, seg_num)/ seg_num is integer, about 5 or 6.read in data points to fill w / w is the buffer/ Enough to approximate seg_num of segments.lower_bound - (size of 同 / 2;upper_bound = 2 * (size of w);while data at inputT = Bottom_Up (w, max_error)/ Call the classic Bottom-Up algorithm.Seg_TS =

7、 CONCAT(SEG_TS, T(l);/ Sliding window to the right.w 二 TAKEOUTS 广);/ Deletes w points in T (1) from w.if data at input / Add points from BEST_LINE() to w.w - CONCAT(w, BEST LINE(max error);12/ Check upper and lower bound, adjust if necessary.else / Flush approximated segments from buffer.Seg_TS = CO

8、NCAT(SEG_TS, (T - T(l)end;end;Function S 二 BESTLINE(maxerror) /returns S points.while error max_error / next potential segment.read in one additional data point, d, into SS = CONCAT(S,由;error = approx_segment (S);end while;return S;使用缓冲区允许我们得到一个半全局的数据观。然而，利用窗口大小的高 低界限也是非常重要的。一个任意增长的缓冲区会使这种算法回到单纯的自底

9、向上算法上去。但是过小的缓冲区也会使它变回滑动窗口算法。在我们算法中, 我们使用了一个两倍于初始缓冲区大小的最大边界。我们的算法可以看成是对一个在滑动窗口和自底向上算法的极端的连续 体进行操作。令人惊喜的是，通过允许缓冲区包含通常数据分段的56倍大小 的数据，算法产生了与自底向上算法几乎相同的结果，而且还能处理一个无限 的数据流。我们的算法仅仅需要一个小的，常量的内存，而且时间复杂度也只 比标准的自底向上算法差一点。4.2实验证实我们重复了第三部分的实验，这次将新的算法与单纯的经典滑动窗口和经 典自底向上算法进行了比较。结果如下图所示，表明了新算法的结果和自底向 上算法的结果本质是一致的。13

10、ii0.8il-0.40iliBNoisy Slno cubedECGManufacturing Water LevelSpace Shuttlo Sine cubdTlckwlse 1Radio WavosTkkwlse 2Exchange Rate5 .结论我们完成了最时间序列分割算法的初次的总体评价和证实比较。我们展示 了，最受欢迎的方法滑动窗口法通常得到较差的结果，而自上而下算法能产生 合理的结果，但是不能很好的线性扩展。相对而言，最鲜为人知的自底向上算 法产生了优秀的结果，而且能够根据数据集的大小进行线性扩展。额外的，我们也提出了 SWAB, 一种新的在线算法，既能对数据集的大小 进

11、行线性扩展，而且只需要一定的空间来产生出高质量的数据近似。14参考文献1 Agrawal, R., Faloutsos, C., & Swami, A. (1993).Efficient similarity search in sequence databases. Proceedings of the 4 the Conference on Foundations of Data Organization and Algorithms._2 Agrawal,R. , Lin,K. I. ,Sawhney, H. S. ,&Shim,K.(1995). Fastsimilaritysearc

12、hin the presenceofnoise,scaling, and translation in times-series databases.Proceedings of 21th International Conference on Very Large Data Bases, pp 490-50.3 Agrawal, R. , Psaila, G. , Wimmers, E. L. ,& Zait, M.(1995). Querying shapes of histories. Proceedings of the 21st International Conference on

13、 Very Large Databases.4 Chan, K. & Fu, W. (1999). Efficient time series matching by wavelets. Proceedings of the 15 the IEEE International Conference on Data Engineering. 5 Das, G. , Lin, K. Manni la, H. , Renganathan, G. , & Smyth, P. (1998). Rule discovery from time series. Proceedings othe 3rd In

14、ternational Conference of Knowledge Discovery and Data Mining, pp 1622.6 Douglas, D. H. & Peucker, T. K. (1973). Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its15 Caricature. Canadian Cartographer, Vol. 10, No. 2, December. Pp. 112-122._7 Duda, R. 0

15、. and Hart, P. E. 1973. Pattern Classification and Scene Analysis. Wiley, New York.8 Ge, X. & Smyth P. (2001). Segmental Semi-MarkovModels for Endpoint Detection in Plasma Etching. To appear in IEEE Transactions on Semiconductor Engineering._9 Heckbert, P. S. & Garland, M. (1997). Survey of polygona

16、l surface simplification algorithms, Multiresolution Surface Modeling Course.Proceedings of the 24th International Conference on Computer Graphics and Interactive Techniques.Hunter, J. & McIntosh, N. (1999). Knowledge-based event detection in complex time series data. Artificial Intelligence in Medi

17、cine, pp. 271-280. Springer.Ishijima, M. , et al. (1983). Scan-Along Polygonal Approximation for Data Compression of Electrocardiograms. IEEE Transactions on Biomedical Engineering. BME- 30 (11):723-729.Koski, A. , Juhola, M. & Meriste, M. (1995). Syntactic Recognition of ECG Signals By Attributed F

18、inite Automata. Pattern Recognition, 28 (12), pp. 1927-1940.16Keogh, E, . Chakrabarti, K, . Pazzani, M. & Mehrotra (2000).Dimensionality reduction for fast similarity search in large time series databases. Journal of Knowledge and Information Systems.Keogh, E. & Pazzani, M. (1999). Relevance feedbac

19、k retrieval of time series data. Proceedings of the 22th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval.15 Keogh, E. , & Pazzani, M. (1998). An enhanced representation of time series which allows fast and accurate classification, clustering and relevan

20、ce feedback. Proceedings of the 4th International Conference of Knowledge Discovery and Data Mining, pp 239一241, AAAI Press.16 Keogh, E., & Smyth, P. (1997). A probabilistic approach to fast pattern matching in time series databases. Proceedings of the 3rd International Conference of Knowledge Disco

21、very and Data Mining, pp 24-20._17 Lavrenko, V. , Schmill, M. , Lawrie, D. , Ogilvie, P. , Jensen, D., & Allan, J. (2000). Mining of Concurent Text and Time Series.Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining, pp.37-44.17Li, C, . Yu, P. & Castelli V. (1998).

22、 MALM: A framework for mining sequence database at multiple abstraction levels. Proceedings of the 9th International Conference on Information and Knowledge Management. pp267-272.McKee, J. J. , Evans, N. E. , & Owens, F. J. (1994). Efficient implementation of the Fan/SAPA-2 algorithm using fixed poi

23、nt arithmetic. Automedica. Vol. 16, pp 109-117.Osaki, R., Shimada, M., & Uehara, K. (1999). Extraction ofPrimitive Motion for Human MotionRecognition. The 2nd International Conference on Discovery Science, pp. 351-352.Park, S. , Kim, S. W. , & Chu, W. W. (2001). Segment- Based Approach for Subsequen

24、ce Searches in Sequence Databases, To appear in Proceedings of the 16th ACM Symposium on Applied Computing.Park, S. & Lee, D. , & Chu, W. W. (1999). Fast Retrieval of Similar Subsequences in Long Sequence Databases”, Proceedings of the 3rd IEEE Knowledge and Data Engineering Exchange Workshop.Pavlid

25、is, T. (1976). Waveform segmentation through functional approximation. IEEE Transactions on Computers.Perng, C. , Wang, H. , Zhang, S. , & Parker, S. (2000). Landmarks:18 a new model for similarity-based pattern querying in time series databases. Proceedings of 16lh International Conference on Data

26、Engineering.Qu, Y. , Wang, C. & Wang, S. (1998). Supporting fast search in time series for movement patterns in multiples scales. Proceedings of the 7th International Conference on Information and Knowledge Management.Ramer, U. (1972). An iterative procedure for the polygonal approximation of planar

27、 curves. ComputerGraphics and Image Processing. 1: pp. 244-256.Shatkay, H. (1995). Approximate Queries and Representations for Large Data Sequences. Technical Report cs-9503, Department of Computer Science, Brown University.Shatkay, IL , & Zdonik, S. (1996). Approximate queries and representations f

28、or large data sequences. Proceedings of the 12th IEEE International Conference onData Engineering, pp 546-553.Sugiura, N. & Ogden, R. T. (1994). Testing Changepoints with Linear Trend Communications in Statistics B: Simulation and Computation. 23 : 287-322.30 Vullings, H. J. L. M. , Verhaegen, M. H.

29、 G. & Verbruggen H. B. (1997).19简介近年来，人们对于时序数据库的发掘的兴趣激增。与大多数计算机科学方 面的问题一样，数据的呈现是实现高效率解决方案的关键，有一些被广泛推荐 的高等的时序数据呈现算法，包括傅里叶变换、小波分析、符号映射、分段线 性表示。在本文中，我们将主要讨论目前最为广泛应用的分段线性表示（PLR）。直观上来说，分段线性表示是指取一个时间序列的近似T,长度为n,有 K条直线。下图包含两个例子。这种表现方式使得数据的存储传输和计算效率更高。具体而言，在数据挖 掘的背景下，分段线性表示已被用于各个研究方面，比如用于支持快速准确的 相似性检索等等。令人惊

30、讶的是，尽管这种表示方案广泛存在，但除了 27以外，几乎 没有人试图了解和比较产生它的算法。事实上，甚至没有出现一个关于什么叫 这样的算法的共识。为了清晰起见，我们将参考这些类型的算法，输入时间序 列并将分段线性表示当做一个分割算法。分割问题可以用各种方式构架。我们在接下来的部分将会看到，不是所有 的算法都能支持这些技术规范。分割算法也可以被分类为批处理或者在线处理。这是很重要的区别，因为 许多数据挖掘问题是内在地不停变化的。需要生产出分段线性近似的数据挖掘研究者，要么独立重新发现了一种算 法要么使用了一种相关文献推荐的方法。比如，来自制图学或者计算机领域。 ECG Segmentation

31、Using Time-Warping. Proceedings of the 2nd International Symposium on Intelligent Data Analysis.31 Wang, C. & Wang, S. (2000). Supporting contentbased searches on time Series via approximation. Proceedings of the 12th International Conference on Scientific and Statistical Database Management.20 再本文中

32、，我们评价文献中三种主要的分割方法，并且对来自金融医疗科学的 数据集一个考察评估。这些实验的主要结果表明，只有在线算法得到了很差的 近似数据，而批处理算法得到了高质量的结果和一一这些结果促使我们介绍一 种新的在线算法，它能够又在线，又产出高质量的数据近似.本文接下来的主体结构如下：在第二节中，我们将对文献中已有的算法进 行总体评价，解释它们的主要方法以及各种各样数据挖掘者的改变和扩展。在 第三节中，我们将详细地考究、比较这些算法。我们会证明最受数据挖掘者欢 迎的方法实际上产生相当糟糕的数据近似。这些糟糕的结果将激励我们寻求一 种新的算法，而我们将在第四节中介绍和评估这种算法。第五节将做一个总结

33、 以及对未来的展望。背景和相关工作在这节中，我们将介绍3种主要的时间序列数据分割方法。为了便于理解, 几乎所有的算法都有二到三维的类似物。本文不讨论更高维度的情况。有兴趣 的读者可以参考文献9,它有一些优秀的探讨。尽管有着不同的名字以及轻微的实现细节的差异，大多数时序数据分割算 法都可以被分成以下三种：滑动窗口算法：直到超过误差界限后才会分段，进程重复在新的近似分割 的数据点。自上而下算法：时间序列递归地被分割，直到一些会导致停止标准出现。自底向上算法：从最可能的近似出发，混合这些分段，直到碰到停止的标 准。T格式为 tl, t2, , tn 的时间序列Ta;b时间序列T的a-b分段ta, t

34、a+1tb3Seg_TS时间序列T (长度n, 有K段)的分段线性近似， 分段个体可以标注为 Seg TS(i)Create_segment (T)带入时间序列和返回线性近似的函数Calcutate_error (T)带入时间序列和返回线性近似的错误的函数给定我们要用一些直线来近似一个时间序列，这里有至少两种方法来找出 近似的线。线性插补：序列Ta:b的近似线段是简单的a点和b点的连线。整个序 列是连续的。线性回归：序列Ta:b的近似线段是对a点到b点间所有数据点进行拟 合。整个序列不是连续的。下图给出了两种方法的示例。线性插补倾向于连接线段初始和结尾的点， 使分段近似看起来比较“光滑”。相较

35、之下，线性回归则产生了不连贯的图像。 线性插补的美观的结果、较低的计算复杂度使它成为了计算机图形应用的选 择。然而，按照欧几里得距离理论，线性插补得到的近似线段的质量通常比回 归方法得到的要差。所有的分割算法都需要一些方法来为评估它应用于一个潜在分段的质量。 通常采用的测量依据是平方和，或者残留的错误。这通最适线段和实际数据点 的垂直差异，计算它们并且总和。另外一种常用的拟合优度的测量依据是最适 线段和垂直方向上最远数据点的距离。以前，我们正如以前，我们一直保持我 们的算法的描述，一般足以涵盖任何错误措施。特别地，伪代码函数 calculate_error (T)可以被当做使用了任何的平方和，

36、最远点或者其他的测 度。2. 1滑动窗口算法滑动窗口算法通过固定潜在分段的左边的数据点，然后尝试向右近似数 据，逐渐增到更长的分段。在一些点i处，潜在分段的误差比用户指定的阈值 大，从起始点到i-1的部分会被分成一个分段，起始点又从i开始，然后进程 重复，直到整个时间序列数据被转换成了分段线性近似。算法的伪代码如下表 所示：Algorithm Seg_TS = Sliding_Window(T , max_error)anchor = 1;while not finished segmenting time seriesi = 2;while calculate_error (T anchor

37、: anchor + i ) max_errori = i + 1;end;Seg_TS=concat(Seg_TS, create_segment(Tanchor:anchor+(i-1);anchor = anchor + i;end;滑动窗口算法的优势在于它的简单，直观性，还有特别是因为它是一种在 线算法。也有以此算法为基础的很多不同的变换和优化。Koski et al提出可 以通过把变量i的增量由1变为“长度k的跳跃”来加速这种算法12 o取决于使用的误差测量，可能还有其他的优化手段。Bulllings et al提 出因为残留的误差即使加入更多的数据点也不会增长，所以我们不必测出从2

38、 到最后一个选值中每一个i的值30 o滑动窗口算法在某些情况下可能得到相当差的结果。大多数研究者没有提 到过这个25,31,可能因为他们在固定的数据里测试过了这个算法，而且它在 噪声数据上的表现是最好的。Shatkay ( 1995),注意到了这个问题而且给出了 简洁的例子和解释27。他们提出了三种基础算法的变体，每一个都对应一种 具体的场景，但他们声明要一种变体能使用于任意数据源场景是极具难度的。滑动窗口算法的变化在医学领域尤其受欢迎11, 12, 19, 30。2.2自上而下算法自上而下算法通过考虑每一种可能的时序分割然后在最佳的地方进行分 割。两个分段将被测试看是否他们的拟合误差小于用户

39、指定的阈值，如果不是, 算法将递归地进行分割子序列直到所有的分段的拟合误差都小于阈值。算法的 伪代码如下表所示：Algorithm Seg_TS = Top_Down (T , max_error)best_so_far = inf:for i = 2 to length (T)- 2 / Find best place to divide. improvement_in_approximation 二improvement_splitting_here(T, i);if improvement_in_approximation max_errorSeg TS 二 Top Down(T1: b

40、reakpoint);end;/ Recursively split the right segment if necessary.if calculate_error ( Tbreakpoint + 1:length(T) ) max_errorSeg TS = Top Down(Tbreakpoint + 1: length (T);end;在数十年前，自上而下算法的变种(包括二维情况)就被独立地应用于各 个领域。在制图学，出名的有Douglas-Peucker算法，在图像处理方面，出名 的有Ramers算法。大多数的机械学习与数据挖掘领域的研究者。在机器学习和 数据挖掘领域，大多数的研究

41、者是学习的由Duda和Harts提出的该算法，称 为“Iterative End-Points Fits。在数据挖掘领域，这种算法也被18用于支持一个多重抽象水平的挖掘数 列数据库的框架。Shatkay和Zdonik使用它来支持求时序数据库的查询近似。Park et al提出了一个修正方案，最初扫描一整串数据集并且标出每一 个波峰和波谷。这些极值点用于创建一个最初的分割，而自上而下的算法被应 用于每一个分段。然后他们使用这个分割来支持动态时间变形的特别情况。这 种修正方案在处理光滑的合成数据集时效果很好。但对真实的含有噪声的数据 集，这个近似算法不算出色。Lavrenko et al使用了自上而下算法来支持文本和时序数据的他并行挖 掘。他们尝试去发现金融市场的新故事的影响，他们的算法包括一些有趣的修 正。最后Smyth和Ge使用这种算法来产生了一种能够支持A HIDDEN MARKOV MODEL方法改变点侦查和样品匹配的表示。2.3自底向上算法自底向上算法是自上而下算法的天然补充。首先得到最精细的线性分段表 示，既时间序列上相邻两点组成最小分段。这样，n/2个分段被用来近似表现n 长度的时间序列。然后计算合并两个相邻分段所产生的拟合误差，合并拟合误 差最小的两个邻接分段，直到该拟