第 1 页
Stéphane Tufféry Statisticien - Data Miner - Enseignant DATA MINING - SCORING STATISTIQUE DÉCISIONNELLE APPLICATION AU CRM 19/02/2006 © 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 - Consulting • L’analyse et la préparation des données • Techniques descriptives de data mining • Techniques prédictives de data mining • Logiciels de statistique et de data mining • Informatique décisionnelle et de gestion • CNIL et limites légales du data mining • Le text mining • Le web mining 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 2 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 2 页
Techniques descriptives Points forts et points faibles 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 3 Sondage sur www.kdnuggets.com (novembre 2003) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 4 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 3 页
Sondage sur www.kdnuggets.com (février 2005) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 5 Techniques descriptives de data mining : La classification 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 6 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 4 页
Qu’est-ce que la classification ? • Regrouper des objets en groupes, ou classes, ou familles, ou segments, ou clusters, de sorte que : • 2 objets d’un même groupe se ressemblent le + possible • 2 objets de groupes distincts diffèrent le + possible • le nombre des groupes est parfois fixé • Méthode descriptive : • pas de variable cible privilégiée • décrire de façon simple une réalité complexe en la résumant • Utilisation en marketing, médecine, sciences humaines… • Les objets à classer sont : • des individus • des variables 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 7 Complexité du problème • Le nombre de partitions (non recouvrantes) de n objets est le nombre de Bell : 1 ∞ kn B = ∑ n e k! • k=1 Exemple : pour n = 4 objets, on a B = 15, avec n • 1 partition à 1 classe (abcd) • 7 partitions à 2 classes (ab,cd), (ac,bd), (ad,bc), (a,bcd), (b,acd), (c,bad), (d,abc) • 6 partitions à 3 classes (a,b,cd), (a,c,bd), (a,d,bc), (b,c,ad), (b,d,ac), (c,d,ab) • 1 partition à 4 classes (a,b,c,d) • Exemple : pour n = 30 objets, on a B = 8,47.1023 • 30 B > exp(n) => Nécessité de définir des critères de bonne n classification et d’avoir des algorithmes performants 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 8 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 5 页
La classification nb de produits âge revenus 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 9 Terminologie : de nombreux synonymes • Classification, ou classification automatique, terme généralement employé par les auteurs français • attention : il est employé dans un autre sens par les anglo- saxons (qui disent « classification » pour désigner la technique prédictive que les français appellent « classement ») • Segmentation : terme employé en marketing (les « segments de clientèle ») et assez explicite • Typologie, ou analyse typologique • Clustering : terme anglo-saxon le plus courant • Taxinomie ou taxonomie (biologie, zoologie) • Nosologie (médecine) • Reconnaissance de forme non supervisée • ... 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 10 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 6 页
Structure des données à classer • Soit une matrice rectangulaire dont : • lignes = individus • colonnes = variables • Cette structure permet de classer individus ou variables • Soit une matrice carrée de similarités, distances entre : • individus • ou variables (par exemple : la matrice des corrélations) • Cette structure permet aussi de classer individus ou variables 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 11 Structure des classes obtenues • Soit 2 classes sont toujours disjointes : méthodes de partitionnement • généralement, le nombre de classes est défini a priori • certaines méthodes permettent de s’affranchir de cette contrainte (analyse relationnelle, méthodes paramétriques par estimation de densité comme la proc SAS/MODECLUS) • Soit 2 classes sont disjointes ou l’une contient l’autre : méthodes hiérarchiques • ascendantes (agglomératives) • descendantes (divisives) • Soit 2 classes peuvent avoir plusieurs objets en commun (classes « empiétantes » ou « recouvrantes ») • analyse « floue », où chaque objet a une certaine probabilité d’appartenir à une classe donnée 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 12 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 7 页
Les différentes méthodes • Méthodes hiérarchiques • ascendantes (agglomératives) • basées sur une notion de distance ou de densité • descendantes (divisives) • Méthodes de partitionnement • centres mobiles, k-means et nuées dynamiques • k-modes, k-prototypes, k-représentants (k-medoids) • réseaux de Kohonen • méthodes basées sur une notion de densité • méthode « de Condorcet » (analyse relationnelle) • Méthodes mixtes • Analyse floue (fuzzy clustering) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 13 Applications de la classification • Marketing : découper la clientèle en segments dotés chacun d’une offre et d’une communication spécifique • Commercial : répartir l’ensemble des magasins d’une enseigne en établissements homogènes du point de vue type de clientèle, CA, CA par rayon (selon type d’article), taille du magasin… • Médical : déterminer des groupes de patients susceptibles d’être soumis à des protocoles thérapeutiques déterminés, chaque groupe regroupant tous les patients réagissant identiquement • Sociologie : découper la population en groupes homogènes du point de vue sociodémographique, style de vie, opinions, attentes… 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 14 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 8 页
Classification générale de la clientèle • Détection des profils : • clients dont on est la 2de banque • clients avec faibles encours mais 1ère banque chez nous • clients à tendance « épargne » • clients à tendance « crédit consommation » • clients à tendance « crédit habitat » • … • Utilisation pour : • les ciblages des actions commerciales • l’évaluation du potentiel commercial • l’affectation des clients aux différents types de commerciaux 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 15 Représentation des classes 10 patrimoine - âge 5 P C R 2 0 crédit conso - CB-5 0 5 10 faibles revenus forts revenus PCR1 S1 : rouge S4 : orange S2 : vert S5 : bleu S3 : rose S6 : noir 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 16 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 9 页
Noeud 0 Catégorie % n Représentation des classes6 42,55 71577 2 11,80 19848 3 11,03 18560 4 6,99 11766 1 20,22 34011 5 7,40 12450 Total (100,00) 168212 Noeud 1 Noeud 2 Catégorie % n Catégorie % n 6 100,00 64771 6 6,58 6806 2 0,00 0 2 19,19 19848 3 0,00 0 3 17,94 18560 4 0,00 0 4 11,37 11766 1 0,00 0 1 32,88 34011 5 0,00 0 5 12,04 12450 Total (38,51) 64771 Total (61,49) 103441 Identification Noeud 3 Noeud 4 Catégorie % n Catégorie % n 6 5,02 1734 6 7,36 5072 des classes par 234 0,160,010,37 127543 234 28,7426,9516,90 197941855711639 1 94,19 32563 1 2,10 1448 un arbre de 5 0,27 92 5 17,94 12358 Total ( 20,55) 34573 Total ( 40,94) 68868 décision Noeud 5 Noeud 6 Catégorie % n Catégorie % n 6 10,28 3362 6 4,73 1710 2 57,00 18959 2 2,31 835 3 0,00 0 3 51,29 18557 4 30,58 9996 4 4,54 1643 1 1,14 373 1 2,97 1075 5 0,00 0 5 34,16 12358 Total (19,43) 32690 Total ( 21,51) 36178 Noeud 7 Noeud 8 Noeud 9 Noeud 10 Catégorie % n Catégorie % n Catégorie % n Catégorie % n 6 8,71 2223 6 15,88 1139 6 3,78 766 6 5,94 944 2 74,30 18958 2 0,01 1 2 1,49 303 2 3,35 532 3 0,00 0 3 0,00 0 3 32,37 6565 3 75,43 11992 4 15,53 3963 4 84,11 6033 4 5,21 1057 4 3,69 586 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr1 1,46 373 1 0,00 0 1 5,30 1075 1 0,00 0 17 5 0,00 0 5 0,00 0 5 51,84 10514 5 11,60 1844 Total (15,17) 25517 Total (4,26) 7173 Total ( 12,06) 20280 Total ( 9,45) 15898 Techniques de classification : La classification d’individus 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 18 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 10 页
Intérêt de la classification pour la prédiction • Classification ⇓ • Homogénéité des groupes d’individus ⇓ • Moins de variables discriminantes • (éventuellement, valeurs manquantes complétées) ⇓ • + grande fiabilité des prédictions 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 19 Critères de bonne classification • Détecter les structures présentes dans les données • Permettre de déterminer le nombre optimal de classes • Fournir des classes bien différenciées • Fournir des classes stables vis-à-vis de légères modifications des données • Traiter tous les types de variables (continues, ordinales et nominales) • Traiter efficacement les grands volumes de données 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 20 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 11 页
Classification avec des variables continues • Nécessité de standardiser les variables si elles ne sont pas toutes mesurées dans la même unité et ont des variances dissemblables • Préférable d’isoler les « outliers » (individus hors-norme) • Quand on a des variables catégorielles ⇒ possibilité de se ramener à une classification de variables continues par une ACM 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 21 Inertie d’un nuage d’individus • Inertie totale I de la population : moyenne (pondérée TOT par le poids de chaque individu – généralement 1/effectif) des carrés des distances des individus au barycentre • Inertie intraclasse I : somme des inerties totales de A chaque classe • Inertie interclasse I : moyenne (pondérée par la somme R des poids de chaque classe) des carrés des distances des barycentres de chaque classe au barycentre global • Formule de Huygens : I = I + I TOT A R ∑ ∑ ∑ ∑ ∑ ( ) p (x − x)2 = p (x − x )2 + p x − x 2 i i i i j i j i∈I j∈classesi∈I j j∈classesi∈I j 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 22 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 12 页
Inertie et qualité d’une classification • Une classe est homogène ⇔ son inertie est faible • Deux critères de bonne classification : grande I , petite I • R A Ces deux critères sont équivalents d’après la formule de Huygens : I = I + I TOT A R inertie interclasse + inertie totale = inertie intraclasse 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 23 Mesures de qualité d’une classification • R² = proportion de la variance expliquée par les classes • rapport I / I R-Squar ed1. 0 R TOT 0. 9 • être le plus proche possible de 1 0. 8 0. 7 sans avoir trop de classes 0. 6 0. 5 • s’arrêter après le dernier saut 0. 4 0. 3 0. 2 important 0. 1 0. 0 1 2 3 4 5 6 7 8 9 Number of Cl ust er s • Pseudo F = mesure la séparation entre toutes les classes • rechercher une grande valeur • avec n = nb d’observations R² • et c = nb de classes c −1 • 1− R² on a pseudo F = n−c 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 24 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 13 页
Mesures de qualité d’une classification • Cubic clustering criterion (CCC) • > 2 : bonne classification • entre 0 et 2 : classification peut-être OK mais à vérifier • < 0 : présence d’outliers gênants (surtout si CCC < - 30) Cubi c Cl ust eri ng Cri t eri on un creux pour k 5 4 classes suivi d’un pic 3 2 pour k+1 classes 1 0 indique une bonne - 1 classification en k+1 - 2 - 3 classes (surtout si on - 4 - 5 a une î ou une ì - 6 - 7 douce à partir de k+2 - 8 classes) - 9 1 2 3 4 5 6 7 8 9 • Number of Cl ust ers Ne pas utiliser CCC et pseudo F avec single linkage 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 25 Mesures de qualité d’une CAH • R² semi-partiel (SPRSQ) = mesure la perte d’inertie interclasse provoquée en regroupant 2 classes • le but étant d’avoir une inertie interclasse maximum, on recherche un faible SPRSQ suivi d’un fort SPRSQ à l’agrégation suivante ó un pic pour k classes et un creux pour k+1 classes indique une bonne classification en k+1 classes Semi -Par t i al R- Squar ed 0. 35 0. 34 0. 33 0. 32 0. 31 0. 30 0. 29 0. 28 0. 27 0. 26 0. 25 0. 24 0. 23 0. 22 0. 21 0. 20 0. 19 0. 18 0. 17 0. 16 0. 15 0. 14 0. 13 0. 12 0. 11 0. 10 0. 09 0. 08 0. 07 0. 06 0. 05 0. 04 0. 03 0. 02 0. 01 1 2 3 4 5 6 7 8 9 Number of Cl uster s 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 26 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 14 页
Classification hiérarchique ascendante • Utilisables dès que l’on dispose d’une distance : dans un espace des individus ou des variables • Schéma de l’algorithme : 1) les classes initiales sont les observations 2) on calcule les distances entre classes 3) les 2 classes les plus proches sont fusionnées et remplacées par une seule 4) on reprend en 2) jusqu’à n’avoir plus qu’une seule classe, qui contient toutes les observations • Résultat sous forme d’un arbre appelé dendrogramme : • le niveau où l’on coupe l’arbre détermine le nb de classes • la hauteur d’une branche est proportionnelle à la perte d’inertie interclasse (R² semi-partiel) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 27 Classification hiérarchique ascendante couper ici avant une forte perte d’inertie interclasse 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 28 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 15 页
Les différentes distances utilisées 1/3 • Distance moyenne entre 2 observations a ∈ A et b ∈ B • tend à produire des classes de variances égales • « saut moyen » ou « average linkage » • Distance entre les barycentres de A et B • plus robuste aux outliers mais moins précise • « distance des barycentres » ou « centroid method » • Distance maximale entre 2 observations a ∈ A et b ∈ B • tend à produire des classes de diamètres égaux • très sensible aux outliers ! • peu utilisée • « saut maximum » ou « critère du diamètre » ou « complete linkage » 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 29 Les différentes distances utilisées 2/3 • Distance minimale entre 2 observations a ∈ A et b ∈ B • sait détecter les classes allongées/irrégulières voire sinueuses • sensible à « l’effet de chaîne » : 2 classes bien distinctes mais reliées par une série de points isolés vont se retrouver regroupées • moins adaptée pour détecter les classes sphériques • bonnes propriétés théoriques • fréquemment utilisée • « saut minimum » ou « single linkage » • Méthode par maximisation de la vraisemblance • peu usitée • temps de traitement en n3 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 30 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 16 页
Les différentes distances utilisées 3/3 • Critère de Ward (baisse d’inertie interclasse résultant de la fusion des 2 classes) • correspond à l’objectif d’avoir la plus forte inertie interclasse possible ⇒ avoir la plus faible baisse d’inertie en fusionnant 2 classes • la distance de 2 classes A et B, de barycentres a et b, et d’effectifs n et n vaut : d(a,b)² A B d(A,B) = 1 1 + n n A B • tend à produire des classes sphériques et de mêmes effectifs – peu efficace sur les classes allongées • très sensible aux outliers • méthode la plus utilisée (fonctionne bien sur les pbs réels) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 31 Influence du choix de la distance 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 32 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 17 页
Effet de chaîne 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 33 Les méthodes non paramétriques en CAH (estimation de densité) • 3 étapes : • estimation de la densité selon une certaine méthode : • plus proches voisins (la densité en un point x = nb d’observations dans une sphère centrée sur x, divisé par le volume de la sphère) • méthode des noyaux uniformes • méthode hybride de Wong (utilise les k-means dans une analyse préliminaire) • on définit une distance d entre 2 classes comme P inversement proportionnelle à la densité au milieu de ces 2 classes (ou d = ∞ si les 2 classes sont non adjacentes) P • CAH selon la méthode du saut minimum appliquée à d • P La densité de probabilité est un paysage vallonné dont les montagnes sont les classes et les fonds des vallées sont les frontières 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 34 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 18 页
Illustration de la CAH 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 35 Illustration de la CAH (suite) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 36 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 19 页
Illustration de la CAH (autre cas) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 37 Illustration de la CAH (fin) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 38 PDF created with pdfFactory Pro trial version www.pdffactory.com
第 20 页
Avantages de la CAH • Permet de classer : des individus, des variables, des moyennes de classes obtenues en sortie d’un algorithme des centres mobiles • si on classe des moyennes, on améliore les résultats si on connaît non seulement les moyennes des classes, mais aussi les inerties intraclasses et les effectifs des classes • S’adapte aux diverses formes de classes, par le choix de la distance • Permet de choisir le nombre de classes de façon optimale, grâce à des indicateurs de qualité de la classification en fonction du nombre de classes • R² semi-partiel et pseudo T² 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 39 Méthode des centres mobiles • 1) On choisit k individus c , …, c • 1 k 2) On regroupe les autres individus autour des centres définis à l’étape 1, en sorte que le groupe de c soit i constitué des individus plus proches de ci que de tout autre centre • 3) On remplace les individus de l’étape 1 par les barycentres des groupes définis à l’étape 2 • 4) Comme l’étape 2 • … • n) On s’arrête quand l’inertie intraclasse, qui décroît d’une partition à la suivante, ne diminue plus sensiblement (en général n ≤ 10) 19/02/2006 © Stéphane Tufféry - Data Mining & Scoring - http://data.mining.free.fr 40 PDF created with pdfFactory Pro trial version www.pdffactory.com
评论 (0)
暂无评论。快来抢沙发吧！