research-article

ePeriodicity: Mining Event Periodicity from Incomplete Observations

Authors:

Jiawei HanAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 27, Issue 5

Pages 1219 - 1232

https://doi.org/10.1109/TKDE.2014.2365801

Published: 01 May 2015 Publication History

Abstract

Advanced technology in GPS and sensors enables us to track physical events, such as human movements and facility usage. Periodicity analysis from the recorded data is an important data mining task which provides useful insights into the physical events and enables us to report outliers and predict future behaviors. To mine periodicity in an event, we have to face real-world challenges of inherently complicated periodic behaviors and imperfect data collection problem. Specifically, the hidden temporal periodic behaviors could be oscillating and noisy, and the observations of the event could be incomplete. In this paper, we propose a novel probabilistic measure for periodicity and design a practical algorithm, ePeriodicity, to detect periods. Our method has thoroughly considered the uncertainties and noises in periodic behaviors and is provably robust to incomplete observations. Comprehensive experiments on both synthetic and real datasets demonstrate the effectiveness of our method.

References

[1]

Z. Li, J. Wang, and J. Han, “Mining event periodicity from incomplete observations,” in Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining , 2012, pp. 444–452.

[2]

M. C. González, C. A. Hidalgo, and A.-L. Barabás, “ Understanding individual human mobility patterns,” Nature, vol. 453, pp. 779–782, 2008.

[3]

Z. Li, B. Ding, J. Han, R. Kays, and P. Nye, “Mining periodic behaviors for moving objects,” in Proc. 16th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2010, pp. 1099–1108.

Digital Library

[4]

T. van Kasteren, A. K. Noulas, G. Englebienne, and B. J. A. Kröse, “Accurate activity recognition in a home setting,” in Proc. 10th Int. Conf. Ubiquitous Comput., 2008, pp. 1–9.

Digital Library

[5]

M. B. Priestley, Spectral Analysis and Time Series. London, U.K. : Academic, 1981.

[6]

M. Vlachos, P. S. Yu, and V. Castelli, “On periodicity detection and structural periodic similarity,” in Proc. SIAM Int. Conf. Data Mining, 2005, p. 1.

[7]

M. G. Elfeky, W. G. Aref, and A. K. Elmagarmid, “ Periodicity detection in time series databases,” IEEE Trans. Knowl. Data Eng., vol. 17, no. 7, pp. 875–887, Jul. 2005.

Digital Library

[8]

N. R. Lomb, “Least-squares frequency analysis of unequally spaced data,” Astrophys. Space Sci., vol. 39, pp. 447 –462, 1976.

[9]

J. D. Scargle, “Studies in astronomical time series analysis. ii—Statistical aspects of spectral analysis of unevenly spaced data,” Astrophys. J., vol. 263, pp. 835–853, 1982.

[10]

R. Durrett, Probability: Theory and Examples. Pacific Grove, CA, USA : Brooks/Cole, 1991.

[11]

J. R. Blum and D. Hanson, “On the mean ergodic theorem for subsequences,” Bull. Amer. Math. Soc., vol. 66, pp. 308–311, 1960.

[12]

J. Blum and B. Eisenbery, “The law of large numbers for subsequences of a stationary process,” Ann. Probability, vol. 3, no. 2, pp. 281– 288, 1975.

[13]

H. Ge, D.-Q. Jiang, and M. Qian, “A simple discrete model of brownian motors: Time-periodic markov chains,” J. Stat. Phys., vol. 123, no. 4, pp. 831–859, 2006.

[14]

R. C. Bradley, “Basic properties of strong mixing conditions. A survey and some open questions,” Probability Surveys, vol. 2, pp. 107–144, 2005.

[15]

I. Junier, J. Herisson, and F. Kepes, “Periodic pattern detection in sparse boolean sequences,” Algorithms Molecular Biol., vol. 5, p. 31, 2010.

[16]

M. Schimmel, “Emphasizing difficulties in the detection of rhythms with lomb-scargle periodograms,” Biol. Rhythm Res., vol. 32, no. 3, pp. 341–345, 2001.

[17]

D. J. Cook and M. Schmitter-Edgecombe, “Assessing the quality of activities in a smart environment, ” Methods Inf. Med., vol. 48, no. 5, pp. 480 –485, 2009.

[18]

