TP 3 : Arbre de décisions

1. Familiarisez-vous avec le contenu du fichier iris.csv.
2. Utilisez numpy.loadtxt ou pandas.read_csv et pandas.DataFrame.to_numpy pour charger le fichier. On créera les tableaux numpy suivants :
   • feature_names de shape (4,) qui contiendra le nom de chaque feature, data de shape (N,4) où N est le nombre d’exemple dans le fichier et qui contiendra les valeurs.
   • classes de shape (N,)qui contiendra les classes (dans le sens où classes[i]est la classe du point data[i]). Pour faciliter l’utilisation avec scikit-learn, on renommera les classes avec des entiers : {"Virginica" : 0, "Versicolor": 1, "Setosa": 2}.
   • cname = ["Virginica", "Versicolor", "Setosa"].

On pourra utiliser les paramètres skiprows, usecols, max_rows de numpy.loadtxt ou des manipulations classiques des dataframes.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
from sklearn import metrics

df = pd.read_csv("iris.csv")

feature_names = df.columns.to_numpy()[:4]
data = df.to_numpy()[:, :4]

d = {"Virginica": 0, "Versicolor": 1, "Setosa": 2}
cname = ["Virginica", "Versicolor", "Setosa"]
classes = df["variety"].replace(d).to_numpy(dtype=int)

3. Pour chaque classe du problème (setosa, versicolor, virginica), combien y a-t-il de fleurs dans le jeu de données ? Cela est-il équilibré ? Pourquoi cela est-il important ?

print(np.bincount(classes))

4. En utilisant matplotlib, visualisez le jeu de données. On pourra par exemple afficher, en nuage de points comme ci-dessous (on pourra utiliser c=classes pour avoir des couleurs qui dépendent des classes) :

d0 = 0 # premier feature 
d1 = 2 # second feature

scatter = plt.scatter(data[:,d0], data[:,d1], c=classes)

plt.xlabel(feature_names[d0])
plt.ylabel(feature_names[d1])

plt.legend(scatter.legend_elements()[0], cname)

plt.show()

Nous allons désormais trouver un arbre de décision pour expliquer les données. On importera les fonctions nécessaires avec :

from sklearn.tree import DecisionTreeClassifier, plot_tree

On crée un arbre de décision avec

clf = DecisionTreeClassifier()

Et on l’entraînera sur les exemples avec fit. On lui passera comme argument un tableau contenant les données et un tableau contenant les classes :

clf.fit(donnees, classes)

Enfin, on affichera l’arbre calculé avec la fonction plot_tree. noms_attributs est un tableau contenant le nom des attributs et noms_classes est un tableau contenant le nom des classes, ce qui permet d’avoir un affichage un peu plus lisible :

plt.figure(figsize=(20,20)) # zoom pour rendre l'arbre plus lisible 
                           # changer en fonction de la taille de votre écran.
plot_tree(clf, feature_names=noms_attributs, class_names=noms_classes, filled=True, rounded=True)
plt.show()

5. Utilisez les instructions ci-dessus pour entraîner et afficher l’arbre de décision.

clf = DecisionTreeClassifier()
clf.fit(data, class)
plt.figure(figsize=(20,20)) # zoom pour rendre l'arbre plus lisible 
                           # changer en fonction de la taille de votre écran.
plot_tree(clf, feature_names=feature_names, class_names=cname, filled=True, rounded=True)
plt.show()

6. Comment sera classée une fleur où la longueur des sépale est 10, la largeur 4, la longueur des pétales 5 et leur largeur 1 par votre modèle ?7. Même question en utilisant clf.predict(t) pour trouver la classe de plusieurs point d’entrée (t est un tableau de vecteurs d’attributs, par exemple [[10,4,5,0.1], [12,1,5,1]]).

print(clf.predict([[10,4,5,1]]))

Scikit Learn nous permet facilement de créer ce genre de partition. On utilisera pour cela la fonction train_test_split :

