def __str__(self): # méthode récursive

return "Node({},{},{})".format(repr(self.label), self.left, self.right)

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 1/

6

Partie 2 : Représentation du modèle de décision

question 1

class DecisionNode(Node):

question 2

def __init__(self, label, distr, seuil = 0.5, left= None, right = None):

super().__init__(label, left, right)

self.distr = distr

self.seuil = seuil

question 3

def outcome(self, val):

assert not self.isLeaf()

if val >= self.seuil:

return self.left

return self.right

question 4

def __str__(self):

paths = self.linearise()

lstrules = []

for path in paths:

rule = ["{}{}{}".format(cn.label,

">=" if cn.left == nn else "<",

cn.seuil)

for cn, nn in zip(path, path[1:])]

lstrules.append("IF {} THEN décision = {}".format(

" AND ".join(rule), path[-1].distr))

return "\n".join(lstrules)

question 5

def predict(self, dicobs):

currentNode = self

while True:

if currentNode.isLeaf() or currentNode.label not in dicobs:

return currentNode.distr

currentvalue = dicobs[currentNode.label]

currentNode = currentNode.outcome(currentvalue)

class DecisionForest:

question 6

def __init__(self):

self.listNodes = []

question 7

def add(self, newinstance):

self.listNodes.append(newinstance)

question 8

def predict(self, dictobs):

if len(self.listNodes) == 0:

return {0:0.5, 1:0.5}

else:

p0 = 0

for dn in self.listNodes:

distr = dn.predict(dictobs)

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 2/

6

p0 += distr[0]

p0 /= len(self.listNodes)

return {0:p0, 1:1-p0}

Partie 3 : Apprentissage

1.

import numpy as np

2.

def CountValues(DSET, index):

return len(set(DSET[:,index]))

3.

def EvalDistr(DSET):

if DSET.size == 0:

return {0:0.5, 1:0.5}

else:

p1 = (DSET[:,-1]).sum()/len(DSET)

return {0:1-p1, 1:p1}

4.

def IsPure(DSET):

return 1 in EvalDistr(DSET).values()

5.

def IsQualitative(DSET):

return [set(DSET[:,i]) <= {0,1} for i in range(DSET.shape[-1])]

6.

def Cut(DSET, colonnes, obs, S = 0.5):

robs = colonnes[:]

robs.remove(obs)

cindex = colonnes.index(obs)

lst1 = []

lst2 = []

for row in DSET:

vals = row.tolist()

vals.pop(cindex)

if row[cindex] >= S:

lst1.append(vals)

else:

lst2.append(vals)

p1 = len(lst1)/len(DSET)

p2 = 1 - p1

return robs, [np.array(lst1), np.array(lst2)], [p1, p2]

7.

def Impurity(DSET, colonnes, obs, S = 0.5):

_, [d1, d2], [p1, p2] = Cut(DSET, colonnes, obs, S)

return p1 min(EvalDistr(d1).values()) + p2 min(EvalDistr(d2).values())

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 3/

6

8.

def SortObs(DSET, colonnes, obs):

col_index = colonnes.index(obs)

Lc = [(v,d) for v, d in zip(DSET[:,col_index], DSET[:,-1])]

return sorted(Lc)

9.

def BestCut(DSET, colonnes, obs, qual):

col_index = colonnes.index(obs)

if qual[col_index]:

return (0.5, Impurity(DSET, colonnes, obs))

Lc = SortObs(DSET, colonnes, obs)

Lseuil = []

if IsPure(DSET):

Lseuil.append(max(Lc)[0])

else:

for (vc,dc),(vn,dn) in zip(Lc, Lc[1:]):

if dc != dn:

Lseuil.append((vc+vn)/2)

impurities = [Impurity(DSET, colonnes, obs, s) for s in Lseuil]

best_index = impurities.index(min(impurities))

return (Lseuil[best_index], impurities[best_index])

10.

def BuildTree(DSET, colonnes, qual):

distr = EvalDistr(DSET)

