Cours DM - Classification

10/04/23 Fodé CAMARAFodé CAMARA 11

Cours DataminingCours 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.

Classeso Groupes d’instances avec des profils particulierso 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.

10/04/23 Fodé CAMARAFodé CAMARA 22

Techniques de datamining(33)

La classification Processus à deux étapes

10/04/23 Fodé CAMARAFodé CAMARA 33

Construction du modèle(2)

10/04/23 Fodé CAMARAFodé CAMARA 44

Données Apprentissage

NomRangAnnéeTitulaire

MaryAssistant Prof3non

JamesAssistant Prof7oui

BillProfessor2oui

JohnAssociate Prof7oui

MarkAssistant Prof6non

AnnieAssociate Prof3non

Algorithmes Classification

Modèle

Si Rang=‘Professor ’Ou Année>6Alors titulaire=Oui

Construction du modèle

10/04/23 Fodé CAMARAFodé CAMARA 55

Données Test

NomRangAnnéeTitulaire

TomAssistant Prof2non

LisaAssistant Prof7non

JackProfessor5oui

AnnAssociate Prof7oui

Classifier

Taux d’erreur du modèle?

Construction du modèle

10/04/23 Fodé CAMARAFodé CAMARA 66

Donnée inconnue

NomRangAnnéeTitulaire

JeffProfessor4?

PaulAssociate Prof7?

Classifier

Titulaire ?

Oui

Oui

Validation de la Classification

10/04/23 Fodé CAMARAFodé CAMARA 77

Validation de la Classification

10/04/23 Fodé CAMARAFodé CAMARA 88

Techniques de datamining(34)La classification Méthodes de Classification

Arbres de décision Classification bayésienneRéseaux de neurones etc.

Caractéristiques

Apprentissage supervisé (classes connues)

10/04/23 Fodé CAMARAFodé CAMARA 99

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

10/04/23 Fodé CAMARAFodé CAMARA 1010

Rang?

Année? Année?Oui

NonNon

OuiOui

Professor

Assistant Prof

Associate Prof

=<6 >6=<6>6

Génération de l'arbreo 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

10/04/23 Fodé CAMARAFodé CAMARA 1313

Rang?

Année? Année?Oui

NonNon

OuiOui

Professor

Assistant Prof

Associate Prof

=<6 >6=<6 >6

Si Rang=‘Professor ’Ou Année>6Alors 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, …Pnpour i = 1 à n faire Partition(Pi);

Procédure de Construction (2)

Processus récursifL'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èneIl 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 IndexSuppose des attributs continusSuppose plusieurs valeurs de division pour chaque attributPeut-être étendu pour des attributs nominaux

Gain d’information

Sélectionner l’attribut avec le plus grand gain d’informationSoient 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

10/04/23 Fodé CAMARAFodé CAMARA 2222

Classifier les clients d'une banque s’ils sont à risque ou pas

BD

Rappel(3)

10/04/23 Fodé CAMARAFodé CAMARA 2323

Evaluation d’une classification