Period Table Based Spatio-temporal Association Rules Mining

  • 1. State Key Lab of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;
    2. Graduate University of Chinese Academy of Sciences, Beijing 100049, China

Received date: 2010-11-16

  Revised date: 2011-06-07

  Online published: 2011-08-23


As periodical geographical phenomena cover lots of rules, geographic data mining provides a way to find out such rules. In this paper, an algorithm called PRules-Miner is designed based on period table to mine spatio-temporal association rules. Using this mining model, spatio-temporal data were reorganized from sequential dataset to period table set. And spatio-temporal association rules, which describe the tele-connected movement model of two or more objects, can be dug out through three steps: 1) Filtering disorder data in period table: we extract spatio-temporal frequent status in each row and store such status into spatio-temporal frequent item set; 2) Matching objects in the item set based on downward closure lemma and spatio-temporal topology: we match the objects in order to create the spatio-temporal association candidate set; 3) Verifying the candidate set under spatio-temporal topology to find the rules which have to satisfy the spatio-temporal support and spatio-temporal confidence. And the final rules are the spatio-temporal association rules. To check the validation of the algorithm, we use 20 years' AVHRR Product 016, which is sea surface inversion temperature data provided by PO.DAAC and the same period records of Nanjing's daily precipitation provided by National Academy of Meteorological Sciences to mine the tele-connection rules between Eastern Indo Ocean and Western Pacific Ocean Warm Pool and Nanjing's precipitation. The results show, this mining model has the following characteristics: 1) this algorithm is object-orientated and can describe geographical status independently. Thus, the final spatio-temporal association rules are not correlated with spatial scale or temporal scale. 2) The candidate item set is created by Cartesian product, and it can represent complicated spatio-temporal topology between objects. And the spatio-temporal topology can be set manually so as to find the association of none adjacent objects in spatio-temporal dimensions. After setting spatio-temporal topology, spatio-temporal association rules can be mined and validated from candidate set. In the final rules, one object's frequent status is combined with another object's frequent status with given spatio-temporal topology. Thus, the association of objects with uncertain time lag can be extracted.

Cite this article

CHAI Siyue, SU Fenzhen, ZHOU Chenghu . Period Table Based Spatio-temporal Association Rules Mining[J]. Journal of Geo-information Science, 2011 , 13(4) : 455 -464 . DOI: 10.3724/SP.J.1047.2011.00455


[1] Verhein F and Chawla S. Mining Spatio-temporal Patterns in Object Mobility Databases[J]. Data Mining and Knowledge Discovery, 2008,16(1): 5-38.

[2] Huang Y P, Kao L J and Sandnes F E. Efficient Mining of Salinity and Temperature Association Rules from ARGO Data[J]. Expert Systems with Applications, 2008,35(1-2): 59-68.

[3] Li Y, et al. Discovering Calendar-based Temporal Association Rules[J]. Data & Knowledge Engineering, 2003. 44(2): 193-218.

[4] Kalnis P, Mamoulis N and Bakiras S. On Discovering Moving Clusters in Spatio-temporal Data[J]. Advances in Spatial and Temporal Databases, 2005,364-381.

[5] Lee A J T, Chen Y A and Weng C C Ip. Mining Frequent Trajectory Patterns in Spatial-temporal Databases[J]. Information Sciences, 2009,179(13): 2218-2231.

[6] Lee J W, Paek O H and Ryu K H. Temporal Moving Pattern Mining for Location-based Service[J]. Journal of Systems and Software, 2004,73(3): 481-490.

[7] Su F, Zhou C, Lyne V, Du Y and Shi W. A Data-mining Approach to Determine the Spatio-temporal Relationship between Environmental Factors and Fish Distribution[J]. Ecological Modelling, 2004,174(4): 421-431.

[8] 孙建奇, 袁薇,高玉中. 阿拉伯半岛-北太平洋型遥相关及其与亚洲夏季风的关系[J]. 中国科学(D辑:地球科学),2008,38(6): 750-762.

[9] 张雪伍, 苏奋振, 石忆邵,等. 空间关联规则挖掘研究进展[J]. 地理科学进展,2007,26(6): 119-128.

[10] Agrawal R and Srikant R. Fast Algorithms for Mining Association Rules. 20th Int.Conf. Very Large Data Bases, Santiago de Chile, Chile, Citeseer, 1994.

[11] Han Jiawei and Kamber M. Data Mining: Concepts and Techniques[M]., San Fransisco, CA, USA: Morgan Kaufmann, 2006.

