Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

Il paper propone Fed-$k^*$-HC, un nuovo framework di clustering federato gerarchico che determina automaticamente il numero ottimale di cluster aggregando prototipi locali su un server e utilizzando un processo di fusione basato sulla densità per adattarsi a distribuzioni di dati non bilanciate e sconosciute, superando i limiti dei metodi esistenti che presuppongono un numero fisso di cluster.

L'essenziale

Immagina di essere un detective che deve organizzare una grande festa, ma c'è un problema: non puoi vedere gli ospiti.

Gli ospiti sono sparsi in diverse case (i "clienti") e non possono uscire di casa per paura di farsi rubare l'identità (la privacy). Tu sei il capo detective (il "server") e devi capire quanti gruppi di amici ci sono alla festa e chi appartiene a quale gruppo, senza mai entrare nelle case degli ospiti.

Ecco come funziona il nuovo metodo descritto in questo articolo, chiamato Fed-k*-HC, spiegato in modo semplice:

1. Il Problema: La Festa Sbagliata

Fino ad ora, i detective (gli algoritmi di clustering federato) facevano un errore di base:

• Assumevano che tutti i gruppi fossero della stessa grandezza. Immagina di pensare che ci siano 5 gruppi di 20 persone ciascuno. Ma nella realtà, un gruppo potrebbe essere una folla di 500 persone, mentre un altro è solo una coppia di amici.
• Non sapevano quanti gruppi ci fossero. Dovevano indovinare il numero prima di iniziare.
• Perdevano i gruppi piccoli. Se c'era un gruppo di sole 3 persone, l'algoritmo tendeva a ignorarli e a mescolarli con i gruppi grandi, perché cercava di rendere tutto "uguale".

2. La Soluzione: Il Metodo "Fed-k*-HC"

I ricercatori hanno inventato un nuovo modo per risolvere il mistero senza violare la privacy. Immagina questo processo in tre fasi:

Fase 1: I Micro-Gruppi (La Preparazione)

Invece di chiedere agli ospiti di uscire, chiedi a ogni casa di fare un piccolo lavoro interno.

• Ogni ospite divide i suoi vicini in piccolissimi gruppi (micro-sottogruppi).
• Non mandano le foto degli ospiti (i dati grezzi), ma creano un fantasma statistico. Immagina di creare un "manichino" che rappresenta la media di quel gruppo: dice "qui ci sono 10 persone, sono alte in media 170cm e piacciono al calcio".
• Questo manichino è un dato sintetico. Non rivela chi sono le persone reali, ma dice al detective come è fatto il gruppo.

Fase 2: L'Incontro dei Manichini (Il Server)

Tutti i manichini arrivano al tuo ufficio (il server).

• Qui non hai ancora un numero fisso di gruppi.
• Il tuo compito è guardare questi manichini e chiederti: "Chi assomiglia a chi?".
• Usano una tecnica intelligente chiamata Clustering Gerarchico. Immagina di avere tanti piccoli cerchi di persone. Invece di forzare tutto in 5 cerchi grandi, inizi a unire i cerchi più vicini tra loro, uno alla volta.

Fase 3: La Magia dell'Auto-Scoperta (Il Numero Perfetto)

Questa è la parte geniale. Non devi dire al detective quanti gruppi ci sono.

• Il sistema unisce i cerchi finché non vede che i cerchi rimanenti sono troppo lontani tra loro per essere amici.
• È come se stessi unendo gruppi di amici: "Ok, questi due gruppi si parlano, uniamoli. E questi altri? Sì, anche loro. Ma questo gruppo là in fondo? È troppo diverso, lasciamolo separato".
• Il sistema si ferma da solo quando ha trovato il numero perfetto di gruppi ($k^*$), anche se alcuni gruppi sono enormi e altri minuscoli.

Perché è così speciale? (Le Analogie)

