TOUR D’HORIZON DU DATA MINING

TOUR D’HORIZON DU DATA MINING

Présentation Générale du Data Mining

Le Data Mining, forage de données en français, est né du croisement de l’IA (Intelligence Artificielle) et de la statistique. Il est difficile de dire à quel époque on a commencé à faire du data mining (1970). Ce n’est que vers les années 1990 que les concepts on été formalisés et le terme data mining a été adopté.
Beaucoup d’institutions possèdent des quantités de données colossales (les banques, les entreprises,…). Il était clair que ces données renfermaient beaucoup d’informations mais comment trouver ces informations. La réponse fut le data mining avec un slogan très attractif:
« trouver du diamant dans une mine de charbon ». En effet le data mining permet de trouver de l’information utile et utilisable dans des amas de données inexploitables à cause de leurs tailles. De plus le data mining découvre, proprement dit, l’information et ne se limite pas à de simples requêtes de recherche d’informations.Le data mining est une phase faisant partie d’un processus plus général appelé KDD (Knowlegde Discovery in Databases), appelé en français, ECD (Extraction de Connaissances à partir des Données).

K plus proches voisins (KNN K Nearest Neighbours)

Cet algorithme  appartient à la famille dite apprentissage basé mémoire. Son principe est très simple. Il n’y a pas de phase d’apprentissage proprement dit.
Car l’algorithme ne fait que mémoriser les exemples qu’on lui fourni (exemples et leurs classes correspondantes). Dans la phase d’exploitation, lorsque on lui présente un exemple X à classifier, l’algorithme cherche dans les exemples qu’il a mémorisés, les k exemples qui lui sont les plus proches. Puis parmi ces derniers, l’algorithme cherche la classe majoritaire et conclue que c’est la classe à attribuer à l’exemple X.
Pour la valeur de k, on peut la fixer au préalable. Cependant une valeur très faible de k, rend le classificateur très sensible au bruit et une valeur trop élevée rend le modèle moins précis. Une technique simple pour fixer k est de l’obtenir en testant toutes ses valeurs possibles et en prenant celle qui minimise l’erreur. On a dit aussi qu’un exemple X est classifié avec la classe de ses k plus proches voisins.
l’auteur propose de pondérer les voisins avec des poids inversement proportionnels à leur distance de l’exemple X. Un autre paramètre important aussi de cet algorithme est le choix de la distance. Ce paramètre aussi peut être fixé par tâtonnement.
Et pour k = 3, le nouvel exemple va être classé dans la famille des carrés. Un des problèmes majeurs de l’algorithme KNN est qu’il exige un temps de calcul considérable durant la phase d’exploitation. En effet, parcourir tous les exemples pour rechercher les plus proches à chaque interrogation, n’est pas très attractif. Pour y remédier, des solutions ont été proposées pour agréger les exemples soit en ne gardant que les exemples opportuns soit en reconstruisant un nouvel ensemble modèle ,à partir des exemples d’apprentissage.

Réseau de neurones

Plus un réseau comporte de neurones, plus son pouvoir expressif augmente. Pour donner un ordre de grandeur: le cerveau d’une fourmi comporte quelques milliers de neurones, celui d’un chien quelques millions et celui d’un homme quelques milliers de milliards. Sachant cela il est tentant d’utiliser un grand nombre de neurones pour construire un équivalent au cerveau humain ou pourquoi pas plus Malheureusement disposer d’un nombre élevé de neurones ne constitue pas pour autant une entité intelligente. Car tous ces neurones doivent être interconnectés correctement pour fonctionner en harmonie. Ceci se fait durant la phase d’apprentissage, cette phase est d’autant plus lente que le nombre de neurones est grand.
Si un neurone est caractérisé par ses poids synaptiques, sa fonction de transfert et sa fonction d’activation, un réseau de neurones lui est caractérisé par le type de ses neurones, leurs nombres et le type de maillage qui existe entre eux. On peut avoir un réseau complètement connecté où tous les neurones sont connectés les uns au autres ou bien un réseau partiellement connecté. On peut aussi avoir un réseau organisé en couches, un réseau avec ou sans rétroaction, un réseau organisé en modules. Il faut aussi savoir qu’un réseau de neurones est aussi caractérisé par son algorithme d’apprentissage.

Le surapprentissage dans les arbres de décision 

