Insertion de proximal SVM dans des arbres aléatoires, mode d`emploi
Contents
1. est prise regardant les s quences de partitions de classes rencontr es le long de la structure binaire La d fini tion des paires de classes superpos es dans chaque arbre fait donc partie du processus al atoire et aide ainsi r duire la variance des r sultats La p nalit de temps de calcul Arbres PSVM Donn es multi classes pSVM T pSVM p SVM p SVM p SVM p SVM p SVM p SVM feuille p SVM p SVM feuille p SVM feuille feuille p SVM feuille feuille p SVM feuille feuille p SVM feuille p SVM feuille feuille feuille feuille feuille feuille feuille feuille Fic 1 Structure g n rale du classifieur base d arbres PSVM provoqu e par l utilisation des SVM dans plusieurs arbres peut tre r duite en utili sant des classifieurs plus simples tel que les LS SVM Suykens amp Vandewalle 1999 least square support vector machine ou encore les PSVM Fung amp Mangasarian 2005 proximal support vector machine Tous deux peuvent tre interpr t s comme une solution aux moindres carr s r gularis e d un syst me d quation lin aire Tikho2. en une paire de classes superpos es qui sont ensuite analys es avec un classifieur SVM binaire Dans Cheong ef al 2004 Cheong propose une architecture d arbre binaire base de SVM afin d obtenir un bon compromis entre la rapidit computation nelle des arbres de d cision utilis s pour une s paration hi rarchique des classes et les bonnes performances de classification des SVM N anmoins ses principales conclu sions mettent en avant le fait que convertir un probl me multi classes en un arbre bi naire optimal soul ve une question d licate En effet les d finitions de paires de classes superpos es qui sont mises en uvre dans les premiers noeuds de l arbre affectent les options d agr gation ult rieures des classes Cela engendre une certaine difficult cr er une structure d arbre de d cision optimale du fait que cela n cessite une in vestigation exhaustive de toutes les options d agr gation possible chaque n ud de l arbre Pour r duire ce probl me Cheng et al ont r cemment propos une approche ascendante pour d terminer les partitions hi rarchiques de donn es multi classes en une s quence de SVM binaires Cheng ef al 2008 Leur approche fait l hypoth se que les premi res classes isoler dans une structure binaire sont celles qui ont la dis tance relative moyenne par rapport aux autres classes la plus grande Ainsi ils suivent une approche ascendante dans laquelle ils inspectent en pr
3. suivants Nous consid rons le probl me de classification de m x points dans un espace r el R n dimensions Les m points sont repr sent s par la http archive ics uci edu ml CAp 2009 matrice A de dimension m x n Chaque point A appartient la classe positive ou n gative tel que sp cifi par une matrice D diagonale m x m avec 1 ou 1 le long de sa diagonale Pour ce probl me un SVM traditionnel avec un noyau lin aire est donn par le programme quadratique suivant avec le param tre v gt O Vapnik 1995 1 pere Der SUR st D Aw ey y2ze 1 y20 G om triquement cette formulation calcule deux hyperplans x w y 1 qui s parent la plupart des chantillons positifs et n gatifs En minimisant la norme 2 du vecteur d erreur y au lieu de la norme 1 et en rempla ant la contrainte d in galit par une galit Fung et Mangasarian Fung amp Mangasarian 2001 changent les SVM traditionnels en formulant le probl me d optimisation libre suivant A netgi 1 2 o iang D Aw en e P 5 ww D Cette nouvelle formulation peut tre vue comme une solution aux moindres carr s r gularis e du syst me d quations lin aires D Aw ey e Ainsi du point de vue math matique cette formule remplace la r solution d un programme lin aire ou quadratique par la r solution d un syst me non singulier d quations lin aires ce qui fut une id e initialement
4. Insertion de proximal SVM dans des arbres al atoires mode d emploi C dric Simon J r me Meessen Christophe De Vleeschouwer 1 Laboratoire de T l communication et T l d tection UCL 2 Place du Levant 1348 Louvain la Neuve Belgique cedric simon uclouvain be christophe devleeschouwer uclouvain be 2 Multitel Mons Belgique jerome meessen multitel be R sum En ins rant plusieurs classifieurs SVM dans une architecture d arbre binaire il est possible de changer un probl me multi classes arbitraire en une hi rarchie de classifications binaires Un des probl mes essentiels consiste d terminer chaque n ud de l arbre la fa on de regrouper les classes multiples en une paire de classes superpos es discriminer Comme contribution principale cet article propose d utiliser un ensemble d arbres al atoires au lieu d un seul arbre de d cision optimis et ce de fa on r duire l impact du choix de la paire de classes superpos es sur les performances du classifieur Les r sultats empiriques obtenus sur diff rents ensembles de donn es UCI d montrent une am lioration des per formances de classification en comparaison aux solutions SVM et aux ensembles d arbres al atoires conventionnels Mots cl s SVM proximal SVM ensemble d arbres de d cision classification multi classes 1 Introduction Les algorithmes de S parateurs Vaste Marge SVM initialement propos s par Vap nik V
5. apnik 1995 sont devenus des m thodes incontournables pour l exploration de donn es appliqu s avec succ s la classification la s lection de caract ristiques le partitionnement de donn es ou encore l analyse de s ries temporelles Dans le contexte de la classification les SVM s adressent implicitement aux probl mes classes bi naires Plusieurs m thodes ont toutefois t propos es afin d tendre son utilisation aux donn es multi cat gories Crammer amp Singer 2001 Platt er al 2000 Hsu amp Lin 2002 mais sans am lioration significative par rapport la strat gie un contre un si ce n est un avantage de rapidit pour la m thode DAGSVM Dans Hsu amp Lin 2002 Hsu et Lin distinguent deux approches permettant de r aliser de la classification SVM CAp 2009 multi classes La premi re est de construire et puis de combiner plusieurs classificateurs binaires alors que la deuxi me consid re directement toutes les donn es dans une seule formulation La m thode que nous proposons ici se situe l intersection de ces deux approches R cemment il a t sugg r que les SVM peuvent b n ficier de l architecture des arbres de d cision pour r aliser des classifications cat gories multiples de fa on plus naturelle Cheong et al 2004 Cheng et al 2008 L id e principale consiste par titionner chaque n ud d un arbre de d cision l ensemble de classes fournies en en tr e
6. d v lopp e par Suykens et al Suykens amp Vandewalle 1999 G om triquement dans cette formulation alternative les hyperplans x w y 1 peuvent tre consid r s comme des hyperplans proximaux pouss s aussi loin que possible l un de l autre et autour desquels les points de chaque classe sont rassembl s Les proximal SVM PSVM ont des performances comparables aux classifieurs SVM mais avec une vitesse de calcul souvent bien plus rapide Or cette rapidit est indispensable dans notre algorithme bas sur un ensemble d arbre o dans certains cas quelques milliers de PSVM sont calcul s Notons que l extension de PSVM lin aires a des PSVM non lin aires est test e dans Fung amp Mangasarian 2001 mais n est pas prise en consid ration dans ce travail Fung et Mangasarian propose aussi dans Fung amp Mangasarian 2005 un PSVM multi cat gories qui peut tre vu comme une stat gie un contre tous Leurs r sultats sont compar s aux n tres dans la section exp rimen tale 2 2 Insertion des PSVM dans une structure d arbre De fa on pouvoir utiliser les PSVM chaque n ud des arbres la classe de chaque chantillon de donn es doit tre convertie en une valeur binaire correspondant une des deux classes superpos es choisies par le noeud Ainsi si les labels des classes a l entr e d un n ud sont 1 2 et 3 la classe 1 peut par exemple tre consid r e comme la premi re cat gori
7. du classifieur Algorithme 1 Entra nement d un n ud N Split_a_node S Entr e un ensemble d entrafnement de m chantillons S s1 sm avec n attributs N classes Sortie un n ud lab lis par les param tres PSVM w et y et la branche de sortie de chaque chantillon d entrainement 1 S1 S2 Split_in_2_categories S 2 m1 amp m2 nombre d chantillons d entrainement dans chaque cat gorie 3 a1 an Select_attributes n 4 ifm amp mz gt m then 5 w y J PSVM S1 S2 a1 an 6 i 1 7 while i lt m do 8 ifw si y lt 0 then 9 si va dans le n ud de droite 10 else 11 si va dans le n ud de gauche 12 end if 13 i i l 14 end while 15 else 16 N est une feuille 17 end if Split_in_2_categories S Entr e un ensemble d chantillons S avec Ne classes Sortie deux ensembles d chantillons S et S2 avec 2 classes 1 x1 N Nombre d chantillons d entrainement dans chaque classe 2 S1 S2 3 while taille S1 lt m 2 do Choisir al atoirement une classe parmi les N ajouter S1 sans replacement 5 end while Select_attributes n Entr e le nombre d attributs n Sortie un ensemble d indices li s aux attributs a1 a N 1 Choisir al atoirement un nombre Na entre N amp Na 2 Choisir N indices d attributs al atoirement PSVM S So a1 eng ANa D Entr e les chantillons d entrai
8. e de classes superpos es alors que la combinaison des classes 2 et 3 Arbres PSVM d finit alors la deuxi me cat gorie de classes superpos es Le choix de ce partitionne ment en deux cat gories est r alis de fa on al atoire La seule contrainte impos e au partitionnement est d viter dans la mesure du possible d avoir des cat gories de tailles fortement in gales ce qui peut entra ner une r duction significative des performances du PSVM Fung amp Mangasarian 2005 En pratique les classes d entr e sont s lec tionn es al atoirement et progressivement pour former la premi re cat gorie de classes superpos es jusqu ce qu au moins la moiti des chantillons ait t assign e cette cat gorie Le label de la seconde cat gorie est ensuite donn toutes les autres classes Evidemment d autres crit res peuvent tre envisag s pour construire ces deux cat go ries mais nos r sultats ont montr que cette approche g n rique et peu contraignante donne de bonnes performances au sein d arbres al atoires Pour le reste notre syst me utilise une proc dure classique descendante pour construire des arbres de d cision non lagu s partir des donn es d entra nement Chaque n ud peut tre vu comme un classifieur faible qui organise les chantillons d entr e en deux branches de mani re fournir un gain d information significatif c est dire r duisant l impuret de la variab
9. emier lieu comment s parer les classes les plus similaires tel que mesur e par une m trique heuristique Bien que possiblement efficace il est utile de mentionner qu un tel proc d heuristique pour gui der la conception d un arbre optimal ne diminue en rien les inconv nients d un arbre de d cision unique En particulier ces arbres sont connus pour offrir des propri t s de g n ralisations relativement pauvre De fa on viter ces d savantages nous proposons de construire un ensemble d arbres al atoires au lieu d un seul arbre de d cision optimis L efficacit d un ensemble d arbre de d cision a t d montr e r cemment dans plusieurs articles Breiman 2001 Geurts et al 2006 ainsi que leur consistance statistique Biau et al 2008 Dans notre cas cette approche a l avantage 1 d assouplir et de contourner virtuellement la ques tion associ e la d finition d une paire de classes superpos es optimale chaque n ud des arbres de d cision et 2 d augmenter la robustesse et la capacit de g n ralisation de l ensemble de classifieurs r sultant Officiellement chaque arbre individuel examine chacun de ses n uds une partition pseudo al atoire des classes d entr e en deux super classes appel es classes super pos es En rendant al atoire le processus de construction de l arbre et en combinant le r sultat de chacun des arbres construits aucune d cision stricte n
10. ines N anmoins sur les donn es identiques a celles utilis es dans ce travail Fung et Mangasarian annonce une diff rence de vi tesse sup rieur un ordre de magnitude entre un SVM lin aire et un PS VM lin aire en utilisant dans les deux cas une strat gie un contre tous 3http www kernel machines org CAp 2009 4 Conclusion et travaux futurs Nous avons propos dans cet article d ins rer des PSVM chaque n ud d un en semble d arbres al atoires de fa on r soudre des probl mes de classification de don n es de grande dimension et multi classes Les r sultats pr liminaires obtenus montrent que cette m thode permet d obtenir sur les donn es analys es de meilleurs r sultats par rapport aux m thodes bas es sur des SVM lin aires ou celles utilisant des ensembles d arbres al atoires Ce b n fice vient de 1 la capacit prendre plusieurs attributs en compte chaque n ud des arbres et 2 la capacit convertir un probl me multi classe en une hi rarchie de classifications binaires sans avoir prendre de d cisions strictes sur la fa on de partitionner les classes multiples en un ensemble binaire Des travaux futurs pourraient effectuer une comparaison plus exhaustive avec plus de don n es de plus grandes dimensions et diff rents types de classifieurs Ils pourraient aussi examiner le b n fice obtenu en utilisant des noyaux non lin aires dans les PSVM ou encore analyser c
11. le de sortie Breiman ef al 1984 Dans notre cas cette partition s effectue sur base d un classifieur PSVM Une fois que l arbre entier a t construit un chantillon classifier tombe simplement de la racine une des feuilles de l arbre et re oit le label de la classe dominante parmi les chantillons d entrainement qui ont atteint cette m me feuille durant la phase d apprentissage 2 3 Ensemble d arbres et processus al atoires De mani re similaire de nombreux travaux pr c dents Breiman 2001 Geurts et al 2006 Ho 1998 une m thode utilisant de l al atoire est examin e afin d am liorer les performances d un arbre de d cision Ces m thodes proposent de rendre al atoire ou semi al atoire la construction des arbres et de cr er ainsi un ensemble d arbres diver sifi s dont les pr dictions sont alors combin es par un simple vote majoritaire Le but principal d un ensemble al atoire d arbres de d cision est de r soudre l erreur d ap proximation et l erreur d estimation en m me temps Dans notre structure l utilisa tion d al atoire permet non seulement de construire des arbres diversifi s mais a aussi l avantage de diminuer l impact d une d cision non optimale chaque n ud des arbres en r partissant les classes d entr e en deux cat gories de classes superpos es En pratique la m thode propos e dans ce travail est proche de celle des sous espaces al atoi
12. nces des PSVM multi classes lin aires MPSVM lin aires sont tir es d un article de Fung and Mangasarian Fung amp Man gasarian 2005 alors que les performances d arbres extr mement al atoires c a d les Extra trees ET sont reprises d un article de Geurts Geurts et al 2006 Nous mon trons galement les r sultats obtenus par un SVM lin aire un contre un UCU SVM disponible dans la OSU SVM Classifier Matlab Toolbox Le nombre d arbres est fix 100 pour les arbres PSVM ainsi que pour les Extra trees La table 3 r sume les r sultats obtenus m tant le nombre d chantillons de donn es et n le nombre d attributs La comparaison des arbres PSVM avec les autres m thodes montre une am lioration non n gligeable des performances sur les ensembles de donn es o les m thodes reposant sur des SVM surpassent les m thodes base d arbres c a d les donn es Vehicle et Isolet Pour les autres ensembles de donn es nos performances sont comparables aux performances des Extra trees Grace 4 la ra pidit de PSVM le temps d entrainement de notre m thode est la plupart du temps similaire aux ensembles d arbres al atoire dont la rapidit est d montr e dans Geurts et al 2006 Nous n avons d lib r ment pas ajout dans les r sultats obtenus les temps de calcul mis par les diff rentes m thodes car celles ci ont t impl ment es dans dif f rents languages et sur diff rentes mach
13. nement d partag s en deux cat gories avec les attributs choisis Sortie les param tres PSVM w amp y A 3 R sultats pr liminaires Afin d analyser les performances des arbres PSVM nous avons utilis des donn es provenant de la UCI Machine Learning Repository Ces donn es contiennent 4 617 http archive ics uci edu ml Arbres PSVM TAB 1 Performance l entra nement et au test avec une 10 fold cross validation pour le MPSVM lin aire le SVM lin aire un contre un les Extra Trees et nos arbres a PSVM lin aire Dataset MPSVM lin aire UCU SVM lin aire ET arbres PSVM mxn Entrainement Entrainement Entrainement Entrainement nb classes Test Test Test Test Vowel 65 7 87 9 00 99 88 528 x 10 11 cl 59 3 81 12 98 26 97 5 Vehicle 79 3 83 8 100 100 846 x 18 4 cl 77 2 79 7 74 84 02 Segment 91 2 96 9 00 99 95 2310 x 19 7 cl 91 0 93 37 98 23 98 23 Isolet 95 1 97 87 00 100 7797 x 617 26 cl 93 8 95 9 92 39 96 64 Spambase 94 65 95 45 100 98 93 4601 x 57 2 cl 92 2 92 89 95 83 95 96 attributs et de 2 4 26 classes couvrant ainsi de larges conditions Nous comparons 4 la table 3 les pourcentages de classification correcte de la m thode propos e avec les r sultats obtenus en utilisant un ensemble d arbres al atoires et une m thode bas e sur des PSVM Les performa
14. nov amp Arsenin 1977 et sont des m thodes extr mement rapides et efficaces Ce travail propose donc l utilisation des PSVM ce qui permet d obtenir un bon compromis entre performance de classification et rapidit de calcul Du point de vue de la m thode d arbre de d cision l utilisation de PSVM chaque n ud permet de trouver une fronti re quasi optimale en utilisant des attributs multiples chaque n ud Or des travaux r cents Lee amp Olafsson 2006 ont montr que des arbres de d cision utilisant plusieurs attributs chaque n ud pouvaient am liorer la performance des arbres de d cision classiques Les r sultats fournis dans la section exp rimentale viennent renforcer cette affirmation Le reste de cet article est organis de la fa on suivante La section 2 pr sente notre m thode Dans la section 3 les r sultats exp rimentaux sont report s pour cinq en sembles de donn es multi classes provenant de la UCI Machine Learning repository Finalement la section 4 tire les conclusions et ouvre des perspectives ce travail 2 Arbres PSVM La figure 1 montre la structure g n rale du classifieur propos Nous expliquons ci dessous la th orie et les sp cificit s du PSVM ainsi que celles des arbres al atoires et la fa on dont ils peuvent tre combin s ensemble 2 1 PSVM lin aire Les l ments cl s de la th orie des PSVM tel que d taill dans Fung amp Mangasarian 2001 2005 sont les
15. omment choisir un meilleur compromis entre le degr d al atoire et une s lection optimale d attributs et ou de classes superpos es chaque noeud R f rences BIAU G DEVROYE L amp LUGOSI G 2008 Consistency of random forests and other averaging classifiers J Mach Learn Res 9 2015 2033 BREIMAN L 2001 Random forests Machine Learning 45 1 5 32 BREIMAN L FRIEDMAN J OLSEN R amp STONE C 1984 Classification and Re gression Trees CRC Press ISBN 0412048418 CHENG L ZHANG J YANG J amp MA J 2008 An improved hierarchical multi class support vector machine with binary tree architecture In International Conference on Internet Computing in Science and Engineering ICICSE 08 p 106 109 Harbin China CHEONG S OH S amp LEE S Y 2004 Support vector machines with binary tree architecture for multi class classification Neural Information Processing Letters and Reviews 2 3 47 51 CRAMMER K amp SINGER Y 2001 On the algorithmic implementation of multi class kernel based vector machines Journal of Machine Learning Research 2 265 292 FUNG G amp MANGASARIAN O 2001 Proximal support vector machine classifiers In International Conference on Knowledge Discovery and Data Mining p 64 70 San Francisco CA USA FUNG G amp MANGASARIAN O 2005 Multicategory proximal support vector ma chine classifiers Machine Learning 59 1 2 pp 77 97 21 GEURTS P ERNST D am
16. p WEHENKEL L 2006 Extremely randomized trees Ma chine Learning 63 1 3 42 HOT K 1998 The random subspace method for constructing decision forests IEEE Transactions on Pattern Analysis and Machine Intelligence 20 8 832 844 Hsu C W amp LIN C J 2002 A comparison of methods for multi class support vector machines EEE Transactions on Neural Networks 13 2 415 425 Arbres PSVM LEE J Y amp OLAFSSON S 2006 Multi attribute decision trees and decision rules in Data Mining and Knowledge Discovery Approaches Based on Rule Induction Tech niques p 327 358 PLATT J CRISTIANINI N amp SHAWE TAYLOR J 2000 Large margin dags for multiclass classification Advances in Neural Information Processing Systems 12 547 553 SUYKENS J A K amp VANDEWALLE J 1999 Least squares support vector machine classifiers Neural Processing Letters 9 3 293 300 TIKHONOV A amp ARSENIN V 1977 Solutions of Ill Posed Problems New York John Wiley amp Sons VAPNIK V N 1995 The nature of statistical learning theory In Springer New York USA
17. res propos e par Ho dans Ho 1998 Celle ci propose de choisir al atoirement un sous ensemble de N attributs parmi les n attributs possibles pour calculer un test chaque n ud de l arbre Cette m thode recherche alors le meilleur test possible pour chacun de ces attributs pris individuellement c d qu il compare la valeur d un attribut par rapport un seuil le caract re al atoire tant alors inversement proportionnel au param tre Na Similairement durant notre processus d apprentissage Na attributs sont s lectionn s au hasard chaque noeud parmi les n possibles Ces attributs sont n an moins utilis s tous ensemble par un PSVM afin de calculer les hyperplans Ici aussi le degr d al atoire est proportionnel au param tre Na Le processus d entrainement de chaque n ud d un arbre est r sum e dans l algo rithme 1 Dans celui ci m d finit le nombre minimum d chantillons d entra ne CAp 2009 ment que doit avoir chacune des classes superpos es pour continuer la s paration d un n ud la taille de l ensemble d entra nement dans un noeud tant de m chantillons Pour nos exp riences m est fix 5 NM et N repr sentent les nombres d attributs minimum et maximum utiliser dans chaque PSV M et N est alors une variable al atoire pouvant varier entre N et N77 mr NU et N sont tous trois des param tres influen ant la complexit et la rapidit
Download Pdf Manuals
Related Search