Trang 1
Stéphane Tufféry Statisticien - Data Miner - Enseignant DATA MINING - SCORING STATISTIQUE DÉCISIONNELLE APPLICATION AU CRM 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 1 Plan du cours • Qu’est-ce que le data mining ? • A quoi sert le data mining ? • Les 2 grandes familles de techniques • Le déroulement d’un projet de data mining • Coûts et gains du data mining • Facteurs de succès - Erreurs à éviter • Informatique décisionnelle et de gestion • La préparation des données • Techniques descriptives de data mining • Techniques prédictives de data mining : les réseaux de neurones, SVM et algorithmes génétiques • Logiciels et consultants • CNIL et limites légales du data mining • Le text mining • Le web mining 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 2 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 2
Technique de classement ou de prédiction : Les réseaux de neurones 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 3 Les réseaux de neurones • Un réseau de neurones : ensemble de nœuds connectés entre eux, chaque variable correspondant à un nœud • Le plus courant est le perceptron : n1 n2 p1 s(n1p1 + … p2 + n p ) DW n3 p Σ k k 3 p4 n4 p5 couche de sortie n5 couche d'entrée 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 4 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 3
Principe du perceptron multicouches • Lors de l’apprentissage du réseau de neurones, pour chaque exemple présenté en entrée, la valeur renvoyée (« rétropropagée ») par le nœud de sortie est comparée à la valeur réelle, et les poids p sont ajustés • i La fonction de combinaison Σnp (produit scalaire) est i i i suivie d’une fonction de transfert : souvent la sigmoïde • s(x) = 1 / [1 + exp(-x)] • L’échantillon d’apprentissage est parcouru plusieurs fois. L’apprentissage s’achève lorsque 1) une solution optimale a été trouvée ou 2) un nb fixé d’itérations a été atteint • L’apprentissage se fait en ajustant 1 à 1 chaque poids (rétropropagation), ou par modification aléatoire des poids suivie d’un mécanisme de sélection (algorithme génétique) 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 5 La fonction logistique Fonction Sigmoïde 1,2 1 0,8 0,6 0,4 1/(1+exp(-x)) 0,2 0 -5 -1 3 -4,2-3,4-2,6-1,8 -0,20,6 1,4 2,2 3,8 4,6 x 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 6 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 4
Les réseaux à couches cachées • On augmente le pouvoir de prédiction en ajoutant une ou plusieurs couches cachées entre les couches d’entrée et de sortie n1 p1 Σ nipi âge q 1 n2 Σ s(Σnipi) nb enfants s[Π.s(Σnipi) Σ + Θ.s(Σniqi)] revenus DW n3 Σ nq i i ... Σ s(Σniqi) n4 ... p5 q couche cachée couche de sortie n5 5 couche d'entrée 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 7 Les réseaux à couches cachées • Le pouvoir de prédiction augmente avec le nombre de nœuds des couches cachées • le nb de couches cachées est très généralement 1 ou 2 • lorsque ce nombre = 0, le réseau effectue une régression linéaire ou logistique (selon la fonction de transfert) • Mais ce dernier doit néanmoins être limité pour que le réseau de neurones ne se contente pas de mémoriser l’ensemble d’apprentissage mais puisse le généraliser • sinon, il y a sur-apprentissage • Le fait que toutes les valeurs soient comprises entre 0 et 1 permet de prendre en entrée d’un nœud la sortie d’un nœud précédent • Autre but de la normalisation des valeurs : éviter que les données avec de grandes valeurs « écrasent » les autres 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 8 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 5
Les réseaux à plusieurs sorties • La couche de sortie du réseau peut parfois avoir plusieurs nœuds, lorsqu’il y a plusieurs valeurs à prédire. n1 n2 DW n3 n4 n couche cachée couche de sortie 5 couche d'entrée 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 9 Différents réseaux de neurones • Le Perceptron multicouches est utilisé pour prédire une variable cible continue ou discrète • Le réseau à fonction radiale de base (« radial basis function » RBF) est aussi utilisé pour prédire une variable cible continue ou discrète • Généralisation de RBF : les Support Vector Machines de Vladimir Vapnik (1998) sont utilisées pour prédire une variable cible discrète • Le réseau de Kohonen effectue les analyses typologiques (clustering, recherche de segments) • Réseaux par estimation de densité de probabilité de Speckt (1990) • PNN (probabilistic neural networks) : classement • GRNN (general regression neural networks) : régression 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 10 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 6
Mise en œuvre d’un réseau • Les étapes dans la mise en œuvre d’un réseau de neurones pour la prédiction ou le classement sont : • identification des données en entrée et en sortie • normalisation de ces données • constitution d’un réseau avec une topologie adaptée • apprentissage du réseau • test du réseau • application du modèle généré par l’apprentissage • dénormalisation des données en sortie. 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 11 Quelques règles empiriques • Il faut 5 à 10 individus pour ajuster chaque poids • On recommande d’avoir 1 unité cachée (réseau RBF) ou 1 ou 2 (réseau PMC) • Un réseau à n unités d’entrée, 1 unité cachée, m unités dans la couche cachée et 1 unité de sortie a n.m+m poids • Il faut donc un échantillon d’au moins 5(n.m+m) individus pour l’apprentissage • La valeur de m est généralement comprise en n/2 et 2n • On a intérêt à diminuer n (en utilisant l’ACP par ex) • Pour un classement, m ≥ nombre de classes • L’échantillon d’apprentissage ne doit pas être trié selon un ordre significatif, qui pourrait induire le réseau en erreur • L’échantillon d’apprentissage doit couvrir tous les cas 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 12 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 7
Algorithmes d’apprentissage 1/2 • Levenberg-Marquardt • très performant (converge plus rapidement et vers une meilleure solution que la rétro-propagation) • ne fonctionne qu’avec un seul nœud en sortie • requiert une grande capacité mémoire, proportionnelle à n², avec n = nb de nœuds • => limité à des petits réseaux (peu de variables) • Descente du gradient conjugué • ses performances se rapproche de Levenberg-Marquardt en terme de convergence • applicable à des réseaux + complexes que Levenberg- Marquardt (avec éventuellement plusieurs sorties) 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 13 Algorithmes d’apprentissage 2/2 • Rétro-propagation du gradient • le plus ancien et le plus répandu • moins fiable (sensible aux minimas locaux) • utilisé sur de grands volumes de données • Propagation rapide (« quick propagation ») • pas toujours meilleurs que la rétro-propagation et parfois pire • difficile à paramétrer • Quasi-Newton • Algorithmes génétiques 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 14 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 8
Rétropropagation du gradient • Fonction d’erreur : mesure écart entre valeur attendue et valeur fournie par le réseau • Chaque n-uplet (p , p , …, p ) de poids peut être 1 2 n représenté dans un espace à n+1 dimensions, la dernière dimension représentant la fonction d’erreur ε • Surface d’erreur : ensemble des valeurs (p , p , …, p ,ε) • 1 2 n Modèles linéaires => surface d’erreur mathématiquement bien définie • Réseaux de neurones => surface d’erreur complexe • Il faut trouver son point le plus bas • Rétropropagation du gradient : déplacement sur la surface d’erreur en suivant la ligne de plus grande pente 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 15 Convergence vers une mauvaise solution C A B 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 16 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 9
Paramètres de rétropropagation • Taux d’apprentissage : contrôle l’importance de la modification des poids durant le processus d’apprentissage • = contrôle la vitesse de déplacement • + il est élevé, + l’apprentissage est rapide mais + le réseau risque de converger vers une solution globalement non optimale • Moment : agit comme un paramètre d’amortissement en réduisant les oscillations et en aidant à atteindre la convergence • = contrôle la rapidité des changements de direction sur la surface d’erreur • + il est faible, + le réseau « s’adapte au terrain » mais + l’influence des données extrêmes sur les poids se fait sentir 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 17 Contrôle interactif de l’apprentissage Un graphique en temps réel du taux d’erreur en apprentissage et en validation permet d’interrompre l’apprentissage dès l’apparition de sur- apprentissage et la hausse du taux d’erreur en validation 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 18 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 10
Réseaux PMC et RBF réseau → PMC RBF « poids » poids p i centre ωi couche(s) fonction combinaison produit scalaire Σi pixi distance euclidienne Σi (xi – ωi)² cachée(s) fonction transfert logistique s(X) = 1/(1 + exp(–X)) gaussienne Γ(X) = exp(– X²/2σ²) nb couches cachées ≥ 1 = 1 couche fonction combinaison produit scalaire Σk pkxk combinaison linéaire de gaussiennes Σk λkΓk (voir ci-après) de sortie fonction transfert logistique s(X) = 1/(1 + exp(–X)) fonction linéaire f(X) = X rapidité plus rapide en mode « application plus rapide en mode « apprentissage du modèle » du modèle » 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 19 Réponse globale du réseau à chaque individu (xi) nb de noeuds∑en entrée (x −ωk )2 nb de noeudscachés 1 i i ∑ λ exp− i=1 k 2 σ 2 k=1 k 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 20 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 11
RBF : choix des paramètres initiaux • Solution simple • nombre de nœuds : + grand qu’avec le perceptron • parfois plusieurs centaines • répartition uniforme des ωk • σ deux fois la distance moyenne entre les ωk • j Solution élaborée : adaptation aux données • dans les zones de forte densité en observations (adaptation aux X) et dans les zones où la donnée à prédire varie rapidement (adaptation aux Y) : • ωk plus nombreux • σk plus faibles • partitionnement par k-means ou Kohonen pour fixer les ωk • k-plus proches voisins pour fixer les σ (prendre la k distance moyenne aux k-plus proches voisins) 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 21 RBF : choix des paramètres initiaux • Importance du choix des σ k • si trop grands => manque de précision du réseau • si trop petits => sur-apprentissage => mauvaise généralisation du réseau 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 22 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 12
Comparaison PMC - RBF • PMC • meilleure capacité de généralisation, notamment sur données bruitées • risque de convergence vers un optimum local non global • paramètres plus difficiles à régler • RBF • apprentissage plus rapide • plus facile de trouver les bons paramètres • moins bonne capacité de généralisation, surtout si l’échantillon d’apprentissage ne couvre pas toutes les configurations possibles • ce sont un peu les avantages et inconvénients des réseaux à estimation de densité de probabilité 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 23 Technique de classification : Les réseaux de neurones de Kohonen 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 24 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 13
Le réseau de Kohonen • Le + utilisé des réseaux de neurones à apprentissage non supervisé • Synonymes : 1) carte de Kohonen 2) SOM (Self Organizing Map) • Pas de variable à prédire => pas de couche de sortie • Une couche d’entrée, avec un nœud pour chacune des n variables utilisées dans la classification • Une couche cachée, dont les nœuds sont disposés sous forme d’une grille généralement rectangulaire de l x m nœuds (on peut avoir l et m ≠ n), chacun de ces l x m nœuds étant connecté à chacun des n nœuds de la couche d’entrée, avec un certain poids pijk (i ∈ [1,l], j ∈ [1,m], k ∈ [1,n]) 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 25 Le réseau de Kohonen couche cachée pijk individu 1 individu 2 … couche d’entrée individu n 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 26 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 14
Apprentissage d’un réseau de Kohonen • Initialisation aléatoire des poids p • ijk Pour tout individu (x ) présenté au réseau sont k k∈[1,n] calculées les distances le séparant des l x m nœuds : ( ) ∑n ( ) d x x − p 2 ij = k ijk • k=1 Le nœud retenu pour représenter (x ) est le nœud (i,j) k pour lequel dij(x) est minimum • Ce nœud et tous les nœuds voisins voient leurs poids ajustés pijk + Θ (xk –pijk) pour les rapprocher de (xk)k∈[1,n] • Θ ∈ [0,1] : tx d’apprentissage æ pendant l’apprentissage • C’est l’ajustement des poids dans tout le voisinage du nœud « gagnant » (i,j) qui rapproche les nœuds voisins de (i,j) de l’individu (xk) • On diminue la taille du voisinage et on prend un autre (x ) k 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 27 Application d’un réseau de Kohonen • C’est comme si la grille du réseau était en caoutchouc et si on la déformait pour lui faire traverser le nuage des individus en s’approchant au + près des individus • contrairement à un plan factoriel, c’est une projection non- linéaire • mais contrairement aux k-means ou d’autres méthodes de typologie, il y a réduction de la dimension • Une fois que tous les individus de l’échantillonnage d’apprentissage ont été présentés au réseau et que tous les poids ont été ajustés, l’apprentissage est achevé. • En phase d’application, le réseau de Kohonen fonctionne en représentant chaque individu en entrée par le nœud du réseau qui lui est le plus proche au sens de la distance définie ci-dessus. Ce nœud sera le segment de l’individu. 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 28 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 15
Avantages des réseaux de neurones • Aptitude à modéliser des structures complexes et des données irrégulières • prise en compte des relations non linéaires (interactions) entre les variables • Assez bonne résistance aux données bruitées • Aptitude à modéliser des problèmes très variés 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 29 Problèmes modélisés par les réseaux de neurones • Analyse typologique • Prédiction – classement • Séries temporelles (prévision de cours boursiers) • Reconnaissance de caractères optiques et de l’écriture manuscrite (sur des chèques, lettres, signatures) • Reconnaissance/synthèse de la parole • Jeu d’échecs (Deep Blue vainqueur de Kasparov en 1997) • Reconnaissance des formes (prévention des pannes de machines par l’analyse de leurs vibrations) • Reconnaissance des visages • Analyse d’images (détecter si une gare est bondée) • Traitement du signal • Séries temporelles 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 30 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 16
Inconvénients des réseaux de neurones • Résultats totalement non explicites • rédhibitoire pour le diagnostic médical ou les pilotes automatiques d’avion • Sensibilité aux individus hors norme • Sensibilité à un trop grand nombre de variables non discriminantes • Convergence vers la meilleure solution globale pas toujours assurée • Difficulté d’utilisation correcte — paramètres nombreux et délicats à régler (nb et tailles des couches cachées, taux d’apprentissage, moment...) • Ne s’appliquent naturellement qu’aux variables continues dans l’intervalle [0,1] • multiplication des nœuds pour les variables catégorielles 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 31 Nouvelle technique de classement : Les « support vector machines » 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 32 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 17
Les Support Vector Machines • Méthode récente (1998) • famille des réseaux de neurones • Méthode de classement • Deux étapes : • transformation non linéaire Φ pour passer dans un espace de dimension plus grande (voire infinie) que l’espace d’origine, mais doté d’un produit scalaire • dans cet espace, on cherche un séparateur linéaire f(x) = a.x+b (ex : fonction discriminante de Fisher), qui est un hyperplan optimal • séparant bien les groupes (précision du modèle) – f(x) > 0 ⇒ classe A ; f(x) ≤ 0 ⇒ classe B • le + loin possible de tous les cas (robustesse du modèle) • on exprime f(Φ(x)) sans faire intervenir explicitement Φ 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 33 Exemple de transformation • Observer l’augmentation de la dimension Source : G. Saporta 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 34 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 18
Maximisation de la marge • a⋅x +b Distance d’un point x à l’hyperplan = a séparation optimale séparation correcte marge 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 35 Forme de la solution • Étant donnés les points (x,y), avec y = 1 si x ∈ A et y = i i i i i –1 si x ∈ B , trouver le séparateur linéaire f(x) = a.x+b ⇔ i trouver un couple (a,b) satisfaisant les 2 conditions : • pour tout i, y(a.x + b) ≥ 1 (bonne séparation) i i • a ² est minimum (marge maximale) • La sol. f(x) s’exprime en fonction de produits scalaires x.x’ • Après transformation Φ, la solution s’exprime en fonction de produits scalaires Φ(x).Φ(x’) • La quantité k(x,x’) = Φ(x).Φ(x’) est appelée noyau • C’est k et non Φ que l’on choisit. En s’y prenant bien, on peut calculer k(x,x’) sans faire apparaître Φ • Les calculs sont alors faits dans l’espace de départ, et sont beaucoup + simples et + rapides 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 36 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 19
Exemples de noyaux • Linéaire • k(x,x’) = x.x’ • Polynomial • k(x,x’) = (x.x’)d • si d = 2, x=(x ,x ) et Φ(x) = (x ²,√2x x ,x ²), alors 1 2 1 1 2 2 Φ(x).Φ(x’) = (x x ’ + x x ’)² = (x.x’)2 • 1 1 2 2 Gaussien (RBF) − x−x' ² • k(x,x’) = e 2σ ² • Sigmoïdal • k(x,x’) = tanh {κ(x.x’) + θ} • Intérêt des SVM : bonne résistance au sur-apprentissage 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 37 Nouvelle technique de data mining : Algorithmes génétiques 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 38 PDF created with pdfFactory Pro trial version www.pdffactory.com
Trang 20
Algorithmes génétiques • Les algorithmes génétiques cherchent à reproduire les mécanismes de la sélection naturelle, en sélectionnant les règles (<=> gènes) les mieux adaptées à la prédiction, et en les croisant et mutant jusqu’à obtention d’un modèle suffisamment prédictif. • Déroulement en 3 phases : • génération aléatoire des règles initiales • sélection des meilleures règles • génération de nouvelles règles par mutation ou croisement • la phase 3 bouclant sur la phase 2 jusqu’à la fin du déroulement de l’algorithme. 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 39 Génération initiale et sélection • Les premières règles sont aléatoirement générées • Elles doivent toutes être distinctes • Chaque règle contient un nombre aléatoire de variables, chacune avec une modalité aléatoirement choisie. • Les règles sont évaluées au vu de l’objectif à atteindre • Les règles sont retenues avec une probabilité d’autant plus grande que la règle sera meilleure • Les règles retenues doivent être satisfaites par un nombre minimum d’individus • Certaines règles vont disparaître, tandis que d’autres seront sélectionnées plusieurs fois. 02/12/2004 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 40 PDF created with pdfFactory Pro trial version www.pdffactory.com
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!