D. J. Cook, “Learning setting-generalized activity models for smart spaces,” IEEE Intell. Syst., vol. 27, no. 1, pp. 32–38, Jan./Feb. 2012.

[19]

E. F. Glynn, J. Chen, and A. R. Mushegian, “ Detecting periodic patterns in unevenly spaced gene expression time series using lomb-scargle periodograms, ” Bioinformatics, vol. 22, no. 3, pp. 310–316, 2005.

[20]

K.-C. Liang, X. Wang, and T.-H. Li, “Robust regression for periodicity detection in non-uniformly sampled time-course gene expression data,” BMC Bioinformat., vol. 8, p. 233, 2009.

[21]

J. Han, W. Gong, and Y. Yin, “Mining segment-wise periodic patterns in time-related databases,” in Proc. Int. Conf. Knowl. Discovery Data Mining , 1998, pp. 214–218.

[22]

J. Han, G. Dong, and Y. Yin, “Efficient mining of partial periodic patterns in time series database,” in Proc. 15th Int. Conf. Data Eng., 1999, pp. 106–115.

[23]

J. Yang, W. Wang, and P. S. Yu, “Mining asynchronous periodic patterns in time series data,” IEEE Trans. Knowl. Data Eng. , vol. 15, no. 3, pp. 613–628, May/Jun. 2003.

Digital Library

[24]

J. Yang, W. Wang, and P. S. Yu, “Infominer: Mining surprising periodic patterns,” in Proc. 7th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2001, pp. 395–400.

[25]

J. Yang, W. Wang, and P. S. Yu, “Infominer+: Mining partial periodic patterns with gap penalties,” in Proc. Int. Conf. Data Mining , 2002, pp. 725–728.

[26]

W. Wang, J. Yang, and P. S. Yu, “ Meta-patterns: Revealing hidden periodic patterns,” in Proc. Int. Conf. Data Mining , 2001, pp. 550–557.

[27]

S. Ma and J. L. Hellerstein, “ Mining partially periodic event patterns with unknown periods,” in Proc. 17th Int. Conf. Data Eng., 2001, pp. 205–214.

Digital Library

[28]

W. G. Aref, M. G. Elfeky, and A. K. Elmagarmid, “ Incremental, online, and merge mining of partial periodic patterns in time-series databases,” IEEE Trans. Knowl. Data Eng., vol. 16, no. 3, pp. 332 –342, Mar. 2004.

Digital Library

[29]

C. Sheng, W. Hsu, and M.-L. Lee, “Mining dense periodic patterns in time series data,” in Proc. 17th Int. Conf. Data Eng., 2006, p. 115.

[30]

F. Rasheed, M. Al-Shalalfa, and R. Alhajj, “ Efficient periodicity mining in time series databases using suffix trees,” IEEE Trans. Knowl. Data Eng., vol. 23, no. 1, pp. 79– 94, Jan. 2011.

Digital Library

[31]

C. Berberidis, W. G. Aref, M. J. Atallah, I. P. Vlahavas, and A. K. Elmagarmid, “Multiple and partial periodicity mining in time series databases,” in Proc. Eur. Conf. Artif. Intell., 2002, pp. 370–374.

[32]

H. Cao, D. W. Cheung, and N. Mamoulis, “Discovering partial periodic patterns in discrete data sequences,” in Proc. 8th Pacific-Asia Conf. Adv. Knowl. Discovery Data Mining, 2004, pp. 653–658.

[33]

P. Indyk, N. Koudas, and S. Muthukrishnan, “ Identifying representative trends in massive time series data sets using sketches,” in Proc. 8th Int. Conf. Very Large Data Bases, 2000, pp. 363–372 .

[34]

M. G. Elfeky, W. G. Aref, and A. K. Elmagarmid, “ Warp: Time warping for periodicity detection,” in Proc. 5th Int. Conf. Data Mining , 2005, pp. 138–145.

Cited By

Iqbal MPrayitno APao HMukhlash I(2024)Mining fuzzy local periodic activity pattern for Smart home applicationsKnowledge-Based Systems10.1016/j.knosys.2024.111629293:COnline publication date: 7-Jun-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111629
Ben Said AErradi A(2022)Spatiotemporal Tensor Completion for Improved Urban Traffic ImputationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.306299923:7(6836-6849)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/TITS.2021.3062999
McNeil MZhang LBogdanov PZhu FChin Ooi BMiao CWang HSkrypnyk IHsu WChawla S(2021)Temporal Graph Signal DecompositionProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining10.1145/3447548.3467379(1191-1201)Online publication date: 14-Aug-2021
https://dl.acm.org/doi/10.1145/3447548.3467379
Show More Cited By

