Présentée par : Sihem OUJDI Intitulé La fouille de données

الجمهورية الجزائرية الديمقراطية الشعبية

وزارة التعليم العالي و البحث العلمي

جامعة وهران للعلوم و التكنولوجيا محمد بوضياف

Présentée par : Sihem OUJDI

Intitulé

La fouille de données spatiales

Faculté :Mathématique et informatique

Département :Informatique

Domaine :Informatique

Filière :Informatique

Intitulé de la Formation :Ingénierie de système d’information

Année Universitaire : 2020-2021

Devant le Jury Composé de :

Membres de Jury Grade Qualité Domiciliation

Mr Sid Ahmed Rahal Pr Président USTO-MB

Mme Hafida BELBACHIR Pr Encadreur USTO-MB

Mme Safia NAIT BEHLOUL Pr Examinateur U-Oran1

Mme Samira CHOURAQUI Pr Examinateur USTO-MB

Mme Fatiha BARIGOU MCA Examinateur U-Oran1

« Les difficultés ne sont pas faites pour abattre, mais pour être

abattues » — Charles de Montalembert

Dédicace

Je dédie ce travail à mon défunt grand-père en témoignage de ma gratitude et mon profond

amour. Ce travail est le fruit d’une promesse que j’ai pu enfin tenir. Puisse Dieu Tout-

Puissant lui accorder toute Sa Miséricorde et l'accueillir en Son Vaste Paradis.

Remerciement

Tout d’abord je tiens à remercier Dieu, le tout puissant et miséricordieux, qui m’a donné la

force, l’intelligence et la patience d’accomplir ce modeste travail.

Il me sera très difficile de remercier tout le monde car c’est grâce à l’aide de nombreuses

personnes que j’ai pu mener cette thèse à son terme.

Je tiens à remercier Madame Hafida BELBACHIR, Professeur à l’Université des sciences et

de la technologie d’Oran Mohamed BOUDIAF, qui m’a encadré tout au long de cette thèse et

qui m’a fait partager ses brillantes intuitions. Je la remercie aussi pour sa gentillesse, sa

disponibilité permanente et pour les nombreux encouragements qu’elle m’a prodiguée.

J’adresse tous mes remerciements à Monsieur Sid-Ahmed RAHAL pour avoir accepté de

présider le jury de cette thèse. Je tiens également à exprimer ma gratitude au Pr. Safia NAIT

BEHLOUL, au Dr. Fatiha BARIGOU, et au Pr. Samira CHOURAQUI pour avoir accepté de

faire partie du jury en qualité d’examinateurs.

Je remercie Monsieur Faouzi BOUFARES du Laboratoire d’Informatique de Paris Nord

(LIPN) de l’Université Paris 13 pour son encadrement durant mes stages. Je le remercie

également pour ses nombreux conseils et orientations qui m’ont permis d’affiner au fur et à

mesure la ligne directrice de cette thèse. Je tiens à remercier aussi Monsieur Mustapha

LEBBAH de LIPN pour son aide et ses conseils.

Je remercie mes amis et mes collègues pour leur soutien moral tout au long de mon doctorat.

Ma profonde gratitude va tout particulièrement à mon amie Meryem BELGHOMARI pour sa

présence et ses encouragements dans les bons comme dans les mauvais moments.

Ces quelques lignes sont peu de choses pour remercier ma famille, et tout particulièrement

ma maman pour ses nombreux sacrifices. Merci à mes frères pour leurs encouragements.

J'exprime tout particulièrement ma plus grande gratitude envers mon cher époux Mahfoud El

Missoum GALFOUT pour sa générosité infinie. Merci d’avoir été présent à mes côtés, pour

l'aide que tu m'as apporté pour finir cette thèse, pour m’avoir toujours incité à continuer

malgré les difficultés, simplement merci d’être présent tout au long du chemin et surtout de

m’avoir soutenu dans tout ce que j’ai entrepris

Résumé

L'utilisation des techniques de la fouille de données classique sur les données spatiales est

complexe. Afin de pouvoir extraire des connaissances, les algorithmes de la fouille de

données spatiales doivent traiter des données sous forme de couches thématiques et

considérer en plus les relations spatiales implicites entre ces données.

Dans ce contexte nous proposons une approche basée sur les arbres de décision, plus

particulièrement sur l’algorithme C4.5.

Pour ce faire, les relations spatiales implicites sont matérialisées par des indexes de jointures

spatiales, et l’algorithme C4.5 est étendu en un algorithme dit S-C4.5.

L’expérimentation s’est faite sur un jeu de données sur les accidents de la route pour

différents cas de figures : étude d’un phénomène par un seul phénomène selon une ou

plusieurs relations spatiales, étude d’un phénomène par plusieurs autres phénomènes selon

une ou plusieurs relations spatiales. L’étude a porté sur le temps de calcul et la consommation

d’espace mémoire

Abstract

Using data mining techniques on spatial data is more complex than on classical data. To be

able to extract useful patterns, the spatial data mining algorithms must deal with the

representation of data as stack of thematic layers and, in addition to that, take into

consideration the spatial relationships that implicitly exist within these data.

In this context, we propose a decision tree-based approach that is particularly focused on the

C4.5 algorithm. To achieve this, we materialized implicit spatial relationships by using

spatial join indexes, thus, the C4.5 algorithm was extended into a new algorithm that we

named S-C4.5.

The experimentation part of our work has been done on a dataset of traffic accidents, which

was used to validate two main cases for our approaches: (1) study of a phenomenon by a

single other phenomenon according to one or multiple spatial relationships; (2) Study of a

phenomenon by multiple other phenomena according to one or multiple spatial relationships.

Our validation mainly focused on execution time and memory usage.

Sommaire

Dédicace .................................................................................................................................... 2

Remerciement ............................................................................................................................. 3

Résumé ....................................................................................................................................... 4

Sommaire ................................................................................................................................... 5

Liste des figures ......................................................................................................................... 9

Liste des Tableaux ................................................................................................................... 10

Liste des Algorithmes .............................................................................................................. 10

Introduction générale ............................................................................................................... 12

Chapitre I ................................................................................................................................. 17

Données et fouille de données spatiales ............................................................................... 17

Introduction .............................................................................................................................. 18

1. Les données spatiales .......................................................................................................... 18

1.1. Définition ...................................................................................................................... 18

1.2. Types de données spatiales ........................................................................................... 19

1.3. Caractéristiques des données spatiales .......................................................................... 19

1.4. Spécificités et particularités des données spatiales ....................................................... 20

1.4.1. Influence du voisinage, première loi en géographie ............................................... 20

1.4.2. Les relations spatiales ............................................................................................. 20

1.5. Modélisation et représentation des données spatiales ................................................... 23

1.5.1. Mode de représentation par tessélation (maillage) ................................................. 23

1.5.2. Mode de représentation par vecteur ........................................................................ 25

1.6. Structures d’indexation des données spatiales .............................................................. 26

1.6.1. Structures en arbre .................................................................................................. 26

1.6.2. Structure en graphe ................................................................................................. 28

1.7. Notion de couches thématiques ..................................................................................... 29

2. Bases de données spatiales .................................................................................................. 30

2.1. Parallèle entre les SGBD spatiaux et les SGBD relationnels .................................... 30

2.2. Architectures des bases de données spatiales ............................................................ 31

3. La fouille de données spatiales ........................................................................................... 32

3.1. Spécificité de la fouille de données spatiales ............................................................ 33

3.2. Inadaptation des techniques de la fouille de données Classique aux données spatiales

……………………………………………………………………………………...33

Conclusion ............................................................................................................................... 34

Chapitre II ................................................................................................................................ 35

État de l’art sur la fouille de données spatiales ................................................................... 35

Introduction .............................................................................................................................. 36

1. Approches monothématiques .............................................................................................. 37

1.1. Analyse de localisations sans attributs ...................................................................... 37

1.1.1. Analyse de localisations munies de mesures numériques .................................. 37

1.1.2. Analyse de localisations munies de catégories .................................................. 37

2. Approches multi-thématiques ............................................................................................. 38

2.1. Les règles d’associations ............................................................................................... 38

2.1.1. Travail 1 : Treillis de Galois pour l’extraction des règles d’associations .......... 38

2.1.2. Travail 2 : Application de l’algorithme Apriori à la fouille de données spatiales

multithématique ................................................................................................................ 39

2.2. Approche basée sur la programmation logique inductive ......................................... 40

2.3. Classification par arbres de décisions ....................................................................... 40

2.3.1. Travail 1 : Extension de l’algorithme CART pour les données spatiales .......... 41

2.3.2. Travail 2 : Extension de l’algorithme ID3 pour les données spatiales .............. 42

Conclusion ............................................................................................................................... 42

Chapitre III ............................................................................................................................... 44

Approches proposées............................................................................................................ 44

Introduction .............................................................................................................................. 45

1. Justification de nos choix .................................................................................................... 45

1.1. Pourquoi les arbres de décision ? .............................................................................. 45

1.2. Limitation des travaux précédents basés sur les arbres de décision .......................... 45

1.3. Pourquoi C4.5 ? ......................................................................................................... 46

2. Approches proposées .......................................................................................................... 47

2.1. Index de jointure spatial ............................................................................................ 47

2.2. Etude d’un phénomène par un seul phénomène : ...................................................... 50

2.2.1. Etude d’un phénomène par un phénomène avec une seule relation spatiale ..... 50

2.2.2. Etude d’un phénomène par un phénomène en incluant plusieurs relations

spatiales. ........................................................................................................................... 51

2.3. Etude d’un phénomène par plusieurs autres phénomènes ......................................... 52

2.3.1. Jointure à la volée .............................................................................................. 52

2.3.2. Matérialisation des jointures .............................................................................. 53

2.3.3. Semi-Matérialisation des jointures .................................................................... 54

2.3.4. Matérialisation imbriquée .................................................................................. 55

2.4. Algorithme S-C4.5 .................................................................................................... 55

3. Conclusion ........................................................................................................................... 57

Chapitre IV............................................................................................................................... 58

Expérimentations et résultats ............................................................................................... 58

1. Introduction ......................................................................................................................... 59

2. Implémentation ................................................................................................................... 59

2.1. Environnement de travail .......................................................................................... 59

2.2. Jeu de données ........................................................................................................... 59

3. Expérimentations et résultats .............................................................................................. 61

3.1. L’étude d’un phénomène avec un seul autre phénomène ......................................... 61

3.2. L’étude d’un phénomène avec plusieurs autres phénomènes ................................... 64

3.3. Jointure à la volée .................................................................................................. 65

3.4. Matérialisation des jointures .................................................................................. 65

3.5. Semi-matérialisation des jointures ......................................................................... 65

3.6. Matérialisation imbriquée ...................................................................................... 65

4. Discussions et comparaisons ............................................................................................... 67

5. Conclusion ........................................................................................................................... 70

Conclusion générale ................................................................................................................. 72

Annexes.................................................................................................................................... 74

Annexe I : Les arbres de décision ............................................................................................ 75

1. Définition ............................................................................................................................ 75

2. Les algorithmes des arbres de décisions ............................................................................. 76

2.1. Algorithme CART ..................................................................................................... 76

2.2. Algorithme ID3 ......................................................................................................... 77

2.3. Algorithme C4.5 ........................................................................................................ 78

Annexe II : Les règles d’associations ...................................................................................... 80

1. Définition ............................................................................................................................ 80

2. Les Algorithmes des règles d’association ........................................................................... 81

2.1. Algorithme APRIORI ............................................................................................... 81

2.2. Algorithme CLOSE ................................................................................................... 82

Notations et paramètres utilisés dans CLOSE...................................................................... 82

Annexe III : Programmation logique inductive ....................................................................... 84

1. Définition ............................................................................................................................ 84

2. Formalisme de la PLI .......................................................................................................... 84

Références Bibliographiques ................................................................................................... 86

Liste des figures

Figure 1: Exemples de certains types de distances ................................................................. 21

Figure 2: Relations d’adjacence .............................................................................................. 22

Figure 3 : Maillage régulier, Raster ......................................................................................... 24

Figure 4: Exemple de maillage irrégulier ................................................................................ 24

Figure 5:Maillage irrégulier, Triangulation de Delaunay ........................................................ 24

Figure 6 : Mode vecteur ........................................................................................................... 25

Figure 7 : Primitives de représentation des collections d'objets selon l’OGC ........................ 26

Figure 8 : Exemple d’un Quad-tree ......................................................................................... 27

Figure 9 : Exemple d’un Oc-tree ............................................................................................. 27

Figure 10: Exemple d’un R-tree .............................................................................................. 28

Figure 11 : Exemple d’un KD-tree (K=3, 3D-tree) ................................................................. 28

Figure 12 : Graphe et matrice de voisinage ............................................................................. 29

Figure 13 : Exemple de représentation en couches thématiques ............................................. 29

Figure 14 : Différentes architectures des bases de données spatiales ...................................... 31

Figure 15 : Calcul des relations spatiales entres les différents objets ...................................... 39

Figure 16: exemple d’index de jointure spatial........................................................................ 48

Figure 17: Etude d’un phénomène par un autre phénomène avec une seule relation spatiale . 51

Figure 18: Etude d’un phénomène par un autre phénomène en incluant plusieurs relations

spatiales. ................................................................................................................................... 51

Figure 19: Etude d’un phénomène par plusieurs autres phénomènes ...................................... 52

Figure 20: La structure de la méthode semi-matérialisation ................................................... 54

Figure 21 : Etude d'un phénomène avec un seul autre phénomène en utilisant une seule

relation spatiale (Distance) ...................................................................................................... 62

Figure 22: Arbre de décision spatial généré par S-C4.5 de l’étude d’un phénomène par un

seul autre phénomène en utilisant une seule relation spatiale (Distance) ................................ 63


seul autre phénomène en utilisant plusieurs relations spatiales ............................................... 63

Figure 24: Etude d'un phénome avec plusieurs autres phénomènes en utilisant deux relations

spatiales (Distance et inclusion)............................................................................................... 64

Figure 25 : Arbre de décision spatial généré par S-C4.5 de l’étude d’un phénomène avec

plusieurs autres phénomènes en utilisant une seule relation spatiale (Distance) ..................... 66


plusieurs autres phénomènes en utilisant deux relations spatiales (Distance et Inclusion) ..... 66

Figure 27 : Arbre de décision spatial généré par S-CART de l’étude d’un phénomène par un

seul phénomène en utilisant une seule relation spatiale (Distance) ......................................... 68


seul phénomène en utilisant deux relations spatiales ............................................................... 69

Liste des Tableaux

Tableau 1 : Parallèle entre SGBD spatiaux et relationnels ...................................................... 30

Tableau 2 : Fouille de données spatiales VS analyse spatiale ................................................. 32

Tableau 3: Première structure de la matérialisation des jointures multithématiques ............... 53

Tableau 4: Seconde structure de la matérialisation des jointures ........................................... 54

Tableau 5: Approches matérialisation imbriquée .................................................................... 55

Tableau 6: Description de la base de données spatiales .......................................................... 59

Tableau 7 : Jeu de données spatiales........................................................................................ 60

Tableau 8: Résultats obtenus par l’étude d’un phénomène par un seul autre phénomène en

utilisant une ou plusieurs relations spatiales ............................................................................ 62

Tableau 9: Résultats obtenus par la jointure à la volée ............................................................ 65

Tableau 10: Résultats obtenus par la matérialisation des jointures ......................................... 65

Tableau 11: Résultats obtenus par la semi-matérialisation des jointures ................................ 65

Tableau 12: Résultats obtenus par la matérialisation imbriquée. ............................................ 66

Tableau 13: Résultats obtenus par l’étude d’un phénomène par un seul autre phénomène en

utilisant une ou plusieurs relations spatiales ............................................................................ 67

Tableau 14: Résultats obtenus par les approches multithématique. ........................................ 70

Liste des Algorithmes

Algorithme 1: Description de la fonction principale de l’Algorithme S-C4.5 proposé ........... 56

Algorithme 2 : Algorithme CLOSE ......................................................................................... 82

Introduction générale

Introduction Générale


12


Grâce aux avancées technologiques, nous vivons aujourd’hui dans l’ère numérique où nous

assistons à une explosion de la quantité des données. Une majeure partie de ces données

(80%) [28] est de nature spatiale et obéit à la première loi de géographie qui introduit la

notion de voisinage reliant les données spatiales les unes aux autres.

Les données spatiales sont la représentation des observations sur des objets ou phénomènes

de fortes interactions : trafic et accidents routiers, épidémie, pollution, séisme…etc. Elles

induisent un volume de données important du fait de leur nature réelle ou localisable dans un

espace à un temps donné (présent, passé ou futur) ou sur une période de temps souvent

longue en vue d’une observation des changements. Les données spatiales peuvent être

dépendantes et sont organisées en couches thématiques.

Les données spatiales sont fournies sous des formats différents par des techniques différentes

appliquées dans divers domaines : Télédétection, images satellitaires et aériennes, systèmes

de localisation par satellite, astronomie, météorologie, cartographie, carte thématiques,

systèmes d’informations géographiques, recensement, épidémiologie, statistiques sociales et

économiques, rapport d’études sur l’environnement…etc. Les données spatiales sont par

nature bruitées et imparfaites nécessitant donc des prétraitements afin de les rendre

exploitables.

Toute donnée spatiale doit absolument avoir des attributs spatiaux et peut disposer d’autres

attributs non spatiaux. Les attributs spatiaux doivent contenir à leur tour des informations de

localisation de type géométrique (emplacement par longitude et latitude, adresse, code

postal…etc.) et peuvent disposer d’informations morphologiques sur l’objet spatial (forme,

taille, périmètre…etc.). Ils peuvent aussi disposer d’informations de types topologiques

(principalement relations de voisinage et d’adjacence) mais ces dernières sont souvent

implicites et constituent la principale problématique dans la fouille de données spatiales.

Quant aux attributs non spatiaux, ils sont plutôt de nature descriptive : qualitatives (type de

bâtiment, nom de région…etc.) ou quantitatives (densité population…etc.) et peuvent être

accompagnés de métadonnées enrichissantes souvent utiles pour déterminer la qualité des

données tels que la date et la méthode d’acquisition.

Travailler sur des données spatiales implique la capacité de les localiser et de les décrire

individuellement, ainsi que de les appréhender collectivement en décrivant leurs relations

spatiales dans l’espace.

Les relations spatiales sont des informations qui traduisent une propriété et caractéristique

essentielle du monde réel, à savoir la notion de l’influence du voisinage ; elles sont souvent

exploitées dans les requêtes et analyses spatiales.

Les relations spatiales peuvent exister explicitement ou implicitement dans une base de

données spatiale. Dans le cas explicite, elles sont représentées selon le modèle topologique

qui permet de les décrire à l’aide de graphes. Dans le cas implicite, des relations simples sont


13

déduites par des calculs couteux, d’ailleurs l’une des premières taches de la fouille de

données spatiales est de les exhiber.

Le calcul des relations spatiales met en lumière deux problématiques liées à la nature même

de ces relations. Premièrement, la pratique nous montre que les relations spatiales ne sont

stockées dans les bases de données que de façon implicite et ne sont résolues à chaque

évocation qu’au prix de calculs géométriques complexes et couteux. Une optimisation de leur

calcul est donc nécessaire. Le second problème, réside dans le fait que les relations spatiales

sont nombreuses (distance, inclusion, …etc.), ce qui rend le choix de la "bonne" relation

spatiale à prendre en compte est complexe.

Une telle masse de données spatiales n’a de valeur que si on peut en extraire des

connaissances utiles, notamment dans les domaines de l’informatique décisionnelle,

opérations de ciblage et marketing à grande échelle, campagnes politiques.

Traiter ces données par les techniques de fouille de données classiques est obsolète d’où le

besoin de développer de nouvelles techniques car aucune méthode d’analyse de données ne

permet d’analyser les données dépendantes. En effet, la statistique et l’analyse de données,

ainsi que les méthodes de fouille de données traditionnelles supposent que toutes les données

indépendantes. De plus, aucune de ces méthodes ne peut interpréter les propriétés spatiales ni

découvrir les liens entre objets spatiaux. C’est là que la fouille de données spatiales est

apparue, en combinant plusieurs approches à la confluence de plusieurs domaines tels que les

