Travaux pratiques - Algorithmes à noyaux

L’objectif de cette séance de travaux pratiques est de montrer l’utilisation des plusieurs algorithmes à noyaux en python (scikit-learn). Nous allons aborder dans cette séance les One Class SVM (OCSVM) et SVM pour la régression.

Références externes utiles :

One Class SVM (OCSVM)

Les OCSVM sont des estimateurs de support de densité pour des données multidimensionnelles. L’idée derrière l’implémentation est de trouver l’hyperplan le plus éloigné de l’origine qui sépare les données de l’origine.

Dans scikit-learn, les One-Class SVM sont implémentés dans le module sklearn.svm, n’hésitez pas à consulter la documentation de ce module pour plus de détails. Nous utilisons un noyau gaussien pour faire la détection des outliers dans un échantillon de données en deux dimensions. Pour cet exemple, nous générons deux clusters gaussiens auxquels nous ajoutons 10% de données anormales, tirées au hasard uniformément dans l’espace à deux dimensions considéré :

import numpy as np
import matplotlib.pyplot as plt

from sklearn import svm

# On créé deux groupes séparés (échantillons de gaussiennes)
N = 200
data1 = 0.3 * np.random.randn(N // 2, 2) + [2,2]
data2 = 0.3 * np.random.randn(N // 2, 2) - [2,2]

# On créé 10% de données anormales (*outliers*)
outliers = np.random.uniform(size=(N // 10, 2), low=-6, high=6)

# Les données = groupes + anomalies
X = np.concatenate((data1, data2, outliers))

plt.scatter(X[:,0], X[:,1]) and plt.show()

Nous pouvons ensuite créer le modèle de one-class SVM avec sklearn. Le paramètre nu correspond à la proportion maximale d’erreurs autorisées, c’est-à-dire au pourcentage maximal de points du jeu de données que l’on acceptera d’exclure de notre classe. Cette fraction doit peu ou prou correspondre au pourcentage de données anormales attendu dans le jeu de données. Dans notre cas, nous savons qu’il y a environ 10% d”outliers donc nous pouvons choisir nu=0.1.

# Construction du modèle (noyau RBF)
clf = svm.OneClassSVM(nu=0.1, kernel="rbf", gamma=0.05)
clf.fit(X)

Le code suivant permet alors de tracer les frontières (plus exactement les lignes de niveaux) de la fonction de décision de la OneClassSVM ainsi entraînée :

# Afficher les points et les vecteurs les plus proches du plan de séparation
xx, yy = np.meshgrid(np.linspace(-7, 7, 500), np.linspace(-7, 7, 500))
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
y_pred = clf.predict(X)

# Choix du jeu de couleurs
plt.set_cmap(plt.cm.Paired)
# Trace le contour de la fonction de décision
plt.contourf(xx, yy, Z)
# Affiche les points considérés comme "inliers"
plt.scatter(X[y_pred>0,0], X[y_pred>0,1], c='white', edgecolors='k', label='inliers')
# Affiche les points considérés comme "outliers"
plt.scatter(X[y_pred<=0,0], X[y_pred<=0,1], c='black', label='outliers')
plt.legend()
plt.show()

Question

Testez plusieurs valeurs pour le paramètre gamma. Pour quelle valeur le résultat semble meilleur (moins de outliers incorrectement classés) ? En pratique on ne connait pas les outliers, l’utilité des OCSVM est de les détecter. Le paramètre nu doit aussi avoir une bonne valeur pour ne pas sous-estimer (ou sur-estimer) le support de la distribution.

Correction

Visuellement, une valeur de gamma entre 1e-4 et 5e-2 semble acceptable : les centres des gaussiennes sont identifiées comme inliers tandis que les points plus éloignés sont marqués comme aberrants (outliers), ce qui correspond à la façon dont on a généré les données.

Question

Remplacez le noyau rbf par un noyau linéaire. Quel problème constatez-vous ?

Correction

Le noyau linéaire ne permet que de trouver des hyperplans séparateurs, c’est-à-dire des droites (dans notre cas bidimensionnel). On ne peut donc pas séparer les inliers et les outliers de cette façon dans notre cas car la frontière réelle n’est pas linéaire !

SVM pour la régression

Dans le cas de la régression, l’objectif est d’apprendre un modèle qui prédit les valeurs d’une fonction à partir des valeurs des variables d’entrée. L’idée est de trouver la fonction la plus « lisse » qui passe par les (ou à proximité des) données d’apprentissage. Scikit-learn implémente le modèle SVR (epsilon-regression) dans le module Python sklearn.svm.SVR dont vous pouvez bien sûr consulter la documentation.

Dans cette partie nous présenterons la régression dans le cas unidimensionnel en comparant plusieurs noyaux avec scikit-learn. Le module sklearn.svm.SVR permet de faire varier tous les paramètres.

Il faut d’abord importer les modules :

import numpy as np
import matplotlib.pyplot as plt

from sklearn.svm import SVR

Données synthétiques

Dans un premier temps, nous allons travailler sur des données générées. Notre objectif sera de reproduire une sinusoïde, comme dans le TP sur les arbres de décision :

X = np.sort(5 * np.random.rand(40, 1), axis=0)
y = np.sin(X).ravel()

On ajoute un bruit aléatoire sur 20% des observations. Nos échantillons d’entraînement correspondent donc à la courbe suivante :

y[::5] += 3 * (0.5 - np.random.rand(8))
plt.scatter(X, y, color='darkorange', label='Données')

Nous pouvons facilement entraîner trois modèles de SVM pour la régression grâce à la classe SVR de scikit-learn :

# Création des SVM
C = 1e3
svr_rbf = SVR(kernel='rbf', C=C, gamma=0.1)
svr_lin = SVR(kernel='linear', C=C)
svr_poly = SVR(kernel='poly', C=C, degree=2)

# Entraînement des SVM sur les observations bruitées
y_rbf = svr_rbf.fit(X, y).predict(X)
y_lin = svr_lin.fit(X, y).predict(X)
y_poly = svr_poly.fit(X, y).predict(X)

Afficher les résultats :

plt.scatter(X, y, color='darkorange', label='Données')
plt.plot(X, y_rbf, color='navy', lw=2, label='RBF')
plt.plot(X, y_lin, color='c', lw=2, label='Linéaire')
plt.plot(X, y_poly, color='cornflowerblue', lw=2, label='Polynomial')
plt.xlabel('X')
plt.ylabel('y')
plt.title('Support Vector Regression')
plt.legend()
plt.show()

Question :

Pourquoi employer une valeur aussi grande pour le parametre C (ici, C = 1000) ?

Correction :

La constante \(C > 0\) permet de choisir le point d’équilibre entre l’aplatissement de la solution et l’acceptation d’erreurs au-delà de \(\epsilon\)-SVM pour la régression. Une valeur trop petite de C nous donne un estimateur trop lisse (sous apprentissage). Pour une valeur trop grande, la fonction estimée prend trop en compte le bruit (sur-apprentissage).

Diabetes dataset

sklearn contient plusieurs jeux de données réels d’exemple. Concentrons-nous sur le jeu de données Diabetes consistant à prévoir la progression de la maladie (représentée par un indice quantitatif) à partir de différentes variables : âge, sexe, pression artérielle, IMC et six valeurs de prélévements sanguins.

from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split

diabetes = load_diabetes()
X_train, X_test, y_train, y_test = train_test_split(diabetes.data, diabetes.target, test_size=0.30, random_state=0)

Question

Chargez la base de données Diabetes du module sklearn.datasets et faites une partition aléatoire en partie apprentissage et partie test (70% apprentissage, 30% test). Construisez un modèle de SVM de régression sur cette base et calculez l’erreur quadratique moyenne sur l’ensemble de test. Utilisez GridSearchCV pour déterminer le meilleur noyau à utiliser.

Correction

Par exemple (il est possible de complexifier la grille) :

from sklearn.pipeline import Pipeline
from sklearn.model_selection import GridSearchCV

svc = svm.SVR(kernel='rbf', gamma='scale')

# Syntaxe : nomdustep__nomduparamètre
param_grid = {
    'C': [0.1, 1.0, 10, 100],
}

search = GridSearchCV(svc, param_grid, n_jobs=4, verbose=1, scoring='neg_mean_squared_error')
search.fit(X_train, y_train)
print(search.best_params_)
print(search.score(X_test, y_test))

scoring='neg_mean_squared_error' permet de spécifier que l’on veut utiliser l’erreur quadratique moyenne comme métrique. Sinon, par défaut, scikit-learn utilise le score R2 pour les modèles de régression (y compris la SVR). Ici, l’énoncé demande explicitement l’erreur quadratique moyenne. Toutefois, il faut garder en tête que cette erreur dépend de l’amplitude des données et qu’elle est en général plus difficile à interpréter que le score R2…

Approfondissement : LibSVM (optionnel)

Note

Cette partie est facultative. Elle vous permet de manipuler directement les bibiothèques LibLinear et LibSVM sur lesquelles s’appuie scikit-learn pour les machines à vecteur de supports. Ces implémentations sont très rapides et sont écrites en langage C.

Il est nécessaire d’avoir un compilateur C fonctionnel pour cette partie.

One Class SVM

LibSVM est une implémentation sous licence libre qui s’est imposée ces dernières années et qui est utilisée par de nombreux logiciels comme « moteur de classification » (par exemple scikit-learn). Les deux paramètres qui permettent une meilleure adaptation aux données d’apprentissage sont le paramètre nu de régularisation et le paramètre de l’échelle du noyau (gamma). Pour obtenir et compiler libSVM suivre ces pas :

cd ~
rm -rf tpalgos
mkdir tpalgos
cd tpalgos
wget http://cedric.cnam.fr/~ferecatu/RCP209/libsvm-3.32.tar.gz
tar xzvf libsvm-3.32.tar.gz
cd libsvm-3.32/
make

Pour comprendre les différents algorithmes, noyaux disponibles dans cette bibliothèque et leurs paramètres lisez le document README dans le répertoire libsvm-3.32/.

Dans une première étape nous évaluons les performances de OCSVM sur la base de données MNIST en utilisant un noyau gaussien. Nous examinons seulement 1 classe : le chiffre 5.

# Récupérer la base de données
cd ~
cd tpalgos
mkdir databases
cd databases
# Rendre les binaires visibles dans le repertoire courant
ln -s ../libsvm-3.32/svm-train .
ln -s ../libsvm-3.32/svm-predict .
ln -s ../libsvm-3.32/svm-scale .
ln -s ../libsvm-3.32/README .
wget wget http://cedric.cnam.fr/~ferecatu/RCP209/mnist.bz2
wget wget http://cedric.cnam.fr/~ferecatu/RCP209/mnist.t.bz2
bzip2 -d mnist.bz2
bzip2 -d mnist.t.bz2

OCSVM utilise les étiquettes de +1 pour les éléments de la classe (inliers) et -1 pour les outliers (hors classe). Nousemployons sed pour préparer les données avec les bonnes étiquettes (+1) :

cat mnist | grep '^5' | shuf -n 2000 | sed -r s/^5/1/g > 5
cat mnist.t | grep '^5' | shuf -n 1000 | sed -r s/^5/1/g > 5.t
# Nombre échantillons apprentissage et test classe 5
wc -l 5
>>> 2000
wc -l 5.t
>>> 892

Entrainer un modèle OC-SVM à noyau gaussien et paramètres par défaut :

./svm-train -s 2 5 5.model_default
./svm-predict 5.t 5.model_default 5.output_default
>>> Accuracy = 0% (0/892) (classification)

Nous pouvons remarqueer que les paramètres par défaut ne sont pas très adéquats. Les valeurs des données représentent les intensités des pixels dans une image en niveaux de gris (entre 0 et 255). La valeur par défaut pour le paramètre gamma (regardez le fichier 5.model_default) est 0.00133511 (1/num_features), ce qui n’est pas très adapté. Nous essayons avec une valeur plus raisonnable :

./svm-train -s 2 -g 0.0000001 5 5.model_default
./svm-predict 5.t 5.model_default 5.output_default
>> Accuracy = 47.1973% (421/892) (classification)

Ceci est plus proche du résultat attendu, car le paramètre nu par défaut a une valeur de 0.5 (50% de outliers). Une autre approche est de mettre les données à l’échelle entre 0 et 1 sur tous les attributs :

./svm-scale -l 0 5 > 5.scaled
./svm-scale -l 0 5.t > 5.t.scaled
./svm-train -s 2 5.scaled 5.model_scaled
./svm-predict 5.t.scaled 5.model_scaled 5.output_scaled
>> Accuracy = 47.7578% (426/892) (classification)

Question :

Changez le paramètre nu à 0.1. Quelle est l’erreur de classement ? Expliquez.

Correction :

svm-predict affiche Accuracy = 90.9193%, ce qui est consistant avec l’interprétation de nu (pourcentage de outliers).

Question :

Testez differents noyaux sur le même probleme.

SVM-toy

Dans la suite nous employons l’outil svm-toy qui permet de visualiser le classement pour des problèmes en deux dimensions.

cd ~/tpsvm/libsvm-3.32/svm-toy/gtk
make
./svm-toy

Travail à faire :

Pour un ensemble de données bidimensionnelles dans un carré utilisez le noyau gaussien et essayez plusieurs valeurs pour les parametres nu (regularisation) et gamma (échelle du noyau : plus gamma est faible, plus le noyau est « large »). Essayez de vous former une intuition sur la connexion entre l’espacement entre les points d’apprentissage (leur densité locale), les bonnes valeurs pour les parametrès et la probabilité pour que les points soient classés comme des outliers. Experimentez avec d’autres formes de classes, qui contiennent eventuellement des détails visibles à plusieurs échelles.

SVM-toy pour la régerssion

Lancez l’utilitaire svm-toy avec un paramètre -s 4 (nu-SVR) et placez des points sur la surface en suivant le contour d’une sinusoïde. Ajouter quelques points de « bruit » un peu plus éloignés. Testez plusieurs valeurs pour le paramètre C. Pour quelle valeur la prédiction SVR semble ignorer le bruit ?