Un arbre de décision s’il est construit de façon à s’adapter de manière exacte aux données d’apprentissage, a de grande chance d’avoir de médiocres résultats sur des données autres que celles utilisées en apprentissage. Ce qui est évidemment un problème majeur, puisque cela remet en question toute l’utilité de cet arbre. Donc pour résoudre ce problème on utilise ce que on appel : l’élagage. L’élagage est une technique qui permet d’augmenter considérablement le pouvoir de généralisation de l’arbre. Comme son nom l’indique, cette technique se débarrasse de certaines branches de l’arbre. On a deux types d’élagage :
Le préélagage :
Dans ce cas il n’y a pas d’élagage proprement dit. Ici on veille à construire un arbre capable de généraliser dés le début de la construction. Pour cela, on introduit dans les conditions d’arrêt de l’algorithme, des paramètres qui vont volontairement empêcher la construction d’arbre ‘‘parfait’’. De cette manière, on évite que l’arbre obtenu ne se spécialise
dans les données d’apprentissage.L’atout majeur de ce type d’élagage est que le temps de construction de l’arbre est plus court qu’avec la technique de postélagage.
Le postélagage :
Dans ce cas il y a une réelle étape d’élagage. Celle-ci aura lieu après la construction de l’arbre sur l’ensemble d’apprentissage. Durant la phase de construction de l’arbre, un nœud n’est transformé en feuille que si le nœud est pure (il ne contient qu’une seule classe) ou s’il ne reste plus de tests possibles capable de diviser ce noeud. Donc à la fin de la première phase, on obtient un arbre très long avec beaucoup de petites feuilles (feuilles qui contiennent peu d’éléments de l’ensemble d’apprentissage). La phase d’élagage se fait avec un ensemble de tests différents de l’ensemble d’apprentissage. L’avantage avec le postélagage, est que si on peut construire un arbre (ou une branche de l’arbre) qui peut être à la fois précis(e) et avec un grand pouvoir de généralisation, cet arbre (ou cette branche) sera vraiment construit(e). Par contre avec la technique de préélagage, ce genre d’arbre (ou branche) sera éliminé(e) d’emblé.

Algorithme CART (Classification And Regression Trees) 

