Soutenance de thèse – Vincent Courjault-Radé

Chargement de la carte ....

Date - Heure / Date - Hour
Date(s) - 17/04/2018
10h30 - 12h30

Emplacement / Location
Amphi Bréguet, Bâtiment Bréguet


Ballstering : un algorithme de clustering dédié à de grands échantillons.

Ballstering appartient à la famille des méthodes de machine learning qui ont pour but de regrouper en classes les éléments formant la base de données étudiée et ce sans connaissance au préalable des classes qu’elle contient. Ce type de méthodes, dont le représentant le plus connu est k-means, se rassemblent sous le terme de « partitionnement de données » ou « clustering ». Récemment un algorithme de partitionnement « Fast Density Peak Clustering » (FDPC) paru dans le journal Science a suscité un intérêt certain au sein de la communauté scientifique pour son aspect innovant et son efficacité sur des données distribuées en groupes non-concentriques. Seulement cet algorithme présente une complexité telle qu’il ne peut être aisément appliqué à des données volumineuses. De plus nous avons pu identifier plusieurs faiblesses pouvant nuire très fortement à la qualité de ses résultats, dont en particulier la présence d’un paramètre général dc difficile à choisir et ayant malheureusement un impact non négligeable. Compte tenu de ces limites, nous avons repris l’idée principale de FDPC sous un nouvel angle puis apporté successivement des modifications en vue d’améliorer ses points faibles. Modifications sur modifications ont finalement donné naissance à un algorithme bien distinct que nous avons nommé Ballstering.
Le fruit de ces 3 années de thèse se résume principalement en la conception de ce dernier, un algorithme de partitionnement dérivé de FDPC spécialement conçu pour être efficient sur de grands volumes de données. Tout comme son précurseur, Ballstering fonctionne en deux phases: une phase d’estimation de densité suivie d’une phase de partitionnement. Son élaboration est principalement fondée sur la construction d’une sous-procédure permettant d’effectuer la première phase de FDPC avec une complexité nettement amoindrie tout évitant le choix de dc qui devient dynamique, déterminé suivant la densité locale. Nous appelons ICMDW cette sous-procédure qui représente une partie conséquente de nos contributions. Nous avons également remanié certaines des définitions au cœur de FDPC et revu entièrement la phase 2 en s’appuyant sur la structure arborescente des résultats fournis par ICDMW pour finalement produire un algorithme outrepassant toutes les limitations que nous avons identifié chez FDPC.

Vincent Courjault-Radé, ENAC, DEVI, Toulouse.