臺灣博碩士論文加值系統

時空間資料的頻繁樣式探勘嘗試找出未知的、人們可能覺得有趣的或有用的事件序列，這些事件序列裡的各個事件發生在特定的時間間格內，而且在地理上彼此的座落位置相近。過去的研究使用切割原始資料或是不完整的資料表示方法來進行資料探勘，也因此忽略存在於原始資料中的某些空間關聯性。再者，傳統的頻繁序列探勘方法並不適用於非交易形式的時空間資料。在這篇論文我們指出時空間資料的空間關聯性會因為不適當的資料表示方式而消失，並提出了一個直觀的時空間頻繁樣式探勘方法。論文最後我們利用兩個真實世界資料做犯罪型態的個案研究。

Spatiotemporal pattern mining tried to discover unknown, potentially interesting and useful event sequences where events occur within a specific time interval and locate geographic close to each others. Previous works use partition or ill-defined representation of spatial objects and neglect some spatial properties exist in original spatiotemporal data. Moreover, traditional sequential pattern mining methods don't suit the non-transactional spatialtemporal database. In this paper we expose the disappearance of spatial correlation due to improper data representation and propose a naive approach to mine frequent sequential spatiotemporal pattern. The end of the paper is a case study of crime pattern analysis.

中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Temporal Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Spatial Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Spatiotemporal Data Mining . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 R-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 STFPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Frequent Spatiotemporal Pattern Mining . . . . . . . . . . . . . . . . . 13
3.3 Pruning: Duration Check . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Experimental Results: Case Study of Crime Pattern Analysis . . . . . . . . . 22
4.1 Philadelphia Police Part One Crime Incidents . . . . . . . . . . . . . . 22
4.2 SpotCrime Crime Map Historical Dataset . . . . . . . . . . . . . . . . . 23
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

