基于层次聚类的时间序列在线划分算法<sup>*</sup>

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (458 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要如何在线划分数据序列以满足持续动态增长的海量数据流需求正成为序列挖掘领域中的重要内容之一.本文提出一种新的基于层次聚类的在线序列分割算法(OSHC).利用数据序列的有序性特征，构造一种存储划分特征的链表结构SFList.该算法通过一次扫描数据库实现数据序列的在线划分，时间复杂度为O(n).利用SFList中保存的划分特征信息，历史信息的快速查询成为可能.实验结果表明OSHC算法具有良好的划分性能和扩展性能.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	杜奕
	卢德唐
	李道伦
	查文舒

关键词 ：时间序列, 在线划分, 划分特征链表, 层次聚类

Abstract：How to segment sequential data in realtime is becoming one of the most important tasks in the time series mining domain. A new online segmentation algorithm called online segmentation algorithm for time series based on hierarchical clustering (OSHC) is presented. According to the order characteristics of sequence data, a novel Segment Feature List (SFList) is developed to save segmentation information. In the algorithm, time series are segmented effectively with one scan of the database and the time complexity is O(n). Historical information can also be inquired quickly by using the SFList. Experimental results show that the algorithm is efficient.

Key words： Time Series Online Segmentation Segment Feature List Hierarchical Clustering

收稿日期: 2005-12-07

ZTFLH:

TP181

基金资助:国家973计划资助项目(No.2006CB705800)

作者简介: 杜奕，女，1977年生，博士研究生，主要研究方向为数据序列挖掘.Email:duyi@mail.ustc.edu.cn.卢德唐，男，1966年生，教授，博士生导师，主要研究方向为大型工程软件.李道伦，男，1972年生，博士研究生，主要研究方向为计算机图形学、图像理解、神经网络.查文舒，男，1982年生，博士研究生，主要研究方向为工程计算可视化.

引用本文:

杜奕，卢德唐，李道伦，查文舒. 基于层次聚类的时间序列在线划分算法^*[J]. 模式识别与人工智能, 2007, 20(3): 415-420. DU Yi, LU DeTang , LI DaoLun, ZHA WenShu. Online Segmentation Algorithm for Time Series Based on Hierarchical Clustering. , 2007, 20(3): 415-420.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/ 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2007/V20/I3/415

[1] Guralnik V, Srivastava J. Event Detection from Time Series Data // Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, USA, 1999: 3342
[2] LI Aiguo, Qin Zheng. OnLine Segmentation of TimeSeries Data. Journal of Software, 2004, 15(11): 16711679 (in Chinese)
(李爱国,覃征.在线分割时间序列数据.软件学报, 2004,15(11): 16711679)
[3] Huang Chao, Zhu Yangyong. An OnLine Algorithm for Segmenting Time Series Based on ARMA Model. Pattern Recognition and Artificial Intelligence, 2005, 18(2): 129134 (in Chinese)
(黄超,朱扬勇.基于ARMA模型的联机时间序列数据分割算法.模式识别与人工智能, 2005, 18(2): 129134)
[4] Firoiu L. Segmenting Time Series with a Hybrid Neural NetworksHidden Markov Model // Proc of the 18th National Conference on Artificial Intelligence. Edmonton, Canada, 2002: 247252
[5] Chung F L, Fu T C, Ng V, et al. An Evolutionary Approach to PatternBased Time Series Segmentation. IEEE Trans on Evolutionary Computation, 2004, 8(5): 471489
[6] Haiminen N, Gionis A. Unimodal Segmentation of Sequences // Proc of the 4th IEEE International Conference on Data Mining. Brighton, UK, 2004: 106113
[7] Perng C S, Wang H X, Zhang S R, et al. Landmarks: A New Model for SimilarityBased Pattern Querying in Time Series Databases // Proc of 16th International Conference on Data Engineering. San Diego, USA, 2000: 3342
[8] Terzi E, Tsaparas P. Efficient Algorithms for Sequence Segmentation // Proc of the 6th SIAM International Conference on Data Mining. Bethesda, USA, 2006: 314325
[9] Keogh E, Kasetty S. On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 102111
[10] Keogh E J, Chakrabarti K, Pazzani M J, et al. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases. Knowledge and Information Systems, 2001, 3(3): 263286
[11] Yi B K, Faloutsos C. Fast Time Sequence Indexing for Arbitrary Lp Norms // Proc of the 26th International Conference on Very Large Data Bases. Cairo, Egypt, 2000: 385394
[12] Keogh E, Chu S, Hart D, et al. An Online Algorithm for Segmenting Time Series // Proc of the IEEE International Conference on Data Mining. San Jose, USA, 2001: 289296
[13] Wu Jiangqin, Gao Wen. Time Series Clustering Algorithm and Its Application in Gesture Recognition. Pattern Recognition and Artificial Intelligence, 2005,18(1):15 (in Chinese)
(吴江琴,高文.时间序列聚类算法及其在手势识别中的应用.模式识别与人工智能, 2005, 18(1): 15)
[14] Han Jiawei, Kamber M. Data Mining: Concepts and Techniques. San Francisco, USA: Morgan Kaufmann Publishers, 2001
[15] MacQueen J B. Some Methods for Classification and Analysis of Multivariate Observations // Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, USA, 1967, Ⅰ: 281297
[16] Kim J S, Kim M H. On Effective Data Clustering in Bitemporal Databases // Proc of the 4th International Workshop on Temporal Representation and Reasoning. Daytona Beach, USA, 1997: 5461