Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

Cet article présente Fed-$k^*$-HC, un cadre novateur de clustering fédéré hiérarchique capable de déterminer automatiquement le nombre optimal de clusters en agrégeant des micro-sous-ensembles générés localement via une fusion hiérarchique basée sur la densité, surmontant ainsi les défis liés à l'inconnu du nombre de clusters, aux tailles déséquilibrées et aux contraintes de confidentialité.

L'essentiel

Imaginez que vous êtes un chef cuisinier (le Serveur) qui doit organiser une grande fête, mais vous ne pouvez pas voir les ingrédients que les invités (les Clients) ont dans leurs paniers. Chaque invité a apporté des fruits, des légumes ou des épices, mais vous ne savez pas exactement ce qu'il y a dedans pour des raisons de confidentialité (c'est le principe du Federated Learning).

Le Problème : Le Chaos des Paniers

Dans le monde réel, les données ne sont pas toujours équitables :

1. Déséquilibre : Certains paniers sont remplis à ras bord de pommes, tandis que d'autres n'ont que quelques cerises.
2. Inconnu : Personne ne sait combien de types de fruits différents il y a au total. Est-ce qu'il y a 3 types de fruits ou 10 ?
3. Confidentialité : Les invités ne veulent pas vous montrer leurs paniers, ils ont peur que vous voliez leurs recettes secrètes.

Les anciennes méthodes de tri avaient deux gros défauts :

• Elles forçaient tout le monde à avoir le même nombre de fruits (ce qui est faux).
• Elles exigeaient que vous sachiez à l'avance combien de types de fruits il y avait (ce qui est souvent impossible).

La Solution : Fed-k∗-HC (Le Tri Intelligent)

Les auteurs proposent une nouvelle méthode, Fed-k∗-HC, qui fonctionne comme un jeu de construction en deux étapes :

Étape 1 : Les Invités font leurs propres petits tas (Côté Client)

Au lieu de vous envoyer tout leur panier en vrac, chaque invité fait un premier tri chez lui.

• L'analogie : Imaginez que chaque invité prend ses fruits et les regroupe en micro-tas très précis. S'il a 100 pommes, il ne les met pas en un seul gros tas, mais en 10 petits tas de 10 pommes chacun.
• La magie : Il ne vous envoie pas les fruits réels (pour la confidentialité). À la place, il vous envoie une "photo statistique" de chaque petit tas (par exemple : "Ce tas ressemble à des pommes rouges, moyennes et rondes"). C'est comme envoyer une carte d'identité du fruit sans envoyer le fruit lui-même.

Étape 2 : Le Chef assemble les pièces du puzzle (Côté Serveur)

Vous recevez des centaines de ces "photos de micro-tas" de tous les invités.

