Shift density estimation based approximately recurring motif discovery

详细信息    查看全文

• 作者：Yasser Mohammad (1) (2)
  Toyoaki Nishida (2)
  
  1. Faculty of Engineering ; Assiut University ; Asyut ; Egypt
  2. Graduate School of Informatics ; Kyoto University ; Kyoto ; Japan
  
• 关键词：Data mining ; Motif discovery ; HRI
• 刊名：Applied Intelligence
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：42
• 期：1
• 页码：112-134
• 全文大小：4,379 KB
• 参考文献：1. Keogh E, Lin J, Fu A (2005) Hot sax: efficiently finding the most unusual time series subsequence. In: 15th IEEE international conference on data mining, p 8. doi:10.1109/ICDM.2005.79
  2. Mohammad Y, Nishida T, Okada S (2009) Unsupervised simultaneous learning of gestures, actions and their associations for human-robot interaction. In: Proceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems, IROS鈥?9. IEEE Press, Piscataway, pp 2537鈥?544. http://dl.acm.org/citation.cfm?id=1733023.1733155 CrossRef
  3. Mohammad Y, Nishida T (2013) Tackling the correspondence problem: closed-form solution for gesture imitation by a humanoid鈥檚 upper body. In: International conference on active media technology (AMT). WIC and IEEE TF-BI, Maebashi, pp 84鈥?5
  4. Mohammad Y, Nishida T (2009) Constrained motif discovery in time series. New Gener Comput 27(4):319鈥?46 CrossRef
  5. Minnen D, Starner T, Essa I, Isbell C (2007) Improving activity discovery with automatic neighborhood estimation. In: International joint conference on artificial intelligence
  6. Chiu B, Keogh E, Lonardi S (2003) Probabilistic discovery of time series motifs. In: KDD 鈥?3: proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 493鈥?98. doi:10.1145/956750.956808 CrossRef
  7. Oates T (2002) Peruse: an unsupervised algorithm for finding recurring patterns in time series. In: International conference on data mining, pp 330鈥?37
  8. Jensen KL, Styczynxki MP, Rigoutsos I, Stephanopoulos GN (2006) A generic motif discovery algorithm for sequenctial data. BioInformatics 22(1):21鈥?8 CrossRef
  9. Lin J, Keogh E, Lonardi S, Patel P (2002) Finding motifs in time series. In: The 2nd workshop on temporal data mining, at the 8th ACM SIGKDD international, pp 53鈥?8
  10. Tang H, Liao SS (2008) Discovering original motifs with different lengths from time series. Know Based Syst 21(7):666鈥?71. doi:10.1016/j.knosys.2008.03.022 CrossRef
  11. Buhler J, Tompa M (2001) Finding motifs using random projections. In: 5th international conference on computational biology, pp 69鈥?6
  12. Patel P, Keogh E, Lin J, Lonardi S (2002) Mining motifs in massive time series databases. In: IEEE international conference on data mining, pp 370鈥?77. doi:10.1109/ICDM.2002.1183925 . http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1183925
  13. Catalano J, Armstrong T, Oates T (2006) Discovering patterns in real-valued time series. In: Knowledge discovery in databases: PKDD 2006, pp 462鈥?69
  14. Mohammad Y, Nishida T (2012) Unsupervised discovery of basic human actions from activity recording datasets. In: Proceedings of the IEEE/SICE international symposium on system integration
  15. Mueen A, Keogh EJ, Zhu Q, Cash S, Westover MB (2009) Exact discovery of time series motifs. In: SDM, pp 473鈥?84
  16. Mohammad Y, Nishida T (2013) Approximately recurring motif discovery using shift density estimation. In: IEA/AIE, pp 141鈥?50
  17. Minnen D, Essa I, Isbell CL, Starner T (2007) Detecting subdimensional motifs: an efficient algorithm for generalized multivariate pattern discovery. In: IEEE international conference on data mining (ICDM)
  18. Tompa M, Buhler J (2001) Finding motifs using random projections. In: 5th international conference on computational molecular biology, pp 67鈥?4
  19. Mueen A (2013) Enumeration of time series motifs of all lengths. In: 2013 IEEE 13th international conference on data mining (ICDM). IEEE
  20. Nunthanid P, Niennattrakul V, Ratanamahatana C (2011) Discovery of variable length time series motif. In: 2011 8th international conference on electrical engineering/electronics, computer, telecommunications and information technology (ECTI-CON), pp 472 鈥?75. doi:10.1109/ECTICON.2011.5947877
  21. Li Y, Lin J (2010) Approximate variable-length time series motif discovery using grammar inference. In: Proceedings of the 10th international workshop on multimedia data mining. ACM, p 10. http://dl.acm.org/citation.cfm?id=18142451814255
  22. Nevill-Manning CG, Witten IH (1997) Identifying hierarchical structure in sequences: a linear-time algorithm. J Artif Intell Res 7(1):67鈥?2. arXiv:9709102
  23. Lin J, Keogh E, Wei L, Lonardi S (2007) Experiencing SAX: a novel symbolic representation of time series. Data Min Knowl Discov 15(2):107鈥?44. doi:10.1007/s10618-007-0064-z CrossRef
  24. Mohammad Y, Nishida T (2009) Robust singular spectrum transform. In: IEA/AIE 2009, pp 253鈥?58
  25. Mohammad Y, Nishida T (2011) On comparing SSA-based change point discovery algorithms. In: 2011 IEEE/SICE international symposium on system integration, pp 938鈥?45
  26. Mohammad Y, Nishida T (2009) Robust singular spectrum transform. In: The 22nd international conference on industrial, engineering and other applications of applied intelligent systems IEA-AIE 2009, pp 123鈥?32
  27. Bro omhead DS, King GP (1986) Extracting qualitative dynamics from experimental data. Physica D 20:217鈥?36 CrossRef
  28. Moskvina V, Zhigljavsky A (2003) An algorithm based on singular spectrum analysis for change-point detection. Commun Stat Simul Comput 32(4):319鈥?52 CrossRef
  29. Ide T, Inoue K (2005) Knowledge discovery from heterogeneous dynamic systems using change-point correlations. In: Proceedings SIAM international conference on data mining
  30. CPMD toolbox: www.ii.ist.i.kyoto-u.ac.jp/~yasser/cpmd
  31. Mohammad Y, Ohmoto Y, Nishida T (2012) Gstex: Greedy stem extension for free-length constrained motif discovery. In: 25th IEA/AIE conference, pp 417鈥?26
  32. Minnen D, Essa I, Isbell C, Starner T (2007) Detecting subdimensional motifs: an efficient algorithm for generalized multivariate pattern discovery. In: IEEE international conference on data mining (ICDM)
  33. Mohammad Y, Nishida T (2014) Exact discovery of length-range motifs. In: ACIIDS. Submitted
  34. Kulic D, Takano W, Nakamura Y (2008) Incremental learning, clustering and hierarchy formation of whole body motion patterns using adaptive hidden Markov chains. Int J Robot Res 27(7):761鈥?84. doi:10.1177/0278364908091153 . http://ijr.sagepub.com/cgi/10.1177/0278364908091153 CrossRef
  35. Pantic M, Pentland A, Nijholt A, Huang T (2007) Machine understanding of human behavior. In: IJCAI 2007 workshop on AI for human computing (AI4HC鈥?7). University of Twente, Centre for Telematics and Information Technology (CTIT), pp 13鈥?4. http://doc.utwente.nl/64116/
  36. Vahdatpour A, Amini N, Sarrafzadeh M (2009) Toward unsupervised activity discovery using multi-dimensional motif detection in time series. In: IJCAI, pp 1261鈥?266
  
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Mechanical Engineering
  Manufacturing, Machines and Tools
  
• 出版者：Springer Netherlands
• ISSN：1573-7497

文摘

Approximately Recurring Motif (ARM) discovery is the problem of finding unknown patterns that appear frequently in real valued timeseries. In this paper, we propose a novel algorithm for solving this problem that can achieve performance comparable with the most accurate algorithms with a speed comparable to the fastest ones. The main idea behind the proposed algorithm is to convert the problem of ARM discovery into a density estimation problem in the single dimensionality shift-space (rather than in the original time-series space). This makes the algorithm more robust to short noise bursts that can dramatically affect the performance of most available algorithms. The paper also reports the results of applying the proposed algorithm to synthetic and three real-world datasets in the domains of gesture discovery and motion primitive discovery.