Origines du Data Mining

Origines du Data Mining

Le DM peut être vu comme la conséquence de l’évolution des systèmes de traitement de l’information et plus particulièrement des Systèmes de Bases de Données. L’industrie des Systèmes de Bases de Données a connu une évolution dans le développement des fonctionnalités suivantes (voir figure 1.01) : la collecte de données et la création de bases de données, la gestion des données et l’analyse avancée des données. Depuis les années 1960, les bases de données et les technologies de l’information se sont systématiquement transformées en partant des systèmes de traitement de fichiers primitifs vers des Systèmes de Bases de Données sophistiqués et puissants. Les progrès constants et étonnants de la technologie informatique a conduit à de grandes quantités d’ordinateurs puissants et abordables, de matériel de collecte de données et de supports de stockage. Les données peuvent être stockées dans différents types de bases de données et de dépôt d’informations. Une architecture de dépôt de données s’est alors manifestée : le Data Warehouse. C’est un entrepôt de données hétérogènes organisées sous un schéma unifié sur un seul site afin de faciliter la prise de décision. La quantité croissante et rapide de données, collectées et stockées dans de grands et nombreux Data Warehouses, a largement dépassé notre capacité humaine de compréhension sans outils puissants. L’abondance des données, associée à la nécessité d’outils puissants d’analyse des données, a été décrite comme une situation riche en données mais pauvre en informations.

En conséquence, les données recueillies dans les grands dépôts de données deviennent des « tombes de données », des archives qui sont rarement visitées. Les décisions importantes sont souvent prises sur l’intuition d’un décideur, simplement parce que le décideur n’a pas les outils pour extraire les connaissances précieuses intégrées dans les vastes quantités de données. L’écart grandissant entre les données et les informations requiert un développement systématique d’outils de DM qui transformeront les tombeaux de données en « pépites d’or » du savoir. Le domaine du Data Mining a ainsi émergé dans les années 1990 à l’issu du premier workshop KDD (Knowledge Discovery in Databases) en 1989. [1][2]

Définitions

Le Data Mining, souvent traduit en français par « fouille de données », est une technique permettant l’extraction d’information d’intérêt (non triviale, implicite, inconnue à priori et potentiellement utile) à partir de données stockées dans de larges entrepôts de données, en utilisant des procédures automatiques ou semi automatiques pour une prise de décision. Comme ce processus peut être très difficile, il est souvent comparé au minage de l’or dans les rivières : le gravier des alluvions représente l’énorme quantité de données et les pépites d’or représentent les connaissances cachées que l’on veut trouver. Le DM est un domaine qui se situe à l’intersection des statistiques, de l’apprentissage automatique et des bases de données .

Terminologies sur le Data Mining 

Pour une bonne compréhension sur ce qui suit, il est nécessaire de définir les termes suivants :
• Concept
Un concept désigne un problème à résoudre, un phénomène à prédire ou un objectif à atteindre à partir des données et des techniques de DM.
• Dataset
Un dataset fait référence aux données utilisées pour le DM représentées sous forme de table. Un exemple est mis en évidence dans le tableau 1.01. Chaque ligne du dataset correspond à un événement tandis qu’une colonne désigne un attribut. Un événement est donc un vecteur composé de différents attributs. Ainsi, un dataset est une matrice dont les lignes sont les événements et les colonnes les attributs. Les attributs peuvent être sous forme nominale ou numérique.
• Classe
La classe désigne un attribut de la dataset dont la valeur est calculée ou conditionnée par la valeur des autres attributs. Elle représente l’attribut à prédire. Chaque événement peut avoir une classe qui lui est associée.

Type de données à explorer

La nature des données pouvant être utilisées pour le DM est variée. Cette section dresse une liste de ces types de données à explorer avec leur description.

