Node('A',Node('B',Node('D'),Node('E')),Node('C',None,Node('F')))

Partie 2 : Repr sentation du mod le de d cision

Les r gles de d cision peuvent tre repr sent es par un arbre binaire, appel arbre binaire de d cision.

Par exemple, pour les donn es dapprentissage de la table 1, il est possible de construire larbre binaire

de d cision illustr par la figure 2.

D cision

0.5

{0:0, 1:1}

Tension

91

{0:0.3, 1:0.7}

D cision

0.5

{0:0.2, 1:0.8}

Age

62

{0:0.5, 1:0.5}

Tachycardie

0.5

{0:0.4, 1:0.6}

D cision

0.5

{0:0.1, 1:0.9}

D cision

0.5

{0:0.9, 1:0.1}

Figure 2 : Exemple dun arbre de d cision

Dans cette partie, on propose construire deux classes :

• DecisionNode : classe qui h rite de la classe Node permettant de repr senter un arbre binaire de

d cision ;

• DecisionForest : classe qui repr sente un ensemble darbres, appel e for t.

Description des classes

• Classe DecisionNode :

o Attributs :

(cid:1) label, chaine de caract res, repr sentant lobservation, h rit de la classe Node ;

(cid:1) distr, un dictionnaire repr sentant la probabilit de chaque d cision :

" chaque cl repr sente une d cision possible 0 ou 1 ;

" chaque valeur est un r el repr sentant la probabilit de d cision.

(cid:1) seuil, un r el, repr sentant le seuil de test utilis pour d duire la branche suivre ;

(cid:1) left, instance de la classe repr sentant le fils gauche, h rit de la classe Node ;

(cid:1) right, instance de la classe repr sentant le fils droit, h rit de la classe Node ;

o M thodes :

(cid:1) __init__(&) : permet linitialisation des attributs de la classe DecisionNode, sachant que

cette derni re h rite de la classe Node.

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 3/10

(cid:1) outcome(&) : permet de retourner, partir dun r el val donn , le fils gauche si val est

sup rieur ou gal la valeur du seuil et le fils droit sinon. Cette m thode doit afficher un

message derreur dans le cas o le nSud courant est une feuille.

(cid:1) __str__(&) : permet de retourner une chaine de caract res repr sentant les r gles de d cision

extraites de larbre conform ment au format donn dans la figure 3. Cette m thode doit appeler

la m thode linearise h rit e de la classe Node.

DecisionNd est une instance de la classe DecisionNode associ e la figure 2

>>>left = DecisionNode('decision', {0:0, 1:1})

>>>right= DecisionNode('age', {0:0.5, 1:0.5}, 62,

DecisionNode('decision', {0:0.2, 1:0.8},0.5),

DecisionNode('tachycardie',{0:0.4,1:0.6},0.5,

DecisionNode('decision', {0:0.1, 1:0.9},0.5),

DecisionNode('decision', {0:0.9, 1:0.1},0.5)) )

>>>DecisionNd = DecisionNode('tension', {0:0.3, 1:0.7}, 91, left, right)

La m thode linearise appliqu e sur DecisionNd donne la liste des branches de larbre de la figure 2

>>>DecisionNd.linearise()

[ , , , ]

La fonction print (appel de la m thode __str__) permet dafficher textuellement les r gles associ es aux

branches de larbre DecisionNd

>>>print(DecisionNd)

IF tension>=91 THEN decision={0:0, 1:1}

IF tension<91 AND age>=62 THEN decision={0:0.2, 1:0.8}

IF tension<91 AND age<62 AND tachycardie>=0.5 THEN decision={0:0.1, 1:0.9}

IF tension<91 AND age<62 AND tachycardie<0.5 THEN decision={0:0.9, 1:0.1}

La deuxi me ligne r sultante de la commande print correspond la r gle associ e la branche , puisque le nSud de label 'age' est un fils droit du nSud de label 'tension', que 'decision' est un fils

gauche de 'age'.

Figure 3 : Exemple de manipulation dune instance de DecisionNode

(cid:1) predict(..) : permet, partir dun ensemble dobservations, de retourner les pr dictions des

d cisions possibles.

Cette m thode prend en param tre un dictionnaire dicobs, associ un ensemble

dobservations, o :

" Chaque cl repr sente le nom dune observation (chaine de caract res) ;

" Chaque valeur repr sente la valeur dune observation (entier).

