Soient D (les données) et M (les modules) deux ensemble de relations binaires sur un ensemble fini d'objets X. le but de cette thèse est l'étude, d'un point de vue axiomatiques, des (D,M)-procédures (ou multiprocédures) c'est à dire des applications qui à tout sous-ensemble fini de D associent un (ou plusieurs) élément de M. La première partie contient la caractérisation axiomatique des procédures et multiprocédures qui ne dépendent que des matrices de préférences ainsi que la caractérisation de ces matrices pour différents ensemble de données. La seconde partie est une étude d'une classe de multiprocédures qui généralisent la notion de fonction de choix. Enfin, dans la troisème partie, sont développées les notions de procédures et de multiprocédures prudentes ainsi que les variantes séquentielles de la procédure de Borda.

Le décideur en entreprise, lors de la prise d'une décision, se trouve généralement en face de la situation suivante : il dispose d'un ensemble d'alternatives qui sont des combinaisons de variables d'action ; et il lui est demandé d'atteindre un certain nombre d'objectifs qui sont caractérisés par un nombre plus ou moins élevé d'indicateurs de performance. Ces objectifs couvrent l'ensemble des relations de l'entreprise avec les différentes parties bénéficiaires des résultats de ses activités et avec lesquelles elle interagit. L'objet des indicateurs de performance est de mesurer la réussite de l'entreprise à répondre aux attentes et besoins de ces parties : clients, actionnaires, personnel, collectivité... et à ses propres attentes. <br />Le décideur a besoin d'évaluer chacune des alternatives selon chacun des critères de choix retenus et qui représentent les objectifs à atteindre, et d'évaluer globalement chacune de ces alternatives selon l'ensemble des critères. <br />Ce travail se place dans le contexte d'aide à la décision managériale de haut niveau où les actions sont des projets potentiels de développement des activités de l'entreprise. L'approche proposée, désignée par SimulValor, utilise la dynamique des systèmes pour modéliser et simuler les alternatives d'action et en évaluer les performances ; et elle utilise la théorie de l'utilité pour l'agrégation de ces performances. <br />En résumé, l'approche SimulValor vise l'évaluation de différentes alternatives d'action concernant la configuration des activités de l'entreprise en simulant les flux de valeurs qui lient les actions aux performances et les performances aux valeurs générées aux parties bénéficiaires. La difficulté principale de la méthode est l'extraction, l'harmonisation et la quantification des données qualitatives qui caractérisent les liens d'influences (et surtout les fonctions d'utilité) existants entre les éléments modélisés.

Le travail de thèse a porté sur une réflexion relative aux méthodes de classification automatique des données pour lesquelles il est bien connu qu'un effet « méthode » existe. Après une première partie qui présente la problématique générale de l'analyse des données et propose un survey des méthodes de classification, les travaux originaux de la thèse sont exposés. Ils relèvent de trois approches interconnectées : une approche basée sur l'agrégation d'opinions, une approche prétopologique et une approche basée sur l'agrégation des préférences. Chacune de ces approches se fonde sur un paradigme différent et propose une nouvelle vision des techniques de classification permettant d'apporter éventuellement de l'information exogène dans la méthode.

