2 IRAD - FD - Chap2

Discrétisation des données numériques
Chapitre 2
La discrétisation des données
numériques
2.1 Introduction ............................................................................................ 1

2.1.1 Information qualitative 2
2.1.2 Information quantitative 2
2.2 L’apprentissage supervisé ....................................................................... 2
2.3 Les méthodes de discrétisation supervisée .............................................. 3

2.3.1 Méthode Hyper Cluster Finder 3
Algorithme de la méthode Hyper Cluster Finder 3
Complexité algorithmique 5
2.3.2 Méthode CONTRAST 5

L’algorithme de CONTRAST 5
Déroulement d’exemple 6
2.3.3 Méthode utilisant une mesure d’entropie (algorithme MDLPC)............................ 9

Le critère de la méthode MDLPC 9
L’algorithme basé sur le critère du MDLPC 10
2.4 Apprentissage non supervisé ..................................................................13
2.5 Les méthodes de discrétisation non supervisées ....................................14

2.5.1 La méthode des quantiles ("des effectifs égaux") ........................................... 14
Algorithme des effectifs égaux 14
2.5.2 La méthode égale amplitude ("Classe égale entendue") .................................. 16

Algorithme classe égale amplitude 16
2.6 Conclusion ..............................................................................................18
Dr ATMANI Baghdad 0
Master IRAD – Module Fouille de données / 2009-2010
Département Informatique – Faculté des Sciences – Université d’Oran
2.1 Introduction
L’étape de prétraitement porte sur l’accès aux données en vue de
construire des tables bidimensionnelles. En fonction du type des données (e.g.
numérique, symbolique, etc.), des méthodes de prétraitements pour la
discrétisation des données continue sont mises en œuvre. Cette phase est
importante puisque c’est elle qui va conditionner la qualité des modèles établis
lors de la fouille de données. En effet, ces choix ont pour objectif de faire
émerger l’information contenue au sein de cette masse de données.
Comme nous allons le voir dans ce mémoire, le prétraitement et en particulier la
phase de discrétisation des données est une phase cruciale. En effet, c’est du
choix des points de coupure des variables continues et de la connaissance précise
de la population que va dépendre la mise au point des modèles de prédiction.
L’information nécessaire à la construction d’un bon modèle de prédiction peut
être disponible dans les données, mais un choix inapproprié des points de
discrétisation des variables peut faire échouer l’opération [Atm, 07a].
La discrétisation des variables exogènes continues est généralement nécessaire
pour pouvoir utiliser les méthodes de fouilles de données opérant sur des tables
bidimensionnelles.
Différents types de méthodes de discrétisation existent, à savoir des
méthodes basées sur la notion d’apprentissage supervisé et d’autres basées sur la
notion du non supervisé.
La discrétisation est un domaine très étudié en apprentissage, en effet
elle joue un rôle très important pour construire un modèle performant issu de
l’ECD.
Définition 1: Discrétiser une variable quantitative, c'est mathématiquement,
transformer un vecteur de nombres réels en un vecteur de nombres entiers
nommés "indices de classe". C'est pourquoi effectuer cette transformation se dit
en langage courant "réaliser un découpage en classes". En statistiques, discrétiser
c'est à la fois réaliser cette transformation mathématique, nommer et justifier les
classes. [Gilles Hunault]
Définition 2: Discrétise un attribut numérique consiste à découpe son domaine de
valeur en un nombre fini d’intervalles qui seront identifié par un code.
Mais avant la discrétisation il faut connaitre parfaitement:
1. le but de discrétisation.
2. les caractéristiques de la variable à discrétiser.
Cela peut aider à trouver les limites des groupes qui traduiront au
mieux les caractéristiques d’une variable. Les principes de discrétisation différent
avec la nature de l’information (que l’attribut soit qualitatif ou quantitatif) :
Dr ATMANI Baghdad 1
2.1.1 Information qualitative

Nominale : on cherche à définir un critère commun de regroupement pour aboutir
a la construction d’une typologie.
Définition d’une variable qualitative (variables catégorielles): Pour les variables
catégorielles, ses modalités n’ont pas de sens quantitatif et il n’existe aucune
relation d’ordre entre elles. Tel est le cas par exemple pour le sexe, la catégorie
sociale au niveau individuel, couleur ou marque d’une voiture c'est-à-dire une
variable qualitative c’est une valeur qui n’a pas de nombre [Hyperge].
2.1.2 Information quantitative

Ordinale : on cherche à conserver la hiérarchie des informations.
Définition d’une variable quantitative (Quantitative variable) : Variable dont les
valeurs sont des nombre, exemple : du poids d'un ensemble d'individus. Si
plusieurs individus montent sur une balance, leur masse totale est la somme de
leurs masses individuelles .Contre exemple de la variable étage d'un ensemble de
logements. Cette variable est mesurée par un nombre, mais ce n'est pas une
quantité, on ne peut pas faire un total avec les étages de plusieurs logements. Par
contre, la variable "pièces" des logements est quantitative. Les variables
quantitatives s'opposent aux variables qualitatives, pour lesquelles le calcul d'un
total associé à plusieurs individus à partir de leurs valeurs individuelles ne peut
pas résulter d'une opération mathématique [Hyperge].
On dit qu’une discrétisation est satisfaisante l’ors qu’elle, permet la
création de classes homogènes et distinctes entre elles. Exemple : les objets
géographiques d’une même classe doivent se ressembler plus entre eux qu’il ne
ressemble aux objets des autres classes.
2.2 L’apprentissage supervisé
L’approche supervisée est basée sur la notion d’apprentissage automatique

