595 lines
17 KiB
Python
595 lines
17 KiB
Python
#!/usr/bin/env python
|
||
# coding: utf-8
|
||
|
||
# # Introduction
|
||
#
|
||
# - Projet partiel présenté par: **François Pelletier**
|
||
# - Matricule: **908144032**
|
||
# - Dans le cadre du cours: **IFT-7025**
|
||
#
|
||
#
|
||
# ## Définitions
|
||
#
|
||
# La **matrice de confusion** est un tableau où on décompte les valeurs réelle O et prédites S pour chaque observation du jeu de données dans un problème de classification. Par sa conception, on peut valider rapidement le nombre d'observations où la prédiction est égale à la valeur réelle sur la diagonale de la matrice. Par convention, on place les valeurs prédites à la verticale et les valeurs observées à l'horizontale. Lorsque le nombre de modalités de la variable prédite est de deux, on a un problème de classification binaire et on obtient alors le décompte des vrais positifs, faux positifs, faux négatifs et vrais négatifs.
|
||
#
|
||
# La **précision** correspont à la proportion d'observations où la prédiction et la valeur réelle est dans une même classe par rapport au nombre d'observations où la prédiction est dans cette classe
|
||
#
|
||
# $$ \text{Précision}_c = \frac{\sum_{i=1}^N 1_{s_i=c}1_{o_i=c}}{\sum_{i=1}^N 1_{s_i=c}}$$
|
||
#
|
||
# Le **rappel** correspond à la proportions d'observations où la prédiction est dans une classe par rapport au nombre d'observations où la valeur réelle est dans cette classe.
|
||
#
|
||
# $$ \text{Rappel}_c = \frac{\sum_{i=1}^N 1_{s_i=c}}{\sum_{i=1}^N 1_{o_i=c}}$$
|
||
|
||
# ## Librairies utilisées
|
||
#
|
||
# Le project actuel est programmé dans le langage Python 3, et ce rapport est produit à l'aide de Jupyter Notebook. Seule les librairie standard `numpy` et `math` est utilisée, les autres ont été développées dans le cadre de ce projet.
|
||
|
||
# In[46]:
|
||
|
||
|
||
# Librairies standard
|
||
import numpy as np
|
||
import math
|
||
# Librairies développées par l'étudiant
|
||
import load_datasets as ld
|
||
import metrics
|
||
import BayesNaif
|
||
import Knn
|
||
|
||
|
||
# ## Jeux de données
|
||
#
|
||
# Ce projet utilise 3 jeux de données: [Iris](https://archive.ics.uci.edu/ml/datasets/Iris), [MONKS](https://archive.ics.uci.edu/ml/datasets/MONK's+Problems) et [Congressional Voting Records Dataset](https://archive.ics.uci.edu/ml/datasets/Congressional+Voting+Records). Pour les jeux qui ne sont pas déjà divisés en entrainement et test, on utilisera un ratio de 70% pour l'entrainement.
|
||
|
||
# In[47]:
|
||
|
||
|
||
train1, train_labels1, test1, test_labels1 = ld.load_iris_dataset(train_ratio = 0.7)
|
||
train2, train_labels2, test2, test_labels2 = ld.load_monks_dataset(1)
|
||
train3, train_labels3, test3, test_labels3 = ld.load_monks_dataset(2)
|
||
train4, train_labels4, test4, test_labels4 = ld.load_monks_dataset(3)
|
||
train5, train_labels5, test5, test_labels5 = ld.load_congressional_dataset(train_ratio = 0.7)
|
||
|
||
|
||
# # Algorithme des k plus proches voisins (kNN)
|
||
#
|
||
# Dans cette section, on présente les résultats obtenus pour l'algorithme des k plus proches voisins. Ce n'est pas un algorithme d'apprentissage à proprement parler, car il n'y a aucun modèle d'entrainé. On prédit la classe d'un nouvel élément en recherchant les $k$ plus proches voisins selon une métrique choisie. Dans notre cas, nous utiliserons la distance de Minkowski, qui est une généralisation de la distance euclidienne et de la distance de Manhattan à l'aide d'un paramètre $p$. Pour nos besoins, on le fixe à $p=2$, soit la distance euclidienne.
|
||
#
|
||
# $${\displaystyle D\left(X,Y\right)=\left(\sum _{i=1}^{N}|o_{i}-s_{i}|^{p}\right)^{1/p}}$$
|
||
#
|
||
# On peut ainsi itérer sur différentes valeurs de ce paramètre pour trouver la mesure la plus adaptée au problème, tout en réutilisant la même fonction. Cette métrique s'utilise aurant pour des domaines de valeurs continus que discrets.
|
||
#
|
||
# ## Pseudocode
|
||
#
|
||
# - Initialisation
|
||
#
|
||
# ```
|
||
# k = 5
|
||
# minkowski_p = 2
|
||
# ```
|
||
#
|
||
# - Entrainement
|
||
#
|
||
# ```
|
||
# Copier le jeu d'entrainement et les étiquettes d'entrainement dans la mémoire du modèle
|
||
# ```
|
||
#
|
||
# - Prédiction
|
||
# ```
|
||
# Pour une observation x_i:
|
||
# Entrainement <- Vrai si on fait le premier entrainement
|
||
# T = copie jeu d'entrainement
|
||
# L = copie des étiquettes d'entrainement
|
||
# K = tableau de paires (point, distance) de longueur k
|
||
# Si Entrainement:
|
||
# Enlever x de T et l'étiquette de x_i de L
|
||
# Pour chaque observation t_j, j=[1,k]) de T:
|
||
# d(x_i,t_i) = distance de Minkowski entre x_i et t_j
|
||
# K[j] <- (t_i,d(x_i,t_j))
|
||
# Pour chaque observation t_j, j=[k+1,N-1] de T:
|
||
# d(x,t_i) = distance de Minkowski entre x_i et t_j
|
||
# d_max <- distance maximum dans K
|
||
# pos_d_max <- position de d_max dans K
|
||
# Si d(x_i,t_j) < d_max
|
||
# Remplacer le point K[pos_d_max] par (t_j,d(x,t_j))
|
||
# s <- mode des valeurs des étiquettes des points dans K
|
||
# retourner s
|
||
# ```
|
||
#
|
||
# - Test
|
||
#
|
||
# ```
|
||
# Pour chaque observation x_i, i=1,N:
|
||
# S_i <- Prédiction(x_i)
|
||
# M <- matrice de confusion avec les étiquettes d'entrainement et les étiquettes S
|
||
# Calculer les métriques depuis M
|
||
# ```
|
||
#
|
||
# - Validation croisée
|
||
#
|
||
# ```
|
||
# K <- Valeurs à tester pour le nombre de voisins
|
||
# Pour un jeu d'entrainement x
|
||
# Permuter aléatoirement les nombre de 1 à N
|
||
# Diviser la permutation en L groupes approximativement égaux
|
||
# Pour l dans L:
|
||
#
|
||
#
|
||
# Pour k dans K:
|
||
# Pour l dans L:
|
||
# Effectuer l'entrainement avec k voisins, x[sans l] comme jeu d'entrainement
|
||
# Effectuer le test avec x[l] comme jeu de validation
|
||
# Calculer l'exactitude
|
||
# Prendre la moyenne des exactitudes
|
||
# Prendre le k avec la meilleur exactitude moyenne
|
||
# ```
|
||
|
||
# ## Iris Dataset
|
||
|
||
# On utilise 70% des données pour le jeu d'entrainement et 30% des données pour le jeu de test
|
||
|
||
# On crée un premier modèle afin d'identifier la meilleure valeur de k
|
||
|
||
# In[48]:
|
||
|
||
|
||
get_ipython().run_cell_magic('capture', '--no-display', 'findbest_Knn = Knn.Knn()\nmeilleur_k = findbest_Knn.set_best_k(train1, \n train_labels1, \n nb_split=5, \n k_potentiel=range(2,12))')
|
||
|
||
|
||
# On crée maintenant un nouveau modèle où on initialise la valeur de K avec celle trouvée précédemment
|
||
|
||
# In[49]:
|
||
|
||
|
||
myKnn = Knn.Knn(meilleur_k)
|
||
|
||
|
||
# On effectue l'entrainement du modèle (la copie du jeu d'entrainement et des étiquettes en mémoire) et on obtient les mesures de validation pour ce jeu d'entraînement. Les valeurs des métriques de précision et de rappel sont calculées pour chacune des étiquettes.
|
||
|
||
# In[50]:
|
||
|
||
|
||
training_iris_knn = myKnn.train(train1, train_labels1)
|
||
|
||
|
||
# On effectue maintenant le test avec l'échantillon de test
|
||
|
||
# In[51]:
|
||
|
||
|
||
test_iris_knn = myKnn.test(test1, test_labels1)
|
||
|
||
|
||
# ## Monks Dataset
|
||
|
||
# ### Premier sous-ensemble
|
||
|
||
# - On identifie la meilleure valeur de k
|
||
|
||
# In[52]:
|
||
|
||
|
||
findbest_Knn = Knn.Knn()
|
||
meilleur_k = findbest_Knn.set_best_k(train2,
|
||
train_labels2,
|
||
nb_split=5,
|
||
k_potentiel=range(2,12))
|
||
|
||
|
||
# In[53]:
|
||
|
||
|
||
myKnn2 = Knn.Knn(meilleur_k)
|
||
|
||
|
||
# - On effectue l'entrainement du modèle
|
||
|
||
# In[54]:
|
||
|
||
|
||
training_monks1_knn = myKnn2.train(train2, train_labels2)
|
||
|
||
|
||
# - On effectue maintenant le test avec l'échantillon de test
|
||
|
||
# In[55]:
|
||
|
||
|
||
test_monks1_knn = myKnn2.test(test2, test_labels2)
|
||
|
||
|
||
# ### Second sous-ensemble
|
||
|
||
# - On identifie la meilleure valeur de k
|
||
|
||
# In[56]:
|
||
|
||
|
||
findbest_Knn = Knn.Knn()
|
||
meilleur_k = findbest_Knn.set_best_k(train3,
|
||
train_labels3,
|
||
nb_split=5,
|
||
k_potentiel=range(2,12))
|
||
|
||
|
||
# In[57]:
|
||
|
||
|
||
myKnn3 = Knn.Knn(meilleur_k)
|
||
|
||
|
||
# - On effectue l'entrainement du modèle
|
||
|
||
# In[58]:
|
||
|
||
|
||
training_monks2_knn = myKnn3.train(train3, train_labels3)
|
||
|
||
|
||
# - On effectue maintenant le test avec l'échantillon de test
|
||
|
||
# In[59]:
|
||
|
||
|
||
test_monks2_knn = myKnn3.test(test3, test_labels3)
|
||
|
||
|
||
# ### Troisième sous-ensemble
|
||
|
||
# - On identifie la meilleure valeur de k
|
||
|
||
# In[60]:
|
||
|
||
|
||
findbest_Knn = Knn.Knn()
|
||
meilleur_k = findbest_Knn.set_best_k(train4,
|
||
train_labels4,
|
||
nb_split=5,
|
||
k_potentiel=range(2,12))
|
||
|
||
|
||
# In[61]:
|
||
|
||
|
||
myKnn4 = Knn.Knn(meilleur_k)
|
||
|
||
|
||
# - On effectue l'entrainement du modèle
|
||
|
||
# In[62]:
|
||
|
||
|
||
training_monks3_knn = myKnn4.train(train4, train_labels4)
|
||
|
||
|
||
# - On effectue maintenant le test avec l'échantillon de test
|
||
|
||
# In[63]:
|
||
|
||
|
||
test_monks3_knn = myKnn4.test(test4, test_labels4)
|
||
|
||
|
||
# ## Congressional Voting Records Dataset
|
||
|
||
# - On identifie la meilleure valeur de k
|
||
|
||
# In[64]:
|
||
|
||
|
||
findbest_Knn = Knn.Knn()
|
||
meilleur_k = findbest_Knn.set_best_k(train5,
|
||
train_labels5,
|
||
nb_split=5,
|
||
k_potentiel=range(2,12))
|
||
|
||
|
||
# In[65]:
|
||
|
||
|
||
myKnn5 = Knn.Knn(meilleur_k)
|
||
|
||
|
||
# - On effectue l'entrainement du modèle
|
||
|
||
# In[66]:
|
||
|
||
|
||
training_congres_knn = myKnn5.train(train5, train_labels5)
|
||
|
||
|
||
# - On effectue maintenant le test avec l'échantillon de test
|
||
|
||
# In[67]:
|
||
|
||
|
||
test_congres_knn = myKnn5.test(test5, test_labels5)
|
||
|
||
|
||
# # Algorithme Bayes Naïf
|
||
#
|
||
# Cet algorithme est basé sur la règle de Bayes:
|
||
#
|
||
# $$
|
||
# P(C|X) = \frac{P(X|C)P(C)}{P(X)}
|
||
# $$
|
||
#
|
||
# Dans notre cas, le dénominateur est une constante et ne nous intéresse pas. Nous le représentons par la lettre $\alpha$
|
||
#
|
||
# En posant l'hypothèse de l'indépendance conditionnelle entre les caractéristiques $X_1,\ldots,X_m$, on peut réécrire la règle comme suit:
|
||
#
|
||
# $$
|
||
# P(C|X) = \alpha P(X) \prod_{f=1}^m P(X_f|C)
|
||
# $$
|
||
#
|
||
# Dans le cas de variables descriptives continues, la probabilité $P(X_f|C)$ prend plutôt la forme d'une distribution de probabilités. On utilisera alors la fonction de densité de probabilités de la loi gaussienne, avec la moyenne et l'écart-type estimés à partir des données.
|
||
#
|
||
# ## Pseudocode
|
||
#
|
||
# ### Initialisation
|
||
#
|
||
# Il n'y a aucun paramètre à initialiser
|
||
#
|
||
# ### Entrainement
|
||
#
|
||
# L'entrainement se fait en deux parties. On calcule d'abord les probabilités à priori des classes de l'étiquette $\mathbf{P}(C)$
|
||
#
|
||
# ```
|
||
# T = copie jeu d'entrainement
|
||
# L = copie des étiquettes d'entrainement
|
||
# Pour c dans unique(L):
|
||
# Compteur=0
|
||
# Pour l dans L:
|
||
# Si l=c:
|
||
# Compteur+=1
|
||
# P(C=c) = Compteur/N
|
||
# ```
|
||
#
|
||
# On calcule ensuite les probabilités conditionnelles des caractéristiques sachant la classe de l'étiquette $\mathbf{P}(F_1,\ldots,F_m|C)$
|
||
#
|
||
# ```
|
||
# F <- Liste des caractéristiques
|
||
# Pour c dans unique(L):
|
||
# TS <- filtrer(T si L=c)
|
||
# NS <- taille(TS)
|
||
# Pour f dans F:
|
||
# Si Gaussien:
|
||
# Parametres(C=c,F=f) = (moyenne(TS[f]), écart-type(TS[f]))
|
||
# Sinon:
|
||
# Pour v dans unique(TS[f]):
|
||
# Compteur = 0
|
||
# Pour l dans TS[f]:
|
||
# Si l=v:
|
||
# Compteur+=1
|
||
# P(C=c,F=f,V=v) = Compteur/NS
|
||
# ```
|
||
#
|
||
# Pour la prédiction, on ne calcule pas le facteur de régularisation $\alpha$ pour amener les probabilité à 1, car ce qui nous intéresse, c'est une relation d'ordre et celle-ci est inchangée si on la divise par un nombre positif.
|
||
#
|
||
# ### Prédiction
|
||
#
|
||
# ```
|
||
# Pour c dans unique(L):
|
||
# Produit=0
|
||
# Pour f dans F:
|
||
# Pour l dans TS[f]:
|
||
# Si Gaussien:
|
||
# Si Parametres(C=c,F=f) existe:
|
||
# Produit *= Densité_Gaussien(l,Parametres(C=c,F=f))
|
||
# Sinon
|
||
# Si P(C=c,F=f,V=l) existe:
|
||
# Produit *= P(C=c,F=f,V=l)
|
||
# P(X|c) = Produit
|
||
# Retourner c où P(X|c) = Max(P(X|C))
|
||
# ```
|
||
#
|
||
# ### Test
|
||
#
|
||
# ```
|
||
# Pour chaque observation x_i, i=1,N:
|
||
# S_i <- Prédiction(x_i)
|
||
# M <- matrice de confusion avec les étiquettes d'entrainement et les étiquettes S
|
||
# Calculer les métriques depuis M
|
||
# ```
|
||
|
||
# ## Iris Dataset
|
||
#
|
||
# Comme ce jeu de données présente des caractéristiques continues, on utilisera la variante gaussienne du Bayes Naif
|
||
|
||
# In[68]:
|
||
|
||
|
||
BN = BayesNaif.BayesNaif(True)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon d'entrainement
|
||
|
||
# In[69]:
|
||
|
||
|
||
train_iris_nb = BN.train(train1, train_labels1)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon de test
|
||
|
||
# In[70]:
|
||
|
||
|
||
test_iris_nb = BN.test(test1,test_labels1)
|
||
|
||
|
||
# ## Monks Dataset
|
||
#
|
||
# Comme ce jeu de données présente des caractéristiques discrètes, on n'utilise pas la variante gaussienne du Bayes Naif
|
||
|
||
# ### Premier sous-ensemble
|
||
|
||
# In[71]:
|
||
|
||
|
||
BN2 = BayesNaif.BayesNaif(False)
|
||
|
||
|
||
# In[72]:
|
||
|
||
|
||
train_monks1_nb = BN2.train(train2, train_labels2)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon de test
|
||
|
||
# In[73]:
|
||
|
||
|
||
test_monks1_nb = BN2.test(test2,test_labels2)
|
||
|
||
|
||
# ### Second sous-ensemble
|
||
|
||
# In[74]:
|
||
|
||
|
||
BN3 = BayesNaif.BayesNaif(False)
|
||
|
||
|
||
# In[75]:
|
||
|
||
|
||
train_monks2_nb = BN3.train(train3, train_labels3)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon de test
|
||
|
||
# In[76]:
|
||
|
||
|
||
test_monks2_nb = BN3.test(test3,test_labels3)
|
||
|
||
|
||
# ### Troisième sous-ensemble
|
||
|
||
# In[77]:
|
||
|
||
|
||
BN4 = BayesNaif.BayesNaif(False)
|
||
|
||
|
||
# In[78]:
|
||
|
||
|
||
train_monks3_nb = BN4.train(train4, train_labels4)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon de test
|
||
|
||
# In[79]:
|
||
|
||
|
||
test_monks3_nb = BN4.test(test4,test_labels4)
|
||
|
||
|
||
# ## Congressional Voting Records Dataset
|
||
#
|
||
# Comme ce jeu de données présente des caractéristiques discrètes, on n'utilise pas la variante gaussienne du Bayes Naif
|
||
|
||
# In[80]:
|
||
|
||
|
||
BN5 = BayesNaif.BayesNaif(False)
|
||
|
||
|
||
# In[81]:
|
||
|
||
|
||
train_congres_nb = BN5.train(train5, train_labels5)
|
||
|
||
|
||
# Mesures de performance sur l'échantillon de test
|
||
|
||
# In[82]:
|
||
|
||
|
||
test_congres_nb = BN5.test(test5, test_labels5)
|
||
|
||
|
||
# # Conclusion
|
||
|
||
# ## Tableau sommaire
|
||
|
||
# In[83]:
|
||
|
||
|
||
tous_resultats = [["Iris",test_iris_knn,test_iris_nb],
|
||
["MONKS1",test_monks1_knn,test_monks1_nb],
|
||
["MONKS2",test_monks2_knn,test_monks2_nb],
|
||
["MONKS3",test_monks3_knn,test_monks3_nb],
|
||
["Votes",test_congres_knn,test_congres_nb]]
|
||
|
||
|
||
# ### Exactitude
|
||
#
|
||
# Le tableau ci-dessous présente l'exactitude pour les modèles KNN et NB ainsi que le meilleur modèle dans ce cas. On remarque que pour le jeu de données Iris, le résultat obtenu est le même pour les deux modèles. Pour les jeux MONKS, dans deux des trois cas, le modèle KNN est meilleur, mais les deux résultats sont faibles. Dans le troisième cas, le modèle NB est largement plus exact, une situation similaire se reproduit pour les données sur les votes.
|
||
|
||
# In[84]:
|
||
|
||
|
||
print(np.array([(i[0],
|
||
i[1][1],
|
||
i[2][1],
|
||
"KNN" if i[1][1]>i[2][1] else "NB") for i in tous_resultats]))
|
||
|
||
|
||
# ### Précision
|
||
#
|
||
# On obtient les mêmes constats que précédemment au niveau de la précision
|
||
|
||
# In[85]:
|
||
|
||
|
||
print(np.array([(i[0],
|
||
i[1][2],
|
||
i[2][2],
|
||
"KNN" if i[1][2]>i[2][2] else "NB") for i in tous_resultats]))
|
||
|
||
|
||
# ### Rappel
|
||
#
|
||
# Pour le rappel, on obtient des résultats différents. Pour le jeu de données MONKS1, l'ordre des valeurs du rappel est inversé. Ceci nous montre qu'il est important de sélectionner la mesure la plus importante pour le problème que nous voulons résoudre, car il est possible d'obtenir un conclusion erronée en utilisant une autre.
|
||
|
||
# In[86]:
|
||
|
||
|
||
print(np.array([(i[0],
|
||
i[1][3],
|
||
i[2][3],
|
||
"KNN" if i[1][3]>i[2][3] else "NB") for i in tous_resultats]))
|
||
|
||
|
||
# ### Temps d'exécution
|
||
#
|
||
# Dans tous les cas, le temps de calcul du Naive Bayes est signicativement plus court.
|
||
|
||
# In[87]:
|
||
|
||
|
||
print(np.array([(i[0],
|
||
i[1][4],
|
||
i[2][4],
|
||
"KNN" if i[1][4]<i[2][4] else "NB") for i in tous_resultats]))
|
||
|
||
|
||
# ## Observations
|
||
#
|
||
# - Le jeu de données Iris présente un problème de classification bien balancé. Les deux algorithmes sont performants et s'exécutent rapidement.
|
||
# - Le jeu de données MONKS représentent des problèmes de classification binaire avec peu d'observations. Les algorithmes ne performent pas très bien lors des tests.
|
||
# - Le jeu de données Congressional Voting Records contient davantage de caractéristiques, mais beaucoup moins de modalités. C'est aussi un problème de classification binaire. Un algorithme tel que KNN pourrait tirer des conclusions erronées étant donné que les distances entre les modalités sont toutes égales.
|
||
|
||
# ## Difficultés rencontrées
|
||
|
||
# ### Algorithme kNN
|
||
#
|
||
# Une des difficultés rencontrées a été d'avoir effectivement le bon nombre de voisins dans l'entraînement, car le jeu d'entrainement contient toujours l'exemple et a une distance de 0. J'ai donc du modifier l'ensemble d'entrainement pour enlever l'exemple actif lors du calcul des métriques. Ceci était nécessaire pour pouvoir calculer la meilleure valeur de $k$.
|
||
#
|
||
# ### Algorithme Bayes Naïf
|
||
#
|
||
# Comme il est possible de rencontrer une classe jamais rencontrée lors de l'entraînement, j'ai du modifier le produite des probabilités conditionnelles indépendantes pour enlever les probabilités qui ne sont pas évaluées durant l'entraînement. J'aurais pu modifier le tableau de probabilités, mais le plus simple a été de leur donner une valeur de 1, ce qui est équivalent à les ignorer dans le produit.
|