Ecole Centrale Polytechnique
Cours : DataMining
Chapitre 2 : La classification
Elaboré par : Houcine ESSID
Niveau : 2ème année ING Affaires et Projets
1
Classification vs prédiction
Classification
• Classification, classement , discrimination
•Prédit la catégorie d’un objet (discrètes ou nominales)
•Construit un modèle basé sur un échantillon de test (jeu d’apprentissage)
et des valeurs (noms de catégorie) et l’utilise pour classer des données
nouvelles
Prédiction
•Modélise des données numériques pour prédire des données inconnue
ou manquantes
Applications
Diagnostic médical, ciblage marketing, credit scoring, détection de fraudes
2
Classification
Quelques méthodes
Š
• arbre de décision
•Š classificateur bayésien
•Š réseau de neurones
•Š plus proches voisins
3
Classification : processus à deux étapes
• Construction du modèle
•Š chaque objet appartient à une classe connue
• jeu de données d’apprentissage : ensemble des objets utilisés pour la
construction du modèle
• Utilisation du modèle pour classer des objets nouveaux ou
inconnus
•Š estimation de la précision du modèle à l’aide du jeu de test
• les classes connues du jeu d’apprentissage sont comparées à celles
prédites
• précision : pourcentage d’objets de jeu de test correctement classés
• le jeu de test est indépendant du jeu d’apprentissage sinon risque
4
de biais (défaut)
Classification : Construction du modèle
Tenured= titulaire 5
Classification : Utilisation du modèle
Règles de classification
6
Apprentissage supervisé vs apprentissage
non supervisé
Apprentissage supervisé (classification)
• supervision : le jeu de données d’apprentissage fournit les classes des objets
• les nouveaux objets sont classés en fonction du jeu d’apprentissage
Apprentissage non supervisé (clustering)
• Pas de classes définies
• Étant donné un ensemble de mesures, d’observations, etc., essayer d’établir
l’existence de classes ou de clusters dans les données
7
Classification par les arbres de décision
Output : arbre de décision “buys_computer”
nœuds internes : test sur un attribut
9 yes branches : résultat d’un test / valeur
age? 5 no de l’attribut
feuilles : classe
<=30 31..40 >40
2 yes 4 yes 3 yes
3 no 0 no 2 no
student? yes credit rating?
no yes excellent fair 3 yes
0 yes 2 yes 0 yes
0 no
3 no 0 no 2 no
no yes yes
8
Classification par les arbres de décision:
généralité
Génération de l’arbre en 2 étapes
1. Construction
• au départ, tous les exemples du jeu d’apprentissage sont à la racine
• partitionne récursivement les exemple en sélectionnant des attributs
2. Élagage
• identification et suppression des branches correspondant à des exceptions ou
du bruit
Utilisation de l’arbre
• teste les valeurs des attributs avec l’arbre de décision
9
Algorithme pour l’induction d’arbres de
décision
• Algorithme glouton
•approche descendante récursive diviser pour régner
•au départ, tous les objets sont à la racine
• attributs catégoriels (les valeurs continues sont discrétisées à l’avance)
•les exemples sont partitionnés récursivement par la sélection d’attribut
•les attributs sont sélectionnés sur la base d’une heuristique ou d’une
mesure statistique
• Conditions d’arrêt
• tous les exemples pour un nœud appartiennent à la même classe
• plus d’attribut pour partitionner, dans ce cas la classe attribuées
correspond à celle la plus représentée
10
Induction d’arbres de décision :
Algorithme générer_arbre_décision
Input:
D : partition de données – jeu d’apprentissage et valeurs des classes
correspondantes
L : liste des attributs candidats
méthode_sélection_attribut: procédure pour déterminer le critère de
scission qui partitionne le mieux les tuples de données en classes on parle
d’attribut de scission, point de scission
Output : arbre de décision
11
Mesure pour la sélection d’attributs:
Plusieurs mesures possibles:
• Entropie ou gain informationnel (ID3, C4.5)
• Indice de concentration ou indice de GINI (CART)
• Mesure de liaison statistique (CHAID)
12
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)
•L’entropie est une fonction mathématique
correspondant à la quantité d’information
contenue ou délivrée par une source
d’information.
•Elle permet de mesurer le désordre dans un
ensemble de données.
• Si la source délivre une seule information
l’entropie est nulle
•Si la source délivre deux informations :
chacune avec une probabilité égale à 0,5
l’entropie est égale à 1.
13
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)
Entropie de Shannon
Shannon en 1949 a proposé une mesure d’entropie valable pour les distributions
discrètes de probabilité. Elle exprime la quantité d’information, c’est-à-dire
le nombre de bits nécessaires pour spécifier la distribution
L’entropie d'information est:
I = - p i log2 (p i )
i=1..k
où pi est la probabilité de la classe Ci.
Entropie d’information de S
C
I ( S ) = − p (ci ) log 2 p (ci )
i =1
Nulle quand il n’y a qu’une classe
D’autant plus grande que les classes sont équiprobables
Vaut log2(k) quand les k classes sont équiprobables
Gain d’information : Gain(S,A)=Réduction d’entropie due à un tri suivant les
valeurs de A → l’objectif est de trouver un attribut permettant d’avoir des feuilles
14
pures cad dont l’information est la plus petite
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)
◼ But: sélectionner l’attribut ayant le plus grand gain d’information
◼ Soit pi la probabilité qu’un tuple arbitraire dans D appartienne à la classe
Ci, estimé par |Ci, D|/|D| (nombre de tuples de D appartenant à Ci
divisé par le nombre de tuples de D)
◼ L’information moyenne (entropie) nécessaire pour classer un tuple dans
m
D:
Info( D) = − p log ( p )
i =1
i 2 i
◼ L’information nécessaire (en utilisant l’attribut A pour scinder D en v
partitions) pour classifier D selon A: v | D |
Info A ( D) =
j
Info ( D j )
j= nombre de valeurs dans A j =1 | D |
◼ Le gain d’information en partitonnant selon l’attibut A
Gain(A) = Info(D) − Info A(D) 15
Sélection d’attribut: Gain d’information
Classe P: buys_computer = “yes” 5 4
Infoage ( D) = I (2,3) + I (4,0)
Classe N: buys_computer = “no” 14 14
9 9 5 5 5
Info( D) = I (9,5) = − log 2 ( ) − log 2 ( ) =0.940 + I (3,2) = 0.694
14 14 14 14 14
5
age pi ni I(pi, ni) I (2,3) → “age <=30” a 5 parmi 14
<=30 2 3 0.971 14
exemples, avec 2 yes et 3 no.
31…40 4 0 0 Ainsi
>40 3 2 0.971
age income student credit_rating buys_computer Gain(age) = Info( D) − Infoage ( D) = 0.246
<=30 high no fair no
<=30 high no excellent no
31…40 high
>40 medium
no
no
fair
fair
yes
yes
On a aussi,
>40
>40
low
low
yes fair
yes excellent
yes
no Gain(income) = 0.029
31…40 low yes excellent yes
<=30
<=30
medium
low
no fair
yes fair
no
yes
Gain( student ) = 0.151
>40
<=30
medium
medium
yes fair
yes excellent
yes
yes Gain(credit _ rating ) = 0.048
31…40 medium no excellent yes
31…40 high
March 20, 2021
yes fair yes Donc on choisit l’attribut AGE 16
>40 medium no excellent no
Pour générer un arbre de décision:
1) Une base d’apprentissage
2) Une base de test
3) Utiliser une mesure statistique
• Entropie (ou gain informationnel)
• Indice de Gini
17
18
19
20
21
22
23
24
25
26
27
Dans le quadrillage ci-dessous 14 points sont dessinés, dont
7 de la classe C1, avec des ronds noirs et 7 de la classe C2,
avec des losanges.
On introduit un nouveau point A, dont on cherche la classe à
l’aide d’un algorithme des k plus proches voisins pour la
distance géométrique habituelle, en faisant varier la valeur de
k parmi 1, 3 et 5.
28
29
On cherche à prédire la couleur d’un fruit en fonction de sa largeur et de
sa hauteur.
On dispose des données d’apprentissage suivantes :
largeur hauteur couleur
2 6 red
5 6 yellow
2 5 orange
6 5 purple
1 2 red
4 2 blue
2 1 violet
6 1 green
Ces données sont placées dans un repère en abscisse, en ordonnée).
30
31
L’objectif ici est d’étudier l’influence des voisins sur la
propriété de couleur d’un fruit.
Soit le nouveau fruit de largeur L = 1, et de hauteur H = 4.
1.Indiquez pour chaque point sa couleur.
2.Quelle est sa couleur si l’on considère 1 voisin ?
3.Quelle est sa couleur si l’on considère 3 voisins ?
32