Dans cette thèse, nous considérons l'étude et la mise en \oe uvre de différentes approches numériques de résolution de problèmes dits d'approximation linéaire conique, en nous concentrant sur les approches par projections et par optimisation sous contraintes de semi-définie positivité. Un problème d'approximation matricielle consiste dans un espace normé de matrices à chercher la matrice ayant une certaine propriété $\mathcal(P)$, la plus proche au sens de la norme de l'espace, d'une matrice $A$ donnée. Ces problèmes apparaissent dans différents domaines, et ont été étudiés par \textsc(Higham) qui en propose un procédure de résolution consistant en les trois points suivants : existence et unicité des solutions, caractérisation et solution explicite éventuelles, algorithmes efficaces de calculs de ces solutions. Nous nous plaçons dans un cadre euclidien, et considérons les cas où les matrices vérifiant la propriété $\mathcal(P)$ forment un ensemble convexe déterminé par des contraintes affines et coniques. Nous parlons alors d'(\it approximation matricielle linéaire conique). Nous prenons comme exemples d'application deux problèmes d'approximation correspondant à des ensembles connus en Analyse convexe pour leur "bonne" structure, mais pour lesquels la résolution explicite d'un problème d'approximation s'avère ardu. Le premier exemple provient d'applications en Recherche opérationnelle ou en Mécanique quantique, et consiste à trouver la matrice bistochastique la plus proche d'une matrice donnée. Le second problème est celui de la calibration de matrices de corrélation, qui est d'une importance majeure en analyse du risque financier encouru avec un choix de portefeuille d'actions boursières donné. Nous étudions et mettons en \oe uvre pour les problèmes d'approximation matricielle linéaire conique deux approches de nature différente. La première est primale : elle consiste à interpréter le problème comme étant celui de la projection sur un convexe qui est l'intersection de convexes plus simples sur lesquels les projections sont faciles. Cela nous permet de proposer un algorithme de projections alternées, inspiré des modifications apportées par \textsc(Boyle et Dykstra) à l'algorithme classique de Von Neumann. La seconde est de type primal-dual, et s'inscrit dans la lignée des récentes avancées obtenues en optimisation sous contraintes de semi-définie positivité ((\it Semidefinite Programming)). Elle consiste en la mise en \oe uvre d'un algorithme de points intérieurs, en utilisant une démarche novatrice consistant en l'utilisation de directions de recherches de Gauss-Newton, obtenues par gradients conjugués et en l'introduction en fin d'algorithme d'une étape de "crossover" permettant d'obtenir asymptotiquement de la convergence superlinéaire. Nous présentons pour chacun des problèmes d'approximation pris en exemples des résultats numériques illustrant les différentes approches ci-dessus et les comparant entre elles de différents points de vue. En application, nous proposons aussi une généralisation de la procédure d'agrégation de préférences de \textsc(Blin) en utilisant l'approximation par matrices bistochastiques.

No description available.