Cette m thode retourne un dictionnaire distr, en consid rant la variable CurrentNode (nSud

courant) initialis e self et en appliquant le proc d suivant :

" si le label de CurrentNode nest pas une cl du dictionnaire dicobs o bien si

CurrentNode est une feuille alors, retourner son attribut distr

" sinon,

o la variable Curvalue re oit la valeur dont la cl est le label de CurrentNode dans

dicobs;

o CurrentNode re oit le r sultat de la m thode outcome partir de linstance

CurrentNode en passant Curvalue comme param tre.

• Classe DecisionForest :

(cid:1) Attribut : listNodes : une liste dinstances de la classe DecisionNode

o M thodes :

(cid:1) __init__(&) : permet dinitialiser lattribut listNodes une liste vide.

(cid:1) add(&) : permet dajouter une instance de la classe DecisionNode lattribut listNodes

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 4/10

(cid:1) predict(&) : permet, partir dun ensemble dobservations repr sent par un dictionnaire

dicobs, de retourner un dictionnaire distr contenant la probabilit moyenne de chaque

d cision suivant les pr dictions des l ments de listNodes.

Travail demand

En se basant sur les descriptions ci-dessus r pondre aux questions suivantes :

Construire la classe DecisionNode :

1. Donner lent te qui permet la d finition de la classe DecisionNode.

2. Ecrire la m thode __init__.

3. Ecrire la m thode outcome.

4. Ecrire la m thode __str__.

5. Ecrire la m thode predict.

Construire la classe DecisionForest :

6. Ecrire la m thode __init__.

7. Ecrire la m thode add.

8. Ecrire la m thode predict.

Partie 3 : Apprentissage (Les questions de 1 8 sont ind pendantes des Parties 1 et 2)

L'objectif de cette partie est dimpl menter un algorithme pour la construction automatique de larbre de

d cision binaire partir des donn es.

Les donn es dapprentissage seront repr sent es par une matrice DSET de n lignes et m colonnes. Pour

chaque ligne de la matrice, nous convenons dassocier les (m-1) premi res colonnes pour les valeurs

dobservations et la derni re pour la d cision associ e ces observations.

Les noms des observations et le nom de la d cision sont stock s dans une liste, not e Lcol, selon le m me

ordre dans la matrice.

Exemple : La matrice DSET et la liste Lcol associ es aux donn es de la table 1 sont :

D

SET

=

110 50 1 0

119 36 0 0

82

81

56

72 0 1

70 0 1

50 1

1

', '

Travail demand

L

col

=

[

'

tension age tachycardie decision

', '

', '

'

]

Dans la suite :

• On suppose que DSET et Lcol sont d j d finies.
• On suppose que le module numpy a t import ainsi : import numpy as np
• Les fonctions demand es seront crites en langage Python en respectant la nomenclature

pr sent e lAnnexe 1 (page 9).

1. Ecrire une fonction nomm e CountValues qui prend en param tres DSET et un entier ind et

retourne le nombre de valeurs distinctes de la colonne dindice ind.

Exemple : Lappel de CountValues(DSET,1) retourne 4.

2. Ecrire une fonction EvalDistr qui prend en param tre DSET et retourne un dictionnaire distr o :

chaque cl , not e d, est une valeur de la d cision (0 ou 1);

chaque valeur est la probabilit dapparition de d dans DSET exprim e par :

p decision

(

=

d DSET

)

=

nombre de lignes o la d cision est gale

d

nombre de lignes de

DSET

(

Eq

.1)

Si DSET est vide, distr= {0:0.5, 1:0.5}.

Exemple : Lappel de EvalDistr(DSET) retourne {0: 0.4, 1: 0.6}.

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 5/10

3. Ecrire une fonction nomm e IsPure, qui prend en param tre DSET et retourne un bool en gal

True si DSET est pure et False sinon, sachant que DSET est pure, si et seulement si, toutes les

valeurs des d cisions sont gales.

4. Ecrire une fonction IsQualitative qui prend en entr e DSET et retourne une liste de bool ens,

qual, de taille gale au nombre de colonnes de DSET, contenant True pour les observations de

valeurs qualitatives (0 ou 1) et False pour les observations de valeurs quantitatives (autres valeurs

num riques).

Exemple : Lappel IsQualitative(DSET) retourne la liste .

5. Ecrire une fonction Cut qui permet de d couper DSET en deux matrices. Elle prend en param tres

DSET, Lcol, obs (une chaine de caract res correspondant au nom dune observation) et un r el S

