||Mining Spatial-Temporal Fluctuating Patterns for Epidemic Evolution
||Institute of Medical Informatics
Spatial-Temporal Data Mining
In this thesis, we explore a new mining paradigm, called Spatial-Temporal Fluctuating Patterns (abbreviated as STFs), to discover potentially fluctuating and useful feature sets from spatial-temporal data. These feature sets have some properties which are variant as time advances. Once STFs are discovered, we can find the turning points of patterns, which enables anomaly detection and transformation discovery over time. For example, the discovery of STFs possibly can figure out the phenomenon of virus variation during the epidemic outbreak, further providing the government clues for the epidemic control.
However, to the best of our knowledge, such temporal fluctuation of the spatial-temporal pattern is left unexplored thus far. Most of the previous work usually attempts to capture the frequent patterns, but the temporal fluctuating factor of frequent patterns is not seriously considered by these studies. Consequently, we devise a novel STF mining system framework. However, using spatial-temporal mining techniques proposed in previous researches is time-consuming in our work. Therefore, we develop a union-based mining with downward-closure structure to speed up the spatial-temporal mining process and dynamically compute fluctuating patterns. As shown in our experimental studies, the proposed framework can efficiently discover STFs on a real epidemic disease dataset, showing its prominent advantages to be utilized in real applications.
中文摘要 .......... i
Abstract .......... ii
Acknowledgment .......... iii
Contents .......... iv
List of Tables .......... vi
List of Figures .......... vii
1 Introduction .......... 1
1.1 Background .......... 1
1.2 Motivation .......... 2
1.3 Organization .......... 4
2 Related Work .......... 5
2.1 Spatial-Temporal Pattern Mining .......... 5
2.2 Fluctuation of Patterns .......... 7
3 Preliminaries .......... 8
3.1 Problem Formulation .......... 8
3.2 Framework Overview .......... 13
4 Mining Spatial-Temporal Fluctuating Patterns .......... 14
4.1 Naive Generation on Spatial Mining(NS) .......... 14
4.2 Downward-Closure Generation on Spatial Mining(DS) .......... 16
4.3 Naive Generation on Temporal Fluctuating Mining(NT) .......... 21
4.4 Unik Generation on Temporal Fluctuating Mining(UT) .......... 22
4.5 Spatial-Temporal Fluctuating Patterns (STFs) Discovery .......... 26
5 Experimental Results .......... 28
5.1 Experimental Setup .......... 28
5.1.1 Dataset Description .......... 28
5.1.2 Competitors and Evaluation Metric .......... 29
5.2 Performance Evaluation .......... 29
5.2.1 Effect of spatial constraint .......... 29
5.2.2 Effect of temporal constraint .......... 30
5.2.3 The reduction of smallest circle checking .......... 31
5.2.4 Effect of top-k .......... 32
5.2.5 Effect of event quantity .......... 33
5.2.6 Effect of feature quantity .......... 33
5.2.7 Effect of region density .......... 34
5.2.8 Effect of memory usage .......... 35
5.3 Results of STFs Mining .......... 36
6 Conclusions .......... 39
Bibliography .......... 40
 J. Yu, W.-S. Ku, M.-T. Sun, and H. Lu, “An RFID and particle filter-based indoor spatial query evaluation system,” in Proceedings of the 16th International Conference on Extending Database Technology (EDBT), 2013.
 H. Chen, W. Chung, J. J. Xu, G. Wang, Y. Qin, and M. Chau, “Crime data mining: a general framework and some examples,” IEEE Computer, vol. 37, no. 4, pp. 50–56, 2004.
 N. B ́echet, P. Cellier, T. Charnois, B. Cr ́emilleux, and M. Jaulent, “Sequential pattern mining to discover relations between genes and rare diseases,” in Proceedings of the 25th IEEE CBMS International Symposium on Computer-Based Medical Systems, 2012.
 M. M. Gaber, A. Zaslavsky, and S. Krishnaswamy, “Mining data streams: a review,” ACM Sigmod Record, vol. 34, no. 2, pp. 18–26, 2005.
 B. Liu, W. Hsu, H. Han, and Y. Xia, “Mining changes for real-life applications,” in Data Warehousing and Knowledge Discovery (DaWaK), 2000.
 C. C. Aggarwal and J. Han, Frequent Pattern Mining. Springer, 2014.
 F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, “Trajectory pattern mining,” in
Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007.
 Y. Liu, Y. Zhao, L. Chen, J. Pei, and J. Han, “Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 11, pp. 2138–2149, 2012.
 H. Cao, N. Mamoulis, and D. W. Cheung, “Discovery of periodic patterns in spatiotemporal sequences,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 4, pp. 453–467, 2007.
 N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao, and D. W. Cheung, “Mining, indexing, and querying historical spatiotemporal data,” in Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004.
 Z. Li, B. Ding, J. Han, R. Kays, and P. Nye, “Mining periodic behaviors for moving objects,” in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010.
 H. Jeung, Q. Liu, H. T. Shen, and X. Zhou, “A hybrid prediction model for moving objects,” in Proceedings of the 24th International Conference on Data Engineering (ICDE), 2008.
 Y. Tao, C. Faloutsos, D. Papadias, and B. Liu, “Prediction and indexing of moving objects with unknown motion patterns,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004.
 J. Han, G. Dong, and Y. Yin, “Efficient mining of partial periodic patterns in time series database,” in Proceedings of the 15th International Conference on Data Engineering (ICDE), 1999.
 Z. Li, B. Ding, F. Wu, T. K. H. Lei, R. Kays, and M. Crofoot, “Attraction and avoidance detection from movements,” Proceedings of the VLDB Endowment, vol. 7, no. 3, pp. 157– 168, 2013.
 Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W. Ma, “Mining user similarity based on location history,” in Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008.
 K. V. Rao, A. Govardhan, and K. C. Rao, “Spatiotemporal data mining: Issues, tasks and applications,” International Journal of Computer Science & Engineering Survey, vol. 3, no. 1, pp. 39–52, 2012.
 F. Verhein and S. Chawla, “Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases,” in Database Systems for Advanced Applications (DASFAA), 2006.
 T. Bittner, “Rough sets in spatio-temporal data mining,” in Temporal, Spatial, and Spatio- Temporal Data Mining (TSDM), 2000.
 A. R. Ganguly and K. Steinhaeuser, “Data mining for climate change and impacts,” in Workshops Proceedings of the 8th IEEE International Conference on Data Mining (ICDM), 2008.
 D. Birant and A. Kut, “St-dbscan: An algorithm for clustering spatial-temporal data,” Data & Knowledge Engineering, vol. 60, no. 1, pp. 208–221, 2007.
 R. Trasarti, F. Pinelli, M. Nanni, and F. Giannotti, “Mining mobility user profiles for car pooling,” in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011.
 G. Andrienko, D. Malerba, M. May, and M. Teisseire, “Mining spatio-temporal data,” Journal of Intelligent Information Systems, vol. 27, no. 3, pp. 187–190, 2006.
 J. L. Mennis and J. W. Liu, “Mining association rules in spatio-temporal data: An analysis of urban socioeconomic and land cover change,” Transactions in GIS, vol. 9, no. 1, pp. 5–17, 2005.
 J. Gudmundsson and M. van Kreveld, “Computing longest duration flocks in trajectory data,” in Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems (SIGSPATIAL), 2006.
 H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen, “Discovery of convoys in trajectory databases,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 1068–1080, 2008.
 Z. Li, B. Ding, J. Han, and R. Kays, “Swarm: Mining relaxed temporal moving object clusters,” Proceedings of the VLDB Endowment, vol. 3, no. 1-2, pp. 723–734, 2010.
 T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu, “An efficient k-means clustering algorithm: Analysis and implementation,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 24, pp. 881–892, 2002.
 L. Rokach and O. Maimon, “Clustering methods,” in The Data Mining and Knowledge Discovery Handbook. Springer, 2005.
 D. Reynolds, “Gaussian mixture models,” Encyclopedia of Biometrics, no. G, pp. 827–832, 2015.
 M. M. Deza and E. Deza, Encyclopedia of distances. Springer, 2009.
 J. Shin, D. Shin, and D. Shin, “Predicting of abnormal behavior using hierarchical markov model based on user profile in ubiquitous environment,” in Grid and Pervasive Computing (GPC), 2013.
 L. Bergroth, H. Hakonen, and T. Raita, “A survey of longest common subsequence algorithms,” in Proceedings Seventh International Symposium on String Processing and Information Retrieval (SPIRE), 2000.
 T. Hengl, G. B. Heuvelink, M. P. Tadi ́c, and E. J. Pebesma, “Spatio-temporal prediction of daily temperatures using time-series of modis lst images,” Theoretical and Applied Climatology, vol. 107, no. 1-2, p. 265–277, 2012.
 S. Scellato, M. Musolesi, C. Mascolo, V. Latora, and A. T. Campbell, “Nextplace: A spatio-temporal prediction framework for pervasive systems,” in Pervasive Computing, 2011.
 D. Yang, E. A. Rundensteiner, and M. O. Ward, “Shared execution strategy for neighbor- based pattern mining requests over streaming windows,” ACM Transactions on Database Systems, vol. 37, no. 1, pp. 5:1–5:44, 2012.
 T. Almanie, R. Mirza, and E. Lor, “Crime prediction based on crime types and using spatial and temporal criminal hotspots,” International Journal of Data Mining & Knowledge Management Process, vol. 5, no. 4, pp. 1–19, 2015.
 R. Alves, O. Belo, and J. Ribeiro, “Mining top-k multidimensional gradients,” in Data Warehousing and Knowledge Discovery (DaWaK), 2007.
 R. Alves, J. Ribeiro, and O. Belo, “Mining significant change patterns in multidimensional spaces,” International Journal of Business Intelligence and Data Mining, vol. 4, no. 3/4, pp. 219–241, 2009.
 A. C. Hora, N. Anquetil, S. Ducasse, and M. T. Valente, “Mining system specific rules from change patterns,” in 20th Working Conference on Reverse Engineering (WCRE), 2013.
 D. Lo, G. Ramalingam, V. P. Ranganath, and K. Vaswani, “Mining quantified temporal rules: Formalism, algorithms, and evaluation,” Science of Computer Programming, vol. 77, no. 6, pp. 743–759, 2012.
 C. Ho, H. Li, F. Kuo, and S. Lee, “Incremental mining of sequential patterns over a stream sliding window,” in Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM), 2006.
 I. Li, J. Huang, and I. Liao, “Mining sequential pattern changes,” Journal of Information Science and Engineering, vol. 30, no. 4, pp. 973–990, 2014.
 C. Tsai and Y. Shieh, “A change detection method for sequential patterns,” Decision Support Systems, vol. 46, no. 2, pp. 501–511, 2009.
 R. Agrawal and R. Srikant, “Fast algorithms for mining association rules in large databases,” in Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 1994.