from sklearn.model_selection import train_test_split
donnees_train, donnees_test, classes_train, classes_test = train_test_split(donnees, classes, test_size=0.2, random_state=52)

Cela permet de créer une partition des données et de leur classe en une partie apprentissage et une partie entrainement. Dans l’exemple ci-dessus, on prélève 20% des données pour faire nos tests. random_state fixe la graine, ce qui permet de reproduire les résultats.

8. Entraînez de nouveau un arbre de décision sur 80% des données et affichez-le.

data_train, data_test, class_train, class_test = train_test_split(data, classes, test_size=0.2, random_state=52)

clf = DecisionTreeClassifier()
clf.fit(data_train, class_train)
plt.figure(figsize=(20,20)) # zoom pour rendre l'arbre plus lisible 
                           # changer en fonction de la taille de votre écran.
plot_tree(clf, feature_names=feature_names, class_names=cname, filled=True, rounded=True)
plt.show()

9. Calculez la précision de votre modèle, c’est-à-dire le nombre d’exemples tests bien classés divisé par le nombre total d’exemples tests. On remarquera que clf.predict peut prendre un tableau de données et renvoyer un tableau de décisions.

predict_test = clf.predict(data_test)
precision = 1-np.sum(class_test != predict_test)/class_test.shape[0]

On peut calculer la précision d’un modèle avec la fonction suivante :

from sklearn import metrics
accuracy = metrics.accuracy_score(classe_test, classe_predites)

10. Utilisez la fonction précédente pour calculer la précision de votre modèle et vérifiez votre résultat.

accuracy = metrics.accuracy_score(class_test, clf.predict(data_test))
print(f"Accuracy: {accuracy}")

11. Refaire l’exercice en prenant seulement 50% du jeux de données. Qu’observez-vous ?

data_train, data_test, class_train, class_test = train_test_split(data, classes, test_size=0.2, random_state=52)

data_train, data_test, class_train, class_test = train_test_split(data, classes, test_size=0.5, random_state=52).

12. En allant lire la documentation, entraînez un classifier en utilisant l’entropie comme fonction de mélange au lieu de la fonction Gini.

clf = DecisionTreeClassifier()

clf = DecisionTreeClassifier(criterion="entropy")

Dans cet exercice, on va implémenter nous-mêmes un algorithme pour trouver un bon arbre de décision. On va implémenter une version simple de l’algorithme CART. On va se limiter au cas où les données sont de la forme \((x_0,\dots,x_k)\) avec \(x_i\) un float et les decisions prises dans chaque nœud sont de la forme \(x_i < v\) pour une certaine valeur \(v\).

1. Écrire une fonction decide(data: np.array, classes: np.array, i : int, v : float) qui prend un ensemble de données data avec leur classe classes, et renvoie quatre tableaux numpy (data0, classes0, data1, classes1) tels que data0 est le sous-ensemble de data où \(x_i \geq v\) et data1 est le sous-ensemble de data où \(x_i < v\). Les classes de data0 seront classes0 et celles de data1 seront classes1. On rappelle qu’on peut écrire data[:,i] qui est un tableau tel que data[:,i][j] = data[j][i].

def decide(data: np.array, classes: np.array, i : int, v : float):
    mask0 = data[:,i]>=v
    mask1 = data[:,i]<v
    data0 = data[mask0]
    classes0 = classes[mask0]
    data1 = data[mask1]
    classes1 = classes[mask1]
    return data0, classes0, data1, classes1

On veut trouver la décision de la forme \(x_i < v\) la plus “clivante”, c’est-à-dire, celle qui sépare le mieux les classes. Pour cela, on utilise une fonction \(F\) qui estime le degré de mélange, comme l’entropie ou la fonction de Gini vu en cours. On estime le gain d’un test \(x_i < v\) comme

\(F(D) - {|D_0| \over |D|} \cdot F(D_0) - {|D_1| \over |D|} \cdot F(D_1)\)

où \(D_0\) est l’ensemble des éléments de \(D\) qui ne satisfont pas le test et \(D_1\) l’ensemble des éléments de \(D\) qui satisfont le test.

