A multi-relational approach to spatial classification

ABSTRACT

Spatial classification is the task of learning models to predict class labels based on the features of entities as well as the spatial relationships to other entities and their features. Spatial data can be represented as multi-relational data, however it presents novel challenges not present in multi-relational problems. One such problem is that spatial relationships are embedded in space, unknown a priori, and it is part of the algorithm's task to determine which relationships are important and what properties to consider. In order to determine when two entities are spatially related in an adaptive and non-parametric way, we propose a Voronoi-based neighbourhood definition upon which spatial literals can be built. Properties of these neighbourhoods also need to be described and used for classification purposes. Non-spatial aggregation literals already exist within the multi-relational framework, but are not sufficient for comprehensive spatial classification. A formal set of additions to the multi-relational data mining framework is proposed, to be able to represent spatial aggregations as well as spatial features and literals. These additions allow for capturing more complex interactions and spatial occurrences such as spatial trends. In order to more efficiently perform the rule learning and exploit powerful multi-processor machines, a scalable parallelized method capable of reducing the runtime by several factors is presented. The method is compared against existing methods by experimental evaluation on a real world crime dataset which demonstrate the importance of the neighbourhood definition and the advantages of parallelization.

REFERENCES

• 1: Nabil R. Adam , Vandana Pursnani Janeja , Vijayalakshmi Atluri, Neighborhood based detection of anomalies in high dimensional spatio-temporal sensor datasets, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968020]
• 2: Appice, A.; Ceci, M.; Lanza, A.: Discovery of spatial association rules in geo-referenced census data: a relational mining approach, In Proceedings of Intelligent Data Analysis (2003)
• 3: Bembenik, R.; Rybinski, H.:"Mining Spatial Association Rules with no Distance Parameter, Advances in Soft Computing, Vol. 35 (2006)
• 4: Ceci, M.; Appice, A.; Malerba, D.:"Spatial Associative Classification at Different Levels of Granularity: A Probabilistic Approach, Lecture Notes in Computer Science, Volume 3202 (2004)
• 5: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 6: Chelghoum, N., Zeitouni K.:"Spatial Data Mining Implementation - Alternatives And Performances, GeoInfo, pp 127--153 (2004)
• 7: Max J. Egenhofer, Reasoning about Binary Topological Relations, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.143-160, August 28-30, 1991
• 8: Estivill-Castro, V.; Lee, I.: Argument free clustering for large spatial point-data sets via boundary extraction from Delaunay Diagram, Computers, Environment and Urban Systems, Vol. 26, No 4, pp. 315--334 (July 2002 )
• 9: Richard Frank , Flavia Moser , Martin Ester, A Method for Multi-relational Classification Using Single and Multi-feature Aggregation Functions, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_43]
• 10: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 11: Arno J. Knobbe , Arno Siebes , Bart Marseille, Involving Aggregate Functions in Multi-relational Search, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.287-298, August 19-23, 2002
• 12: Longley, P.A.; Goodchild, M.F.; Maguire, D.J; Rhind, D.W.: Geographical Information Systems: Principles, Techniques, Applications and Management, Wiley, 2nd Edition (1999)
• 13: Miller, H. J.:"Tobler's First Law and spatial analysis, Annals of the Association of American Geographers, 94. (2004)
• 14: Ohyama ,T.:"Some Voronoi diagrams that consider consumer behavior analysis, In Industrial Mathematics of the Japan Journal of Industrial and Applied Mathematics (2005)
• 15: Papadias, D., Theodoridis, Y.: Spatial Relations, Minimum Bounding Rectangles, and Spatial Data Structures, International Journal of Geographic Information Science Volume 11, Issue 2 (1997)
• 16: J. Ross Quinlan , R. Mike Cameron-Jones, FOIL: A Midterm Report, Proceedings of the European Conference on Machine Learning, p.3-20, April 05-07, 1993
• 17: M. Yasmina Santos , L. Alfredo Amaral, Geo-spatial data mining in the analysis of a demographic database, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.5, p.374-384, May 2005 [doi>10.1007/s00500-004-0417-0]
• 18: Schlossberg, M.: GIS, The US Census And Neighbourhood Scale Analysis, Planning, Practice&Research, Vol. 18, No. 2--3 (2003)
• 19: Taskar, B., Segal, E., and Koller, D.: Probabilistic classification and clustering in relational data, In Proceedings IJCAI (2001)
• 20: Tobler, W.R.: A computer movie simulating urban growth in the Detroit region, In Economic Geography, Volume 46 (1970)
• 21: Vens, C.; Van Assche, A.; Blockeel, H.; Dzeroski, S.:"First order random forests with complex aggregates, In Proceedings of ILP (2004)
• 22: Xiaoxin Yin , Jiawei Han , Jiong Yang , Philip S. Yu, CrossMine: Efficient Classification Across Multiple Database Relations, Proceedings of the 20th International Conference on Data Engineering, p.399, March 30-April 02, 2004

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
aggregation, parallelization, spatial classification, spatial data mining