repr sentant le seuil de d coupage et prenant la valeur 0.5 par d faut.

Cette fonction retourne un tuple form par les trois listes L1, L2 et L3 :

L1 contient les noms des observations except obs ;

L2 contient les matrices DSET1 et DSET2 telles que :

(cid:1) DSET1 est form e par les lignes de DSET o la valeur de lobservation obs, not e Vobs,

est sup rieure ou gale S ;

(cid:1) DSET2 est form e par les autres lignes de DSET ;

(cid:1) La colonne obs de DSET ne doit pas figur r dans DSET1 et DSET2 ;

Eq

2p d crites par les quations (

L3 contient les probabilit s

1p et

et (

Eq

.2)

.3) :

p

1

p

2

=

p

(

Vobs S DSET

e

)

=

=

p

(

Vobs S DSET

<

)

=

nombre de lignes de

nombre de lignes de

nombre de lignes de

nombre de lignes de

DSET1

DSET

DSET2

DSET

=

1

p

1

(

Eq

.2)

(

Eq

.3)

Exemple : Lappel Cut(DSET, Lcol, 'age', 70) retourne :

(['tension', 'tachycardie', 'decision'],

, [81,0,1]]), array ([[110,1,0],[119,0,0],[56,1,1]])],

[0.4, 0.6])

6. Ecrire une fonction Impurity qui prend en param tres DSET, Lcol, obs et un seuil S (ayant par

d faut la valeur 0.5). Cette fonction retourne un r el mesurant la qualit du d coupage de DSET

en deux matrices DSET1 et DSET2, calcul selon l quation (Eq.4).

=

p

1

p decision

p decision

d DSET2

d DSET1

min

min

Eq

.4)

))

))

+

=

p

