基于周期表的时空关联规则挖掘方法与实验

doi:10.3724/SP.J.1047.2011.00455

摘要/Abstract

摘要： 地理现象的周期性往往掩盖了许多地学规律,这也是地学数据挖掘的一个主要内容。本文以周期表设计了一种时空层次关联规则挖掘方法——PRules-Miner。模型利用周期表的表现形式对时空数据进行组织,并通过两步挖掘过程发现具有"遥相关"地理事物间的变化模式。模型算法分为3个步骤: (1)过滤周期表内无序数据:逐行地提取多周期内时空状态的频繁项,生成新的时空频繁状态表;(2)基于向下闭合引理,对时空频繁状态表中的对象进行时空拓扑匹配,得到时空关联规则候选集;(3)对于候选数据集进行时空拓扑验证,得到时空关联规则集。为证明模型算法的可靠性,应用PO.DAAC提供的20年AVHRR Product 016海表面温度遥感反演数据集和国家气象科学院提供的南京地区降水逐日数据资料,研究大洋暖池与南京降水间的时空关联规则。实践表明,这种挖掘方法具有以下特点:(1)算法基于面向对象思想,对地理对象状态进行独立描述。因此,所得时空关联规则与时空粒度无关,并能够挖掘出时空粒度不一致的地物间的关联关系。(2)算法使用笛卡尔积得到在时空拓扑阈值内匹配的时空候选集,并可以发现时域、空域均不邻接的事物间的时空关联规则,即时延不确定的地理现象的相互关联。

关键词: 数据挖掘, 关联规则, 时空数据, 层次挖掘, 周期表

Abstract: 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.

Key words: hierarchical structure, period table, data mining, association rules, spatio-temporal data

柴思跃, 苏奋振, 周成虎. 基于周期表的时空关联规则挖掘方法与实验[J]. 地球信息科学学报, 2011, 13(4): 455-464.DOI:10.3724/SP.J.1047.2011.00455

CHAI Siyue, SU Fenzhen, ZHOU Chenghu. Period Table Based Spatio-temporal Association Rules Mining[J]. , 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 8^th 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. 20^th 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.