Support Vector Machine

Objectif du chapitre

L’algorithme SVM fut introduit par Vapnik en 1995 et il est basé sur la théorie de Vapnik-Chervonenkis. Théoriquement, les SVM sont une généralisation des modèles de classification linéaires. Les SVM ont été appliqués avec beaucoup de succès dans divers domaines et spécialement dans le domaine de la reconnaissance de formes à partir d’images et le domaine de la bio-informatique.

Dans la littérature francophone, l’algorithme SVM est le plus souvent nommé algorithme séparateur à vaste marge. En effet, les algorithmes SVM se distinguent de la plupart des autres classifieurs linéaires par la maximisation de la marge qui sépare deux classes de données. Justement, ce chapitre tente d’expliquer les SVM d’un point de vue intuitif, mais aussi analytique, tout en mettant l’accent sur cet aspect de maximisation de la marge séparatrice.

À la fin de ce chapitre, le lecteur aura abordé :

Le SVM du point de vue géométrique

Les SVM sont des algorithmes supervisés qui au début ont été développés pour résoudre des problèmes de classification binaire. Ils ont été généralisés pour prédire des variables quantitatives.

Dans le cas de la classification binaire, les SVM recherchent un hyperplan discriminant de marge optimale entre deux classes. Pour comprendre l’idée apportée par cet algorithme, cette section donne une explication intuitive en se basant sur des exemples.

Dans la figure 9-1 ci-dessous, deux ensembles, des carrés et des cercles, sont représentés sur quatre repères en deux dimensions.

Figure 9-1 : exemple de séparateurs des carrés et des cercles

Supposons que les carrés et les cercles vides forment la base d’apprentissage et que les carrés et les cercles noirs (pleins) sont les données futures.

Sans prendre en compte les données futures (les carrés et les cercles pleins), le modèle représenté par la droite dans chacun des repères sépare toutes les données d’apprentissage de façon correcte. Cependant, des différences existent entre ces quatre modèles. En effet, bien qu’ils soient égaux vis-à-vis des données d’apprentissage, ils n’ont pas le même...

Le SVM du point de vue analytique

L’objectif de l’algorithme SVM est de trouver l’hyperplan qui sépare en deux classes avec la marge maximale les données de la base d’apprentissage. Cette section montre la démarche analytique pour atteindre cet objectif.

Supposons que les deux classes à séparer sont la classe des exemples positifs et la classe des exemples négatifs. Une fois que l’hyperplan séparateur est trouvé, pour déterminer la classe d’appartenance d’un point , le SVM utilise le vecteur normal à l’hyperplan et une constante comme suit :

Si alors est positif.

Si alors est négatif.

On remplace et on obtient :

, pour les futurs points positifs

, pour les futurs points négatifs

Avec les deux inéquations précédentes, déterminer la classe d’un point revient à étudier le signe de la quantité . S’il est positif, alors appartient à la classe des points positifs sinon, il appartient à la classe des points négatifs. En résumé, la classe d’un point est déterminée par :

L’équation (1) constitue donc la règle de décision que le SVM utilise pour la prédiction de la classe d’appartenance des futurs points. Cette règle est basée sur les deux inconnues et . L’objectif du reste de cette...

Données non linéairement séparables

Jusqu’à présent dans ce chapitre, le SVM tel qu’il a été présenté traite uniquement les données qui sont linéairement séparables. Ainsi, la figure 9-2 a montré que pour trouver la classe d’appartenance d’un nouveau point, le modèle SVM procède à la projection de ce point sur l’axe portant le vecteur normal de l’hyperplan qui sépare linéairement les données de la base d’entraînement.

Dans la plupart des problèmes posés dans la vraie vie, les données sont rarement linéairement séparables. Pour contourner ce problème, une solution existe et elle consiste en l’application d’une transformation sur les données.

L’idée de cette transformation, est de passer par un espace intermédiaire dans lequel les données sont linéairement séparables, et dans lequel le SVM peut être appliqué exactement comme l’ont montré les sections précédentes, puis restituer les résultats dans l’espace d’origine.

La figure 9-5 suivante montre un exemple très simple de données non linéairement séparables. En effet, aucune droite ne pourra séparer correctement les cercles d’un côté et les triangles de l’autre côté.

Figure 9-5 : exemple de données non linéairement séparables

Détecter les fraudes de cartes de crédit

Cet exemple concerne la réalisation d’une expérience Azure ML pour détecter les fraudes de cartes de crédit. Il s’agit d’entraîner un modèle sur un ensemble de données contenant des transactions saines et des transactions frauduleuses.

1. Les données des transactions de cartes de crédit

Un jeu de données issu du site kaggle.com sera utilisé. Il s’agit d’un Dataset du monde réel contenant 284 807 transactions par carte de crédit. Parmi ces transactions, 492 représentent des fraudes. Vous trouverez ce jeu de données dans le fichier creditcard.csv disponible en téléchargement sur le site : https://www.kaggle.com/eikedehling/exploring-class-imbalance-resampling-and-weights/data

Ce jeu de données est défini par 28 variables anonymes qui sont les résultats d’une ACP réalisée sur les données d’origines, plus trois autres variables Time, Amount et Class définies comme suit :

• Time : représente le temps en secondes passé depuis la première transaction du Dataset.

• Amount : indique la somme d’argent concernée par la transaction.

• Class : c’est la variable binaire à expliquer. Elle indique si la transaction est frauduleuse ou pas. Elle vaut 0 si la transaction est normale, sinon elle vaut 1 si la transaction est frauduleuse.

Il faut noter d’ores et déjà que la variable Class est très mal équilibrée, car le taux des transactions frauduleuses est très faible, il est égal à 0,172 %. Par conséquent, l’utilisation de l’indicateur AUC pour évaluer un quelconque modèle sur ce jeu de données ne sera pas appropriée. Dans ces cas-là, c’est l’utilisation de la courbe Précision/Recall qui sera recommandée.

Pour des raisons de confidentialité, les données à l’origine de l’ACP ne sont pas divulguées sur le site www.kaggle.com.

Ce jeu de données...

Détecter la présence d’une maladie

Dans ce deuxième exemple sur les SVM, un jeu de données contenant des informations médicales sur un ensemble de personnes est utilisé. L’expérience réalisée consiste à prédire la présence ou non d’une maladie cardiaque des coronaires à partir de certaines informations sur un patient. Deux SVM sont appliqués et comparés sur ce jeu de données. Un SVM classique et un SVM avec une fonction Kernel.