Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

03/05/2013 Fodé CAMARA Fodé CAMARA 1 1 Cours Datamining Cours Datamining Dr. F.

03/05/2013 Fodé CAMARA Fodé CAMARA 1 1 Cours Datamining Cours Datamining Dr. F. CAMARA fode.camara@ucad.edu.sn ISI-Institut Supérieur d’Informatique Techniques de datamining La classification Elle permet de prédire si une instance de donnée est membre d’un groupe ou d’une classe prédéfinie. Classes o Groupes d’instances avec des profils particuliers o Apprentissage supervisé: classes connues à l’avance  Applications: marketing direct (profils des consommateurs), grande distribution (classement des clients), médecine (malades/non malades), etc. Exemple 1: les acheteurs de voitures de sport sont de jeunes citadins ayant un revenu important Exemple 2: 45% des clients ayant fait un achat en ligne sur la page /societe/produits/produit1 sont originaires de la côte Ouest des états unis. 03/05/2013 Fodé CAMARA Fodé CAMARA 2 2 Techniques de datamining(33) La classification  Processus à deux étapes 03/05/2013 Fodé CAMARA Fodé CAMARA 3 3 Construction du modèle(2) 03/05/2013 Fodé CAMARA Fodé CAMARA 4 4 Données Apprentissage Nom Rang Année Titulaire Mary Assistant Prof 3 non James Assistant Prof 7 oui Bill Professor 2 oui John Associate Prof 7 oui Mark Assistant Prof 6 non Annie Associate Prof 3 non Algorithmes Classification Modèle Si Rang=‘Professor’ Ou Année>6 Alors titulaire=Oui Construction du modèle 03/05/2013 Fodé CAMARA Fodé CAMARA 5 5 Données Test Nom Rang Année Titulaire Tom Assistant Prof 2 non Lisa Assistant Prof 7 non Jack Professor 5 oui Ann Associate Prof 7 oui Classifier Taux d’erreur du modèle ? Construction du modèle 03/05/2013 Fodé CAMARA Fodé CAMARA 6 6 Donnée inconnue Nom Rang Année Titulaire Jeff Professor 4 ? Paul Associate Prof 7 ? Classifier Titulaire ? Oui Oui Validation de la Classification 03/05/2013 Fodé CAMARA Fodé CAMARA 7 7 Validation de la Classification 03/05/2013 Fodé CAMARA Fodé CAMARA 8 8 Techniques de datamining(34) La classification  Méthodes de Classification  Arbres de décision  Classification bayésienne Réseaux de neurones  etc. Caractéristiques Apprentissage supervisé (classes connues) 03/05/2013 Fodé CAMARA Fodé CAMARA 9 9 Techniques de datamining(35) La classification  Arbre de décision Génération d’arbres de décision à partir des données Arbre = Représentation graphique d’une procédure de classification 03/05/2013 Fodé CAMARA Fodé CAMARA 10 10 Rang? Année? Année? Oui Non Non Oui Oui Professor Assistant Prof Associate Prof <=6 >6 <=6 >6 Génération de l'arbre o Au départ, toutes les instances d’apprentissage sont à la racine de l’arbre. o Sélectionner un attribut et choisir un test de séparation(split) sur l’attribut, qui sépare le “mieux” les instances. o Partitionner les instances entre les nœuds fils suivant la satisfaction des tests logiques. o Traiter chaque nœud fils de façon récursive. o Répéter jusqu’à ce que tous les nœuds soient des terminaux. o Etiqueter le nœud terminal par la classe majoritaire A1 = ? v1 v2 v3 v'1 v'2 v'3 A2 = ? v'1 v'2 v'3 ... C1 C2 A2 = ? C3 C7 C8 C9 Arbre = ensemble de règles (A1=v1)&(A2=v'1)  C1 (A1=v1)&(A2=v'2)  C2 (A1=v1)&(A2=v'3)  C3 … (A1=v3)&(A2=v'1)  C7 (A1=v3)&(A2=v'2)  C8 (A1=v3)&(A2=v'3)  C9 A1? v1 v2 v3 v'1 v'2 v'3 A2? v'1 v'2 v'3 ... C1 C2 A2? C3 C7 C8 C9 Arbre = ensemble de règles 03/05/2013 Fodé CAMARA Fodé CAMARA 13 13 Rang? Année? Année? Oui Non Non Oui Oui Professor Assistant Prof Associate Prof <=6 >6 <=6 >6 Si Rang=‘Professor’ Ou Année>6 Alors titulaire=Oui Exemple: Procédure de construction (1) recherche à chaque niveau de l’attribut le plus discriminant Partition (nœud P) si (tous les éléments de P sont dans la même classe) alors retour; pour chaque attribut A faire évaluer la qualité du partitionnement sur A; utiliser le meilleur partitionnement pour diviser P en P1, P2, …Pn pour i = 1 à n faire Partition(Pi); Procédure de Construction (2) Processus récursif L'arbre commence à un nœud représentant toutes les données Si les objets sont de la même classe, alors le nœud devient une feuille étiqueté par le nom de la classe. Sinon, sélectionner les attributs qui séparent le mieux les objets en classes homogènes => Fonction de qualité La récursion s'arrête quand: Les objets sont assignés à une classe homogène Il n'y a plus d'attributs pour diviser Class Atr=? Mesure de qualité La mesure est appelé fonction de qualité  Goodness Function en anglais Varie selon l'algorithme : Gain d'information (ID3/C4.5) Suppose des attributs nominaux (discrets) Peut-être étendu à des attributs continus Gini Index Suppose des attributs continus Suppose plusieurs valeurs de division pour chaque attribut Peut-être étendu pour des attributs nominaux Gain d’information Sélectionner l’attribut avec le plus grand gain d’information Soient P et N deux classes et S un ensemble d’instances avec p éléments de P et n éléments de N. L’information nécessaire pour déterminer si une instance prise au hasard fait partie de P ou N est(entropie). Gain d’information Soient les ensembles {S1, S2, …, , Sv} formant une partition de l’ensemble S , en utilisant l’attribut A Toute partition Si contient p instances de P et n instances de N L’entropie, ou l’information nécessaire pour classifier les instances dans les sous-arbres Si est: Le gain d’information par rapport au branchement sur A est Choisir l’attribut qui maximise le gain Indice de GINI Utiliser l’indice Gini pour un partitionnement pur pi est la fréquence relative de la classe C dans S Si S est pur (classe unique), Gini(S) = 0 Trouver le branchement (split-point) qui minimise l’indice Gini Indice de GINI (Exemple 1) Indice de GINI (Exemple 2) Exemple d’application 03/05/2013 Fodé CAMARA Fodé CAMARA 22 22 Classifier les clients d'une banque s’ils sont à risque ou pas BD Rappel(3) 03/05/2013 Fodé CAMARA Fodé CAMARA 23 23 Evaluation d’une classification uploads/Marketing/cours-dm-classification.pdf