Spatial Data Mining by Decision Trees

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.

• S. Oujdi
• H. Belbachir

• C4.5 Algorithm
• Decision trees
• S-CART
• Spatial data mining.

[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.