Skip to Main content Skip to Navigation
Theses

Ballstering: un algorithme de clustering dédié à de grands échantillon

Résumé : 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.
Complete list of metadatas

Cited literature [77 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/tel-01883743
Contributor : Vincent Courjault-Radé <>
Submitted on : Friday, September 28, 2018 - 3:48:44 PM
Last modification on : Tuesday, July 28, 2020 - 4:58:02 PM

File

Thèse.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01883743, version 1

Collections

Citation

Vincent Courjault-Rade. Ballstering: un algorithme de clustering dédié à de grands échantillon. Statistiques [stat]. UPS Toulouse - Université Toulouse 3 Paul Sabatier, 2018. Français. ⟨tel-01883743⟩

Share

Metrics

Record views

158

Files downloads

349