• Le tri automatique : Au lieu de deviner le nombre de fruits, vous commencez à rapprocher les micro-tas qui se ressemblent le plus. C'est comme si vous colliez des aimants ensemble.
• La détection du nombre : Vous continuez à coller les tas ensemble jusqu'à ce qu'il ne reste plus que des groupes distincts qui ne veulent plus se mélanger. À ce moment précis, vous savez : "Ah ! Il y a exactement 5 types de fruits différents !" (C'est le $k^*$ automatique).
• Le résultat final : Vous avez maintenant une carte complète de la fête avec tous les types de fruits, même ceux qui étaient rares (les cerises), sans jamais avoir vu les paniers originaux.

Pourquoi est-ce génial ? (Les Avantages)

1. Pas de "Effet Uniforme" : Les anciennes méthodes avaient tendance à écraser les petits groupes (les cerises) pour les égaliser avec les gros (les pommes). Cette méthode, en commençant par des micro-tas, protège les minorités. C'est comme si vous ne laissiez pas les gros tas de pommes avaler les cerises.
2. Zéro Devinettes : Vous n'avez plus besoin de dire "Je pense qu'il y a 3 fruits". Le système trouve le bon nombre tout seul en regardant comment les tas se connectent.
3. Confiance Totale : Comme les invités ne vous envoient que des statistiques synthétiques (des "photos"), leurs données réelles restent chez eux. C'est comme envoyer un résumé de votre recette sans révéler la marque exacte de vos épices.

En Résumé

Fed-k∗-HC est une méthode intelligente qui permet de trier des données dispersées et déséquilibrées en respectant la vie privée. Au lieu de forcer un modèle rigide, elle laisse les données se "retrouver" naturellement, comme des gouttes d'eau qui forment des rivières, pour révéler la structure réelle du monde sans jamais briser le secret des données.

C'est un peu comme organiser une bibliothèque mondiale où chaque libraire envoie juste une description de ses livres les plus rares, et où vous assemblez ces descriptions pour découvrir, sans jamais ouvrir les livres, exactement combien de genres littéraires existent réellement.

Résumé technique

1. Problématique

Le Clustering Fédéré (FC) est une approche prometteuse pour découvrir des modèles de distribution de données à partir de données distribuées et privées sans supervision. Cependant, les méthodes existantes souffrent de limitations majeures qui les rendent peu adaptées aux scénarios réels :

• Hypothèses irréalistes : La plupart des méthodes supposent que le nombre de clusters est connu à l'avance et que les clusters sont de taille uniforme. En réalité, le nombre de clusters est souvent inconnu et les distributions de données sont naturellement déséquilibrées (certaines classes sont beaucoup plus fréquentes que d'autres).
• Effet d'uniformité (« Uniform Effect ») : Les algorithmes de partitionnement classiques (comme le k-moyennes fédéré) tendent à forcer une répartition égale des échantillons, ce qui échoue à capturer les petits clusters minoritaires dans des données déséquilibrées.
• Contraintes de confidentialité : L'apprentissage fédéré interdit l'envoi de données brutes vers le serveur. Les méthodes actuelles qui envoient des statistiques simples (centroïdes) perdent souvent la structure fine des données, tandis que les méthodes cryptées sont trop coûteuses en calcul.
• Manque d'adaptabilité : Peu de méthodes peuvent déterminer automatiquement le nombre optimal de clusters ($k^*$) dans un cadre fédéré, en particulier avec une communication en un seul tour (one-shot).

2. Méthodologie : Fed-k*-HC

Les auteurs proposent un nouveau cadre nommé Fed-k-HC*, qui combine un partitionnement micro-local et une fusion hiérarchique globale pour résoudre ces problèmes. L'approche se déroule en deux phases principales :

A. Partitionnement Micro-Automatisé côté Client (Client-Side Automated Micro-Partitioning)

Au lieu d'envoyer des données brutes ou un nombre fixe de clusters, chaque client partitionne ses données locales en de nombreux micro-sous-clusters fins.

• Algorithme SNP (Selection of Number of Prototypes) : Une méthode d'apprentissage compétitif est utilisée pour diviser les données en sous-clusters de tailles similaires, indépendamment de la distribution globale. Cela permet de capturer la structure locale fine sans biais.
• Préservation de la vie privée : Pour éviter d'envoyer les données réelles, le client génère des données synthétiques de remplacement basées sur une distribution normale multivariée. Ces données sont générées à partir des statistiques locales (moyenne, covariance, rayon, nombre d'échantillons) de chaque micro-sous-cluster.
• Résultat : Le serveur reçoit des données synthétiques qui approximent fidèlement la distribution globale sans révéler les échantillons individuels.

B. Fusion Hiérarchique côté Serveur (Server-Side Hierarchical Merging)

Le serveur agrège les sous-clusters de tous les clients pour reconstruire la distribution globale et déterminer $k^*$.

• Détermination automatique de $k^*$ (Algorithme SNC) :
  • Le serveur utilise une méthode basée sur les voisins naturels (Natural Neighbors).
  • Une distinction est faite entre les « voisins naturels lâches » (Loose Natural Neighbors - LNN) et les « voisins naturels stricts » (Strict Natural Neighbors - SNN). Les SNN imposent une contrainte de réciprocité stricte (les points doivent être mutuellement voisins), ce qui réduit les erreurs de connexion entre clusters de densités différentes (problème majeur des données déséquilibrées).
  • L'algorithme identifie le nombre de composantes connexes dans le graphe de voisinage pour estimer automatiquement le nombre optimal de clusters $k^*$.
