Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

´ Ecole Sup´ erieure des communications de Tunis Rapport d’atelier d’optimisati

´ Ecole Sup´ erieure des communications de Tunis Rapport d’atelier d’optimisation M´ ethode SVM lin´ eaire de classiﬁcation Elyes Ben Cheikh Table des mati` eres 1 Bibliographie de la m´ ethode 3 1.1 Qu’est ce qu’un SVM ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Principe G´ en´ eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 La Programmation de la m´ ethode 6 2.1 Probl´ ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Algorithme SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Les r´ esultats de la programmation 11 3.1 R´ esultat de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Veriﬁcation avec une base de donn´ ee . . . . . . . . . . . . . . . . . . . . . . . . . 12 Bibliographie 13 Table des ﬁgures 1.1 Aper¸ cu du r´ esultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Application de la fonction φ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Etapes du Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Tableau de classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Matrice des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Partition des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Rang de la matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Partition des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.1 Sch´ ema des droites de s´ eparations des diﬀ´ erentes r´ egions . . . . . . . . . . . . . . . . 11 3.2 Tableau correspondant aux points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 R´ esultats avec plus de points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Chapitre 1 Bibliographie de la m´ ethode 1.1 Qu’est ce qu’un SVM ? Les machines ` a vecteurs de support ou s´ eparateurs ` a vaste marge (en anglais support vector machine, SVM) sont un ensemble de techniques d’apprentissage supervis´ e destin´ ees ` a r´ esoudre des probl` emes de discriminationnote 1 et de r´ egression. Les SVM sont une g´ en´ eralisation des classiﬁeurs lin´ eaires. C’est un algotithme supervis´ e qui nous permet de faire des pr´ edictions sur des variables qualita- tives ou quantitatives.[1] 1.2 Historique L’id´ ee des hyperplans ` a marge maximale a ´ et´ e explor´ ee d` es 1963 par Vladimir Vapnik et A. Lerner, et en 1973 par Richard Duda et Peter Hart dans leur livre Pattern Classiﬁcation. Les fondations th´ eoriques des SVM ont ´ et´ e explor´ ees par Vapnik et ses coll` egues dans les ann´ ees 70 avec le d´ eveloppement de la th´ eorie de Vapnik-Chervonenkis, et par Valiant et la th´ eorie de l’apprentissage PAC. L’id´ ee des fonctions noyaux n’est pas non plus nouvelle : le th´ eor` eme de Mercer date de 1909, et l’utilit´ e des fonctions noyaux dans le contexte de l’apprentissage artiﬁciel a ´ et´ e montr´ e d` es 1964 par Aizermann, Bravermann et Rozoener. Ce n’est toutefois qu’en 1992 que ces id´ ees seront bien comprises et rassembl´ ees par Boser, Guyon et Vapnik dans un article, qui est l’article fondateur des s´ eparateurs ` a vaste marge. L’id´ ee des variables ressorts, qui permet de r´ esoudre certaines limitations pratiques importantes, ne sera introduite qu’en 1995. ` A partir de cette date, qui correspond ` a la publication du livre de Vapnik, les SVM gagnent en popularit´ e et sont utilis´ es dans de nombreuses applications. Un brevet am´ ericain sur les SVM est d´ epos´ e en 1997 par les inventeurs originels.[2] Chapitre 1. Bibliographie de la m´ ethode 4 1.3 Principe G´ en´ eral Le principe est simple : ils ont pour but de s´ eparer les donn´ ees en classes ` a l’aide d’une fronti` ere aussi « simple » que possible, de telle fa¸ con que la distance entre les diﬀ´ erents groupes de donn´ ees et la fronti` ere qui les s´ epare soit maximale. Cette distance est aussi appel´ ee « marge » et les SVMs sont ainsi qualiﬁ´ es de « s´ eparateurs ` a vaste marge », les « vecteurs de support » ´ etant les donn´ ees les plus proches de la fronti` ere. Comme le montre la ﬁgure ci-dessous, dans cet espace ` a deux dimensions, la « fronti` ere » est la droite noire, les « vecteurs de support » sont les points entour´ es (les plus proche de la fronti` ere) et la « marge » est la distance entre la fronti` ere et les droites bleue et rouge. Fig. 1.1 – Aper¸ cu du r´ esultat Cette notion de fronti` ere suppose que les donn´ ees soient lin´ eairement s´ eparables, ce qui est rarement le cas. Pour y pallier, les SVMs reposent souvent sur l’utilisation de « noyaux ». Ces fonctions math´ ematiques permettent de s´ eparer les donn´ ees en les projetant dans un feature space (un espace vectoriel de plus grande dimension, voir ﬁgure ci-dessous). La technique de maximisation de marge permet, quant ` a elle, de garantir une meilleure robustesse face au bruit – et donc un mod` ele plus g´ en´ eralisable.[3] Fig. 1.2 – Application de la fonction φ Chapitre 1. Bibliographie de la m´ ethode 5 Cet algotithme a besoin ` a la fois de donn´ ees d’entr´ ees et ` a la fois des donn´ ees cibles lors de l’entrainement pour pouvoir par la suite pouvoir pr´ edire une donn´ ee cible en ayant seulement les donn´ ees d’entrainement. Dans l’exemple pr´ esent´ e ci-dessous, on a plusieurs types d’arbres. La taille des branches et du tronc sont des donn´ ees d’entr´ ees.Une fois le svm entrain´ e, il poura pr´ edire le type d’arbre en entr´ ee.[1] Fig. 1.3 – Etapes du Support Vector Machine Chapitre 2 La Programmation de la m´ ethode 2.1 Probl´ ematique Soit une population d’individus d´ ecrits par un nombre n de param` etres. L’objectif de la clas- siﬁcation est de regrouper les individus selon des crit` eres d´ eﬁnis sur ces param` etres. Ceci revient ` a d´ eﬁnir des fronti` eres qui s´ eparent entre les classes d’individus. Un exemple important est celui de la classiﬁcation uploads/Industriel/ rapport-atelier-optimisation1.pdf