Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

O artigo propõe o Fed-$k^*$-HC, um novo framework de agrupamento federado hierárquico que determina automaticamente o número ótimo de clusters e lida com tamanhos desbalanceados, gerando micro-subclusters nos clientes para fusão hierárquica baseada em densidade no servidor.

O essencial

Imagine que você tem um grande grupo de amigos espalhados pelo mundo, e cada um deles tem um caderno de anotações com desenhos de animais. O objetivo é descobrir quantas espécies de animais existem e agrupar os desenhos por tipo (leões, elefantes, pássaros), mas há um problema: ninguém pode mostrar os desenhos originais. A privacidade é sagrada. Além disso, alguns amigos têm milhares de desenhos de leões, enquanto outros têm apenas dois desenhos de pássaros. A maioria dos métodos antigos falharia aqui, tentando forçar todos os grupos a terem o mesmo tamanho ou exigindo que você dissesse de antemão "existem 5 tipos de animais".

O artigo que você enviou apresenta uma solução inteligente chamada Fed-k*-HC. Vamos explicar como funciona usando uma analogia simples:

1. O Problema: A "Festa dos Grupos Desiguais"

Na vida real, os dados não são justos. Alguns grupos são gigantes (como "leões") e outros são minúsculos (como "pássaros raros").

• O erro comum: Métodos antigos tentam dividir a festa em mesas do mesmo tamanho. Isso faz com que os grupos pequenos sejam ignorados ou misturados com os grandes.
• O segredo: Ninguém sabe quantos grupos existem. Você não pode pedir para a máquina "achar 5 grupos" se a resposta real for 7.

2. A Solução: O "Detetive de Mini-Grupos" (Fed-k*-HC)

A equipe criou um método que funciona em duas etapas principais, como se fosse uma investigação em duas fases:

Fase 1: No Bairro de Cada Amigo (O Cliente)

Em vez de enviar os desenhos originais (o que quebraria a privacidade), cada amigo faz algo inteligente:

• Eles olham para seus próprios cadernos e dividem os desenhos em pequenos "mini-grupos" (micro-subclusters). Imagine que eles pegam os desenhos e colocam em caixinhas pequenas, agrupando os que parecem muito parecidos.
• Em vez de enviar os desenhos, eles enviam apenas uma "ficha técnica" de cada caixinha: "Esta caixinha tem 10 desenhos, o centro é aqui, e eles variam um pouco assim".
• O truque de mágica: Para proteger ainda mais a privacidade, eles geram desenhos fictícios que seguem exatamente as mesmas regras estatísticas da ficha técnica. É como enviar um "fantasma" do desenho que parece real, mas não é o original. O servidor recebe esses fantasmas, que são suficientes para entender a forma dos grupos sem ver os dados reais.

Fase 2: Na Sede Central (O Servidor)

Agora, o servidor recebe todas essas caixinhas e fichas de todos os amigos.

• A Grande Fusão (Hierárquica): O servidor começa a juntar as caixinhas mais parecidas. É como se ele estivesse colando caixinhas de leão com caixinhas de leão, e caixinhas de pássaro com pássaro.
• O Detetive Automático: Aqui está a parte genial. O servidor não precisa saber quantos grupos existem. Ele usa uma regra inteligente baseada em "vizinhos". Ele pergunta: "Quão perto estão essas caixinhas? Elas se tocam? Elas se sobrepõem?"
• Ele continua colando as caixinhas até que não faça mais sentido juntar duas que são muito diferentes. Nesse momento, ele para e diz: "Pronto! Descobrimos que existem exatamente X grupos."
• Isso evita o problema de "mesas iguais". Se houver um grupo gigante e um grupo minúsculo, o método consegue ver ambos, porque ele olha para a densidade e a proximidade, não para o tamanho.

Por que isso é revolucionário?

