UNIVERSITE DR « YAHIA FARES » DE MEDEA

Faculté des Sciences

Département de Mathématiques et Informatique Année universitaire : 2018-2019
Date : 24/01/2019

EFS S1 : Théorie et pratique du Datamining

Exercice 01 (06 Pts) : Soit un ensemble de données X représenté par les valeurs suivantes :
X 1 2 9 12 20
a) Effectuer une Classification Hiérarchique Ascendante sur l’ensemble X en utilisant la distance
de Manhattan entre instances et la distance minimale (single link method) entre clusters.
Il faut spécifier :

Le tableau des distances à chaque regroupement d’instances ou de clusters (chaque itération).

Les données regroupées à chaque étape.

Le dendrogramme obtenu.
b) On aimerait maintenant voir la qualité de ces regroupements. Calculer l’inertie intra-cluster
pour un regroupement en 2 et en 3 clusters, quelle est le meilleur regroupement ?.

Exercice 03 (08 Pts) : Beaucoup de personnes ont des problèmes de colon qui peuvent affecter leur vie
quotidienne. Pour déterminer si une personne a une colopathie fonctionnelle, on considère les trois
facteurs : Degré de Stress quotidien (DegStr), Nombre d’heures du sommeil par rapport la norme
(HrSom) et fumeur (Fum). Le tableau ci-après représente un échantillon d’une base de données :

Instance DegStr HrSom Fum Colopathie

01 Petit Moins Non Yes
02 Petit Moins Oui Yes
03 Petit Egal Non No
04 Petit Egal Oui No
05 Petit Supérieur Non No
06 Petit Supérieur Oui Yes
07 Normal Moins Non Yes
08 Normal Moins Oui Yes
09 Normal Egal Non No
10 Normal Egal Oui No
11 Normal Supérieur Non No
12 Normal Supérieur Oui Yes
13 Fort Moins Non Yes
14 Fort Moins Oui Yes
15 Fort Egal Non No
16 Fort Egal Oui Yes
17 Fort Supérieur Non Yes
18 Fort Supérieur Oui Yes

Enseignant : Mr K. Boudjebbour Page 1 / 2

 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématiques et Informatique Année universitaire : 2018-2019
1. En se basant sur les 18 instances ci-dessus, appliquez la fonction gain basée sur l'entropie pour
construire l’arbre de décision correspondante à ces instances.
2. Traduire cet arbre en une seule règle optimisée.
3. Construisez la matrice de confusion associée à l’ensemble test suivant en déduisant le taux
d’erreur :

Instance DegStr HrSom Fum Colopathie

19 Petit Supérieur Oui Yes
20 Fort Supérieur Non Yes
21 Petit Egal Non No
22 Fort Egal Non Yes
23 Normal Supérieur Oui No
24 Petit Egal Oui No

Calculer la précision et la spécifité. Que représentent réellement ces deux indicateurs dans ce
problème (leur signification)?
4. En utilisant l’ensemble des dix huit instances, classez les 18 instances du plus proche de
l’instance 19 au plus loin en mentionnant les distances entre chaque instance et l’instance 19
(Précisez les formules des distances utilisées) ?

Exercice 03 (06 Pts) : En utilisant l’algorithme Apriori, générer les règles d’associations de support
minimum = 2 et d’une confiance ≥ 60 % pour la base des transactions suivante :
Transaction item
T1 A, C, D
T2 B, C, E
T3 A, B, C, E
T4 B, E
T5 A, C, E

- Qu’es ce qu’un itemset fréquent fermé et maximal ? donner des exemples de cet exercice.

☺ Un tiens dans la main vaut mieux que deux tu l'auras ☺

☺ A bird in the hand is worth two in the bush ☺

☺ ‫ﻋﺼﻔﻮر ﰲ اﻟﻴﺪ ﺧﲑ ﻣﻦ ﻋﴩة ﻋﲆ اﻟﺸﺠﺮة‬ ☺

Enseignant : Mr K. Boudjebbour Page 2 / 2

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

Corrigé type EFS S1 : Théorie et pratique du Datamining

Exercice 01 (06 Pts) :

a) Appliquer la classification hiérarchique ascendante sur l’ensemble X
X 1 2 9 12 20
On va utilisé la distance de Manhattan entre instances : D(X,Y) = ∑ | − |
Et la distance minimale entre toutes les paires de données des 2 clusters (single link method) :
DSingle(i,j) = Minx€i y€j D(X,Y) 0,5 Pt
Les tableaux suivants représentent les différentes distances DSingle entre différents clusters :
Etape 1 :
1 2 9 12 20
1 1 8 11 19
2 7 10 18  Regroupement des clusters {1} et {2} en {1,2}
9 3 11
12 8
Etape 2 :
1,2 9 12 20
3 Pt 1,2 7 10 18
 Regroupement des clusters {9} et {12} en {9,12}