• Niente più "Effetto Uniforme": I vecchi metodi erano come un sarto che taglia tutti i vestiti della stessa taglia (M). Se c'era un gigante e un nano, il vestito M andava male per entrambi. Questo nuovo metodo è come un sarto sartoriale: misura ogni persona e crea un vestito su misura, sia per il gigante che per il nano.
• Privacy Totale: Non hai mai visto i volti degli ospiti. Hai solo visto i "manichini" (i dati sintetici) che rappresentano le loro medie. Se qualcuno ruba i manichini, non può ricostruire la lista degli invitati reali.
• Una sola chiamata: Tutto questo succede in un solo round di comunicazione. I clienti inviano i manichini una volta sola e tu fai il lavoro. Non serve un'eterna conversazione.

In Sintesi

Questo articolo ci dice che ora possiamo analizzare dati sparsi in tutto il mondo (come dati medici di diversi ospedali o abitudini di guida di diverse città) senza violare la privacy, senza sapere prima quanti gruppi esistono e senza perdere i gruppi piccoli e rari.

È come riuscire a mappare l'intera popolazione di un continente sapendo solo la "media" di ogni quartiere, senza mai entrare nelle case delle persone, e scoprendo automaticamente quanti villaggi e città ci sono davvero.

Sommario tecnico

1. Il Problema

Il Federated Clustering (FC) è una tecnica emergente per analizzare pattern di distribuzione dei dati in ambienti distribuiti e protetti dalla privacy, senza condividere i dati grezzi. Tuttavia, i metodi FC esistenti affrontano diverse sfide critiche:

• Ipotesi irrealistiche: La maggior parte degli approcci attuali assume che il numero di cluster sia noto a priori e che le dimensioni dei cluster siano uniformi. Nella realtà, il numero di cluster è spesso sconosciuto e le distribuzioni dei dati sono sbilanciate (imbalanced), con alcuni cluster molto grandi e altri molto piccoli.
• Effetto "Uniforme": Gli algoritmi di partizionamento tradizionali tendono a forzare una distribuzione uniforme dei campioni, fallendo nel rilevare cluster di piccole dimensioni o forme irregolari.
• Vincoli di Privacy e Comunicazione: In scenari federati, la trasmissione di dati grezzi è vietata. I metodi esistenti che cercano di aggirare questo problema spesso richiedono molte iterazioni di comunicazione (costose) o introducono un overhead computazionale elevato (es. crittografia complessa).
• Mancanza di Adattabilità: Esiste una scarsità di metodi in grado di determinare automaticamente il numero ottimale di cluster ($k^*$) in un setting federato, specialmente con dati non-IID (non indipendenti e identicamente distribuiti) e sbilanciati.

2. Metodologia: Fed-k∗-HC

Gli autori propongono Fed-k∗-HC, un nuovo framework di clustering federato che opera in un unico passaggio di comunicazione (one-shot) e determina automaticamente il numero di cluster. Il metodo si articola in due fasi principali:

A. Partizionamento Micro-Automatizzato sul Client (Client-Side)

Ogni client elabora i propri dati localmente senza inviarli al server:

1. Micro-sottocluster: Invece di formare pochi grandi cluster, i dati locali vengono partizionati in molti piccoli "micro-sottocluster" utilizzando un algoritmo di apprendimento competitivo chiamato SNP (Selection of Number of Prototypes). Questo approccio evita di imporre forme o dimensioni specifiche ai cluster.
2. Generazione di Dati Sostitutivi: Per preservare la privacy, i client non inviano i dati originali. Calcolano invece le statistiche di ciascun micro-sottocluster (centroide, covarianza, raggio) e generano dati sintetici basati su una distribuzione normale multivariata che approssima la distribuzione originale.
3. Trasmissione: Vengono inviati al server solo i dati sintetici e le statistiche dei sottocluster, garantendo che i dati grezzi non lascino mai il dispositivo.

B. Fusione Gerarchica e Selezione del Numero di Cluster sul Server (Server-Side)

Il server riceve i dati sintetici da tutti i client e procede come segue:

