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

Université Ghardaïa
Faculté des Sciences et de la Technologie
Département des Mathématiques et d’Informatique

Concours d’accès à la formation de troisième cycle en vue de l’obtention du diplôme de

doctorat au titre de l’année universitaire 2021-2022
Filière : Informatique
Spécialité : Systèmes Intelligents et Apprentissage Automatique

Module : Apprentissage Automatique Durée : 02 heures Coefficient : 3

Exercice 1. — Arbres de décision (04 points)

Considérons le tableau suivant, qui présente un ensemble d’apprentissage tiré aléatoirement
d’une base de données d’achats des clients d’une entreprise.
Id Âge Salaire Étudiant A acheté
1 Petit Haut Non Non
2 Petit Haut Non Non
3 Moyen Haut Non Oui
4 Sénior Moyen Non Oui
5 Sénior Bas Oui Oui
6 Sénior Bas Oui Non
7 Moyen Bas Oui Oui
8 Petit Moyen Non Non
9 Petit Bas Oui Oui
10 Sénior Moyen Oui Oui
11 Petit Moyen Oui Oui
12 Moyen Moyen Non Oui
13 Moyen Haut Oui Oui
14 Sénior Moyen Non Non
On veut construire un arbre de décision pour prédire la classe (A acheté) d’un nouvel client, en
se basant sur ce tableau. Utiliser la technique du gain d’information pour choisir l’attribut à la racine de
l’arbre.
Où : m est le nombre de classes présentes dans D, v est le nombre de valeurs distinctes d’un attribut A.
Q.1.— En utilisant le gain d’information maximal, déterminer uniquement l’attribut racine de
l’arbre (ayant le maximum de gain) puis en déduire l’arbre final sans faire de calculs
supplémentaires.
Q.2.— Utiliser l’arbre de décision construit pour classifier et calculer la précision sur l’ensemble
de test suivant :
Id Âge Salaire Étudiant A acheté
1 Petit Haut Non Non
2 Sénior Bas Oui Non
3 Moyen Bas Oui Oui
4 Petit Bas Oui Oui
5 Moyen Moyen Non Oui
6 Sénior Moyen Non Non

1/3
 mme pour les forêts aléatoire, on utilise OOB (Out Of Bag) dans le Bagging, :
our prévenir le sur-apprentissage.
On choisit une Branche B là où l’erreur se stabilise et ne descend plus.
’erreur est calculée avec les données de l’échantillon de Bootstrap.
mme pour les forêts aléatoire, on utilise OOB (Out Of Bag) dans le Bagging, :
NB le
our prévenir : sur-apprentissage.
On choisit une Branche B là où l’erreur se stabilise et ne descend plus.
’erreur est calculée avec les
L’information données
avant de l’échantillon
le partitionnement de Bootstrap.
d’un ensemble D
démarrage à froid est :
ne technique pour éviter le sur-apprentissage.
tiliser dans le systèmes de recommandations
L’information pouren
après le partitionnement prédire sans
utilisant connaissance
un attribut un A préalable.
roblème rencontrer dans la phase d’apprentissage dans le filtrage collaboratif.
démarrage à froid est :
ne technique pourGain d’information
éviter le sur-apprentissage. Info (D) – InfoA(D)
tiliser dans le systèmes de recommandations pour prédire sans connaissance préalable.
roblème rencontrer dans la phase d’apprentissage dans le filtrage collaboratif.
Exercice 2. — Support Vector Machines (07 points)
e 2 : SVM ((8 points)
dère ici un problème de classification binaire vers ! = {−%, +%} de données dans un espace de
On considère ici un problème de classification binaire vers 𝑌 = {−1, +1} de données dans un
on * + ℝ! . On note {(." , /" ) + (*, !)], 2 + {%,!. . . , 4} l’ensemble" d’apprentissage
" considéré.
espace de description 𝑋𝜖𝑅 . On note {,𝑥 , 𝑦 /𝜖(𝑋, 𝑌), 𝑖𝜖{1, . . . , 𝑛} l’ensemble d’apprentissage
on de décision du classifieur considéré par 5#,% (.) = 6274 (8& . + 9).
considéré. La fonction de décision du classifieur considéré par 𝑓#,% (𝑥) = 𝑠𝑖𝑔𝑛(𝑤 & 𝑥 + 𝑏).
dère dans un premier temps un
On considère ensemble
dans de données
un premier temps linéairement
un ensembleséparable.
de données Cet linéairement
ensemble de séparable. Cet
et la frontièreensemble de données
sont représentés et la
(en 2D) frontière
sur la figuresont
1. représentés (en 2D) sur la Figure 1.

A
w
"
:

B Figure 1 – Ensemble de données

linéairement séparables

Figure
Sur 1 – figure,
cette Ensemble de données
l’échantillon 𝑥 "linéairement "
et le label 𝑦séparables
est représenté par le point A. On s’intéresse à sa
"
distance signée 𝛾 à la fonction 2/7de décision (dont le point le plus proche est représenté en B sur la
figure).

Partie 1 : Formulation du SVM (partie 1 sur 04 points)

Q.1.1.— Sachant que 𝑤/‖𝑤‖ est un vecteur unitaire orthogonal à la frontière de décision.
Donner l’expression de la fonction de minimisation primale en fonction de 𝑥 " , 𝑦 " , 𝑤 et 𝑏.
Q.1.2.— Proposer, selon les conditions de Karush-Kuhn-Tucker (KKT), une formulation duale à
base de Lagrangien afin de résoudre ce problème d’optimisation quadratique de la question
Q.1.1
Q.1.3.— Donner la solution analytique de la minimisation de ce Lagrangien selon les paramètres
𝑤 et 𝑏.
Q.1.4.— Donner la fonction de décision (classification) optimale obtenue après optimisation de
cette formulation duale du SVM qu’on notera 𝑓(𝑥).
Q.1.5.— Interpréter les résultats dans les cas suivants : 𝑓(𝑥) = 0, 𝑓(𝑥) > 0, 𝑓(𝑥) < 0,
𝑓(𝑥) = +1 et 𝑓(𝑥) = −1 .
Q.1.6.— Que cela implique-t-il si l’on souhaite éloigner au maximum (au sens géométrique) les
points de la frontière de décision ?
Q.1.7.— D’après les conditions de Karush-Kuhn-Tucker (KKT) concernant les propriétés de la
solution optimale d’un Lagrangien, on a : 𝛼" ,𝑦 " ,𝑤 & 𝑥 " + 𝑏/ − 1/ ≥ 0, ∀𝑖𝜖{1. . 𝑁} Qu’en déduire
pour les paramètres 𝛼" obtenus à l’optimum ?
Q.1.8.— Quel rapport y a-t-il entre les 𝛼" et les vecteurs supports de vecteurs.

2/3