Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira de Bejaïa

Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

b. L'algorithme C4.5

 Prise en compte les attributs numérique

 Des attributs dont l'arité est élevée (voire infinie)
 C'est un successeur d'ID3
 Dans le cas de C4.5, un nœud de l’arbre de décision peut contenir un test du fait que la valeur d’un
attribut numérique est inferieure à un certain seuil : cela correspond donc à un nouveau pseudo-
attribut binaire. C4.5 ne dispose pas d’autres possibilités de prendre en compte ce type d’attributs.

Exemple
Nous illustrons le déroulement de l'algorithme C4.5 sur le jeu de données « jouer au tennis ? » dans
lequel les attributs «Température» et «Humidité» prennent des valeurs numérique
20

Jour Ciel Température Humidité Vent Jouer Au Tennis?

1 Ensoleillé 27.5 85 Faible Non
2 Ensoleillé 25 90 Fort Non
3 Couvert 26.5 86 Faible Oui
4 Pluie 20 96 Faible Oui
5 Pluie 19 80 Faible Oui
6 Pluie 17.5 70 Fort Non
7 Couvert 17 65 Fort Oui
8 Ensoleillé 21 95 Faible Non
9 Ensoleillé 19.5 70 Faible Oui
10 Pluie 22.5 80 Faible Oui
11 Ensoleillé 22.5 70 Fort Oui
12 Couvert 21 90 Fort Oui
13 Couvert 25.5 75 Faible Oui
14 Pluie 20.5 91 Fort Non

 Test d’un attribut numérique

Considérons les exemples dont l’attribut «Ciel» vaut «Ensoleillé», soit l’ensemble XCiel = Ensoleillé
d’exemples ayant un seul attribut numérique comme suit :

21
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

Température 19.5 21 22.5 25 27.5

Jour Température "Jouer au Tennis" Jour 9 8 11 2 1
1 27.5 Non "Jouer au tennis?" Oui Non Oui Non Non
2 25 Non
8 21 Non
9 19.5 Oui On détermine le seuil s pour partitionner cet
11 22.5 Oui ensemble d’exemples. C4.5 utilise les règles
suivantes :
On commence par trier les exemples sur la valeur de 1. Ne pas séparer deux exemples successifs
leur attribut numérique. A chaque attribut, on associe ayant la même classe ; donc, on ne peut
le numéro de son exemple associé ainsi que la valeur
couper qu’entre les exemples x9 et x8, x8 et
de l’attribut cible :
x11, x11 et x2.

22 23