1. Determinazione Automatica di $k^*$ (Algoritmo SNC):
   • Viene utilizzato un metodo basato sui Natural Neighbors (Vicini Naturali).
   • Vengono definiti i Loose Natural Neighbors (LNN) e i Strict Natural Neighbors (SNN). Gli SNN aggiungono un vincolo di reciprocità stretta (essere l'uno l'ennesimo vicino dell'altro) per ridurre le connessioni errate tra cluster densi e sparsi, migliorando la robustezza sui dati sbilanciati.
   • L'algoritmo costruisce un grafo di vicinanza e conta i componenti connessi per determinare automaticamente il numero ottimale di cluster globali ($k^*$).
2. Fusione Gerarchica:
   • Una volta stimato $k^*$, il server esegue un processo di fusione bottom-up.
   • I sottocluster vengono fusi iterativamente in base a una metrica di distanza speciale ($d_{Ci,Cj}$) che considera:
     • La distanza tra i centroidi.
     • Il grado di sovrapposizione (overlap) tra i cluster.
     • La similarità delle deviazioni standard (densità).
   • Questo processo si ferma quando il numero di cluster raggiunge $k^*$, mitigando l'effetto "uniforme" e preservando i cluster di piccole dimensioni.

3. Contributi Chiave

• Paradigma Federato Innovativo: Introduce un approccio che risolve il problema del clustering federato su dati sbilanciati senza richiedere la conoscenza preventiva del numero di cluster.
• Meccanismo di Partizione Fine e Fusione Gerarchica: L'uso di micro-sottocluster locali e la successiva fusione gerarchica sul server permette di catturare distribuzioni complesse e di forme irregolari, superando i limiti degli algoritmi basati su centroidi tradizionali.
• Selezione Automatica di $k^*$ in Setting Federato: L'algoritmo SNC (Selection of Number of Clusters) permette di stimare il numero corretto di cluster basandosi esclusivamente sulle relazioni di vicinanza dei dati sintetici, eliminando la necessità di iperparametri fissi.
• Protezione della Privacy One-Shot: Il framework richiede una sola round di comunicazione, riducendo drasticamente il rischio di perdita di privacy e l'overhead di comunicazione rispetto ai metodi iterativi.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su 11 dataset (5 reali e 6 sintetici), inclusi scenari IID, Non-IID, bilanciati e fortemente sbilanciati. I risultati mostrano:

• Prestazioni Superiori: Fed-k∗-HC supera gli stati dell'arte (come KFed, MUFC, F3KM, Orchestra) in termini di metriche di valutazione (F-measure, Accuracy, NMI, ARI), specialmente sui dati sbilanciati.
• Rilevamento di Cluster Minori: A differenza di altri metodi che tendono a ignorare i cluster di piccole dimensioni (effetto uniforme), Fed-k∗-HC riesce a identificarli con alta precisione.
• Accuratezza nella Stima di $k^*$: L'algoritmo SNC stima il numero di cluster con alta accuratezza, corrispondente spesso al valore reale (ground-truth) in molti dataset, anche senza fornire tale informazione in input.
• Efficienza: Il metodo dimostra una scalabilità lineare rispetto al numero di client e alla dimensione dei dati, con un tempo di esecuzione competitivo grazie alla strategia one-shot.

5. Significato e Impatto

Questo lavoro è significativo perché colma un divario fondamentale tra le teorie del clustering federato e le applicazioni reali complesse.

• Praticità: Rimuove la necessità di conoscere a priori il numero di cluster, un requisito spesso impossibile da soddisfare in scenari reali dinamici.
• Robustezza: Offre una soluzione robusta al problema dello sbilanciamento dei dati, che è una delle principali cause di fallimento negli algoritmi di clustering distribuiti attuali.
• Privacy: Dimostra che è possibile ottenere un'analisi globale accurata dei dati distribuiti mantenendo una protezione rigorosa della privacy e minimizzando la comunicazione.

In sintesi, Fed-k∗-HC rappresenta un avanzamento sostanziale verso l'adozione pratica del clustering federato in settori critici come la diagnostica medica, il rilevamento di frodi finanziarie e l'analisi industriale, dove i dati sono per natura distribuiti, eterogenei e sensibili.