Fouille de données spatiales

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 V^e et IV^e 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^[4]. Du temps de Ptolémée la classification des formes du relief est achevée^[5]. En Europe, apparaissent à la fin du IX^e 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^[6].

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

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))^[8],[9].

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)^[10], formalisée par Georges Matheron à l'École des Mines de Paris en 1962^[10].

Le premier SIG, le Système canadien d'information géographique^[11] est créé par Roger Tomlinson en 1964-66 et est opérationnel en 1971^[12]. La société Environmental Systems Research Institute (ESRI) est fondée en 1969 par Jack et Laura Dangermond à Redlands, Californie^[13]. Le 22 février 1978 à 23h44, le premier satellite GPS est lancé par l'US Air Force^[14].

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.

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^{[15],[Note 1]}, tandis que l'industrie a des objectifs de rentabilité dans l'implantation d'usines, d'antennes de télécommunication, de panneaux publicitaires, etc.^[6],[16]. 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^[17] 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^[18].

En archéologie, les données géographiques et la fouille de données spatiales sont exploitées pour trouver de nouveaux sites^[19]. Par exemple, l’étude du peuplement mycénien utilise des modèles informatiques pour simuler l’occupation humaine dans l’espace, illustrant ainsi l’application des techniques numériques dans l’analyse spatiale complexe^[20].

La fouille de données spatiales est utilisée en épidémiologie pour suivre et prévoir la propagation des maladies^[21]. 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^[22].

« 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^[23] comme GeoDa^[24]. Un des SIG les plus connus que l'on trouve sur le marché est ArcGIS^[25]; Quantum GIS^[26] 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^[27],[28]. 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^[29].

Outre GeoDa, déjà cité, on trouve Geominer^[30], Descartes^[31], Fuzzy Spatial OQL for Fuzzy KDD, GWiM, GeoKD^[32], SPIN^[33]!, etc.

Summarize Timeline Top Qs Fact Check

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^[34].

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^[35]. On trouve cette technique dans la recherche des incidents de trafic automobiles (accidents, bouchons...)^[35]. 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^[36].

La recherche des colocalisations concerne deux ou plusieurs phénomènes spatiaux reliés entre eux^[37]. 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^[38].

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^[39]. 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^[40] permettent d'en avoir une connaissance précise^[41],[42].

L'interpolation est la technique consistant à estimer la valeur d'un phénomène au point ${\displaystyle x_{0}}$ en fonction des valeurs de ce même phénomène aux points ${\displaystyle 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^[43].

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^[44], 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 »)^[45].

• Dans la seconde catégorie, les analystes géographes se tournent vers la régression, la régression locale et le krigeage^[45].

Le Clustering^{[6],[Note 2]} 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)^[32]. 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^[46].

La régionalisation recouvre des techniques dont le but est la classification non supervisée incorporant les contraintes de contiguïté^[46]. Plus précisément, ces techniques permettent de regrouper des objets spatiaux dans des régions contiguës tout en optimisant une fonction "objectif"^[47].

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^[48]...

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^{[49],[50],[51]}. Autrement dit, les modèles permettent d'estimer les fonctions de classification, en fonction des caractéristiques géospatiales de l'environnement^[52]. 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^[53], l'analyse d'image^[54], l'hydrologie^[55], l'analyse criminologique^[56], 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 ^[57],[58].

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é^[52], en tenant compte de la caractéristique markovienne exprimant que la dépendance ne provient que des voisins immédiats^[52]. Si ${\displaystyle f:S\rightarrow L}$ définit les classes ${\displaystyle L=\{l_{i},~i=1..n\}}$ d'un ensemble de sites ou d'évènements spatiaux ${\displaystyle S=\{s_{j},~j=1..m\}}$ est un champ aléatoire markovien, alors les classes ${\displaystyle f_{L}(s_{i})}$ sont des variables aléatoires possédant la propriété de Markov qui considère que la classe ${\displaystyle f_{L}(s_{i})}$ ne dépend que des voisins de ${\displaystyle s_{i}}$, traduisant ainsi dans le modèle la dépendance spatiale^[59],[60].

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^[61]. 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^[62].

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^[63]. L'exemple tiré de ^[64]

${\displaystyle is\_a(x,school)\rightarrow close\_to(x,parks)}$ ${\displaystyle (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, ${\displaystyle close\_to}$ est un prédicat.