(

(

(

(

(

2

d

{

}

0,1

d

{

}

0,1

O :

DSET1 et DSET2 r sultent du d coupage de la matrice DSET selon obs et S ;

p1 et p2 sont d crites par les quations (Eq.2) et (Eq.3) ;

p(decision = d|DSET) est donn e par l quation (Eq.1).

Exemple : Limpuret du d coupage illustr dans lexemple de la question 5 est donn e par :

(cid:1)(cid:2)(cid:3)(cid:4)(cid:5)(cid:6)(cid:7)(cid:8)(cid:9)(cid:10)(cid:11)(cid:12)(cid:13), (cid:15)(cid:16)(cid:17)(cid:18), 2(cid:20)(cid:21)(cid:22)(cid:23), (cid:24)(cid:25)(cid:26) = (cid:25). (cid:29) (cid:2)(cid:6)(cid:31)(cid:9)(cid:25), (cid:26) + (cid:25). " (cid:2)(cid:6)(cid:31) #

$

% ,

%& = (cid:25). $

7. Ecrire une fonction SortObs qui prend en param tres DSET, Lcol et obs, puis retourne une liste

Lc obtenue selon les tapes suivantes :

partir des deux colonnes obs et 'decision', cr er la liste Lc qui est une liste de tuples (v,d) o

v est une valeur de lobservation obs et d la valeur de la d cision associ e,

puis, trier Lc par ordre croissant suivant les valeurs de obs.

Exemple

Lappel de SortObs(DSET, 'age') retourne : [(36,0),(50,0),(50,1),(70,1),(72,1)]

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 6/10

8. Ecrire une fonction BestCut qui prend en param tres DSET, Lcol obs et une liste qual et retourne

un tuple (vBest, sBest) o vBest est la meilleure impuret et sBest est le meilleur seuil de

d coupage associ . vBest et sBest sont d termin s comme suit :

Cas des observations qualitatives :

(cid:1) sBest= 0.5

(cid:1) vBest= Impurity(DSET, Lcol, obs).

Cas des observations quantitatives :

(cid:1) Cr er Lc, la liste form e par les tuples (vi,di) tri e par ordre croissant en utilisant la fonction

SortObs.

(cid:1) Cr er partir de Lc, une liste LSeuil contenant les seuils possibles de d coupage de la

matrice DSET selon les conditions suivantes :

o Si DSET est pure, alors LSeuil contient la valeur maximale des vi de la liste Lc.

o Si DSET est impure, alors LSeuil est form e par les valeurs

v

i

1

pour tous les

i

v ++

2

tuples adjacents (vi ,di) et (vi+1 , di+1) de Lc avec '(cid:6) ` '(cid:6)) .

(cid:1) D terminer le meilleur seuil sBest de la liste LSeuil associ e la valeur minimale de

limpuret , vBest.

9. Ecrire une fonction nomm e BuildTree qui prend en param tres DSET, une liste Lcol et une liste

de bool ens qual et retourne une instance de la classe DecisionNode (d finie dans la partie 1)

repr sentant larbre de d cision, selon le proc d r cursif suivant :

cr er le dictionnaire distr en calculant la distribution des valeurs de d cisions dans DSET.

Traitement de base : Si DSET est vide ou bien si DSET est pure ou bien si Lcol contient une

seule valeur, alors retourner une instance de DecisionNode correspondant un nSud feuille avec

la distribution distr ;

Traitement r cursif (g n ral) :

(cid:1) pour chaque observation obs de Lcol, calculer (en utilisant la fonction BestCut) le meilleur

seuil ainsi que limpuret associ e ;

(cid:1) trouver lobservation oBest qui a la meilleure impuret vBest (minimale) associ e son seuil

sBest parmi toutes les observations obs dans Lcol ;

(cid:1) cr er une instance de DecisionNode contenant le nom de lobservation oBest comme label et

son seuil sBest et la distribution distr ;

(cid:1) appliquer le d coupage de DSET en DSET1 et DSET2 selon oBest et sBest laide de la

fonction Cut ;

(cid:1) cr er le nSud fils gauche (appel r cursif avec DSET1, Lcol sauf oBest) ;

(cid:1) cr er le nSud fils droit (appel r cursif avec DSET2, Lcol sauf oBest).

PROBLEME 2

Soit la base de donn es relationnelle intitul e 'classifieurs.db' contenant la description des donn es

dapprentissage avec les classifieurs automatiques cr s autour de ces donn es, repr sent e par le sch ma

relationnel suivant :

(cid:1) DataSet (ds_id, ds_name, nb_instances, format, ds_description)

La table DataSet d crit les donn es dapprentissage, avec les colonnes :

• ds_id : identifiant du dataset (entier), cl primaire.
• ds_name : nom du dataset (cha ne de caract res).
• nb_instances : nombre de lignes du dataset (entier).

-

• ds_description : le sommaire du dataset (chaine de caract res).

format : le format des donn es du dataset (chaine de caract res).

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 7/10

(cid:1) Classifieur (cls_id, cls_description, error_rate, language, ds_id)

La table Classifieur d crit un classifieur automatique construit partir dun dataset, avec les colonnes :

-

-

-

-

cls_id : identifiant du classifieur (chaine de caract re), cl primaire.

cls_description : description du classifieur (chaine de caract res).

error_rate : un nombre r el entre 0 et 1 qui d crit le pourcentage des donn es o les d cisions

pr dites par le classifieur sont diff rentes de la r alit .

language : nom du langage de programmation utilis pour impl menter le classifieur (chaine

de caract re).

• ds_id : identifiant du dataset utilis pour lapprentissage du classifieur, cl trang re.

(cid:1) Method (m_name, category, m_description)

La table Method d crit les m thodes utilis es dans le domaine de lapprentissage automatique pour la

construction des classifieurs, avec les colonnes :

• m_name : le nom de la m thode (chaine de caract res), cl primaire.

-

• m_description : la description de la m thode (chaine de caract res).

category : la cat gorie de la m thode (chaine de caract res).

(cid:1) Combine (cls_id, m_name, description)

La table Combine d crit les m thodes de classification utilis es dans chaque classifieur, de cl

primaire (cls_id, m_name), avec les colonnes :

-

cls_id : identifiant du classifieur (chaine de caract re), cl trang re.

• m_name : le nom de la m thode (chaine de caract re), cl trang re.
• description : strat gie dint gration de la m thode dans le classifieur (chaine de caract res)

Partie 1 : alg bre relationnelle

Exprimer en alg bre relationnelle les requ tes suivantes :

1. D terminer les identifiants, les noms et les descriptions des datasets au format 'csv'.

2. D terminer les descriptions des classifieurs impl ment s en 'Python' et qui utilisent la m thode

de cat gorie 'KNN'.

Partie 2 : SQL

Exprimer en SQL les requ tes suivantes :

3. Donner les identifiants des datasets pour lesquels il existe au moins un classifieur avec un taux

derreur < 0.3 (error_rate).

4. Donner les identifiants et les noms des datasets o tous les classifieurs sont impl ment s en

'Python'.

5. Donner pour chaque dataset le nombre de m thodes de classification utilis es.

6. Mettre jour le nombre dinstances des datasets utilis s pour les classifieurs crits en 'Python',

en ajoutant 100 instances.

Partie 3 : sqlite3

On dispose dun fichier texte nomm 'DataMeth.txt' contenant des informations relatives aux m thodes

utilis es par les classifieurs, chaque ligne du fichier a la forme suivante :

Nom_m thode#cat gorie#description

7. Ecrire les instructions python permettant de :

importer le module sqlite3 ;

-

• se connecter la base de donn es 'classifieurs.db';
• cr er le curseur cur dex cution ;
• cr er la table Method ;
• remplir la table Method partir du fichier 'DataMeth.txt' ;

-

tracer la courbe dont les abscisses sont les identifiants des datasets et les ordonn es sont les

taux derreur moyens des classifieurs associ s.

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 8/10

ANNEXE 1 Nomenclature associ e la Partie 3 du PROBLEME 1

Nom

DSET

DSET1

DSET2

n, m

ind

distr

qual

Lcol

obs

S

Lc

vBest

sBest

LSeuil

oBest

Type

Description

numpy.ndarray Matrices repr sentants des donn es dapprentissage

int

int

dict

list

list

str

float

list

float

float

list

str

Respectivement nombre de lignes et de colonnes de DSET

Indice dune colonne de la matrice DSET

Dictionnaire repr sentant la distribution des probabilit s des

d cisions

Liste indiquant les observations qualitatives et les observations

quantitatives

Liste de chaines des caract res repr sentant les noms des

observations ainsi que le nom de la d cision

chaine de caract res repr sentant le nom dune observation

Seuil de d coupage

Liste de tuples o chaque tuple est form par la valeur dune observation

et la valeur de la d cision associ e

Impuret donnant le meilleur seuil

Meilleur seuil

Liste des seuils possibles de d coupage

Nom de lobservation qui a la meilleure impuret

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 9/10

ANNEXE 2 Quelques fonctions Python

Op rations utiles sur les it rables (str, tuple, list, dict, etc.)

len(it) retourne le nombre d l ments de lit rable it.

range(d,f) retourne la s quence de valeurs enti res successives comprises entre d et f exclu.

-

-

• min(it) (resp. max(it)) retourne la valeur minimale (resp. maximale) de lit rable it.
• x in it (resp. x not in it) v rifie si x appartient it (resp. nappartient pas).

-

-

-

-

-

-

-

sorted(it) retourne une liste contenant les l ments de it dans lordre croissant.

lst.sort() trie la liste lst dans lordre croissant.

lst.count(val) retourne le nombre doccurrences de val dans la liste lst.

lst.append(val) ajoute val la fin de la liste lst.

lst.remove(val) supprime la premi re occurrence de val dans la liste lst.

lst.index(val) retourne lindice de la premi re occurrence de val dans la liste lst.

source.split(motif) retourne une liste form e par des chaines de caract res r sultant du d coupage

de la chaine source autour de la chaine motif.

• motif.join(it rable de chaine de caract re) retourne une chaine de caract res r sultant de la

concat nation des l ments de lit rable intercal s par le motif.

• motif.format(param tres) retourne une chaine de caract res obtenue en substituant dans lordre

chaque {} dans motif par un objet de param tres.

• d.values() retourne un it rable form par les valeurs du dictionnaire d.
• d.items() retourne un it rable de couples (k,v) ou k est une cl du dictionnaire d et v est la valeur

associ e.

• M.shape ou np.shape(M) retourne un tuple form par le nombre de lignes et le nombre de

colonnes dune matrice M.

Op rations sur les fichiers

-

-

-

-

-

f=open (nomF,m) permet douvrir le fichier nomF en mode m o m='r' ou 'w'.

f.close( ) permet de fermer un fichier.

f.read() permet de lire et retourner le contenu dun fichier dans une chaine de caract res.

f.readline() permet de lire et retourner le contenu de la ligne courante dun fichier dans une chaine

de caract res.

f.readlines() : permet de lire et retourner le contenu de toutes les lignes dun fichier dans une

liste.

Op rations sur le module matplotlib.pyplot

-

-

-

import matplotlib.pyplot as plt permet le chargement du module

plt.plot(x,y) cr e la courbe o les abscisses sont d crites par les valeurs de lit rable x et les

ordonn es par ceux de lit rable y.

plt.show() affiche une fen tre contenant le r sultat du dessin.

Concours (Math matiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve dInformatique Page 10/10