Data Mining ENIT Partie 1 (1) PDF - 15/12/2020

15/12/2020 Intoduction : Panorama du Data Mining Introduction...

15/12/2020 Intoduction : Panorama du Data Mining Introduction Définition du Data Mining Le processus ECD La méthodologie CRISP Quelques applications et outils Data Mining Techniques du Data Mining : descriptives et prédictives 3A INFO Le logiciel R Dr. Ines BOUZOUITA Technique prédictive (supervisée) Maitre assistante en informatique 1. Arbre de décision Contact: ines.bouzouita@enit,utm,tn 2. La méthode Random Forest Technique descriptive (non supervisée) 1. La méthode Kmeans 2. Les règles associatives 1 2 1 2 Références Exemple introductif (1/3) 1. Data Mining: Concepts and Techniques (Anglais) Relié – 2011 Demande de crédit bancaire: de Jiawei Han , Micheline Kamber , Jian Pei 2. Data Mining: Practical Machine Learning Tools and Techniques – 2016 de Ian H. Witten , Eibe Frank, Mark A. Hall , Christopher J. Pal 3. http://cedric.cnam.fr/~saporta/DM.pdf de Cédric Saporta 3 4 3 4 1  15/12/2020 Exemple introductif (2/3) Demande de crédit bancaire: Exemple introductif (3/3) Pour cela on doit disposer soit: Expert humain Système expert Système d’apprentissage 5 6 5 6 Motivations Motivations   Accroissement de la concurrence   Individualisation des consommateurs   Brièveté du cycle de vie des produits  Anticiper le marché et pas seulement réagir  Cibler au mieux la clientèle pour répondre à ses attentes  Connaissance du métier, des schémas de comportement des clients et des fournisseurs 7 8 7 8 2  15/12/2020 Motivations Motivations La grande distribution a besoin d'apprendre à connaître ses clients  La grande distribution a besoin d'apprendre à connaître ses clients Créer des relations privilégiées Créer des relations privilégiées Apprendre à évaluer un client dans la durée Apprendre à évaluer un client dans la durée   Petit commerce :   Petit commerce : Observe un client, se souvient de ses préférences Observe un client, se souvient de ses préférences Apprend des contacts passés comment améliorer le Apprend des contacts passés comment améliorer le service service futur futur 3 9 10 9 10 Le Data Mining Le Data Mining  A disposition une masse importante de données  Faire la même chose avec une entreprise de Explorer ses réservoirs de données grande taille Extraction de connaissances  Données provenant de nombreuses sources le client peut ne jamais entrer en contact avec un employé À rassembler et à organiser selon un plan cohérent et le client voit chaque fois un employé différent exploitable Exploiter les nombreuses traces enregistrées lors de À analyser, comprendre et transformer en informations l'observation du client (enregistrements transactionnels) exploitables Une solution : le data mining 4 5 11 12 11 12 3  15/12/2020 Le Data Mining DÉCOUVERTE DE MODÈLES Le data mining est l’ensemble des : algorithmes et méthodes Confiance destinés à l’exploration et l’analyse de (souvent) grandes bases de données Entrées informatiques Sortie en vue de détecter dans ces données des règles, des associations, des tendances inconnues (non Modèle fixées a priori), des structures particulières restituant de façon concise l’essentiel de x1 x2 x3 y l’information utile 1 10 100 alpha pour l’aide à la décision 8 2 20 200 beta 13 14 13 14 Le Data Mining Intelligence Statistiques Artificielle  "Trop de données tue l’information" seuls 15% des données stockées sont analysées  Objectif : favoriser la prise de décision en exploitant les tonnes d’information disponibles Data Reconnaissance modéliser pour prédire Bases de Mining des Formes données faciliter la décision mais ne prend pas de décision améliorer la réactivité d’une entreprise / marché  Défi: améliorer la productivité/ volume exponentiel de données Etc.. Génie Logiciel Extrapoler le passé pour prédire l’avenir 6 15 16 15 16 4  15/12/2020  Intérêt économique Intérêt scientifique Amélioration de la qualité des Processus d’aide à la décision où les produits et des services utilisateurs cherchent des modèles d’interprétation dans les données Passage d’un marketing de masse Extractiond’informations à un marketing individualisé auparavant inconnues et potentiellement utiles à partir des données Fidélisation des clients disponibles Favoriser la différentiation stratégique de l’entreprise 7 17 18 17 18 ECD vs Fouille de Données PRINCIPALES ÉTAPES DU PROCESSUS D’ECD Connaissances L’ECD (Extraction de Connaissances à partir de Données) est un Motifs, structures, etc. processus itératif de découverte, dans les BD larges, de modèles A->BE 4 – Interprétation et BD -> C de données valides, utiles et compréhensibles. Données … évaluation préparées A B C  Itératif : nécessite plusieurs passes o1 x x x … x x 3 – Fouille de données  Valides : valables dans le futur on x Données 2 - Pré-traitement  Utiles : permettent à l’utilisateur de prendre des décisions sélectionnées  Compréhensibles : présentation simple 1 – Intégration et L’un de ses traitements est la Fouille de données (Data Mining) Sélection Données C’est un processus interactif et itératif 14 19 20 19 20 5  15/12/2020 ECD VERSUS FOUILLE DE DONNÉES (2) BUT D’UN PROCESSUS D’ECD Découverte de motifs et de modèles (patterns) L’ECD peut être considérée comme une extension de difficiles à percevoir car : l’analyse de données afin de tenir compte de – Volume de données peut être très grand, l’augmentation du volume des données à traiter. Elle est – Nombre de variables à considérer peut être très élevé. à l’intersection de différentes disciplines telle que les statistiques, l’intelligence artificielle, les bases de  Ces motifs sont alors imprévisibles et permettent de données, les techniques de programmation, etc. refléter des tendances cachées, de dégager des règles significatives, etc. La fouille de données est l’étape centrale du processus d’ECD. Ce dernier, par le biais de la fouille de données, Orienter, par exemple, les décisions d’une entreprise ou est alors vu comme une ingénierie pour extraire des connaissances à partir des données. un groupe médical en exploitant les données collectées. 28 21 22 21 22 CRISP: Démarche méthodologique CRISP: illustration CRISP (Cross Industry Standard Process for Data Mining) est développée au départ par IBM pour réaliser les projets Data Mining. Elle présente aujourd’hui l’unique méthode utilisable efficacement pour tous les projets Data Mining et Data Science en général. 23 24 23 24 6  15/12/2020 Les données: type (1/6) Définition du Data Mining Vectorielles ou transactionnelles Le data Mining ou la fouille de données présente la découverte d'une Séquences connaissance (information intéressante) à partir de grandes quantités Structurées de données, par des méthodes automatiques.  Quels types de données? Temporelles  Qu’est ce qu’une connaissance? Spatiales  Qu’entend-on par découverte? Fortement lié à l’apprentissage automatique! 25 26 25 26 Les données: type (2/6) Les données: type (3/6) Transactionnelles Vectorielles Séquences Séquences Structurées Structurées Temporelles Temporelles Spatiales Spatiales Classe ou étiquette 27 28 27 28 7  15/12/2020 Les données: type (4/6) Les données: type (5/6) Vectorielles Vectorielles Séquences Séquences Structurées Structurées Temporelles Temporelles Spatiales Spatiales 29 30 29 30 EXEMPLE 1 (ANALYSE DES ASSOCIATIONS ENTRE LES ARTICLES Les données: type (6/6) D’UNE GRANDE SURFACE) : CONSTRUCTION DU CONTEXTE D’EXTRACTION (1) Vectorielles Séquences Supposons que l’ensemble des données soit représenté par une table (appelée aussi contexte Structurées d’extraction). Temporelles Spatiales une instance (ou objet) est représenté par un vecteur de n variables (ou attributs ou items), une table comporte m lignes (les objets) et n colonnes (les items). 16 31 32 31 32 8  15/12/2020 EXEMPLE 1 (ANALYSE DES ASSOCIATIONS ENTRE LES ARTICLES D’UNE GRANDE EXEMPLE 3 (CLASSIFICATION DES CLIENTS D’UNE BANQUE EN « SURFACE: CONSTRUCTION DU CONTEXTE D’EXTRACTION (2) SOLVABLE OU NON ») : DONNÉES HISTORIQUES montant taux du profession état civil revenus solvabilité Soit une table représentant les achats de 5 clients parmi du crédit crédit 4 articles (m = 5 et n = 4) : analyse de 5 tickets de 1000 9,5% enseignant Marié 980 Oui caisse 2000 7,4% employé Marié 1080 Non Lait Pain Huile Coca 2500 8,1% ouvrier Célibataire 1200 Oui 2200 5,3% cadre Marié 1600 Oui 1 X x x 3000 8,1% ouvrier Marié 1500 Non 2 x x 1900 6,1% profession Divorcé 2100 Oui libre 3 x x 4200 6,9% cadre Marié 1800 Oui 4 x x x 5 x x 22 33 34 33 34 EXEMPLE 3 (CLASSIFICATION DES CLIENTS D’UNE BANQUE EN « SOLVABLE OU NON ») : APPLICATION AUX NOUVEAUX CLIENTS QUELQUES DOMAINES D’APPLICATION montant du taux du profession état civil revenus solvabilité crédit crédit – Analyse de risque (assurance) 2100 7,2% employé Célibataire 1200 – Marketing - Grande distribution/surface 1900 7,4% employé Marié 1170 – Médecine - Pharmacie 3300 6,9% profession Célibataire 1900 – Analyse financière libre 1700 7,0% cadre Marié 2050 – Gestion de stocks 3100 7,3% ouvrier Marié 1200 – Maintenance 2400 6,9% employé Marié 1100 – Contrôle de qualité 4000 7,1% cadre Marié 1900 31 23 35 36 35 36 9  15/12/2020 EXEMPLE : MARKETING EXEMPLE : FINANCE (SECTEUR BANCAIRE, ETC.) Quel profil de client à cibler lors d’une compagne marketing? (marketing ciblé) Quel facteur risque associer à un demandeur de crédit?  Quel client est susceptible de réagir à une  Le client est ou non solvable? promotion déterminée? Peut on détecter un usage frauduleux d’une carte de Quel est le profil des clients de longue durée? crédit? (détection de fraudes) Quels produits proposer en achats groupés? (pour une Quels produits financiers proposer à une catégorie donnée de promotion ou autre : ventes croisées (cross selling)) clients?  Analyse du panier de la “ménagère” (Market Basket Analysis). Quels clients sont susceptibles de nous quitter pour des concurrents? etc. 32 33 etc. 37 38 37 38 Evolution du Data Mining EXEMPLE : MÉDICAL Web Mining Text Mining Quelle composition de gênes entraîne la présence d’un autre ensemble de gênes? Quels sont les symptômes d’une maladie donnée? Data Audio, Vidéo Image Mining Mining Mining Quels sont les diagnostics associés à un ensemble de symptômes? Quels sont les facteurs de guérison d’une maladie donnée? Comment prévenir une maladie donnée? Etc.. Multimédia Mining 34 etc. 39 40 39 40 10  15/12/2020 LA HIÉRARCHIE D’INTERVENTION DES ACTEURS D’UN PROCESSUS ÉVOLUTION DE LA FOUILLE DE DONNÉES (2) D’ECD Spatial et Image mining : fouille des images Modélisation des phénomènes météorologiques (détection, analyse, Potentiel de support prédiction) de décision Utilisateurs Prise Analyse et prédiction de l’urbanisation et de la déforestation de décisions Présentation des Décideurs connaissances  La nature des données dépend du domaine : du texte pour Techniques de visualisation le « text mining », un signal audio/vidéo pour l’« audio/video Data Mining Analystes mining », des pixels pour l’«image mining », etc. Découverte de connaissances de données 36 Exploration de données (Statistiques, Requêtes,...) Administrateur(s)de Sources de données bases de données (Papier, Fichiers, Fournisseurs d’information, SGBD, …) 41 42 41 42 CHOIX D’UN LOGICIEL DE DATA MINING OUTILS D’ECD Selon son prix - Quelques outils payants : - Clementine (SPSS) - Entreprise Miner (SAS) Selon son intégration possible - Intelligent Miner (IBM) Selon le problème à résoudre - Quelques outils gratuits : - Le projet Weka (librairiede classes Java) accessible à http://www.cs.waikato.ac.nz/ml/weka Selon les compétences des utilisateurs - SPMF : An Open-Source Data Mining Library accessible à www.philippe-fournier-viger.com/spmf/ - FIMI : Frequent Itemset Mining Implementations accessible à 48 www.fimi.ua.ac.be - http://www.rdatamining.com/ 43 44 43 44 11  15/12/2020 WEKA ORANGE Attributs TANAGRA (features) SIPINA Logiciel R RapidMiner KNIME AlphaMiner Statistica dataMiner http://eric.univ- Exemples Yes lyon2.fr/~ricco/tanagra/fr/contenu_tutoriaux_comparaison_logiciels.html http://chirouble.univ-lyon2.fr/~ricco/data- (Instances) mining/logiciels/revue_rapide_des_logiciels_sur_le_site_kdnuggets.pdf 45 45 46 TÂCHES DE FOUILLE DE DONNÉES (1) PARTIE 2 Une tâche est définie comme un problème que l’on cherche à résoudre, et qui dépend des données à traiter ainsi que des besoins des utilisateurs (c’est à dire les décideurs et les experts du domaine). 47 48 47 48 12  15/12/2020 TÂCHES DE FOUILLE DE DONNÉES (1) TÂCHES DE FOUILLE DE DONNÉES (3) Chaque tâche peut être réalisée par différents outils/méthodes (plus communément appelées, techniques) qui sont généralement complémentaires entre elles. Une tâche peut être soit descriptive soit prédictive : Un fait important communément admis est : " Pour une tâche donnée, il – descriptivesi elle vise à mettre en évidence des n’existe pas de technique supérieure à toutes les autres ". connaissances présentes mais cachées par le volume des données à traiter. – prédictive si elle vise à extrapoler de nouvelles informations à partir des données présentes. Elle présente une variable ou classe cible à prédire. 39 49 50 49 50 Le data mining utlise des techniques concrètes qui peuvent Les techniques prédictives (supervisées) être limitées à un type de technique spécifique ou être se basent sur des observations étiquetées ou classées. partagées par plusieurs types de techniques. Un expert (superviseur) est employé pour fournir correctement ces étiquettes. Exemple de méthodes descriptives super : la classification L’apprenant doit alors trouver ou approximer la fonction qui hiérarchique, la classification des K moyennes, les règles permet d’affecter la bonne étiquette à ces observations afin d’association. de déterminer l’output d'une observation inconnue. Il existe 2 types d’algorithmes: Exemples de méthodes prédictives : les méthodes de Régression (Prédire l’âge d’un embryon à partir de sa régression, les arbres de décision, les réseaux de neurones, taille, son poids, etc) les K plus proches voisins. Classification (Prédire qui gagne plus de 50.000$ à partir de données de recensement ) 51 52 51 52 13  15/12/2020 EXEMPLES DE TÂCHES DE FOUILLE DE DONNÉES (1) Régression: Prédire des valeurs continues (output: prix) Régression : variable cible numérique  similaire à la classification mais permet de prédire des valeurs de variables et non de classes Prédiction de prix de maison estimer la valeur d'un bien immobilier prédire la durée d'hospitalisation d'un patient estimer le retour sur investissement d'une campagne publicitaire Prix en dinars Classification : variable cible catégorique  consiste à examiner les caractéristiques d’un objet et lui attribuer une classe. filtrer les mails (spam or non) détecter les tendances boursières (hausse, baisse) diagnostiquer une maladie (positif, négatif) superficie 40 53 54 53 54 Classification: Prédire des valeurs discrètes ( 0 ou 1  malin ou bénin) Les techniques descriptives (non supervisées) Aucun expert n’est disponible. L'algorithme doit découvrir par lui-même la structure des données. Par exemple, grouper des exemples de manière à ce que les exemples au sein d'un même groupe se ressemblent suffisamment, et que les exemples de groupes différents soient suffisamment différents. Si on veut automatiquement grouper les utilisateurs du Facebook selon leurs réputations, de sorte que les utilisateurs les plus dignes de confiance (les plus réputés) appartiennent au même cluster On peut avoir 5 clusters différents (very high, high, medium, low, very low). Il existe deux approches de l’apprentissage non supervisé: Le Clustering (regroupement) Les règles d’associations 55 56 55 56 14  15/12/2020 37 EXEMPLES DE TÂCHES DE FOUILLE DE DONNÉES (2) EXEMPLE DE CLUSTERING Segmentation or regroupement (clustering)  consiste à identifier des distinctions conceptuelles dans un grand volume de données et à diviser les objets associés en groupes non connus à l’avance segmenter la clientèle (campagnes promotionnelles) détecter les groupes aberrants (fraudes, intrusions) Analyse des associations  consiste à trouver quelles valeurs des variables vont ensemble analyser le panier d'achats analyser les cours choisis par les étudiants interpréter les parcours des navigateurs sur Internet 41 57 58 57 58 CONSTRUCTION ET ÉVALUATION D’UN Analyse factorielle MODÈLE Méthodes Descriptives Clustering Clustering ( non supervisées)  Les données sont séparées en deux Associativité ensembles: Data Mining Régression Méthodes Ensemble d’apprentissage Analyse Prédictives Classification prédictive (supervisées) Ensemble test 59 60 59 60 15  15/12/2020 MATRICE DE CONFUSION VALIDATION D’UN MODÈLE  Matrice de confusion comparaison des cas observés par rapport aux prédictions  exemple : prédiction de factures impayées Prédit Observé  VN : Nombre de vrais négatifs Payé Retardé Impayé Total  FN : Nombre de faux négatifs Payé 80 15 5 100  FP : Nombre de faux positifs Retardé 1 17 2 20  VP : Nombre de vrais positifs Impayé 5 2 23 30 ie:Si le classifieur ne commet aucune erreur, c'est-à-dire qu'il prédit toujours la classe réelle, alors est une matrice diagonale (ce qui signifie que les coefficients Total 86 34 30 150 en dehors de la diagonale sont tous nuls). Validité du modèle  nombre exacte (diagonale) / nombre totale = 120/150 = 0.80 61 62 61 62 PRINCIPALES TECHNIQUES Analyse factorielle  Dérivées Méthodes Descriptives Clustering Clustering des statistiques ( non supervisées) de l'analyse de données (e.g., analyse en composantes) de l'intelligence artificielle (e.g., arbres de décision, Associativité réseaux de neurones) Data Mining des bases de données (e.g., règles associatives) Régression  Appliquées aux grandes bases de données Méthodes  Difficultés : Analyse Prédictives prédictive Classification (supervisées) passage à l'échelle et performance fonctionnement avec échantillon > qq milliers présentation et validation des résultats 63 64 63 64 16  15/12/2020 6 LES PRINCIPALES FAMILLES DE MÉTHODES DESCRIPTIVES Analyse Clustering factorielle Associativité 65 66 65 66 L'analyse factorielle plusieurs méthodes d'analyses de grands tableaux rectangulaires de données, visant à déterminer et à hiérarchiser des facteurs corrélés aux données placées en colonnes. 67 68 67 68 17  15/12/2020 69 70 69 70 71 72 71 72 18  15/12/2020 73 74 73 74 Métodes descriptives Méthodes prédictives NON SUPERVISEES SUPERVISEES 75 76 75 76 19  15/12/2020 APPRENTISSAGE SUPERVISÉ APPRENTISSAGE NON SUPERVISÉ  Modèle inductif où l’apprenant considère un  Construction d’un modèle et découverte des ensemble d’exemples, et infère l’appartenance d’un relations dans les données sans référence à objet à une classe en considérant les similarités d’autres données entre l’objet et les éléments de la classe  On ne dispose d'aucune autre information  Les classes sont étiquetées préalablement (image préalable que la description des exemples médicale, sport…)  La segmentation, le regroupement (cluster), la  La plupart des algorithmes (classification, méthode des k-moyennes et les associations sont estimation, prédiction) utilisent l’apprentissage des méthodes d’apprentissage non supervisées supervisé 77 78 77 78 20 R EST UN SYSTÈME D’ANALYSE STATISTIQUE ET GRAPHIQUE CRÉÉ PAR R. IHAKA ET R. GENTLEMAN1 Logiciel gratuit et langage qualifié de dialecte du langage S. Il est téléchargeable dans sa version 2.9.2. depuis : http://www.r-project.org/ Également disponible sous forme commercialisée S-Plus Développé par une communauté de statisticiens rassemblés dans le R Development Core Team Distribué pour Windows, Linux, Unix, Macintosh 80 79 79 80 20  15/12/2020 21 22 http://www.r-project.org/ Liens pour télécharger (gratuitement) R, des packages, de la doc, POUR VOUS GUIDER, VOUS DISPOSEZ DE NOMBREUX SITES D’AIDE etc… ET D’EXEMPLES SUR INTERNET, PAR EXEMPLE : Moteur de recherche Documentation http://zoonek2.free.fr/UNIX/48_R/all.html http://pbil.univ-lyon1.fr/R/enseignement.html 81 82 81 82 23 DE NOMBREUX TUTORIELS SONT ÉGALEMENT DISPONIBLES SUR INTERNET, PAR EXEMPLE : « R pour les débutants », Emmanuel « An introduction to R », Venables et BIENVENUE DANS R… Paradis al (en anglais) http://cran.r- http://cran.r- project.org/doc/contrib/Paradis- project.org/doc/manuals/R-intro.pdf rdebuts_fr.pdf D’autres sont disponibles sur le site de R-project : http://cran.r-project.org 83 84 (cliquer sur « Manuals » dans la sous-partie « Documentation ») 83 84 21  15/12/2020 Pour obtenir l’aide sur une commande : ?NOM_DE_LA_COMMANDE Il est indispensable avant tout travail dans R, de spécifier le dossier de travail dans lequel se trouve le (ou les) fichier(s) de données à analyser : File → Change Dir… → sélectionner le dossier Ou pour la version française : Fichier → Changer le répertoire courant… → sélectionner le dossier* Pour vérifier que vous travaillez bien dans le bon dossier, vous pouvez contrôler votre working directory par la commande : getwd() Pour utiliser une commande : nom_de_la_commande(argument1,argument2,…) 85 N.B. certains arguments sont définis par défaut pour une fonction donnée. 86 85 86 27 28 Opération Commande sous R IMPORTATION DES DONNÉES : pi pi Racine carrée sqrt Multiplication, division, addition, soustraction *, /, +, - Commande read.table(…) (voir ? read.table()) Arrondir round Moyenne, médiane, variance mean, median, var Importer des données à partir d’un fichier.txt Obtenir pour chaque variable d’un tableau : quartiles et summary moyenne Exemple : importer le fichier.txt nommé cars_dataset.txt Ecart-type sd Etendue d’une série de valeurs range ayant le format suivant : Appliquer une même fonction (FUN) à toutes les catégories Y tapply (X,Y,FUN) d’une variable X Importer des données d’un tableau read.table Créer une matrice matrix Effectuer un modèle linéaire lm(x~y*z) Représenter un nuage de points plot(y~x) Tracer une droite de régression correspondant à un modèle abline(lm) linéaire (lm)…… 87 88 87 88 22  15/12/2020 29 30 IMPORTATION DES DONNÉES : IMPORTATION DES DONNÉES : Commande Commande read.xls() (utiliser librairie xlsReadWrite) Exemple : importer le fichier.txt nommé cars_dataset.txt ayant le format suivant : Exemple : importer le fichier.xls nommé autos_dataset.xls ayant le format suivant : > don = read.table(‘cars_dataset.txt’, header=TRUE); Première ligne contient les Nom de la variable Affectation Nom du fichier noms des colonnes 89 90 89 90 31 32 IMPORTATION DES DONNÉES : EXEMPLE : IMPORTER LE FICHIER.XLS NOMMÉ OPÉRATIONS SUR LES COLONNES D’UNE TABLE AUTOS_DATASET.XLS OU UNE MATRICE : ayant le format suivant : Sélection d’une colonne : nom_table$nom_colonne Exemple : colonne PUISS de la table autos >autos$PUISS; ou aussi >autos[,2]; Sélection d’un bloc de ligne(s) ou de colonne(s) : -Sélection des trois premières colonnes de la table autos >library(xlsReadWrite); >autos[,1:3]; >autos=read.xls(‘autos_dataset.xls’,colNames=TRUE,rowNa -Sélection un bloc composé des ligne 2,5,7 et des colonnes 3,4 mes=TRUE,sheet=1) > autos[c(2,5,7),c(3,4)]; N.B. : c() permet de définir un vecteur unidimensionnel. 91 92 91 92 23  15/12/2020 Installation des packages dans R 93 94 93 94 95 96 95 96 24  15/12/2020 97 98 97 98 DU DATA MINING AU TEXT MINING Le data mining est un processus d’extraction de structures (connaissances) inconnues, valides et potentiellement exploitables dans les bases (entrepôts) de données (Fayyad, 1996), à travers la mise en œuvre des techniques statistiques et de machine learning Les données textuelles constituent également une source d’information qui permettrait d’extraire de la connaissance (détecter des régularités [patterns], recherche des similarités, identifier les relations de causalité, etc.). 99 100 99 100 25  15/12/2020 PARTIE 3 1. Exemples d’application les arbres de décision 2. Principes de base de l’apprentissage statistique avec des arbres de décision (en classification et en régression), 3. Description détaillée des implémentations les plus utilisées aujourd’hui (ID3, C4.5, C5.0 et CART). 4. La méthode CART avec l’environnement R 101 102 101 102 LA CLASSIFICATION SUPERVISÉE consiste à examiner les caractéristiques d’un objet et lui attribuer une classe. filtrer les mails (spam or non) détecter les tendances boursières (hausse, baisse) diagnostiquer une maladie (positif, négatif) 103 104 103 104 26  15/12/2020 LA CLASSIFICATION: CLASSIFIEUR LINEAIRE CLASSIFICATION: ALGORITHMES ET MODELES K-nn K-nearest neighbors (K plus proches Voisins ) Naive Bayes Régression linéaire Arbre de Décision Forêt aléatoire LightBoost, CatBoost, xgBoost, AdaBoost Support Vector Machine (SVM) Deep Learning (réseaux de neurones) 105 106 105 106 LES ARBRES DE DÉCISION LES ARBRES DE DECISION 107 108 107 108 27  15/12/2020 EXEMPLE INTRODUCTIF : EXEMPLE INTRODUCTIF : Arbres de Arbres de Décider décision si un patient est malade ou bien portant selon sa température décision et s’il a la gorge irritée temperature < 37,5 Arbre de décision Nœud intermédiaire ou test )chaque nœud intermediaire est défini par un test 2 classes (malade, bien portant) construit à partir d’une variable) OUI NON 2 variables (température, gorge irritée) temperature < 37,5 temperature 375 > malade gorge irritee OUI NON NON gorgeirritee malade OUI OUI NON bien malade portant Nœud terminal ou feuille malade bien portant 109 110 109 110 Exemple de problème adapté à un approche par arbres de décision : comment répartir une population d’individus (e.g. clients, produits, utilisateurs, etc.) en groupes homogènes selon un ensemble de variables descriptives (e.g. âge, temps passé sur un site Web, etc.) et en fonction d’un objectif fixé (variable de sortie ; par exemple : chiffre d’affaires, probabilité de cliquer sur une publicité, etc.). Voici quelques exemples où on doit classer une situation ou individu en suivant une séquence de tests. Le processus de décision est équivalent à une « descente » dans l’arbre (de la racine vers une des feuilles) : à chaque étape un attribut est testé et un sous-arbre est choisi, la parcours s’arrête dans une feuille (une décision est prise). 111 112 111 112 28  15/12/2020 ONS JABEUR VA-T-ELLE JOUER DU TENNIS? ONS JABEUR VA-T-ELLE JOUER DU TENNIS? 113 114 ARBRE DE DÉCISION: REPRÉSENTATION ARBRE DE DÉCISION: DÉFINITION Racine Nœud = attribut de test Un arbre de décision est un classifieur représenté sous forme d’un arbre tel que: les nœuds de l’arbre testent les attributs Branche = valeur de l’attribut Il y a une branche pour chaque valeur possible de l’attribut testé Les feuilles spécifient les classes (2 ou plus) Feuille= classification Parcours = Règle 115 116 29  15/12/2020 GÉNÉRALITÉ : ARBRE DE DÉCISION Arbres de dé- C’est une technique permettant de réaliser des tâches prédictives cision supervisées. -Variable cible à prédire, à partir de variables explicatives, qui peut être : En théorie des graphes, un arbre est un graphe non orienté, acyclique - qualitative (malade ou non)  cas de la classification et connexe. L’ensemble des nœuds se divise en trois catégories : - continue (valeur d’un bien immobilier)  cas de la régression Nœud racine (l’accès à l’arbre se fait par ce nœud), - Cette technique permet de créer un arbre appelé aussi classifieur dont Nœuds internes : les nœuds qui ont des descendants (ou enfants), qui l’objectif est de placer chaque individu de la sont à leur tour des nœuds, population dans une classe, parmi plusieurs classes Nœuds terminaux (ou feuilles) : nœuds qui n’ont pas de descendant. prédéfinies, en fonction des caractéristiques de l’individu décrites par des variables qualitatives et quantitatives, - Produit des classes les plus homogènes que possibles du point de vue de la variable cible à prédire. 117 118 117 118 GÉNÉRALITÉ : ARBRE DE DÉCISION Idée PRINCIPE ALGORITHMIQUEDES ARBRES DEDÉCISION Diviser récursivement et le plus efficacement possible les individus de l’ensemble d’apprentissage par des tests définis à l’aide des variables explicatives jusqu’à ce que l’on obtienne des sous-ensembles d’individus ne contenant (presque) que des individus appartenant à une même classe, Procédure construire-arbre(X) c’est-à-dire ont la même valeur de la variable cible. SI tous les individus X ont la même valeur de la variable cible Trois opérations ALORS créer un nœud feuille portant le nom de cette valeur de la variable cible 1.Décider si un nœud est terminal c’est-à-dire s’il vérifie une des conditions (ce sera ainsi la classe des individus X) d’arrêt et qui peut être par exemple : - tous les individus sont dans la même classe SINON - il n’y a plus de variables à utiliser choisir la meilleure variable pour créer un nœud //la variable qui sépare le mieux les - il y a moins d’un certain nombre d’individus dans le nœud individus X - la profondeur du nœud atteint une limite fixée le test associé à ce nœud partitionne X en des branches : Xd………Xg - le nombre de nœuds feuilles atteint un maximum fixé - etc.  construire-arbre(Xd) 2.Sélectionner un test à associer à un nœud non terminal : ce test consiste à choisir une variable aléatoirement ou en utilisant des critères statistiques  construire-arbre(Xg) 3.Affecter une classe à une feuille (nœud terminal) : la classe FIN majoritaire des individus associés à cette feuille Remarque : Les différents algorithmes vont différer par ces trois opérations 119 120 119 120 30  15/12/2020 ARBRE DE DÉCISION : APPRENTISSAGE PAR GÉNÉRATION PRINCIPE ALGORITHMIQUEDES ARBRES DE DÉCISION DE RÈGLES C’est un algorithme qui génère à partir des observations déjà classées des règles de production pour la classification. -On a besoin de comparer les différents choix possibles induits par les variables explicatives qu’on peut utiliser. Les règles de production sont sous la forme : Si [prémisse] Alors [conclusion] -Différentes fonctions sont introduites pour permettre de mesurer le degré Prémisse: conjonction de descripteurs logiques du type Attribut = de mélangeance dans les différentes classes telles que l’entropie, l’indice valeur (ou opérateur de comparaison, ou ensemble de valeurs) de Gini, etc. Conclusion : Classe = modalité. -Propriétés des fonctions : - Le minimum est atteint lorsque tous les nœuds sont “purs”. C’est un algorithme qui requiert seulement la base - Le maximum est atteint lorsque les individus sont équirepartis entre d’apprentissage, il est non paramétrique. les classes. 121 121 122 ARBRE DE DÉCISION : POURQUOI? Pour certains domaines d’application, il est essentiel de produire des procédures de classification compréhensibles par l’utilisateur. Les arbres de décision répondent à cette contrainte grâce à: La représentation graphique d’un ensemble de règles L’interprétation aisée de tel graphe Les algorithmes d’apprentissage par arbre de décision sont: Efficaces Disponibles dans la plus part des environnements de fouille de données 124 123 124 31  15/12/2020 ALGORITHME CART (CLASSIFICATION ALGORITHME CART AND REGRESSION TREES)  Utilise comme critère de séparation : Indice de Gini  Parmi les plus performants et les plus répandus IG  Entrées : avec n : nombre de classes à prédire fi : fréquence de la classe dans le nœud - p variables continues ou discrètes - unevariable supplémentaire contenant la classe de  Plus l’indice de Gini est bas, plus le nœud est pur (c’est-à-dire que plus chaque individu (c classes) tous les individus associés appartiennent à la même classe)  En séparant un nœud en n nœuds fils, on cherche la plus grande  Sortie : hausse de la pureté - un arbre de décision  La variable la plus discriminante doit maximiser : Gain = IG(avant séparation) - [IG(fils1) + … + IG(filsn)] 125 126 125 126 DEGRÉ DEMÉLANGEANCE n Test t à m modalites t = le test (la variable) m = le nombre de modalités de t IG = l’indice de Gini associé à une position (un nœud de l’arbre) donnée (c’est la fonction mesurant le degré de mélangeance)... n1 n2 nm On introduit la fonction de gain : Gain(n, t) = IG(n) - [IG(n1)+……+IG(nm)] nj = la proportion des individus du nœud n qui vont au nœud fils nj La position n est fixée  On cherche le test (la variable) qui maximise le gain 127 128 127 128 32  15/12/2020 EXEMPLE EXEMPLE 129 130 129 130 EXEMPLE EXEMPLE 131 132 131 132 33  15/12/2020 EXEMPLE EXEMPLE 133 134 133 134 EXEMPLE EXEMPLE 135 136 135 136 34  15/12/2020 EXEMPLE EXEMPLE 137 138 137 138 EXEMPLE EXEMPLE 139 140 139 140 35  15/12/2020 EXEMPLE 141 142 141 142 EXEMPLE EXEMPLE 143 144 143 144 36  15/12/2020 EXEMPLE EXEMPLE 145 146 145 146 EXEMPLE EXEMPLE 147 148 147 148 37  15/12/2020 EXEMPLE EXEMPLE 149 150 149 150 EXEMPLE EXEMPLE 151 152 151 152 38  15/12/2020 EXEMPLE EXEMPLE 153 154 153 154 EXEMPLE EXEMPLE 155 156 155 156 39  15/12/2020 EXEMPLE EXEMPLE 157 158 157 158 EXEMPLE EXEMPLE 159 160 159 160 40  15/12/2020 EXEMPLE EXEMPLE 161 162 161 162 EXEMPLE EXEMPLE 163 164 163 164 41  15/12/2020 EXEMPLE EXEMPLE 165 166 165 166 EXEMPLE EXEMPLE 167 168 167 168 42  15/12/2020 EXEMPLE EXEMPLE 169 170 169 170 DES ARBRES DE DÉCISIONS AUX RÈGLES DE CLASSIFICATION -A partir de l’arbre précédent, on peut dériver les règles de classification EXERCICE suivantes : - Si E = non Alors I = Non Donnez l’arbre de décision qui - Si E = oui ET A = jeune Alors I = Oui correspond à ce dataset! - Si E = oui ET A = moyen Alors I = Oui - Si E = oui ET A = agé Alors I = Non -Ces règles peuvent être présentées d’une manière plus optimisée comme suit : - Si (E = non) OU (E = oui et A = agé) Alors I = Non - Si (E = oui) ET (A = jeune OU A = moyen) Alors I = Oui  Dans la version succincte, on obtient ainsi une seule règle par valeur de la variable cible I (une règle