9 3 11
12 8
Etape 3 :
1,2 9,12 20
1,2 7 18  Regroupement des clusters {1,2} et {9,12} en {1,2,9,12}
9,12 8
Etape 4 :
1,2,9,12 20
 Regroupement des clusters {1,2,9,12} et {20} en {1,2,9,12,20}
1,2,9,12 8
 {1,2,9,12,20} D
Single Dendrogramme :
 {
b) L’inertie intra-cluster IA = ∑
 ∑
 ²(, )
i : instance ; Gk : centroid du groupe k ;
Nk : Nombre d’instance du groupe k
1 Pt
- Un regroupement en 2 clusters :
C1={1,2,9,12}
centroid C1 = 6
C2={20}
centroid C2 = 20
1,5 Pt IA= ((1-6)²+ (2-6)²+ (9-6)²+ (12-6)²)+ (20-20)²=86 Données
- Un regroupement en 3 clusters : 1 2 9 12 20  {1,2
C1={1,2}
centroid C1=1,5 C2={9,12}
centroid C2 = 10,5 et C3={20}
centroid C3 = 20
IA= ((1-1,5)²+ (2-1,5)²)+((9-10,5)²+ (12-10,5)²)+ (20-20)²=5
Donc le meilleur regroupement est celui de 3 clusters car son inertie intra-cluster IA est la plus petite.

Enseignant : Mr K. Boudjebbour Page 1 / 4

 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématiques et Informatique Année universitaire : 2018-2019
Exercice 02 (09 Pts) :

 
1) On calcul l’entropie sur l’ensemble des données : I(11,7)= - log - log = 0,964 0,5 Pt
   
Ensuite on calcul le gain de chaque attribut :
  
Gain (DegStr)= I(11,7)-E(DegStr)=0,964-( I(3, 3)+ I(3,3) + I(5,1))= 0,081
  
  
Gain (HrSom)= I(11,7)-E(HrSom)=0,964-( I(6,0)+ I(1,5) + I(4,2))= 0,441 1 Pt
  
 
Gain (Fum)= I(11,7)-E(Fum)=0,964-( I(4,5)+ I(7,2))= 0,086
 

Donc on choisit l’attribut « HrSom » avec le gain le plus grand (Gain=0.411) qui représente la racine
de l’arbre, Donc l’arbre initial sera : HrSom
Egal 0,5 Pt
Supérieur
Moins
Inst : 5, à 12 ??? Inst : 13 à 18
Yes ???

Les valeurs Egal et Supérieur donnent deux valeurs de la classe, donc, il faut refaire le même travail
(calcul du gain) pour l’ensemble des données SEg={3,4,9,10,15,16} et SSup={5,6,11,12,17,18}.
• I(SEg) =I(1,5)=0,650
  
Gain (SEg, DegStr)= I(1,5)-E(SEg, DegStr)= 0,650-( I(0,2)+ I(0,2) + I(1,1))= 0,317
  
 
1 Pt Gain (SEg, Fum)= I(1,5)-E(SEg, Fum)= 0,650-( I(0,3)+ I(1,2))= 0,191
  HrSom
Donc on choisit l’attribut « DegStr » avec Egal Supérieur
le gain le plus grand (Gain=0.317), et l’arbre devient : Moins
DegStr
???
Petit ou Normal Fort Yes Inst : 13 à 18
or
No Fum
Non Oui
• I(SSup) =I(4,2)=0,919
 No Yes
Gain (SSup, DegStr)= I(4,2)-E(SSup, DegStr)= 0,919-( I(1,1)

 
+ I(1,1)+ I(2,0))= 0,252 HrSom
 
Gain (SSup, Fum)= I(4,2)-E(SSup, Fum) 1 Pt Egal Supérieur
  Moins
= 0,919-( I(1,2)+ I(3,0))= 0,495 DegStr Fum
 
Petit ou Normal Fort Yes Oui Non
Donc on choisit l’attribut « Fum » avec
le gain le plus grand (Gain=0.495), No Fum Yes DegStr
et l’arbre final devient : Non Oui Petit ou Normal Fort
No Yes No Yes
2) Règle :
(HrSom = Moins) ou ((HrSom ≠ Moins) et (DegStr=Fort) et ((Fum=Oui) ou ((Fum=Non) et
(DegStr=Fort)))) 1 Pt

Enseignant : Mr K. Boudjebbour Page 2 / 4

 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématiques et Informatique Année universitaire : 2018-2019
3) On applique l’ensemble test T sur l’arbre de décision et on trouve la classe prédite :