[1] R. Agrawal, C. Faloutsos, and A. Swami, “Efficient Similarity
Search In Sequence Databases, Proceedings of the 4th International
Conference on Foundations of Data Organization and Algorithms,
pp. 69–84, 1993.
[2] R. Agrawal, K. Lin, H. Sawhney, and K. Shim, “Fast Similarity
Search in the Presence of Noise, Scaling, and Translation in Time-
Series Databases, International Conference on Very Large Data
Bases, pp. 490–501, 1995.
[3] R. Agrawal and R. Srikant, “Fast algorithms for mining association
rules, Proceedings of the 20th International Conference on Very
Large Data Bases, pp. 487–499, 1994.
[4] R. Agrawal and R. Srikant, “Mining Sequential Patterns, Proceed-
ings of the Eleventh International Conference on Data Engineering,
pp. 3–14, 1995.
[5] G. Andrienko, D. Malerba, M. May, and M. Teisseire, “Min-
ing spatio-temporal data, Journal of Intelligent Information Sys-tems:pp. 187–190, 2006.
[6] M. Azim, A. Kumarappah, S. Bhavsar, S. Backus, and G. Arhon-
ditsis, “Detection of the Spatiotemporal Trends of Mercury in Lake
Erie Fish Communities: A Bayesian Approach, Environmental Sci-
ence and Technology:pp. 2217–2226, 2011.
[7] V. Barnett and T. Lewis, Outliers in statistical data, 1978.
[8] D. Birant and A. Kut, “ST-DBSCAN: An algorithm for clustering
spatial-temporal data, Data and Knowledge Engineering, 2007.
[9] T. Bittner, “Rough Sets in Spatio-Temporal Data Mining, Inter-
national Workshop on Temporal, Spatial, and Spatio-Temporal Data
Mining, pp. 89–104, 2000.
[10] K. Chan and A. Fu, “Efficient Time Series Matching by Wavelets,
International Conference on Data Engineering, pp. 126–133, 1999.
[11] N. Cressie, Statistics for Spatial Data, 1993.
[12] G. Das, K. Lin, H. Mannila, G. Renganathan, and P. Smyth, “Rule
Discovery From Time Series, Knowledge Discovery and Data Min-
ing, pp. 16–22, 1998.
[13] A. R. Ganguly and K. Steinhaeuser, “Data Mining for Climate
Change and Impacts, Proceedings of the IEEE International Con-
ference on Data Mining Workshops, pp. 385–394, 2008.
[14] X. Ge and P. Smyth, “Deformable Markov model templates for time-
series pattern matching, Proceedings of the sixth ACM SIGKDD
international conference on Knowledge discovery and data mining,
pp. 81–90, 2000.
[15] R. Güting, “An Introduction to Spatial Database Systems, The
International Journal on Very Large Data Bases:pp. 357–399, 1994.
[16] A. Guttman, “R-trees: A Dynamic Index Structure for Spatial
Searching, Proceedings of the 1984 ACM SIGMOD International
Conference on Management of Data, pp. 47–57, 1984.
[17] M. Halkidi, Y. Batistakis, and M. Vazirgiannis, “Clustering algo-
rithms and validity measures, Proceedings of the Thirteenth Inter-
national Conference on Scientific and Statistical Database Manage-
ment, pp. 3–22, 2001.
[18] J. Han, M. Kamber, and A. Tung, “Spatial Clustering Methods in
Data Mining: A Survey, Geographic Data Mining and Knowledge
Discovery, pp. 1–29, 2001.
[19] D. Hawkins, Identification of outliers, 1980.
[20] Y. Huang, C. Chen, and P. Dong, “Modeling Herds and Their
Evolvements from Trajectory Data, Geographic Information Sci-
ence, pp. 90–105, 2008.
[21] E. Keogh and M. Pazzani, “An Enhanced Representation of Time
Series Which Allows Fast and Accurate Classification, Clustering
and Relevance Feedback, Knowledge Discovery and Data Mining,
pp. 239–243, 1998.
[22] K. Koperski and J. Han, “Discovery of Spatial Association Rules in
Geographic Information Databases, Proceedings of the 4th Inter-
national Symposium on Advances in Spatial Databases, pp. 47–66,
1995.
[23] K. Lang, B. Pearlmutter, and R. Price, “Results of the Abbadingo
One DFA Learning Competition and a New Evidence-Driven State
Merging Algorithm, International Conference on Grammatical In-
ference, pp. 1–12, 1998.
[24] Y. Morimoto, “Mining Frequent Neighboring Class Sets in Spatial
Databases, Proceedings of the Seventh ACM SIGKDD Interna-
tional Conference on Knowledge Discovery and Data Mining, pp.
353–358, 2001.
[25] K. Rao, A. Govardhan, and K. Rao, “Spatiotemporal Data Mining:
Issues, Tasks And Applications, International Journal of Computer
Science and Engineering Survey, 2012.
[26] J. Rocha, V. Times, G. Oliveira, L. Alvares, and V. Bogorny, “DB-
SMoT: A direction-based spatio-temporal clustering method, IEEE
International Conference on Intelligent Systems, pp. 114–119, 2010.
[27] P. Smyth, “Clustering Sequences with Hidden Markov Models,
Advances in Neural Information Processing Systems, pp. 648–654,
1997.
[28] P. Smyth, “Probabilistic Model-Based Clustering of Multivariate
and Sequential Data, Proceedings of Artificial Intelligence and
Statistics, pp. 299–304, 1999.
[29] R. Trasarti, F. Pinelli, M. Nanni, , and F. Giannotti, “Mining
Mobility User Profiles for Car Pooling, Proceedings of the 17th
ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, pp. 1190–1198, 2011.
[30] F. Verhein and S. Chawla, “Mining Spatio-temporal Association
Rules, Sources, Sinks, Stationary Regions and Thoroughfares in
Object Mobility Databases, Database Systems for Advanced Ap-
plications, pp. 187–201, 2006.
[31] M. Vieira, V. Frias-Martinez, N. Oliver, and E. Frias-Martinez,
“Characterizing Dense Urban Areas from Mobile Phone-Call Data:
Discovery and Social Dynamics, Proceedings of the 2010 IEEE Sec-
ond International Conference on Social Computing, pp. 241–248,
2010.