if len(DSET) == 0 or IsPure(DSET) or len(colonnes) == 1:

return DecisionNode(colonnes[-1], distr)

bestImp = np.inf

for obs in colonnes[:-1]:

sBest, vBest = BestCut(DSET, colonnes, obs, qual)

if bestImp > vBest:

bestObs = obs

bestImp = vBest

bestT = sBest

root = DecisionNode(bestObs, distr, bestT)

cols, [ds1, ds2], [p1, p2] = Cut(DSET, colonnes, bestObs, bestT)

rqual = qual[:]

rqual.pop(colonnes.index(bestObs))

root.left = BuildTree(ds1, cols, rqual)

root.right = BuildTree(ds2, cols, rqual)

return root

PROBLEME 2

Partie 1 : algèbre relationnelle

1. Π

𝑑𝑠_𝑖𝑑,𝑑𝑠_𝑛𝑎𝑚𝑒,𝑑𝑠_𝑑𝑒𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 (𝜎𝑓𝑜𝑟𝑚𝑎𝑡=′𝑐𝑠𝑣′(𝐷𝑎𝑡𝑎𝑆𝑒𝑡))

2. Π𝑐𝑙𝑠_𝑑𝑒𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛( 𝜎𝑙𝑎𝑛𝑔𝑢𝑎𝑔𝑒=′𝑃𝑦𝑡ℎ𝑜𝑛′𝑒𝑡 𝑐𝑎𝑡𝑒𝑔𝑜𝑟𝑦=′𝐾𝑁𝑁′(𝐶𝑙𝑎𝑠𝑠𝑖𝑓𝑖𝑒𝑢𝑟 ⋈𝑐𝑙𝑠_𝑖𝑑 𝐶𝑜𝑚𝑏𝑖𝑛𝑒⋈𝑚_𝑛𝑎𝑚𝑒 𝑀𝑒𝑡ℎ𝑜𝑑)

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 4/

6

Partie 2 : SQL

1.

SELECT ds_id

FROM Classifieur

WHERE error_rate < 0.3 ;

2.

SELECT D.ds_id, ds_name

FROM DataSet AS D, Classifieur AS C

WHERE (D.ds_id = C.ds_id)

EXCEPT

SELECT D.ds_id, ds_name

FROM DataSet AS D, Classifieur AS

WHERE (D.ds_id = C.ds_id) AND (language <> 'Python');

3.

SELECT D.ds_id, COUNT(DISTINCT M.m_name) AS NB_M

FROM DataSet AS D,

Classifieur AS C,

Combine AS CM,

Method AS M

WHERE (D.ds_id = C.ds_id) AND

(C.cls_id = CM.cls_id) AND

(CM.m_name = M.m_name)

GROUP BY C.cls_id;

4.

UPDATE DataSet

Set nb_instances = nb_instances + 100

WHERE ds_id IN

(SELECT ds_id

FROM Classifieur

WHERE language ='Python');

Partie 3 : sqlite3

5.

import sqlite3

cnx = sqlite3.connect("CMP.db")

cur = cnx.cursor()

sql_tbl = """

CREATE TABLE Method

(

m_name TEXT PRIMARY KEY,

category TEXT,

m_description TEXT

);

"""

cur.execute(sql_tbl)

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 5/

6

with open("DataMeth.txt") as f:

ldata = [l.strip().split('#') for l in f]

sql_ins = """

INSERT INTO Method VALUES(?,?,?);

"""

cur.executemany(sql_ins, ldata)

cnx.commit()

sql_sel = """

SELECT ds_id, AVG(error_rate) AS M_erreur

FROM Classifieur

GROUP BY ds_id

ORDER BY ds_id

"""

cur.execute(sql_sel)

x, y = zip(*cur.fetchall())

import matplotlib.pyplot as plt

plt.plot(x,y)

plt.show()

cnx.close()

Concours (Mathématiques et Physique, Physique et Chimie et Technologie)- Session Juin 2019 Epreuve d’Informatique Page 6/

6