2. 1. Écrire une fonction gini(classes: np.array) qui estime le degré de mélange du jeu de données. On observe qu’on n’a pas besoin des données pour calculer cela.

def gini(classes: np.array):
    N = classes.shape[0]
    T = (np.bincount(classes)/N)**2
    return 1-np.sum(T)

2. Écrire une fonction gain(data: np.array, classes: np.array, i: int, v : float) qui estime le gain du test \(x_i < v\) pour la fonction de mélange gini.

def gain(data: np.array, classes: np.array, i: int, v : float):
    d0,c0,d1,c1 = decide(data, classes, i, v)
    return gini(classes) - (c0.shape[0]/classes.shape[0])*gini(c0) - (c1.shape[0]/classes.shape[0])*gini(c1)

3. Écrire une fonction maxgain(data: np.array, classes: np.array) qui renvoie un couple (i,v) maximisant le gain possible parmis tous les tests \(x_j < w\) possible. Pour cela, on remarquera que pour chaque i, on a un nombre restreint de valeurs à tester (bonus : réfléchir à différentes façons de tester cela).

def maxgain(data: np.array, classes: np.array):
    best_idx = 0
    best_value = data[0][best_idx]
    currentg = gain(data, classes, best_idx, best_value)

    for i in range(data.shape[1]):
        candv = np.unique(data[:,i])
        for v in candv:
            if gain(data, classes, i, v) > currentg:
                best_idx = i
                best_value = v
                currentg = gain(data, classes, best_idx, best_value)
    return (best_idx, best_value)

4. On va représenter un arbre de décision comme suit:

class LeafNode(DecisionNode):
    def __init__(self, value):
        self.value = value

class InternalNode(DecisionNode):
    def __init__(self, i, v, left, right):
        self.i = i
        self.v = v
        self.left = left
        self.right = right

Créer une récursive fonction fit(data,classes) qui crée un arbre de décision pour les données passées en paramètre et renvoie la racine de cet arbre. Votre fonction devra créer l’arbre ainsi :

• Si classes ne contient qu’une seule classe c, alors on renverra un LeafNode qui renvoie la classe c.
• Sinon, on retourne un noeud InternalNode qui sépare le jeu de données en fonction de la question maximisant le gain (selon maxgain) et construire left et right recursivement.

def fit(data: np.array, classes: np.array):
    if gini(classes) == 0: # Il n'y a plus qu'une seule classes représentée dans le jeu de données
        return LeafNode(classes[0])
    else: # Sinon, on choisit la meilleure question et on construit l'arbre récursivement
        (i,v) = maxgain(data, classes)
        d0,c0,d1,c1 = decide(data, classes, i, v)
        left = fit(d0,c0)
        right = fit(d1,c1)
        return InternalNode(i, v, left, right)

5. Ajouter des méthodes pour afficher les arbres de décision et prédire une valeur.

def printTree(t, tab=0):
    if t.nodetype() == "leaf":
        print(tab*"\t" + f"Return classe {t.value}")
    else:
        print(tab*"\t" + f"Current gini = {t.gini}")
        print(tab*"\t" + f"Current bins = {t.bins}")
        print(tab*"\t" + f"if (x_{t.i} < {t.v})")
        printTree(t.left, tab=tab+1)
        print(tab*"\t" + f"else")
        printTree(t.right, tab=tab+1)

def predict_v(t, d):
    if t.nodetype() == "leaf":
        return t.value
    else:
        if d[t.i] >= t.v:
            return predict_v(t.left, d)
        else:
            return predict_v(t.right,d)

def predict(t, data):
    r = np.zeros(data.shape[0])
    for i in range(data.shape[0]):
        r[i] = predict_v(t, data[i])    
    return r

6. Évaluez votre arbre sur le jeu de données iris.csv.

accuracy = metrics.accuracy_score(class_test, predict(t, data_test))
print(f"Accurracy: {accuracy}")