Index Terms

ePeriodicity: Mining Event Periodicity from Incomplete Observations
1. Information systems
  1. Information systems applications
    1. Data mining

Index terms have been assigned to the content through auto-classification.

Recommendations

Mining event periodicity from incomplete observations
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining

Advanced technology in GPS and sensors enables us to track physical events, such as human movements and facility usage. Periodicity analysis from the recorded data is an important data mining task which provides useful insights into the physical events ...
Updating beliefs with incomplete observations

Currently, there is renewed interest in the problem, raised by Shafer in 1985, of updating probabilities when observations are incomplete (or set-valued). This is a fundamental problem in general, and of particular interest for Bayesian networks. ...
Online periodicity mining

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 27, Issue 5

May 2015

315 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Iqbal MPrayitno APao HMukhlash I(2024)Mining fuzzy local periodic activity pattern for Smart home applicationsKnowledge-Based Systems10.1016/j.knosys.2024.111629293:COnline publication date: 7-Jun-2024
https://dl.acm.org/doi/10.1016/j.knosys.2024.111629
Ben Said AErradi A(2022)Spatiotemporal Tensor Completion for Improved Urban Traffic ImputationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.306299923:7(6836-6849)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/TITS.2021.3062999
McNeil MZhang LBogdanov PZhu FChin Ooi BMiao CWang HSkrypnyk IHsu WChawla S(2021)Temporal Graph Signal DecompositionProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining10.1145/3447548.3467379(1191-1201)Online publication date: 14-Aug-2021
https://dl.acm.org/doi/10.1145/3447548.3467379
Zhang LZhang WMcNeil MChengwang NMatteson DBogdanov P(2021)AURORA: A Unified fRamework fOR Anomaly detection on multivariate time seriesData Mining and Knowledge Discovery10.1007/s10618-021-00771-735:5(1882-1905)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10618-021-00771-7
Huang JJaysawal BWang C(2021)Mining full, inner and tail periodic patterns with perfect, imperfect and asynchronous periodicity simultaneouslyData Mining and Knowledge Discovery10.1007/s10618-021-00753-935:4(1225-1257)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10618-021-00753-9
Shi TJi GYu ZZhao B(2021)Collective periodic pattern discovery for understanding human mobilityCluster Computing10.1007/s10586-020-03220-024:1(141-157)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10586-020-03220-0
Wu HHe WLiu QYang Y(2020)Discovery of Chasing Patterns in Trajectory DataDatabase Systems for Advanced Applications. DASFAA 2020 International Workshops10.1007/978-3-030-59413-8_4(47-59)Online publication date: 24-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-59413-8_4
Pierson EAlthoff TLeskovec JChampin PGandon FMédini LLalmas MIpeirotis P(2018)Modeling Individual Cyclic Variation in Human BehaviorProceedings of the 2018 World Wide Web Conference10.1145/3178876.3186052(107-116)Online publication date: 10-Apr-2018
https://dl.acm.org/doi/10.1145/3178876.3186052
Yuan QShang JCao XZhang CGeng XHan JLim EWinslett MSanderson MFu ASun JCulpepper SLo EHo JDonato DAgrawal RZheng YCastillo CSun ATseng VLi C(2017)Detecting Multiple Periods and Periodic Patterns in Event Time SequencesProceedings of the 2017 ACM on Conference on Information and Knowledge Management10.1145/3132847.3133027(617-626)Online publication date: 6-Nov-2017
https://dl.acm.org/doi/10.1145/3132847.3133027
Ghosh ALucas CSarkar RLim EWinslett MSanderson MFu ASun JCulpepper SLo EHo JDonato DAgrawal RZheng YCastillo CSun ATseng VLi C(2017)Finding Periodic Discrete Events in Noisy StreamsProceedings of the 2017 ACM on Conference on Information and Knowledge Management10.1145/3132847.3132981(627-636)Online publication date: 6-Nov-2017
https://dl.acm.org/doi/10.1145/3132847.3132981

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents