# Fouille de données spatiales

La fouille de données spatiales (spatial data mining) est la technique d'exploration de données géographiques, à notre échelle sur terre, mais aussi astronomiques, dont le but est de découvrir des régularités intéressantes dans des données textuelles, diachroniques, ou géométriques telles que vecteurs, trames, graphes. Les données spatiales donnent des informations à des échelles différentes, fournies par des techniques différentes, sous des formats différents, dans une période de temps souvent longue en vue de l'observation des changements. Les volumes sont donc très importants, les données peuvent être imparfaites, bruitées. De plus, les relations entre les données spatiales sont souvent implicites : les relations ensemblistes, topologiques, directionnelles et métriques se rencontrent fréquemment dans cette spécialisation de l'exploration des données. La fouille de données spatiales est donc particulièrement ardue.
L'analyse spatiale participe avec les systèmes d'information géographique à l'analyse exploratoire des données spatiales, mais sa raison d'être constitue la modélisation spatiale.
On utilise la fouille de données spatiales pour explorer les données des sciences de la terre, les données cartographiques du crime, celles des recensements, du trafic routier, des foyers de cancer, etc.

## Histoire

L’histoire de la fouille de données spatiales est liée à celle de la géographie, de l’astronomie et des mathématiques, et au développement de ces disciplines.
Historiquement, la fouille de données est tout d’abord physique et descriptive. La cartographie a été un des moteurs de celle-ci. En Chine, aux environs des Ve et IVe siècles av. J.-C., les premières cartes indiquent les éléments du relief et des éléments économiques avec une tentative de classification pour les représenter. Du temps de Ptolémée la classification des formes du relief est achevée. En Europe, apparaissent à la fin du IXe siècle les portulans pour lesquels le référencement et la classification des amers étaient nécessaires.
C’est en 1855 qu’apparait peut-être la première fouille de données géographique prédictive. Cette année-là, John Snow recherche les causes de l’épidémie de choléra de la fin de l’année 1854 à Londres, et avec une hypothèse novatrice, et une description précise des foyers de la maladie, prouve que l’eau est un vecteur de contamination et trouve la pompe à eau de Broad Street qui en est la cause.
En 1905, les docteurs McKay, Fleming, et Burton font un véritable travail de data miners pour expliquer les taches dentaires de 87,5 % des habitants de Colorado Springs. Analyse des corrélations, avec l’observation des caries notamment, analyse géographique du phénomène, localisant aux alentours de Pikes Peak les enfants ayant des taches, et finalement, en 1931, l’explication par d’autres dentistes du phénomène lié au fluor présent dans les eaux du Colorado bues par les habitants.
En 1934, Gehlke et Biehl se rendirent compte, en étudiant les résultats d'un recensement dans la région de Cleveland, qu'un coefficient de corrélation augmentait avec les niveaux d’agrégation, soulevant ainsi un fameux problème connu en analyse géographique à savoir : le problème des unités spatiales modifiables (modifiable areal unit problem (MAUP))$^,$.
Le sud-africain Daniel Gerhardus Krige, créateur éponyme, met au point la technique d'interpolation des données spatiales en 1951-1952 connue sous le nom de krigeage (Kriging), formalisée par Georges Matheron à l'École des Mines de Paris en 1962.
Le premier SIG, le Système canadien d'information géographique est créé par Roger Tomlinson en 1964-66 et est opérationnel en 1971. La société Environmental Systems Research Institute (ESRI) est fondée en 1969 par Jack et Laura Dangermond à Redlands, Californie. Le 22 février 1978 à 23h44, le premier satellite GPS est lancé par l'US Air Force.
Depuis l’avènement de l’exploration de données, les techniques de fouilles de données se sont rapprochées de celles en vigueur dans l'analyse spatiale pour traiter les gros volumes de données, perfectionner les techniques, et diversifier les applications.

## Applications

La fouille de données spatiales trouve son application aussi bien dans le domaine public, dans le domaine scientifique que dans le secteur privé. Mais les objectifs ne sont pas identiques. En exploitant les données géographiques, les administrations recherchent plutôt des modèles concernant la population et son bien-être$^,$, tandis que l'industrie a des objectifs de rentabilité dans l'implantation d'usines, d'antennes de télécommunication, de panneaux publicitaires, etc.$^,$. Dans le domaine des sciences, l'exploration des données spatiales sert la recherche. En astronomie et en astrophysique, la fouille de données spatiales sert à la classification automatique d'objets spatiaux, ou bien à découvrir des régions dignes d’intérêt, ou des objets rares dans l'immensité de notre univers. En archéologie, les données géographiques et la fouille de données spatiales sont exploitées pour trouver de nouveaux sites. La fouille de données spatiales est utilisée en épidémiologie pour suivre et prévoir la propagation des maladies. Les Sciences de la vie et de la Terre ont aussi recours à cette technique pour évaluer les tendances au cours du temps des modifications de la végétation dans des zones sensibles.

## Système d'information
### Système d'information géographique

   « Un Système d'information géographique est un système informatique permettant, à partir de diverses sources, de rassembler et d'organiser, de gérer, d'analyser et de combiner, d'élaborer et de présenter des informations localisées géographiquement, contribuant notamment à la gestion de l'espace. »
— Société française de photogrammétrie et télédétection, 1989
Les SIG ont pour vocation l'acquisition, l'archivage, l'analyse, l'affichage et l'abstraction des données géographiques. L'apport d'un SIG, pour ce qui concerne la fouille de données, est le stockage de l'information géographique numérisée que l'analyste géographe peut ainsi manipuler avec un outil intégré au SIG pour la visualisation par exemple ou bien des outils externes comme GeoDa. Un des SIG les plus connus que l'on trouve sur le marché est ArcGIS; Quantum GIS est un autre SIG que l'on peut citer et qui appartient à la sphère des logiciels libres.
Un SIG contient des données alphanumériques et des données spatiales. Dans un SIG, les données sont stockées soit sous format vectoriel, soit sous format raster$^,$. Le format vectoriel gère les points, les lignes et les polygones, les vecteurs sont complétés par des informations alphanumériques. Les données raster sont stockées sous forme de cellules formant une maille. Ces données sont aussi complétées par des données alphanumériques telles que la moyenne, le max, le min, la somme de grandeurs géographiques.

### Autres logiciels

Outre GeoDa, déjà cité, on trouve Geominer, Descartes, Fuzzy Spatial OQL for Fuzzy KDD, GWiM, GeoKD, SPIN!, etc.

## Fouilles et techniques de fouille

Les techniques de fouilles de données spatiales s'inspirent de celles de la fouille de données classique, avec une difficulté supplémentaire dans la nature des données qui est celle de la dépendance des données entre elles. Dans la fouille de données classique les variables sont supposées indépendantes, dans la fouille de données spatiales les données sont liées entre elles : une zone est dépendante de ce qui se passe aux alentours, une situation à un instant t dépend de ce qui s'est passé à l'instant t-1. Ces relations peuvent être métriques, topologiques, ou directionnelles.

### Fouilles
#### Données aberrantes

La recherche de données spatiales aberrantes (« outliers ») concerne la recherche de données spatiales dont les valeurs ne sont pas similaires à celles de leurs voisins. On trouve cette technique dans la recherche des incidents de trafic automobiles (accidents, bouchons...). Les données aberrantes peuvent être repérées par les techniques de visualisation graphiques, ou par des techniques quantitatives. Dans la première catégorie on trouve les nuages de variogrammes et les graphes de dispersions de Moran (« Moran scatterplots »); dans la seconde sont répertoriés les autres graphes de dispersions.

#### Colocalisation

La recherche des colocalisations concerne deux ou plusieurs phénomènes spatiaux reliés entre eux. Plus précisément, Shekhar et al. nous disent que des caractéristiques spatiales booléennes (« Boolean spatial feature ») sont des types d'objets spatiaux présents ou absents en différents lieux. Par exemple, des espèces de plantes, d'animaux, des types de routes, etc. sont des caractéristiques spatiales booléennes. Des schémas de colocalisation sont des sous-ensembles de caractéristiques spatiales booléennes qui sont souvent situées simultanément aux mêmes endroits.

#### Autocorrélation

Les méthodes statistiques supposent que les échantillons ou/et les variables soient non corrélées. En analyse des données spatiales, il arrive que les variables soient autocorrélées, souvent parce que leurs mesures dépendent de la distance. Il est important de savoir si les variables sont autocorrélées ou non. Les tests I de Moran, C de Geary et K de Ripley permettent d'en avoir une connaissance précise$^,$.

### Techniques
#### Interpolation

L'interpolation est la technique consistant à estimer la valeur d'un phénomène au point $x_{0}$ en fonction des valeurs de ce même phénomène aux points $x_{1},x_{2},....,x_{n}$. L'interpolation est nécessaire quand les mesures ne peuvent pas être effectuées partout, comme pour les précipitations, les températures, la composition des sols, les sources de pollution, la végétation.
Les techniques d'interpolation spatiales utilisent des approches déterministes ou des approches stochastiques.
* Dans la première catégorie, les analystes géographes préfèrent la méthode de Shepard, celles des plus proches voisins, ou la pondération inverse de la distance ( « Inverse distance weighting »), ou bien des méthodes de partitionnement comme celle des diagrammes de Voronoï, les techniques de type splines laplaciennes ou de tendances de surfaces (« Surface Trend »).
* Dans la seconde catégorie, les analystes géographes se tournent vers la régression, la régression locale et le krigeage.

#### Segmentation

Le Clustering$^,$ dans le domaine des données spatiales permet de grouper des points selon des caractéristiques communes intéressantes, trouver des sous-trajectoires dans des chemins empruntés, ou bien de regrouper des pixels selon des couleurs qui permettent ensuite de retrouver des éléments naturels (fleuves, mer, forêts). Plusieurs techniques ayant des buts différents sont utilisées dans la segmentation :
La classification non supervisée spatiale ou segmentation spatiale peut être développée par des méthodes hiérarchiques, des méthodes de partitionnement, d'autres fondées sur la densité de points ou de trajectoires, ou les méthodes fondées sur des grilles.
La régionalisation recouvre des techniques dont le but est la classification non supervisée incorporant les contraintes de contiguïté. Plus précisément, ces techniques permettent de regrouper des objets spatiaux dans des régions contiguës tout en optimisant une fonction "objectif".
L'analyse de motifs de points s'intéresse à la détection des points chauds, foyers d'épidémies ou proximité entre centres industriels et apparition de phénomènes tels que maladie, disparition d'espèces...

#### Classification et Régression

La classification spatiale utilise des modèles pour prédire les classes prédéfinies fondées sur des caractéristiques (variables explicatives) que sont les entités aussi bien que les relations spatiales avec d'autres entités et leurs caractéristiques$^,$$^,$. Autrement dit, les modèles permettent d'estimer les fonctions de classification, en fonction des caractéristiques géospatiales de l'environnement. Parmi les techniques modélisant la dépendance spatiale à des fins de classification ou de régression figurent :
Le Modèle d’Auto-régression simultanée (« Simultaneous AutoRegressive Model » ou « SAR ») est une généralisation du modèle de régression linéaire défini pour tenir compte de l'autocorrélation spatiale dans les problèmes de classification et de régression. Le modèle est utilisé dans les domaines aussi divers que l'économie locale, l'analyse d'image, l'hydrologie, l'analyse criminologique, etc.
La Régression géographiquement pondérée (« Geographically Weighted Regression » ou « GWR ») est un autre modèle de régression tenant compte de l'hétérogénéité spatiale$^,$.
Les champs aléatoires markoviens forment une autre famille d'outils permettant la classification des phénomènes géolocalisés. Dans ce modèle les relations d'interdépendances sont décrites par un graphe non orienté, en tenant compte de la caractéristique markovienne exprimant que la dépendance ne provient que des voisins immédiats. Si $f:S\rightarrow L$ définit les classes $L=\{l_{i},~i=1..n\}$ d'un ensemble de sites ou d'évènements spatiaux $S=\{s_{j},~j=1..m\}$ est un champ aléatoire markovien, alors les classes $f_{L}(s_{i})$ sont des variables aléatoires possédant la propriété de Markov qui considère que la classe $f_{L}(s_{i})$ ne dépend que des voisins de $s_{i}$, traduisant ainsi dans le modèle la dépendance spatiale$^,$.
Une alternative au modèle d’auto-régression simultanée est le modèle d'Auto-régression conditionnelle fondé sur le concept de champ aléatoire de Markov. Ce modèle est utilisé lorsque les dépendances sont locales avec une dépendance de premier ordre (Est-Ouest/ Nord-Sud) alors que le modèle SAR est plutôt utilisé dans le cas des dépendances de second ordre.

#### Règles
##### Règle d'association

Une règle d'association spatiale est une règle d'association où X ou Y contient des prédicats spatiaux - de types distance, direction, topologique - tels que proche, éloigné, contient, contigu, etc. Effectuer une fouille pour trouver les règles d'associations spatiales, consiste à trouver tous les prédicats, trouver tous les ensembles d'objets ( « itemset » ), et générer les règles fortes ( « strong rules » ), celles qui atteignent le support minimum et dépassent le seuil de confiance. L'exemple tiré de
$is\_a(x,school)\rightarrow close\_to(x,parks)$
$(80\%)$
signifie que si l'objet est une école elle est proche d'un parc avec un taux de confiance de 80 %. School et park sont des objets, $close\_to$ est un prédicat.

##### Règle prédictive
#### Détection de tendance
#### Géovisualisation
## Limites et problèmes

Le problème des unités spatiales modifiables (modifiable areal unit problem (MAUP)) se pose quand des données spatiales sont collectées au niveau individuel des objets et sont progressivement agrégées dans des groupes préalablement définis. Parfois, les résultats changent au fur et à mesure que le nombre de groupes diminue et l'agrégation augmente. En fait, ce problème peut être décomposé en deux phénomènes distincts : le premier est un problème d'échelle - les résultats se modifient quand les groupes s'agrandissent -, mais aussi un problème d'agrégation - le choix des groupes influe sur les résultats.
Comme dans toute exploration de données, la fouille de données spatiale est soumise à la contrainte de la qualité des données. Deux aspects de la qualité des données sont envisagées : la qualité interne et la qualité externe. La première fait référence à la généalogie des données - d'où proviennent-elles, quelles sont les transformations qu'elles ont subies -, à la précision géométrique (positional accuracy) par rapport au terrain, à l'actualité (temporal accuracy) qui met en jeu l'aspect temporel, à la cohérence logique (logical consistency) mettant en jeu la modélisation des données par rapport aux lois de la physique par exemple, et à l'exhaustivité (completeness)$^,$. La seconde fait référence à l'adéquation des données aux besoins des analystes (fitness for use)$^,$. Des données de qualité pour un analyste sont celles qui égalent ou dépassent ses attentes.