Cet algorithme a été proposé par L. Breiman, J. H. Friedman, R. A. Olshen et C. J. Stone en1984 . Cet algorithme produit des arbres binaires, c’est-à-dire, chaque nœud parent a uniquement deux nœuds fils. Il peut être utilisé pour tous types de données que se soient des données à attributs binaires, des données à attributs multimodales ou des données à attributs continus. Au niveau de chaque nœud on a un nombre fini de tests possibles. Ce nombre est la somme des tests possibles sur chaque attribut. Le nombre de tests possibles sur un attribut dépend de sa nature et du nombre de ces valeurs possibles. Lorsque l’attribut sur lequel se fait le test est binaire le nombre de tests candidats est un (soit l’exemple porte la première valeur pour cette attribut soit il porte la deuxième valeur). Lorsque l’attribut sur lequel se fait le test est ordonné discret, il y’aura autant de tests candidats que de valeurs capable de séparer les valeurs possibles de l’attribut en deux sous ensembles. Lorsque l’attribut sur lequel se fait le test est continu, on se ramène au cas ordonné discret. L’astuce consiste à ne garder que les valeurs de l’attribut réellement présentes dans les exemples d’apprentissage. Et enfin lorsque l’attribut sur lequel se fait le test est multimodale non ordonné, il y’aura autant de tests candidats que d’éléments dans l’ensemble des parties de l’ensemble des valeurs de l’attribut. Cet algorithme est aussi le premier à implémenter la technique du postélagage.

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1 : PRESENTATION GENERALE DU DATA MINING 
I-1) INTRODUCTION
I- 2) APPRENTISSAGE AUTOMATIQUE 
I-2-a) Apprentissage supervisé
I-2-b) Apprentissage non supervisé
I-2-c) Apprentissage semi supervisé
I-2-d) Apprentissage paramétrique vs apprentissage non paramétrique
I-2-e) La classification
I-2-f) Le clustering (ou segmentation)
I-2-g) La régression
I-2-h) les règles d’associations
I-3) LE RISQUE 
I-3-1) le risque réel
I-3-2) le risque empirique
I-3-3) Le risque structurel
I-4) METHODES DE VALIDATION 
I-4-1) Validation statistique
I-4-2) Validation par expertise
I-5) CONCLUSION 
CHAPITRE 2 : TOUR D’HORIZON DU DATA MINING
INTRODUCTION
II-1) METHODES DE CLASSIFICATION 
II-1-1) Classificateur Naïf de Bayes (Naïves Bayes Classifier)
II-1-2) K plus proches voisins (KNN K Nearest Neighbours)
II-1-3) Les Réseaux de neurones
II-1-3-1) Le Perceptron
II-1-3-2) ADALINE
II-1-3-3) Réseau de neurones
II-1-3-4) Le Perceptron Multi Couches (PMC)
II-1-3-5) Les Réseaux à Fonction de base Radial (RBF)
II-1-4) Les arbres de décisions (decision trees)
II-1-4-1) Arbre de classification ( Principe des arbres de décision)
II-1-4-2) Arbre de régression
II-1-4-3) Construction d’un arbre de décision
II-1-4-4) Le surapprentissage dans les arbres de décision
II-1-4-5) Quelques algorithmes de construction d’arbre de décision
II-1-4-5-1) Algorithme CHAID (CHi-2 Automatic Interaction Detection)
II-1-4-5-2) Algorithme CART (Classification And Regression Trees)
II-1-4-5-3) Algorithme C4.5
II-2) DETECTION DE CLUSTERS
II-2-1) Méthodes par partitionnement
II-2-1-1)Clustering avec k-moyennes (k-means)
II-2-1-2)Clustering avec les K-moyennes floues (fuzzy K-means)
II-2-2) Méthodes Hiérarchiques
II-2-2-1) Clustering hiérarchique ascendant
II-2-2-2)Clustering hiérarchique descendant
II-2-3) Méthodes basées sur la densité
II-2-4) Méthodes basées sur un découpage (Grid based )
II-2-5) Méthodes basées sur les modèles
II-2-5-1) Clustering avec mélange de gaussiennes
II-2-5-2) La carte auto organisatrice de Kohonen
II-2-6) Clustering semi supervisé
II-3) REGLES D’ASSOCIATION
II-3-1) présentation et définition
II-3-2) Algorithme Apriori de recherche de règles
II-3-3) Algorithme AprioroTID
II-3-4) Algorithme Partitionné
II-3-5) Algorithme de comptage dynamique (Dynamic Itemset Counting)
II-3-6) Algorithme BitMap
II-3-7) Algorithme de découverte de règles multi niveaux
II-3-8) Algorithme de recherche de règles d’association avec des items pondérés
II-3-10) Algorithme de recherche de règles d’association quantitative
II-4) CONCLUSION
CHAPITRE 3 : PRESENTATION DES SVM
3-1) INTRODUCTION
3-2) SVM POUR LA CLASSIFICATION
3-2-1) SVM pour la classification (cas linéaire)
3-2-1-1) SVM à marge dure
3-2-1-2) SVM avec marge molle
3-2-2) SVM pour la classification (cas non linéaire)
3-3) SVM POUR LA REGRESSION (CAS LINEAIRE)
3-3-1) SVM pour la régression (cas linéaire)
3-3-2) SVM pour la régression (cas non linéaire)
3-4) LES FONDEMENTS THEORIQUES DES SVM
3-4-1) La VC dimension
3-4-2) Principe de la minimisation du risque structurel (SRM)
3-4) FONCTIONNEMENT DES SVM
3-5) CONCLUSION
CHAPITRE 4 : ALGORITHMES POUR LES SVM
4-1) INTRODUCTION
4-2) METHODES BASEES SUR LA DECOMPOSITION
4-2-1) Algorithme Chunking
4-2-2) Algorithme de Décomposition
4-2-2) Algorithme SMO
4-3) ALGORITHMES BASES SUR D’AUTRES FORMULATIONS MATHEMATIQUES DU SEPARATEUR
4-3-1) Algorithme kernel Adatron
4-3-2) Algorithme SOR SVM
4-3-3) Smooth SVM
4-3-4) SVM avec L1 et L+∞
4-3-4-1) SVM avec L1
4-3-4-2) SVM avec L+∞
4-3-5) Proximal SVM
4-4) ALGORITHME BASE SUR LA REDUCTION DE L’ENSEMBLE D’APPRENTISSAGE
4-4-1) Random Sampling the data
4-4-2) Active Learning with SVM
4-4-3) Algorithme CB-SVM
4-4-4) Algorithme CB-SOCP
4-5) CONCLUSION
CHAPITRE 5 : CONTRIBUTION, REALISATION ET DISCUTIONS
5-1) INTRODUCTION
5-2) SMOWR (SMO WITH WEIGHTED RAY)
5-2-1) SMOWR pour le cas linéaire
5-2-2) SMOWR pour le cas non linéaire
5-3) CONVERGENCE DE SMOWR
5-4) EXPERIMENTATION
5-5) CONCLUSION
CONCLUSION ET PERSPECTIVES

Télécharger le rapport complet