MMD and Ward criterion in a RKHS : application to Kernel based hierarchical agglomerative clustering / Na Li ; sous la direction de Nicolas Lefebvre et de Régis Lengellé

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Classification automatique (statistique)

Reconnaissance des formes (informatique)

Apprentissage automatique

Tests d'hypothèses (statistique)

Classification Dewey : 620.004 52

Lefebvre, Nicolas (1977-....) (Directeur de thèse / thesis advisor)

Lengellé, Régis (19..-....) (Directeur de thèse / thesis advisor)

Université de technologie (Troyes ; 1994-....) (Organisme de soutenance / degree-grantor)

Ecole doctorale Sciences pour l'Ingénieur (Troyes, Aube) (Ecole doctorale associée à la thèse / doctoral school)

Résumé / Abstract : La classification non supervisée consiste à regrouper des objets afin de former des groupes homogènes au sens d’une mesure de similitude. C’est un outil utile pour explorer la structure d’un ensemble de données non étiquetées. Par ailleurs, les méthodes à noyau, introduites initialement dans le cadre supervisé, ont démontré leur intérêt par leur capacité à réaliser des traitements non linéaires des données en limitant la complexité algorithmique. En effet, elles permettent de transformer un problème non linéaire en un problème linéaire dans un espace de plus grande dimension. Dans ce travail, nous proposons un algorithme de classification hiérarchique ascendante utilisant le formalisme des méthodes à noyau. Nous avons tout d’abord recherché des mesures de similitude entre des distributions de probabilité aisément calculables à l’aide de noyaux. Parmi celles-ci, la maximum mean discrepancy a retenu notre attention. Afin de pallier les limites inhérentes à son usage, nous avons proposé une modification qui conduit au critère de Ward, bien connu en classification hiérarchique. Nous avons enfin proposé un algorithme itératif de clustering reposant sur la classification hiérarchique à noyau et permettant d’optimiser le noyau et de déterminer le nombre de classes en présence

Résumé / Abstract : Clustering, as a useful tool for unsupervised classification, is the task of grouping objects according to some measured or perceived characteristics of them and it has owned great success in exploring the hidden structure of unlabeled data sets. Kernel-based clustering algorithms have shown great prominence. They provide competitive performance compared with conventional methods owing to their ability of transforming nonlinear problem into linear ones in a higher dimensional feature space. In this work, we propose a Kernel-based Hierarchical Agglomerative Clustering algorithms (KHAC) using Ward’s criterion. Our method is induced by a recently arisen criterion called Maximum Mean Discrepancy (MMD). This criterion has firstly been proposed to measure difference between different distributions and can easily be embedded into a RKHS. Close relationships have been proved between MMD and Ward's criterion. In our KHAC method, selection of the kernel parameter and determination of the number of clusters have been studied, which provide satisfactory performance. Finally an iterative KHAC algorithm is proposed which aims at determining the optimal kernel parameter, giving a meaningful number of clusters and partitioning the data set automatically