• Fusion Hiérarchique :
  • Une fois $k^*$ déterminé, le serveur fusionne itérativement les sous-clusters les plus similaires.
  • Une nouvelle métrique de distance est proposée, combinant la distance entre les centroïdes, le degré de chevauchement des clusters et la similarité de leurs écarts-types.
  • Ce processus de fusion ascendante (bottom-up) évite l'effet d'uniformité en permettant aux petits clusters de rester distincts jusqu'à ce que leur fusion soit justifiée par la densité locale.

3. Contributions Clés

1. Nouveau paradigme de clustering fédéré : Le papier adresse le problème sous-estimé du clustering fédéré sur des données déséquilibrées avec un nombre de clusters inconnu, fournissant une base pour la recherche future.
2. Mécanisme de partitionnement fin et fusion hiérarchique : La stratégie de division locale en micro-sous-clusters suivie d'une fusion hiérarchique sur le serveur permet de mieux gérer les distributions complexes et déséquilibrées que les méthodes de partitionnement classiques.
3. Détermination automatique de $k^*$ en contexte fédéré : Contrairement aux méthodes existantes qui nécessitent un $k$ prédefini, Fed-k*-HC détermine automatiquement le nombre de clusters optimal ($k^*$) en exploitant les relations de voisinage des prototypes, éliminant ainsi les hypothèses restrictives sur la distribution des données.
4. Protection de la vie privée efficace : L'utilisation de données synthétiques générées à partir de statistiques locales permet une communication en un seul tour (one-shot) tout en préservant la confidentialité des données brutes.

4. Résultats Expérimentaux

Les auteurs ont évalué Fed-k*-HC sur plusieurs jeux de données (réels et synthétiques), y compris des scénarios IID et Non-IID, ainsi que des distributions équilibrées et déséquilibrées.

• Performance supérieure : Sur des jeux de données déséquilibrés (ex: yeast, abalone, ids2), Fed-k*-HC surpasse systématiquement les méthodes de l'état de l'art (KFed, MUFC, F3KM, Orchestra) en termes de F-mesure, de NMI, d'ARI et d'exactitude.
• Gestion des données Non-IID : Dans des scénarios où les clients ne possèdent qu'un sous-ensemble de clusters (absence de certains clusters sur certains nœuds), la méthode proposée maintient une performance élevée, surpassant les approches itératives et les méthodes basées sur k-moyennes.
• Précision de $k^*$ : L'algorithme SNC parvient à estimer le nombre de clusters très proche de la vérité terrain ($K$) sur la majorité des jeux de données, même sans information préalable.
• Efficacité computationnelle : L'approche one-shot réduit considérablement le temps de communication par rapport aux méthodes itératives. La complexité temporelle augmente de manière linéaire avec la taille des données et le nombre de clients, démontrant une bonne évolutivité.

5. Signification et Impact

Ce travail est significatif car il comble un fossé important entre les méthodes théoriques de clustering fédéré et les réalités des environnements de données distribués complexes.

• Résolution du compromis Sécurité-Information : En utilisant des données synthétiques basées sur des statistiques locales et une fusion hiérarchique, la méthode contourne le compromis habituel entre la protection de la vie privée et la richesse de l'information nécessaire au clustering.
• Robustesse face au déséquilibre : La capacité à détecter des clusters minoritaires sans les noyer dans des clusters majoritaires (évitant l'« effet d'uniformité ») est cruciale pour des applications réelles comme la détection de fraudes, le diagnostic médical ou l'analyse de comportements utilisateurs rares.
• Automatisation : L'élimination de la nécessité de préconfigurer le nombre de clusters rend le système plus autonome et adaptable à des environnements dynamiques où la structure des données peut changer.

En conclusion, Fed-k-HC* représente une avancée majeure pour le clustering fédéré, offrant une solution robuste, privée et automatique pour l'analyse de données hétérogènes et déséquilibrées.