Spatial Data Mining by Decision Trees

Authors: S. Oujdi, H. Belbachir

Abstract:

Existing methods of data mining cannot be applied on spatial data because they require spatial specificity consideration, as spatial relationships. This paper focuses on the classification with decision trees, which are one of the data mining techniques. We propose an extension of the C4.5 algorithm for spatial data, based on two different approaches Join materialization and Querying on the fly the different tables. Similar works have been done on these two main approaches, the first - Join materialization - favors the processing time in spite of memory space, whereas the second - Querying on the fly different tables- promotes memory space despite of the processing time. The modified C4.5 algorithm requires three entries tables: a target table, a neighbor table, and a spatial index join that contains the possible spatial relationship among the objects in the target table and those in the neighbor table. Thus, the proposed algorithms are applied to a spatial data pattern in the accidentology domain. A comparative study of our approach with other works of classification by spatial decision trees will be detailed.

Keywords: C4.5 Algorithm, Decision trees, S-CART, Spatial data mining.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1097439

References:

[1] Chelghoum N, Zeitouni K, “Datamining spatial un problème de datamining multi-tables”, Prism.France, Université de Versailles, 2004, Vol.14 N°02, pp.129-145.
[2] Chelghoum N, Zeitouni K., “Extension du projet TOPASE par la prise en compte des interactions entre le réseau viaire et l’environnement urbain”, Convention PRISM-CERTU, Juillet 2004.
[3] Chelghoum N., Zeitouni K, Laugier T., Fiandrino A., Loubersac L., “Fouille de données spatiales - Approche basée sur la programmation logique inductive”, EGC 2006, Edition CEPADUES, Lille,Janvier 2006.
[4] Chelghoum N., Zeitouni K. “Mise en oeuvre des méthodes de fouille de données spatiales : Alternatives et performances”, EGC 2004, Clermont- Ferrand, January 2004.
[5] Chelghoum N., Zeitouni K., Boulmakoul A., “Fouille de données spatiales par arbre de décision multi-thèmes”, EGC 2002, Montpellier, January 2002.
[6] Cliff A.D., Ord J.K., “Spatial autocorrelation”, Pion, London, 1973.
[7] Ester M., Frommelt A., Kriegel H.-P., Sander J., “Algorithms for Characterization and Trend Detection in Spatial Databases“, Proc. 4th Int. Conf. on Knowledge Discovery and Data Mining, New York, NY, 1998.
[8] Ester M., Kriegel H.P., Sander J., Xu X., “A density-Based algorithm for discovering clusters in lager spatial databases with noise”, In proceeding of second international conference on knowledge discovery and data mining, Portland, 1996, pp 226-231.
[9] Franklin, C, “An introduction to geographic information systems: linking maps to databases. Database”, vol. 15, no. 2, pp.13--21, 1992.
[10] Gatrell A., Bailey T., Diggle P., Rowlingson B., “Spatial point pattern analysis and its application in geographical epidemiology”, Transactions of the Institute of British Geographers, n° 21, 1996, pp. 256-274.
[11] G.Manikandan et al, “Mining of spatial co-location pattern implementation by fp growth”, European Journal of Scientific Research ISSN 1450-216X Vol.68 No.3 (2012), pp. 352-366.
[12] ImasSukaesihSitanggang, RazaliYaakob, Norwati Mustapha, Ahmad Ainuddin B Nuruddin, “An Extended ID3 Decision Tree Algorithm for Spatial Data”, Published in: Spatial Data Mining and Geographical Knowledge Services (ICSDM), 2011 IEEE International Conference on, June 29 2011 - July 1 2011, pages: 48 – 53.
[13] Shekhar Sh. and Huang Y., “Discovering Spatial Co-location Patterns: A Summary of Results”, 7th Int. Symposium on Spatial and Temporal Databases (SSTD), Springer-Verlag, Lecture Notes in Computer Science, July 2001.
[14] R. Marghoubi, A. Boulmakoul, K. Zeitouni, “Utilisation des treillis de Galois pour l’extraction et la visualisation des règles d’association spatiales”, Faculty of sciences and technology of Mohamadia (FTSM).
[15] Zeitouni Karine. “Mémoire d’habilitation à diriger des recherches : Analyse et extraction de connaissances des bases de données spatiotemporelles”. Informatique. France : University of Versailles Saint-Quentin-en-Yvelines, December 2006.