Base de données relationnelle
Une base de données relationnelle est une base de données où l’information est organisée dans des tableaux à deux dimensions appelés relations ou tables. Selon ce modèle relationnel, une base de données consiste en une ou plusieurs relations. Les lignes de ces relations sont appelées des enregistrements tandis que les   sont appelées attributs. Chaque enregistrement dans une table représente un objet identifié par une clé unique et décrit par un ensemble de valeurs d’attribut. Un modèle de données sémantiques, tel qu’un modèle de données entité-relation (ER), est souvent construit pour des bases de données relationnelles. Un modèle de données ER représente la base de données comme un ensemble d’entités et leurs relations. Les logiciels qui permettent de créer, utiliser et maintenir des bases de données relationnelles sont des Systèmes de Gestion de Base de Données Relationnelles ou SGBDR. [1]

Data Warehouse
Un Data Warehouse est un entrepôt de données collectées à partir de sources multiples, stockées sous un schéma unifié et qui résident habituellement sur un site unique. Les entrepôts de données sont construits par un processus de nettoyage des données, d’intégration des données, de transformation des données, de chargement des données et de rafraîchissement périodique des données. Un exemple illustre ce concept sur la figure 1.03. La structure physique réelle d’un Data Warehouse peut être une mémoire de données relationnelle ou un cube de données multidimensionnel. Un cube de données fournit une vue multidimensionnelle des données et permet l’accès rapide aux données déjà résumées. [1]

Base de données objet-relationnelles
Les bases de données objet-relationnelles sont construites sur la base d’un modèle objet-relationnel. Ce modèle étend le modèle relationnel en fournissant un type de données riche pour gérer des objets complexes et l’orienté objet. Conceptuellement, le modèle objet-relationnel hérite des concepts essentiels des bases de données orientées objet, où, en termes généraux, chaque entité est considérée comme un objet. Les données et le code relatifs à un objet sont encapsulés dans une seule unité. Chaque objet est associé à ce qui suit :

• un ensemble de variables qui décrivent les objets. ceux-ci correspondent aux attributs dans les modèles relationnels y compris le modèle ER ;
• un ensemble de messages que l’objet peut utiliser pour communiquer avec d’autres objets ou avec le reste du système de base de données ;
• un ensemble de méthodes, où chaque méthode détient le code pour implémenter un message. Lors de la réception d’un message, la méthode renvoie une valeur en réponse. Pour le DM dans des systèmes objet-relationnels, des techniques doivent être développées pour gérer des structures d’objets complexes, des types de données complexes, des hiérarchies de classes et de sous-classes, l’héritage de propriétés, de méthodes et de procédures. [1]

Bases de données spatiales et spatio-temporelles

Base de données spatiale 

Une base de données spatiale est une base de données optimisée pour stocker et requêter des données reliées à des objets référencés géographiquement y compris des points, des lignes et des polygones. Il existe une multitude d’exemples comprenant : des bases de données géographiques (carte), des bases de données dont la conception est assistée par ordinateur, ainsi que des bases de données d’imagerie médicales et d’images satellitaires. Les données spatiales peuvent être représentées en format raster, consistant en des cartes binaires (bit maps) ou des cartes de pixels (pixel maps) à n dimensions. Par exemple, une image satellite 2D peut être représentée sous forme de données raster, chaque pixel enregistrant les précipitations dans une zone donnée. Les relations entre un ensemble d’objets spatiaux peuvent être examinées par le DM afin de découvrir quels sous-ensembles d’objets sont spatialement auto-corrélés ou associés. De plus, la classification spatiale peut être effectuée pour construire des modèles de prédiction basés sur l’ensemble pertinent de caractéristiques des objets spatiaux. [1]

Base de données spatio-temporelle
Une base de données spatiale stockant des objets spatiaux qui changent avec le temps est appelée une base de données spatiotemporelle, à partir de laquelle des informations intéressantes peuvent être extraites. Par exemple, nous pourrions être en mesure de distinguer une attaque bioterroriste basée sur la propagation géographique d’une maladie avec le temps. [1]

Bases de données temporelle, séquentielle et série-chronologique

