La classification est un des nombreux domaines de la Fouille de Données qui vise à extraire l'information à partir de grands volumes de données en utilisant différentes techniques computationnelles de l'apprentissage, des statistiques et de la reconnaissance des formes. Une des deux approches fondamentales de la classification non supervisé (ou clustering) est la classification hiérarchique. Son but est de produire un arbre dans lequel les nœuds représentent des classes des objets analysés. Un des inconvénients principaux de la méthode ascendante hiérarchique la plus connue et la plus utilisée, la Classification Ascendante Hiérarchique (CAH), est le fait qu'on ne peut pas mettre en évidence des classes d'objets ayant des caractéristiques communes. Cette propriété se trouve par exemple dans les classes qui se recouvrent et qui ont été introduites et étudies dans les extensions de la CAH.<br /><br />Cette thèse porte sur une extension récente de la Classification Ascendante Hiérarchique, appelée Classification Ascendante 2-3 Hiérarchique et proposé par P. Bertrand en 2002, avec en vue son application au domaine de la Fouille de Données.<br />Les trois contributions majeures de cette thèse résident dans l'étude théorique des 2-3 hiérarchies (appelées aussi paired hierarchies), dans le nouvel algorithme de 2-3 CAH avec son implémentation et dans la première étude applicative de cette méthode dans deux domaines de la Fouille de Données.<br /><br />Notre étude théorique inclut la découverte de quatre nouvelles propriétés théoriques des 2-3 hiérarchies et les définitions des liens d'agrégation entre les classes pour ce type de structure. Ceci nous a aussi permis de mettre en évidence un cas spécial de fusion des classes et d'introduire une étape intermédiaire dans la construction des 2-3 hiérarchies. L'étude exhaustive et systématique des cas possibles nous a permis de formuler les meilleurs choix concernant le lien d'agrégation et l'indexation de la structure, avec en vue l'amélioration de la qualité des 2-3 hiérarchies.<br /><br />Dans un deuxième temps, basé sur notre étude et contributions théoriques, nous proposons un nouvel algorithme général de Classification Ascendante 2-3 Hiérarchique. Ceci représente la concrétisation de notre travail précédent, aboutissant à un algorithme performant, qui explore plusieurs possibilités du modèle 2-3 hiérarchique. Une analyse théorique de la complexité de notre algorithme a montré que la complexité a été réduite de O(n3) dans l'algorithme initial de 2-3 CAH à O(n2 log n) pour notre algorithme. Les comparaisons des 2-3 hiérarchies avec les hiérarchies classiques obtenues sur différents ensembles de données (réels et simulés), ont validé l'analyse de complexité par les temps d'exécution. En plus, des résultats très satisfaisants ont été obtenus en analysant la "qualité" des 2-3 hiérarchies comparées aux hiérarchies classiques : jusqu'au 50% de classes en plus et un gain maximum de 84% en utilisant l'indice de Stress.<br />Nous avons ensuite proposé un modèle orienté-objet de notre algorithme de 2-3 CAH, qui a été intégré dans une boite à outils ``Hierarchical Clustering Toolbox'' (HCT) que nous avons développée pour la visualisation des méthodes ascendantes hiérarchiques de classification. Ce modèle a été également intégré comme méthode d'indexation des cas dans la plateforme de Raisonnement à Partir de Cas (RàPC), CBR*Tools, développé à l'INRIA Sophia Antipolis, et utilisé pour la conception des systèmes de recommandations. <br /><br />Notre dernière contribution concerne une toute première étude de l'utilisation de notre algorithme de 2-3 CAH sur des données réelles relevant de deux domaines de la Fouille des Données : le Web Mining et la Classification de Documents XML. Celle-ci a donné lieu à des résultats intéressants et portait sur la comparaison de la classification 2-3 hiérarchique des équipes de recherche de l'INRIA en utilisant soit le comportement des utilisateurs sur leur sites Web, soit leur rapport annuel d'activité écrit en XML, par rapport à la structure organisationnelle existante en thèmes de recherche.<br /><br />Pour conclure, nous montrons que ce sujet est loin d'être épuisé et nous proposons plusieurs pistes de recherche future relatives à la Classification Ascendante 2-3 Hiérarchique ainsi qu'à notre boite à outils HCT, développée pendant cette thèse.

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.