L'agrégation de classements consiste à établir un consensus entre un ensemble de classements (éléments ordonnés). Bien que ce problème ait de très nombreuses applications (consensus entre les votes d'utilisateurs, consensus entre des résultats ordonnés différemment par divers moteurs de recherche...), calculer un consensus exact est rarement faisable dans les cas d'applications réels (problème NP-difficile). De nombreux algorithmes d'approximation et heuristiques ont donc été conçus. Néanmoins, leurs performances (en temps et en qualité de résultat produit) sont très différentes et dépendent des jeux de données à agréger. Plusieurs études ont cherché à comparer ces algorithmes mais celles-ci n’ont généralement pas considéré le cas (pourtant courant dans les jeux de données réels) des égalités entre éléments dans les classements (éléments classés au même rang). Choisir un algorithme de consensus adéquat vis-à-vis d'un jeu de données est donc un problème particulièrement important à étudier (grand nombre d’applications) et c’est un problème ouvert au sens où aucune des études existantes ne permet d’y répondre. Plus formellement, un consensus de classements est un classement qui minimise le somme des distances entre ce consensus et chacun des classements en entrés. Nous avons considérés (comme une grande partie de l’état-de-art) la distance de Kendall-Tau généralisée, ainsi que des variantes, dans nos études. Plus précisément, cette thèse comporte trois contributions. Premièrement, nous proposons de nouveaux résultats de complexité associés aux cas que l'on rencontre dans les données réelles où les classements peuvent être incomplets et où plusieurs éléments peuvent être classés à égalité. Nous isolons les différents « paramètres » qui peuvent expliquer les variations au niveau des résultats produits par les algorithmes d’agrégation (par exemple, utilisation de la distance de Kendall-Tau généralisée ou de variantes, d’un pré-traitement des jeux de données par unification ou projection). Nous proposons un guide pour caractériser le contexte et le besoin d’un utilisateur afin de le guider dans le choix à la fois d’un pré-traitement de ses données mais aussi de la distance à choisir pour calculer le consensus. Nous proposons finalement une adaptation des algorithmes existants à ce nouveau contexte. Deuxièmement, nous évaluons ces algorithmes sur un ensemble important et varié de jeux de données à la fois réels et synthétiques reproduisant des caractéristiques réelles telles que similarité entre classements, la présence d'égalités, et différents pré-traitements. Cette large évaluation passe par la proposition d’une nouvelle méthode pour générer des données synthétiques avec similarités basée sur une modélisation en chaîne Markovienne. Cette évaluation a permis d'isoler les caractéristiques des jeux de données ayant un impact sur les performances des algorithmes d'agrégation et de concevoir un guide pour caractériser le besoin d'un utilisateur et le conseiller dans le choix de l'algorithme à privilégier. Une plateforme web permettant de reproduire et étendre ces analyses effectuée est disponible (rank-aggregation-with-ties.lri.fr). Enfin, nous démontrons l'intérêt d'utiliser l'approche d'agrégation de classements dans deux cas d'utilisation. Nous proposons un outil reformulant à-la-volé des requêtes textuelles d'utilisateur grâce à des terminologies biomédicales, pour ensuite interroger de bases de données biologiques, et finalement produire un consensus des résultats obtenus pour chaque reformulation (conqur-bio.lri.fr). Nous comparons l'outil à la plateforme de références et montrons une amélioration nette des résultats en qualité. Nous calculons aussi des consensus entre liste de workflows établie par des experts dans le contexte de la similarité entre workflows scientifiques. Nous observons que les consensus calculés sont très en accord avec les utilisateurs dans une large proportion de cas. / The rank aggregation problem is to build consensus among a set of rankings (ordered elements). Although this problem has numerous applications (consensus among user votes, consensus between results ordered differently by different search engines ...), computing an optimal consensus is rarely feasible in cases of real applications (problem NP-Hard). Many approximation algorithms and heuristics were therefore designed. However, their performance (time and quality of product loss) are quite different and depend on the datasets to be aggregated. Several studies have compared these algorithms but they have generally not considered the case (yet common in real datasets) that elements can be tied in rankings (elements at the same rank). Choosing a consensus algorithm for a given dataset is therefore a particularly important issue to be studied (many applications) and it is an open problem in the sense that none of the existing studies address it. More formally, a consensus ranking is a ranking that minimizes the sum of the distances between this consensus and the input rankings. Like much of the state-of-art, we have considered in our studies the generalized Kendall-Tau distance, and variants. Specifically, this thesis has three contributions. First, we propose new complexity results associated with cases encountered in the actual data that rankings may be incomplete and where multiple items can be classified equally (ties). We isolate the different "features" that can explain variations in the results produced by the aggregation algorithms (for example, using the generalized distance of Kendall-Tau or variants, pre-processing the datasets with unification or projection). We propose a guide to characterize the context and the need of a user to guide him into the choice of both a pre-treatment of its datasets but also the distance to choose to calculate the consensus. We finally adapt existing algorithms to this new context. Second, we evaluate these algorithms on a large and varied set of datasets both real and synthetic reproducing actual features such as similarity between rankings, the presence of ties and different pre-treatments. This large evaluation comes with the proposal of a new method to generate synthetic data with similarities based on a Markov chain modeling. This evaluation led to the isolation of datasets features that impact the performance of the aggregation algorithms, and to design a guide to characterize the needs of a user and advise him in the choice of the algorithm to be use. A web platform to replicate and extend these analyzes is available (rank-aggregation-with-ties.lri.fr). Finally, we demonstrate the value of using the rankings aggregation approach in two use cases. We provide a tool to reformulating the text user queries through biomedical terminologies, to then query biological databases, and ultimately produce a consensus of results obtained for each reformulation (conqur-bio.lri.fr). We compare the results to the references platform and show a clear improvement in quality results. We also calculate consensus between list of workflows established by experts in the context of similarity between scientific workflows. We note that the computed consensus agree with the expert in a very large majority of cases.