silico.biotoul.fr
 

M1 BBS Data Mining TD Classification

From silico.biotoul.fr

Jump to: navigation, search

Contents

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

Mushrooms

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 ici.

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 :

Image:mushrooms.gill.attachment.png

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).

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

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 :

Image:Italian.wine.alcohol.boxplot.png

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 :

Image:Italian.wine.alcohol-flavonoids.png

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 ?


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

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])
wine=DF[,-1]
# analyse discriminante
library(MASS)
sol = lda(x=wine, grouping=y)

Commentez le contenu de sol.

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(sol) 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(sol)
plot(as.matrix(wine) %*% sol$scaling, col=y, pch=19)

Image:Italian.wine.sol-projection.png


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(wine)
training = sample(n, round(2*n/3)) # tirage aléatoire de 2/3 pour le jeu d'apprentissage
train = wine[training,]
train_y = y[training]
test = wine[-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(sol, test). Commentez la sortie de la fonction predict.

Tracez le résultat avec plot et text :

Image:Italian.wine.lda.cross-validation.png

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  (X - \overline{X})^T(X - \overline{X})/ n

W = \frac{1}{n} \sum_k n_k \times W_k 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

 B = \frac{1}{n} \sum_k n_k (\mu_k -\mu)(\mu_k-\mu)^T

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 \frac{u_1^TBu_1}{u_1^TVu_1}

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)

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) : x_{norm} = \frac{x - \mu}{\sigma}

La librairie numpy fournit les fonctions pour le calcul de la moyenne et de l'écart-type :

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 (suite)

Vous allez maintenant programmer un classificateur bayésien naïf en python (sans l'aide d'une librairie).

Jeu d'apprentissage, table de probabilité et classification d'un objet selon un classificateur bayésien naïf.

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 : P(C/X) = \frac{P(X/C) P(C)}{P(X)}

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/python
 
import argparse
import csv
import numpy
import scipy.stats
import sys
from pprint import pprint
 
# 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 (suite)

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

Italian wines (fin) : clustering

Objectfis : Mise en oeuvre des concepts vus en cours concernant l'évaluation des résultats d'un clustering.

Etapes :

  1. Sous R, normaliser le jeu de données wine (centrage et réduction)
  2. Réaliser une ACP non normée. Ceci nous permettra de visualiser les différents résultats. Afficher le plot sur les 2 premiers axes en faisant apparaître les classes connues
  3. 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.
  4. Evaluation non supervisée : Calcul du coefficient de silhouette (pour chaque objet et pour le clustering)
  5. Utilisation du coefficient de silhouette pour déterminer le nombre de clusters (paramètre k de k-means)
  6. Evaluation supervisée : Calcul de la pureté et de l'entropie, et leur utilisation pour déterminer k
  7. 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
  • s_i = \frac{b_i - a_i}{max(a_i,b_i)}
Résultats de k-means pour k=3 sur le jeu de données itlian wine. Les nombres et niveaux de gris correspondent au coefficient de silhouette de chacun des objets (0 : noir, 1 : blanc). Les objets sont projetés sur les 2 premiers axes de l'ACP.

Pureté :

pi = maxj(pij) en d'autres termes, la fréquence de la classe majoritaire dans le cluster i

purity=\sum_{i=1}^K \frac{m_i}{m}p_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 :

e_i = - \sum_{j=1}^{L} p_{ij} \log p_{ij} avec L le nombre de classes et pij = mij / mi la probabilité qu'un membre du cluster i appartienne à la classe j

E = \sum_{i=1}^{K} \frac{m_i}{m} e_i avec K le nombre de clusters et j les classes

FIN TP7&8 2h