1. Privacidade Total: Os dados originais nunca saem do dispositivo do usuário. Apenas estatísticas e "fantasmas" de dados são enviados.
2. Sem Chutes: Você não precisa dizer ao computador "procure 5 grupos". O sistema descobre sozinho quantos grupos existem na natureza dos dados.
3. Justiça para os Pequenos: Diferente de métodos antigos que ignoram os grupos pequenos (os "pássaros raros"), este método é sensível o suficiente para encontrá-los, mesmo que eles sejam muito menores que os grupos grandes.
4. Uma Única Viagem: Tudo isso é feito em uma única rodada de comunicação (One-shot). Os amigos enviam a informação uma vez e o servidor responde com o resultado. É super rápido e economiza bateria e internet.

Em resumo

Imagine que você quer organizar uma biblioteca gigante onde os livros estão espalhados em casas diferentes e ninguém pode sair de casa. O Fed-k*-HC é como um bibliotecário inteligente que pede a cada pessoa uma lista de "temas de livros" que eles têm (sem os livros em si). O bibliotecário então junta esses temas, descobre sozinho quantas seções de livros existem (Ficção, História, Ciência) e organiza a biblioteca inteira, garantindo que até os livros raros tenham seu lugar, tudo sem ninguém precisar sair de casa ou mostrar seus livros pessoais.

É uma forma de encontrar padrões ocultos em dados desiguais, mantendo o segredo de cada um.

Resumo técnico

1. Problema Abordado

O artigo foca no desafio do Agrupamento Federado (Federated Clustering - FC) em cenários do mundo real, onde existem duas limitações críticas não resolvidas adequadamente pelas métodos existentes:

1. Desconhecimento do Número de Agrupamentos ($k$): A maioria dos algoritmos de FC assume que o número ideal de agrupamentos é conhecido a priori. No entanto, em cenários reais, esse número é frequentemente desconhecido.
2. Distribuição Desbalanceada de Dados: Os dados distribuídos entre os clientes (dispositivos) raramente são uniformes. Existem desequilíbrios significativos no tamanho dos agrupamentos (alguns são muito grandes, outros muito pequenos) e na distribuição dos dados entre os clientes (Non-IID).
3. O "Efeito Uniforme" (Uniform Effect): Algoritmos tradicionais baseados em partição (como k-means federado) tendem a forçar agrupamentos de tamanhos iguais, falhando em detectar clusters minoritários ou de formas complexas em dados desbalanceados.
4. Restrições de Privacidade e Comunicação: A necessidade de proteger os dados brutos e minimizar a comunicação (idealmente em um único turno ou one-shot) limita a quantidade de informações que o servidor pode receber para análise.

2. Metodologia Proposta: Fed-k*-HC

Os autores propõem um novo framework chamado Fed-k-HC*, que combina agrupamento hierárquico com uma estratégia de partição micro-local e fusão hierárquica no servidor. O método opera em duas fases principais:

A. Lado do Cliente: Partição Micro-Automatizada (Automated Micro-Partitioning)

Em vez de enviar dados brutos ou apenas centróides globais, cada cliente executa um processo local:

1. Agrupamento em Micro-subagrupamentos: Os dados locais são divididos em muitos "micro-subagrupamentos" (subclusters) usando um método de aprendizado competitivo chamado SNP (Selection of Number of Prototypes). Isso permite capturar a distribuição local com alta granularidade sem viés de forma.
2. Geração de Dados Sintéticos (Substitutos): Para preservar a privacidade, os dados brutos não são enviados. Em vez disso, para cada micro-subagrupamento, o cliente calcula sua média e covariância e gera um conjunto de dados sintéticos seguindo uma distribuição normal multivariada com esses parâmetros.
3. Envio: Apenas os dados sintéticos (que representam a distribuição estatística, não os dados reais) e parâmetros estatísticos (raio, tamanho) são enviados ao servidor.

B. Lado do Servidor: Fusão Hierárquica e Seleção Automática de $k^*$

O servidor recebe os dados sintéticos de todos os clientes e executa:

1. Determinação Automática de $k^*$ (Algoritmo SNC):
   • Utiliza uma abordagem baseada em Vizinhos Naturais (Natural Neighbors).
   • Define Vizinhos Naturais Frouxos (LNN) e Vizinhos Naturais Estritos (SNN). A definição estrita exige que dois pontos sejam vizinhos mútuos e também o $m$-ésimo vizinho um do outro, o que ajuda a lidar com dados desbalanceados e evita conexões errôneas entre clusters de densidades diferentes.
   • O algoritmo ajusta iterativamente o parâmetro de vizinhança ($b$) e calcula a distância média entre pares de vizinhos estritos para construir uma matriz de adjacência.
   • O número de componentes conectados no grafo resultante define automaticamente o número ótimo de clusters globais, $k^*$.
2. Fusão Hierárquica (Hierarchical Merging):
   • Uma vez determinado $k^*$, o servidor realiza uma fusão bottom-up dos micro-subagrupamentos.
   • Utiliza uma métrica de distância especial que considera a distância entre centróides, o grau de sobreposição (overlap) e a similaridade das variâncias (desvios padrão).
   • O processo de fusão continua até que restem exatamente $k^*$ clusters globais. Isso mitiga o "efeito uniforme", permitindo que clusters pequenos e grandes coexistam.

3. Principais Contribuições

1. Novo Paradigma de FC para Dados Desbalanceados: O trabalho aborda a lacuna de métodos que lidam simultaneamente com dados desbalanceados, distribuições Non-IID e número desconhecido de clusters em um cenário federado.
2. Mecanismo de Partição Fina e Fusão Hierárquica: A estratégia de dividir dados locais em micro-unidades e fundi-las hierarquicamente no servidor permite a detecção precisa de clusters de tamanhos variados, superando as limitações de métodos baseados em centróides fixos.
3. Seleção Automática de $k^*$ em Ambiente Federado: O algoritmo SNC (Selection of Number of Clusters) permite determinar o número de clusters sem intervenção humana ou suposições prévias, adaptando-se à distribuição global explorada através dos dados sintéticos.
4. Proteção de Privacidade em Turno Único (One-Shot): O método opera em um único ciclo de comunicação (envio de dados sintéticos e recebimento de rótulos), minimizando o risco de vazamento de dados e reduzindo a latência de comunicação.

4. Resultados Experimentais

Os autores realizaram extensos experimentos em 11 conjuntos de dados (5 reais do UCI e 6 sintéticos), incluindo cenários balanceados, desbalanceados, IID e Non-IID.

• Desempenho Superior: O Fed-k*-HC superou consistentemente métodos state-of-the-art (SOTA) como KFed, MUFC, F3KM e Orchestra em métricas como F-measure, Acurácia, NMI, ARI e DCV (métrica específica para desbalanceamento).
• Robustez ao Desbalanceamento: Em datasets com clusters altamente desbalanceados (ex: yeast, abalone), o método proposto manteve alta performance, enquanto outros métodos falharam em identificar clusters minoritários ou foram forçados a criar agrupamentos uniformes.
• Precisão na Estimativa de $k^*$: O algoritmo SNC conseguiu estimar o número correto de clusters ($k^*$) na maioria dos datasets, alinhando-se com o número real ($K$) sem necessidade de input manual.
• Eficiência Computacional: O método demonstrou escalabilidade linear em relação ao tamanho dos dados e ao número de clientes, sendo particularmente eficiente em comunicação devido à estratégia one-shot.

5. Significado e Impacto

O trabalho Fed-k-HC* é significativo porque:

• Ponte entre Teoria e Prática: Resolve problemas práticos (desconhecimento de $k$ e desbalanceamento) que limitam a aplicação de clustering federado em cenários reais (como saúde e finanças), onde os dados são heterogêneos e sensíveis.
• Inovação na Privacidade: Demonstra que é possível realizar análise de distribuição complexa (agrupamento hierárquico) sem expor dados brutos, utilizando apenas estatísticas sintetizadas.
• Flexibilidade: Elimina a necessidade de hiperparâmetros rígidos (como o número de clusters), tornando o sistema mais adaptável a ambientes dinâmicos.

Em resumo, o artigo apresenta uma solução robusta e automatizada para o agrupamento federado, superando as limitações de métodos anteriores ao integrar aprendizado competitivo local, geração de dados sintéticos e fusão hierárquica inteligente no servidor.