systèmes d’informations géographiques, les statistiques, l’analyse spatiale, les bases de

données ainsi que la fouille de données classique.

La fouille de données spatiales peut être considérée comme une fouille de données multi-

relationnelles, où chaque table représente une catégorie de données spatiales représentant un

certain phénomène, c’est ce qu’on appelle une couche thématique. A la différence d’une

fouille de données multi-relationnelles, la fouille de données spatiales doit prendre en

considération les relations spatiales entre les données, ce qui en fait un domaine à part entière

de la fouille de données classique. Prendre en compte cette spécificité pose deux problèmes :

le premier est lié à l’inadaptation des méthodes existantes de fouille de données à l’analyse

spatiale. Le deuxième est dû à la complexité de calcul des relations spatiales, ce qui a suscité

l’intérêt de beaucoup de chercheurs et organismes de divers domaines.

Les méthodes de la fouille de données spatiales sont, pour la plupart, une extension de celles

de la fouille de données classiques, elles engendrent plus de problèmes de performances en

raison du volume de données important généré par le codage des localisations géométriques

et la complexité du calcul des relations spatiales. Les recherches sur la fouille de données

spatiales visent donc à proposer et optimiser des méthodes d’analyse tenant compte des

relations spatiales.

Plusieurs approches ont vu le jour basées sur les techniques de fouille de données telles que

les règles d’association, la programmation logique inductive et les arbres de décisions. Parmi

ces techniques, on s’’intéresse à la fouille de données spatiales par les arbres de décision.

Notre choix pour la technique des arbres de décision revient à la source même de la


14

problématique, qui est l’exploration des données spatiales. Cette dernière tente de générer de

façon automatique des hypothèses à partir d’une grande masse de données, passant in

fine d’une fouille de données complexes sur un gros volume de données spatiales vers une

simple analyse spatiale. Afin d’y parvenir, le choix des arbres de décision comme technique

de fouille de données, semble le plus adapté.

Il existe plusieurs approches basées sur les arbres de décision spatial par exemple :[48][51],

néanmoins ces approches présentent certaines limites : La première réside dans le fait que les

approches dans ces travaux ne considèrent qu’une seule relation spatiale (généralement la

distance) or, les données spatiales sont caractérisées par plusieurs relations qui les relient

entre elles. Le fait de ne considérer qu’une seule relation et une seule table voisine, limite les

résultats de l’analyse et de la fouille de ces données. La seconde limite concerne la non prise

en charges des données continues, qui sont très fréquentes dans les bases de données

spatiales, tel que l’utilisation de l’algorithme ID3. Et enfin, la dernière limite a été constatée

lors de la génération des arbres de décisions binaires, évoluant en profondeur uniquement, tel

que l’utilisation de l’algorithme CART.

Afin de pallier ces limites, nous proposons d’étendre l’algorithme C4.5 aux données spatiales

générant ainsi un nouvel algorithme dit S-C4.5.

Notre choix s’est porté sur l’algorithme C4.5 car il répond le mieux à nos besoins selon le

type de données supportées, la rapidité et performances, l’utilisation de la mémoire et l’arbre

de décision généré. L’algorithme C4.5 permet de prendre en considération un maximum de

types de données, y compris les données continues. Il permet aussi une gestion des données

manquantes ce qui constitue une amélioration par rapport à l’algorithme ID3. De plus

l’algorithme génère des arbres N-aires, contrairement à l’algorithme CART.

L’adaptation de l’algorithme C4.5 aux données spatiales est faite selon deux modifications.

La première est au niveau de l’organisation de données qui consiste à inclure parmi les

données d’analyse, les relations spatiales précalculées dans l’index de jointure spatiale inspiré

des travaux de Zeitouni et Chelghoum [51][13]. La seconde est au niveau de la formulation

de l’algorithme C4.5, cette modification consiste à prendre en charge la nature multi-

relationnelle des données spatiales, qui sont généralement organisées en plusieurs tables

représentant chacune un phénomène spatial.

Nous avons étudié le problème de fouille de données spatiales selon deux cas d’études

majeurs :

Le premier cas est l’étude d’un phénomène par un seul autre phénomène. Cette étude consiste

à prendre deux tables en entrées : une table cible (Phénomène Cible), une table voisine

(Phénomène Voisin) et un index de jointure spatiale qui relie le premier phénomène avec le

second phénomène, en incluant dans un premier temps une seule relation spatiale ensuite

plusieurs relations spatiales. La modification de l’algorithme réside surtout dans le calcul du

gain informationnel. L’algorithme S-C4.5 dans ce cas d’étude a été implémenté selon deux

méthodes de jointures : La jointure à la volée et la matérialisation des jointures.


15

Le deuxième cas est l’étude d’un phénomène par plusieurs autres phénomènes. Cette étude

nous a permis de se rapprocher plus de la réalité, et de pouvoir effectuer une analyse plus

pertinente. Le fait d’effectuer une étude d’un phénomène par un seul phénomène dans la

fouille de données spatiale, constitue une limitation due à la considération d’un seul

phénomène explicatif, et cela malgré la considération de plusieurs relations spatiales. Or,

dans la réalité, un certain phénomène peut être expliqué par plusieurs autres phénomènes

d’où la nécessité de pouvoir réaliser une étude d’un phénomène par plusieurs autres

phénomènes. Dans cette étude l’algorithme S-C4.5 a été adapté selon quatre méthodes de

jointures : jointure à la volée, matérialisation des jointures, semi-matérialisation des jointure

et jointure imbriquée.

Nous avons testé nos approches sur un jeu de données réel de la sécurité routière, les

circonstances et les blessures des accidents de la route en Grande-Bretagne de 1979 à 2001,

les types des véhicules impliqués et leurs conséquences.

Le but de l’étude d’un phénomène par un seul phénomène en utilisant une seule relation

spatiale ou plusieurs, est de lier les types d’accidents à la zone, ce qui pourrait aider à prendre

des décisions afin de prévoir et pouvoir intervenir efficacement dans cette zone en ayant une

certaine prévision sur les types d’accidents qu’on pourrait avoir par emplacement.

Le but du deuxième cas d’étude qui est l’étude d’un phénomène par plusieurs autres

phénomènes en incluant plusieurs relations spatiales, est de pouvoir déterminer et prévoir le

type d’accidents qui peuvent se produire en fonction du type de la route et des conditions

météos. Cela pourrait aider à prendre des décisions concernant la mise en place d’une

signalisation routière plus efficace par exemple, ou modifier des tronçons de route afin

d’éviter certains accidents quelques soit les conditions météorologiques.

Après avoir présenté le contexte scientifique dans lequel s’inscrit notre thèse, ainsi que ses

objectifs et les contributions associées, la suite de ce manuscrit s’organise en 4 chapitres :

- Le premier chapitre présente au préalable les concepts de base sur les données spatiales,

leurs types et caractéristiques. Il définit ensuite la fouille de données spatiales en

soulignant sa différence avec la fouille de données classique.

- Le deuxième chapitre est un état de l’art sur la fouille de données spatiales. Nous

présentons quelques travaux utilisant des approches différentes : règles d’association,

logique inductive, arbres de décision. Nous insistons sur ces derniers car les approches

proposées se base sur les arbres de décision.

- Le troisième chapitre est consacré à la description de notre contribution sous la forme de

deux cas d’études en se basant sur l’adaptation de l’algorithme C4.5 aux données

spatiales en appliquant différentes méthodes de jointures.

- Le quatrième chapitre décrit l’étude expérimentale sur les deux cas d’études de notre

contribution en utilisant une base de données réelles d’une taille importante, les résultats

de notre contribution sont comparés à ceux obtenus par les autres algorithmes

implémentés.


16

- Enfin la conclusion Générale présente un bilan des contributions proposées et leurs

apports dans la problématique traitée, on rappellera les principaux résultats obtenus de

chaque approche. Ensuite, un ensemble de piste à explorer sont précisées pour améliorer

notre contribution.

- Le chapitre annexes est consacré pour l’explication du déroulement des algorithme des

arbres de décision, règles d’association, programmation logique inductive, et l’opérateur

de croisement :

• Annexe I : Nous exposons dans cette partie le principe des algorithmes de base

des arbres de décision classique utilisé dans notre travail : CART, ID3 et C4.5

• Annexe II : cette partie est consacré pour quelques notions de bases et les

algorithmes des règles d’association : Apriori et CLOSE

• Annexe III : nous exposons l’algorithme général de la programmation logique

inductive.

• Annexe IV : Nous expliquons le principe de l’operateur de CROISEMENT

Chapitre I

Données et fouille de données spatiales

Chapitre I : Données et fouilles de données spatiales

18

Introduction

Les données spatiales sont la représentation des observations sur des objets ou phénomènes

de fortes interactions (trafic et accidents routiers, épidémie, pollution, séisme, …etc.) bien

réels ou imaginaires, localisables dans un espace, à un moment donné (présent, passé ou

futur) ou sur une période de temps souvent longue en vue d’une observation des changements

(ce qui rend leur volume très important). Elles sont de nature dépendante (ou

interdépendante), et elles peuvent être organisées en couches thématiques.

Les données spatiales sont fournies par des techniques différentes et sous formats différents,

parmi les sources on cite : la télédétection, les images satellitaires et aériennes, les systèmes

de localisation par satellite(GPS1), l’astronomie, la météorologie, la cartographie, la carte

thématiques, le systèmes d’informations géographiques, le recensement, l’épidémiologie,

statistiques sociales et économiques, les rapports d’études sur l’environnement,… ce qui fait

qu’elles peuvent être bruités et imparfaites nécessitant donc des prétraitements.

Selon [28], 80% des données d’une organisation ont une composante spatiale. Avec

l’évolution des outils d’acquisition des données, le volume de données dans les bases de

données spatiales ne cesse d’augmenter. Ces données sont utilisées dans des applications

décisionnelles et la fouille de données est reconnue comme un moyen très efficace d’analyse

avancée de données, permettant d’extraire des connaissances cachées depuis de grandes

masses de données. Etant donné le volume croissant des données spatiales, la fouille de

données spatiales permet d’extraire des propriétés spatiales cachées dans ces données et

présente donc un intérêt certain pour les applications spatiales décisionnelles. La fouille de

données spatiale est aujourd’hui identifiée comme un domaine à part entière de la fouille de

données. Elle résulte de la combinaison de cette dernière et des bases de données spatiales.

Dans ce chapitre, nous présentons au préalable les données spatiales, et leurs spécificités,

ensuite nous introduisant la fouille de données spatiales.

1. Les données spatiales

1.1. Définition

On peut citer deux définitions des données spatiales concernant les données géospatiales et le

domaine de télédétection, mais qui peuvent être généralisées à toute donnée de caractère

spatial.

La première [36] est apportée par l’Open Geospatial Consortium (OGC) qui est un

consortium international pour développer et promouvoir des standards ouverts, afin de

garantir l'interopérabilité des contenus, des services et des échanges dans les domaines de la

géomatique et de l'information géographique.

Selon l’OGC : une donnée spatiale (ou géospatiale, ou encore information géographique) est

définie comme étant “toute information représentant la localisation géographique et les

1 Global Positioning System


19

caractéristiques d’une entité (objet, phénomène) naturelle ou construite par l’homme, ainsi

que ses frontières terrestres. Une donnée spatiale représente une abstraction des entités du

monde réel, telles que les routes, les bâtiments, les véhicules, les lacs, les forêts et les pays.”

[36]

La deuxième [22] est apportée par l’équipe de fouille de données et bio-informatique

théorique de l’université de Strasbourg, notamment dans le domaine de la télédétection

décrivant la donnée spatiale à 4 niveaux : multi-sources, multi-vues, multi-résolutions et

multi-temporelles.

- [22]Multi-sources : fourni par des satellites et capteurs différents.

- Multi-vues : images représentant différentes descriptions d’une même zone ou région.

- Multi-résolutions : à différentes résolutions.

- Multi-temporelles : recueillies à différents instants [22].

Toute donnée spatiale doit absolument avoir des attributs spatiaux, et peut disposer d’autres

attributs non spatiaux. Les attributs spatiaux doivent contenir à leur tour des informations de

localisations de type géométrique (emplacement par longitude et latitude par exemple,

adresse, code postal,…) et peuvent disposer d’informations morphologiques sur l’objet

spatiale (forme, taille, périmètre,…), ils peuvent aussi disposer d’informations de type

topologique (principalement relations de voisinage et d’adjacence) mais ces informations

sont souvent implicites, c’est d’ailleurs ce dernier type d’informations qui constituent la

principale problématique dans la fouille de données spatiales.

Quant aux attributs non spatiaux, ils sont plutôt de nature descriptive, qualitative (type de

bâtiment, nom de région, …) ou quantitative (densité population, …), et peuvent être

accompagnés de métadonnées enrichissantes souvent utiles pour déterminer la qualité des

données (tels que la date et la méthode d’acquisition, …) [50] [51].

1.2. Types de données spatiales

Les données spatiales peuvent être classées en trois types selon la façon dont les phénomènes

qu’elles représentent se produisent dans l’espace [33].

- Données spatiales sur les évènements : représentent des phénomènes à des endroits précis

dans l’espace, à titre d’exemple : lieux de crimes, d’accidents, …

- Données spatiales discrètes sur les surfaces : quand un phénomène est réparti de manière

homogène sur une surface donnée, exemple : revenu d’un comté ou une région, …

- Données spatiales continues sur les surfaces : quand on dispose de plusieurs valeurs d’un

certain phénomène dans une surface donnée, et comme la surface est un ensemble de

points, la notion de continuité est le fait de remplir les points sans valeurs à partir de

plusieurs points ou observations de référence, on a comme exemple : qualité d’air

ambiant dans une région…etc.

1.3. Caractéristiques des données spatiales

Une donnée spatiale est caractérisée par trois niveaux distincts d’attributs :


20

- Niveau sémantique : c’est l’ensemble d’informations relatives à la description d’un objet

spatial par sa nature et son aspect (exemple : nom d’une rue, d’un fleuve, d’une

commune, …).

- Niveau topologique : les relations éventuelles liant une donnée spatiale à d’autres

(exemple : un local se trouve dans un bâtiment qui se trouve lui-même dans une localité,

croisement entre deux rues, …).

- Niveau géométrique : il s’agit de l’ensemble des informations décrivant la morphologie

(forme) et la localisation de la donnée. [4] [14] [33] [50]

1.4. Spécificités et particularités des données spatiales

1.4.1. Influence du voisinage, première loi en géographie

Contrairement aux données traditionnelles, les données spatiales sont interdépendantes. En

effet, elles décrivent des phénomènes avec de fortes interactions dans l’espace, car tout

phénomène spatial à un endroit est influencé par son voisinage et cette influence décroit avec

l’éloignement, par exemple, la contamination des moules dans une lagune est influencée par

les champs d’agriculture autour. Cette notion de dépendance est à l’origine de la première loi

en géographie de Tobler “Everything is related to everything else but near by things are more

related than distant things”, traduction : “ce qui se passe dans une localité particulière

dépend de ce qui se passe dans d’autres localités et ces interactions sont d’autant plus fortes

que les localités concernées sont plus proches” [3] [9] [12] [51].

Du point de vue analyse de données, l’analyse des données spatiales doit se faire en fonction

de leurs caractéristiques, celles de leurs voisins et les relations spatiales entre elles

[43][44][45].

1.4.2. Les relations spatiales

Travailler sur des données spatiales implique la capacité de les localiser et de les décrire

individuellement, ainsi que de les appréhender collectivement en décrivant leurs relations

dans l’espace.

Les relations spatiales sont des informations qui traduisent une propriété et caractéristique

essentielle du monde réel, à savoir la notion de l’influence du voisinage ; elles sont souvent

exploitées dans les requêtes et analyses spatiales.

Les relations spatiales peuvent exister explicitement ou souvent implicitement dans une base

de données spatiale. Dans le cas explicite, elles sont représentées selon le modèle topologique

qui permet de les décrire à l’aide de graphes. Dans le cas implicite, les relations simples sont

déduites par des calculs couteux, d’ailleurs l’une des premières taches de la fouille de

données spatiales est de les exhiber [1] [51].

On distingue trois types de relations spatiales ou de voisinage : relations de distance, relations

directionnelles et les relations topologiques.


21

1.4.2.1. Relations de distance

Appelées aussi métriques, ces relations comparent la distance entre deux objets spatiaux à

une constante donnée, elles sont souvent évaluées en unités de longueur. La distance

physique peut être Euclidienne (vol d'oiseau, correspond rarement à la distance que l'on

parcourt réellement sur le terrain), ou de Manhattan (le long d'un réseau rectiligne) ou

topologique (le long d'un réseau pas forcément rectiligne). Elles peuvent aussi se mesurer en

temps (duré du parcours) et en cout (prix du transport) [18][50][51].

Figure 1: Exemples de certains types de distances [18]

1.4.2.2. Relations directionnelles

Ces relations décrivent l’emplacement des objets par rapport à un autre objet de référence

suivant le sens ou la direction. Exemples : au nord de, à gauche de, avant, … [18]

1.4.2.3. Relations topologiques

C’est sans doute le type de relations le plus important. En dépit des relations de distance qui

décrivent les relations entre les entités au niveau quantitatif par une certaine métrique ; les

relations topologiques les décrivent au niveau qualitatif. [18]

Le concept de topologie se rapporte à une démarche courante de notre esprit pour

appréhender la réalité : “notre perception visuelle est topologique”.

Lorsque nous observons un paysage, un lieu ou lorsqu’on consulte une carte, notre perception

immédiate est globale. Les objets spatiaux tels que les bâtiments, agglomérations sont “vus”

dans leur contexte et la notion de voisinage est implicite : “la rivière traverse l’agglomération,

la parcelle de M.X jouxte celle de M.Y”. [18]

Au sens de notre appréhension de l’espace, la topologie est donc l’ensemble des relations

perçues qui nous permettent de situer les objets les uns par rapport aux autres, la notion de

voisinage devient donc : “qu’est ce qui est à coté de quoi ?” et “qu’est ce qui est connecté à

?” en ce qui concerne les réseaux.


22

Parmi les relations topologiques, on peut citer l’adjacence, la connectivité, l’inclusion et

l’intersection.

A. L’adjacence

La notion d’adjacence (ou contiguïté) implique que les unités spatiales possèdent en commun

un côté ou un sommet. On dénomme une adjacence au sens strict si seule une ligne frontière

est commune, au sens large si au moins un sommet est commun comme l’illustre la Figure 2.

Elle répond à la question ”Qu’est-ce qui est à côté de quoi ?”

La topologie apporte cependant des nuances dans la notion d’adjacence. Dépourvue de

métrique, elle prend en compte seulement l’ordre dans lequel des unités spatiales se

rencontrent en s’éloignant de l’unité cible.

L’adjacence est dite de 1er ordre si les deux entités sont en contact, de 2ème ordre si une

entité s’intercale (Figure 2) et ainsi de suite. L’ordre d’adjacence intervient, par exemple,

dans les transports pour déterminer le nombre de transbordements nécessaires pour déplacer

des biens ou des personnes d'un endroit à un autre.

Figure 2: Relations d’adjacence [18]

B. La connectivité

La connectivité exprime l’adjacence pour des réseaux linéaires. Elle met en liaison les

segments constitutifs du réseau. La connectivité peut être orientée. C’est le cas de la

modélisation d’un réseau de distribution de fluide (gaz, eau, électricité), de biens ou de

personnes. En revanche, un réseau routier est parcouru dans les deux sens. Les ”Sens unique”

sont les exceptions [7][18].

La connectivité est décrite au moyen de graphe et de matrice pour indiquer au moment de la

conception du système qu’est-ce qui est relié à quoi.

C. L’inclusion

L’inclusion se rencontre lorsqu’une unité spatiale est totalement située à l’intérieur d’une

autre, telle une enclave ou un îlot, les départements ou provinces à l’intérieur d’un pays. En

termes topologiques, il s’agit d’un cas particulier d’adjacence [18].

D. L'intersection

L'intersection exprime le point où la surface commune à deux entités [18].


23

1.4.2.4. Complexité du calcul des relations spatiales

Le problème des relations spatiales est double : Le premier est que ces relations sont souvent

implicites. Elles ne sont pas stockées dans les bases de données spatiales et sont résolues

chaque fois qu’elles sont évoquées, nécessitant des calculs géométriques complexes et

coûteux. Il faut donc optimiser leur calcul. Le deuxième problème est que les relations

spatiales sont nombreuses (distance, inclusion, …). Par conséquent, le choix de la "bonne "

relation spatiale à prendre en compte dans un processus de fouille est difficile. La plupart des

méthodes de fouille de données spatiales existantes considèrent un nombre limité de relations

spatiales choisies par un utilisateur métier. Ce choix devient difficile lorsque les relations

potentiellement intéressantes sont multiples. Il faut donc trouver des méthodes qui permettent

de choisir automatiquement ces "bonnes" relations spatiales [52] [51].

1.5. Modélisation et représentation des données spatiales

Tout objet spatial est représenté dans une base de données spatiale par une certaine structure,

qui contient à la fois des données sémantiques dites “aspatiales” ou non spatiales et des

données spatiales.

Concernant les données sémantiques, elles décrivent qualitativement ou quantitativement les

propriétés de l’objet spatial, par exemple le nom d’une ville, le nombre de ses habitants, …,

et sont de type alphanumérique, et donc stockées sous de fichiers, tables ou objets.

Par contre, les données spatiales, qui ont pour rôle de décrire l’objet spatial dans sa

morphologie et préciser sa localisation, s’appuient sur une représentation plus souvent

géométrique. Pour illustrer ce cas, on peut citer l’exemple d’une carte contenant une

collection d’objets spatiaux, qui est une abstraction ou une représentation symbolique du

monde réel.

Pour la représentation des données spatiales, on distingue deux grandes perceptions. La

première est une perception par étendu dont la représentation utilise des modèles basés sur la

tessélation (ou le maillage), tandis que la deuxième est par objet et utilise souvent des

modèles vecteurs [14] [21] [49].

1.5.1. Mode de représentation par tessélation (maillage)

Elle consiste à décomposer l’objet de l’intérieur ce qui aboutit à des mailles soit régulières

soit irrégulières.

Pour ce qui est des mailles régulières, l’exemple le plus courant concerne les images

(appelées Rasters), qui sont représentées par une matrice de pixels. À chaque maille est

attribuée une valeur numérique correspondant à une mesure, catégorie ou identifiant d’un

objet [14].


24

Figure 3 : Maillage régulier, Raster [14]

Et pour les mailles irrégulières, il existe un algorithme bien connu de Delaunay qui suit le

principe de triangulation. Il existe d’autres exemples tels que le modèle numérique de

terrains.

Figure 4: Exemple de maillage irrégulier [14]

Figure 5:Maillage irrégulier, Triangulation de Delaunay [14]

Parmi les avantages du modèle maillé, on peut citer :

- Bonne représentation visuelle.

- Facilité d’utilisation : Par rapport au modèle vecteur, il permet d’effectuer certains

traitements et opérations d’interpolation, seuillage ou agrégation à moindre cout. Le


25

croisement des données est lui aussi facilité, puisque toutes les grandeurs sont ramenées à

la même unité de base qui est le pixel [14].

De l’autre côté, comme inconvénient, on a les fichiers conteneurs de ce format qui sont

lourds en mémoire.

1.5.2. Mode de représentation par vecteur

Dans ce mode de représentation, les données sont représentées géométriquement par leurs

contours sous forme de points, lignes et polygones. (Ils sont aussi appelés types spatiaux de

base).

- Points : permet de représenter les lieux par des points. Exemples : forages, points

géodésiques, …

- Lignes : ce sont des collections de points. Exemples : routes, rivières, …

- Polygones (surfaces) : ce sont des lignes reliées entre elles, et où le premier et dernier

point sont identiques. Exemples : parcelles, communes, … [14] [37].

Figure 6 : Mode vecteur [14]

Pour ce mode vecteur, il existe trois modèles [17] :

Le modèle spaghetti : il considère les objets spatiaux comme étant isolé, décrivant leurs

contours sans prendre en compte les relations spatiales entre eux. Il est simple d’utilisation

cependant, les relations spatiales doivent être calculées avant chaque traitement, c’est

pourquoi il est souvent utilisé quand le voisinage ne change pas fréquemment, comme pour

représenter les terrains urbains.

Le modèle réseau : il décrit la connexité des lignes. Ce modèle est principalement utilisé

pour effectuer des traitements de type parcours de graphes.

Le modèle topologique : c’est le modèle le plus riche, il permet de représenter les entités

spatiales ainsi que les relations entres elles quel que soit leurs formes ; nœuds, lignes ou

surfaces. De plus il ne permet pas la redondance, ce qui économise l’espace mémoire. Bien

que la structure de données soit plus complexe dans ce modèle, le fait de prendre en

considération les relations spatiales, facilite grandement les traitements, c’est pourquoi il est


26

souvent utilisé pour représenter les données spatiales destinées à la fouille de données

spatiales [18].

Pour ce qui est des avantages du mode vecteur, on a :

• Une représentation très conforme à la réalité.

• La précision des calculs des localisations et dimensions.

• Réduction du poids du fichier conteneur [14] [37].

On tient à préciser qu’il est possible de passer d’un mode de représentation à un autre.

Autre précision concernant la modélisation d’entités spatiales, qui selon l’OGC2 elle se base

sur deux types de primitives géographiques :

- Les primitives représentant des objets simples (ou singuliers) : par trois abstractions qui

sont les types spatiaux de base, à savoir point, ligne et polygone, et cela en prenant en

compte uniquement leur position et non leur forme.

- Les primitives représentant des collections d’objets : par deux abstractions qui sont les

partitions et les réseaux. Une partition permet de représenter un ensemble de régions

disjointes, par exemple une partition peut représenter les quartiers d’une ville. Tandis que

le réseau permet de représenter un graphe constitué d’un ensemble de points (les nœuds

du graphe) reliés entre eux par un ensemble de lignes (les arêtes du graphe), par exemple,

un réseau peut représenter un réseau routier ou gazier[7].

Figure 7 : Primitives de représentation des collections d'objets selon l’OGC [7]

1.6. Structures d’indexation des données spatiales

Les bases de données spatiales doivent pouvoir contenir les données spatiales ainsi que les

relations entre elles. L'index spatial est une forme d'indexation utilisée par les bases de

données pour optimiser l’accès à ces données et les calculs impliquant les relations spatiales.

Pour indexer les données spatiales, on a recour soit à des arbres soit à des graphes [14][37].

1.6.1. Structures en arbre

Il existe plusieurs structures en arbre : Quad-tree, Oc-tree, KD-tree et R-tree :

- Quad-tree : ces arbres sont généralement utilisés pour indexer les espaces à deux

dimensions. Où chaque nœud interne de l’arbre divise l’espace en quatre sous-espaces

disjoints (appelés : NO, NE, SO, SE selon les axes). Chacun de ces sous-espaces est

2Open Geospatial Consortium


27

divisé récursivement jusqu’à qu’il n’y est qu’un seul et unique objet à l’intérieur de

chacun d’eux.

- Oc-tree : est une variante des Quad-tree, les nœuds sont divisés jusqu’à 8 sous-espaces, il

est généralement utilisé pour indexer les espaces à trois dimensions.

Figure 8 : Exemple d’un Quad-tree [37]

Figure 9 : Exemple d’un Oc-tree [37]

- KD-tree : est une structure de données en forme d'arbre binaire dans lequel chaque nœud

est un point dans un espace à K-dimensions.

- R-tree : est une structure de données similaire à un B-tree, utilisée comme méthode

d’accès spatiale, c'est-à-dire servant à indexer des informations multi-dimensionelles,

comme par exemple, les coordonnées (x,y) de données géographiques. Ce sont les arbres

les plus utilisés dans l’indexation spatiale. [37]


28

Figure 10: Exemple d’un R-tree [37]

Figure 11 : Exemple d’un KD-tree (K=3, 3D-tree) [37]

Il existe d’autres variantes des R-tree qui sont les R*-tree et les R+-tree.

Il existe d’autres arbres qui séparent les données dans un espace métrique qui est un ensemble

au sein duquel une notion de distance entre les éléments de l'ensemble est définie. Parmi ces

arbres on cite : VP-tree (Vantage Point, Point Privilégié), M-way VP-tree (Multi-way VP-

tree), MVP-tree (Multi-Vantage-Way), et les M-tree [37].

1.6.2. Structure en graphe

Il existe plusieurs types de graphes : le graphe du plus proche voisin relatif, le graphe de

Gabriel, la triangulation de Delaunay [14] [37].

Mais la structure la plus utilisée dans la fouille de données spatiales, est sans doute les

graphes de voisinage, car ils permettent de visualiser les relations spatiales.

Historiquement, la communauté de l’analyse spatiale de données s’est focalisée sur une

représentation de l’espace continu, soit par cellule, soit par ensemble de points soit par

zonage.


29

M=

Figure 12 : Graphe et matrice de voisinage

Les relations spatiales sont communément formalisées par la notion de graphe de voisinage,

et peuvent utiliser une représentation sous forme de matrice de voisinages. Celle-ci est une

matrice binaire M où M [i,j]=1 si l’objet i est voisin de l’objet j et M[i,j]=0 dans le cas

inverse [3][50][51]. Nous illustrons ceci par un exemple dans la Figure 12.

La notion de voisinage est générale et peut aussi bien représenter une contiguïté entre formes

zonales ou une proximité sur des points. Elle peut être étendue à une matrice de poids en

qualifiant la proximité par une distance. Dans ce cas, elle n’est pas binaire. La matrice de

voisinage est généralement symétrique, sauf si le graphe est orienté. Les distances par la

route, en tenant compte des voies à sens unique, sont, par exemple, une illustration de

graphes orientés.

1.7. Notion de couches thématiques

Une couche thématique est un regroupement d’objets spatiaux partageant les mêmes

propriétés, les mêmes structures en une collection homogène. Ce regroupement définit un

thème et est une approche naturelle de modélisation. Chaque thème peut ainsi désigner une

couche. Par exemple, une couche peut représenter de l’hydrologie ou de la pédologie. Pour

les traitements, on peut faire intervenir sélectivement les couches utiles. La superposition de

ces couches suivant la métaphore des papiers calques constitue une carte. Du point de vue

informatique, l’ensemble de ces couches thématiques constitue une base de données

géographique. [49].

Figure 13 : Exemple de représentation en couches thématiques [49]

1

2

3

4

1 0 1 0

0 1 1 1

1 1 1 0

0 1 0 1


30

Selon l’influence du voisinage qui définit les couches thématiques, on peut déduire deux

classes d’influence :

- Intra-thème comme l’auto-corrélation spatiale des mesures de phénomènes géographiques

(la température de deux lieux proches est proche) ;

- Inter-thèmes comme l’influence du trafic routier sur le phénomène de pollution et de bruit

[18].

2. Bases de données spatiales

Une base de données spatiales est une base de données optimisée pour stocker et interroger

des données reliées à des objets référencés géographiquement, y compris des points, les

lignes et des polygones, alors que les bases de données classiques peuvent comprendre

différents types de données numériques et caractères, des fonctions additionnelles ont besoin

d'être ajoutées pour stocker, traiter et requêter sur des données spatiales [50].

2.1. Parallèle entre les SGBD spatiaux et les SGBD relationnels

Malgré leurs spécificités, les SGBD3 Spatiaux peuvent être vus comme des extensions des

SGBD relationnels.

Ce parallèle est récapitulé par le Tableau 1 qui montre à gauche les concepts bien connus

dans le domaine des SGBD relationnels et à droite les concepts spécifiques aux SGBD

spatiaux. [50].

Tableau 1 : Parallèle entre SGBD spatiaux et relationnels [50]

Relationnel Spatial

Données Entier, réel, texte, … Plus complexes : point, ligne, région, …

Prédicats et calculs Tests : =, >, …

Calculs : +, /, …

Fonctions simples

Prédicats et calculs géométriques et

topologiques

Tests : en intersection avec, adjacent à,

…

Fonctions : Intersection, surface, …

Manipulations Opérateurs algébriques :

Sélection, projection,

jointure

Agrégats : Count, Sum,

Avg, …

Manipulations mono ou inter-thèmes

Sélection et jointure sur critère spatial

Agrégats : fusion d’objets adjacents

Liens entre objets Par clés de jointures Relations spatiales (souvent implicites)

Méthodes d’accès Index B-tree, hachage Index R-tree, Quad-tree…etc

3 Système de Gestion de Bases de Données


31

2.2. Architectures des bases de données spatiales

Pour évaluer les différents SGBD, il est important de considérer leur architecture qui impacte

leurs performances.

Il existe principalement (Figure 14) trois grandes familles d’architecture pour la gestion des

données sémantiques et des données spatiales. Ces architectures influent sur les

performances, la fiabilité et la cohérence dans la gestion des deux types de données.

Figure 14 : Différentes architectures des bases de données spatiales [50]

Ainsi, suivant la Figure 14 :

• L’architecture de gauche traduit la première génération de systèmes d’informations

spatiales qui place côte à côte un SGBD pour la gestion des données sémantiques et un

système propre (appelé également boîte à outils) pour gérer les données spatiales. Ce type

de couplage nécessite une couche d’intégration qui doit ventiler les demandes (requêtes)

des applications vers l’une des deux parties [50].

L’avantage est de pouvoir s’intégrer à n’importe quel SGBD commercial par exemple

dont il est impossible d’adapter le noyau en raison de l’inaccessibilité des codes sources.

Le SGBD est alors un serveur du système qui est sollicité pour gérer ce qu’il sait faire au

mieux, à savoir les données alphanumériques [50].

Le désavantage est un couplage faible. Bien qu’un objet spatial soit constitué de données

sémantiques et de données spatiales, le stockage dans les deux parties pose le problème de

cohérence entre les deux systèmes. Par exemple, la restauration après une panne d’un côté

ne garantit pas la cohérence avec l’autre côté. L’autre désavantage est de nécessiter que la

couche au-dessus joue le rôle de médiateur pour synchroniser la gestion d’objets

géographiques de part et d’autre. Ce rôle de médiateur se traduit par de nombreuses

requêtes qui dégradent les performances globales du système [50].


32

• L’architecture du milieu de la Figure 14 résout en partie les problèmes cités

précédemment. Les données spatiales et alphanumériques sont stockées uniformément

dans le SGBD. Ceci a été rendu possible grâce aux nouvelles possibilités des SGBD de

stocker des données binaires longues et non interprétées (appelé également BLOB44. La

construction d’un système d’information spatial consiste alors à placer une surcouche

chargée, comme dans le cas précédent, du traitement des opérations spatiales [50].

L’avantage est un stockage plus intégré des données spatiales. Cependant, l’exécution

d’une requête spatiale reste peu performante car toute requête doit être interprétée par la

couche supérieure qui doit ainsi solliciter de manière importante la couche du bas pour

évaluer toute requête. Signalons que cette approche a été mise en œuvre dans Oracle 8

avec les notions de “cartridges” (cartouches) [50].

• La dernière architecture, celle de droite de la Figure 14 montre un système totalement

intégré. Un tel système résout les problèmes évoqués. Cependant, l’offre est pauvre dans

cette approche, car elle nécessite de concevoir un SGBD entier, ce qui requiert des

ressources de développement très importantes. Il existe des prototypes de recherches dans

cette catégorie d’architecture comme le Système d’information géographique GéoSabrina

[50].

En résumé, l’architecture peut influer sur la fiabilité des données gérées et sur les

performances. Les évolutions de ces architectures ont permis d’aller vers un couplage de plus

en plus fort entre la partie sémantique et la partie spatiale. Ces évolutions garantissent des

performances et une fiabilité accrue. [50]

3. La fouille de données spatiales

La fouille de données spatiales consiste à appliquer la fouille de données dans un but

décisionnel sur des données à caractère spatial susceptibles de délivrer des informations ou

des connaissances implicites. Celles-ci peuvent être des relations spatiales ou d'autres

propriétés non explicitement stockées dans la base de données spatiales [51].

Afin de mieux comprendre la fouille de données spatiale, il existe un exemple pour

illustrer l’extraction de connaissances depuis des données spatiales. Cet exemple remonte à

1854 où une épidémie de choléra avait touché Londres. Le principe est de lier les

concentrations de cas et les mettre en relation avec des points d’eau par Dr Snow, puis il

ordonna leur fermeture, ce qui a stoppé l’épidémie. En quelque sorte, le Dr. Snow a fouillé

des données spatiales par l’extraction des relations entre les puits et les cas de choléra [51].

Tableau 2 : Fouille de données spatiales VS analyse spatiale [51]

Fouille de données spatiales Analyse spatiale (Dr J. Snow)

Découverte automatique de connaissances Découverte visuelle de connaissances

Exploratoire (génère des hypothèses) Confirmatoire

4Binary Large Object qui peut aller jusqu’à 4Gb


33

Opère sur des gros volumes de données Inapplicable sur des BD volumineuses

3.1. Spécificité de la fouille de données spatiales

La particularité de la fouille de données spatiales par rapport à la fouille de données

classique, est le fait de prendre en compte des relations spatiales entre objets qui sont souvent

implicites. Les méthodes classiques de fouille de données sont insuffisantes pour ce type

d’analyse. C’est ce qui a motivé les recherches en fouille de données spatiales [12].

Contrairement aux données classiques, les données spatiales sont dépendantes, car tout

phénomène naturel est influencé par son voisinage. Cette dépendance est justifiée par la

première loi de géographie[12]. Du point de vue analyse de données, ceci revient à dire que

l’analyse spatiale nécessite l’analyse des entités spatiales en fonction de leurs

caractéristiques, les caractéristiques de leurs voisins et les relations spatiales. Analyser ces

données sans tenir compte de cette spécificité génère des résultats erronés et incorrects [12].

Prendre en compte cette spécificité nous pose deux problèmes. Le premier est lié à

l’inadaptation des méthodes existantes de data mining à ce type d’analyse. Le deuxième est

dû à la complexité de calcul des relations spatiales.

3.2. Inadaptation des techniques de la fouille de données Classique aux données

spatiales

Selon [51] Aucune méthode d’analyse de données ne permet d’analyser les données

dépendantes. En effet, la statistique et l’analyse de données, ainsi les méthodes de fouille de

données traditionnelles supposent toutes les données indépendantes. De plus, aucune de ces

méthodes ne peut interpréter les propriétés spatiales ni découvrir les liens entre objets

spatiaux. Toutes traitent des données simples de type numérique ou chaîne de caractère.

Certes, les systèmes d’information géographique et la statistique dite spatiale intègrent

parfaitement les relations spatiales, mais ils restent encore limités dans l’analyse spatiale

exploratoire. En fait, les SIG, même s’ils permettent d’interroger les données spatiales et de

répondre à un certain calcul (exemple : trouver la surface d’une lagune), ne permettent pas de

découvrir des modèles, ni des règles ou de nouvelles connaissances cachées dans les bases de

données spatiales. La statistique spatiale, même si elle est largement répandue et offre un

grand nombre de techniques allant de la géostatistique à l’analyse globale et locale

d’autocorrélation ou l’analyse de données multi-variées, reste le plus souvent confirmatoire,

guidée par un expert, basée sur des données numériques et ne découvre pas de règles. De

plus, l’analyse exploratoire de données multi-variées sous contrainte de contiguïté présente

l’inconvénient de ne considérer que les relations entre objets d’une même table excluant les

relations spatiales pouvant exister entre objets de tables différentes. Par conséquent, ces

méthodes ne sont pas adaptées à la fouille des données spatiales [51].


34

Conclusion

Ce chapitre nous a permis de faire le tour d’horizon des données spatiales, à commencer par

les distinguer des données classiques, nous avons aussi retenu certaines particularités dont la

dépendance entre elles qui leur permet de traduire une caractéristique essentielle du monde

réel, à savoir la notion de voisinage. De ce fait, elles sont plus complexes à appréhender, d’où

l’émergence de la fouille de données spatiales qu’on a définit ainsi que ses particularités, et

précisé aussi pourquoi les techniques de la fouille de données classique ne sont pas adaptées à

la fouille de données spatiales d’où l’émergence de nouvelles approches pour y remédier, que

nous présentons dans le chapitre suivant.

Chapitre II : État de l’art

35

Chapitre II État de l’art sur la fouille de données

spatiales


36

Introduction

Les méthodes de la fouille de données spatiales sont, pour la plupart, une extension de celles

de la fouille de données classiques. Cependant, elles engendrent plus de problèmes de

performances en raison du volume de données important généré par le codage des

localisations géométriques et la complexité du calcul des relations spatiales. Les recherches

sur la fouille de données spatiales visent donc à proposer et optimiser des méthodes d’analyse

tenant compte des relations spatiales.

Comme ce domaine est à la croisée de plusieurs disciplines, cette recherche est menée au sein

de deux communautés : des statisticiens s’intéressant à l’analyse spatiale et des chercheurs en

bases de données [17] [31] [51].

Quant à l’approche statistique, elle comprend d’anciens travaux comme sur l’autocorrélation

spatiale et la géostatistique.

En ce qui nous concerne, nous allons détailler plus les travaux s’intéressant aux bases de

données spatiales qu’à ceux par approches statistiques.

Nous avons été intéressés par des travaux des approches de la fouille de données spatiales

sous une autre vision, de la même façon qu’on distingue deux perceptions de l’information

géographique, on peut distinguer deux approches respectives en fouille de données spatiales.

Elles dépendent de la manière de considérer les relations spatiales. Certaines méthodes ne

considèrent que les relations intra-thème. Elles constituent la première approche, appelée

fouille de données monothématique [51].. Elles sont souvent apparentées aux statistiques et

à l’analyse de données. L’idée est d’incorporer un paramètre de contiguïté dans le modèle ou

d’effectuer une pondération des variables par les valeurs du voisinage. Ceci est faisable car

s’agissant d’un même thème, les données sont décrites avec les mêmes variables et sont

comparables [51].

Par contre, si on considère le voisinage entre thèmes on ne peut plus appliquer ces méthodes,

car ce qu’il nous intéresse c’est de décrire ou d’expliquer un phénomène par un autre ayant

lieu au même endroit ou proche de cet endroit. La seconde approche est désignée par fouille

de données multi-thèmes. Les méthodes de fouille de données multi-thèmes sont

généralement basées sur des prédicats spatiaux interprétés comme des propriétés à prendre en

compte dans le modèle à induire. Pour cela, ces méthodes distinguent un thème cible de

l’analyse et explorent les autres thèmes (ou phénomènes) susceptibles de l’influencer. Enfin,

certains travaux distinguent des catégories d’objets, comme la recherche de co-localisation de

phénomènes différents [51], mais dans ce cas, seule la catégorie et la localisation sont

utilisées dans la description de l’objet, sans pouvoir tenir compte d’autres attributs. Or, un

thème est généralement décrit par plusieurs attributs et ces attributs sont différents d’un thème

à l’autre. Par conséquent, la méthode de co-localisation a été considérée comme

monothématique [26] [27] [38] [51].


37

Donc suivant cette perception, nous allons organiser et classer l’exposition des différentes

approches.

Ces techniques sont impliquées dans divers domaines : Systèmes d’informations

géographiques, science de la terre, météorologie, géologie, science de l’environnement,

médecine et épidémiologie, sécurité, économie, … etc

Nous allons citer les différentes applications de la fouille de données spatiales sur plusieurs

domaines, mais comme il en existe une grande variété, il est difficile de les exposer selon une

certaine organisation. C’est pourquoi on a préféré les citer selon les catégories de tâches de la

fouille de données. On peut appliquer plusieurs techniques dans un seul domaine, souvent

pour des raisons de comparaison, mais notre but est d’illustrer le plus de travaux possibles.

En ce qui concerne les méthodes de la fouille de données, elles peuvent être classées en deux

catégories : les méthodes utilisées dans une phase exploratoire et les méthodes à caractère

plus décisionnel qui cherchent à prédire une donnée (un attribut) particulière.

1. Approches monothématiques

Il existe plusieurs approches monothématiques que nous décrivons brièvement dans ce qui

suit :

1.1. Analyse de localisations sans attributs

Parmi les approches monothématiques, certaines sont basées uniquement sur les localisations.

Elles explorent généralement un ensemble de localisations (ensemble de points) pour révéler

des tendances ou des concentrations [51]. L’approche de regroupement (clustering) spatial

proposée dans [25] peut être classée dans cette catégorie, on peut citer aussi :

- L’analyse de tendances par la méthode de densité [29].

- La Segmentation (Clustering) [25].

1.1.1. Analyse de localisations munies de mesures numériques

Cette catégorie s’intéresse aux mesures relevées sur un domaine spatial, souvent couvrant

l’espace par un découpage surfacique. Il s’agit souvent d’un seul attribut numérique.

L’analyse vise à caractériser la variation spatiale de cette ou de ces mesures. On peut citer

- L’auto-corrélation spatiales globale et locale [15].

- L’analyse de tendances par régression linéaire [24].

1.1.2. Analyse de localisations munies de catégories

Dans cette catégorie, les localisations sont supposées être décrites par des attributs catégoriels.

L’analyse porte sur la présence simultanée de catégories dans l’espace ou sur les propriétés

caractéristiques s’étendant au voisinage. On peut citer la co-localisation. [30] [46] et la

caractérisation. [23].


38

2. Approches multi-thématiques

Nous présentons dans cette partie les travaux de la fouille de données spatiales

multithématiques. On cite les règles d’association, la programmation logique inductive et les

arbres de décisions concernant l’analyse prédictive, sur lesquels beaucoup de contributions

ont été apportées et qui ont été appliqués à plusieurs domaines.

2.1. Les règles d’associations

Afin de mieux comprendre ce type d’approche, le lecteur peut se référencer à l’annexe II où

nous présentons les concepts de base des règles d’associations.

L’extension de la découverte de règles d’association aux données spatiales permet de générer

des règles de type :

X → Y (s, c) avec un support s et une confiance c

Telles que X et Y sont des ensembles de prédicats, dont au moins un est un prédicat spatial.

En d’autres termes, ces règles correspondent à des associations entre des propriétés des objets

et celles de leurs « voisins ». Cette méthode génère pour chaque objet d’un thème cible de

l’analyse, une liste de prédicats comprenant sa description, la description d’objets liés d’autres

thèmes et leurs relations spatiales avec l’objet. Cette liste constitue des items d’une

transaction sur laquelle un algorithme de type APRIORI ( Voir Annexe II) peut opérer pour

générer des règles d’association spatiales de type :

Signifie que si l'objet est une école elle est proche d'un parc avec un taux de confiance de

80%. école et parc sont des objets, proche_de est un prédicat [51].

Cette méthode permet, en outre, de générer des règles multi-niveaux en exploitant à la fois la

généralisation des attributs sur la base d’une hiérarchie de concepts et la généralisation de la

relation spatiale de voisinage [2] [51], nous exposons dans ce qui suit deux approches

d’extraction de règles d’associations : l’approche de treillis de Galois et l’approche de

l’application de l’algorithme Apriori sur des données spatiales.

2.1.1. Travail 1 : Treillis de Galois pour l’extraction des règles d’associations

Cette technique a été appliquée par [34] [35] dans le domaine de la géographie économique,

qui étudie la répartition spatiale et la localisation des activités économiques. Dans cet

exemple, le contexte est l’analyse et la promotion du marché de l’internet au Maroc.

L’approche est basée sur les fondements mathématiques du concept de Treillis de Galois

notamment la fermeture de la connexion de Galois en utilisant l’algorithme CLOSE (Voir

annexe II) dans un contexte spatial pour l’extraction des règles d’association.


39

Afin d’élaborer le contexte spatial d’extraction, il faut d’abord déterminer les prédicats

spatiaux, selon le choix de l’utilisateur, ensuite calculer les distances de chaque objet spatial

avec tous les autres objets spatiaux des différentes couches thématiques.

La détermination des relations métriques basées sur la distance se fait par le calcul des

différentes distances de la manière suivante : pour chaque objet spatial, il faut calculer sa

distance avec les autres objets, dont les indices sont supérieurs à l’indice de l’objet choisi.

L’indice représente le numéro d’ordre de l’objet dans la table regroupant les différents objets

des différentes couches thématiques.

Figure 15 : Calcul des relations spatiales entres les différents objets [35]

Une fois les distances calculées, on associe à chaque objet spatial, dans un premier temps, les

prédicats correspondants, en faisant un parcours de la table contenant les relations des

différentes couches thématiques. Ensuite on va choisir à partir des différentes sources de

données les attributs non spatiaux répondant à l’objectif défini par le décideur.

Cette approche a été expérimentée sur une base de données fournie par L’Agence Nationale

de la Réglementation des Télécommunications (ANRT) Marocaine, dans le but de

promouvoir le marché de l’internet au Maroc, en étudiant le cas des cybercafés. Cinq couches

thématiques ont pu être distinguées, à savoir les cybercafés, les établissements

d’enseignements, les centres culturels et de loisirs, les réseaux routiers, les communes et les

zones des bidonvilles.

D’après les tests de performances, l’utilisation de l’algorithme CLOSE basé sur la fermeture

de la connexion de Galois est une alternative importante dans le cas d’un jeu de données

denses et corrélés par rapport à l’algorithme Apriori, que ce soit au niveau du temps

d’exécution ou l’occupation d’espace mémoire.

2.1.2. Travail 2 : Application de l’algorithme Apriori à la fouille de données spatiales

multithématique

Cette approche a été appliquée dans le domaine de la géographie de la population, qui étudie

la distribution de cette dernière à la surface du globe et les variations de cette répartition [5].


40

La base de données utilisée contient des tables concernant la population, l’hypsographie, l’eau

surfacique et l’eau sous terraine en Algérie. Le but est d’étudier la distribution de la

population, et d’essayer de trouver des associations avec l’environnement.

La procédure suivie par [5] définit d’abord deux couches distinctes, une couche référence et

une couche descriptive, ainsi qu’un ensemble de prédicats spatiaux décrivant les relations

entre ces deux couches. La première phase permet d’extraire les relations spatiales entre les

couches de la base de données spatiale par calcul approximatif de la distance Euclidienne. Les

relations extraites sont stockées dans une table. La deuxième phase génère et calcule les

ensembles de prédicats fréquents (itemsets). Tout d’abord, l’algorithme Apriori [39] est

appliqué à chaque table de la base de données. Ensuite, pour chaque couche de référence, il

est aussi appliqué à chaque table des relations spatiales calculées dans la première phase. Les

itemsets calculés doivent contenir un prédicat spatial qui spécifie la relation spatiale entre la

couche de référence et la couche descriptive. Puis combine l’ensemble des itemsets générés et

calcul leurs supports. Finalement, la dernière phase génère les règles d’associations spatiales.

Pour extraire uniquement les règles d’associations valables, un critère appelé

"contraintessyntaxiques" a été utilisé. Ce dernier implique des restrictions aux prédicats qui

peuvent apparaitre dans une règle. Par exemple n’extraire que les règles ou un prédicat

spécifique apparait dans la conséquence.

Le jeu de données utilisé contient des tables concernant la population, l’hypsographie, l’eau

surfacique et l’eau sous terraine en Algérie. Le but est d’étudier la distribution de la

population, et d’essayer de trouver des associations avec l’environnement.

2.2. Approche basée sur la programmation logique inductive

Cette approche propose de se ramener à la programmation logique inductive (PLI) pour

résoudre le problème multi-relationnel. Elle consiste à transformer les données en entrée du

processus d’analyse qui se présentent sous plusieurs relations (table cible, table voisin et table

d’indexe de jointure) en logique des prédicats et à appliquer ensuite les méthodes de la PLI

pour l’extraction des connaissances. [11] [51]

L’avantage de cette approche est de bénéficier du pouvoir expressif de la logique des

prédicats, de la simplicité de ses modèles et la possibilité d’intégrer des connaissances

implicites lors du processus d’analyse. Par contre, elle hérite aussi des inconvénients de la PLI

à savoir la lenteur d’exécution sur des jeux de données volumineux.

Cette approche a été appliquée au domaine de l’épidémiologie pour l’analyse de la

contamination des coquillages. La conclusion est que les bassins versants urbains sont

majoritairement la cause de la contamination car il y’a plus de prélèvements contaminés à leur

alentours.

2.3. Classification par arbres de décisions

Les concepts de base des arbres de décision sont présentés en annexe.


41

2.3.1. Travail 1 : Extension de l’algorithme CART pour les données spatiales

Les travaux présentés dans [9] [10] [12] [13] et décrits dans [51] s’intéressent à la

classification des données spatiales par arbre de décision en utilisant l’algorithme S-CART.

Ces méthodes ont été mises en œuvre dans le cadre de l’analyse des risques d’accidents

routiers. Trois alternatives ont été étudiées que nous présentons comme suit :

A. Interroger à la volée les différentes tables

Cette approche prend en entrée trois tables : table des objets à analyser, tables des objets du

voisinage et un index de jointure spatial. Chaque fois que l’attribut à analyser est un attribut

du voisinage, l’algorithme S-CART fait appel à une double jointure entre la table de faits,

l’index et la table de voisinage c’est là que réside la modification à apporter aux algorithmes

existants [12] [51].

B. Matérialisation des jointures

Le principe de cette approche consiste à matérialiser les jointures entre les trois tables de

l’analyse : la table cible, la table voisine et la table index de jointure spatial une fois pour

toute afin d’éviter de les recalculer à chaque fois. La jointure conduit à la duplication des

objets de l’analyse, la méthode de fouille de données a été modifiée sur le résultat de la

jointure afin de prendre en compte cette duplication.[12] [51].

C. Réorganisation des données en une seule table

Le principe de cette approche est l’utilisation de l’opérateur CROISEMENT (voir annexe IV)

qui a pour rôle de joindre les différentes tables en entrée du processus d’analyse en une seule

table, ce qui fait que les données seront soumises à un prétraitement avant l’application de

l’algorithme d’apprentissage. La seconde étape est l’application de l’apprenant sur la table

résultante de l’application de l’opérateur CROISEMENT sans modification préalable de

l’algorithme CART. Cet opérateur consiste à construire une seule table à partir des jointures

sur les différentes tables sans dupliquer les objets. L’idée est de compléter au lieu de joindre

la table d’analyse par des données présentes dans les autres tables. Le principe est de générer

pour chaque valeur d’attribut de la table liée un attribut dans la table résultat :

Soient , et trois tables dont les clés sont

celles soulignées et telles que les attributs sont qualitatifs et leurs valeurs

distinctes. Soit un ensemble de fonctions agrégats.

est une table ayant le schéma suivant :

de clé et où :

,

• .

• si est non vide, la

valeur sinon.


42

désigne le poids ou la relation spatiale dans la fouille de données spatiales. est une table de

correspondance pondérée qui relie la table de « faits » à analyser avec une table comprenant

des « dimensions » à considérer. L’opérateur d’agrégat est noté

. Les opérateurs et

désignent respectivement la sélection et la jointure [12] [51].

Les trois approches (Jointure à la volée, matérialisation des jointures et la réorganisation des

données en une seule table) ont été appliquées sur un même jeu de données traitant le

domaine de l’accidentologie.

Les expérimentations se sont faites sur huit échantillons de données relatifs à la sécurité

routière, l’algorithme CART fut utilisé dans le cadre de la fouille de données spatiales pour

implémenter les approches. Les critères retenus pour la comparaison sont la taille de la table

cible, la taille de la table liée et la taille de l’index de jointure spatial étant donné que les tests

se sont effectués dans le cadre de la fouille de données spatiales.

Les résultats montrent que l’approche 2 qui est la matérialisation des jointures, présente de

meilleures performances en comparaison avec l’approche jointure à la volée et l’approche

réorganisation des données en une seule table en termes de temps d’exécution et en fonction

de l’accroissement de la taille de l’échantillon de données.

2.3.2. Travail 2 : Extension de l’algorithme ID3 pour les données spatiales

Le travail présenté dans [48] propose un nouvel algorithme des arbres de décisions spatiales

basé sur l’algorithme ID3 pour les caractéristiques discrètes représentées avec des points,

lignes et polygones.

L’algorithme ID3 utilise le gain informationnel pour la sélection des attributs ; l’algorithme

proposé utilise le gain informationnel spatial pour choisir la meilleure couche de division à

partir d’un ensemble de couches explicatives. La nouvelle formule pour le gain

informationnel spatial est proposée en utilisant des mesures spatiales pour les caractéristiques

points, lignes et polygones.

Le résultat montre que l'algorithme ID3 peut être utilisé pour la jointure de deux objets

spatiaux dans la construction d’un arbre de décision spatial sur un petit ensemble de données

spatiales. L'algorithme proposé a été appliqué à un ensemble de données spatiales réel

constitué des points et des polygones. Le résultat est un arbre de décision spatiale avec 138

feuilles et avec une précision de 74,72%.

Conclusion

Dans ce chapitre, nous avons exposé certains travaux concernant les techniques de la fouille

de données spatiales en utilisant les diverses tâches de la fouille de données spatiales, et parmi

les méthodes de la fouille de données spatiales, on s’intéresse aux arbres de décisions et cela


43

revient à la lisibilité du modèle de prédiction grâce à l’arbre de décision généré. Ce dernier

constitue une technique exploratoire privilégiée pour appréhender de gros fichiers de données.

Parmi les algorithmes des arbres de décision présentés dans ce chapitre, notre choix s’est

porté sur l’algorithme C4.5 qui génère un arbre n-aire contrairement à l’algorithme CART qui

génère des arbres binaires. L’algorithme C4.5 traite aussi les valeurs continues et les valeurs

manquantes contrairement à l’algorithme ID3. Dans le chapitre suivant nous décrivons

l’approche proposée.

Chapitre III Approches proposées

Chapitre III : Approches proposées

45

Introduction

Dans le précédent chapitre, nous avons exposé quelques travaux et approches de la fouille de

données spatiales. Parmi ces approches nous nous sommes intéressés à la fouille de données

spatiales par les arbres de décision.

Dans ce chapitre, nous commençons d’abord par argumenter nos choix, ensuite nous

présentons nos approches selon notre étude, soit un phénomène par un phénomène ou par

plusieurs autres phénomènes.

1. Justification de nos choix

1.1. Pourquoi les arbres de décision ?

La production d’un arbre de décision aboutit à la répartition d’une population d’individus en

groupes homogènes, selon un ensemble de variables discriminantes en fonction d'un objectif

fixé et connu. À ce titre, cette technique fait partie des méthodes d’apprentissage supervisé. Il

s’agit de prédire avec le plus de précision possible les valeurs prises par la variable à prédire

(objectif, variable cible, variable d’intérêt, attribut classe, variable de sortie, …) à partir d’un

ensemble de descripteurs (variables prédictives, variables discriminantes, variables d'entrées).

Le succès réside en grande partie à ses caractéristiques :

- Lisibilité du modèle de prédiction, l’arbre de décision fourni.

- Capacité à sélectionner automatiquement les variables discriminantes dans un fichier de

données contenant un très grand nombre de variables potentiellement intéressantes. En ce

sens, un arbre de décision constitue une technique exploratoire privilégiée pour

appréhender de gros fichiers de données.

L’adaptation des arbres de décisions aux données spatiales, prend en entrée une base de

données spatiale BDS, qui contient plusieurs tables : table1, table2,…etc, chaque table

dispose d’un ensemble de colonnes ou attributs, parmi lesquels on doit spécifier un sous

ensemble d’attributs d’intérêt : attribut1, attribut2,… . Parmi l’ensemble de tous les attributs

et toutes les tables, on détermine un seul et unique attribut à prédire ou expliquer

attributCible.

1.2. Limitation des travaux précédents basés sur les arbres de décision

Les approches existantes basées sur les arbres de décision présentées précédemment,

présentent certaines limites :

- La première réside dans le fait que ces approches ne considèrent qu’une seule relation

spatiale (généralement la distance), or, les données spatiales sont caractérisées par

plusieurs relations qui les relient entre elles, et le fait de ne considérer qu’une seule

relation et une seule table voisine, limite les résultats de l’analyse et de la fouille de ces

données.


46

- La seconde limite concerne la non prise en charges des données continues, qui sont très

fréquentes dans les bases de données spatiales (mesures, relevés météorologiques, …), tel

que l’utilisation de l’algorithme ID3.

- La troisième limite a été constatée lors de la génération des arbres de décisions binaires,

évoluant en profondeur uniquement, tel que l’utilisation de l’algorithme CART.

Afin de palier à la première limite, nous considérons le problème dans sa généralité, c’est-à-

dire que les données spatiales peuvent être reliées entre elles par différentes relations spatiales

(Distance, direction, relations topologiques).

Afin de palier à la seconde et troisième limite, nous proposons d’utiliser l’algorithme C4.5

que nous argumentons dans ce qui suit.

1.3. Pourquoi C4.5 ?

Une fois qu’on a opté pour les arbres de décision, il reste à choisir un algorithme parmi ceux

des arbres de décision. Là encore, notre choix s’est porté sur l’algorithme C4.5 et ce choix

s’est fait après une comparaison entre les algorithmes existants, pour en choisir celui qui

répond le mieux à nos besoins selon les critères suivants :

• Type de données supportées.

• Rapidité et performances.

• Utilisation de la mémoire.

• Arbre de décision généré.

Lors de nos recherches, nous avons étudié plusieurs algorithmes des arbres de décision. Nous

avons résumé de façon très brève leurs principales lacunes :

L’algorithme CART permet de générer uniquement des arbres de décision binaires, ce qui

peut limiter l’analyse de l’arbre généré.

L’algorithme ID3 ne traite que les données discrètes, ce qui peut limiter l’extraction de

connaissances.

Pour ce qui est de C4.5, qui est une amélioration de l’algorithme ID3, il permet de prendre en

compte un grand éventail de données que ce soit des variables catégorielles ou numériques, le

seul désavantage est le fait de discrétiser les variables continues. Pour ce qui est du critère de

division, il se fait à partir du calcul du gain informationnel qui est la différence d’entropie.

Enfin, il permet de générer des arbres de décisions N-aires contrairement à l’algorithme

CART.

Sachant qu’on va travailler sur des données spatiales, notre choix s’est porté sur cet

algorithme C4.5, connu pour sa rapidité, il nous permet de garder des performances

acceptables, surtout en termes de temps d’exécution, et de prendre en considération un

maximum de types de données, y compris les données continues, et même d’assurer la gestion

des données manquantes.


47

2. Approches proposées

Les différentes approches proposées suivent les étapes suivantes :

- Création de l’index de jointure spatial.

- Application de l’algorithme S-C4.5.

- Génération de l’arbre de décision spatial.

- Extraction des règles de décision à partir de l’arbre généré.

2.1. Index de jointure spatial

L'aspect principal de la fouille de données spatiales est la prise en compte des relations

spatiales entre les objets. L’index de jointure spatial a été proposé pour calculer les relations

spatiales entre les collections d'objets de différentes couches thématiques et pour améliorer les

performances des opérations complexes dans un système de gestion de base de données

(SGBD ). L’index de jointure spatial (IJS) est une structure secondaire qui joint et stocke les

références des tuples permettant l’optimisation des requêtes de jointure. La fouille de données

spatiales utilise d’une manière intensive les relations spatiales car ces dernières mettent en

évidence l’influence du voisinage entre les entités spatiales. Ces relations sont à l’origine

implicites et nécessitent des jointures coûteuses sur des critères spatiaux pour être exhibées.

Pour les rendre explicites, une extension aux données spatiales fut proposée par [27]. À la

différence des jointures les plus courantes en relationnel, les jointures spatiales ne sont pas des

équi-jointures, mais des jointures sur critère spatial. Ce critère peut porter sur n’importe

quelles relations spatiales : topologiques, métriques ou directionnels. [51]

L’index de jointure a un double but. Le premier est d’accélérer toutes les jointures spatiales de

proximité (topologique ou métrique). Le second est d’enrichir par la matérialisation de la

relation spatiale, la base de données et de ramener le raisonnement spatial à des requêtes

relationnelles [51].

La définition du périmètre utile permet de réduire l’espace de stockage de l’index et la durée

nécessaire à son calcul. Dès lors, le coût de construction de cet index équivaut à celui de la

jointure spatiale sur critère de distance, mais son avantage est de permettre de gagner ce coût

lors des multiples utilisations ultérieures des relations spatiales pré-calculées.

Parmi les avantages de l’index de jointure spatiale, on peut citer :

• Stockage des relations spatiales ce qui évite de les recalculer à chaque application.

• Le même index permet d’accélérer les jointures selon tout prédicat spatial dans la limite

du périmètre défini.

• Il représente de manière sémantique toute relation spatiale entre objets.

• Il ramène le problème de la fouille de données spatiale à la fouille de données

relationnelles [51].

Le résultat de l’index de jointure spatial est une nouvelle table qui contient les résultats

précalculés des relations spatiales entre différents objets. La figure 16 montre le schéma de

base d’un index de jointure spatial IJS (IDX, SR, IDY), où IDX et IDY sont respectivement des


48

identifiants d’objets et SR leur relation spatiale calculée, qui peut être topologique, métrique

ou directionnelle. Par exemple, dans le cas d'une relation métrique, SR contiendra la valeur de

la distance exacte. IJS peut être traité de la même manière que les autres tables et manipulé à

l'aide du langage SQLquery standardisé. L'introduction de cette nouvelle table intermédiaire

augmentera l'espace requis en fonction du nombre de relations spatiales incluses. Pour réduire

l'utilisation de la mémoire supplémentaire générée par le IJS, les objets concernés seront

référencés via leurs identifiant ID. Les relations spatiales précalculées peuvent être des

variables quantitatives (discrètes / continues) et stockées telles quelles ou des variables

qualitatives et seront stockées à l'aide de techniques de codage des données.

Figure 16: exemple d’index de jointure spatial

Afin de pouvoir traiter les données spatiales, nous proposons l’algorithme S-C4.5 (Spatial

C4.5), qui est l’adaptation de l’algorithme C4.5 aux données spatiales selon deux

modifications, la première est au niveau de l’organisation de données, et la seconde est au

niveau de l’algorithme C4.5.

Modification de l’organisation de données : Cette modification est nécessaire afin

d’examiner la nature spatiale des données, qui consiste à inclure parmi les données d’analyse,

les relations spatiales précalculées dans l’index de jointure spatiale (IJS). Pour cela, nous

avons proposé différentes structures pour différentes approches permettant d’évaluer le

compromis de besoins en espace mémoire et temps de traitement. Ces structures peuvent être

réparties en deux principales catégories : celles nécessitant peu de prétraitements et d’autres

regroupant toutes les données, dans les deux cas, l’idée est de ramener la fouille de données

spatiales vers une fouille multi-relationnelle par jointure ou matérialisation (avant ou durant

l’exécution) tout en considérant l’aspect spatiale de ces données par la distinction des

relations spatiales. Ces différentes structures sont détaillées un peu plus loin dans la partie 2.3

relative à l’étude d’un phénomène par plusieurs autres phénomènes.

Modification de l’algorithme : Cette modification est nécessaire pour prendre en charge la

nature multi-relationnelle des données spatiales, qui sont généralement organisées en

Table d’objets X

IDX Att X

… Att X’

X01 X1 … X’1

X02 X2 … Y’2

… … … … XN XN … X’N

Index de jointure

spatiale

IDX SR IDY

X01 15 Y01 X01 2 Y02 X01 18 … X01 68 YN

X02 140 Y01 X02 46 Y02 X02 7 … X02 12 YN

… .. XN 31 YN

Table d’objets Y IDY Att Y … Att Y’ Y01 Y1 … Y’1

Y02 Y2 … Y’2

… … … …

YN YN Y’N


49

plusieurs tables représentant chacune un phénomène spatial. La modification réside surtout

dans le calcul du gain informationnel, si l’attribut cible se trouve dans la table cible, alors le

gain informationnel est calculé directement, sinon pour chaque attribut voisin, une jointure est

nécessaire avant le calcul du gain (Le calcul du gain informationnel est détaillé dans l’annexe

I).

Quel que soit l’organisation de données adoptée, le fait de ramener la fouille de données

spatiales vers une fouille de données multi-relationnelle tout en gardant les propriétés

spatiales, permet la construction de l’arbre par division successive du résultat de la jointure ou

la matérialisation. Cette division successive évalue le gain informationnel pour chacun des

critères de division possibles. C’est là qu’on intègre l’interprétation de la notion du voisinage

en tant que combinaison entre attribut descriptif et relation spatiale.

Dans la fouille de données classique, les conditions sont testées en tant que « Table.Attribut

Comparateur Valeur ». Dans la fouille de données multi-relationnelles, on introduit la notion

de table cible et voisins explicatifs, les conditions sont donc testées en tant que

« Cible.Attribut Comparateur Valeur » pour les attributs de la table cible et « Voisin.Attribut

Comparateur Valeur » pour les attributs des tables explicatives.

Pour ce qui est de la fouille de données spatiales, l’aspect spatiale doit être considéré, faute de

quoi, elle n’apporterait aucune description de l’influence du voisinage par rapport à la fouille

multi-relationnelle. Dans ce cas, les conditions sont donc testées en tant que « Cible.Attribut

Comparateur Valeur » pour les attributs de la table cible et « Voisin.Attribut Comparateur

Valeur ET Voisin à Relation R de Cible ». Parmi l’ensemble de ces divisions, on sélectionne

celui maximisant le gain informationnel, on retient donc la combinaison entre la valeur de la

relation R la plus discriminante pour chaque propriété.

Concrètement, dans notre cas qui est basé sur l’algorithme C4.5 utilisant l’entropie pour la

mesure de l’incertitude d’une variable dans le calcul du gain d’information, on passe de la

formule classique à la mesure d’une entropie conjointe entre attribut explicatif voisin et

relation spatiale.

Dans le cas d’un attribut voisin explicatif sans influence spatiale, on garde la formule

classique de l’entropie, où pour une variable aléatoire V comportant n symboles, chaque

symbole vi ayant une probabilité d'apparaître Pi, l'entropie E de la variable V est définie par :

Dans le cas d’un attribut voisin explicatif avec influence spatiale, on utilise la formule de

l’entropie conjointe, où chaque paire d’états possibles (rsx, v) d’une relation spatiale RSX et

d’une variable aléatoire V ont une probabilité d'apparaître P RSx , V, l’entropie Ec conjointe de

(RSX, V) est définie par :


50

Ainsi, l’entropie conjointe Ec est calculée pour chaque variable V autant de fois que de

relations spatiales RSX considérées. La combinaison maximisant le gain informationnel sera

retenue.

Dans la pratique, cela se traduit par le calcul du gain informationnel par les couples (relation

spatiale, attribut explicatif), par exemple : (distance=proche, bâtiment=école),

(inclusion=hors, zone=urbaine).

N.B. : L’élagage et la gestion des données manquantes sont hors cadre de notre travail.

Nous avons appliqué notre algorithme S-C4.5 sur deux cas d’études majeur :

- 1er cas : Etude d’un phénomène par un seul autre phénomène.

- 2eme cas : Etude d’un phénomène par plusieurs autres phénomènes.

Nous présentons au préalable les différentes études effectuées, et exposons ensuite

l’algorithme général S-C4.5 applicable à tous les cas étudiés.

2.2. Etude d’un phénomène par un seul phénomène :

Cette étude consiste à prendre deux tables en entrées : une table cible (Phénomène Cible), et

une table voisine (Phénomène Voisin), et un index de jointure spatiale qui relie le premier

phénomène avec le second phénomène en incluant une ou plusieurs relations spatiales.

La table cible est automatiquement désignée au moment où on choisit un attribut cible qui

représente un certain phénomène pour lequel on va effectuer une étude spatiale. Elle peut être

définie comme étant la table qui contient l’attribut cible, et il ne peut donc y avoir qu’une

seule et unique table cible.

La table voisine définit un phénomène pris en considération afin d’expliquer le phénomène

cible.

La table Index de jointure spatiale contient les résultats précalculés des relations spatiales

entre les différents objets (tables). L’index de jointure spatiale est nécessaire afin d’inclure le

caractère spatial de ces données, il est donc obligatoirement pris en considération comme un

intermédiaire afin de permettre une jointure entre la table cible et la table voisine.

Nous divisons notre étude selon deux cas : Le premier cas considère une seule relation

spatiale entre les deux phénomènes étudiés (table cible, et la table voisine) ; et le deuxième

cas, considère plusieurs relations spatiales entre les deux phénomènes.

2.2.1. Etude d’un phénomène par un phénomène avec une seule relation spatiale

Dans ce cas, la structure de l’étude est représentée dans la figure 17 où SR est la relation

spatiale dans l’index de jointure spatial :


51

Figure 17: Etude d’un phénomène par un autre phénomène avec une seule relation spatiale

La modification de l’algorithme S-C4.5 réside dans le calcul du gain informationnel.

L’algorithme S-C4.5 a été implémenté selon deux méthodes : Jointure à la volée et la

matérialisation des jointures.

La jointure à la volée consiste à faire une jointure entre la table cible et voisine en passant par

l’index de jointure spatial lorsque cela est nécessaire, c’est-à-dire, lorsque l’attribut pour

lequel on veut calculer le gain informationnel se trouve hors de la table cible.

Par contre, la matérialisation des jointures consiste à calculer au préalable la jointure des

tables impliquées : table cible, table voisine, table index de jointures spatiales, et à considérer

le résultat comme une seule table, et appliquer ensuite l’algorithme classique de fouille de

données sur cette table.

2.2.2. Etude d’un phénomène par un phénomène en incluant plusieurs relations

spatiales.

Contrairement à la première étude, cette fois-ci, l’index de jointure spatial, contient plus d’une

relation spatiale. Ceci permet de prendre en considération plusieurs relations spatiales entres

les objets lors d’une étude, ce qui permet d’enrichir les résultats obtenus. Le schéma de la

figure 18 illustre la structure générale de cette étude, ou les SRi représentent différentes

relations spatiales entre la table cible et la table voisine

Figure 18: Etude d’un phénomène par un autre phénomène en incluant plusieurs relations spatiales.

Cette étude, a également été appliquée avec les deux méthodes utilisées lors de la première

étude, à savoir méthode de jointure à la volée et la matérialisation des jointures. Cela, sans

aucune modification nécessaire des algorithmes de la première étude suite au changement de

la structure de l’index de jointure spatial.

Index de jointure

spatiale

ID_T SR ID_N

T01 T01SRN01 N01 T01 T01SRN02 N02 T02 T02SRN01 N01 T02 T02SRN02 N02

Table voisine N ID_N Att_N1 … Att_Nn N01 A’ … A’’ N02 B’ … B’’

Table cible T

ID_T Att_cible Att_T1 … Att_TN T01 X X’ … X’’

T02 Y Y’ … Y’’

Table voisine N ID_N Att_N1 … Att_Nn N01 A’ … A’’ N02 B’ … B’’

Table cible T


T02 Y Y’ … Y’’

Index de jointure spatiale

ID_T SR1 SR2 ID_N

T01 T01SR1N01 T01SR2N01 N01 T01 T01SR1N02 T01SR2N02 N02 T02 T02SR1N01 T02SR2N01 N01 T02 T02SR1N02 T02SR2N02 N02


52

2.3. Etude d’un phénomène par plusieurs autres phénomènes

Le fait d’effectuer une étude d’un phénomène par un seul phénomène dans la fouille de

données spatiale, constitue une limitation due à la considération d’un seul phénomène

explicatif, et cela malgré la considération de plusieurs relations spatiales. Or, dans la réalité,

un certain phénomène peut être expliqué par plusieurs autres phénomènes d’où la nécessité de

pouvoir réaliser une étude d’un phénomène par plusieurs autres phénomènes. La figure 19

illustre la structure générale de cette étude qui nécessite une table cible, des tables voisines, et

des indexes de jointure spatiale. Chaque index de jointure spatial relie la table cible avec une

table voisine dont les SRi sont les relations spatiales nécessaires entre les deux tables :

Figure 19: Etude d’un phénomène par plusieurs autres phénomènes

Suivant cette structure de l’étude d’un phénomène par plusieurs autres phénomènes, nous

avons adapté l’algorithme S-C4.5 selon quatre méthodes : Jointure à la volée, matérialisation

des jointures, semi-matérialisation des jointures et matérialisation imbriquée.

2.3.1. Jointure à la volée

Cette méthode consiste à effectuer la jointure lorsque l’attribut pour lequel on souhaite

calculer le gain se trouve hors de la table cible en passant par l’index de jointure spatiale.

Index de jointure spatiale TIJSN1

ID_T SR1 SR2 … SRn ID_

N T01 T01SR1N101 T01SR2N101 … T01SRnN101 N101 T01 T01SR1N102 T01SR2N102 … T01SRnN102 N102 T02 T02SR1N101 T02SR2N101 … T02SRnN101 N101 T02 T02SR1N102 T02SR2N102 … T02SRnN102 N102

Table voisine N1 ID_N Att_N11 … Att_N1n N101 A’ … A’’ N102 B’ … B’’

Table cible T


T02 Y Y’ … Y’’

Index de jointure spatiale TIJSN1


N T01 T01SR1N201 T01SR2N201 … T01SRnN201 N201 T01 T01SR1N202 T01SR2N202 … T01SRnN202 N202 T02 T02SR1N201 T02SR2N201 … T02SRnN201 N201 T02 T02SR1N202 T02SR2N202 … T02SRnN202 N202

Table voisine N2 ID_N Att_N21 … Att_N2n N201 C’ … C’’ N202 D’ … D’’

Index de jointure spatiale TIJSNz


N T01 T01SR1Nz01 T01SR2Nz01 … T01SRnNz01 N101 T01 T01SR1Nz02 T01SR2Nz02 … T01SRnNz02 N102 T02 T02SR1Nz01 T02SR2Nz01 … T02SRnNz01 N101 T02 T02SR1Nz02 T02SR2Nz02 … T02SRnNz02 N102

Table voisine Nz ID_N Att_Nz1 … Att_Nzn N201 E’ … E’’ N202 F’ … F’’


53

Suivant la structure décrite dans la figure 19, on obtient des paires d’attributs sous la forme

suivante : [Attribut cible, Attribut X] ou attribut X est l’attribut pour lequel on veut calculer le

gain, et qui se trouve hors de la table cible.

2.3.2. Matérialisation des jointures

Pour ce qui est de la méthode de matérialisation des jointures, qui a pour avantage de ramener

la fouille de données spatiales vers une fouille de données classique, cela, en réalisant une

matérialisation de la jointure de toutes les tables en une seule table.

L’implémentation de l’algorithme S-C4.5 avec la méthode de matérialisation des jointures

génère une table matérialisée qui lors de l’exécution de l’algorithme s’avère irréalisable. Cela,

est surtout causé par une incohérence lors de l’analyse de données, encore plus lorsque les

relations spatiales chevauchent entres elles. Le tableau 3 illustre la difficulté rencontrée.

Tableau 3: Première structure de la matérialisation des jointures multithématiques

Table cible Index de jointure spatial Voisin 1 … Voisin n

Att

Cible

Att

C1 …

Att

Cn R1 R2 … Rn

Att 1

V1 …

Att n

V1 …

Att 1

Vn …

Att n

Vn

X X’ … X’’ xR1a NULL … xRNa A … A’ … NULL NULL NULL

X X’ … X’’ xR1b NULL … xRNb B … B’ … NULL NULL NULL

Y Y’ … Y’’ yR1a NULL … yRNa A … A’ … NULL NULL NULL

Y Y’ … Y’’ yR1b NULL … yRNb B … B’ … NULL NULL NULL

X X’ … X’’ NULL xR2c … xRNc NULL NULL NULL … C … C’

X X’ … X’’ NULL xR2d … xRNd NULL NULL NULL … D … D’

X X’ … X’’ NULL xR2e … xRNe NULL NULL NULL … E … E’

Y Y’ … Y’’ NULL yR2c … yRNc NULL NULL NULL … C … C’

Y Y’ … Y’’ NULL yR2d … yRNd NULL NULL NULL … D … D’

Y Y’ … Y’’ NULL yR2e … yRNe NULL NULL NULL … E … E’

La principale difficulté dans la structure exposée dans le tableau 3 intervient lorsqu’on

considère la même relation spatiale avec plusieurs voisins, lors du calcul du gain

informationnel d’une relation donnée, on ne sait pas si ce gain est apporté pour un certain ou

plusieurs phénomènes en même temps, ce qui est incohérent et fausse donc les résultats. La

seule possibilité, est de considérer des relations distinctes pour chaque voisin, par exemple si

on considère la relation de distance pour le premier voisin, elle ne sera plus utilisée pour les

autres, ce qui limite nettement notre analyse, et lui fait perdre tout intérêt.

Cependant, il existe une alternative afin de contourner cette difficulté exposée dans le tableau

4, mais qui impose de reprendre une même relation spatiale en précisant avec quel voisin elle

a été calculée. Cela génère une table immense, surtout quand on travaille sur des bases de

données spatiales.


54

Tableau 4: Seconde structure de la matérialisation des jointures

Table cible Voisin 1 … Voisin n

Att

Cible

Att

C1 …

Att

C2

Relations Voisin 1 Attributs Voisin 1 Relations Voisin n Attributs Voisin n

R1V1 … RnV1 Att 1

V1 …

Att n

V1 … R2Vn … RnVn

Att 1

Vn …

Att n

Vn

X X’ … X’’ xR1a … xRNa A … A’ … NULL … NULL NULL … NULL

X X’ … X’’ xR1b … xRNb B … B’ … NULL … NULL NULL … NULL

Y Y’ … Y’’ yR1a … yRNa A … A’ … NULL … NULL NULL … NULL

Y Y’ … Y’’ yR1b … yRNb B … B’ … NULL … NULL NULL … NULL

X X’ … X’’ NULL … NULL NULL … NULL … xR2c … xRNc C … C’

X X’ … X’’ NULL … NULL NULL … NULL … xR2d … xRNd D … D’

X X’ … X’’ NULL … NULL NULL … NULL … xR2e … xRNe E … E’

Y Y’ … Y’’ NULL … NULL NULL … NULL … yR2c … yRNc C … C’

Y Y’ … Y’’ NULL … NULL NULL … NULL … yR2d … yRNd D … D’

Y Y’ … Y’’ NULL … NULL NULL … NULL … yR2e … yRNe E … E’

Les contraintes d’implémentation liées à la matérialisation des jointures, surtout celles de la

gestion de la duplication des données, nous ont poussé à proposer une approche alternative,

qui est une méthode hybride, qui se situe entre la matérialisation des jointures et la jointure à

la volée qu’on a appelé la semi-matérialisation.

2.3.3. Semi-Matérialisation des jointures

Cette méthode consiste à joindre séparément la table cible avec chaque table voisine via son

index de jointure spatial. Ensuite, on détermine le meilleur attribut pour chaque couple (table

cible – index – voisin) qui sera l’élément de division afin de générer notre arbre de décision.

On précise que dans cette méthode, le calcul du gain pour les relations spatiales incluses est

directement identifié par rapport au voisin adéquat, contrairement au problème lié à la

méthode de matérialisation des jointures. Cela, nous permet d’avoir des relations spatiales

distinctes et communes en même temps pour toutes les tables voisines. La figure 20 illustre la

méthode semi-matérialisation des jointures.

Figure 20: La structure de la méthode semi-matérialisation


55

2.3.4. Matérialisation imbriquée

Malgré l’implémentation de la méthode de la semi-matérialisation, on était toujours contraint

par l’équilibre entre espace mémoire et temps de calcul. Afin de se libérer de ces contraintes,

on a proposé de passer aux données imbriquées qui peuvent nous dispenser de plusieurs autres

problématiques, telle que la duplication des données. Cette méthode a le même principe que la

matérialisation des jointures, et donc, de ramener toutes les tables vers une seule table. Sauf

que cette fois, nous avons proposé une autre approche qui recourt aux bases données orientées

objet qu’on a appelé la matérialisation imbriquée. Elle nous permet d’éviter la duplication des

données grâce à l’inclusion des attributs de type "table" (qu’on doit préalablement définir)

dans la structure de la table principale (matérialisée).

On a proposé une structure illustrée dans le tableau 5, qui répond à tous ces critères (sans

duplication et sans perte d’informations).

Tableau 5: Approches matérialisation imbriquée

Table cible T Table Voisine N1 ... Table Voisine Nz

Att_ Cible Att_

T1 ...

Att_

Tn

Relations

spatiales Attributs ... Relations spatiales Attributs

SR1N1 ... SRnN1 N11Att ... N1nAtt ... SR2Nz ... SRnNz Nz1

Att ... Nzn

Att

X X' ... X" XSR1A ... XSRnA A' ... A" ... XSR2C ... XSRnC C' ... C"

XSR1B ... XSRnB B' ... B" ... XSR2D ... XSRnD D' ... D"

Y Y' ... Y" YSR1A ... YSRnA A' ... A" ... YSR2C ... YSRnC C' ... C"

YSR1B ... YSRnB B' ... B" ... YSR2D ... YSRnD D' ... D"

Notre approche exige deux étapes nécessaires :

- Création d’un type table pour les tables imbriquées.

- Création de la table principale (matérialisée), contenant les tables imbriquées.

Une colonne de la table matérialisée représente un ensemble des tables imbriquées, et une

ligne peut représenter un ensemble de lignes dans la table imbriquée adéquate. De ce fait, la

taille de la table matérialisée est considérablement réduite, et cela sans aucune perte

d’informations.

2.4. Algorithme S-C4.5

On applique l’algorithme S-C4.5 sur la table résultante dans le cas de la jointure à la volée et

la semi-matérialisation des jointures après avoir effectué les jointures nécessaires,

L’algorithme 3, décrit la récursivité de la fonction principale de l’algorithme S-C4.5.


56

Algorithme 1: Description de la fonction principale de l’Algorithme S-C4.5 proposé

Entrées :

• Jeu de données spatiales comportant les tuples d’apprentissage SD ainsi que leurs étiquettes de classes générées à partir d’un ensemble de couches en utilisant les relations spatiales.

• Couche cible TL ⊂ SD incluant l’attribut cible TA ∈ TL.

• Ensemble de couches voisines (explicatives) NL ⊆ SD.

• Ensemble d’attributs voisins (explicatifs) NA, tel que ∃ NA ⊆ NL et ∃ NA ⊂ TL.

• Ensemble de relations spatiales SR précalculées en utilisant l’index de jointure spatial.

Sortie :

• Arbre de décision spatial. Méthode : 1. fonction S-C4.5(SD, TA, NA, SR) 2. pour chaque table T de SD faire 3. si NA = NULL alors → (Nœud final) 4. retourner un nœud N avec la valeur la plus représentée

de TA 5. sinon 6. si tous les exemples ont la même valeur de TA alors →

(Nœud final) 7. retourner un nœud N avec cette valeur de TA 8. sinon → (Nœud intermédiaire) 9. attributSéléctionné SA = calculMeilleurGain(NA, SR, TA) 10. attributsVoisinsRestants RNA = retirerDeLaListe(NA, SA) 11. nouveauNœud NN = nœud étiqueté avec SA 12. pour chaque valeur VSA de SA faire 13. echantillonFiltrés FS = filtrerEchantillonsAvecValeurAttributs(T, SA, VSA) 14. NN->fils(VSA) = S-C4.5(FS, TA, RNA, SR) 15. fin pour 16. retourner NN 17. fin si 18. fin si 19. fin pour 20. fin fonction

- En entrée on aura besoin :

• D’un jeu de donnée spatial SD qui contient :

• Une table cible TL qui contient un attribut cible TA

• Tables voisines NL qui contiennent des attributs voisins NA

• Un ensemble de relations spatiales SR

• Un Index de jointure spatial

- Etapes 2‒7 vérifications du critère d’arrêt : s’il n’y a plus d’attributs voisins ou si tous les

tuples d’apprentissage sont dans la même classe, alors une feuille étiquetée avec la classe

dominante est retournée.

- Etapes 8‒9 évaluations des mesures des attributs candidats et des seuils de division pour la

génération des nœuds intermédiaires. La fonction CalculMeilleurGain dans l’étape 9 renvoie

après calcul, l’attribut avec le meilleur gain informationnel et opère selon notre modification

décrite ci-dessus.


57

- Etapes 10 à 20 sont identiques à l’algorithme C4.5 classiques avec une seule différence :

l’inclusion des relations spatiales SR précalculées dans l’index de jointure spatial.

3. Conclusion

Nous avons exposé dans ce chapitre nos approches proposées pour la fouille de données

spatiales par les arbres de décision, que nous allons implémenter et tester sur des données

spatiales dans le chapitre suivant.

Chapitre IV Expérimentations et résultats

Chapitre IV : Expérimentations et résultats

59

1. Introduction

Nous allons exposer dans ce chapitre l’implémentation et l’expérimentation de l’algorithme S-

C4.5 sur un jeu de données réelles avec les différentes approches proposées qu’on a abordé au

chapitre précédent, à savoir la jointure à la volée, la matérialisation des jointures, semi-

matérialisation des jointures et la matérialisation imbriquée.

2. Implémentation

2.1. Environnement de travail

Nous avons implémenté nos approches sous un environnement Windows, avec Oracle 10g

comme système de gestion de base de données. Les tests ont été effectués sur une machine

dotée d’un processeur cadencé à 2.40Ghz et une mémoire vive de 12Go.

2.2. Jeu de données

Pour toutes nos expériences, nous avons travaillé avec une base de données de la sécurité

routière, les circonstances et les blessures des accidents de la route en Grande-Bretagne de

1979 à 2001 [40], les types (modèle inclus) des véhicules impliqués et leurs conséquences.

Les statistiques se réfèrent uniquement aux accidents de la voie publique avec blessures

corporelles, qui ont été signalés à la police puis enregistrés. Le tableau 6 présente notre jeu de

données :

Tableau 6: Description de la base de données spatiales

Nom de la table Nombre d’attributs Nombre des tuples

Accident 13 1048576

Véhicules 24 1048576

Climat 4 1048576

Route 12 1048576

Victimes 14 1048576

Zone 3 1048576

Ce jeu de données nous permet d’étudier le risque d’occurrence d’accidents liés à la

circulation selon 3 niveaux de gravité : léger, grave et mortel par la considération de

différentes couches thématiques liées, tels que l’état et conditions de la chaussée, milieu

urbain, conditions météorologiques ; en plus de ces paramètres, il nous est également possible

de tester différentes relations spatiales tels que la distance et l’inclusion. Les attributs des

différentes tables que nous avons pris en considération figurent dans le tableau 7. On tient à

préciser que chaque table de notre jeu de données contient DEUX attributs spatiaux

l’ALTITUDE et LONGITUDE :


60

Tableau 7 : Jeu de données spatiales

Type Table Table Attribut Type

Cible Accident

Accident Severity [Cible] Discret

Number of Vehicles Continue

Number of Casualties Continue

Date (DD/MM/YYYY) Continue

Day of Week Discret

Time (HH:MM) Continue

Carriageway Hazards Discret

Voisine Véhicules

Vehicle Type Discret

Age of Vehicle (manufacture) Continue

Vehicle Propulsion Code Discret

Engine Capacity Continue

Towing and Articulation Discret

Was Vehicle Left Hand Drive Discret

Vehicle Manoeuvre Discret

Vehicle Location-Restricted Lane Discret

Junction Location Discret

Skidding and Overturning Discret

1st Point of Impact Discret

Journey Purpose of Driver Discret

Sex of Driver Discret

Age of Driver Continue

Driver Home Area Type Discret

Voisine Climat Weather Conditions Discret

Winds Discret

Voisine Route

Road Type Discret

Speed limit Discret

Junction Detail Discret

Junction Control Discret

1st Road Class Discret

2nd Road Class Discret

Light Conditions Discret

Road Surface Conditions Discret

Special Conditions at Site Discret

Pedestrian Crossing-Human Control Discret

Pedestrian Crossing-Physical Facilities Discret

Voisine Victime

Casualty Class Discret

Sex of Casualty Discret

Age of Casualty Continue

Casualty Severity Discret

Pedestrian Location Discret

Pedestrian Movement Discret

Car Passenger Discret

Bus or Coach Passenger Discret

Pedestrian Road Maintenance Worker (From 2011) Discret

Casualty Type Discret

Casualty IMD Decile Discret

Casualty Home Area Type Discret

Voisine Zone Urban/Rural Discret


61

3. Expérimentations et résultats

3.1. L’étude d’un phénomène avec un seul autre phénomène

Ces approches nécessitent l’étude d’un phénomène par un seul autre phénomène en incluant

une ou plusieurs relations spatiales. Dans ce cas, nous avons définit la table Accident comme

une table cible, et la table Climat comme une table voisine.

But de l’étude

Le but de notre étude sur ce jeu de données, est de lier les types d’accidents aux conditions

météorologiques, ce qui pourrait aider à prendre des décisions afin de prévoir et pouvoir

intervenir efficacement en ayant une certaine prévision sur les types d’accidents qu’on

pourrait avoir par emplacement.

Résultats obtenus

En ce qui concerne l’étude d’un phénomène par un seul phénomène et une seule relation

spatiale, nous avons fait l’étude avec la relation spatiale Distance, et pour l’étude d’un

phénomène par plusieurs autres phénomènes en utilisant plusieurs relations spatiales, nous

avons choisi deux relations spatiales : la distance et l’inclusion.

Les comparaisons de performances concernent le temps d’exécution nécessaire, l’espace

mémoire consommé durant les traitements, et le résultat généré par l’arbre de décision

spatiale, on remarque (voir tableau 8) en termes de temps d’exécution pour les deux cas

d’études (Avec une seule ou plusieurs relations spatiales), que la première approche – Jointure

à la volée – met plus de temps comparés à la seconde approche – Matérialisation des jointures

–. Cet écart revient à la conception même de ces deux approches, vu que la première ne fait la

jointure que lorsqu’il est nécessaire (Attribut à traiter n’appartient pas à la table cible), tandis

que dans la deuxième approche, les jointures sont faites une fois pour toutes avant de

commencer les traitements.

Pour ce qui est de l’espace mémoire, là encore il existe un grand écart entre les deux

approches dans les deux cas d’études. La première consomme peu d’espace mémoire comparé

à la deuxième, ce qui est logique vu qu’elle ne fait la jointure que lorsque cela est nécessaire,

puis libère cette espace utilisée, alors que la deuxième approche, fait la matérialisation des

jointures avec laquelle elle va travailler par la suite.

De plus nous avons constaté, que l’utilisation de plus d’une relation spatiale génère un arbre

de décision plus précis. La figure 21 décrit la structure de l’étude d’un phénomène avec un

seul autre phénomène en utilisant la relation spatiale « Distance », Le tableau 8 et les figures

22 et 23 décrivent les résultats obtenus.


62

La table Accident est la table cible, elle contient l’attribut cible qui est la gravité de

l’accident

La table Météo est la table voisine.

La table IJS-Accident-Météo est la table index de jointure spatial qui contient la relation

spatiale entre la table Accident et la table Météo. Cette relation spatiale est la Distance

Tableau 8: Résultats obtenus par l’étude d’un phénomène par un seul autre phénomène en utilisant

une ou plusieurs relations spatiales

Jointure à la volée Matérialisation de jointure

Temps

d’exécution

Espace

mémoire

Temps d’exécution Espace

mémoire Total Phase 1 Phase 2

Une seule relation

spatiale

73 min

15.080 s 1057 Mo

41 min

48.480 s 18.380 s

41 min

30.100 s 4850 Mo

Avec deux relations

spatiales

96 min

26.680s

1392 Mo 54 min

21.480 s

20.460 s 54 min

01.020 s

6438 Mo

Figure 21 : Etude d'un phénomène avec un seul autre phénomène en utilisant une seule relation spatiale

(Distance)


63


seul autre phénomène en utilisant une seule relation spatiale (Distance)

La figure 22 représente l’arbre généré par l’étude du niveau de gravité des accident routiers

par un seul autre phénomène déterminé par les mauvaises conditions météos en considérant

seulement la distance comme relation spatiale. En limitant le jeu de données à 900

échantillons aléatoires, nous remarquons que la classe dominante est les accidents provoquant

des blessures graves (Serious) avec une légère dominance quand les accidents se produisent

près d’une zone à mauvaises conditions météos.


seul autre phénomène en utilisant plusieurs relations spatiales

La figure 23 représente l’arbre généré par l’étude du niveau de gravité des accidents routiers

par un seul autre phénomène déterminé par les mauvaises conditions météos en considérant la

distance et l’inclusion (dans une zone ou la vitesse des vents est estimée) comme relations

spatiales. Bien que l’arbre généré soit plus détaillé, on n’obtient toujours pas d’informations

discriminantes. La qualité de cet échantillon de données peut avoir influencer les résultats non

discriminants, c’est pourquoi nous avons gardé cet échantillon pour l’enrichir avec des

phénomènes et relations spatiales supplémentaires afin d’avoir un comparatif quant à l’apport

décisionnel par la considération d’informations supplémentaires dans l’analyse spatiale.


64

3.2. L’étude d’un phénomène avec plusieurs autres phénomènes

Dans ce cas d’étude, nous avons définit la table Accident comme une table cible, et les tables

Climat, Route et Zone comme des tables voisines.

Figure 24: Etude d'un phénome avec plusieurs autres phénomènes en utilisant deux relations spatiales

(Distance et inclusion)

But de l’étude

Avec la considération de ces tables (thèmes), on va pouvoir déterminer et prévoir le type

d’accidents qui peuvent se produire en fonction du type de la route et des conditions météos

dans une zone. Cela pourrait aider à prendre des décisions concernant la mise en place d’une

signalisation routière plus efficace par exemple, ou modifier des tronçons de route afin

d’éviter certains accidents quelques soit les conditions météorologiques. Nous avons utilisé

deux relations spatiales : la distance et l’inclusion.


65

3.3. Jointure à la volée

Bien que cette méthode simplifie l'inclusion de plusieurs phénomènes (tables), mais on

remarque une utilisation intensive des opérations de jointure lorsque l'attribut concerné par le

calcul du gain informationnel est hors de la table cible. Le tableau 9 décrit les résultats

obtenus.

Tableau 9: Résultats obtenus par la jointure à la volée

Temps d’exécution Espace mémoire

115 min 02.335 s 1 644 Mo

3.4. Matérialisation des jointures

La matérialisation des jointures réduit considérablement la durée d'exécution nécessaire par

rapport à la jointure à la volée, mais elle nécessite beaucoup plus d’espace mémoire.

Nous prenons en compte les contraintes d'implémentation liées à la matérialisation des

jointures, notamment celle de la gestion de la duplication des données, nous avons proposé

une approche alternative, qui est une méthode hybride, située entre la matérialisation des

jointures et la jointure à la volée, nommée la semi-matérialisation. Le tableau 10 décrit les

résultats obtenus.

Tableau 10: Résultats obtenus par la matérialisation des jointures


71 min 15.320 s 7 280 Mo

3.5. Semi-matérialisation des jointures

Le temps d'exécution nécessaire est moins par rapport à l’approche jointure à la volée, et cela

dû aux nombres d’opérations de jointure qui sont réduits, par contre, elle nécessite un espace

mémoire plus important par rapport à la jointure à la volée. Le tableau 11 décrit les résultats

obtenus.

Tableau 11: Résultats obtenus par la semi-matérialisation des jointures


79 min 24.289 s 3 729 Mo

3.6. Matérialisation imbriquée

L'application de l’approche matérialisation imbriquée, nous a permis d'optimiser les

performances en réduisant la taille de la table matérialisée, représentée comme un objet

contenant des tables imbriquées, sans aucune duplication (élément principal de réduction de la

taille), ce qui réduit automatiquement le temps de calcul. Par conséquent, cette méthode


66

établit un certain équilibre entre le temps d’exécution et l'espace mémoire. Le tableau 12

décrit les résultats obtenus.

Tableau 12: Résultats obtenus par la matérialisation imbriquée.


67 min 42.010 s 2 456 Mo

On tient à préciser que l’arbre généré par les approches présentés précédemment de l’étude

d’un phénomène par plusieurs autres phénomènes est le même dans toute l’étude d’un

phénomène par plusieurs autres phénomènes. Les figures 25 et 26 montrent le résultat obtenu

de cette étude.


plusieurs autres phénomènes en utilisant une seule relation spatiale (Distance)


plusieurs autres phénomènes en utilisant deux relations spatiales (Distance et Inclusion)

En limitant l’arbre généré à 3 niveaux, nous remarquons que l’élément le plus déterminant est

la distance par rapport aux mauvaises conditions météos avec une dominance des accidents

grave.

Ensuite, en étant loin d’une zone de mauvaises conditions, c’est la vitesse limitée qui est

déterminante, suivie par les conditions d’éclairage, type de la route et mauvais état de la

chaussée.

En étant proche d’une zone avec de mauvaises conditions météos, c’est le type de zone qui est

déterminant, entre zone rurale ou urbaine. En zone rurale c’est le type de route qui permet de

classer la gravité des accidents, ensuite en zone urbaine c’est la vitesse limite.

En zone avec mauvaises conditions météos, c’est encore la vitesse limite qui est déterminante,

avec des accidents mortels à des endroits où la vitesse est limitée à 40 et 60 MPH. Il s’en suit

parmi tous les paramètres inclus, les conditions lumineuses, le type de zone et type de route.


67

4. Discussions et comparaisons

Nous remarquons clairement que dans les approches de l’étude d’un phénomène par plusieurs

autres phénomènes, le besoin en ressources est nettement supérieur, que ce soit en temps

d’exécution ou en espace mémoire ; ce qui est normal, étant donné qu’on dispose de plus d’un

voisin, tout en incluant plusieurs relations spatiales.

Pour les approches de l’étude d’un phénomène par un seul phénomène, et à des fins de

comparaison avec d’autres travaux, nous avons testé l’algorithme S-C4.5 selon deux

différentes méthodes : jointure à la volée, et la matérialisation des jointures sur un jeu de

données spatiales en le comparant avec l’algorithme S-CART en utilisant une seule relation

spatiale puis plusieurs relations spatiales.

Tableau 13: Résultats obtenus par l’étude d’un phénomène par un seul autre phénomène en utilisant

une ou plusieurs relations spatiales

Une relation spatiale Deux relations spatiales

Ap

pro

che

ma

téria

lisa

tio

n d

es

join

ture

s

L’algorithme

S-C4.5

Durée Espace

mémoire

Durée Espace

mémoire

Phase 1 Phase 2

4850 Mo

Phase 1 Phase 2

6438Mo 18.380 s 41 min

30.100 s

20.460 s 54min 01.020 s

41 min 48.480 s 54 min 21.480 s

L’algorithme

S-CART

Phase 1 Phase 2

5013 Mo

Phase 1 Phase 2

6534Mo 17 min

45.954 s

56 min

32.860 s

20 min

05.496 s

71 min 44.912 s

74 min 18.814 s 91 min 50.408 s

Jo

intu

re à

la

vo

lée

L’algorithme

S-C4.5

73 min 15.080 s

1057 Mo

96 min 26.680 s

1392 Mo

S-CART

94 min 56.031 s

1282 Mo

126 min 15.660 s

1668 Mo

NB : Dans la méthode de matérialisation, ‘Phase 1’ correspond à la matérialisation des

jointures, ‘Phase 2’ correspond à l’exécution de l’algorithme.

On peut clairement remarquer dans le tableau 13 que la seconde approche –Matérialisation

des jointures- nécessite moins de temps d’exécution (avec un gain de performances d’environ

28%) par rapport à la première approche –Jointure à la volée-. Cela est dû au fait que la

jointure de toutes les tables est faite une fois pour toute avant le début des traitements ce qui a

pour effet de réduire le temps de calcul nécessaire. Cependant, ce gain de performances de la

seconde approche -Matérialisation des jointures- se fait en dépit d'un espace mémoire plus

important par rapport à la première approche -Jointure à la volée-, ce qui explique l'espace


68

mémoire nécessaire afin de contenir la jointure de toutes les tables, tandis que la première

approche consomme l'espace mémoire selon le besoin lorsque la jointure est vraiment

nécessaire.

En comparant avec l’algorithme S-CART, et pour ce qui est de -La jointure à la volée-, avec

une consommation mémoire légèrement supérieure de notre algorithme par rapport à S-

CART, on a obtenu un meilleur temps d’exécution, cela est dû aux performances supérieures

de C4.5 par rapport à l’algorithme CART qui nécessite des opérations coûteuses pour la

division binaire d’attributs. Quant à la seconde approche –Matérialisation des jointures-, on

constate qu’avec une consommation mémoire presque identique, le temps d’exécution de

notre algorithme S-C4.5 modifié est bien inférieur à celui de S-CART, cela revient également

aux performances supérieures de C4.5 par rapport à CART.

Pour ce qui est du nombre de relations spatiales incluses, on remarque dans toutes les

approches, un temps d’exécution légèrement supérieur ainsi qu’une légère consommation

mémoire supplémentaire. Au fait, cela est équivalent à l’inclusion d’un attribut

supplémentaire dans l’analyse. Les résultats confirment donc, que la prise en charge de

plusieurs relations spatiales ne va pas trop dégrader les performances, tout en enrichissant les

arbres de décisions générés.

En ce qui concerne la comparaison des résultats générés par l’arbre de décision, on remarque

clairement que le fait de ne considérer qu’une seule relation spatiale constitue une limitation

dans l’étude. Surtout lorsqu’un phénomène dépend d’un autre phénomène lié par différentes

relations spatiales (le cas de notre étude). Car ces dernières sont des informations qui

traduisent une propriété et caractéristique essentielle du monde réel, à savoir la notion de

l’influence du voisinage, elles sont souvent exploitées dans les requêtes et analyses spatiales,

il est donc nécessaire de les prendre en considération afin d’enrichir l’analyse de ces données.


seul phénomène en utilisant une seule relation spatiale (Distance)


69


seul phénomène en utilisant deux relations spatiales

Contrairement au premier arbre généré par l’algorithme S-C4.5 (Figure 22), S-CART permet

d’avoir un arbre se développant plus en profondeur. Là encore, on confirme que l’élément le

plus déterminant c’est la proximité aux mauvaises conditions météos, ensuite le type de zone

(urbaine ou rurale), puis s’en suit la vitesse limite et type de route. On remarque qu’à partir de

40 MPH les accidents sont de plus en plus mortels, surtout en zone urbaine.

En ce qui concerne les approches de l’étude d’un phénomène par plusieurs autres

phénomènes, et pour le but de comparaison, nous avons utilisé le même ensemble de données

tout au long de nos travaux dans le même environnement de travail. Selon la méthode

appliquée, nous avons obtenu des différents résultats ; chacune des approches a ses propres

avantages et inconvénients par rapport aux autres méthodes, le tableau 14 résume les résultats

obtenus des 4 approches multithématiques.

La première méthode appliquée consiste à utiliser l'opération de jointure lorsque cela est

nécessaire, en réduisant le besoin d'espace mémoire au détriment d'un temps de calcul plus

élevé, en raison du nombre important d'opérations de jointure.

Contrairement à la première méthode, la seconde méthode qui est la matérialisation des

jointures nécessite moins de temps d’exécution, mais elle consomme plus d'espace mémoire

en matérialisant toutes les tables en une seule table une fois pour toutes.

Afin de pallier les limites de ces deux approches, nous avons opté pour une nouvelle

approche qui combine entre les deux approches précédentes, à savoir jointure à la volée et la

matérialisation des jointures, nommée semi-matérialisation des jointures, son principe est de

réduire le nombre d'opération des jointures, ce qui donne un meilleur temps de calcul par

rapport à la première méthode (jointure à la volée).

La dernière méthode est la matérialisation imbriquée, permet un certain équilibre entre le

temps de calcul et l'espace mémoire requis, combinant les avantages des méthodes

précédentes et cela est permis par les bases de données orientées objet.


70

Tableau 14: Résultats obtenus par les approches multithématique.

Approches Proposées Temps d’exécution Espace mémoire

Approche 1 : Jointure à la volée 115 min 02.335s 1 644 MB

Approche 2 : Matérialisation des jointure 71 min 15.320 s 7 280 MB

Approche 3 : Semi-matérialisation des jointures 71 min 15.320 s 3 729 MB

Approche 4 : Matérialisation imbriquée 67 min 42.010 s 2 456 MB

Les approches de l’étude d’un phénomène par plusieurs autres phénomènes génèrent un arbre

de décision plus précis par rapport aux approches multithématiques avec un seul voisin, et

cela revient aux nombres de phénomènes et relations spatiales utilisés.

5. Conclusion

Dans ce dernier chapitre, nous avons présenté les expérimentations et les résultats de nos

approches de l’étude d’un phénomène par un seul phénomène ou plusieurs autres phénomènes

en incluant une seule relation spatiale ou plusieurs sur un jeu de données réelles.

Les résultats montrent que les approches proposées de l’étude d’un phénomène par plusieurs

autres phénomènes génèrent des arbres de décision plus précis par rapport aux approches

proposées de l’étude d’un phénomène par un seul autre phénomène en utilisant une seule

relation spatiale ou plusieurs.

L’approche matérialisation des jointures donne de meilleurs résultats en termes de temps

d’exécution par rapport à la jointure à la volée, et cette dernière consomme moins d’espace

mémoire dans l’étude d’un phénomène par un seul autre phénomène en utilisant une ou

plusieurs relations spatiales.

La matérialisation imbriquée est meilleure en termes de temps d’exécution dans le cas de

l’étude d’un phénomène par plusieurs autres phénomènes en utilisant plusieurs relations

spatiales.

Conclusion et perspectives

Conclusion Générale


72

Conclusion générale

La fouille de données spatiales doit en prendre en considération les relations de voisinage

entre les données et l’organisation en couches thématiques des données.

Dans ce contexte nous avons proposé des approches basées sur les arbres de décision. Ces

derniers génèrent un modèle de prédiction plus lisible, et permet de sélectionner

automatiquement les variables discriminantes dans un fichier de données contenant un très

grand nombre de variables potentiellement intéressantes. En ce sens, un arbre de décision

constitue une technique exploratoire privilégiée pour appréhender de gros fichiers de données

par rapport à l’utilisation des règles d’association ou la logique inductive proposée dans

certains travaux.

Plusieurs travaux proposent des approches basées sur les arbres de décision en utilisant les

algorithmes CART ou ID3. Le premier algorithme ne permet pas de générer un arbre n-aire

tandis que le second ne traite pas les données continues.

Nous avons proposé d’utiliser C4.5 et l’étendre aux données spatiales (S-C4.5). Cet

algorithme permet de lever les limites des algorithmes CART et ID3 et de traiter les données

spatiales dans toute leur complexité.

L'adaptation de l'algorithme de classification C4.5 aux données spatiales s’est faite selon

deux modifications, la première au niveau de l'organisation des données par l'utilisation de

l’index de jointure spatial (IJS) et la seconde au niveau de l'algorithme. Nous avons appliqué

notre algorithme S-C4.5 à l'ensemble des données spatiales de la sécurité routière organisé en

couches multithématiques et mené des mesures de performance à travers différentes

approches divisées en deux cas d'étude.

Le premier cas est l'étude d'un phénomène par un seul autre phénomène, comprenant une ou

plusieurs relations spatiales. Le deuxième cas est l’étude d'un phénomène par plusieurs autres

phénomènes, y compris de multiples relations spatiales. Dans le premier cas, nous avons

utilisé deux méthodes, la jointure à la volée et la matérialisation des jointures. La première

méthode qui est la jointure à la volée consomme moins d’espace mémoire par rapport à la

seconde méthode par contre la matérialisation de jointure consomme moins de temps

d’exécution.

Nous avons comparé nos résultats à ceux obtenus par les approches basées sur S-CART et

avons confirmé que nos approches améliorent le temps d’exécution et la consommation de

l’espace mémoire.

Pour le second cas, qui est l’étude d’un phénomène par plusieurs autres phénomènes en

utilisant plusieurs relations spatiales nous avons eu un impact négatif sur les performances en

termes de temps d’exécution avec la jointure à la volée, cela nous amène à expérimenter la

deuxième méthode qui la matérialisation des jointures, qui présentait des problèmes de

duplication des données. Pour pallier à ces deux problèmes, nous avons proposé une nouvelle


73

méthode, que nous avons nommée semi-matérialisation des jointures, cette méthode se situe

entre les deux méthodes précédentes en termes de temps d’exécution et d'espace mémoire.

Enfin, nous avons utilisé des bases de données orientées objet, afin de réaliser un certain

équilibre entre le temps d’exécution et l'espace mémoire requis, en évitant en même temps les

inconvénients des méthodes précédentes, notamment la duplication des données.

Les résultats montrent que la matérialisation imbriquée est meilleure en termes de temps

d’exécution et d’espace mémoire consommé

Les données spatiales représentent un énorme volume de données complexes qui influence

négativement sur les algorithmes d'apprentissage automatique, ce qui rend l'analyse de ces

données complexe sur une seule machine en raison de la mémoire limitée et des ressources

CPU. Pour ces raisons, il serait intéressant d'amener nos travaux vers des architectures de

calcul parallèles et / ou distribuées, où la méthode de jointure à la volée, par exemple,

pourrait présenter de meilleurs résultats.

Il serait également intéressant d'expérimenter et de comparer nos travaux avec des

technologies récentes bien connues du Big Data, des Data Warehouses et des Data Lakes,

avec différents systèmes de gestion de bases de données. Les travaux futurs ne se limiteront

pas uniquement aux problèmes de performances, ils traiteront également d'autres aspects

importants de la classification tels que l'amélioration de la précision.

Annexes

Annexe I: Les arbres de décision

75

Annexe I : Les arbres de décision

1. Définition

Un arbre de décision est un arbre au sens informatique du terme, il permet de représenter

graphiquement une procédure de classification. CART ID3 et C4.5 sont des algorithmes

d’apprentissage par arbre de décision.

L’idée principale est de diviser récursivement les exemples de l’échantillon d’apprentissage

selon un indice de segmentation jusqu'à obtenir des classes homogènes.

Les arbres de décisions sont souvent sujets à un sur-apprentissage, c'est-à-dire que l’arbre

généré est très profond. Dans ce cas nous procédons à un élagage de l’arbre qui consiste à

remplacer un sous arbre par une feuille selon un critère qui diffère d’un algorithme à un autre.

[16]

➢ Notation

Soient un échantillon d’apprentissage noté , un ensemble de classes notées et un

arbre de décision . A chaque position de correspond un sous-ensemble de qui satisfait

les tests de la racine jusqu’à cette position. Pour toute position de nous définissons les

quantités suivantes :

cardinal de l’ensemble des exemples associés à .

cardinal de l’ensemble des exemples associés à qui sont de classe .

la proportion d'éléments de classe à la position .

➢ Algorithme général d’apprentissage

Entrée échantillon de enregistrements classés

Début

Initialiser arbre à vide, nœud courant= racine et échantillon courant=

Répéter

Décider si le nœud courant est terminal

Si le nœud est terminal Alors lui affecter une classe

Sinon sélectionner un test et créer le sous arbre

FinSi

Nœud courant= nœud non encore exploré

échantillon courant= échantillon atteignant le nœud courant

Jusqu'à obtenir un arbre de décision

Fin [10]

Elagage de l’arbre obtenu

Sortie

Arbre de décision élagué


76

2. Les algorithmes des arbres de décisions

2.1. Algorithme CART

L’algorithme CART (Classification And Regression Tree) permet de construire un arbre de

décision à partir d’un échantillon de données. Le modèle de classification crée est un arbre

binaire et l’indice de segmentation utilisé est l’indice de Gini. [16][47].

Nous allons définir les différentes étapes de l’algorithme général selon CART puis nous

verrons l’étape d’élagage. Nous définissons pour cela un ensemble de tests binaires

prédéfinis, un échantillon d’exemples composé de un ensemble d’apprentissage et un

ensemble test.

➢ Phase de construction

L’algorithme prend en entrée l’ensemble . La fonction utilisée pour mesurer le degré

d’impureté des données est l’indice de Gini définit comme suit :

• Décider si un nœud est terminal. Un nœud courant est terminal si ou

, où et sont des paramètres a définir.

• Sélectionner un test à associer à un nœud. Soit la position du nœud courant et un

test. On choisit le test qui maximise la valeur tel que :

On étiquette le nœud par ce test et l’échantillon courant associé à est divisé en

et . (respectivement ) est la proportion de l’ensemble

d’exemples associé à qui vont au fils gauche de (respectivement. fils droit ).

• Affecter une classe à une feuille. On étiquette la feuille par la classe majoritaire.

[10][47]

➢ Phase d’élagage

Dans cette phase nous utilisons l’ensemble d’apprentissage , l’arbre produit et l’ensemble

test .

• Construction de la suite des arbres. On construit une suite , telle que est

l’arbre obtenu à la fin de la première phase. Pour tout , est un élagué de et le

dernier arbre de la suite est réduit à une feuille. L’élagage de se fait en calculant


77

l’erreur apparente si on remplace le sous arbre de à la position par une feuille.

L’erreur apparente est calculée de la manière suivante :

est la variation d'erreur apparente mesurée sur l'ensemble d'apprentissage

lorsqu'on élague en position et est la taille de . est le cardinal de

l'ensemble des exemples de associé à la position de , est le nombre

d'éléments de mal classés à la position lorsqu'on élague en position et

est le nombre d'éléments de associés à la position de mal classés par .

On choisit la position pour laquelle est minimale et est l'élagué de en

position .

• Choix final. On calcul pour chaque arbre de la suite précédente l’erreur apparente sur

l’ensemble test et on retourne l’arbre qui minimise l’erreur apparente sur .

Lorsqu’on ne dispose pas d’échantillon test, CART permet de faire l’élagage par validation

croisée. [10]

2.2. Algorithme ID3

L’algorithme ID3 est un algorithme de classification qui permet de construire un arbre n-aire

contrairement à l’algorithme CART et qui traite que les données discrètes.

➢ Construction de l’arbre

L’algorithme commence par le placement de tous les exemples d’apprentissage dans le nœud

racine. Ensuite, chaque nœud est coupé sur un des attributs restants (qui n’a pas encore été

testé). Le choix de cet attribut se fait à travers une mesure d’homogénéité par rapport à la

variable cible. Cette mesure est le gain d’information obtenu par le découpage.

On suppose que la variable cible a m valeurs distinctes (les étiquettes de classe). Pour un

nœud s (interne ou feuille) on calcule son entropie par rapport à la cible comme suit :

• Partitionner S sur les valeurs de la cible en m groupes : C1,...,Cm.

• Calculer pi,i=1...m, la probabilité qu’un élément de S se retrouve

dans Ci (pi≈|Ci|/|S| ou |Ci| est la taille du groupe Ci).

• . est l’entropie de S. H(S) mesure l’écart de la distribution

de la variable cible par rapport à la distribution uniforme :

• H(S)=0 si S est homogène (tous les éléments sont dans la même classe : toutes les

probabilités pi sont égales à 0, sauf une - qui est égale à 1).


78

• H(S)=max si toutes les probabilités pi sont égales (tous les groupes Ci ont la même

taille : p1=⋯=pn=1/m).

Pour calculer le gain d’information dans un nœud interne S sur l’attribut aa :

• Partitionner S sur les valeurs de l’attribut a en k sous-groupes : S1,...,Sk (k est le

nombre de valeurs distinctes de l’attribut a),

• pi : la probabilité qu’un élément de S appartient à Si (pi≈|Si|/|S|,

• Calculer le gain d’information sur l’attribut a.

Avec ces précisions, l’algorithme ID3 commence par la racine. Ensuite pour le nœud S en

train d’être testé :

• Calculer le gain d’information pour chaque attribut pas encore utilisé,

• Choisir l’attribut a de gain d’information maximal,

• Créer un test (décision) sur cet attribut dans le nœud S et générer les sous-

nœuds S1,...Sk correspondant à la partition sur l’attribut choisi a,

• Récurrence sur les nœuds qui viennent d’être crées.

Sortie de la récursivité :

• Tous les éléments de SS sont dans la même classe (H(S)=0: S devient nœud feuille,

• Pas d’attributs non utilisés : nœud feuille sur la classe majoritaire,

• S=∅: nœud feuille sur la classe majoritaire du parent (ce cas est nécessaire pour le

classement de nouveaux échantillons) [16].

2.3. Algorithme C4.5

L’algorithme C4.5 est une amélioration de l’algorithme ID3 qui permet de travailler à la fois

avec des données discrètes et des données continues. Il permet également de travailler avec

des valeurs d’attributs manquantes.

➢ Phase de construction

L’algorithme prend en entrée l’ensemble d’apprentissage . Le critère de segmentation est la

fonction entropie définie comme suit :

• Décider si un nœud est terminal. Un nœud est terminal si tous les exemples associés à

ce nœud appartiennent à la même classe ou s’il n’existe pas de test ayant au moins deux

éléments sur deux branches.

• Sélectionner un test à associer à un nœud. Soit la position et le test d’arité , on

choisit le test qui maximise le gain en utilisant la fonction qui mesure le degré

de mélange. La fonction privilégie les tests qui répartissent les exemples en un

grand ensemble de sous-classes, elle est donc pondérée par une fonction qui

mesure la répartition :


79

est la proportion d'éléments associés à la position qui satisfont la branche du

test.

est la proportion des éléments présents à la position p prenant la jème valeur de

test.

La nouvelle fonction est appelée . On choit le test qui maximise le

:

• Affecter une classe à une feuille. On étiquette la feuille par la classe majoritaire, s’il n’y

a aucun exemple on lui attribue la classe majoritaire du père. [16]

➢ Phase d’élagage

C4.5 utilise l’ensemble d’apprentissage pour la phase de l’élagage. L’élagage est basé sur une

heuristique qui permet de calculer l’erreur réelle sur un sous arbre donné. L’heuristique

proposée par C4.5 est définie par :

• On construit le système à base de règles associé à l’arbre de décision produit à la phase

précédente.

• On choisit une méthode permettant de coder les règles et les exemples mal classés par les

règles.

• Lorsqu’on supprime une règle on risque de voir le nombre d’exemples mal classés

augmenter et la taille du codage diminuer.

• On choisit la règle qui produit la plus grande diminution et on procède itérativement tant

que la taille des codages diminue [16].

Annexe II: Les règles d’association

80

Annexe II : Les règles d’associations

1. Définition

La recherche de règles d’association est une tâche très étudiée du domaine de l’extraction de

connaissances à partir de données. Les règles d’association est une technique d’apprentissage

non supervisée, elles sont devenues populaire avec Agrawal et ses travaux sur l’extraction de

règles d’association à partir de bases de données commerciales.

Dans une telle base, chaque enregistrement est une transaction composée d’attributs qui

correspondent aux articles susceptibles de figurer dans la transaction. Un article est appelé

item et un ensemble d’article un itemset. Une règle d’association a la forme dont

l’interprétation est « un client qui achète l’article est susceptible d’acheter l’article . et

sont des itemsets n’ayant pas d’items en commun, est l’antécédent de la règle et son

conséquent.

L’extraction des règles d’association est caractérisée par le problème suivant : le nombre de

règles croît de façon exponentielle avec le nombre d’items. C’est pour cela que l’extraction

est fondée sur la définition des règles intéressantes, leur identification et leur validation.

[19][32][42]

➢ Notation

Soit l’ensemble des items pouvant faire partie d’une base de données

transactionnelle et une transaction, est donc un sous-ensemble de : .

Une règle d’association est de la forme où , et . [53]

➢ Fréquence, support, confiance et lift

Les algorithmes d’extraction basés sur le support et la confiance recherchent les règles

d’association dont le support et la confiance dépassent des seuils prédéfinis notés

respectivement . [53][32]

Soit le nombre de transactions de la base de données . La fréquence de la règle

est le nombre de transactions dans qui contiennent et notée .

Le support d’une règle est la proportion de transactions où et apparaissent à la fois :

La confiance d’une règle est le nombre de transaction réalisant , parmi celles réalisant

(sachant ) :


81

Le lift d’une règle mesure son intérêt, si le lift est inférieur à 1 alors la règle n’est pas utile :

2. Les Algorithmes des règles d’association

2.1. Algorithme APRIORI

Les algorithmes basés sur le support et la confiance comme l’algorithme Apriori parcourent

le treillis des itemsets (ensemble des parties des itemsets où la borne supérieure est l'union et

la borne inférieure l'intersection) à la recherche des itemsets fréquents, à partir de ceux-là, les

règles d’association sont extraites et ne sont retenues que celles dont la confiance dépasse

. [32]

Itemsets fréquents

Un itemset est dit fréquent si son support dépasse , la construction des itemsets est

rendu facile grâce à deux de leurs propriétés :

• Propriété 1. Tout sous-ensemble d’un itemset fréquent est fréquent.

Exemple. Si l’itemset est fréquent alors et sont aussi fréquents.

• Propriété 2. Tout sur-ensemble d’un itemset non fréquent est non fréquent.

Exemple. Si l’itemset est non fréquent alors l’itemset est non fréquent.

[53][42]

Construction des itemsets

Grâce à leurs propriétés, les itemsets peuvent être construits incrémentalement :

1. Générer les itemsets de taille .

2. Un itemset de taille est généré à partir des itemsets de taille par jointure de ceux-

ci avec eux même (la jointure se fait par union des items ayant un seul élément différent),

en ne gardant que ceux dont la fréquence dépasse .

Etapes de l’algorithme

L’algorithme Apriori énoncé par Agrawal et Srikant en 1994 est considéré comme

l’algorithme fondateur de la recherche de règles d’association, il procède de la manière

suivante :

• Fixer la valeur de .

• Pour allant de à faire

1. Générer les itemsets de taille à partir des itemstes fréquents de taille .

2. Garder ceux dont le support dépasse .


82

• Pour chaque itemset fréquent , on garde les seules règles du type , avec

, dont la confiance dépasse .

L’efficacité de l’algorithme diminue en présence de données denses ou fortement corrélée.

Toute la difficulté réside dans l’identification de la barrière entre itemsets fréquents et

itemsets non fréquents [53][32].

2.2. Algorithme CLOSE

L’algorithme CLOSE est un algorithme pour la découverte des règles associatives. Il est basé

sur l’élagage de l’espace de recherche des itemsets fermés. Ainsi étant donné un contexte

d’extraction K, CLOSE génère toutes les règles associatives en trois étapes successives :

1) découvrir des itemsets fermés fréquents ;

2) dériver tous les itemsets fréquents à partir de ceux fermés obtenus durant la première

étape ;

3) pour chaque itemset fréquent i, générer toutes les règles dérivables et ayant une

confiance au moins égale à minconf.

Notations et paramètres utilisés dans CLOSE

• FFCk Ensemble des k-itemsets fréquents candidats.

• FCk Ensemble des k-itemset fermés fréquents.

• Chaque élément de ces ensembles possède trois champs :

i) gen : le générateur ; ii) supp : le support iii) ferm : la fermeture.

Algorithme 2 : Algorithme CLOSE

Dans l’algorithme CLOSE Les items sont triés dans un ordre lexicographique. A chaque

itération, l’algorithme construit un ensemble d’itemsets fermés candidats (FFC). Cet

ensemble est élagué par rapport à minsup, obtenant ainsi un ensemble d’itemsets fermés


83

fréquents. Finalement, en utilisant cet ensemble, il construit l’ensemble des générateurs qui

seront utilisés dans la prochaine itération [41].

L’algorithme s’arrête quand la liste des générateurs est vide. Ainsi, chaque itération est

composée de deux étapes :

1) Étape d’élagage : durant cette étape, la fonction GEN-FERMETURE est appliquée à

chaque générateur de FFCk, déterminant ainsi son support et sa fermeture. Notons ici une

particularité de l’algorithme CLOSE qui élague par rapport à minsup après avoir calculé les

fermetures des générateurs dont certains peuvent être non fréquents.

2) Étape de construction : dans cette étape, on commence par éliminer les générateurs non

fréquents. Ensuite, la fonction GEN-GENERATEUR prend comme l’ensemble des itemsets

fermés fréquents FCk et calcule l’ensemble FFCk+1 contenant tous les (k + 1)-itemsets, qui

seront utilisés dans l’itération suivante. A ce niveau, comme l’algorithme CLOSE dispose de

l’ensemble des itemsets fermés fréquents obtenus au niveau k, alors l’ensemble FFCk+1 est

élagué comme suit.

Pour tout c ∈ FFCk+1, si c’est inclus dans la fermeture d’un des sous-ensembles, les

éléments de FCk dont la jointure a permis d’obtenir c. Dans ce cas, c’est éliminé FFCk+1.

L’algorithme s’arrête quand il n’y a plus de générateurs à traiter, i.e. FFCk est vide [44].

Annexe III: La programmation logique inductive

84

Annexe III : Programmation logique inductive

1. Définition

Les algorithmes de la fouille de données classiques proviennent de l’apprentissage machine,

en effet, ce sont des algorithmes d’apprentissage supervisés et non supervisés élaborés de

telle sorte à apprendre les tendances de l’échantillon de données à analyser à des fins de

classification, de prédiction, d’estimation…etc. La fouille de données multi-relationnelles

s’inspire de la programmation logique inductive pour ses techniques, c’est à dire, les règles

produites sont exprimées en logique relationnelle car celle-ci permet de formuler les relations

entre les données de la base.

2. Formalisme de la PLI

Située entre l’apprentissage automatique et la programmation logique, la programmation

logique inductive (PLI) est la synthèse de nouvelles connaissances à partir d’observations et

d’une base de connaissances. La PLI partage la même tâche que la fouille de données

classiques, à savoir déduire des hypothèses à partir d’un ensemble de données. Cependant,

contrairement à la fouille de données qui suppose les données organisées dans des tables de

format , la PLI suppose que les données en entrée ainsi que les modèles

extraits sont exprimés en logique du premier ordre (logique des prédicats). Le formalisme de

la PLI se présente ainsi :

Entrée Trois ensembles de clauses : , et avec

• : base de connaissances exprimées sous forme de clause de Horn.

• : exemples positifs exprimés sous forme de clauses de Horn.

• : exemples négatifs exprimés sous forme de clauses de Horn.

Sortie Trouver une hypothèse sous forme d’un ensemble de clauses de Horn et telle que

les propriétés suivantes soient le plus possible respectées :

• Complétude : .

• Consistance : .

L’hypothèse en sortie, doit satisfaire les exemples positifs et rejeter au maximum les

exemples négatifs. Le processus de recherche de l’hypothèse se base sur des techniques de

la programmation logique telles que la substitution, la spécialisation, la généralisation,

l’unification et la résolution, mais aussi sur les méthodes de fouille de données adaptées à la

logique de premier ordre et souvent sur la propositionnalisation.[11][20].

Références

Bibliographiques

Références bibliographiques

86

Références Bibliographiques

[1] Abdiche F, Atmani B. Extraction de Règles de Classification à partir des Données

Spatiales.Informatique, Article de l’équipe de recherche « Simulation, Intégration et Fouille

de données (SIF)»Algerie:Université d’Oran Es-Senia, 2006, pp.1-12

[2]Ansaf S. Recherche de motifs fréquents pour l’extraction de règles d'associations et de

caractérisation, Thèse de doctorat,Université d’Orléans, 2003, pp. 1-34.

[3]Aufaure M, Laurent Y, Zeitouni K. Fouille de données spatiales, "Le temps, L'espace et

l'évolutif en sciences du traitement de l'information - Tome 2", Livre, Cépaduès éditions.

