ISI-Institut Suprieur dInformatique
Cours Datamining
Dr. F. CAMARA
[Link]@[Link]
03/05/2013
Fod CAMARA
Techniques de datamining
La classification
Elle permet de prdire si une instance de donne est membre dun groupe ou dune classe prdfinie. Classes o Groupes dinstances avec des profils particuliers o Apprentissage supervis: classes connues lavance Applications: marketing direct (profils des consommateurs), grande distribution (classement des clients), mdecine (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 cte Ouest des tats unis.
03/05/2013
Fod CAMARA
Techniques de datamining(33)
La classification Processus deux tapes
03/05/2013
Fod CAMARA
Construction du modle(2)
Donnes Apprentissage Algorithmes Classification
Nom Mary James Bill John Mark Annie
Rang Assistant Prof Assistant Prof Professor Associate Prof Assistant Prof Associate Prof
Anne 3 7 2 7 6 3
Titulaire non oui oui oui non non
Modle
Si Rang=Professor Ou Anne>6 Alors titulaire=Oui
03/05/2013
Fod CAMARA
Construction du modle
Donnes Test Classifier
Nom Tom Lisa Jack Ann
Rang Assistant Prof Assistant Prof Professor Associate Prof
Anne 2 7 5 7
Titulaire non non oui oui
Taux derreur du modle ?
03/05/2013
Fod CAMARA
Construction du modle
Donne inconnue Classifier
Nom Jeff Paul
Rang Professor Associate Prof
Anne 4 7
Titulaire ? ?
Titulaire ?
Oui Oui
03/05/2013
Fod CAMARA
Validation de la Classification
03/05/2013
Fod CAMARA
Validation de la Classification
03/05/2013
Fod CAMARA
Techniques de datamining(34)
La classification Mthodes de Classification
Arbres de dcision Classification baysienne Rseaux de neurones etc.
Caractristiques Apprentissage supervis (classes connues)
03/05/2013
Fod CAMARA
Techniques de datamining(35)
La classification Arbre de dcision
Gnration darbres de dcision partir des donnes Arbre = Reprsentation graphique dune procdure de classification
Rang?
Professor Associate Prof Assistant Prof
Oui
Anne?
<=6 Non >6 Oui
Anne? <=6 >6
Non Oui
03/05/2013
Fod CAMARA
10
Gnration de l'arbre
o
o o o o o
Au dpart, toutes les instances dapprentissage sont la racine de larbre. Slectionner un attribut et choisir un test de sparation(split) sur lattribut, qui spare le mieux les instances. Partitionner les instances entre les nuds fils suivant la satisfaction des tests logiques. v'1 Traiter chaque nud fils de faon rcursive. Rpter jusqu ce que tous les nuds soient des terminaux. C1 Etiqueter le nud terminal par la classe majoritaire
A1 = ? v1 v2 A2 = ? ... v'3 v'2 v'1 A2 = ? v'3 v3
v'2
C2
C3
C7
C8
C9
Arbre = ensemble de rgles
(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 A2? ... v'1 v'2 A2? v'3 v3
v'1
v'2
v'3
C1
C2
C3
C7
C8
C9
Arbre = ensemble de rgles
Exemple:
Rang?
Professor Associate Prof Assistant Prof
Oui
Anne? <=6 Non >6 Oui
Anne? <=6 >6 Non Oui
Si Rang=Professor Ou Anne>6 Alors titulaire=Oui
03/05/2013
Fod CAMARA
13
Procdure de construction (1)
recherche chaque niveau de
classe) alors retour; pour chaque attribut A faire
lattribut le plus discriminant Partition (nud P) si (tous les lments de P sont dans la mme
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);
Procdure de Construction (2)
Processus rcursif
Class Atr=?
L'arbre commence un nud reprsentant
toutes les donnes Si les objets sont de la mme classe, alors le nud devient une feuille tiquet par le nom de la classe. Sinon, slectionner les attributs qui sparent le mieux les objets en classes homognes => Fonction de qualit La rcursion s'arrte quand:
Les objets sont assigns une classe homogne Il n'y a plus d'attributs pour diviser
Mesure de qualit
La mesure est appel fonction de
qualit Goodness Function en anglais Varie selon l'algorithme : Gain d'information (ID3/C4.5)
Gini Index
Suppose des attributs continus Suppose plusieurs valeurs de division pour chaque
Suppose des attributs nominaux (discrets) Peut-tre tendu des attributs continus
attribut Peut-tre tendu pour des attributs nominaux
Gain dinformation
Slectionner lattribut avec le plus grand gain dinformation Soient P et N deux classes et S un ensemble dinstances
avec p lments de P et n lments de N. Linformation ncessaire pour dterminer si une instance prise au hasard fait partie de P ou N est(entropie).
Gain dinformation
Soient les ensembles {S1, S2, , , Sv} formant une partition de
lensemble S , en utilisant lattribut A Toute partition Si contient p instances de P et n instances de N Lentropie, ou linformation ncessaire pour classifier les instances dans les sous-arbres Si est:
Le gain dinformation par rapport au branchement sur A est Choisir lattribut qui maximise le gain
Indice de GINI
Utiliser lindice Gini pour un partitionnement pur
pi est la frquence relative de la classe C dans S Si S est pur (classe unique), Gini(S) = 0
Trouver le branchement (split-point) qui minimise lindice Gini
Indice de GINI (Exemple 1)
Indice de GINI (Exemple 2)
Exemple dapplication
Classifier les clients d'une banque sils sont risque ou pas
BD
03/05/2013
Fod CAMARA
22
Rappel(3)
Evaluation dune classification
03/05/2013
Fod CAMARA
23