supervisé. C’est un ensemble de méthodes utilisant un ensemble d’exemples où
les classes d’appartenance sont connues au préalable. Cet ensemble utilisé est
constitué d’un groupes de caractéristiques décrivant chaque individu (ces
caractéristiques appelées variables prédictifs ou exogènes) et chaque individu
possède une caractéristique particulière (appelée classe ou variable à prédire), on
peut définir une classe comme étant un groupes d’instances avec des profils
particuliers, Dans l’exemple « jouer au tennis ? », l’attribut « jouer », constitué
de deux classe : « oui » et « non », est la classe à prédire. A partir de cet
ensemble des règles d’affectation seront définies.
L’objectif de l’apprentissage supervisé est de chercher à estimer les
dépendances entre les données. Ou encore à chercher une liaison entre un attribut
à prédire Y et une série d’attributs prédictifs Xi. Une grande partie des méthodes
développées dans ce cadre, issues de l’intelligence artificielle, le sont
Dr ATMANI Baghdad 2
exclusivement pour des attributs prédictifs [MIC 83]. C’est pour ce là, qu’il est
primordial avant de passer a l’étape d’apprentissage, de ré-encoder chaque
attribut prédictif continu en attribut constitué d’un ensemble d’intervalles
disjoints : ce processus est connu sous le terme de discrétisation [DOU 95].
2.3 Les méthodes de discrétisation supervisée

Parmi les différentes méthodes de discrétisation supervisée nous allons présenter :
 Méthode hyper cluster finder
 Méthodes utilisant une mesure d’entropie (algorithme MDLPC)
 Méthode CONTRAST
2.3.1 Méthode Hyper Cluster Finder

La méthode a été proposée par Fabrice Muhlenbach et Ricco RaKotomalala.
C’est une méthode de discrétisation supervisée polythétique (Un groupe est dit
polythétique lorsqu'il ne peut pas être défini par un caractère ou un ensemble
restreint de caractères nécessaires et suffisants pour faire partie de ce groupe)
[FAB 02]. Elle repose sur la notion d’amas et travaille en deux phases :
 Dans un premier temps, à l’aide d’un algorithme de construction de
voisinage, nous isolons des groupes d’individus de même étiquette,
 Puis dans un deuxième temps, nous procédons au découpage des attributs
prédictifs en projetant, sur chaque axe de l’espace de représentation, les
extrémités des groupes.
Cette approche à l’avantage de répondre directement à la problématique de
l’apprentissage supervisé, en effet le découpage tient compte des valeurs prises
par la variable à prédire, et elle tient compte des éventuelles interactions entre les
attributs prédictifs.
Algorithme de la méthode Hyper Cluster Finder

La méthode, Hyper-Cluster Finder, se déroule de la manière suivante :
1. Génération d’un graphe de voisinage, Les graphes de voisinage sont des
constructions issues de la géométrie computationnelle qui permettent de
rendre compte de la proximité des données dans l’espace de
représentation [ZIG 99]. Il existe plusieurs graphes :
 Le Graphe des Voisins Relatifs(GVR)
 Le Graphe de Gabriel (GG)
 La Triangulation de Delaunay(TD)
 Ou l’Arbre de Longueur Minimale (ALM).
La figure 2.1 illustre la construction du graphe des voisins relatifs :
Dr ATMANI Baghdad 3
Figure 2.1. Graphe de voisinage relatif (GVR).
Le graphe des voisins relatifs (GVR) est un graphe connexe dans lequel, si
deux points sont reliés par une arrête, alors ils vérifient la propriété ci-
dessous ou d(u,v) est la distance euclidienne entre deux points u et v dans
.
( , )≤ ( , ), ( , ) ∀ , ≠ ,
2. Coupure des arêtes reliant des points de classes différentes afin de

constituer les amas. On appelle amas un sous-graphe connexe du graphe
dont tous les sommets sont de même classe. Dans la figure 2.2 après avoir
coupé 3 arrête, nous obtenons un ensemble de deux amas (à l’intérieur
des rectangles à bouts arrondis).
Figure 2.2. Les deux amas après coupure des trois arrêtes.
3. Sélection des amas les plus pertinents. il est possible de supprimer les
amas considérés comme trop « petits » parmi les candidats à la
constitution des intervalles. La solution consiste a ne retenir que les amas
dont le nombre d’individus est au moins égal a un nombre fixé a priori,
ou un nombre dépendant de la taille de la population du plus grand des
amas obtenus.
4. Recherche des valeurs minimales et maximales de chacun des amas sur
les variables continues. C'est-à-dire prendre les valeurs des limites des
amas projetées sur les axes.
Dr ATMANI Baghdad 4
5. Utilisation de ces valeurs minimales et maximales pour définir des

