Density based co-location pattern discovery

ABSTRACT

Co-location pattern discovery is to find classes of spatial objects that are frequently located together. For example, if two categories of businesses often locate together, they might be identified as a co-location pattern; if several biologic species frequently live in nearby places, they might be a co-location pattern. Most existing co-location pattern discovery methods are generate-and-test methods, that is, generate candidates, and test each candidate to determine whether it is a co-location pattern. In the test step, we identify instances of a candidate to obtain its prevalence. In general, instance identification is very costly. In order to reduce the computational cost of identifying instances, we propose a density based approach. We divide objects into partitions and identifying instances in dense partitions first. A dynamic upper bound of the prevalence for a candidate is maintained. If the current upper bound becomes less than a threshold, we stop identifying its instances in the remaining partitions. We prove that our approach is complete and correct in finding co-location patterns. Experimental results on real data sets show that our method outperforms a traditional approach.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: V. Estivill-Castro and I. Lee. Data mining techniques for autonomous exploration of large volumes of geo-referenced crime data. Proceedings of Geocomputation, pages 24--26, 2001.
• 3: Vladimir Estivill-Castro , Alan T. Murray, Discovering Associations in Spatial Data - An Efficient Medoid Based Approach, Proceedings of the Second Pacific-Asia Conference on Research and Development in Knowledge Discovery and Data Mining, p.110-121, April 15-17, 1998
• 4: Jaiwei Han , Krzysztof Koperski , Nebojsa Stefanovic, GeoMiner: a system prototype for spatial data mining, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.553-556, May 11-15, 1997, Tucson, Arizona, United States
• 5: 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]
• 6: Yan Huang , Shashi Shekhar , Hui Xiong, Discovering Colocation Patterns from Spatial Data Sets: A General Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.12, p.1472-1485, December 2004 [doi>10.1109/TKDE.2004.90]
• 7: Yan Huang , Hui Xiong , Shashi Shekhar , Jian Pei, Mining confident co-location rules without a support threshold, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952630]
• 8: 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]
• 9: 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
• 10: 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]
• 11: S. Shekhar and Y. Huang. Co-location rules mining: A summary of results. SSTD, 2001.
• 12: 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]
• 13: Jin Soung Yoo , Shashi Shekhar , John Smith , Julius P. Kumquat, A partial join approach for mining co-location patterns, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032258]
• 14: Xin Zhang , Nikos Mamoulis , David W. Cheung , Yutao Shou, Fast mining of spatial collocations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014095]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
co-location patterns, participation ratio, prevalence