# TP1 : Machine Learning

> Le rendu de ce TP se fera uniquement par TPLab et consistera en une archive (zip, tar, etc.) contenant un répertoire TP1-NOM ! Un non respect de cette consigne entrainera une claque humiliante de la part de Haris.

Ce TP doit vous aider à vous familiariser avec deux différents algorithmes de machine learning, le K-NN et le Random Forest.

## Partie 1 : Algorithme K-NN

> L’algorithme des K plus proches voisins ou K-nearest neighbors (kNN) est un algorithme de Machine Learning qui appartient à la classe des algorithmes d’apprentissage supervisé simple et facile à mettre en œuvre qui peut être utilisé pour résoudre les problèmes de classification et de régression.

Dans cette partie vous allez implémenter et utiliser le modèle K-NN. Pour ce faire, vous allez :

### 1) Cas pratique

> Nous allons donc implémenter l'algorithme K-NN dans un cas pratique, l'objectif étant de construire un algorithme permettant de reconnaitre des chiffres manuscrits.

Commencez par créer un nouveau [Notebook Jupyter](https://colab.research.google.com/) sur Google Collab, et suivez ces consignes :
(Il est également possible d'utiliser Kaggle (pour les anti google)

#### a) Importez le dataset

Commencez par importer ces librairies qui seront nécéssaires par la suite :

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_digits
from sklearn.metrics import confusion_matrix

Nous allons ensuite charger le dataset à l'aide de la fonction [`load_digits()`](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_digits.html) de sklearn. Puis séparer en deux tableaux contenant les 'data' et les 'targets'.

<details>
<summary>Solution</summary>

digits = load_digits()
X, y = digits.data, digits.target

</details>

Puis pour mieux se rendre compte du type de données que nous allons manipuler, nous allons afficher les chiffres du jeu de données. Ajoutez ces lignes de code dans une nouvelle cellule.

_, axes = plt.subplots(nrows=1, ncols=4, figsize=(8,8))
for ax, image, label in zip(axes, digits.images, digits.target):
    ax.set_axis_off()
    ax.imshow(image, cmap=plt.cm.gray_r, interpolation="nearest")
    ax.set_title("Image: %i" % label)

Vous devriez obtenir ce résultat :


#### b) Divisez le dataset en deux (entrainement / test)

Pour cela nous allons utiliser la fonction [`train_test_split()`](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html) pour diviser notre jeu de donnée en deux parties avec un ratio 80/20 :

<details>
<summary>Solution</summary>

X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)

</details>

#### c) Créer et entraîner le modèle K-NN (valeur pour k arbitraire)

Nous allons ensuite utiliser *SCIKit-Learn* pour appliquer l'algorithme K-NN à nos données que l'on a préalablement préparé et ainsi les classer grâce à leurs voisins :

Consultez [cette documentation](https://scikit-learn.org/stable/modules/neighbors.html) pour compléter le code ci-dessous :

knn = ????
knn.???(???, ???)

<details>
<summary>Solution</summary>

knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)

</details>

#### d) Afficher le taux de précision

Affichez le taux de précission (score) de l'algorithme précédemment exécuté pour cela consultez [la documentation](https://scikit-learn.org/stable/modules/neighbors.html):

<details>
<summary>Solution</summary>

score = knn.score(X_test, y_test)
print('Score: %f' % score)

</details>

#### e) Tester et comparer les taux pour k de 1 à 20

Nous allons ensuite tester et comparer le taux de précision de notre algorithme pour K nombre de voisins, complétez ce code :

neighbors = np.arange(1,21)
train_accuracy = np.empty(len(neighbors))
test_accuracy = np.empty(len(neighbors))

for i,k in enumerate(neighbors) :
    ?????
    ?????
    ?????
    ?????
    
print(test_accuracy)

<details>
<summary>Solution</summary>

neighbors = np.arange(1,21)
train_accuracy = np.empty(len(neighbors))
test_accuracy = np.empty(len(neighbors))

for i,k in enumerate(neighbors) :
   knn = KNeighborsClassifier(n_neighbors=k)
   knn.fit(X_train, y_train)
   train_accuracy[i] = knn.score(X_train, y_train)
   test_accuracy[i] = knn.score(X_test, y_test)

print(test_accuracy)

</details>

Vous devriez obtenir un résultat similaire :

> [0.99166667 0.99444444 0.98888889 0.99166667 0.99444444 0.99444444
0.99166667 0.98888889 0.99166667 0.99166667 0.98333333 0.98611111
0.98333333 0.98333333 0.98333333 0.98333333 0.98333333 0.98333333
0.98055556 0.98055556]

#### f) Créer et afficher la matrice de confusion

Nous allons ensuite afficher graphiquement nos résultats :

Utilisez [MatplotLib (Cliquez-ici)](https://matplotlib.org/stable/gallery/lines_bars_and_markers/index.html) pour afficher les résultats ci-dessous.

Variables à utiliser : test_accuracy, train_accuracy

| k-NN précision par nombre de voisins | k-NN précision par nombre de voisins |
| -------- | -------- |
|  |  |

<details>
<summary>Solution</summary>

plt.plot(test_accuracy, 'o-')
plt.title('k-NN précision par nombre de voisins')
plt.xlabel('Nombre de voisins')
plt.ylabel('Précision')
plt.show()

plt.figure(figsize=(12,6))
plt.title('k-NN précision par nombre de voisins')
plt.scatter(neighbors, test_accuracy, label='Test_Accuracy', color="green")
plt.scatter(neighbors, train_accuracy, label='Train Accuracy', color="red")
plt.legend()
plt.xlabel('Nombre de voisins')
plt.ylabel('précision')
plt.show()

</details>

Nous allons ensuite générer la matrice de confusion de notre algorithme :

> La matrice de confusion est en quelque sorte un résumé des résultats de prédiction pour un problème particulier de classification. Elle compare les données réelles pour une variable cible à celles prédites par un modèle.

Complétez le code ci-dessous

y_pred = knn.???

cm = ???
cm

<details>
<summary>Solution</summary>

y_pred = knn.predict(X_test)

cm = confusion_matrix(y_test, y_pred)
cm

</details>

---

# Partie 2 : Algorithme Random Forest

> Le random forest est un algorithme qui se base sur l’assemblage d’arbres de décision. Il est assez intuitif à comprendre, rapide à entraîner et il produit des résultats généralisables. Seul bémol, le random forest est une boîte noire qui donne des résultats peu lisibles, c’est-à-dire peu explicatifs.

### 1) Qu'est ce qu'un arbre de décision ?

<details>
<summary>Réponse</summary>
Un arbre de décision est un arbre binaire qui divise le dataset récursivement jusqu’à obtenir que des feuilles (= data avec 1 seul type de classe)
</details>
<br>

*Exemple :*


### 2) Utilisez ce dataset pour faire un arbre de décision (10 pts. rouges et 10 pts. verts)


On calcule tout d'abbord l’entropie de chaque noeud : $E = - p_i (log(p_i))$ avec $p_i$ la probabilité de la $i^{ème}$ classe : $i = \frac{nb succes}{nb total}$
L’entropie est compris entre 0 et 1 (0 pour une feuille)

On calcule ensuite l’entropie de chaque noeud : : $$ Entropie = \Sigma - p_i \; log(p_i) \qquad avec \,p_i = \frac{nbSucces}{nbTotalInitial} $$
Elle est compris entre $0$ et $1$ ($0$ pour une feuille).
(L'entropie mesure la quantité d'information présente dans une variable)

Nous allons faire un example simple ou nous devons choisir entre 2 splits : $x \leq -12$ ou $y \leq 4$
> (les axes x=-12 et y=4 sont représentés en jaune)
- Effectuer le split des données en focntion des 2 valeurs données précédement
- Calculer l'entropie pour chaque noeud
- Calculer L'IG pour les valeurs de split
- Quelle fiabilité obtenez-vous K-NN ? Comparez ces 2 valeurs. Que pouvez-vous en dire ?

<details>
<summary>Réponse</summary>

** On obtient dans le premier cas ($x \leq -12$) les reponse en rouge et dans le 2eme cas ($y \leq 4$) les reponses en verts **

</details>
<br>

On calcule ensuite l’entropie pour chaque noeud et état possible et donc obtient :

Rappel :

*Image 1 : Etat d'un noeud*

$\hspace{10em}$
$$ p_i = \frac{nb Points Verts}{nb Points Verts + nb Points Rouges} \qquad Entropie = \Sigma - p_i \; log(p_i)$$

Pour savoir quel noeud choisir par la suite, on calcule ensuite $IG$ (Information gains ou gains d’information i.e. la condition qui nous apporte le plus d’information) pour chaque branche avec la formule(N.B : plus le nombre est grand plus le gain d’information est grand) :
$$IG = E(parent) - \Sigma\omega_i\times E(child_i)$$

<details>
<summary>Réponse</summary>

**et on obtient :**

$$IG_1 = 1 - \frac{14}{20} \times 0.99 - \frac{6}{20} \times 0,91 = 0,034$$

$$IG_2 = 1 - \frac{4}{20} \times 0 - \frac{16}{20} \times 0,95 = 0,24$$

**Donc dans ce cas nous choisirons $IG_2$ et donc plutôt la condition $y \leq 4$.**

**En réalité, le computer fait cette opération pour chaque valeur possible.**

</details>

<br/>

from sklearn.model_selection import cross_val_score
from sklearn.ensemble import RandomForestClassifier  #Random Forest algorithm

#Cross validation
rf=RandomForestClassifier(n_estimators=100)
rf.fit(df_x, df_y)
score = cross_val_score(rf, df_x, df_y)
print (np.mean(score))

> \>>> 0.962381270528

Avec l'algorithme random forest nous obtenons un fiabilité d'environ 96%.

Quelle fiabilité obtenez-vous K-NN ? Comparez ces 2 valeurs. Que pouvez-vous en dire ?

**Donc dans ce cas nous choisirons $IG_2$ et donc plutôt la condition $y \leq 4$.**

**En réalité, le computer fait cette opération pour chaque valeur possible.**

<details>
<summary>Réponse</summary>

**Nous voyons que nous obtenons un fiabilité de 95% pour KNN ce qui est très proche de la fiabilté de random forest. Cela ne change pas grand chose dans l'utilisation des algorithme. La différence va se faire dans l'entrainement de ces derniers. En effet pour entrainer KNN, nous devons determiner K (nb de voisins) ainsi que la distance avec ces derniers ce qui demande un temps de calcul énorme. Pour random forest ce n'est rien de plus qu'un ensemble arbres de decisions combinés. Cet algorithme permet de gérer des grands dataset. Les random forest peuvent fonctionner immédiatement d'où leur popularité.**

</details>

---

# Questionnaire

### 1) Quelles sont les différentes étapes nécessaires à la classification ?
>(nous avons noté 5 étapes, la 2e étant optionnelle en fonction du modèle)

1ère Étape : Récupération du jeu de Donnée et le séparer en 2 partie (données d'entraînement et de test)
2eme Étape : Transformation des données afin de pouvoir les manipuler avec le modèle (étape non nécessaire selon le modèle utilisé)
3eme Étape : Application du modèle d'entraînement
4eme Étape : tester l'efficacité du modèle avec les données de test
5eme Étape : générer et analyser la matrice de confusion

### 2) Pourquoi diviser le jeu de données de base en 2 ?

Afin de pouvoir avoir un jeu de données pour entraîner le modèle et un pour les tests.

### 3) Qu'est-ce qu'une matrice de Confusion ?

Elle est utilisée pour mettre en valeur les prédictions correctes et incorrectes ainsi qu'un indice sur le type d'erreurs commises.

### 4) Quel est le principe de fonctionnement du modèle K-NN ?

K-NN est un modèle qui va chercher à classifier une données en la comparant au K donné les plus proche de cette données parmis toutes les données déjà classifiées et choisir de lui attribuer la classe la plus représenté
### 5) Qu'est-ce qu'un modèle ?

Il va apprendre à associer une entrée à une sortie en se basant sur un jeu de données de couple entrée/sortie