進階搜尋


下載電子全文  
系統識別號 U0026-1007201916150100
論文名稱(中文) 流行病演變下的時空間變動樣式探勘
論文名稱(英文) Mining Spatial-Temporal Fluctuating Patterns for Epidemic Evolution
校院名稱 成功大學
系所名稱(中) 醫學資訊研究所
系所名稱(英) Institute of Medical Informatics
學年度 107
學期 2
出版年 108
研究生(中文) 歐政寬
研究生(英文) Cheng-Kuan Ou
學號 q56064014
學位類別 碩士
語文別 英文
論文頁數 44頁
口試委員 指導教授-莊坤達
口試委員-陳朝鈞
口試委員-李政德
中文關鍵字 時空間資料探勘  樣式探勘  變動樣式 
英文關鍵字 Spatial-Temporal Data Mining  Pattern Mining  Fluctuating Patterns 
學科別分類
中文摘要 為了從時空間資料中發現潛在的變動和有用的特徵集,我們在時空間資料探勘中探索了一個新的問題稱為「時空間變動樣式」(簡稱為STFs)。這些特徵集通常具有隨時間演進而變化的特性。隨著「時空間變動樣式」的挖掘,我們可以發現樣式的轉變點,並且更進一步地進行即時地異常檢測及轉型發掘。舉例來說,「時空間變動樣式」的發現能夠在傳染病爆發期間找出可能的病毒變異現象,並提供政府對疫情控制的有用線索,進而採取有效的防疫措施。

而就我們目前所知,這樣關注於時間變動的「時空間變動樣式」仍未被探索,在過去大多的研究關注於頻繁樣式這類的樣式,並沒有適當的考量時間變動因子。因此,在我們的研究中,我們開發了一個新的系統框架,使用時空間資料探勘技術來探索變動樣式。然而,以傳統的方法進行變動樣式的探勘是相當耗費時間的,為了加速時空間探勘過程和動態地更新變動樣式,我們開發了下封閉結構的聯合探勘演算法,使能在實際應用中達到有效地「時空間變動樣式」探勘。
最後,我們實驗在真實的流行病時空數據集中,從實驗結果顯示,我們所提出的框架不僅可以有效率的挖掘「時空間變動樣式」,變動樣式在實際應用中也是實用且有效的。
英文摘要 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
參考文獻 [1] 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.
[2] 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.
[3] 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.
[4] M. M. Gaber, A. Zaslavsky, and S. Krishnaswamy, “Mining data streams: a review,” ACM Sigmod Record, vol. 34, no. 2, pp. 18–26, 2005.
[5] B. Liu, W. Hsu, H. Han, and Y. Xia, “Mining changes for real-life applications,” in Data Warehousing and Knowledge Discovery (DaWaK), 2000.
[6] C. C. Aggarwal and J. Han, Frequent Pattern Mining. Springer, 2014.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] T. Bittner, “Rough sets in spatio-temporal data mining,” in Temporal, Spatial, and Spatio- Temporal Data Mining (TSDM), 2000.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] 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.
[29] L. Rokach and O. Maimon, “Clustering methods,” in The Data Mining and Knowledge Discovery Handbook. Springer, 2005.
[30] D. Reynolds, “Gaussian mixture models,” Encyclopedia of Biometrics, no. G, pp. 827–832, 2015.
[31] M. M. Deza and E. Deza, Encyclopedia of distances. Springer, 2009.
[32] 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.
[33] 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.
[34] 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.
[35] 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.
[36] 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.
[37] 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.
[38] R. Alves, O. Belo, and J. Ribeiro, “Mining top-k multidimensional gradients,” in Data Warehousing and Knowledge Discovery (DaWaK), 2007.
[39] 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.
[40] 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.
[41] 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.
[42] 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.
[43] 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.
[44] C. Tsai and Y. Shieh, “A change detection method for sequential patterns,” Decision Support Systems, vol. 46, no. 2, pp. 501–511, 2009.
[45] 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.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-07-23起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-07-23起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw