Selon [12], [17], jusqu'à 80% des données d'une organisation ont une composante spatiale. Les données spatiales sont de plus en plus nombreuses grâce à l'évolution des outils d'acquisition de données (ex. GPS, images satellite, photo aériennes, etc.) et des méthodes de structuration (ex. raster, vecteur) et de représentation (ex. représentations 2D, 3D). De plus, des outils et des méthodes de représentation des données spatiales (ex. des outils de visualisation) ont été développés pour mettre en évidence les caractéristiques spatiales des données (position, forme, taille, orientation, etc.) et les relations qui existent entre elles (ex. intersection, adjacence, etc.) afin de faciliter leur interprétation. En outre, il y a eu des innovations importantes dans le domaine des technologies de l'information, particulièrement dans les technologies de base de données et des systèmes intelligents d'aide à la décision (SIAD). Les SIAD sont des outils issus de l'IA qui fournissent des techniques, des données et des solutions pour identifier et résoudre les problèmes liés à la prise de décisions stratégiques.
Les SIAD utilisent généralement les techniques de fouille de données qui permettent l'exploration des entrepôts de données actuelles et historiques à différents niveaux d'agrégation. Les entrepôts de données se basent généralement sur une structure multidimensionnelle, ils contiennent alors ce qu'on appelle des « cubes de données ». Les cubes de données facilitent la navigation rapide des données selon différents niveaux de granularité (ex. d'un niveau détaillé à un niveau plus général). Lorsque les cubes de données contiennent des données spatiales (nous les appelons «cubes de données spatiales»), ils permettent à la fois de profiter des avantages de la structure multidimensionnelle et de la représentation cartographique des données spatiales.
La fouille de données est l'analyse des observations de larges jeux de données dans le but d'identifier des relations non soupçonnées et de résumer la connaissance incluse au sein de ces données sous de nouvelles formes à la fois compréhensibles et utiles pour l'expert de ces données. La fouille de données fait appel principalement aux disciplines de l'intelligence artificielle, de l'apprentissage automatique, de la logique floue, des réseaux de neurones, des arbres de décisions et de la statistique et l'analyse de données. Elle s'effectue généralement sur des tables bidimensionnelles et se décompose essentiellement en trois grandes familles de méthodes : les méthodes descriptives, les méthodes de structuration et les méthodes explicatives.
La classification, qui appartient à la troisième catégorie des méthodes de fouille de donnée, est une méthode explicative qui cherche à établir un modèle décrivant un phénomène, défini à partir d'une variable endogène, à l'aide d'un ensemble de descripteurs appelés variables exogènes.
La plupart des méthodes de classification ne prennent pas en considération la représentation des données sous format relationnelles. Une donnée spatiale est généralement composée de trois parties : une partie géométrique (la forme par exemple ligne, point, polygone), une partie descriptive (par exemple le nom, la population d'une ville) et une partie métrique calculée (par exemple la superficie, le périmètre) [16]. Pendant le processus de fouille de données spatiales, on cherche à trouver les règles qui divisent l'ensemble des objets on plusieurs classes en utilisant non seulement leurs attributs descriptifs mais aussi leurs relations spatiales.
Par ailleurs, la représentation de la connaissance est aussi une question fondamentale dans la conception d'un SIAD, car la représentation utilisée peut réduire la complexité en termes de traitement et de stockage. Nous présentons par cet article notre contribution dans ce domaine qui consiste à apporter une solution au problème d'extraction et de représentation des règles de classification par la mise en oeuvre d'un outil de construction de graphe cellulaire [5], [2], [6].
La fouille de données spatiales est définie comme l'extraction de connaissances implicites de relations spatiales ou d'autres propriétés non explicitement stockées dans les bases de données spatiales [18]. Dans ce contexte, beaucoup de travaux existent, mais la majorité consiste à appliquer des techniques de la fouille de données pour extraire de la connaissance à partir des données non spatiales. Nous pouvons citer à titre d'exemple les travaux de Han [13] qui proposent un algorithme pour l'extraction des relations d'hiérarchie. Cette technique suppose que l'utilisateur ou l'expert doit fournir à l'algorithme une hiérarchie de concepts, qui n'est souvent pas possible. Nous pouvons citer aussi la méthode STING [19], qui est une méthode hiérarchique et qui consiste à diviser le territoire en plusieurs zones de taille plus réduite afin de minimiser la complexité de la recherche.
Nous pouvons invoquer aussi les travaux sur les règles d'associations spatiales [15] qui sont une extension des règles d'associations classiques appliquées pour l'extraction d'un motif fréquent. De même nous soulignons l'importance du clustering qui est une méthode de classification automatique permettant le regroupement d'objets par classes homogènes. Pour cela, elle cherche à maximiser la similarité intra-classe et à minimiser la similarité inter-classes. Les principales méthodes sont celles par agrégation autour de centres mobiles, comme les k-means, les nuées dynamiques, la classification automatique hiérarchique (CAH) et enfin, les méthodes par densité comme DBSCAN [9], BIRCH [22] et OPTICS [3]. La transposition au domaine spatial s'appuie sur une mesure de similarité d'objets localisés suivant leur distance métrique.
Nous citons aussi les travaux de Fayyad [11] qui a utilisé les arbres de décision pour la classification des objets stellaires pour les étoiles et les galaxies et, où environs 3 Terabytes d'images ont été analysées. Ces données ont été traité à l'aide du système FOCAS, qui sélectionne les objets et fournie des attributs de base comme : la magnitude, les régions, intensité, l'orientation, …. Les objets ont été classifiés par des astronomes. Basé sur cette classification, dix bases de données d'apprentissages ont été conçues pour construire l'arbre de décision dont des règles sont extraites. La méthode ne s'applique pas à la base de données sous format vectoriel, souvent utilisé dans les systèmes d'informations géographique.
Par ailleurs, une méthode de classification des objets spatiaux utilisant les graphes de voisinages a été proposée par Ester [10]. L'algorithme est basé sur la méthode ID3 et les objets sont traités comme voisins s'ils satisfont les relations de voisinages, qui peuvent être une des cas de figure suivants : Les relations topologiques, les relations de métriques et les relations de directions.
Dans notre contribution nous nous sommes inspirés des travaux de Chelghoum [7], par l'algorithme SCART (Spatial CART) et les travaux de Zeitouni [20], [21]. La plupart de ces travaux considèrent que les bases de données spatiales et la majorité des SIG organisent les données en couches thématiques, chacune avec une description ou schéma propre. Les méthodes à bases de clustering ou de généralisation ne prennent pas en compte cette organisation et par conséquent, ne peuvent révéler des relations inter-thèmes cachées.
Le Clustering est une méthode en fouille de données permettant le regroupement d'objets par classes homogènes. Donc il s'agit de trouver une métrique qui peut détecter les points similaires vis-à-vis un phénomène et visualisé les concentrations.
Le point faible de cette technique est le fait qu'elle repose sur un seul critère qui est la localisation alors que la réalité est multicritère.
La méthode STING comme les méthodes à base de Clustering, vise à identifier des classes d'objets fortement similaires. Elle ne fournie aucune description sur la relation des classes et leurs relations avec les caractéristiques des objets.
La méthode d'hiérarchie et généralisation de concept repose sur l'intervention préalable d'un expert pour définir l'hiérarchie de concept.
Ainsi nous pouvons remarquer que les méthodes précédentes n'exploite qu'un seul thème à la fois, alors que les données géographiques sont souvent représentées par plusieurs couches thématiques qui cachent des relations topologiques entres les objets qu'elles contiennent.
Notre contribution dans ce domaine, en prenant en considération le caractère spatial des données et l'interaction avec l'environnement géographique, est la conception d'un système d'extraction et d'optimisation des règles de classification appliqué à la sécurité routière.
Comme il a été souligné précédemment, la mise en place de l'exemple d'apprentissage nécessite l'analyse des données spatiales, cette dernière s'appuie sur la prise en compte des relations spatiales qui sont explicites entre phénomène du territoire (accident, épidémie, séisme, …) qui fournissent des données implicites, nécessaires pour l'algorithme de la fouille données, nous disons que la fouille de données spatiales est une extension de la fouille de données classique [11]. Dans ce paragraphe, nous introduisons quelques primitives basées sur le concept de relations de voisinage.
L'influence mutuelle entre deux objets dépend des facteurs tels que la topologie, la distance ou la direction entre les objets. Par exemple, un nouvel ensemble industriel peut polluer son voisinage selon la distance et sur la direction principale du vent. La figure 1 montre une carte utilisée dans l'évaluation d'un endroit possible pour un nouvel ensemble industriel. La carte montre trois régions avec différents degrés de pollution (indiquée par les différentes couleurs) provoqués par l'usine prévue.
Dans cette section, nous présentons trois types de base de relations spatiales : relations topologiques, de distance et de direction qui sont des relations binaires, c'est-à-dire, relations entre les paires d'objets. Les objets spatiaux peuvent être des points ou des objets dans l'espace prolongés tels que des lignes, des polygones. Des objets dans l'espace prolongés peuvent être représentés par un ensemble de points sur sa surface, par exemple par les bords d'un polygone (représentation de vecteur) ou par les points contenus dans l'objet, par exemple les Pixel d'un objet.
Les relations topologiques sont les relations qui restent invariables sous des transformations topologiques, elles sont préservées si les deux objets sont changés d'échelle, translatés ou pivotés simultanément. Les définitions formelles sont basées sur les frontières, les intérieurs et les compléments des deux objets connexes. Ces relations selon les extensions SQL d'oracle spatial sont [4]: Inside, Touch, Covers, Equal, Contains, Disjoint, Coverded By, Overlap Boundary. Une définition théorique est dans [8].
Les relations de distance Les relations de distance sont ces relations comparant la distance de deux objets à une constante donnée utilisant un des opérateurs arithmétiques. La distance entre deux objets, ensemble de points, peut alors simplement être défini par la distance minimum entre leurs points. Nous citons selon SQL étendu d'oracle spatial [4] : Within Distance, Nearest Neighbor.
Pour définir la relation de direction ܱ ଶ ܴ ܱ ଵ , nous distinguons l'objet source ܱ ଵ de l'objet destination ܱ ଶ de la relation ܴ de direction. Il y a plusieurs possibilités pour définir des relations de direction selon le nombre de points qu'ils considèrent dans la source et l'objet de destination.
Nous définissons la relation de direction de deux objets dans l'espace prolongés utilisant un représentant de l'objet ܱ ଵ de source et tous les points de la destination object ܱ ଶ . . La valeur de proximité est un paramètre subjectif, nous considérons que deux objets spatiaux sont proches si la distance euclidienne est inférieure à 10 mètres. À la fin de cette phase d'analyse de propriété de voisinage, nous fournissons au module chargé de la génération des règles un échantillon d'apprentissage. Nous utilisons l'outil IGSS développé au sein de notre équipe de recherche, pour la partie arbre de décision et génération des règles.
À partir de notre échantillon d'apprentissage issu de l'analyse de voisinage, nous appliquons le principe de la machine cellulaire au sein du module IGSS. Ce dernier aide à l'extraction des règles conjonctives, illustrées par la figure 6, qui seront insérées dans la base de règles de la machine CASI [5] (Cellular Automata for Symbolic Induction). En exploitant les propriétés de voisinages entre les objets spatiaux de trois couches thématiques, nous avons réussi à extraire trois règles utiles et porteuses d'information qui n'ont pas été implicite au préalable.
Dans cet article nous avons abordé la fouille de données spatiale comme un cas particulier de la fouille de données classique par l'enrichissement avec des requêtes de voisinage. Étant donné la diversité de solutions logicielles existantes implémentant une multitude d'algorithmes d'apprentissage, nous avons choisi dans un premier temps d'intégrer les fonctionnalités d'analyse des propriétés de voisinages. Nous avons réussi donc à ramener plusieurs couches thématique en une table relationnelle afin d'appliquer n'importe quel algorithme de classification.
Dans le contexte de l'analyse des accidents de la route, le graphe d'induction cellulaire engendré est un modèle booléen qui nous permettra de voir de plus prêt les relations entre l'accident est sont environnement ainsi que les éléments responsables de ce dernier, donc le graphe d'induction engendré facilitera l'identification des problèmes de sécurité sur le réseau routier en vue de proposer des mesures de sécurité pour y remédier.