UNIVERSITE DR « YAHIA FARES » DE MEDEA

Faculté des Sciences

Département de Mathématique et Informatique Année universitaire : 2017-2018

Interrogatoire : Théorie et pratique du Datamining

Exercice 01 (02 pts) : Supposons qu’on veut utiliser des données binaires dans un processus de
clustering. Citer (ou proposer) une (des) mesure(s) de similarité (distance(s)) pour ce type de données.
Evaluer la (les) distance(s) entre les objets X = 0101010001 et Y = 0100011000. Que remarquez-vous ?
Déduisez la distance de Hamming associée. A quoi la valeur trouvée correspond-elle ?

Exercice 02 (03 pts) : Répondez brièvement aux questions suivantes :

1. Que signifie l’élagage et quel est son objectif ?
2. Quelle est la différence entre les techniques descriptives et les techniques prédictives de datamining ?
3. Dans le processus ECD, une phase de préparation des données est nécessaire. Que signifie la
transformation des données ? expliquer en donnant des exemples

Exercice 03 (05 pts) : Soit l’ensemble d’apprentissage ci-dessous. La classe est « Edible ».
N° Shape Color Odor Edible
1 C B 1 Y
2 D B 1 Y
3 D W 1 Y
4 D W 2 Y
5 C B 2 Y
6 D B 2 N
7 D G 2 N
8 C U 2 N
9 C B 3 N
10 C W 3 N
11 D W 3 N
1. En utilisant l’algorithme ID3 et le gain d’information, construire l’arbre de décision du dataset. Donner
les détails des calculs.
2. Déduire de l'arbre trouvé une seule règle comportant 2 disjonctions et 2 conjonctions au maximum.
3. En utilisant l’arbre construit, classer l’instance N°12: Shape=C, Color=G, Odor=2.
4. En utilisant l’ensemble des onze instances, et en supposant que les attributs « Color » et « Odor » sont
des variables énumératives, dites lequel des instances est plus proche de l’instance N° 12 ? quelle est la
distance utilisée ? Que représentent ces calculs (donner le nom de ces calculs) ?
☺ To succeed in life one must have the courage to pursue what he wants ☺

Enseignant : Mr K. Boudjebbour Page 1 / 1

 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématique et Informatique Année universitaire : 2017-2018

Corrigé Interrogatoire : Théorie et pratique du Datamining

Exercice 01 (02,50 Pts): il faut dessiner la table de dissimilarité (contingence) : Y

0,5 Pt
on a trois cas possibles :
1 0
1. Similarité invariante, si toutes les variables sont symétriques (Coefficient de
correspondance simple) :

  1 2 2
D1(X,Y) =
==0,3 0,5 Pt X
2. Similarité non invariante, si toutes les variables sont asymétriques (Coefficient 0 1 5
de Jaccard):

 
D2(X,Y) = = =0,6 0,5 Pt


3. Si les variables sont symétriques et asymétriques : il faut spécifier la nature de chaque variable. 0,25 Pt

0,5 Pt Malgré que D1 et D2 représentent deux distances entre les mêmes instances, on remarque que qu’elles
sont très éloignées car D2=2*D1
Distance de hamming = b+c = 3. Elle représente le nombre de caractéristiques différentes entre x et y. 0,25 Pt
Exercice 02 (03 Pts) :
1. L’élagage est la suppression de quelques sous-arbres dans la l’arbre de décision. Son objectif
principal est la réduction de l’arbre afin d’améliorer le taux d’erreur.
2. les techniques descriptives de datamining visent à mettre en évidence des informations présentes
mais cachées par le volume de données alors que les techniques prédictives visent à extrapoler de
nouvelles informations à partir des informations présentes. Elles se basent essentiellement sur des
modèles qui utilisent des données présentes ou passées pour construire des scénarios futurs.
3. La transformation des données est la transformation d’un attribut A en une autre variable A’ qui
serait selon les objectifs de l’étude, plus appropriée.
Exp 1 : Variable continue en variable discrète et vice versa
Exp 2 : La construction d’agrégats par exemple, le prix au mètre-carré d’un appartement
Exercice 03 (05,50 Pts):
 
1) On calcul l’entropie sur l’ensemble des données : I(5,6)= - log - log = 0,994 0,5 Pt
   
Ensuite on calcul le gain de chaque attribut :

Gain (Shape)= I(5,6)-E(Shape)= I(5,6)-( I(2,3)+
I(3,3))=0,008
 
  
Gain (Color)= I(5,6)-E(Color)= I(5,6)-( I(3,2)+ I(2,2)+ I(0,1)+ I(0,1)=0,189
   
 
Gain (Odor)= I(5,6)-E(Odor)= I(5,6)-( I(3,0)+ I(2,3)+ I(0,3))=0,553
  
Donc on choisit l’attribut « Odor » avec le gain le plus grand (Gain=0.553) qui représente le nœud la
racine de l’arbre, Donc l’arbre initial sera : Odor 1 Pt
2 3
1
????? N
Y
Instances : 4,5,6,7,8 Instance : 9,10,11
Instances : 1,2,3 Page 1 / 2
 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématique et Informatique Année universitaire : 2017-2018
La valeur Odor = 2 donne plusieurs valeurs de l’attribut classe, donc, il faut refaire le même travail
(calcul du gain) pour l’ensemble des données S2 ={4,5,6,7,8}. I(S2) =I(2,3)=0,971
   
Gain (S2, Color)= I(2, 3)-E(S2, Color)=0,971-( I(1,0) + I(1,1)+ I(0,1)+ I(0,1))=0,571
 
Gain (S2, Shape)= I(2, 3)-E(S2, Shape)=0,971-( I(1,2) + I(1,1))=0,020
Donc on choisit l’attribut « Color» avec le gain le plus grand (Gain=0,571). On aura deux branches
avec des nœuds terminaux et la branche B qui sera nécessairement départagée par le seul attribut
restant à savoir «Shape» et l’arbre final sera : Odor
2 3
1
Color N
Y Instance : 9,10,11
B G ou U W Instances : 1,2,3

Shape N Y 1 Pt
C D Instances : 7,8 Instance : 4

Y N
Instance : 5 Instance : 6
2) La règle qu’on peut déduire est :
(Odor = 1) ⋁ ((Odor = 2) ∧ ((Color = W) ⋁ ((Color = B) ∧ (Shape = C))) 1 Pt
3) La classe est : N 0,25 Pt
4) Il faut calculer la distance entre l’instance N°12 et les 11 autres instances :
D(X,Y)=D1(Xi,Yi) + D2(Xi,Yi)
D1(Xi,Yi)= (P-M) / P tel que : P est le nombre total d’attributs et M le nombre de ressemblance
Qui concerne les deux attributs énumératifs « Odor » et « Color »
D2(Xi,Yi)= 0 si Xi = Yi ; 1 sinon Concerne l’attribut binaire « Shape » 01 Pt

N° Instance D1 D2 D N° Instance D1 D2 D
1 1 1 2 7 0,5 0 0,5
2 1 0 1 8 0 1 1
3 1 0 1 9 1 1 2
4 0,5 0 0,5 10 1 1 2
5 0,5 1 1,5 11 1 0 1
6 0,5 0 0,5
Donc, les instances les plus proches de l’instance N°12 sont : l’instance N° 4, N° 6 et N° 7. 0,25 Pt
La distance utilisée est la distante mixte entre deux type d’attributs (dans notre cas, on a utilisé la
distance de Manhattan) qui représente un calcul de similarité entre instantes afin d’appliquer une
méthode de clustering. 0,5 Pt

Page 2 / 2