Mining confident co-location rules without a support threshold

ABSTRACT

Mining co-location patterns from spatial databases may reveal types of spatial features likely located as neighbors in space. In this paper, we address the problem of mining confident co-location rules without a support threshold. First, we propose a novel measure called the maximal participation index. We show that every confident co-location rule corresponds to a co-location pattern with a high maximal participation index value. Second, we show that the maximal participation index is non-monotonic, and thus the conventional Apriori-like pruning does not work directly. We identify an interesting weak monotonic property for the index and develop efficient algorithms to mine confident co-location rules. An extensive performance study shows that our method is both effective and efficient for large spatial databases.

REFERENCES

• 1: R. Agarwal and R. Srikant. Fast algorithms for Mining association rules. In VLDB'94.
• 2: Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001 [doi>10.1109/69.908981]
• 3: N. Cressie. Statistics for spatial data. John Wiley and Sons, (ISBN:0471843369), 1991.
• 4: Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.67-82, August 06-09, 1995
• 5: Y. Huang, H. Xiong, S. Shekhar, and J. Pei. Mining confident co-location rules without a support threshold: A summary of results. In University of Minnesota Technical Report, 2002.
• 6: E. M. Knorr and R. T. Ng. Extraction of spatial proximity patterns by concept generalization. In KDD'96.
• 7: Krzysztof Koperski , Jiawei Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.47-66, August 06-09, 1995
• 8: Yasuhiko Morimoto, Mining frequent neighboring class sets in spatial databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.353-358, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502564]
• 9: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 10: S. Shekhar and Y. Huang. Co-location Rules Mining: A Summary of Results. In SSTD'01.
• 11: Shashi Shekhar , Chang-Tien Lu , Pusheng Zhang, Detecting graph-based spatial outliers: algorithms and applications (a summary of results), Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.371-376, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502567]
• 12: S. Shekhar, P. Schrater, W. Raju, and W. Wu. Spatial Contextual Classification and Prediction Models for Mining Geospatial Data. IEEE Transactions on Multimedia (special issue on Multimedia Databases), 2002.

INDEX TERMS

Keywords:
confident co-location rules, spatial data mining