En classification multi-labels graduée (CMLG), chaque instance est associée à un ensemble de labels avec des degrés d’association gradués. Par exemple, une même molécule odorante peut être associée à une odeur forte ‘musquée’, une odeur modérée ‘animale’, et une odeur faible ‘herbacée’. L’objectif est d’apprendre un modèle permettant de prédire l’ensemble gradué de labels associé à une instance à partir de ses variables descriptives. Par exemple, prédire l’ensemble gradué d’odeurs à partir de la masse moléculaire, du nombre de liaisons doubles, et de la structure de la molécule. Un autre domaine intéressant de la CMLG est les systèmes de recommandation. En effet, les appréciations des utilisateurs par rapport à des items (produits, services, livres, films, etc) sont d’abord collectées sous forme de données MLG (l’échelle d’une à cinq étoiles est souvent utilisée). Ces données sont ensuite exploitées pour recommander à chaque utilisateur des items qui ont le plus de chance de l’intéresser. Dans cette thèse, une étude théorique approfondie de la CMLG permet de ressortir les limites des approches existantes, et d’assoir un ensemble de nouvelles approches apportant des améliorations évaluées expérimentalement sur des données réelles. Le cœur des nouvelles approches proposées est l’exploitation des relations entre les labels. Par exemple, une molécule ayant une forte odeur ‘musquée’ émet souvent une odeur faible ou modérée ‘animale’. Cette thèse propose également de nouvelles approches adaptées au cas des molécules odorantes et au cas des gros volumes de données collectées dans le cadre des systèmes de recommandation. / In graded multi-label classification (GMLC), each instance is associated to a set of labels with graded membership degrees. For example, the same odorous molecule may be associated to a strong 'musky' odor, a moderate 'animal' odor, and a weak 'grassy' odor. The goal is to learn a model to predict the graded set of labels associated to an instance from its descriptive variables. For example, predict the graduated set of odors from the molecular weight, the number of double bonds, and the structure of the molecule. Another interesting area of the GMLC is recommendation systems. In fact, users' assessments of items (products, services, books, films, etc.) are first collected in the form of GML data (using the one-to-five star rating). These data are then used to recommend to each user items that are most likely to interest him. In this thesis, an in-depth theoretical study of the GMLC allows to highlight the limits of existing approaches, and to introduce a set of new approaches bringing improvements evaluated experimentally on real data. The main point of the new proposed approaches is the exploitation of relations between labels. For example, a molecule with a strong 'musky' odor often has a weak or moderate 'animal' odor. This thesis also proposes new approaches adapted to the case of odorous molecules and to the case of large volumes of data collected in the context of recommendation systems.