• Une base de données temporelle stocke généralement des données relationnelles qui incluent des attributs temporels. Ces attributs peuvent impliquer plusieurs horodatages (associations d’une heure et d’une date à un événement), chacun ayant une sémantique différente.
• Une base de données séquentielle stocke des séquences d’événements ordonnés, avec ou sans notion concrète de temps. Voici quelques exemples : les séquences d’achats des clients, les flux de clics Web et les séquences biologiques.
• Une base de données de série-chronologique stocke des séquences de valeurs ou d’événements obtenus sur des mesures répétées de temps (horaire, quotidien, hebdomadaire). L’exemple concret que l’on peut citer est l’observation de phénomènes naturels comme la température et le vent. Les techniques de DM peuvent être utilisées pour trouver les caractéristiques de l’évolution des objets, ou la tendance à changer des objets dans la base de données. Ces informations peuvent être utiles dans la prise de décision et la planification de stratégie. [1]

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1: ETAT DE L’ART DU DATA MINING
1.1 Introduction
1.2 Origines du Data Mining
1.3 Définitions
1.4 Terminologies sur le Data Mining
1.5 Type de données à explorer
1.5.1 Base de données relationnelle
1.5.2 Data Warehouse
1.5.3 Base de données objet-relationnelles
1.5.4 Bases de données spatiales et spatio-temporelles
1.5.4.1 Base de données spatiale
1.5.4.2 Base de données spatio-temporelle
1.5.5 Bases de données temporelle, séquentielle et série-chronologique
1.5.6 Bases de données textuelles et multimédias
1.5.6.1 Base de données textuelles
1.5.6.2 Base de données multimédias
1.5.7 Le World Wide Web
1.6 Applications du Data Mining
1.7 Techniques de Data Mining
1.7.1 Analyse prédictive
1.7.2 Analyse descriptive
1.8 Elaboration d’un projet de Data Mining
1.8.1 Compréhension du concept
1.8.1.1 Evaluer la situation
1.8.1.2 Déterminer les objectifs à atteindre
1.8.2 Compréhension des données de départ
1.8.3 Préparation des données
1.8.4 Construction du modèle ou modélisation
1.8.5 Evaluation du modèle
1.8.6 Déploiement
1.9 Conclusion
CHAPITRE 2: APPRENTISSAGE AUTOMATIQUE
2.1 Introduction
2.2 Définitions
2.3 Apprentissage supervisé
2.3.1 Principe
2.3.2 Classification
2.3.2.1 Formulation du problème de classification
2.3.2.2 Minimisation du Risque Empirique
2.3.2.3 Sur-apprentissage et risque total
2.3.2.4 Théorie de Vapnik
2.3.3 Régression
2.3.4 Quelques algorithmes d’apprentissage supervisé
2.3.5 Séparateur à Vaste Marge (SVM)
2.3.5.1 SVM à classe binaire
2.3.5.2 SVM multiclasse
2.4 Apprentissage non supervisé
2.4.1 Notions sur le clustering
2.4.1.1 Partitions, pseudo-partitions et partitions floues
2.4.1.2 Hiérarchies et pseudo-hiérarchies
2.4.1.3 Centroïdes et médoïdes
2.4.1.4 Concavité et convexité
2.4.2 Etapes du clustering
2.4.2.1 Préparation des données
2.4.2.2 Le choix de l’algorithme
2.4.2.3 L’exploitation des clusters
2.4.3 Différentes méthodes de clustering
2.4.3.1 Le clustering hiérarchique
2.4.3.2 Le clustering par partitionnement
2.4.4 L’algorithme des K-means
2.5 Conclusion
CHAPITRE 3: MODELISATION D’UN SYSTEME DE CLASSIFICATION D’IMAGES
3.1 Introduction
3.2 Généralités sur la classification d’images
3.3 Etapes de création d’un système de classification d’image
3.4 Acquisition d’image
3.5 Prétraitement
3.6 Segmentation
3.6.1 Approches contours
3.6.2 Approche région
3.6.2.1 Le seuillage
3.6.2.2 Le region-growing
3.6.2.3 Le split and merge
3.6.3 Segmentation par clustering
3.7 Extraction des caractéristiques
3.7.1 Extracteurs de bas niveau
3.7.1.1 Les statistiques d’histogramme
3.7.1.2 Les statistiques des matrices de cooccurrence
3.7.2 Extracteurs de plus haut-niveau
CONCLUSION

Télécharger le rapport complet