2. Si on coupe entre deux valeurs V et W (V < W) Pour S = 21, le gain d’information est :
de l’attribut, le seuil S est fixé à V (on aurait
Gain en information de température :
pu aussi utiliser V+W/2)
3. Choisir S de telle manière que le gain
Gain (température)= 0.971- (1/5 * E(Ctempérature<
d’information soit maximal.
4. Une fois le seuil S fixé et le nœud créé, chaque 21 ) + 4/5 *E(Ctempérature >= 21))
sous-arbre pourra à nouveau tester la valeur de Avec:
cet attribut E(Ctempérature < 21) = - (1ln21+0ln20)=0
5. En effet, contrairement au cas des attributs
qualitatifs qui produisent des nœuds ayant et
autant de branches que l’attribut prend de E(Ctempérature >= 21)= -(1/4ln21/4+3/4ln23/4)≅0.608
valeurs différentes, l’ensemble des valeurs soit
prises par un attribut numérique est coupé en 1 4
deux : chaque partie peut donc encore être gain(C,S=21)≅ 0.971 − (5 ∗ 0 + 5 ∗
raffinée jusqu’`a ne contenir que des exemples 0.608) ≅ 0.485
ayant même valeur cible.
de la même manière, en fonction du seuil,
L’entropie de l’ensemble d’exemples est : le gain d'information est alors:

E (Cjouer
𝟐 𝟐 3 3
= oui,C jouer = non)=-−(𝟓l𝑛2 𝟓 + 5 𝑙𝑛2 5) ≅ 0.971 seuil Gain(C, température,S)
S=21 0.485
S=22.5 0.02
S=25 0.42

24 25
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

6. C4.5 effectue ce traitement pour chaque Arbres de décision avantages & inconvénients
attribut quantitatif et détermine donc pour + Compréhensible pour tout utilisateur (lisibilité du
chacun un seuil produisant un gain résultat-règles-arbre)
d’information maximal. + Justification de la classification d'une instance
7. Le gain d’information associé à chacun des + Tout type de données
attributs quantitatifs est celui pour lequel le + Robuste au bruit et aux valeurs manquantes
seuil entraine un maximum. + Attributs apparaissent dans l'ordre de pertinence
8. Finalement, l’attribut choisi (parmi les + Classification rapide (parcours d'un chemin dans
quantitatifs et les nominaux pour lesquels le un arbre)
principe est identique ID3) est celui qui +Outils disponible dans la plupart des
produit un gain d’information maximal environnements de data mining.
9. En présence d’attribut numérique ou d’attribut - Sensible au nombre de classes: performances se
d’arité élevée, ceux-ci sont automatiquement dégradent
favorisés pour être sélectionné comme test -Evolution dans le temps: si les données évoluent
dans les nœuds. Pour contrecarrer cet effet, dans le temps, il est nécessaire de relance la
C4.5 utilise le rapport de gain au lieu du gain phase d'apprentissage.
d’information pour déterminer l’attribut `a
utiliser dans un nœud.
 2.5.4. Les réseaux de neurones artificiels
Le rapport de gain est défini par:  Réseau neuronal :
𝐺𝑎𝑖𝑛(𝐶,𝐴)
𝑅𝑎𝑝𝑝𝑜𝑟𝑡 𝑑𝑒 𝑔𝑎𝑖𝑛(𝐶, 𝐴) = , où  Simule le système nerveux biologique
𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜 (𝐶,𝐴)

𝑆𝑝𝑙𝑖𝑡 𝐼𝑛𝑓𝑜(𝐶, 𝐴) =
|𝐶𝐴 = 𝑣| |𝐶𝐴 = 𝑣|
∑ 𝑙𝑛2
𝑣∈𝑣𝑎𝑙𝑒𝑢𝑟𝑠(𝐴) |𝐶 | |𝐶 |

26 27

 Un réseau de neurones est composé de plusieurs neurones ou d'unité de traitement

interconnectés entre elles. Un poids est associé à chaque arc. A chaque neurone on associe une
valeur
 Les réseaux de neurones se distinguent en particulier par la topologie des connexions et le
mécanisme d'apprentissage
 Neurone:
 Unité de calcul élémentaire
 Le vecteur d'entrée X est transformé en une variable de sortie Y, par un produit scalaire et une
fonction de transformation non linéaire

28
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

X0 w0

Σ
X1 w1
. .
F
. .
Sortie y
. .
Xn wn
Fonction
d'activation

Somme
Vecteur Vecteur poids w
pondérée
entrée x (coefficients
Synaptiques)
29

X1
W1j
X2
W2j Neurone j Yi
. .
. .

.
Wnj

Xn

30
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

 Le neurone prend un ensemble de valeur Xi en entrée et produit une sortie Yi calculée de la

manière suivante:
𝑛

𝑦𝑖 = 𝑓(∑ 𝑥𝑖𝑤𝑖𝑗 + 𝑏𝑖𝑎𝑖𝑠𝑗) OÙ 𝑓 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛 𝑑′𝑎𝑐𝑡𝑖𝑣𝑎𝑡𝑖𝑜𝑛

𝑖=1
le biais peut être assimilé à un poids W0j pour une entrée X0 qui est toujours activées(X0=1).Voici
quelques exemples de fonctions d'activation populaires:
Linéaire: 𝑓(𝑥) = 𝑎𝑥
Seuil: 𝑓(𝑥) = 1 𝑠𝑖 𝑥 > 0 𝑠𝑖𝑛𝑜𝑛 0
Sigmoïde (logistique): 𝑓(𝑥) = 1/1 + 𝑒 −𝑥 , 𝑑𝑜𝑛𝑐 𝑓(𝑥) ∈ [0. .1]
 Certains mécanismes d'apprentissage exigent que la fonction d'activation soit dérivable, ce
qui n'est pas le cas de la fonction seuil. La sortie y peut être passée à un autre neurone qui
effectue le même calcul à son tour
31

2.5.4.1.Mise en œuvre d’un réseau

Les étapes dans la mise en œuvre d’un réseau de neurones pour la prédiction ou le classement sont :
 Identification des données en entrée et en sortie
 Normalisation de ces données
 Constitution d’un réseau avec une topologie adaptée
 Apprentissage du réseau
 Test du réseau
 Application du modèle généré par l’apprentissage
 Dé normalisation des données en sortie.
2.5.4.2. Modèles de réseau de neurones:
 Le réseau à fonction radiale de base («radial basis function» RBF) est aussi utilisé pour prédire
une variable cible continue ou discrète
 Le réseau de Kohonen effectue les analyses typologiques (clustering, recherche de segments)
 etc...
Perceptron multicouches:
 Est utilisé pour prédire une variable cible continue ou discrète

32
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

33

Paradigme d'apprentissage

34
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

Algorithme d'apprentissage :Rétro-propagation  Apprentissage de réseau utilisant les

du gradient
données disponibles
 Construction de réseau:
 Représentation des entrées  Pour effectuer la classification, le réseau
 Nombre de nœuds en entrée: correspond doit être entrainé en ajustant les poids
à la dimension des données du problème (incluant les biais) à partir de
l'échantillon d'entrainement
(attributs ou leurs codages) et normaliser
 Au départ les poids peuvent être
dans l'intervalle [0,1]. initialisés de manière quelconque
 Chacun des éléments de l'échantillon est
Exemple: un attribut A prends ses valeurs {1, 2, 3,
donné en entrée et la sortie est comparée
4,5} avec la classe d'appartenance de
l'élément
 5 entrée à la valeur binaire; 3=00100  L'apprentissage est effectué en
 3 bit; 3=010 ajustant les poids en fonction de la
 1 entrée réelle;0,0.25, 0.5, 0.75, 1 différence entre la réponse produite et
 Nombre de couches cachées: ajuster pendant la bonne réponse
l'apprentissage.  Un mécanisme populaire
 Nombre de nœuds par couche: le nombre de d'ajustement des poids est la rétro-
nœuds par couche est aux moins égale à propagation de l'erreur, le principe est
deux et au plus égal au nombre de nœuds en d'ajuster les poids de manière à
entrée rapprocher la réponse du système de
 Nombre de nœuds en sortie: fonction du celle attendue
nombre de classes associées à l'application.

35 36

 En appliquant le principe d'optimisation bien connu de descente du gradient pour minimiser la

moyenne des carrés d’erreurs, on obtient les formules suivantes d'ajustement des poids

𝒘𝒊𝒋 = 𝒘𝒊𝒋 + ∆𝒘𝒊𝒋

∆𝒘𝒊𝒋 = 𝒗𝒊𝒕𝒆𝒔𝒔𝒆𝑨𝒑𝒑𝒓𝒆𝒏𝒕𝒊𝒔𝒔𝒂𝒈𝒆 ∗ 𝑬𝒓𝒓𝒆𝒖𝒓𝒋 ∗ 𝒚𝒊

𝑬𝒓𝒓𝒆𝒖𝒓𝒋 = 𝒚𝒊(𝟏 − 𝒚𝒊)(𝒗𝒂𝒍𝒆𝒖𝒓 𝒂𝒕𝒕𝒆𝒏𝒅𝒖 − 𝒚𝒊) 𝒑𝒐𝒖𝒓 𝒏𝒆𝒖𝒓𝒐𝒏𝒆 𝒋 𝒆𝒏 𝒔𝒐𝒓𝒕𝒊𝒆

= 𝒚𝒊(𝟏 − 𝒚𝒊) ∑ 𝑬𝒓𝒓𝒆𝒖𝒓𝒌𝒘𝒋𝒌 𝒑𝒐𝒖𝒓 𝒏𝒆𝒖𝒓𝒐𝒏𝒆 𝒋 𝒅𝒆 𝒍𝒂 𝒄𝒐𝒖𝒄𝒉𝒆 𝒄𝒂𝒄𝒉é𝒆

37
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

 La vitesse d'apprentissage est un paramètre ajustable dont la valeur typique entre 0 et 1.On peut
la faire décroitre graduellement afin de stabiliser l'évolution des poids. Par exemple, en prenant
une valeur 1/n où n croît avec le nombre d'élément traités
 pour le biais, les formules d'apprentissage sont:
 𝑏𝑖𝑎𝑖𝑠𝑖𝑗 = 𝑏𝑖𝑎𝑖𝑠𝑖𝑗 + ∆𝑏𝑖𝑎𝑖𝑠𝑖𝑗
 ∆𝑏𝑖𝑎𝑖𝑠𝑖𝑗 = 𝑣𝑖𝑡𝑒𝑠𝑠𝑒 𝐴𝑝𝑝𝑟𝑒𝑛𝑡𝑖𝑠𝑠𝑎𝑔𝑒 ∗ 𝐸𝑟𝑟𝑒𝑢𝑟𝑗
 L'apprentissage peut être effectué en ligne en ajustant les paramètres à chacun des patrons
d'entrée ou en lot en accumulant les ajustements pour un lot de patrons
 d'entrée. Dans l'apprentissage en lot, chacun des cycles d'apprentissage appelé une époque
 le critère d'arrêt: la tolérance définit l'erreur cible ou/et le nombre d'instances bien classés
(seuil)
 Elagage de réseau
 Réseau fortement connexe est difficile à articuler: N nœuds en entrée, h couches cachées, et m
nœuds en sortie → ℎ(𝑚 + 𝑛) 𝑎𝑟𝑐𝑠(𝑝𝑜𝑖𝑑𝑠)
 Elagage: supprimer les arcs et les nœuds qui n'affectent pas le taux d'erreur du réseau
 Interprétation des résultats

Exemple

La figure ci dessus montre un exemple de RNA pour notre problème de classification des données
de profils Internet. Le réseau prend en entrée les données qui représentent un élément à classifier et
produit en sortie une réponse qui identifie la classe d'appartenance de l'élément. Chaque ovale
représente un neurone artificiel. Un arc représente une connexion entre deux neurones et W ij est le
poids de la connexion du neurone i au neurone j .Les arcs sont implicitement orientés de gauche à
droite dans notre diagramme. La sortie d'un neurone est passée comme entrée à un autre neurone ou
encore à la sortie. Ce réseau est constitué de trois couches, une couche d'entrée, une couche cachée
et une couche de sortie. La couche d'entrée représente les données utilisées pour la classification. Il
ya un neurone pour chacun des valeurs d'un attribut. Pour représenter le fait qu'un élément possède
une valeur particulière d'attribut, une valeur 1 sera transmise en entrée au neurone et la valeur 0 sera
transmise pour les autres neurones du même attribut. Par convention, la valeur 1 en sortie du seul
neurone de la couche de sortie représente la classe internet=oui et un 0, la valeur internet=non.

38
 Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abderrahmane Mira de Bejaïa
Faculté des Sciences Exactes
Département de d’Informatique

Module: Data Mining Année: 2021-2022

Nature de document: Cours N.BERMAD
Niveau: M1-RN-SIA
Chapitre: 2(suite)
Titre: Les tâches et les techniques du Data Mining

Couche d'entrées Couche cachée

1 si sexe=m 0 sexe=m
sinon Wij

sexe=f

âge = jeune 0=non

internet =?
1= oui
âge = vieux
.
.
revenu=faible

..
.
revenu=élevé
..
Réseaux de neurones - Avantages
39
.
 Taux d'erreur généralement bon
 Outil disponible dans les environnements de data mining
 Robustesse (bruit)-reconnaissance de formes (son, images sur une rétine,...)
 Classification rapide (réseau étant construit)
 Combinaison avec d'autres méthodes (ex: arbre de décision pour sélection d'attributs)

Réseaux de neurones - Inconvénients

 Apprentissage très long
 Plusieurs paramètres (architecture, coefficients synaptique, ...)
 Pouvoir explicatif faible (boite noire)
 Pas facile d'incorporer les connaissances du domaine.
 Traitent facilement les attributs numériques et binaires
 Evolutivité dans le temps (phase d'apprentissage)
40