Instance DegStr HrSom Fum Classe réelle Classe prédite

19 Petit Supérieur Oui Yes Yes
20 Fort Superieur Non Yes Yes
21 Petit Egal Non No No
22 Fort Egal Non Yes No
23 Normal Supérieur Oui No Yes
24 Petit Egal Oui No No

• Matrice de 1 Pt
Prédite (Yes) Prédite (No) Total
confusion :
Classe réelle (Yes) 2 1 3
Classe réelle (No) 1 2 3
Total 3 3 6
• Taux d’erreur = b+c / n, Donc le taux d’erreur est : 2/6 = 0,3333 = 33,33 %
0,5 Pt • Précision = a/(a+c) = 66,66 % : représente le pourcentage des colopathies positivement prédites
par rapport aux total des colopathies prédites
0,5 Pt • Spécificité = d/(c+d) = 66,66 % représente le pourcentage des non colopathies positivement

prédite par rapport aux total des non colopathies réelles.

4) Il faut calculer la distance entre l’instance N°19 et les 18 autres instances tel que :
D1(Xi,Yi)= (P-M) / P tel que : P est le nombre total d’attributs (=2) et M le nombre de
ressemblance entre les deux attributs énumératifs « DegStr » et « HrSom »
D2(Xi,Yi)= 0 si Xi = Yi
Concerne l’attribut binaire « Fum »
0,5 Pt 1 sinon
Ensuite, calculer la distance global D avec une distance d’attributs numériques par exemple
avec la distance de manhattan : D(X,Y)= ∑ | − |
Donc : D(X,Y)=D1(Xi,Yi) + D2(Xi,Yi)
Instance 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
D1 0,5 0,5 0,5 0,5 0 0 1 1 1 1 0,5 0,5 1 1 1 1 0,5 0,5
D2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
D 1,5 0,5 1,5 0,5 1 0 2 1 2 1 1,5 0,5 2 1 2 1 1,5 0,5
rang 4 2 4 2 3 1 5 3 5 3 4 2 5 3 5 3 4 2

1,5 Pt

Enseignant : Mr K. Boudjebbour Page 3 / 4

 UNIVERSITE DR « YAHIA FARES » DE MEDEA
Faculté des Sciences
Département de Mathématiques et Informatique Année universitaire : 2018-2019
Exercice 03 (06 Pts) :
- On génère d’abord les itemsets fréquents de support minimum = 2 :
C1 itemset {A} {B} {C} {D} {E}
Card 1

Support 3 3 4 1 4
F1 itemset Oui Oui Oui Non Oui

2 Pt
C2 itemset {A,B} {A,C} {A,E} {B,C} {B,E} {C,E}
Card 2

Support 1 3 2 2 3 3
F2 itemset Non Oui Oui Oui Oui Oui

C3 itemset {A,B,C} {A,B,E} {A,C,E} {B,C,E} C4 itemset {A,B,C,E}

Support / / 2 2 Support /
Card 3

Card 4
F3 itemset Non Non Oui Oui F4 itemset Non
Cause {A,B} non Fréquent {A,B,C}
Cause
non Fréquent
- On génère maintenant les règles d’associations d’une confiance minimale = 60 % pour tout sous
ensembles non vides fréquents :
- Pour l’itemset fréquent {A,C,E}
Règle {A,C}
E {A,E}
C {C,E}
A A
{C,E} C
{A,E} E
{A,C}
Confiance 66,66 % 100 % 66,66 % 66,66 % 50 % 50 % 1 Pt
Conclusion Acceptée Acceptée Acceptée Acceptée Rejetée Rejetée
- Pour l’itemset fréquent {B,C,E}
Règle {B,C}
E {B,E}
C {C,E}
B B
{C,E} C
{B,E} E
{B,C}
Confiance 100 % 66,66 % 66,66 % 66,66 % 50 % 50 % 1 Pt
Conclusion Acceptée Acceptée Acceptée Acceptée Rejetée Rejetée
- Pour les autres itemset
- A
C , A
E sont redondantes par rapport à A
{C,E}
- B
C , B
E sont redondantes par rapport à B
{C,E} 1 Pt

Règle C
A E
A C
B E
B C
E E
C

Confiance 75 % 50 % 50 % 75 % 75 % 75 %
Conclusion Acceptée Rejetée Rejetée Acceptée Acceptée Acceptée

- Un motif fréquent est dit fermé s’il ne possède aucun sur-motif qui a le même support, exp : {A,C} 1 Pt
- Un motif fréquent est dit Maximal si aucun de ses sur-motifs immédiats n’est fréquent, exp:{A,C,E}

Enseignant : Mr K. Boudjebbour Page 4 / 4