bornes sur chacune des variables.
6. Pour chaque variable, le minimum et le maximum sont remplacés
respectivement par moins et plus l’infini.
7. Les valeurs de ces bornes délimitent un ensemble d’intervalle sur chaque
variable.
8. Les valeurs numériques des données sont ré-encodées par leur
appartenance à un des intervalles obtenus.
Sur la figure11, les bornes qui ont été trouvées ( 1 , 2 ) permettent
d’obtenir les intervalles suivant :
 ]−∞; 1 [, [ 1 ; 2 [ [ 2 ; +∞[ Pour la variable .
 ] − ∞; [ [ ; +∞[ Pour la variable .
Complexité algorithmique
Dans le cas ou il y’a des variables prédictives >3 la complexité
algorithmique est en ( ) en raison de la création de graphe.
Hyper Cluster Finder, est une méthode de discrétisation procédant de manière
polythétique et supervisée, ce qui permet en particulier de retrouver des
intervalles adaptés au traitement des problèmes d’apprentissage comprenant des
interactions entre les variables prédictives.
2.3.2 Méthode CONTRAST

La méthode de discrétisation CONTRAST a était proposé par T. Van
de Merckt [Van 93], son principe est que pour discrétiser un attribut il faut
chercher un point de coupure qui fournit le meilleur « contraste» entre deux
attribut même si les intervalles générés contiennent des exemples de classes
différents, cela revient à trouver les points de coupure qui maximise la distance
entre deux intervalles tout en minimisant la distance entre les exemples d‘un
même intervalle.
L’algorithme de CONTRAST
1. Initialisation en classant les exemples d’apprentissage par ordre croissant
des valeurs de l’attribut X à discrétiser.
2. Détermination des k points frontière. Les points de discrétisation sont
nécessairement des points frontières.
3. Sélectionner parmi les k points frontière celui qui maximise la quantité
( , , ):
( , , )
( , , )=−
, ( )
Soit
Dr ATMANI Baghdad 5
. .( . − .)
( , , )=−
∑ ∑ log
.
Avec
S l’échantillon ou sommet considéré
N l’effectif de l’échantillon S, ( )=
le sous - échantillon composé des exemples tels que = {ω ∈ s ; X(ω) ≤
d}
le sous - échantillon composé des exemples tels que = {ω ∈
s; X (ω) > }
L’effectif du sous - échantillon (i=1,2)
. la moyenne de l’attribut X sur le sous - échantillon (i=1,2)
M le nombre de classes ( = 1, … , )
4. Partitionner les exemples, selon le point de discrétisation, en deux sous -
populations.
Cet algorithme fournit une discrétisation descendante, binaire et dynamique.
Déroulement sur un exemple

Déroulement de l’algorithme CONTRAST sur l’exemple « joué au tennis ? ». Le
tableau suivant regroupe les observations des individus par rapport au jeu :
Numéro Ensoleillement Température Humidité Vent Jouer

1 Soleil 75 70 Oui Oui
2 Soleil 80 90 Oui Non
3 Soleil 85 85 Non Non
4 Soleil 72 95 Non Non
5 Soleil 69 70 Non Oui
6 Couvert 72 90 Oui Oui
7 Couvert 83 78 Non Oui
8 Couvert 64 65 Oui Oui
9 Couvert 81 75 Non Oui
10 Pluie 71 80 Oui Non
11 Pluie 65 70 Oui Non
12 Pluie 75 80 Non Oui
Tableau 2.1. Exemple « Joué au tennis ? ».
On remarque que l’attribut « Température » est un attribut continu, alors on lui

applique la discrétisation selon la méthode CONTRAST. Ce qui suit nous montre
le déroulement de l’algorithme de la méthode CONTRAST :
Etape 1 : classer les exemples d’apprentissage par ordre croissant des valeurs de
l’attribut « Température » :
Dr ATMANI Baghdad 6
64 – 65 – 68 – 69 – 70 – 71 – 72 – 72 – 75 – 75 – 80 – 81 – 83 – 85
Etape 2 : détermination des K points frontières, selon la figure 2.3.
64 65 68 69 70 71 72 72 75 75 80 81 83 85
O N O O O N N O O O N O O N
D1 D2 D3 D4 D5 D6 D7
Figure 2.3. Les K points frontières (Etape2).
Etape 3 : sélectionner parmi les K points frontières celui qui maximise la

quantité ( , , ) :
Pour D1 = 64 :
( ∗ )∗( . )²
( , , )= = 110.42
∗ ( ∗ ) ( ∗ )
Pour D2 = 65 :
( ∗ )∗( . . )²
( , , )= = 205.85
∗ ∗ ( ∗ ) ( ∗ )
Pour D3 = 70 :
( ∗ )∗( . . )²
( , , )= = 352.42
∗ ∗ ( ∗ ) ( ∗ )
Pour D4 = 72 :
( ∗ )∗( . . )²
( , , )= = 468.74
∗ ∗ ( ∗ ) ( ∗ )
Pour D5 = 75 :
( ∗ )∗( . . )²
( , , )= = 460.96
∗ ∗ ( ∗ ) ( ∗ )
Pour D6 = 80 :
( ∗ )∗( )²
( , , )= = 361.64
∗ ∗ ( ∗ ) ( ∗ )
Pour D7 = 83 :
( ∗ )∗( . )²
( , , )= = 205.85
∗ ∗ ( ∗ )
On sélectionne le D4 point frontière parce que c’est lui qui maximise le plus la
quantité ( , , ).
Etape 4 : partitionnement des exemples, selon le point de discrétisation D4, en
deux sous-populations. La figure 2.4 nous montre les exemples après partition.
Dr ATMANI Baghdad 7
64 65 68 69 70 71 72 72 75 75 80 81 83 85
S1 D4 S2
Figure 2.4. Le partitionnement, selon le 1er point de discrétisation D4.
Ou,
S1 : la première sous-population.
S2 : la deuxième sous-population.
Etape 5 : Refaire l’étape 3 à 5 pour chacune des deux sous-populations obtenues.
La figure 2.5. Nous montre les points de discrétisation obtenus, après avoir
appliqué le même processus à chacune des deux sous populations S1 et S2. Le
processus s’arrête dés qu’aucun point frontière ne peut augmenter la
quantité ( , , ).
64 65 68 69 70 71 72 72 75 75 80 81 83 85
<68.5 68.5-70.5 70.5-72 72-77.5 77.5-84 >84
Figure 2.5. Les intervalles obtenus après application de la méthode

CONTRAST sur un attribut continu.
On refait les mêmes étapes pour l’attribut continu « Humidité », on

obtient le tableau suivant après discrétisation :

1 Soleil 72-77.5 <72.5 Oui Oui
2 Soleil 77.5-84 82.5-90 Oui Non
3 Soleil >84 82.5-90 Non Non
4 Soleil 70.5-72 >90 Non Non
5 Soleil 68.5-70.5 <72.5 Non Oui
6 Couvert 70.5-72 82.5-90 Oui Oui
7 Couvert 77.5-84 72.5-79 Non Oui
8 Couvert <68.5 <72.5 Oui Oui
9 Couvert 77.5-84 72.5-79 Non Oui
10 Pluie 70.5-72 79-82.5 Oui Non
Dr ATMANI Baghdad 8
11 Pluie <68.5 <72.5 Oui Non

12 Pluie 72-77.5 79-82.5 Non Oui
13 Pluie <68.5 79-82.5 Non Oui
14 Pluie 68.5-70.5 >90 Non Oui
Tableau 2.2. Exemple « jouer au tennis ? » après application de la

méthode CONTRAST.
2.3.3 Méthode utilisant une mesure d’entropie (algorithme MDLPC)

U. M. Fayyad et K. B. Irani propose une méthode de discrétisation
binaire dynamique récursive utilisant le Gain d’Information associé à un critère
d’arrêt basé sur le MDLPC (Minimum Description Lenght Principale Cut)
[Fayyad 93]. Le domaine de définition D est découpé, lors de la construction du
graphe, en deux intervalles qui sont à leur tour découpés chacun en deux
intervalles, et ainsi de suite jusqu’à une certaine condition d’arrêt. Un même
attribut ne sera discrétisé et n’apparaîtra qu’une seule fois au cours de la
construction du graphe. Ainsi la discrétisation est semi –dynamique.
Le critère de la méthode MDLPC

Se critère permet de choisir l’hypothèse qui a une probabilité maximale
ce qui revient a sélectionné l’hypothèse qui a une probabilité « de faire une
mauvaise décision minimale »
Le critère est calculé de la manière suivante :
log ( − 1) ∆( , , )
( , , )> +
Avec
L’échantillon ou sommet considéré
L’effectif de l’échantillon , ( )=
Le sous - échantillon composé des exemples tels que = {ω ∈ s ; X(ω) ≤ d}
Le sous - échantillon composé des exemples tels que = {ω ∈ s; X (ω) > }
L’effectif du sous - échantillon (i = 1,2)
Le nombre de classes ( = 1, … , )
, , Les m classes d’effectif . sur
Dr ATMANI Baghdad 9
Le nombre de classes présentes dans le sous - échantillon (i = 1,2)

( , , ) = ( )− , ( )
. .
( )=− ∗ log
.
, ( )= ∗ − ∗ log
. .
∆( , , ) = log (3 − 2) − ( ( )− ( )− ( ))
A titre complémentaire, il est intéressant de noter que J. R. Quinlan
préconise à l’heure actuelle de discrétiser non plus selon le critère du Ratio de
Gain, mais d’utiliser le Gain et un critère basé sur le principe du MDL [Quinlan
96].
L’algorithme basé sur le critère du MDLPC

1. Initialisation en classant les exemples d’apprentissage par ordre croissant des
valeurs de l’attribut X à discrétiser.
2. Détermination des k points frontière Par définition, les points de discrétisation
sont nécessairement des points frontières.
3. Sélectionner parmi les k points frontière celui qui maximise le gain
d’information ( , , ) et qui vérifie le critère du MDLPC.
4. Partitionner les exemples, selon le point de discrétisation, en deux sous -
populations.
5. ← + 1
6. Recommencer les étapes 3 à 5, sur chacune des deux nouvelles sous -
populations. Le processus s’arrête dès que plus aucune bi - partition n’est
possible.
La méthode MDLPC est donc une méthode contextuelle, binaire, semi -
dynamique, récursive et descendante. En effet, au départ il n’y a aucun point de
discrétisation, les exemples constituent un seul intervalle. Puis sont déterminées
récursivement des partitions binaires, où chaque intervalle est divisé en deux sous
- intervalles. L'intérêt de cette approche, outre l'apport de la notion de points
frontière, réside dans la définition du critère d'arrêt de la discrétisation.

Nous allons dérouler la méthode MDLPC sur un échantillon
d’apprentissage « Achat », qui est représenté par le tableau 2.3 suivant :
Numéro Age Revenu Etudiant Crédit Achat

1 26 Élevé Non Bon Non
2 28 Élevé Non Excellent Non
3 31 Élevé Non Bon Oui
4 41 Moyen Non Bon Oui
Dr ATMANI Baghdad 10
5 43 Faible Oui Bon Oui

6 45 Faible Oui Excellent Non
7 33 Faible Oui Excellent Oui
8 27 Moyen Non Bon Non
9 29 Faible Oui Bon Oui
10 42 Moyen Oui Bon Oui
11 30 Moyen Oui Excellent Oui
12 35 Moyen Non Excellent Oui
13 39 Élevé Oui Bon Oui
14 44 Moyen Non Excellent Non
Tableau 2.3. Exemple « Achat ».
On remarque que l’attribut « Age » est continu, donc on lui applique la

discrétisation par l’algorithme MDLPC, Les étapes à suivre :
 Etape 1 : Classer les exemple d’apprentissage de l’attribut age par ordre
croissant :
26 – 27 – 28 – 29 – 30 – 31 – 33 – 35 – 39 – 41 – 42 – 43 – 44 - 45
 Etape2 : Déterminer les k points frontières, voir figure 2.6.
calcul de l’entropie :
Info (9,5) = 0.94
26 – 27 – 28 29 – 30 – 31 – 33 – 35 – 39 – 41 – 42 – 43 44 – 45
N N N O O O O O O O O O N N
28.5 43.5
Figure 2.6. Etape2
 Etape3 : Sélectionner parmi les k points frontières celui qui maximise le

gain
d’information Gain (X, d, S) et qui vérifie le critère du MDLPC.

5  3 3 2 2  9 9 9
Info x, d(s) = *   log 2  log 2    log 2   0.34
14  5 5 5 5  14  9 9
Gain = 0.94 − 0.34 = 0.62.
D1: 28.5
( − 1) ∆( , , )
+
(14 − 1)
=
14
2 2 9 9 3 3
(3 − 2) − 2 ∗ 0.94 − 2 ∗ + −1∗
5 5 9 9 5 5
+
14
= 0,22.
D2 : 43.5
( − 1) ∆( , , )
+
(14 − 1)
=
14
3 3 9 9 2 2
(3 − 2) − 2 ∗ 0.92 − 2 ∗ + −1∗
5 5 9 9 5 5
+
14
= 0,09.
On prend celui qui maximise le gain c'est-à-dire : « D2 : 43.5 ».

 Etape4 : On partitionne l’échantillon en deux sous population S1 et S2,
voir figure 2.7.
S1 S2
26 – 27 – 28 29 – 30 – 31 – 33 – 35 – 39 – 41 – 42 – 43 44 – 45
43.5
Figure 2.7. Etape 4.
 Etape5: k  2 .
 Etape6 : Refaire l’étape 3 à 5, voir figure 2.8.
S3 S1 S2
26 – 27 – 28 29 – 30 – 31 – 33 – 35 – 39 – 41 – 42 – 43 44 – 45
]- ;28,5 [ [28.5 ; 43.5] [28.5 ;   [
Figure 2.8. Etape6.

Le processus s’arrête car on ne peut plus partitionner les sous échantillon S21 et
S22 puisque les exemples appartiennent à la même classe.
L’attribut « âge » sera divisé en 3 intervalles :] − ,28,5 [ − [28.5, 43.5] −
[43.5,   [. Le tableau 2.4 illustre se changement :
numéro âge revenu étudiant crédit Acaht

1 <28.5 Élevé Non Bon Non
2 <28.5 Élevé Non Excellent Non
3 28.5-43.5 Élevé Non Bon Oui
4 28.5-43.5 Moyen Non Bon Oui
5 28.5-43.5 Faible Oui Bon Oui
6 >43.5 Faible Oui Excellent Non
7 28.5-43.5 Faible Oui Excellent Oui
8 <28.5 Moyen Non Bon Non
9 28.5-43.5 Faible Oui Bon Oui
10 28.5-43.5 Moyen Oui Bon Oui
11 28.5-43.5 Moyen Oui Excellent Oui
12 28.5-43.5 Moyen Non Excellent Oui
13 28.5-43.5 Élevé Oui Bon Oui
14 28.5-43.5 Moyen Non Excellent Non
Tableau 2.4. Exemple « Achat » après application de la méthode MDLPC.
2.4 Apprentissage non supervisé
Contrairement à l’apprentissage supervisé, dans le cadre du non

supervisé la variable à prédire Y n’est pas explicite dans les données, le non
supervisé se base essentiellement sur les variables prédictives Xi.
L’objectif de la fouille de données non supervisé est donc de trouver
des relations entre caractéristiques (variables prédictifs) suffisamment
significatives et permettant d’augmenter les connaissances du domaine étudié
[AZE 03].
Dans la discrétisation il existe d’autres méthodes basées sur le non
supervisé, car le principe du découpage ne se base pas sur la notion de variable à
prédire (variable classe) et se fait selon certains critères. Dans ce qui suit nous
allons voir quelques méthodes de discrétisation non supervisées
2.5 Les méthodes de discrétisation non supervisées
Parmi les différentes méthodes de discrétisation non supervisée nous allons

présenter deux d’entre elles, qui sont les suivantes:
 La méthode des quantiles
 La méthode égale amplitude
2.5.1 La méthode des quantiles ("des effectifs égaux")

Elle appartient à la famille des méthodes de discrétisation statistiques
ou probabilistes. Cette méthode retient des effectifs égaux dans chaque classe.
Algorithme des effectifs égaux

Remarquez qu’ici la classe représente l’intervalle, et N nombre d’individus a
traités.
Premier calcul:
n
effectif total N 
nombre de classes
n  nombre d ' individus par classe

Deuxième calcul: Calcul des limites de classes. On détermine les limites de
classes en comptant le nombre d'individus de chaque classe dans la distribution
ordonnée.
Le critère visé est l'équirépartition, c'est à dire le même nombre de
données par classe. Dans la version stricte, à partir du nombre N de données et du
nombre n classes, on en déduit le nombre F d'individus par classe. On trie les
données par ordre croissant et on met dans la classe 1 les F premières données,
dans la classe 2 les F suivantes etc. Dans la version relâchée, on met
éventuellement plus de F données par classe car on force les données égales à
être dans une même classe. Voici ce que cela donne sur un exemple de 6 valeurs
avec 2 classes :
Données 10 11 12 12 13 14
Version stricte 1 1 1 2 2 2
Version relâchée 1 1 1 1 2 2
Tableau 2.5 table des résultats de la discrétisation par la méthode des quantiles
Cette méthode permet de faire des groupes équilibrés et apporte un

maximum d'information (autant d'individus pour chaque classe), mais elle ignore
les particularités de la distribution, regroupe des individus très éloignés (par
exemple les dix premiers, puis les dix suivants, etc.) et elle est d'amplitude
inégale.
La méthode des quantiles est conseillées lorsque la distribution :
- N'offre pas de seuils nets.
- Est uniforme (mais également normale).
- Contient des valeurs douteuses

Nous allons dérouler la méthode des quantiles ("des effectifs
égaux") sur l’exemple « jouer au tennis ? » qui est représenter par le tableau 2.1,
et on va l’appliquer plus précisément sur la variable (attribut) « Température » :
On prendra le nombre de classes (d’intervalles) égale à 7, et on sait que
l’effectif total est égal à 14, ainsi :
Etape 1 : on calcul le nombre d’individus par classe :
14
n   2
7
Etape2 : classer les exemples d’apprentissage par ordre croissant des valeurs de
l’attribut « Température », puis choisir les points de discrétisation selon le
nombre n ici est égal à 2. Comme le montre la figure suivante
64 – 65 – 68 – 69 – 70 – 71 – 72 – 72 – 75 – 75 – 80 – 81 – 83 – 85
Figure 2.9. Classement des exemples par ordre croissant et les points de
discrétisation.
Sur l’attribut « Température » qu’on soit dans la version stricte ou

relâché on obtiendra le même résultat. Le tableau 2.6 montre le résultat de
l’application de la méthode avec la version relâchée, on applique le même
procédé a l’attribut « Humidité »:

1 Soleil 72-75 ≤70 Oui oui
2 Soleil 75-81 85-90 Oui Non
3 Soleil >81 80-85 Non Non
4 Soleil 71-72 >90 Non Non
5 Soleil 65-69 ≤70 Non Oui
6 Couvert 71-72 85-90 Oui Oui
7 Couvert >81 70-78 Non Oui

8 Couvert ≤65 ≤70 Oui Oui
9 Couvert 75-81 70-78 Non Oui
10 Pluie 69-71 78-80 Oui Non
11 Pluie ≤65 ≤70 Oui Non
12 Pluie 72-75 78-80 Non Oui
13 Pluie 65-69 78-80 Non Oui
14 Pluie 69-71 >90 Non Oui
Tableau 2.6. Exemple « jouer au tennis ? » après application de La

méthode des quantiles.
2.5.2 La méthode égale amplitude ("Classe égale entendue")

Cette méthode appartient à la famille des méthodes de discrétisation
mathématique, ou sa progression est à intervalle constant.
On garantit ici que le critère d'égalité d'amplitude de classe est respecté,
l'amplitude étant la différence entre la plus grande valeur et la plus petite valeur.
Y min
A partir du minimum global des données et du maximum global
Y min
des données on calcule les bornes de classe à l'aide d'une simple
progression arithmétique.
Elle caractérise des classes de pas constant contenant un nombre d'unités
statistiques variables.
Algorithme classe égale amplitude

1. Comme première étape, c’est de calculer l’étendue de chaque classe :
e
Y max  Y  min 
K
Où
e est l'étendue de chaque classe ;
Y max est la valeur maximale de l'effectif ;
Y min est la valeur minimale de l'effectif ;
K est le nombre de classes.
2. Deuxième étape, définition des classes (intervalles) :
- La 1ère classe vaut Y min ;Y min  e
- La 2e classe vaut Y min  e; Y min  2e


- La Kéme classe vaut

Y min  K  1 * e; Y min  K * e
Avec
Y min  K * e  Y max
Cette méthode permet de faire des paliers "ronds" mais peut aussi causée les
risques suivant :
o Si la distribution est discontinue => risque de classes vides.
o Si la distribution est asymétrique => effet de masse en début ou fin de
distribution.
o Si la distribution est normale => effet de masse au centre de la
distribution.
Cette méthode est Conseillées lorsque :
o La distribution est relativement uniforme ou normale.
o Le Min et le Max sont significatifs

Toujours sur le même échantillon d’apprentissage, à savoir « jouer au
tennis ? ». On applique la méthode sur l’attribut « Température » :
On prendra le nombre de classes (d’intervalles) égale à 7, le déroulement se fait
comme suit :
Etape 1 : on calcul l'étendue de chaque classe:
85  64
e   3
7
Etape 2 : si le choix du nombre d’intervalle est 7, alors on obtiendra 6 points de
discrétisation. En appliquant le principe de la méthode on obtient alors :
1ér point de discrétisation = 64 + 1 * 3 = 67.
2éme point de discrétisation = 64 + 2 * 3 = 70.
5éme point de discrétisation = 64 + 5 * 3 =79.
Le tableau 2.7 suivant montre le résultat de l’application de la méthode sur
l’exemple « jouer au tennis ? », on applique le même procédé à l’attribut
« Humidité » :

1 Soleil 73-76 69-73 Oui oui
2 Soleil 79-82 >89 Oui Non
3 Soleil >82 81-85 Non Non
4 Soleil 70-73 >89 Non Non

5 Soleil 67-70 69-73 Non Oui
6 Couvert 70-73 >89 Oui Oui
7 Couvert >82 77-81 Non Oui
8 Couvert ≤67 ≤69 Oui Oui
9 Couvert 79-82 73-77 Non Oui
10 Pluie 70-73 77-81 Oui Non
11 Pluie ≤67 69-73 Oui Non
12 Pluie 73-76 77-81 Non Oui
13 Pluie 67-70 77-81 Non Oui
14 Pluie 67-70 >89 Non Oui
Tableau 2.7. Exemple « Joué au tennis ? » après application de la

méthode égale amplitude.
2.6 Conclusion
Nous avons présenté dans ce chapitre plusieurs méthodes de

discrétisation, le choix de la méthode dépend du modèle qui va être utilisé dans
l’extraction de connaissance a partir de données mais aussi de l’intérêt qu’a
l’ingénieur de la connaissance pour une certaine méthode. Cependant discrétiser
est souvent synonyme d’une perte d’informations et perte d’objectif, donc pour
obtenir de bons résultats il faut savoir appliquer la méthode qui minimise cette
perte et conserve les caractéristiques essentielles présentées par les données.
En termes de performance chaque méthode à ses points forts et ses
points faibles, et la comparaison de ces méthodes peut être faite à l’aide des bases
de données réelles et des jeux de données fictifs.
Bibliographie
[Hyperge] Hyperge, « Discrétisation »,

http://www.hypergeo.eu/spip.php?article374.
[Gilles hunault] Gilles hunault, « Découpage en classes et discrétisation »,

http://www.info.univ-angers.fr/pub/gh/.
[MIC 83] MICHALSKI R. S, « Theory and Methodology of Inductive Learning »,

MICHALSKI R. S., CARBONNEL J. G., MITCHELL T. M., Eds., Machine
Learning : An Artificial Intelligence Approach, vol. 1, p. 83–134, Morgan
Kaufmann, 1983.
[DOU 95] DOUGHERTY J, KOHAVI R, SAHAMI M, « Supervised and unsupervised

discretization of continuous attributes », Machine Learning : Proceedings
of the 12th International Conference (ICML-95), Morgan Kaufmann, 1995,
p. 194–202.
[FAB 02] Fabrice Muhlenbach, Ricco Rakotomalala, « Utilisation d’amas pour la

discrétisation de variables », Laboratoire ERIC 2002.
[ZIG 99] ZIGHED D. A, SEBBAN M, « Sélection et validation statistique de

variables et de prototypes », SEBBAN M., VENTURINI G., Eds.,
Apprentissage automatique, Hermès Science, 1999.
[Kerber 92] R. KERBER, « ChiMerge : Discretization of numeric attributes ». AAAI 92

10th National Conference on Artificial Intelligence. 1992. pages 123-128.
[ZIG 98] Zighed D.A, Rabaseda S, Rakotomalala R, « Fusinter: a Method for

discretization of continuous attributes for supervised learning »,
International Journal of Uncertainty, Fuzzinzss and Knowledge-Based
Systems, 307-326.
[Van 93] T. VAN DE MERCKT, « Decision Trees in Numerical Attribute Spaces ».

Procceedings of the 13th International Joint Conference on Artificial
Intelligence. 1993. pages 1016-1021.
[Fayyad 93] U.M. FAYYAD, K.B. IRANI, « Multi-Interval Discretization of

Continuous-Valued Attributes ». Proceedings of the 13th International
Conference on Artifcial Intelligence. 1993. pages 1022-1027.
[Quinlan 96] J.R. QUINLAN, « Improved Use of Continuous Attributes in C4.5 ».

Journal of Artificial Intelligence Research. 1996. 4, pages 77-90.
[AZE 03] JEROME AZE, « Extraction de connaissance a partir de données

numériques et textuelles ». 2003, page 2-3.
[Atm, 07a] Neuro-IG

2 IRAD - FD - Chap2

Transféré par

Droits d'auteur :

Formats disponibles

2 IRAD - FD - Chap2

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

2 IRAD - FD - Chap2

Transféré par

Droits d'auteur :

Formats disponibles

Discrétisation des données numériques

2.1 Introduction ............................................................................................ 1

2.2 L’apprentissage supervisé ....................................................................... 2

2.3 Les méthodes de discrétisation supervisée .............................................. 3

2.3.2 Méthode CONTRAST 5

2.3.3 Méthode utilisant une mesure d’entropie (algorithme MDLPC)............................ 9

2.4 Apprentissage non supervisé ..................................................................13

2.5 Les méthodes de discrétisation non supervisées ....................................14

2.5.2 La méthode égale amplitude ("Classe égale entendue") .................................. 16

2.6 Conclusion ..............................................................................................18

2.1.1 Information qualitative

2.1.2 Information quantitative

2.2 L’apprentissage supervisé

L’approche supervisée est basée sur la notion d’apprentissage automatique

2.3 Les méthodes de discrétisation supervisée

2.3.1 Méthode Hyper Cluster Finder

Algorithme de la méthode Hyper Cluster Finder

Figure 2.1. Graphe de voisinage relatif (GVR).

2. Coupure des arêtes reliant des points de classes différentes afin de

5. Utilisation de ces valeurs minimales et maximales pour définir des

2.3.2 Méthode CONTRAST

Déroulement sur un exemple

Numéro Ensoleillement Température Humidité Vent Jouer

Tableau 2.1. Exemple « Joué au tennis ? ».

On remarque que l’attribut « Température » est un attribut continu, alors on lui

Figure 2.3. Les K points frontières (Etape2).

Etape 3 : sélectionner parmi les K points frontières celui qui maximise la

Figure 2.4. Le partitionnement, selon le 1er point de discrétisation D4.

<68.5 68.5-70.5 70.5-72 72-77.5 77.5-84 >84

Figure 2.5. Les intervalles obtenus après application de la méthode

On refait les mêmes étapes pour l’attribut continu « Humidité », on

Numéro Ensoleillement Température Humidité Vent Jouer

11 Pluie <68.5 <72.5 Oui Non

Tableau 2.2. Exemple « jouer au tennis ? » après application de la

2.3.3 Méthode utilisant une mesure d’entropie (algorithme MDLPC)

Le critère de la méthode MDLPC

Le nombre de classes présentes dans le sous - échantillon (i = 1,2)

L’algorithme basé sur le critère du MDLPC

Déroulement sur un exemple

Numéro Age Revenu Etudiant Crédit Achat

5 43 Faible Oui Bon Oui

Tableau 2.3. Exemple « Achat ».

On remarque que l’attribut « Age » est continu, donc on lui applique la

Figure 2.6. Etape2

 Etape3 : Sélectionner parmi les k points frontières celui qui maximise le

d’information Gain (X, d, S) et qui vérifie le critère du MDLPC.

On prend celui qui maximise le gain c'est-à-dire : « D2 : 43.5 ».

Figure 2.7. Etape 4.

]- ;28,5 [ [28.5 ; 43.5] [28.5 ;   [

Figure 2.8. Etape6.

numéro âge revenu étudiant crédit Acaht

Tableau 2.4. Exemple « Achat » après application de la méthode MDLPC.

2.4 Apprentissage non supervisé

Contrairement à l’apprentissage supervisé, dans le cadre du non

Parmi les différentes méthodes de discrétisation non supervisée nous allons

2.5.1 La méthode des quantiles ("des effectifs égaux")

Algorithme des effectifs égaux

n  nombre d ' individus par classe

Cette méthode permet de faire des groupes équilibrés et apporte un