France, Septembre 2000, pp. 319-328.

[4] Barre M, Roger Ch. Les bases de données spatiales, Projet IRD, Université de la Nouvelle

Calldonie ,2005,pp. 1-45

[5] Belbachir Kh. Etude de l'application du Data Mining à l'analyse spatiale : Extraction des

règles d'associations, Mémoire de magister, Université Usto Mohamed BOUDIAF –Oran,

2007.

[6] Blockeel H., L. De Raedt, Top-Down induction of first order logical decision trees,

Artificial intelligence, 102(2-2)/ 285-297, 1998

[7] Boulahya S, Représentation et interrogation de données spatio-temporelles : Cas d'étude

sur PostgreSQL/PostGIS.Belgique, Mémoire, Université libre de Bruxelles , 2008 - 2009,pp.

1-113

[8] Breiman L., J.H. Friedman, R.A. Olshen, C.J. Stone, Classification and Regression Trees,

Ed. Wadsworth& Brooks. Montery, Californie, 1984

[9] Chelghoum N, Zeitouni K. Article : Datamining spatial un problème de datamining multi-

tables. Prism.France, Université de Versailles, 2004, Vol.14 N°02, pp.129-145.

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

[11] Chelghoum N., Zeitouni K, Laugier T., Fiandrino A., Loubersac L., "Fouille de données

