Incremental mining of temporal patterns in interval-based database

详细信息    查看全文

• 作者：Lin Hui ; Yi-Cheng Chen ; Julia Tzu-Ya Weng ; Suh-Yin Lee
• 关键词：Incremental mining ; Dynamic representation ; Sequential pattern ; Temporal pattern
• 刊名：Knowledge and Information Systems
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：46
• 期：2
• 页码：423-448
• 全文大小：3,006 KB
• 参考文献：1.Agrawal R, Srikant R (1995) Mining Sequential Patterns, Proceedings of 11th International Conference on Data Engineering. (ICDE’95), pp 3–14
  2.Allen J (1983) Maintaining knowledge about temporal intervals. Commun ACM 26(11):832–843CrossRef MATH
  3.Chang L, Wang T, Yang D, Luan H, Tang S (2009) Efficient algorithms for incremental maintenance of closed sequential patterns in large databases. Data Knowl Eng 68(1):68–106CrossRef
  4.Chen J (2010) An up down directed acyclic graph approach for sequential pattern mining. IEEE Trans Knowl Data Eng 22(7):913–928CrossRef
  5.Chen Y, Guo J, Wang Y, Xiong Y, Zhu Y (2007) Incremental Mining of Sequential Patterns using Prefix Tree, The 11th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’07), pp 433–440
  6.Chen Y, Jiang J, Peng W, Lee S (2010) An Efficient Algorithm for Mining Time Interval-based Patterns in Large Databases, 19th ACM International Conference on Information and Knowledge Management (CIKM’10), pp 49–58
  7.Cheng H, Yan X, Han J (2004) IncSpan: Incremental Mining of Sequential Patterns in Large Database, Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’04), pp 527–532
  8.Hoppner F (2002) Finding informative rules in interval sequences. Intell Data Anal 6(3):237–255MathSciNet
  9.Kam P, Fu W (2000) Discovering Temporal Patterns for Interval-based Events, International Conference on Data Warehousing and Knowledge Discovery (DaWaK’00), pp 317–326
  10.Lin M, Lee S (2004) Incremental update on sequential patterns in large databases by implicit merging and efficient counting. Inf Syst 29(5):385–404MathSciNet CrossRef
  11.Lin M, Lee S (2005) Fast discovery of sequential patterns by memory indexing and database partitioning. J Inf Sci Eng 21(1):109–128
  12.Mannila H, Toivonen H, Verkamo I (1997) Discovery of frequent episodes in event sequences. Data Min Knowl Discov 1(3):259–289CrossRef
  13.Masseglia F, Cathala F, Poncelet P (1998) The PSP Approach for Mining Sequential Patterns, European Conference on Principles of Data Mining and Knowledge Discovery (PKDD’01), pp 176–184
  14.Masseglia F, Poncelet P, Teisseire M (2003) Incremental mining of sequential patterns in large databases. Data Knowl Eng 46(1):97–121CrossRef
  15.Morchen F, Ultsch A (2007) Efficient mining of understandable patterns from multivariate interval time series. Data Min Knowl Discov 15(2):181–215MathSciNet CrossRef
  16.Nguyen S, Sun X, Orlowska M (2005) Improvements of IncSpan: Incremental Mining of Sequential Patterns in Large Database, The 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’05), pp 442–451
  17.Papapetrou P, Kollios G, Sclaroff S, Gunopulos D (2005) Discovering frequent arrangements of temporal intervals, International Conference on Data Mining (ICDM’05), pp 354–361
  18.Parthasarathy S, Zaki M, Ogihara M, Dwarkadas S (1999) Incremental and interactive sequence mining, Proceedings of the 8th International Conference on Information and Knowledge Management (CIKM’99), pp 251–258
  19.Patel D, Hsu W, Lee M (2008) Mining Relationships Among Interval-based Events for Classification, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (KDD’08), pp 393–404
  20.Pei J, Han J, Mortazavi-Asl B, Wang J, Pinto H, Chen Q, Dayal U, Hsum M (2004) Mining sequential patterns by pattern-growth: the prefixspan approach. IEEE Trans Knowl Data Eng 16(10):1424–1440
  21.Rowley A, Shulman S (1998) Kawasaki syndrome. Clin Microbiol Rev 11(3):405–414
  22.Srikant R, Agrawal R (1996) Mining Sequential patterns: Generalizations and Performance Improvements, Proceedings of 5th International Conference on Extended Database Technology (EDBT’96), pp 3–17
  23.Tang H, Liao S, Sun S (2013) A prediction framework based on contextual data to support mobile personalized marketing. Decis Support Syst 56:234–246CrossRef
  24.Villafane R, Hua K, Tran D (2000) Knowledge discovery from series of interval events. J Intell Inf Syst 15:71–89CrossRef
  25.Winarko E, Roddick JF (2007) ARMADA-an algorithm for discovering richer relative temporal association rules from interval-based data. Data Knowl Eng 63(1):76–90CrossRef
  26.Wu S, Chen Y (2007) Mining nonambiguous temporal patterns for interval-based events. IEEE Trans Knowl Data Eng 19(6):742–758CrossRef
  27.Wu S, Chen Y (2009) Discovering hybrid temporal patterns from sequences consisting of point-and interval-based events. Data Knowl Eng 68(11):1309–1330CrossRef
  28.Zaki M (2001) SPADE: an efficient algorithm for mining frequent sequences. Mach Learn 42(1–2):31–60CrossRef MATH
  29.Zhang L, Chen G, Brijs T, Zhang X (2008) Discovering during-temporal patterns (DTPs) in large temporal databases. Expert Syst Appl 34:1178–1189CrossRef
  30.Zhang M, Kao B, Cheung D, Yip C (2002) Efficient algorithms for incremental updates of frequent sequences, The 6th Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’02), pp 186–197
  
• 作者单位：Lin Hui (1)
  Yi-Cheng Chen (2)
  Julia Tzu-Ya Weng (3) (4)
  Suh-Yin Lee (5)
  
  1. Department of Innovative Information and Technology, Tamkang University, New Taipei City, Taiwan
  2. Department of Computer Science and Information Engineering, Tamkang University, New Taipei City, Taiwan
  3. Department of Computer Science and Engineering, Yuan Ze University, Taoyuan, Taiwan
  4. Innovation Center for Big Data and Digital Convergence, Yuan Ze University, Taoyuan, Taiwan
  5. Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan
  
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service
  Business Information Systems
  
• 出版者：Springer London
• ISSN：0219-3116

文摘

In several real-life applications, sequence databases, in general, are updated incrementally with time. Some discovered sequential patterns may be invalidated and some new ones may be introduced by the evolution of the database. When a small set of sequences grow, or when some new sequences are added into the database, re-mining sequential patterns from scratch each time is usually inefficient and thus not feasible. Although there have been several recent studies on the maintenance of sequential patterns in an incremental manner, these works only consider the patterns extracted from time point-based data. Few research efforts have been elaborated on maintaining time interval-based sequential patterns, also called temporal patterns, where each datum persists for a period of time. In this paper, an efficient algorithm, Inc_TPMiner (Incremental Temporal Pattern Miner) is developed to incrementally discover temporal patterns from interval-based data. Moreover, the algorithm employs some optimization techniques to reduce the search space effectively. The experimental results on both synthetic and real datasets indicate that Inc_TPMiner significantly outperforms re-mining with static algorithms in execution time and possesses graceful scalability. Furthermore, we also apply Inc_TPMiner on a real dataset to show the practicability of incremental mining of temporal patterns.