M1 BBS Data Mining TD Classification
From silico.biotoul.fr
Introduction
Afin de mettre en pratique les concepts vus en cours, nous allons nous appuyer sur des jeux de données publiques hébergées par le UC Irvine Machine Learning Repository.
Pour le premier jeu de données intitulé "mushrooms", il s'agit de classer un champignon comme comestible ou non en fonction d'attributs de type catégoriel. Pour le second - italian wines -, il s'agit de prédire le cultivar du cépage en fonction de mesures quantitatives.
Pour cela, nous utiliserons différents environnements :
- KNIME : un logiciel d'analyse qui est en fait un environnement dérivé de la plateforme de développement intégré Eclipse
- R : environnement orienté calcul numérique & statistiques
- python : un langage de programmation afin de voir l'utilisation de bibliothèque de fouille de données ainsi que pour réaliser son propre programme de classification
Environnement de travail
Nous allons utiliser quelques librairies pas toujours présentes dans un environnement par défaut. C'est l'occasion de s'initier à la gestion de différents environnements de développement et/ou d'analyse. Pour cela, nous allons utiliser l'utilitaire conda. Plus d'informtaion sur cet utilitaire sur silico Conda ou sur gitlab via un projet dans lequel vous pouvez contribuer (envoyer un mail à R. Barriot avec votre identifiant gitlab, ex: @rbarriot pour R. Barriot).
Les commandes suivantes sont à exécuter dans un terminal (surtout PAS en tant qu'administrateur/root).
# dépôts des librairies et programmes conda config --add channels conda-forge conda config --add channels bioconda # création d'un nouvel environnement contenant les librairies spécifiées conda create -n fouille r-base r-tidyverse r-ggally r-reticulate r-rmysql bioconductor-made4 r-codetools r-caTools r-rprojroot r-shiny r-plotly r-knitr r-dt r-kableextra python numpy pandas scipy scikit-learn matplotlib plotly # activation de ce nouvel environnement conda deactivate && conda activate fouille
Classification
Mushrooms - TP 2h - R + Knime - Decision trees + random forests & cross-validation & performances
Les données
Le premier jeu de données concerne des champignons. Il est publié à l'adresse : http://archive.ics.uci.edu/ml/datasets/Mushroom
La description du jeu de données est aussi accessible ici.
Le jeu de données modifié pour inclure une première ligne contenant les noms des colonnes est disponible là : Media:mushrooms.data.txt.
Analyses préliminaires avec R
Charger le jeu de données et utiliser la commande summary pour vous faire une idée du nombre d'instances de chaque classe, et du nombre de modalité de chaque facteur (attribut/dimension/variable).
Etudiez ensuite la liaison entre chaque variable et la classe. Pour cela, vous pourrez utiliser le test du χ2 d'indépendance. Utilisez également la fonction table (pour générer une table de contingence) pour la combiner avec la fonction plot afin d'explorer visuellement les biais entre chaque attribut et la classe.
Exemple de visualisation :
Ces analyses devrait vous permettre de vous faire une idée sur la pertinence d'un attribut en ce qui concerne l'objectif : classer un champignon comme comestible ou pas.
Quels attributs vous semblent les plus pertinents ?
A partir de là, il semble qu'aucun attribut peut permettre à lui seul de classer un échantillon. Nous allons donc utiliser des méthodes d'apprentissage proposées dans le logiciel KNIME.
Analyses avec KNIME
Pour cette partie, nous allons utiliser l'environnement pour la fouille de données KNIME. C'est un logiciel en Java développé à l'origine par l'université de Constance (Allemagne).
L'installation pour linux consiste à télécharger et désarchiver le contenu d'un fichier au format .tar.gz. Une copie de la dernière version a sûrement été placée sur le PC de l'intervenant : http://pc2
Après extraction, il faudra lancer l'exécutable en ligne de commande qui se trouve dans le nouveau répertoire knime_VERSION/knime.
Construction du modèle
La première étape consiste à charger les données. Dans KNIME, ajoutez un noeud File Reader (section IO pour Input/Output) et configurez-le afin de charger le fichier de données.
Comme premier exercice, ajoutez un noeud Decision Tree Learner (induction d'arbre de décision) et connectez la sortie du File Reader à l'entrée du Decision Tree Learner. Configurez ce dernier pour qu'il cherche à prédire la classe du champignon. Lancez l'éxécution de ces noeuds et visualisez l'arbre de décision inféré. Quelles sont les variables les plus importantes ?
Remarque : A la configuration du noeud Decision Tree Learner, observez les autres paramètres disponibles (mesure de pertinence d'un attribut, élagage).
Effectuez la même chose avec un classificateur bayésien naïf et visualisez le modèle obtenu.
Evaluation des performances
Afin de décider quelle méthode fonctionne le mieux (arbre de décision ou bayésien naïf) pour ce jeu de données et avec quels paramètres (gain ratio ou gini index par exemple), vous allez effectuer des validation croisées.
Pour cela, ajoutez et en configurez un noeud Cross validation (section Meta). Une leave-one-out cross validation (ou LOOCV) sera pour ce TP trop couteuse en temps (> 8000 modèles inférés par méthode). Essayez par exemple avec les valeurs 3 et 10 pour le noeud X-partitioner (3-fold ou 10-fold cross validation). Ceci aura pour effet de diviser le jeu de données en entrées en jeux de données d'apprentissage (pour le learner) et jeux de données tests (pour le modèle produit par le learner). Configurez enfin le noeud X-agregator qui confrontera la classe prédite à la classe connue.
Examinez ensuite le taux d'erreurs à l'aide d'un noeud Statistics view.
Faites varier la méthode et ces paramètres et notez à chaque fois les performances obtenues (taux d'erreurs) :
- arbre de décision
- gain ratio ou gini index
- no pruning ou MDL TP1 g2 2017
- bayésien naïf TP1 g1 2017
Qu'observez vous lorsque vous augmentez le nombre de validations croisées (3-fold vs. 10-fold) ?
FIN TP1 2h
Italian wines - TP 2h - R/tidyvers + Knime - k-nn & normalization
Les données
Le second jeu de données concerne des cépage de vins italiens. Il est publié à l'adresse : http://archive.ics.uci.edu/ml/datasets/Wine
La description du jeu de données est aussi accessible ici.
Le jeu de données modifié pour inclure une première ligne contenant les noms des colonnes est disponible ici.
Analyses avec R
Analyse descriptive
Commencez par charger le jeu de données et faire un summary.
Pour la suite, il vous est conseillé de stocker la classe dans un vecteur (par exemple y) et les données sous forme de matrice.
Tracez un camembert pour l'effectif de chaque classe.
Etudiez ensuite la distribution des valeurs de chaque dimension par rapport à la classe. Vous pourrez par exemple tracer des boites à moustache :
Notez les attributs qui vous semblent le mieux séparer les classes.
Comme vue en cours de Traitement de données biologiques, il est possible de faire une ANOVA à plusieurs facteurs afin d'estimer si les moyennes des différentes mesures sont égales et s'il y a interaction entre ces facteurs. Même si ce n'est pas le sujet d'aujourd'hui, ici, il y a clairement un effet du cultivar sur plusieurs des mesures effectuées et certaines sont sûrement corrélées. On remarquera tout de même que lorsqu'il y a plus de 2 mesures, l'analyse se complexifie.
Sur la base des distributions par classe (boxplots précédents), il semble qu'aucune des mesures n'est capable de discriminer à elle seule les différents cultivars. Par contre, il est peut-être possible de séparer les classes en combinant plusieurs variables.
Essayez de combiner quelques paires de variables parmi celles relevées précédemment. Par exemple, avec alcohol et flavonoids on obtient :
On observe que la séparation entre les classes (différentes couleurs) bien que pas mauvaise n'est pas complète pour ce couple de mesures.
Remarque : pour visualiser toutes les pairs de variables, utilisez la fonction pairs.
Avant de passer à la partie suivante, réalisez une ACP et affichez les individus sur les 2 premiers axes. Qu'observez-vous ?
Fichier "premiers pas" avec tidyverse sur ce jeu de données : Rmd - html
Analyses avec KNIME
Chargez le jeu de données et faites construire le modèle de classificateur bayésien naïf. Observez le modèle obtenu. Quelle(s) différence(s) au niveau du modèle observez-vous par rapport à celui appris sur les champignons ?
Pour choisir entre la méhotde bayésienne et celle des k plus proches voisins, effectuez des validations croisées (10-fold CV). Pour la méthode k-nn, faites varier le nombre de voisins considérés (1, 3 et 10 par exemple). Observez-vous une différence notable de performances ? par rapport à k ? par rapport à la méthode bayésienne ?
La distance calculée par k-nn est en fait sensible aux unités (et plages de valeurs) de chacune des dimensions. Refaites la validation en ayant au préalable normalisé les dimensions avec la méthode z-score.
Pour décider la méthode et ses paramètres, effectuez des validations croisées (10-fold et LOOCV) avec comme normalisation (z-score, min-max, decimal scaling) et notez les taux d'erreurs obtenus.
TP2 g1 2017 TP2 g2 2017 FIN TP2 2h
Italian wines - TP 2h - R & LDA
Analyse discriminante linéaire
L'analyse discriminante linéaire permet de trouver la combinaison linéaire des variables qui permet de séparer le mieux les classes. Pour cela, nous allons utiliser la librairie MASS :
# lecture des données dans une data.frame puis vecteur y et matrice DF=read.table('wine.data.txt',header=T,sep=',') y=as.factor(DF[,1]) mat=as.matrix(DF[,-1]) # analyse discriminante library(MASS) model = lda(x=mat, grouping=y)
Commentez le contenu de model.
Comme il y a 3 classes, on peut projeter le résultat sur 2 axes (un de moins que le nombre de classes). Faire plot(model) et commenter.
LD1 et LD2 sont les vecteurs portant les axes de la projections (vecteurs propres associées aux plus grandes valeurs propres de V-1B avec V et B les matrices de variance-covariance totale et inter-classes respectivement, cf. cours).
Pour s'en assurer, on peut tracer la projection des individus d'origine :
par(mfrow=c(1,2)) plot(model) plot(mat %*% model$scaling, col=y, pch=19)
Est-ce qu'il est possible d'obtenir a priori de bonnes performances sur ce jeu de données avec une analyse discriminante ?
Pour l'analyse des performances, vous allez faire le schéma 2/3 training et 1/3 test set :
n = nrow(mat) training = sample(n, round(2*n/3)) # tirage aléatoire de 2/3 pour le jeu d'apprentissage train = mat[training,] train_y = y[training] test = mat[-training,] # le reste pour le jeu de test test_y = y[-training]
Effectuer l'analyse discriminante avec le jeu de données d'apprentissage ainsi obtenu et la prédiction sur le jeu de données test à l'aide de la fonction predict(model, test). Commentez la sortie de la fonction predict.
Tracez le résultat avec plot et text :
Selon l'échantillon test tiré, il y aura ou non des individus mal classés : par exemple, un 2 apparaissant en vert sur le plot ci-dessus.
Remarque : la projection est sensiblement différente de la précédente puisque le jeu de données d'apprentissage est différent.
Calculer le taux d'erreurs pour votre tirage.
Analyse discriminante pas à pas
Rappels théoriques
Objectif : combinaison linéaire des variables permettant de séparer au mieux les groupes dans un nouvel espace de représentation
Dispersion intra-groupes : matrice de variance-covariance Wk
Rappel : matrice de variance-covariance
avec n le nombre d'individus et nk le nombre d'individus de la classe k
Eloignement entre les groupes : matrice de variance-covariance inter-groupes B
Dispersion totale : V = W + B
Principe : trouver les les axes factoriels qui maximisent l'éloignement des groupes par rapport à la dispersion totale
Z1 premier axe factoriel associé au vecteur u1 tel que l'on maximise
Solution : résolution de V-1Bu=λu
Mise en oeuvre
Décomposer les calculs en R afin d'afficher la projection : Tout d'abord le calcul de W, puis de B, puis de V pour résoudre V-1Bu.
TP3 g1 2017 TP3 g2 2017 FIN TP3 2h
Pour faire la classification, il faut rechercher la classe qui maximise le score (adaptation de la distance de Mahalanobis) : score(C = c,X = x) = − (X − μc)TW − 1(X − μc)
Italian wines - TP 2h - python sklearn - k-nn
Analyses avec python
Le but de cette section est d'utiliser une librairie fournissant des fonctionnalités de data mining dans un langage de programmation.
La librairie s'appelle sklearn. Nous n'en n'utiliserons qu'une toute petite partie. Pour plus d'informations, consulter son site http://scikit-learn.org
Dans cette partie, nous allons charger la librairie pour accéder à la méthode des k plus proches voisins. Au passage, cela nous permettra d'appréhender d'autres aspects :
- création d'un script utilisable en ligne de commande pleinement fonctionnel
- récupération des paramètres passés en ligne de commande
- lecture de fichiers (notamment au format CSV)
- et quelques commandes du shell afin de déterminer le meilleur k pour un jeu de données
Première étape : un script et ses paramètres en ligne de commande
Créer et un fichier texte vide, par exemple knn.py.
Pour qu'il soit considéré comme un programme, il faut qu'il ait les droits d'exécution (sous linux). Utilisez pour cela la commande chmod :
chmod a+x knn.py
Afin que le système puisse exécuter le script, la toute première ligne doit indiquer le chemin de l'interpréteur (ici python). Ajoutez les lignes suivantes :
#!/usr/bin/env python3 # -*- coding: utf-8 -*- print("Hello world")
et lancez votre programme :
./knn.py
Pour récupérer les valeurs des paramètres passés en ligne de commande vous allez utiliser une librairie : argparse
#!/usr/bin/env python3 import argparse # SCRIPT PARAMETERS parser = argparse.ArgumentParser(description='k-nn classifier.') parser.add_argument('-t', '--training', required=True, help='File containing training examples (class,att1,...') parser.add_argument('-u', '--test', required=False, help='File containing test data to estimate performances.') parser.add_argument('-k', '--k', required=False, default=5, help='Number of nearest neighbor to consider (default 5)', type=int) parser.add_argument('-n', '--normalize', required=False, action="store_true", help='Normalize values.') parser.add_argument('-v', '--verbose', required=False, action="store_true", help='Verbose output.') opt = parser.parse_args() # AFFICHAGE DES PARAMETRES PASSES EN LIGNE DE COMMANDE opt = parser.parse_args() if opt.verbose: print(opt)
Essayez votre script avec différents paramètres pour vous assurer de son fonctionnement. Par exemple :
./knn.py --k 3
Deuxième étape : chargement du jeu de d'apprentissage
Utilisation d'une librairie pour lire les fichiers au format CSV. Adaptez votre script avec les commandes suivantes pour charger le jeu de données :
import csv # LOAD TRAINING DATA (MAY EAT ALL MEMORY) y = [] data = [] with open(opt.training) as csvfile: # open the specified file csvreader = csv.reader(csvfile, delimiter=',') # instantiate CSV reader head = next(csvreader) # the first line contains the column names if opt.verbose: print("header:", head) for row in csvreader: y.append( row.pop(0) ) # the first column contains the class data.append( row )
Essayez votre script avec le jeu d'apprentissage Media:Italian.wine.training.data.txt
Troisième étape : classification d'un individu
Dans un premier temps, nous allons transformer le jeu de données en matrice de la librairie numérique numpy. Rajoutez les lignes suivantes :
import numpy as np X = np.array(data).astype(np.float) # convert data to array of float
Création du classificateur (source: http://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbors-classification ):
from sklearn import neighbors # INSTANTIATE CLASSIFIER clf = neighbors.KNeighborsClassifier( opt.k ) clf.fit(X, y)
Création d'un individu et utilisation du classificateur :
sample = [12.87, 4.61, 2.48, 21.5, 86.0, 1.7, 0.65, 0.47, 0.86, 7.65, 0.54, 1.86, 625.0] print(clf.predict( [sample]) ) # predict expects a list of samples to classify
De quelle cultivar serait issu ce vin ?
Si besoin d'installer scikit-learn et scipy :
pip --version python3 --version python3 -m pip search sklearn python3 -m pip install --user sklearn python3 -m pip search scipy python3 -m pip install --user scipy
Quatrième étape : performances
Jeu de données test : Media:Italian.wine.test.data.txt
Rajoutez une partie pour charger le jeu de données test fourni (même format que le jeu d'apprentissage). Pour chacun des individus, effectuez la classification et comparez la classe prédite à la classe réelle afin de déterminer le taux d'erreurs.
Vous pourrez optimiser l'occupation mémoire du script si vous ne chargez pas la totalité des données test mais que vous effectuez la classification à la lecture de chaque individu.
Détermination de la meilleure valeur de k
Etant donnée la petite taille du jeu de données, il n'est pas nécessaire de modifier le script pour optimiser le balayage du paramètre k : il suffit de lancer plusieurs fois le script avec un k différent.
Boucle for en shell :
for i in 1 2 3; do echo iteration i: $i; done
Remarque : les retours à la ligne dans l'exemple ci-dessus sont facultatifs
La boucle for va simplement itérer sur une liste (ici une chaîne de caractère qui va être découpée sur les blancs).
Il est possible de remplacer cette liste par le résultat d'une commande. Celle qui va nous servir ici est la commande seq qui permet de générer une séquence d'entiers (cf. man seq) :
seq 10
Pour s'en servir dans une boucle for :
for i in $(seq 10); do echo iteration $i; done
Utilisez une boucle for pour déterminer la meilleure valeur de k.
TP4 g2 2017
Dernière étape : normalisation
Comme vu avec KNIME, les données utilisées nécessitent une étape de normalisation.
Pour la normalisation, nous allons utiliser les valeurs centrées réduites (avec la moyenne et l'écart-type) :
La librairie numpy fournit les fonctions pour le calcul de la moyenne et de l'écart-type :
- http://docs.scipy.org/doc/numpy/reference/generated/numpy.mean.html
- http://docs.scipy.org/doc/numpy/reference/generated/numpy.std.html
Vous pouvez utiliser ces fonctions directement sur la matrice X définie précédemment (jeu d'apprentissage) afin d'obtenir ces mesures par colonnes.
Comparez les performances obtenues avec et sans normalisation en gérant le paramètre --normalize du script.
TP4 g1 2017 FIN TP4 2h
Mushrooms - TP 4h - python + pandas - Naive Bayes
Vous allez maintenant programmer un classificateur bayésien naïf en python (sans l'aide d'une librairie).
Etapes pour la construction et l'utilisation d'un classificateur bayésien naïf :
- Lecture du jeu d'apprentissage pour construire la table de probabilité. Utilisation
- des fréquences pour les variables discrètes
- d'une gaussienne pour les variables continues
- Lecture des échantillons à classer
- calcul de la vraisemblance de chaque classe
- attribution de la classe la plus vraisemblable
Le jeu de données mushrooms étant essentiellement constitué de variables discrètes, la tâche sera plus rapide.
La table de probabilité devrait contenir :
- classe EDIBLE : effectifs
- classe POISONOUS : effectifs
- classe EDIBLE, attribut cap-surface : effectifs BELL, effectifs CONICAL, effectifs CONVEX, effectifs FLAT, effectifs KNOBBED, effectifs SUNKEN
- classe POISONOUS, attribut cap-surface : effectifs BELL, effectifs CONICAL, effectifs CONVEX, effectifs FLAT, effectifs KNOBBED, effectifs SUNKEN
- classe EDIBLE, attribut cap-shape : effectifs FIBROUS, ...
- ...
Ceci se représente très bien avec un dictionnaire de dictionnaires de dictionnaires : occurrences[ classe ] [ attribut ] [ modalité ] = effectifs
Ecrire un script python qui scanne un jeu de données d'apprentissage et affiche la table d’occurrences (le modèle). Ce script devrait utiliser la librairie argparse afin d'utiliser les paramètres de la ligne de commande (comme le script knn.py précédemment).
Jeu de données d'apprentissage : Media:Mushrooms.training.data.txt
TP5 g2 2017
Ecrire une fonction attribuant la classe la plus probable d'un individu à l'aide du théorème de Bayes.
Rappel :
Evaluez les performances avec le jeu de test fourni et comparez avec les résultats obtenus avec KNIME.
TP6 g2 2017
Jeu de données de test : Media:Mushrooms.test.data.txt
TP5 g1 2017
En considérant la classe EDIBLE comme positive et la classe POISONOUS comme négative, calculez :
- sensibilité = VP/P
- spécificité = VN/N
- Précision = VPP = VP/PP
- FDR = 1 - VPP = FP/PP
- VPN = VN/PN
- Exactitude = (VP+VN)/(P+N)
- Taux d'erreurs = 1 - Exactitude = (FP+FN)/(P+N)
Résultats attendus
Tests: 2806 , Errors: 8 , Error rate: 0.29 % prediction/reality | P 1535 | N 1271 P 1529 | TP 1528 | FP 1 N 1277 | FN 7 | TN 1270 Sensitivity TP/P = 0.995439739414 Specificity TN/N = 0.999213217939 Precision TP/PP = 0.999345977763 Accuracy (TP+TN) / (P+N) = 0.9971489665
TP6 g1 2017
Début du script
#!/usr/bin/env python import argparse import csv import numpy as np import scipy.stats import sys from pprint import pprint import pandas as pd # SCRIPT PARAMETERS parser = argparse.ArgumentParser(description='Naive Bayesian learner and classifier.') parser.add_argument('--training', required=True, help='CSV File with a header row in containing training examples.') parser.add_argument('--test', required=False, help='CSV File with a header row containing new objects to be classified for performance evaluation.') parser.add_argument('--sample', required=False, help='CSV File with a header row containing new objects to be classified. NOT YET IMPLEMENTED') parser.add_argument('--model', nargs='?', const=True, help='Only displays the probability table.') parser.add_argument('--gauss', nargs='?', const=True, help='Data is numeric, thus, gaussian should be used to compute probabilities.') parser.add_argument('--delimiter', required=False, default=',', help='Field delimiter in CSV files.') opt = parser.parse_args()
Italian wines
Adaptez le script précédent pour classer les vins italiens (données numériques continues).
Votre script acceptera en paramètre une option supplémentaire :
parser.add_argument('--gauss', nargs='?', const=True, help='Data is numeric, thus, gaussian should be used to compute probabilities.')
Vous pourrez vous aider de la partie stats de la librairie scipy :
import scipy.stats
dont notamment la loi normale et sa fonction de densité https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.stats.norm.html#scipy.stats.norm
Quelles performances obtenez-vous ? FIN TP5&6 2h
Clustering
Italian wines - TP 4h - clustering
Objectfis : Mise en oeuvre des concepts vus en cours concernant l'évaluation des résultats d'un clustering.
Etapes :
- Sous R, normaliser le jeu de données wine (centrage et réduction)
- Réaliser une mise à l'échelle multi-dimensionnelle pour visualiser les différents résultats que nous obtiendrons ensuite. Pour cela, calculer la matrice de distance puis faire la mise à l'échelle avec la fonction cmdscale. Afficher le plot en faisant apparaître les classes connues.
- Réaliser un clustering (cf. fonction kmeans et ses paramètres de la librairie stats) et afficher le résultat comme précédemment mais en faisant en plus apparaître les clusters.
- Evaluation non supervisée : Calcul du coefficient de silhouette (pour chaque objet et pour le clustering)
- Utilisation du coefficient de silhouette pour déterminer le nombre de clusters (paramètre k de k-means)
- Evaluation supervisée : Calcul de la pureté et de l'entropie, et leur utilisation pour déterminer k
- Comparaison de clustering : utiliser le coefficient simple d'appariement et l'indice de Jaccard pour comparer k-means aux classes réelles.
Rappels :
Coefficient de silhouette :
- ai : distance moyenne de l'objet i aux objets de son cluster
- bi : minimum des moyennes des distances de l'objet i aux objets des autres clusters
-
Pureté :
pi = maxj(pij) en d'autres termes, la fréquence de la classe majoritaire dans le cluster i
avec K le nombre de clusters, pi la pureté du cluster i, m le nombre d'objets et mi la taille du cluster i.
Entropie :
avec L le nombre de classes et pij = mij / mi la probabilité qu'un membre du cluster i appartienne à la classe j
avec K le nombre de clusters et j les classes
FIN TP7&8 2h