Home

Rapport de stage ISIMA 2ème Année - Soccer-lab

1. 14 Nouveau diagramme de classe UML de la partie solver 14 En t te de la classe Example sise 16 Diam tre d un cl ster svssen se estonien ne A QEA DA BE DBL RAE EEA te 19 Probl me de la somme des diam tres 20 Algorithme initial de la m thode calculDiam iiic niens 20 Nouvel algorithme de la m thode calculDiam caie nae 21 Algorithme initial de la m thode CreateFirstColumn ness 22 Algorithme temporaire de la m thode CreateFirstColumn icies iias 22 Algorithme final de la m thode CreateFirstColumn cici ici iciiiieiiieia ee 23 Comparaison de r sultats sise 24 Algorithme de la descente sise 25 Algorithme dela VINS dier loat rte ends T NN NA a 26 Algorithme de la m thode init siens 27 Probl me lin aire associ la m thode exacte 28 Ancien code de la m thode exacte ss 28 Nouveau code de la m thode exacte ss 29 Algorithme de la m thode hi rarchique 38 Algorithme de construction de la liste des NN 38 Exemple de dendogramme sise 39 Algorithme de la m thode run sise 40 Algorithme de la m thode DetermineNN iens 41 R sultat de la m thode hi rarchique 41 Rapport de stage 2009 Class
2. l or L to output results in LaTeX file Figure 6 Ligne de commande du main global 2 4 Gprof 2 4 1 Description Dans le but d optimiser le code du programme nous avons utilis le logiciel Gprof C est un logiciel libre faisant partie des utilitaires binaires GNU et qui 12 Rapport de stage 2009 Classification de donn es non supervis e 2 4 Gprof permet d effectuer du profilage de code c est dire de cr er une liste de toutes les m thodes appel es par une application et d indiquer le temps pass dans celles ci Cela permet ainsi de savoir quelles parties du code prennent le plus de temps et sont donc optimiser en priorit et quelles parties sont rapides et ne n cessitent donc pas de retouche Les fichiers de profilage g n r s sont pr sent s ainsi Flat profile Each sample counts as 0 01 seconds cumulative self self total time seconds seconds calls s call s call name 18 02 250 58 250 58 solveUright2 14 51 452 34 201 76 617220 0 00 0 00 SumDiameter calculDiam Dcolumn amp 10 63 600 20 147 86 test_x 10 49 746 08 145 88 139478351 0 00 0 00 SumDiameter entr Dcolumn amp int 9 72 881 20 135 12 CPXPselectSFullNorm 4 70 946 62 65 42 961438177 0 00 0 00 SymMatrix get unsigned long conste unsigned long const amp 2 06 975 28 28 66 CPXPrmatbld 1 84 1000 89 25 62 5256405473 0 00 0 00 DataSet getDissimilarity unsigned long unsigned long 1 62 1023 46 224 57 solveUright
3. Conclusion Le but du stage tait de tenter d optimiser les performances du programme existant et de continuer son d veloppement Pour ma part j ai plus pr cis ment sur les parties concernant le crit re de la somme des diam tres et du lien avec les logiciels de programmation lin aire Il m a de plus t demand de coder une m thode hi rarchique ind pendamment du projet Ces objectifs sont tous consid r s comme atteints L optimisation des performances qui s est traduite par des modifications parfois mineures dans le code a permis de faire gagner du temps l ex cution du programme La suite du d veloppement du crit re de la somme des diam tres bien qu apportant des r sultats mitig s a vu l adaptation de la m thode exacte pour Glpk L ajout de la possibilit d utiliser un logiciel de programmation lin aire gratuit ouvre des perspectives pour la mise disposition du programme et m a permis de d couvrir comment utiliser ces logiciels dans un programme Enfin j ai cr un programme permettant d utiliser une m thode hi rarchique de mani re totalement autonome Le fait de continuer un projet existant a pr sent une certaine difficult au d but car il nous a fallu bien assimiler tout le travail r alis par nos pr d cesseurs et reprendre leur code N anmoins travailler sur un projet de cette envergure m a permis de progresser au niveau de la vision globale d un projet ainsi que dans le langage C et en
4. Figure 11 Diam tre d un cluster La somme des diam tres est un crit re d homog n it qui consiste r partir n points en p clusters de telle sorte que la somme des diam tres des clusters formant la partition finale soit la plus petite possible avec videmment n gt p Le probl me math matique associ ce crit re peut donc se formuler de la mani re suivante avec Test l ensemble des clusters t possibles e VY vaut 1 sit est dans la partition solution O sinon e aj Vaut 1 si l objet i appartient au cluster t O sinon Rapport de stage 2009 19 3 La somme des diam tres Classification de donn es non supervis e min gt Diam C y P teT sous contraintes yaya 1 teT L y p r tET y e 0 1 3 Figure 12 Probl me de la somme des diam tres Les contraintes assurent que chaque point doit se trouver dans un seul cluster contrainte 1 que le nombre de cluster final est p contrainte 2 et enfin que les variables y sont binaires contrainte 3 La gestion de ce crit re a t impl ment e et ajout e au programme par les stagiaires de l an pass et mon travail consistait apporter d ventuelles am liorations Pour cela il a fallu dans un premier temps que je parcours la litt rature pour mieux connaitre ce crit re 3 1 Modifications du code existant 3 1 1 Optimisation de m thodes Comme nous l avons vu dans la partie 2 4 2 sur l utilisation du logici
5. ISIMA Institut Sup rieur d Informatique de Mod lisation et de leurs Applications GERAD Groupe d Etude et de Recherche en Analyse des D cisions Rapport de stage de deuxi me ann e d cole d ing nieur Fili re 2 g nie logiciel et syst me informatique Classification de donn es non supervis e Tome Auteur Etienne Duclos Dur e 5 mois Avril Septembre 2009 Responsables Entreprises Gilles Caporossi Pierre Hansen Sylvain Perron Responsable ISIMA Christophe Duhamel 2008 2009 ISIMA GERAD Institut Groupe d Sup rieur d Etude et de Informatique de Recherche en Mod lisation et de leurs Analyse des Applications D cisions Rapport de stage de deuxi me ann e d cole d ing nieur Fili re 2 g nie logiciel et syst me informatique Classification de donn es non supervis e Tome Auteur Responsables Entreprises Etienne Duclos Gilles Caporossi Pierre Hansen Sylvain Perron Responsable ISIMA Christophe Duhamel Dur e 5 mois Avril a Septembre 2009 2008 2009 Classification de donn es non supervis e Remerciements Remerciements Je tiens avant tout remercier toutes les personnes qui m ont permis d effectuer mon stage dans un environnement de travail agr able et dans d excellentes conditions Je tiens ainsi remercier tous les employ s du GERAD pour leur accueil au sein de leur laboratoire Je remercie aussi
6. tre la m thode de mise a jour de la matrice de dissimilarit s En effet il fallait mettre a jour les bonnes cases et avec les bonnes valeurs le tout suivant le crit re utilis lien simple ou lien double Car si au d part la fusion de deux points i et j ne pose pas de probleme particulier la fusion de deux clusters contenant chacun plusieurs points peut s av rer quand a elle plus d licate Il a donc fallu trouver comment faire en sorte que la fusion de deux clusters soit identique au moins dans la forme a la fusion de deux points Cela a t fait en utilisant un vecteur qui m a permis de marquer les entit s s lectionn es Ainsi lors de la fusion de deux points l un des deux est marqu comme tant fusionn et ne sera plus utilis Il ne sert donc a rien de mettre a jour ses dissimilarit s Et grace a cette m thode les clusters sont consid r s comme des points par la m thode de mise a jour et la fusion de deux clusters se fait facilement La s lection des NNs fusionner se fait selon l algorithme suivant les points im et jm tant ceux s lectionn s 40 Rapport de stage 2009 Classification de donn es non supervis e 5 2 Impl mentation dmin 100 000 pour chaque point i si le point n a pas d ja t fusionn avec un autre si dissnn i lt dmin dmin dissnn i im NN i jm fin si fin si fin pour retourner im et jm Figure 29 Algorithme de la m thode DetermineNN 5 3 R su
7. thode d lagage de l arbre ce qui permet de r duire le nombre de solutions et d acc l rer la vitesse de r solution du probl me Le parcours de l arbre et l lagage constituent la m thode de Branch And Bound ou de s paration et d valuation progressive en fran ais Cette m thode fonctionne de la mani re suivante on relaxe et on r sout le probl me initial pour obtenir la racine de l arbre Cette solution n est pas forc ment enti re et on ajoute donc des contraintes de branchement pour obtenir de nouveaux probl mes lin aires relax s Ces contraintes sont expliqu es plus en d tails dans le document 5 On r sout ensuite les probl mes cr s on applique de nouveaux les contraintes sur les solutions obtenues et ce jusqu obtenir un arbre dont toutes les feuilles sont des solutions enti res ou des solutions fractionnaires de moins bonne qualit que la meilleure solution enti re trouv e 1 2 3 M thode de r solution par g n ration de colonne Nous l avons vu le nombre de solutions possibles pour les probl mes de classification est exponentiel Ces solutions seront not es pour la suite comme tant les colonnes de la matrice A a avec n le nombre de points a classer Le terme colonne employ par la suite fait r f rence aux colonnes de A qui repr sentent les clusters La m thode de g n ration de colonne consiste ne consid rer non pas toutes les solutions possibles du probl me mais seulement
8. 1 34 1042 05 18 59 upddnorml 1 25 1059 46 17 41 solveUrightsv Figure 7 Exemple d un fichier de profilage g n r par Gprof 2 4 2 Utilisation Pour pouvoir utiliser Gprof il faut rajouter une option la compilation des fichiers Il a donc fallu modifier le makefile en cons quence et une option PROFILING pg a ainsi t ajout e L utilisation de Gprof se fait ensuite simplement il suffit de lancer l application dont on souhaite faire le profilage de la laisser se terminer normalement puis de lancer Gprof avec le fichier gnom out que l application a cr Cependant l application connait certains ralentissements dus l utilisation de Gprof le temps d ex cution pouvant parfois tre doubl Dans le cadre de mon stage j ai donc t amen utiliser Gprof pour optimiser le code du crit re de la somme des diam tres Apr s avoir effectu plusieurs profilages sur des probl mes diff rents il est apparu que les m thodes qui prenaient le plus de temps taient outre les m thodes de r solution du solver la m thode de calcul du diam tre et celle faisant la mise jour du diam tre d une colonne lors de l entr e d un point dans celle ci De plus la m thode getDissimilarity qui permet d aller chercher une valeur dans la matrice de dissimilarit s tait appel e un tr s grand nombre de fois L utilisation de Gprof m a ainsi permis de savoir sur quelles m thodes il tait le plus utile d apporter des modific
9. Programming Kit Les stagiaires de l an dernier ont donc commenc a impl menter en m me temps que pour Cplex les classes permettant au programme de se servir de Glpk Seulement cette id e a t abandonn e pour se concentrer sur Cplex qui est priori plus sur et plus performant Cette ann e cependant nous avons d cid de terminer cette partie En effet maintenant que le programme fonctionne correctement avec Cplex il semble int ressant de pouvoir comparer les performances des deux solvers et d tudier ainsi la possibilit de ne plus utiliser que Glpk a la place de Cplex Cette d cision a aussi t prise dans le but de mettre le programme en cours a disposition du grand public une fois termin L utilisation d un solver gratuit rendrait ainsi plus pratique celle du programme et ce pour plus de personnes Glpk est un ensemble de fonctions crites en C organis es sous forme d une librairie qui permettent de r soudre entre autre des probl mes lin aires en variables continues et des probl mes lin aire en nombres entiers Il est de part sa conception relativement simple utiliser en C et dans les langages en d rivant tel le C J ai donc commenc par lire le manuel d utilisation de Glpk pr sent sur le site internet du logiciel 7 et par chercher un document me permettant de faire le lien entre les fonctions de Cplex et celles de Glpk 8 Ceci m a t tr s utile car les classes pour Cplex existaien
10. bits Il y a donc logiquement eu quelques changements faire pour que le programme fonctionne de nouveau correctement Les principaux changements effectuer se sont situ s au niveau des librairies utilis es En effet les libraires standards du C ne sont pas les m mes en version 32 ou 64 bits Il a donc fallu changer les inclusions des fichiers d en t te pour ces librairies la De m me la librairie permettant d utiliser le logiciel de programmation lin aire Cplex avec du C fut elle aussi a changer De plus des modifications furent cette fois ci a faire dans le makefile 2 2 Utilisation de la classe accuracy L un des points important du programme est la pr cision des calculs En effet les erreurs d arrondis pr sentent d s lors que l on fait de la programmation num rique peuvent entrainer des erreurs importantes dans le programme tel par exemple le cyclage d une descente Pour rem dier a a les stagiaires de l an dernier ont impl ment une classe accuracy qui permet de g rer la pr cision de la plus grande majorit des calculs effectu s Cette classe permet de fixer la pr cision actuellement a 10e 6 pour tout ce qui touche a la comparaison entre deux doubles leur galit savoir lequel des deux est sup rieur a l autre ou savoir si un double est nul ou non la pr cision souhait e Elle porte sur des doubles car c est le type de tous les attributs importants du programme tel le co t d une colonne ou les dissi
11. chaleureusement Messieurs Gilles Caporossi Pierre Hansen et Sylvain Perron mes ma tres de stage pour leur accueil leur disponibilit ainsi que leurs conseils et leur encadrement tout au long du stage Je tiens galement remercier Monsieur Christophe Duhamel mon r f rent ISIMA pour m avoir donner l opportunit de faire ce stage Je tiens enfin remercier Mme Mouzat pour ses cours de communication qui m ont aid faire ce rapport et pr parer ma soutenance Rapport de stage 2009 Classification de donn es non supervis e Table des figures Table des figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Figure 9 Figure 10 Figure 11 Figure 12 Figure 13 Figure 14 Figure 15 Figure 16 Figure 17 Figure 18 Figure 19 Figure 20 Figure 21 Figure 22 Figure 23 Figure 24 Figure 25 Figure 26 Figure 27 Figure 28 Figure 29 Figure 30 Probl me d d part anne 32 P S sde nee dense een ner de nn nee 5 probleme relax issrss ist tene il AAE intention en AEA agir tags d 6 R solution du probl me lin aire sise 7 Probl me auxiliaire ssiiiisssiieieeereenereeeeereereneeeeeeneeeenenee 7 Diagramme de classe UML de l application 9 Ligne de commande du main global 12 Exemple d un fichier de profilage g n r par Gprof ss 13 Ancien diagramme de classe UML de la partie solver
12. les colonnes possibles pour un point La possibilit de pouvoir faire ce changement de type de contraintes a amen e a modifier quelque peu les classes G pkSolver et GlpkSolverStabilized tandis que Rapport de stage 2009 23 3 1 Modifications du code existant Classification de donn es non su pervis e les classes CplexSolver et CplexSolverStabilized taient quand elles pr vues pour cet ventuel changement Une fois ce changement effectu j ai lanc des tests pour voir si on avait effectivement un gain de temps ou non Ces tests ont t effectu s sur un fichier de 59 points Les temps sont exprim s en secondes et ceux affich s sont la moyenne des temps de dix tests Le terme contraintes de type E signifie que le programme a t ex cut avec la contrainte suivante D ayel tE TF et le terme contraintes de type G signifie que le programme a t ex cut avec la contrainte suivante Var teT Temps total Temps total Intervalle de Intervalle de Nombre de cluster moyen avec des moyen avec des temps avec temps avec contraintes de contraintes de contraintes de contraintes de type E type G type E type G 3 726 419 194 88 80 17 3155 25 28 17 615 09 4 73 816 71 387 45 16 111 26 14 4 167 97 5 147 615 70 407 97 93 269 26 30 13 152 59 6 443 634 303 532 368 46 715 84 157 41 752 1 7 388 372 163 135 225 53 613 1
13. parties sont articul es autours de la classe centrale MasterProblem comme le montre la figure 5 en page suivante Une importante source de documentation que nous avons utilis e pour nous familiariser est les rapport de stage de l quipe pr c dente 2 6 La classe MasterProblem fait donc le lien entre toutes les parties du programme gr ce ses attributs et m thodes La classe Column ainsi que ses d riv es sp cifiques chaque sous probl me repr sente les clusters Cette classe tant une fille de la classe BitVector les colonnes sont des vecteurs de bits de taille le nombre d observations Elle comporte de plus un attribut cost pour stocker le co t du cluster Les objets sont quant eux des points et leur pr sence dans un cluster est repr sent e par un 1 dans le vecteur contre un O pour leur absence De plus l ordre des points est d fini arbitrairement celui de leur lecture dans le fichier d entr e Les matrices classes Matrix et SymMatrix sont des vecteurs de vecteurs doubles servant stocker les dissimilarit s Les dissimilarit s sont des valeurs num riques positives permettant de mesurer les diff rences entre deux observations La pr sence de deux classes distinctes vient du fait que les dissimilarit s ne sont pas forc ment sym triques m me si elles le sont pour la plupart des crit res sur lesquels nous avons travaill Ces valeurs sont utilis es pour calculer le co t d une colonne
14. rarchique 5 1 Principe et code existant 5 1 1 Principe Le principe d une m thode hi rarchique est le suivant pour un ensemble de n points on cr e n clusters On fusionne ensuite les clusters deux a deux de telle sorte que le co t de la fusion soit le plus faible possible et ce jusqu n obtenir plus qu un seul cluster Une telle m thode permet de savoir en combien de clusters il faut classer les n points pour avoir la meilleure solution optimale possible La fusion d un cluster peut se faire de plusieurs fa on diff rentes Voici les deux principales m thodes existantes m thodes que j ai impl ment es dans mon programme La m thode du lien simple lors de la fusion de deux points ou de deux clusters on garde la plus petite dissimilarit entre cette nouvelle entit et les autres La m thode du lien complet lors de la fusion on garde la plus grande dissimilarit entre la nouvelle entit et les autres Pierre Hansen m a appris qu un programme permettant de faire une classification hi rarchique a d j t cr e par M Fionn Murtagh professeur l universit de Londres en Fortran 77 Il m a donc conseill de rechercher le code et de m en inspirer pour cr er mon programme qui lui devait tre en C M Hansen m a galement donner les r f rences d un article de M Murtagh 9 dans lequel il explique les algorithmes qu il a utilis pour la cr ation de son programme Rapport de stage 2009
15. sensiblement identique Une telle classe se doit donc d tre particuli rement bien comment e et doit comporter toutes les m thodes indispensables pour qu un crit re puisse tre ajout De plus une impl mentation de ces m thodes fut r alis e en mettant chaque fois les diff rentes possibilit s offertes telle l utilisation de l heuristique de recherche voisinage variable Variable Neighborhood Search en anglais g n rique ou quadratique toute deux pr sentes dans le programme Afin de faciliter la t che de programmeurs voulant reprendre le projet Isabelle Barclay et moi m me avons r alis un tutoriel pr sent en annexe du rapport expliquant les diverses manipulations effectuer pour l ajout d un crit re telles les modifications apporter au makefile 3 Voir description compl te dans la section 3 2 en page 24 Rapport de stage 2009 15 2 5 Cr ation de classes Classification de donn es non supervis e If you use the generic VNS you have to create your class like this class Example public VnsColumnGeneration public VnsFirstPartition protected place here the attributs public 1 4 Constructor Example DataSet inDataSet SolverInterface inSolver MasterProblem inDataSet inSolver initialisation of the random generator long int graine time NULL loop in order to make srand working better srand graine int i rand 1000000 std cout lt lt graine l
16. solution optimale Nous avons d cid d impl menter une V N S sp cifique la somme des diam tres Une V N S pour Variable Neighborhood Search ou Recherche Voisinage Variable est un algorithme d optimisation stochastique propos en 1997 par Pierre Hansen et Nenad Mladenovi Le principe est de modifier progressivement une solution d j existante du probl me pour en trouver une meilleure Dans le cas d une V N S sp cifique la somme des diam tres les modifications se font en d pla ant un point formant le diam tre d une colonne appel index dans une autre colonne L algorithme de base de la m thode descent qui effectue ces modifications est donc le suivant trouv vrai optimal faux Tant que trouv on prend un point au hasard dans la liste des index on stock le co t de sa colonnel et les index de cette colonne on choisi une colonne2 diff rente de colonnel on stock le co t de cette colonne et ses index on change le point de colonne on calcul les nouveaux diam tres si la somme des 2 nouveaux diam tres est inf rieure celle des 2 anciens ou si elle est gale on met jour la liste d index trouv vrai optimal vrai sinon on remet les index et co t initiaux des colonnes on remet le point dans son ancienne colonne on change de colonne2 fin si fin tant que retourner optimal Figure 19 Algorithme de la descente Rapport de stage 2009 25 3 2 Nouvelle heuristique de d par
17. 37 5 1 Principe et code existant Classification de donn es non supervis e 5 1 2 Code existant L algorithme principale utilis par M Murtagh est le suivant tape 1 construire la matrice de dissimilarit s tape 2 construire une cha ne de NNs partir d un point NN Nearest Neighbour tape 3 Fusionner les RNNs en un cluster RNN Related NN tape 4 mise jour des dissimilarit s et de la liste des NNS tape 5 Recommencer l tape 2 jusqu n avoir qu un seul cluster Figure 25 Algorithme de la m thode hi rarchique La matrice de dissimilarit contient les dissimilarit s entre les diff rents points bas es sur la norme euclidienne Ainsi la dissimilarit entre deux points X x1 xn et Y y1 yn est calcul e de la mani re suivante n d X Y gt xy Pour l tape 2 la cha ne de Nearest Neighbour ou voisin proche et construite selon l algorithme suivant On prend un point i au hasard On prend j NN i On continue jusqu trouver p NN q et q NN p Figure 26 Algorithme de construction de la liste des NN Lorsque p NN q et q NN p on dit que les points p et q sont des RNN Related Nearest Neigbhour soit voisins proches reli s On d finie de plus la relation j NN i comme suit j NN i gt d i j min d i k keP il ou P est l ensemble des points La programme de M Murtagh affiche en sortie u
18. 6 23 64 579 38 8 732 431 281 786 217 9 1079 61 132 9 459 93 Figure 18 Comparaison de r sultats On remarque ainsi que cette modification apporte r ellement un gain de temps important Cependant de plus amples tests seront a mener pour voir si ce gain est pr sent pour tous les types de probl mes qu ils soient difficiles ou simples Il va de soit que les r sultats obtenus concernant la fonction objectif restent les m mes avant et apres le changement 24 Rapport de stage 2009 ga igation de donn es non supervis e 3 2 Nouvelle heuristique de d part la 3 2 Nouvelle heuristique de d part la V N S Dans le but d am liorer le crit re de la somme des diam tres nous avons test une nouvelle heuristique de d part c est dire une nouvelle mani re de cr er de fa on stochastique les premi res colonnes qu on fournit au programme L heuristique de d part existante consistait cr er p 1 clusters contenant chacun 1 point et 1 cluster contenant n p 1 points de telle sorte que la colonne contentant n p 1 points soit de diam tre le plus petit possible Cette m thode donnait des r sultats mitig s trouvant parfois la solution optimale mais trouvant la plupart du temps une solution de l ordre de 10 de la solution optimale alors que les heuristiques initiales des autres crit res impl ment s dans le programme trouvent dans le pire des cas des solutions de l ordre de 2 de la
19. Ainsi pour le crit re de la somme des diam tres le co t d une colonne est la plus grande dissimilarit entre deux points de cette colonne 8 Rapport de stage 2009 Classification de donn es non supervis e 1 2 Pr sentation du probl me CplexStabilized CplexSolver PartitionColumn solverinterface lt LE ColumnVnsAble F soron a RE 1 1 1 BranchAndBound EE 1 Y i 1 1 1 eo ColumnPmedian ColumnStorage lt gt MasterProblem lt gt SymMatrix oo F PWn i C MMM A pataser F 37 Q PointStoragelnterface VnsFirstPartition CF M C EJ el vir h VnsColumnGeneration L gt ClusteringPointStorage LocalisationPointStorage GenericProblem DimensionException ConfigurationException OpeningException PartitionException CplexException typeerception nangeexception Figure 5 Diagramme de classe UML de l application Rapport de stage 2009 9 Deuxi me partie Gestion du code Classification de donn es non supervis e 2 Gestion du code 2 Gestion du code 2 1 Passage de 32 64 bits L une des premi res choses faire sur le programme a consist le mettre jour En effet les serveurs qu utilisaient les stagiaires de l an pass et donc pour lesquels avait t cr le programme taient en 32 bits Une mise jour ayant t effectu e les serveurs sont maintenant pass s en 64
20. In order to solve such problems the program on which i did my internship and which is composed by an initial heuristic a second heuristic and an exact method use linear programming softwares However these softwares can add problems such as the numerical precision and we have to use a specific class in order to control this There is also a fast way to know the optimal number of cluster for a given problem We have to use a hierarchic method which gives us the cost of the fusion of two clusters and allow us to determine if a classification in that number of cluster is correct or not Keywords clustering sum of diameters heuristic exact method linear programming software numerical precision hierarchic method Rapport de stage 2009 Table des mati res Classification de donn es non supervis e Remerciements Table des figures R sum Abstract Table des Mati res Introduction 1 1 Pr sentation 3 Til Pr sentation du GERAD sapin int Il 3 1 2 Pr sentation du probl Me s seresrrerrrsrrsrrrrrerrrrrnrrrnrrnrrrernrrnrnnrnrnrnrrnrenrne 4 1 2 1 La classification non supervis e iiic 4 1 2 2 Utilisation du Branch And Bound ccc cici ccc ecc ciciriririrrerirras 5 1 2 3 M thode de r solution par g n ration de colonne 6 1 2 4 Le projet Stan eo CA nd ed nn er A 7 2 Gestion du code 11 2 1 Passage de 32 64 PIS ann Ac ARS es se Sada eet 11 2 2 Utilisation de
21. a meilleur partition au probl me ma tre compl ter la partition Figure 17 Algorithme final de la m thode CreateFirstColumn 3 1 3 Changement de type de contraintes du probl me maitre On a vu la figure 12 que la fonction objectif est soumise des contraintes permettant d assurer le fait qu on ai une partition et que celle ci soit du bon nombre de clusters Cependant dans le cas de la somme des diam tres la contrainte qui fait que chaque point doit se trouver dans un seul cluster savoir Xayal teT peut tre chang e en la contrainte suivante ayy 21 teT c est dire qu un point peut tre dans plusieurs clusters Cela peut paraitre surprenant car on veut une partition des points et on permet cependant un point d tre dans plusieurs clusters La particularit de la somme des diam tres vient du fait qu un point peut changer de cluster plusieurs fois sans que cela change le diam tre des clusters concern s et donc la fonction objectif Le changement de type de contrainte fait qu elles sont ainsi plus rapidement respect es et devrait donc permettre un gain de temps relativement important De plus on est quand m me assur d avoir une partition car le programme ne met effectivement le point que dans une seule colonne Le changement de type de contraintes permet seulement au solver de trouver plus facilement une solution r alisable du probl me lui vitant de devoir calculer toutes
22. ai mis l ancienne heuristique de d part comme m thode d initialisation On est ainsi sur d avoir une solution r alisable en un temps court et avec une part d al atoire De plus elle pr sentait l avantage d tre d j impl ment e Cependant je me suis rendu compte au bout de quelques tests que ce n tait peut tre pas la meilleur solution car le temps du programme taient beaucoup plus long qu avec l ancienne version J ai donc impl ment une m thode cr ant une partition des points selon l algorithme suivant 26 Rapport de stage 2009 Caa HERO de donn es non supervis e 3 2 Nouvelle heuristique de d part la cpt 0 tant que cpt lt n on se place au d but de la partition tant que on est pas a la fin de la partition on choisi un point au hasard dans la liste des points si ce point n a pas d ja t choisi on le met dans la colonne on passe a la colonne suivante on marque le point comme tant marqu on incr mente cpt fin si si cot n on va a la fin de la liste de la partition fin si fin tant que fin tant que Figure 21 Algorithme de la m thode init La liste de points est un vecteur dans lequel on met l indice du point s il n a pas encore t choisi et 1 d s que le point est plac dans une colonne Gr ce a cette m thode on est s r d avoir une partition des points et une part importante d al atoire J ai donc effectu des tests qui cette fois ci se sont av r s un peu plus co
23. ations et donc de ne pas perdre de temps en optimisant d autres m thodes inutilement L optimisation de ces m thodes sera d velopp e dans la partie suivante Rapport de stage 2009 13 2 5 Cr ation de classes Classification de donn es non supervis e 2 5 Cr ation de classes 2 5 1 Cr ation de classes m res pour les solver Afin de rendre le code un peu plus lisible il a t convenu que des classes m res Cplexinterface et Glilpkinterfaces seraient cr es En effet dans le programme existant taient pr sentes deux classes CplexSolver et CplexSolverStabilized De m me une classe G pkSolver existait et j ai cr une classe GlpkSolverStabilized sur le m me principe Ces classes qui comme leur nom l indique permettent de faire le lien avec les logiciels de programmation lin aire regroupaient cependant des m thodes identiques et cr aient ainsi une redondance de code inutile Ancienne organisation gt rai N CplexSolver CplexSolverStabilized GlpkSolver GlpkSolverStabilized Figure 8 Ancien diagramme de classe UML de la partie solver Pour r duire cette redondance j ai cr des classes interm diaires Glpkinterface et Cplexinterface tel que repr sent sur la figure 5 regroupant toutes les m thodes identiques pr sentes dans les classes en d rivant tels le constructeur les m thodes d criture dans un fichier ou encore celle de fermeture du programme Nouvelle organ
24. concernant le crit re de la somme des diam tres de m occuper de la pr cision num rique dans le code et de cr er un programme permettant d effectuer une m thode hi rarchique ind pendamment du projet Cependant au fil des semaines j ai t amen en plus impl menter un lien entre le programme et un logiciel de programmation lin aire et m occuper de la maintenance du code Je pr senterai dans une premi re partie l environnement de travail ainsi que le projet existant Dans une deuxi me partie seront expliqu s les changements que j ai r alis dans le code du programme La troisi me partie d crira le crit re de la somme des diam tres et les modifications que j ai apport ce sous probl me J expliquerai dans une quatri me partie l ajout de la possibilit d utiliser le logiciel de programmation lin aire Gipk Enfin la derni re partie traitera de la cr ation d un programme effectuant une m thode hi rarchique Rapport de stage 2009 1 Premi re partie Pr sentation Classification de donn es non supervis e 1 Pr sentation 1 Pr sentation 1 1 Pr sentation du GERAD Le GERAD Groupe d Etude et de Recherche en Analyse des D cisions est un centre de recherche inter universitaire de Montr al cr en 1979 Il est essentiellement financ par HEC Montr al l cole Polytechnique de Montr al l Universit McGill l Universit du Qu bec a Montr al et le Fond Qu b cois de la Recherche sur la Natu
25. ctionne correctement elle trouve les m mes r sultats que Cplex et dans des Rapport de stage 2009 29 3 3 M thode exacte de r solution du probl me auxiliaire Classification de donn es non supervis e temps sensiblement identiques pour des petits probl mes jusqu 30 points Cependant les temps d ex cution augmentent avec le nombre de points mais de mani re beaucoup plus importante que pour Cplex Ainsi pour un probl me de 60 points l o le programme met en moyenne 30 secondes pour r soudre le probl me avec Cplex il met jusqu 80 000 secondes avec Glpk On s est ainsi rendu compte que Glpk n tait pas un bon concurrent pour Cplex sur les probl mes lin aires en variables binaires et qu il faudrait continuer d utiliser Cplex pour le crit re de la somme des diam tres 30 Rapport de stage 2009 Quatri me partie GLPK 4 Glpk Classification de donn es non supervis e 4 Glpk 4 1 Description Comme nous l avons vu pr c demment le programme utilise des logiciels de programmation lin aire et plus particuli rement Cplex Or ce dernier est un logiciel propri taire cr par l entreprise Fran aise ILOG dont les licences sont relativement on reuses et le GERAD n en poss de que quelques unes L utilisation du programme est donc souvent limit e par la disponibilit ou non d une licence Cplex Pour rem dier a ce probleme Gilles et Sylvain ont voulu utiliser le logiciel libre Glpk GNU Linear
26. dans un premier temps v rifier si ces m thodes taient finies et faisaient ce qu il fallait J ai ensuite d cr er les m thodes n cessaires l utilisation de Glpk telle la m thode d initialisation du solver qui se charge de transcrire le probl me fourni par le programme en probl me compr hensible par le solver ou les m thodes permettant de modifier les contraintes appliqu es aux colonnes et aux points les composants L une des parties difficiles de cette impl mentation t de faire le lien entre les diff rents index que prennent les colonnes au cours du programme En effet les colonnes sont cr es avec un index par le solver puis envoy es au probl me secondaire qui v rifie si elles sont am liorantes ou non et qui le cas ch ant les fait parvenir jusqu au probl me ma tre qui les stocke Cependant le solver est appel plusieurs fois par le programme et cr un nouveau probl me chaque appel Une colonne fournie par le solver peut ainsi avoir le m me index qu une colonne d j stock e par le probl me ma tre Pour rem dier a un tableau index faisant le lien entre les index du solver et ceux du probleme ma tre a t ajout en attribut la classe G pkSolver et les m thodes permettant de mettre jour ce tableau ont t cr es Ce tableau pr sent aussi dans les classes permettant de faire le lien avec Cplex m a de plus permis de trouver par la suite pourquoi ma premi re version de la cla
27. el Gprof un gain de temps et de performances du programme pour le crit re de la somme des diam tres passe par une optimisation de m thodes notamment celle qui permet de calculer le diam tre d une colonne et celle qui calcule le co t de l entr e d un point dans une colonne Je me suis donc pench sur entre autre ces deux m thodes La m thode calculDiam qui prend en param tre la colonne dont on veut calculer le co t fonctionne selon l algorithme suivant temp 1 Pour chaque pointl si le point1 est dans la colonne pour chaque point2 sup rieur point1 si point2 est dans la colonne et si la dissimilarit entre point2 et pointl est sup rieure a temp temp la dissimilarit entre point2 et point 1 pointl et point2 forment le diam tre de la colonne fin si fin pour fin pour on met jour le co t de la colonne Figure 13 Algorithme initial de la m thode calculDiam 20 Rapport de stage 2009 Classification de donn es non supervis e 3 1 Modifications du code existant Pour conna tre la dissimilarit entre les points 1 et 2 on fait un appel la m thode getDissimilarity On fait ainsi deux appels cette m thode si le point2 est dans la colonne alors qu on pourrait n en faire qu un seul et stocker le r sultat dans une variable Cela ferait faire moins d appels la m thode et donc gagner en th orie un peu de temps J ai effectu ce changement et fait en sorte que l appel la m thode ge
28. ent LP solvers 2004 9 Murtagh F Complexities of hierarchic clustering algorithms state of the art Computational Statistics Quarterly 1 101 113 1984 Rapport de stage 2009 Classification de donn es non supervis e Lexique Lexique de programmation Attribut selon l orientation objet un attribut est une donn e interne une classe Ci langage de programmation cr dans les ann es 1970 C langage de programmation objet cr dans les ann es 1980 par Bjarne Stroustrup bas sur le C Classe description abstraite des donn es et du comportement d un objet Diagramme de classe diagramme UML repr sentant les liens des classes les unes par rapport aux autres Fichier d en t te en C fichier contenant une liste des libraires utilis es et la d finition de la classe concern e Fortran 77 langage de programmation cr en 1956 utilis principalement pour les math matiques et les applications de calculs scientifiques G n rateur de nombre pseudo al atoire algorithme g n rant une s quence de nombres pr sentant des propri t s du hasard Interface classe abstraite c est dire qui ne peut tre instanci e qui d finie les grandes lignes adopter par les classes en d rivant Librairie ou biblioth que ensemble de fonctions ou de proc dures ayant de pr f rence un point commun mises a la disposition des programmeurs Logiciel libre logiciel dont la licence
29. est libre que chacun peut utiliser modifier tudier et diffuser Rapport de stage 2009 Classification de donn es non supervis e Lexique Logiciel propri taire logiciel entravant l une des possibilit s d un logiciel libre le terme logiciel propri taire est souvent employ pour d signer un logiciel dont l utilisation requiert l achat d une licence aupr s de son producteur Main programme principal Makefile logiciel traditionnel d UNIX servant cr er des fichiers M thode selon l orientation objet une m thode est une fonction interne aux classes Pointeur en C comme en C un pointeur est une variable contenant l adresse m moire de l objet point UML Unified Modeling Language ou Langage de Mod lisation Unifi c est un langage graphique non propri taire de mod lisation des donn es Rapport de stage 2009 Classification de donn es non supervis e Lexique Lexique du programme Cluster terme anglais pour classe ensemble de points On parle aussi de colonne Dissimilarit repr sente les diff rences entre deux points lorsqu elle est bas e sur la norme euclidienne il s agit de la distance entre les deux points G n ration de colonne m thode permettant d initialiser les programmes lin aires efficacement M thode exacte m thode permettant de trouver coup sur s il en existe une colonne am liorante pour le probl me D pend de chaque cri
30. et de mettre a jour la liste des NNs la m thode display qui affiche le r sultat Rapport de stage 2009 39 5 2 Impl mentation Classification de donn es non supervis e Le choix des structures de donn es utilis es s est fait en fonction des avantages et des inconv nients de chaque type et de l utilisation que j allais en faire Ainsi la matrice de dissimilarit s qui tait dans le code de M Murtagh une matrice triangulaire stock e dans un simple vecteur est dans mon programme une v ritable matrice sym trique stock e dans un vecteur de vecteur Ce choix a t fait pour faciliter l acc s aux donn es vitant ainsi l utilisation d une m thode devant calculer la position du point dans la matrice gr ce aux coordonn es de ce point comme cela tait fait dans le code en Fortran De m me la liste de NNs est en fait un vecteur l aussi par soucis d acc s au donn es J ai enfin utilis un vecteur pour stocker les dissimilarit s associ es aux NNs appel dissnn La m thode run fonctionne selon l algorithme suivant Cpt nombre de points on construit la liste des NNs tant que cpt est diff rent de 1 cpt cpt 1 on choisi quelles entit s fusionner on met a jour les donn es pour la m thode display on met a jour la matrice de dissimilarit s on met a jour la liste des NNs fin tant que Figure 28 Algorithme de la m thode run La m thode qui a pos le plus de probl mes s est av r e
31. fet Rapport de stage 2009 27 3 3 M thode exacte de r solution du probl me auxiliaire Classification de donn es non supervis e l utilisation de la m thode exacte ralentie consid rablement le programme c est d ailleurs pour cela qu on utilise une heuristique Mais en pratique la m thode heuristique ne trouve pas toujours la solution optimale du premier coup et il faut donc lancer plusieurs fois la m thode exacte Pour le crit re de la somme des diam tres la m thode exacte inspir e par Sylvain Perron est un probl me lin aire qui fait appel directement au solver Si la r solution de ce probl me fournie une colonne am liorante alors on l ajoute au probl me ma tre et on relance l heuristique Sinon l optimalit a t atteinte La formulation du probl me lin aire r soudre est la suivante min Drax u Yi H s c dli j y lt Dmax VW i j et y y lt y j 1 V i j Figure 22 Probl me lin aire associ la m thode exacte O Dmax est le diam tre de la colonne e yi vaut 1 si le point i est dans la colonne O sinon yj vaut 1 si les points i et j appartiennent la colonne 0 sinon Ui Un H est le vecteur dual associ au probl me P d fini figure 12 3 3 1 Passage a GLPK Comme dit pr c demment cette m thode fait directement appel au solver Or l an dernier elle n a t impl ment e que pour tre utilis e par le logiciel Cplex Comme no
32. i au moment d envoyer la solution trouv e par le solver au programme Il faut en effet r cup rer les bonnes variables renvoyer sous peine de fausser totalement les r sultats Il a donc fallu faire tr s attention aux indices utilis s lors des manipulations sur les colonnes La classe Gl pkSolverStabilized contient de plus des m thodes que la classe GlpkSolver n a pas telles les m thodes pour fixer les bornes des points ou pour r cup rer les diverses valeurs telles les dites bornes 4 3 R sultats du solver Pour pouvoir comparer les deux solvers j ai lanc un grand nombre de tests sur les crit res de la clique de l toile et de la coupe normalis e crit res g r s aussi par le programme Je n ai pu en faire sur la sommes des diam tres car comme nous l avons vu pr c demment la m thode exacte de ce crit re est limit e un faible nombre de points avec Glpk Les tests ont donc t effectu s comme suit sur un fichier de 59 points class s de 3 a 35 clusters pour le crit re de la clique e sur un fichier de 500 points class s de 50 250 clusters pour les crit res de l toile et de la coupe normalis e J ai lanc en parall le le programme avec Cplex et avec Glpk avec et sans stabilisation et est ensuite compar diff rents r sultats qui ont t assez surprenants Ainsi pour le crit re de la clique nous avons les r sultats suivants sans stabilisation le programme est de 10 50 plus le
33. ienne m thode exactSol Celle ci cr e un nouveau probl me Cplex qui est celui pr sent figure 22 et le r sout en faisant directement appel aux m thodes de la librairie permettant d utiliser Cplex en C Elle ne passe pas par les m thode de la classe CplexSolver J ai donc cr er la m thode exactSolGlpk qui fait la m me chose mais en utilisant la librairie permettant d utiliser Glpk en C La modification de la m thode exactSol pour faire en sorte d utiliser les m thodes des classes CplexSolver et GlpkSolver tait impossible car le probl me r solu par la m thode exacte utilise des variables binaires Or le probl me ma tre et les sous probl mes n utilisent que des variables continues et les m thodes des classes CplexSolver et GlpkSolver qui ont t cr es pour r soudre ces probl mes ne sont ainsi pr vues que pour utiliser des variables continues Une modification de la m thode exacte aurait donc entrainer des modifications importantes dans les classes des solvers et aurait t plus fastidieuse que de cr er une nouvelle m thode 3 3 2 R sultats J ai ensuite lanc des tests pour v rifier si la m thode marchait et pour compar les temps d ex cution avec les deux solvers Je me suis ainsi rendu compte que Glpk affichait beaucoup d informations inutiles au cours de la r solution du probl me et ai modifi ce probl me Les r sultats obtenus ont t mitig s En effet la m thode exacte sous Glpk fon
34. ier que celle ci est la m me dans tout le programme en utilisant une classe d di e cette t che Il existe aussi une mani re rapide de conna tre le nombre de sous ensembles optimal pour un probl me donn Il suffit pour cela d appliquer une m thode hi rarchique ce probl me Une telle m thode nous fournie le co t engendr par la fusion de deux sous ensembles et nous permet de d terminer si une classification en ce nombre d ensemble est correcte ou non Mots cl s classification de donn es non supervis e somme des diam tres heuristique m thode exacte logiciel de programmation lin aire pr cision num rique m thode hi rarchique Rapport de stage 2009 Abstract Classification de donn es non supervis e Abstract The clustering is a method which consist in classifying different observations in an unknown partition of clusters following a criterion These observations can be classified in an homogeneous way a distinct way or those two The homogeneity is when every points in a same cluster are very close and the distinction is when the points in a cluster are different from the points in other clusters The sum of diameters criterion is an homogeneous problem of clustering Following this criterion points are classified in clusters in order to have the smallest diameter for the final partition which means that the sum of all the diameters of the clusters in the partition are is the smallest possible
35. ification de donn es non supervis e R sum R sum La classification de donn es non supervis e est une m thode consistant classer diff rents objets en une partition de sous ensembles non connue l avance selon un crit re Ces observations peuvent ainsi tre class es de mani re homog ne distincte ou les deux L homog n it se traduit par le fait que tous les points pr sents dans un sous ensemble sont similaires la distinction se traduit quand elle par le fait que les points pr sents dans un sous ensemble sont diff rents de ceux pr sents dans un autre sous ensemble Le crit re de la somme des diam tres est un probl me de classification homog ne Selon ce crit re les objets sont rang s dans les sous ensembles de telle sorte que le diam tre de la partition finale qui correspond la somme des diam tres des sous ensembles la composant soit le plus petit possible Le diam tre d un sous ensemble correspond la plus grande dissimilarit entre deux objets pr sents dans cet ensemble Pour r soudre de tels probl mes le programme sur lequel j ai effectu mon stage et qui se compose d une heuristique initiale d une seconde heuristique et d une m thode exacte utilise des logiciels de programmation lin aire reli s au programme gr ce des classes sp cifiques L utilisation de tels logiciels peut cependant poser des probl mes au niveau par exemple de la pr cision num rique et nous devons v rif
36. isation m T Solverinterface K Glpkinterface Cplexinterface GlpkSolver CplexSolver CplexSolverStabilized GlpkSolverStabilized Figure 9 Nouveau diagramme de classe UML de la partie solver 14 Rapport de stage 2009 Classification de donn es non supervis e 2 5 Cr ation de classes Notons qu il a fallu faire quelques modifications dans le code suite ce changement En effet Cplex tant un logiciel propri taire son utilisation n cessite une licence qui co te relativement cher Or pour le crit re de la somme des diam tres la m thode exacte impl ment e se sert du solver Cplex Les classes CplexSolver et CplexSolverStabilized avaient donc t cr es pour que la m me licence soit utilis e dans la r solution de la m thode exacte de la somme des diam tres et dans la r solution du probl me ma tre et il a fallu modifier quelque peu les classes associ es Cplex pour que cela soit toujours le cas 2 5 2 Cr ation de la classe Example Le programme sur lequel porte mon stage a t commenc l an dernier et sa conception se poursuivra encore au moins l an prochain Ainsi dans l objectif de laisser un programme sur lequel il sera facile de revenir il a t d cid de cr er une classe servant d exemple pour l ventuel ajout d un futur crit re Cela a t facilit par le fait que la plupart des crit res actuels sont cod s de fa on
37. it d exporter les fichiers de sortie au format Latex ou Excel a t rajout e suite la cr ation par Florian des classes le permettant Les mains des diff rents sous probl mes tant tous construits de la m me facon appel des m thodes buildBranchAndBound et widthTreeCover la mise en commun n a pas t compliqu e Le choix du crit re se fait gr ce a un entier pass en param tre qui se r percute ensuite par un changement d un param tre de la m thode buildBranchAndBound Il en va de m me pour le choix du solver et de l utilisation ou non de la stabilisation La possibilit d exporter les fichiers de sorties tant optionnelle il a fallu trouver comment faire en sorte de prendre en compte ces options uniquement lorsqu elles sont pr sentes Il a donc t convenu de les placer la fin de la ligne de commande et les deux derniers arguments sont test s chaque fois pour voir s il s agit ou non de ces options La ligne de commande finale du main global ressemble donc ceci exeGlobal ProblemType Stabilization SolverType InputFile NbOfCluster NbOfClusterFinal OutputOptions ProblemType 1 Normalized Cut 2 Clique 3 Sum of Diameters 5 Sum of Stars Stabilization 1 no 2 yes SolverType 1 Cplex 2 Glpk NbOfClusterFinal if you wan t to do tests from nbOfCluster to NbofClusterFinal OutputOptions e or E to output results in CSV file
38. ivante IC f C X ua n Le sous probl me peut donc se r sumer comme suit 4 C a 0 1 tel que p C lt 0 Figure 4 Probl me auxiliaire Ce probl me peut tre r solu de plusieurs mani res gr ce des m thodes heuristiques des m thodes exactes ou les deux comme nous le verrons dans la partie 3 en page 19 On obtient ainsi une colonne ai i 1 17 de la matrice A qui repr sente le cluster en variables binaires Si le probl me auxiliaire a une solution alors celle ci est ajout e au probl me ma tre sinon on a r solu le probl me R 1 2 4 Le projet existant Le but de mon stage ainsi que de celui des autres stagiaires de cette ann e tait de travailler en quipe sur le projet ayant t commenc l an dernier par les stagiaires de l ISIMA Lors de ce stage ils ont d velopp un programme permettant de faire de la classification non supervis e selon diff rents crit res tel par exemple la somme des diam tres crit re que j expliquerai dans une partie 1 Voir figure 1 page 5 2 Voir figure 2 page 6 Rapport de stage 2009 7 1 2 Pr sentation du probl me Classification de donn es non supervis e ult rieure Le programme comporte cinq grandes parties qui sont la gestion du probl me ma tre la gestion des sous probl mes l interface avec les logiciels de programmation lin aire le stockage des donn es et la gestion du Branch And Bound Ces cinq
39. la classe accuracy 11 2 53 Main GIODa lisa En etes Duran R Rats ne nie fume vous rene us BRON LE 12 PN C 0170 A RE ARTS EE E ETTA A NA R RA 12 2441 ICS CHDEON Se 20202 e Re OO Mn a ee tete re SES 12 2 4 2 WIS ATOS SR ee ne tn Er e SORS Eata CACA Dain 13 25 Cr ation de CSSS nn retenue e aient E 14 2 5 1 Cr ation de classes m res pour les solver 14 2 5 2 Cr ation de la classe Example 15 2 5 3 Utilisation d une partitiONisssess ss sian and eeenet eatin cee 17 3 La somme des diam tres 19 3 1 Modifications du code exiStaht sss emmener en ee sienees 20 3 1 1 Optimisation de m thodes 20 3 1 2 Modification de m thodes 21 3 1 3 Changement de type de contraintes du probl me maitre 23 3 2 Nouvelle heuristique de d part la V N S 25 3 3 M thode exacte de r solution du probl me auxiliaire 27 3 3 1 Passage CRE E d 229222 22 E E e em de rien ete R Rae 28 3 3 2 R SUIE ES inserer ca E A ae trade DeM denen ede R rE 29 4 Glpk 32 AL DESTINE irera n EEE EE EALE A a E AR DE Soda 32 4 2 Impl mentation du SO Ver sut sessareeerevenssenenseranenenennenerementeus sente 33 4 2 1 Sans Sta OMS el LOW isos troci 2292204443306660 a se ennui 33 4 2 2 Avec StAaDHISATION 5 an de Un I errant uns 34 43 R sultats SOMME etant Mania ere ee nr ttes 34 5 M thode hi rarchique 37 5 1 Principe etcode exis tant antenne xeeeanes cent
40. ltats Comme on l a vu le programme de M Murtagh affiche un dendogramme Cependant pour ne pas passer trop de temps a coder la m thode display nous avons d cid de ne pas chercher faire de m me mais plut t a afficher un tableau qui comprendrait les entit s fusionner le co t de la fusion et le nombre de clusters Voici un exemple de ce que nous fourni le programme ost NbCluster Points 19 X X 18 17 16 15 14 13 12 LT 10 Ra ve x e x x EE a NEPBBBBBBBBBEEBEFEEFBEBEO Ww x e N U amp C1 OU J oO 0 T Figure 30 R sultat de la m thode hi rarchique La colonne cost repr sente le co t engendr par la fusion des deux entit s s lectionn es qui correspondent au X dans le tableau On remarque ainsi que pour ce fichier de 20 points on peut fusionner sans probl mes jusqu deux Rapport de stage 2009 41 5 3 R sultats Classification de donn es non supervis e clusters mais la fusion en un unique cluster est tr s co teuse Le programme fourni des r sultats coh rents avec les tests que nous avions men s pour les diff rents crit res et ce pour tout nombre de points De plus ces r sultats sont tr s rapides Il faut par exemple 13 secondes au programme pour traiter un fichier de 1 000 points L impl mentation d une m thode hi rarchique a donc t un succ s 42 Rapport de stage 2009 Classification de donn es non supervis e Conclusion
41. mbreuses revues scientifiques internationales Richard Loulou a t directeur du GERAD de 1989 a 1992 et a fait partie de l quipe qui a labor un logiciel de simulation utilis par Al Gore dans ses travaux lui ayant valu son prix Nobel de la Paix en 2007 Francois Soumis a t directeur du GERAD de 1992 a 1996 et fait partie de l quipe l origine du logiciel GENCOL logiciel de GEN ration de COLonnes Il s agit d un logiciel d optimisation math matique d velopp pour traiter les probl mes de tourn es et d horaires de v hicules et d quipage Site internet de GENCOL Il est utilis pour mettre au point les syst mes de transport en commun dans des villes telles Tokyo Singapour ou Barcelone Ce logiciel est galement utilis par des compagnies telles Air France ou Air Canada Rapport de stage 2009 3 1 1 Pr sentation du GERAD Classification de donn es non supervis e Le GERAD travaille principalement sur trois grands axes de recherches qui sont les suivants e M thodes d analyse math matique pour l aide la d cision e D veloppement d applications dans les grands syst mes technologiques commerciaux et conomiques D veloppement de logiciels commerciaux d aide la d cision 1 Le laboratoire poss de de plus trois missions e D velopper la math matique de la d cision sous toutes ses formes dans les grands syst mes technologiques commerciaux et cono
42. milarit s entre les points Cependant les stagiaires de l an dernier n avaient pas utilis les m thodes de cette classe syst matiquement Cela cr ait donc des probl mes car certains calculs taient effectu s une pr cision de 10e 6 et d autres ceux utilisant la librairie standard du C 10e 12 Il a donc fallu parcourir le code pour faire en sorte que toutes les comparaisons de double se fassent gr ce la classe accuracy Cela a permis de r gler certains probl mes dont nous n arrivions pas a trouver la source et qui d pendaient en fait de la pr cision des calculs Rapport de stage 2009 11 2 3 Main Global Classification de donn es non supervis e 2 3 Main Global A notre arriv e il n existait pas de main global permettant de choisir la main son crit re Chaque sous probl me avait ainsi son main et il fallait veiller compiler le programme avec les bonnes options pour pouvoir avoir l ex cutable souhait Par soucis de simplifier l utilisation du programme en ligne de commande et pour pouvoir plus facilement faire le lien avec l interface graphique qu lsabelle a d velopp e cette ann e nous avons d cid de cr er un main global permettant de choisir non seulement son crit re mais aussi le type de solver que l on veut utiliser Cplex ou Glpk et si on veut utiliser ou non la stabilisation choses qui n taient pas r alisables avec les mains sp cifiques a chaque crit re De plus la possibil
43. miques et en amont de la d cision d velopper la mod lisation fond e sur la statistique la simulation et l exploitation des donn es e Former des chercheurs dans les domaines ci dessus e Contribuer l enrichissement de la soci t par la cr ation de spins offs et par le transfert de savoir faire sous forme de consultations en entreprise et de d veloppement de logiciels d aide la d cision 1 Cette volont d ouverture sur le monde de la recherche se traduit entre autre par l organisation annuelle d v nements tels Les journ es de l optimisation durant lesquelles des sp cialistes mondiaux viennent pr senter leurs recherches ou l Universit d t du GERAD s rie d expos s de chercheurs venus d universit s am ricaines ou canadiennes De plus les chercheurs du GERAD prennent part l atelier de r solution de probl mes industriels organis par le Centre de Recherche en Math matiques CRM Lors de ces ateliers des personnes du monde de l industrie soumettent des probl mes aux participants qui sont r partis en quipes de travail comportant des chercheurs des tudiants et des personnes de l entreprise concern e Au bout d une semaine les quipes pr sentent leurs solutions l assembl e Ces ateliers permettent de cr er des liens entre le monde industriel et les chercheurs et aboutissent des contrats de recherche ou des sujets de th ses L quipe de d veloppemen
44. n dendogramme qui permet de conna tre le co t des fusions 38 Rapport de stage 2009 Classification de donn es non supervis e 5 1 Principe et code existant 150 l 50 1 Figure 27 Exemple de dendogramme Sur ce dendogramme l axe des abscisses repr sente les points ou clusters fusionner et l axe des ordonn es repr sente le co t engendr par la fusion des ces deux entit s Avec un tel dendogramme on peut se rendre compte que pour cet exemple une classification en 4 clusters est bien alors qu une classification en 1 en 2 voire en 3 clusters engendre des co t tr s lev s 5 2 Impl mentation Je me suis donc inspir du code de M Murtagh pour cr er le mien J ai ainsi cr plusieurs m thodes ayant chacune un objectif bien pr cis la m thode readFile qui permet de lire le fichier de points pass en parametre du programme et de stocker les points dans une matrice Cette m thode a t reprise du programme principal la m thode buildDissMatrix qui construit la matrice de dissimilarit s a partir de la matrice de points la m thode run qui est la m thode principale et dont le fonctionnement sera d taill par la suite la m thode ConstructList qui permet de construire la liste des NNs la m thode DetermineNN qui permet de choisir quelles entit s fusionner la m thode updateDiss qui permet de mettre la matrice de dissimilarit s a jour la m thode updateNN qui perm
45. ncluant En effet les temps sont voisins de ceux de l ancienne heuristique Ceci est donc encourageant N anmoins la solution trouv e par la V N S est en g n ral aux alentours de 85 de la solution optimale contre environ 10 pour l ancienne heuristique Cependant le temps maximum laiss la V N S ainsi que le nombre d it ration maximum sans am liorations ont t arbitrairement fix a 0 33 secondes et 10 it rations Les r sultats pourront donc peut tre tre am lior s en changeant ces param tres Mais je n ai au moment d crire ce rapport pas encore eu le temps de faire des tests avec d autres param tres 3 3 M thode exacte de r solution du probl me auxiliaire Le but du programme est de trouver la solution optimale coup sur pour chaque probl me qu on lui soumet Pour cela il est d compos en trois tapes tout d abord l heuristique initiale cr e rapidement une solution pas forc ment optimale comme nous l avons vu Ensuite une seconde heuristique cherche la solution optimale Seulement celle ci n est pas sur de la trouver tous les coups Il faut donc une troisi me tape qui est l utilisation d une m thode exacte Cette m thode doit pouvoir g n rer une solution meilleure que celle trouv e par l heuristique si celle ci n est pas la solution optimale Id alement la m thode exacte n est appel e qu une seule fois pour v rifier que la solution trouv e par l heuristique est la solution optimale En ef
46. nt en utilisant Glpk plut t que Cplex Cependant le nombre de colonnes g n r es par le programme et le nombre d it rations qu il lui a fallu pour trouver la bonne solution est 34 Rapport de stage 2009 Classification de donn es non supervis e 4 3 R sultats du solver sensiblement identique peu importe le solver utilis Une fois la stabilisation utilis e par contre le programme devient aussi rapide que se soit avec Cplex ou avec Glpk Pour le crit re de l toile Glpk est plus lent que Cplex de 50 lorsque la stabilisation n est pas utilis e et de 10 a 20 secondes lorsqu elle l est Cependant les temps totaux d passent rarement la minute donc cela reste acceptable Pour le crit re de la coupe normalis e enfin aucun solver ne se d marque En effet le programme peut tre un coup plus rapide avec Glpk et le coup d apr s 30 plus lent avec le m me solver Ces variations n ont pu tre expliqu es On peut donc voir que dans l ensemble Glpk obtient des r sultats satisfaisants par rapport ceux de Cplex pour selon qu il est gratuit L impl mentation de l utilisation de ce solver est donc un succ s Rapport de stage 2009 35 Cinqui me partie M thode hi rarchique Classification de donn es non supervis e 5 M thode hi rarchique 5 M thode hi rarchique En parall le du programme principal nous avons d cid d impl menter un petit programme ind pendant permettant d effectuer une m thode hi
47. onnent correctement par exemple en fournissant directement la solution optimale au programme Cependant cette m thode n tait pas comment e et nous n avions donc aucune id e de comment organiser les donn es dans le fichier qu elle lit m me apr s examen du code correspondant Heureusement une m thode saveFirstPartition tait aussi pr sente dans le code Cette m thode cr e un fichier contenant la partition initiale dans le format voulu et nous a donc permis de nous servir de la m thode loadFirstPartition Il n existait par contre aucune m thode permettant de sauvegarder la partition finale et il fallait cr er a la main le fichier la contenant ce qui peut s av rer fastidieux pour des probl mes de plusieurs centaines de points J ai donc cr une m thode saveOptimalPartition permettant de sauvegarder la partition optimale dans un fichier lisible par la m thode oadFirstPartition Elle est bas e sur le m me principe que la m thode saveFirstPartition Rapport de stage 2009 17 Troisi me partie Le somme des diam tres Classification de donn es non supervis e 3 La somme des diam tres 3 La somme des diam tres Le crit re sur lequel j ai t amen travailler est celui de la somme des diam tres Le diam tre d un cluster C est la plus grande dissimilarit entre deux points x et y pr sents dans ce cluster Diam C max d x y W x y EC En voici une illustration
48. ournait non pas le premier optimum mais le meilleur devenant ainsi identique dans le principe du moins la m thode BestLocalSearch impl ment e elle aussi J ai donc modifi cette m thode pour qu elle fasse vraiment ce qu on attend d elle Ce changement n a cependant pas modifi les r sultats obtenus car la m thode FirstLocalSearch n est appel e qu au tout d but du programme Cela cependant fait gagner quelques secondes l ex cution Rapport de stage 2009 21 3 1 Modifications du code existant Classification de donn es non su pervis e La m thode CreateFirstColumn qui permet comme son nom l indique de cr er les premi res colonnes fournies au programme semblait tre une version encore en construction Il y avait en effet plusieurs tests et variables inutiles pr sents dans le code En voici l algorithme i 0 value 1 000 000 tant que i lt 1 cr er les premi res colonnes et les stocker dans la partition courante si la partition courante a un co t inf rieur a value la partition courante devient la meilleur partition value re oit le co t de la partition fin si i i 1 sii 1 ajouter la meilleur partition au probl me ma tre fin si fin tant que compl ter la partition Figure 15 Algorithme initial de la m thode CreateFirstColumn Remarquant que la boucle tant que i est inf rieur 1 tait inutile de m me que le test pour savoir si i est gal 1 j ai enlev le tes
49. programmation lin aire Enfin le stage m a vraiment fait d couvrir le travail en quipe Le programme n est cependant pas fini et sera continu par les prochains stagiaires La cr ation d une heuristique initiale donnant de meilleurs r sultats que l actuelle sera ainsi faire pour le crit re de la somme des diam tres ainsi que des modifications importantes dans la structure du programme tel par exemple l ajout de la possibilit de ne pas utiliser de m thode heuristique Nous savions d s le d part que le programme serait continu par d autres stagiaires et nous avons donc tout fait au cours de notre stage pour que cela se fasse le plus simplement possible en commentant correctement notre code et en cr ant des tutoriels expliquant les parties les plus compliqu es Rapport de stage 2009 43 Classification de donn es non supervis e R f rences bibliographiques R f rences bibliographiques 1 http www gerad ca site internet du GERAD 2 Helfenstein R Rapport de stage de 2e ann e de l ISIMA 2008 3 Legrand B Rapport de stage de 2e ann e de l ISIMA 2008 4 Ruiz M Rapport de stage de 2e ann e de l ISIMA 2008 5 Sabatier M Rapport de stage de 2e ann e de l ISIMA 2008 6 Thouement S Rapport de stage de 2e ann e de l ISIMA 2008 7 http www gnu org software glpk site internet du logiciel Glpk 8 Fischetti M amp Baracco D Interfacing a MIP heuristic based on ILOG Cplex with differ
50. re des Technologies FQRNT Il regroupe actuellement 70 chercheurs sp cialistes en m thodes quantitatives de gestion en recherche op rationnelle en informatique th orique et en math matiques Il compte aussi 37 chercheurs post doctoraux Le GERAD publie aussi chaque ann e environ 70 num ros des Cahiers du GERAD regroupant les derniers travaux de ses membres De plus ses chercheurs obtiennent r guli rement des contrats de recherche provenant d entreprises priv es du Qu bec et d ailleurs ainsi que d organismes publics provinciaux ou f d raux Pour r pondre ces contrats le GERAD dispose d quipes de chercheurs et de professeurs qui travaillent avec leurs l ves et en collaboration avec d autres laboratoires du Canada ou trangers et plus sp cialement en Europe et aux tats Unis On compte parmi ses membres des chercheurs de renomm e internationale tels VaSek Chvatal Pierre Hansen Richard Loulou et Fran ois Soumis Va ek Chv tal est titulaire de la Chaire de recherche du Canada en optimisation combinatoire et fut le laur at en l an 2000 du prix Beale Orchard Hays for Excellence in Computational Mathematical and Programming Pierre Hansen a t directeur du GERAD de 1996 2001 et est titulaire de la Chaire HEC en exploitation des donn es Il est sp cialiste en recherche op rationnelle et en th orie des graphes et a publi environ 300 articles Il est aussi membre du comit de r daction de no
51. rtait mon stage traitait de la classification non supervis e Le but de la classification est de regrouper un ensemble d objets ou d observations en une partition de diff rents sous ensembles qui doivent tre homog nes et ou distincts selon un crit re choisi Les sous ensembles sont appel s classe en fran ais et cluster en anglais Cependant je vais par la suite utiliser le terme anglais cluster pour ne pas cr er de confusion avec le terme classe qui est aussi utilis lorsque l on parle de programmation Des clusters sont homog nes si les observations l int rieur d un m me cluster se ressemblent Des clusters sont distincts si les objets pr sents dans un cluster sont diff rents de ceux pr sents dans un autre cluster En pratique cela revient minimiser une fonction objectif qui est la somme du co t des clusters sous certaines contraintes comme nous pouvons le voir sur la figure suivante min X f C y P teT souscontraintes gt a y 1 1 teT gt y p 2 teT y 0 1 3 Figure 1 Probleme de d part O nous avons e f C qui repr sente le co t du cluster Cr Test l ensemble des clusters t possibles e y vaut 1 si t est dans la partition solution O sinon e ai Vaut 1 si l objet i appartient au cluster t O sinon pest le nombre de clusters d sir La contrainte 1 assure le fait que nous ayons une partition c est dire que chaque point se trouve dans un et
52. s 37 Rapport de stage 2009 Table des mati res Classification de donn es non supervis e Salk PRINCIDS wiactendhssenewest a a en ee at elt 37 5 132 Code BXIS EAN RE Rendre ee ES Ne 38 52 1mpl mentationz LAS nee den ne pute aaa Tee it auras et Os 39 By S ROSUI ES LE DE ET 41 Conclusion 43 R f rences bibliographiques Lexique de programmation Lexique du programme Rapport de stage 2009 Classification de donn es non supervis e Introduction Introduction Le monde de l industrie de part sa volont de cibler ses clients potentiels est tr s int ress par les probl mes de classification de donn es Ainsi lors d une tude de march une entreprise cherchera conna tre les groupes de population les plus susceptibles d acheter son produit Pour cela elle va tablir diff rents crit res tel l ge ou le sexe de la personne qui lui permettront par la suite de classer cette personne dans un groupe au moyen de m thodes de classification Mon stage de deuxi me ann e l Institut Sup rieur d informatique de Mod lisation et de leurs Applications ISIMA effectu au Groupe d Etude et de Recherche en Analyse des D cisions GERAD Montr al portait sur un programme de classification de donn e non supervis e Le but du stage tait en collaboration avec les quatre autres stagiaires de continuer l impl mentation de ce programme Mon travail a t dans un premier temps de continuer la partie
53. sse GlpkSolver ne fonctionnait pas correctement En effet il existe un d calage sur les num ros des index des colonnes cr es entre Cplex et Glpk chose qui n est mentionn e nulle part Ainsi les index des colonnes commencent O pour Cplex alors qu ils commencent 1 pour Glpk Ce petit d tail qui rendait ainsi le tableau index obsol te cr ait un d calage entre les colonnes r ellement fournies au programme et celles qui devaient tre Rapport de stage 2009 33 4 2 Impl mentation du solver Classification de donn es non supervis e fournies en th orie Le probl me ma tre ne recevait ainsi pas la bonne solution et le programme ne marchait donc pas correctement Le probl me a cependant t vite r gl une fois ce d tail remarqu 4 2 2 Avec stabilisation La classe GlpkSolverStabilized a elle aussi pos quelques probl mes En effet dans cette classe qui sert faire le lien avec le solver lorsqu on utilise la stabilisation le probl me r soudre et donc transcrire contient beaucoup plus de contraintes que celui non stabilis L initialisation du probl me en est dont d autant plus compliqu e Ainsi en plus de cr er les colonnes et les contraintes de bases savoir pas plus d une colonne par point et pas plus de p clusters au final il faut aussi ajouter pour chaque point les bornes ne pas d passer soit 2 n contraintes suppl mentaires Ces contraintes suppl mentaires se retrouvent auss
54. t laquelle j tais int gr est compos e d l ves ing nieurs de l ISIMA encadr s par trois chercheurs du GERAD sp cialis s en recherche op rationnelle et optimisation Le premier d entre eux est Gilles Caporossi co auteur du logiciel de th orie des graphes AGX co responsable des s minaires du GERAD et professeur HEC Montr al Le second est Pierre Hansen expert entre autres dans les probl mes de localisation tel la P m diane Le troisi me est Sylvain Perron professeur HEC Montr al et d veloppeur d une nouvelle version du logiciel d optimisation quadratique non convexe QP 1 2 Pr sentation du probleme 1 2 1 La classification non supervis e Une part importante du travail d une entreprise est l tude de march En effet avant de concevoir un produit en grande quantit il est toujours bon de savoir si celui ci se vendra bien ou non a quelle population et quelle publicit 4 Rapport de stage 2009 Classification de donn es non supervis e 1 2 Pr sentation du probl me serait la plus ad quate pour ce produit Pour r pondre ces questions les entreprises peuvent tre amen es classer leurs clients potentiels selon par exemple leurs habitudes de consommation Il s agit alors de classification On parle de classification non supervis e si les classes finales de r partition des objets ne sont pas connues par avance et de classification supervis e dans le cas contraire Le projet sur lequel po
55. t la V N S Classification de donn es non supervis e Cette m thode rend vrai si elle a r ussi trouver une partition am liorante par rapport celle qu elle a re ue en param tre et faux sinon Pour choisir au hasard le point dans la liste je me suis servis du g n rateur de nombres pseudo al atoire rand48 Par soucis de simplicit la liste des index est un vecteur de pair contenant l index et un pointeur vers la colonne laquelle il appartient L algorithme de la V N S en elle m me est le suivant init currentpartition Tant que temps lt tempsMax et nbiter lt nbiterMax on fait une descente sur currentpartition si la descentre trouve une partition am liorante on la stock dans bestpartition iter 0 magnitude 0 sinon shake magnitude on stock bestpartition dans currentpartition iter iter 1 magnitude magnitude 1 fin si fin tant que Figure 20 Algorithme de la V N S La m thode shake se contente de bouger magnitude index sans se soucier d une am lioration de la solution et est donc bas e sur le m me principe que la descente avec le test en moins La m thode d initialisation init est celle qui a pos le plus de probl mes Il a en effet fallu trouver une m thode qui donne une solution r alisable donc une partition ou une couverture des points qui ne prend pas trop de temps et qui a une part d al atoire J ai donc impl ment et test plusieurs m thodes Tout d abord j
56. t lt graine lt lt std endl for int k 0 k lt i k lrand48 fff Destructor Example j 2 brief Compute the cost of a column param col The column we want to compute the cost of return The cost of col double evalCost const Column amp col brief Generate columns and add them to the problem param NbCol Number of column to add to the problem return Total number of generated columns uint heuristicCreateColumns uint nbCol brief Generate columns for the master problem param NbCol number of columns you want return Number of created columns uint createColumns uint NbCol brief Launch the exact method param nbCol the number of column wanted 1 return Number of created columns uint exactCreateColumns uint nbCol brief Create a first partition with VNS return Number of created columns always nbObs uint createFirstColumns Figure 10 En t te de la classe Example 16 Rapport de stage 2009 Classification de donn es non supervis e 2 5 Cr ation de classes 2 5 3 Utilisation d une partition Initialement le programme prend en entr e un fichier de points en calcule les dissimilarit s puis lance l heuristique initiale et le reste du programme Une m thode loadFirstPartition permet de lire une partition dans un fichier ce qui permet de tester si la seconde heuristique et la m thode exacte foncti
57. t re M thode heuristique m thode approximative permettant de trouver des colonnes am liorantes pour le probl me Est plus rapide que la m thode exacte Partition une partition de n points en p clusters signifie que chaque point est dans un et un seul cluster Probl me ma tre partie commune tous les crit res elle s occupe de faire le lien entre autre entre le sous probl me les classes de stockage des donn es et les solvers Solver logiciel de r solution de probl mes lin aire tels Cplex ou Glpk Sous probl me partie propre chaque crit re elle s occupe en autre de calculer le co t d une colonne ou de r soudre le probl me de mani re exacte Stabilisation m thode permettant de cibler les solutions recherch es par le programme Stochastique se dit de quelque chose qui n est pas d terministe c est a dire dont on ne peut pr dire le r sultat final qui d pend du hasard Rapport de stage 2009
58. t d j dans le programme J ai ainsi pu v rifier plus facilement si les m thodes des classes pour Glpk taient correctes en les comparant celles des classes pour Cplex 32 Rapport de stage 2009 Classification de donn es non supervis e 4 2 Impl mentation du solver 4 2 impl mentation du solver Pour ajouter au programme la possibilit d utiliser Glpk il m a fallu finir la classe GlpkSolver et cr er les classes G pkSolverStabilized et comme nous l avons vu pr c demment Glpkinterface La pr sence de deux classes distinctes vient du fait que le solver peut tre utilis de deux fa ons avec ou sans stabilisation La stabilisation est une m thode permettant au programme de cibler les recherches effectuer le rendant ainsi th oriquement plus rapide Le choix d utiliser ou non la stabilisation est fait par l utilisateur au moment de lancer le programme Un probl me stabilis contenant plus d informations qu un probl me normal telles des bornes suppl mentaires ne sera pas fourni de la m me mani re au solver et n cessite donc une classe diff rente 4 2 1 Sans stabilisation La classe GlpkSolver avait t d but e par les stagiaires de l an pass e et contenait d j les m thodes les plus importantes savoir celles permettant de r soudre le probl me les m thodes servant ajouter des colonnes au probl me ou encore celle permettant au solver de retourner la solution au programme J ai donc
59. t et est chang la condition d arr t de la boucle tant que en rempla ant le 1 par 10 Cette nouvelle version permet plus de possibilit s d am lioration et semble tre l id e originale L algorithme pens tait donc probablement le suivant i 0 value 1 000 000 tant que i lt 10 cr er les premi res colonnes et les stocker dans la partition courante si la partition courante a un co t inf rieur value la partition courante devient la meilleur partition value re oit le co t de la partition courante fin si i it l fin tant que ajouter la meilleur partition au probleme maitre compl ter la partition Figure 16 Algorithme temporaire de la m thode CreateFirstColumn La valeur 10 a t choisie arbitrairement et d autres valeurs ont aussi t 22 Rapport de stage 2009 Classification de donn es non supervis e 3 1 Modifications du code existant test es Les tests effectu s avec cet algorithme ont donn des r sultats d cevants les temps d ex cution taient doubl s pour des r sultats identiques et ce quelque soit le nombre d essais laiss s On est donc revenu l algorithme de d part dans une criture simplifi e comme suit on cr er les premi res colonnes et les stocker dans la partition courante si la partition courante a un co t inf rieur 1 000 000 la partition courante devient la meilleur partition value re oit le co t de la partition courante fin si ajouter l
60. tDissimilarity ne soit effectu que lorsque les deux points sont pr sents dans la colonne Le nouvel algorithme est le suivant Temp 1 diss 0 Pour chaque pointl si le point1 est dans la colonne pour chaque point2 sup rieur point1 si point2 est dans la colonne diss getDissimilarity point1 point2 si diss gt temp temp diss pointl et point2 forment le diam tre de la colonne fin si fin pour fin pour on met jour le co t de la colonne Figure 14 Nouvel algorithme de la m thode calculDiam De plus l ancien algorithme tait utilis plusieurs endroits dans le code pour calculer le diam tre d une colonne notamment dans la m thode calculant le co t d entr e d un point qui prenait elle aussi du temps J ai donc effectu ce changement dans toute les m thodes o cet algorithme apparaissait et ai lanc des tests pour savoir si on gagnait effectivement du temps ou pas Cette optimisation ainsi que les quelques autres que j ai apport ont chacune contribu acc l rer le programme m me si aucune d entre elle n apporte de changements r ellement significatif 3 1 2 Modification de m thodes En plus d optimiser le code il a aussi fallu effectuer des changements dans certaines m thodes Ainsi la m thode FirstLocalSearch qui est utilis e dans l heuristique doit comme son nom l indique retourner le premier optimum local trouv Or en regardant le code je me suis rendu compte qu elle ne ret
61. un seul cluster Le fait que la partition finale comporte p clusters se traduit par la contrainte 2 et la contrainte 3 signale que les variables y sont binaires 1 2 2 Utilisation du Branch And Bound La r solution d un syst me lin aire en nombre entier tel celui pr sent en figure 1 est relativement difficile La plupart des m thodes utilisent la forme relax e du probl me c est dire permettent des solutions fractionnaires au probl me Ces solutions plus faciles trouv es sont ensuite si cela est possible Rapport de stage 2009 5 1 2 Pr sentation du probl me Classification de donn es non supervis e pass es sous forme enti re La forme relax e du probl me de d part est la suivante min D f C y R teT sous contraintes Y y 4 teT D y p 5 teT y e 0 1 6 Figure 2 probl me relax Les variables y ne sont plus binaires mais continues sur l intervalle 0 1 Une solution envisag e pour r soudre le probl me est une num ration des solutions enti res possibles Cela est r alis l aide d un arbre dont chaque branche repr sente une contrainte et dont les feuilles repr sentent les solutions enti res Cependant pour la majorit des probl mes une telle num rations est impensable car le nombre de solutions possibles est trop lev de l ordre de 2 2 solutions o n repr sente le nombre de points classer Nous introduisons donc une m
62. un sous ensemble de ces solutions On cherche donc la solution optimale d un probl me appel probl me ma tre qui est identique au probl me de d part mais qui contient seulement un nombre limit de colonnes Une fois la solution optimale trouv e un second 6 Rapport de stage 2009 Classification de donn es non supervis e 1 2 Pr sentation du probl me probl me appel sous probl me ou probl me auxiliaire permet de chercher s il existe une ou plusieurs colonnes am liorant la solution du probl me initial et qui n est pas comprise dans le probl me maitre C est donc l algorithme qui r sout le sous probl me qui constitue le g n rateur de colonne La g n ration de colonne fonctionne donc de la mani re suivante tape 1 R solution du probl me ma tre jusqu l optimalit r cup ration des variables duales tape 2 R solution du sous probl me pour trouver une colonne am liorante tape 3 Si aucune colonne n est trouv e fin de l algorithme sinon on ajoute la colonne au probl me ma tre et on recommence l tape 1 Figure 3 La g n ration de colonne La r solution du probl me auxiliaire se fait de la mani re suivante il faut trouver une colonne C ayant un cout r duit n gatif Le co t r duit d une colonne est bas sur le vecteur dual associ au probl me P Le vecteur dual est not u u Ui Un M Le codt r duit est calcul de la mani re su
63. us allons le voir dans la partie suivante j ai t durant mon stage en charge de modifier le programme pour qu il puisse tre utilis avec un autre solver Glpk Il a donc fallu que je modifie la m thode exacte de la somme des diam tres pour que celle ci s adapte dans un premier temps au solver utilis et dans un deuxi me temps qu elle puisse tre utilis e avec Glpk Le code de la m thode exactCreateColumns tait le suivant uint SumDiameter exactCreateColumns uint uint added 0 added exactSol return added Figure 23 Ancien code de la m thode exacte 28 Rapport de stage 2009 Classification de donn es non supervis e 3 3 M thode exacte de r solution du probl me auxiliaire J ai ainsi modifi cette m thode pour qu elle appelle suivant le solver utilis la bonne m thode Pour cela il a fallu que j ajoute un attribut dans les classes concernant les solvers qui permet au sous probl me de savoir quel solver est utilis par le programme chose qui n tait pas possible avant Le nouveau code de la m thode est donc le suivant uint SumDiameter exactCreateColumns uint uint added 0 int solverType getSolverType if solverType solverType 2 added exactSolCplex es if solverType solverType 4 l added exactSolGlpk return added Figure 24 Nouveau code de la m thode exacte La m thode exactSolCplex est l anc

Rapport de stage ISIMA 2ème Année - Soccer-lab

Contents

Download Pdf Manuals

Related Search

Related Contents

Rapport de stage ISIMA 2&egrave;me Ann&eacute;e - Soccer-lab

Contents

Download Pdf Manuals

Related Search

Related Contents

Rapport de stage ISIMA 2ème Année - Soccer-lab