spatiales - Approche basée sur la programmation logique inductive", 6èmes Journées

d'Extraction et de Gestion des Connaissances, EGC 2006, Edition CEPADUES, Lille,Janvier

2006, pp. 529-540.

[12] Chelghoum N., Zeitouni K. Article : Mise en œuvre des méthodes de fouille de données

spatiales : Alternatives et performances. EGC 2004, Clermont-Ferrand, Janvier 2004.

[13] Chelghoum N., Zeitouni K., Boulmakoul A. Article : Fouille de données spatiales par

arbre de décision multi-thèmes. EGC 2002, Montpellier, Janvier 2002, pp. 281-286.

[14] Clais S. Rapport de stage : étude comparative des systèmes de gestion de bases de

données spatiales.Lirmm.France, Université Montpellier II,décembre 2003, pp.1-69.


87

[15] Cliff A.D., Ord J.K., "Spatial autocorrelation", Pion, London, 1973.

[16] Denis F, Rémi G. Apprentissage automatique : les arbres de décision [en ligne].

Disponible sur :

< http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie004.html > (consulté le

25.02.2016).

[17] Deren L, Shuliang W. Concepts, principles and applications of spatial data mining and

knowledge discovery, National Laboratory for Information Engineering in Surveying:

Wuhan University, 430079, China, 2005.pp. 1-13

[18] Dominique Sch , Regis C .Les concepts spatiaux fondamentaux. GITTA,pp.1-23.

[19] Dzeroski Sa. MultiRelational Data Mining : An Introduction. ACM SIGKDD

Explorations Newsletter, Vol. 5, Issue 1, pp. 1-16, July 2003.

[20] Dzeroski S, Raedt L. Multi Relational Data Mining: The Current Frontiers. ACM

SIGKDD Explorations Newsletter, Vol. 5, Issue 1, pp. 100-101, July 2003,.

[21] El Hadi Kh. Représentation de données spatiales adifférents niveaux d'abstraction

:Application à l'archéoastronomie. Thèse doctorat. France, Université de Corse, tel-

00188500, version 1 - 17 Nov. 2007, pp.1-52

[22] Equipe de fouille de données et bioinformatique théorique de l’université de Strasbourg.

http://newlsiit.u-strasbg.fr/bfo_fr/index.php/Accueil

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

[24] Ester M, Kriegel H.P., Sander J., "Spatial Data Mining: A Database Approach", in

proceedings of 5th Symposium on Spatial Databases, Berlin, Germany, 1997.

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

[26] Ester M, Hans-Peter Kriegel, Jörg Sander. Algorithms and Applications for Spatial Data

Mining, Université de Munich, 2001.

[27] Ester M, Hans-Peter Kriegel, Jörg Sander. Spatial Data Mining: A Database Approach,

Université de Munich, 1997.

[28] Franklin, C.: An introduction to geographic information systems: linking maps to

databases. Database, vol. 15, no. 2, pp.13--21,1992

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

http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie004.html


88

[30] Huang Y., Xiong H., Shekhar S., and Pei J., Mining Confident Co-location Rules

without a Support Threshold. 18th ACM Symp.on Applied Computing, 2003.

[31] Koperski K ,adhikary J,Han J.spatial data mining:Progress and Challenges survey paper

.Université de Canada ,pp.1-16

[32] Lallich S, Teytaud O. Evaluation et validation des règles d'association. n° spécial

"Mesures de qualité pour la fouille des données", Revue des Nouvelles Technologies de

l'Information, RNTI-E-1, pp. 193-218. 2004.

[33] Luc A. Vidéo de cours sur les données spatiales sur le site de GeoDa,

http://geodacenter.asu.edu/spatial-data-br, consulté le 12 fevrier 2012.

[34] Marghoubi R, Boulmakoul A, Zeitouni K. Spécification d’un système de data mining

spatial dans le contexte de gestion des services à valeur ajoutée, Faculté des sciences

techniques de Mohamadia (FTSM).

[35] Marghoubi R, Boulmakoul A, Zeitouni K. Utilisation des treillis de Galois pour

l’extraction et la visualisation des règles d’association spatiales, Faculté des sciences

techniques de Mohamadia (FTSM).

[36] Open Geospatial Consortium. < http://www.opengeospatial.org/> ,( consulter le 27.mars

2016)

[37] Petre K. Data Structures for Spatial Data Mining.FI MU.CzechRepublic:Masaryk

University,FIMU-RS-2001-05,September 2001,pp 1-24

[38] Pierre G, Arnaud M. Atelier : Fouille de données complexes dans un processus

d'extraction des connaissances .EGC 2008,Nice:Université de Sophia Antipolis ,janvier

2008,1-124

[39] Rakesh A, Ramakrishnan S. Fast algorithms for mining association rules in large

databases. Proceedings of the 20th International Conference on Very Large Data Bases,

VLDB, pages 487-499, Santiago, Chile, Septembre 1994.

[40] Road Safety Data. [Online]. Available: <https://data.gov.uk/dataset/road-accidents-

safety -data> [Consulter: 19-Nov-2019].

[41] Sadok Ben Y, Engelbert MN. Approches d’extraction de règles d’association basées sur

la correspondance de Galois. RSTI - ISI – 9/2004. Motifs dans les bases de données, pages 23

à 55.

[42] Scharff C. Règles d’association [en ligne]. Disponible sur : <

http://www.csis.pace.edu/~scharff/DMIFI/associations5.ppt > (consulté le 27.03.2016).

[43] Shashi S ,Pusheng Z, Yan H, Ranga RV .What's Special about Spatial Data Mining?

.USA:université de Minnesota,pp.1-44

[44] Shashi S, Pusheng Z, Yan H, Ranga RV. Trends in Spatial Data Mining.

informatique.USA: Université de Minnesota ,pp.4-192

http://www.opengeospatial.org/

http://www.csis.pace.edu/~scharff/DMIFI/associations5.ppt


89

[45] Shashi S, Pusheng Z. Spatial Data Mining: Accomplishments and Research Needs.

department.USA:université de Minnesota ,pp.1-65

[46] Shekhar Sh, Huang Y., Discovering Spatial Co-location Patterns : A Summary of

Results, In Proc. of 7th Int. Symposium on Spatial and Temporal Databases (SSTD),

Springer-Verlag, Lecture Notes in Computer Science, Juillet 2001

[47] Sihem O,Lamia G, Hafida B. Fouille de données multi-relationnelles : extraction de

connaissances par les règles d’association.informatique. Mémoire de master, Algerie,

Université Usto Mohamed BOUDIAF –Oran, 2011.

[48] Sitanggang I. S. et al., "An Extended ID3 Decision Tree Algorithm for Spatial Data," in

Proc. of the IEEE International Conference on Spatial Data Mining and Geographical

Knowledge Services, 2011, pp. 48‒53.

[49] Thomas G. Fouille de données spatiales pour la caracatérisation de paysages en lien avec

des fonctionnalités agro-écologiques. IRISA.Rennes,inria-00544144, version 1, pp.385-387,

7 Dec 2010

[50] Zeitouni K, Laurent Y. Le Data Mining Spatial et les bases de données spatiales,

Laboratoire PRISM.

[51] Zeitouni K. Mémoire d’habilitation à diriger des recherches : Analyse et extraction de

connaissances des bases de données spatiotemporelles. Informatique. France : Université de

Versailles Saint-Quentin-en-Yvelines, Décembre 2006.

[52] Zeitouni K.Fouille de données complexes. COSY:Université de Versailles,ppt, Edition

2005-2006 ,pp.1-61

[53] Zone cours. Intelligence d’affaires Partie II : Data Mining [en ligne]. Disponible sur :

< http://zonecours.hec.ca/.../H2006-1-710197.401600H06_Seance13.ppt > (consulté le

27.03.2016).

http://zonecours.hec.ca/.../H2006-1-710197.401600H06_Seance13.ppt

Documents

Présentée par : Sihem OUJDI Intitulé La fouille de données