[12] 刘君强,潘云鹤,挖掘空间关联规则的前缀树算法设计与实现[J],中国图象图形学报, A辑,2003(4): 476-480.

[13] Winarko E and Roddick J F. ARMADA——An Algorithm for Discovering Richer Relative Temporal Association Rules from Interval-based Data[J]. Data & Knowledge Engineering, 2007,63(1): 76-90.

[14] Chen C H, Hsu W and Lee M L. Discovering Trends and Relationships among Rules. Database and Expert Systems Applications, Proceedings, 2009, 5690: 603-610.

[15] Lee Y J, Lee J W, Chai D J, Hwang B H and K. H. Ryu K H. Mining Temporal Interval Relational Rules from Temporal Data[J]. Journal of Systems and Software,2009,82(1): 155-167.

[16] Jabas A, Garimella R M, Ramachandram S and Soc I C. MANET Mining: Mining Temporal Association Rules. The 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA-8) and The 2008 International Conference on Intelligent Pervasive Computing (IPC-08), 2008.

[17] Beaubouef T, Petry F E and Ladner R. Spatial Data Methods and Vague Regions: A Rough Set Approach[J]. Applied Soft Computing, 2007,7(1): 425-440.

[18] Teegavarapu R S V. Estimation of Missing Precipitation Records Integrating Surface Interpolation Techniques and Spatio-temporal Association Rules[J]. Journal of Hydroinformatics, 2009,11(2): 133-146.

[19] Zaki M J. SPADE: An Efficient Algorithm for Mining Frequent Sequences[J]. Machine Learning, 2001,42(1): 31-60.

[20] Pujari K A. Data Mining Techniques[M].Universities Press,2001.

[21] Allen J F. Maintaining Knowledge about Temporal Intervals[J]. Communications of ACM,1983,26(11): 832-843

[22] Lee W J, Jiang J Y and Lee S J. Mining Fuzzy Periodic Association Rules[J]. Data & Knowledge Engineering,2008,65(3): 442-462.

[23] Ozden B, Ramaswamy S and Silberschatz A. Cyclic Association Rules 14th International Conference on Data Engineering, Orlando, FL , USA, 1998.

[24] Bembenik R and Rybiński H. Mining Spatial Association Rules with No Distance Parameter Intelligent Information Processing and Web Mining, 2006,499-508.

[25] Appice A, Berardi M, Ceci M and Malerba D. Mining and Filtering Multi-level Spatial Association Rules with ARES[J]. Foundations of Intelligent Systems, 2005,342-353.

[26] Chen J P and Tan X J. Mining Spatial Association Rules with Geostatistics. Proceedings of the 8th International Symposium on Spatial Accuracy Assessment in Natural Resources and Environmental Sciences, 2008.

[27] Qu L L and Chen Y (Eds.). An Algorithm to Improve the Effectiveness of Association Rules Mining. Harbin, Harbin Institute Technology Publishers, 2005.

[28] Kacar E and Cicekli N K. Discovering Fuzzy Spatial Association Rules. Proc. SPIE 4730, 94 (2002). doi:10.1117/12.460216

[29] Mennis J and Liu J. Mining Association Rules in Spatio-temporal Data. Proc. of the 7the Int'l Conf. on Geocomputation, 2003.

[30] Tao Y, Kollios G, Considine F. Li F and Papadias D. Spatio-temporal Aggregation Using Sketches. 20th International Conference on Data Engineering, IEEE, 2004.

[31] Agrawal R, Imieliński T and Swami A. Mining Association Rules between Sets of Items in Large Databases[J]. ACM SIGMOD Record, 1993,22(2): 207-216

[32] 薛峰,王会军,何金海.马斯克林.高压和澳大利亚高压的年际变化及其对东亚夏季风降水的影响[J].科学通报,2003,48(3): 287-291.

[33] Wang H and Fan K. Central-north China Precipitation as Reconstructed from the Qing Dynasty: Signal of the Antarctic Atmospheric Oscillation[J].Geophysical Research Letters, 2005, 32(24): 1-4.

[34] Fan K and Wang H. Antarctic Oscillation and the Dust Weather Frequency in North China[J]. Geophysical Research Letters, 2004,31: 1-4.

[35] Tan H, Dillon T, Hadzic F, Chang E and Feng L. (2006). IMB3-Miner: Mining Induced/Embedded Subtrees by Constraining the Level of Embedding[J]. Lecture Notes in Computer Science, 2006, 3918:450-461.

[36] 王秀荣, 王维国, 刘还珠,等. 北京降水特征与西太副高关系的若干统计[J]. 高原气象,2008(4): 822-829.