Finding regional co-location patterns for sets of continuous variables in spatial datasets

ABSTRACT

This paper proposes a novel framework for mining regional co-location patterns with respect to sets of continuous variables in spatial datasets. The goal is to identify regions in which multiple continuous variables with values from the wings of their statistical distribution are co-located. A co-location mining framework is introduced that operates in the continuous domain and which views regional co-location mining as a clustering problem in which an externally given fitness function has to be maximized. Interestingness of co-location patterns is assessed using products of z-scores of the relevant continuous variables. The proposed framework is evaluated by a domain expert in a case study that analyzes Arsenic contamination in Texas water wells centering on regional co-location patterns. Our approach is able to identify known and unknown regional co-location patterns, and different sets of algorithm parameters lead to the characterization of Arsenic distribution at different scales. Moreover, inconsistent colocation sets are found for regions in South Texas and West Texas that can be clearly attributed to geological differences in the two regions, emphasizing the need for regional co-location mining techniques. Moreover, a novel, prototype-based region discovery algorithm named CLEVER is introduced that uses randomized hill climbing, and searches a variable number of clusters and larger neighborhood sizes.

REFERENCES

• 1: Elke Achtert , Christian Böhm , Hans-Peter Kriegel , Peer Kröger , Arthur Zimek, Deriving quantitative models for correlation clusters, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150408]
• 2: C. C. Aggarwal , C. Procopiuc , P. S. Yu, Finding Localized Associations in Market Basket Data, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.51-62, January 2002 [doi>10.1109/69.979972]
• 3: Yonatan Aumann , Yehuda Lindell, A statistical theory for quantitative association rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.261-270, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312243]
• 4: Brimicombe, A. J. 2005. Cluster Detection in Point Event Data Having Tendency Towards Spatially Repetitive Events. In the 8th Intl. Conf. on GeoComputation.
• 5: Toon Calders , Bart Goethals , Szymon Jaroszewicz, Mining rank-correlated sets of numerical attributes, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150417]
• 6: Choo, J., Jiamthapthaksin, R., Chen, C., Celepcikay, O., Giusti, C., and Eick, C. F. 2007. MOSAIC: A Proximity Graph Approach to Agglomerative Clustering. In Proc. of the 9th Intl. Conf. on Data Warehousing and Knowledge Discovery. DaWaK' 07.
• 7: Cougar^2: Data Mining and Machine Learning Framework, https://cougarsquared.dev.java.net/.
• 8: Data Mining and Machine Learning Group, University of Houston, http://www.tlc2.uh.edu/dmmlg.
• 9: Wei Ding , Christoph F. Eick , Jing Wang , Xiaojing Yuan, A Framework for Regional Association Rule Mining in Spatial Datasets, Proceedings of the Sixth International Conference on Data Mining, p.851-856, December 18-22, 2006 [doi>10.1109/ICDM.2006.5]
• 10: Ding, W., Jiamthapthaksin, R., Parmar, R., Jiang, D., Stepinski, T., and Eick, C. F. 2008. Towards Region Discovery in Spatial Datasets. In Proc. of Pacific-Asia Conference on Knowledge Discovery and Data Mining (Osaka, Japan, May 2008). PAKDD '08.
• 11: Eick, C. F., Vaezian, B., Jiang, D., and Wang, J. 2006. Discovering of Interesting Regions in Spatial Data Sets Using Supervised Clustering. In Proc. of the 10th European Conference on Principles of Data Mining and Knowledge Discovery. PKDD '06.
• 12: Christoph F. Eick , Nidal Zeidat , Zhenghong Zhao, Supervised Clustering " Algorithms and Benefits, Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence, p.774-776, November 15-17, 2004 [doi>10.1109/ICTAI.2004.111]
• 13: Getis, A., and Ord, J. K. 1996. Local Spatial Statistics: an Overview. In Spatial analysis: modeling in a GIS environment, Cambridge, GeoInformation International. (Cambridge, 1996), 261--277.
• 14: Yan Huang , Jian Pei , Hui Xiong, Mining Co-Location Patterns with Rare Events from Spatial Data Sets, Geoinformatica, v.10 n.3, p.239-260, September 2006 [doi>10.1007/s10707-006-9827-8]
• 15: Yan Huang , Pusheng Zhang, On the Relationships between Clustering and Spatial Co-location Pattern Mining, Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence, p.513-522, November 13-15, 2006 [doi>10.1109/ICTAI.2006.91]
• 16: Jaroszewicz, S. 2008. Minimum Variance Associations---Discovering Relationships in Numerical Data. In Proc. of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, (Osaka, Japan, May 2008). PAKDD '08.
• 17: Kaufman, L., and Rousseeuw, P. J. 2005. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons, New Jersey.
• 18: Kulldorff, M. 2001. Prospective Time Periodic Geographical Disease Surveillance Using a Scan Statistic. Journal of the Royal Statistical Society Series A, 164, 6--72.
• 19: Lloyd, S. P. 1982. Least Squares Quantization in PCM. IEEE Trans. on Information Theory, 28, 128--137.
• 20: 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
• 21: Ord, J. K., and Getis, 1995. A. Local Spatial Autocorrelation Statistics: Distributional Issues and an Application. Geographical Analysis, 27(4), 286--306.
• 22: Scanlon, B. R., Nicot, J. P. et al. 2005. Evaluation of Arsenic Contamination in Texas. Technical report prepared for TCEQ, under contract no. UT-08-5-70828.
• 23: Shashi Shekhar , Yan Huang, Discovering Spatial Co-location Patterns: A Summary of Results, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.236-256, July 12-15, 2001
• 24: Smedley, P. L., and Kinniburgh, D. G. 2002. A Review of the Source, Behavior and Distribution of Arsenic in Natural Waters. Applied Geochemistry 17, 517--568.
• 25: Smith, A. H. et al. 1992. Cancer Risks From Arsenic in Drinking Water. Environmental Health Perspectives, 97, 259--267.
• 26: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, ACM SIGMOD Record, v.25 n.2, p.1-12, June 1996
• 27: Texas Water Development Board, http://www.twdb.state.tx.us/home/index.asp
• 28: Xiong, H., Shekhar, S., Huang, Y., Kumar, V., Ma, X., and Yoo, J. S. 2004. A Framework for Discovering Co-location Patterns in Data Sets with Extended Spatial Objects. In Proc. of SIAM Intl. Conf. on Data Mining (SDM).
• 29: Jin Soung Yoo , Shashi Shekhar, A Joinless Approach for Mining Spatial Colocation Patterns, IEEE Transactions on Knowledge and Data Engineering, v.18 n.10, p.1323-1337, October 2006 [doi>10.1109/TKDE.2006.150]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS; Data mining

General Terms:
Algorithms, Experimentation

Keywords:
clustering, finding associations between continuous variables, regional co-location mining, regional knowledge discovery, spatial data mining