📊 statistics

A novel k-means clustering approach using two distance measures for Gaussian data

Este artigo propõe um novo algoritmo de agrupamento k-means para dados gaussianos que utiliza métricas de distância intra-cluster e inter-cluster juntamente com o critério de Calinski-Harabasz para alcançar uma convergência mais robusta e um melhor tratamento de outliers em comparação com métodos tradicionais.

Autores originais: Naitik Gada (Rochester Institute of Technology)

Publicado 2026-07-31

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Naitik Gada (Rochester Institute of Technology)

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está entrando em uma festa enorme e caótica onde milhares de pessoas estão se misturando, mas ninguém sabe a quem pertence. Não há crachás, não há líderes de grupo e não há placas apontando para mesas diferentes. Seu trabalho é descobrir quais pessoas naturalmente andam juntas. Este é o mundo do aprendizado não supervisionado, um ramo da ciência da computação onde algoritmos tentam encontrar padrões ocultos em dados bagunçados sem serem informados sobre as respostas previamente. Uma das ferramentas mais populares para este trabalho é chamada k-means clustering. Pense nisso como um jogo de dança das cadeiras onde o computador tenta agrupar itens semelhantes, encontrando um "centro" para cada grupo e puxando todos para mais perto desse centro. O objetivo é garantir que todos em um grupo sejam muito semelhantes entre si, enquanto são muito diferentes das pessoas em outros grupos. No entanto, este jogo tem uma falha complicada: o computador frequentemente fica preso em uma solução local "boa o suficiente" porque começa com um palpite aleatório sobre onde os centros deveriam estar. Se ele escolher o ponto de partida errado, todo o agrupamento pode dar errado. Isso importa porque, no mundo real, desde a organização de dados de clientes até a análise de imagens médicas, acertar esses grupos é crucial para tomar decisões inteligentes.

Este artigo introduz uma nova reviravolta ao clássico jogo k-means para torná-lo mais confiável. O autor, Naitik H. Gada, sugere que o método tradicional olha apenas para o quão próximos as pessoas estão do centro de seu próprio grupo (chamado de distância intra-cluster). A nova abordagem adiciona uma segunda regra: ela também verifica o quão distantes os diferentes grupos estão uns dos outros (chamado de distância inter-cluster). Imagine se, ao agrupar os convidados da festa, você não perguntasse apenas: "Você está perto dos seus amigos?", mas também: "Você está longe o suficiente das outras mesas?". Ao equilibrar essas duas medições, o algoritmo tenta criar grupos que não são apenas unidos, mas também claramente separados uns dos outros.

Os pesquisadores testaram essa ideia usando dois tipos de dados. Primeiro, eles criaram conjuntos de dados fictícios que pareciam nuvens de pontos redondas e limpas (simulando dados Gaussianos) com diferentes níveis de "bagunça" ou variância. Eles também testaram o algoritmo em conjuntos de dados de referência do mundo real, incluindo os famosos dados da flor Iris, uma análise química de Vinho e um conjunto de dados médicos de Câncer de Mama. Os resultados mostraram que o novo método, que utiliza as duas medições de distância, desempenhou consistentemente melhor do que o k-means tradicional. Nos testes de dados fictícios, o novo algoritmo foi mais preciso e menos propenso a erros quando os dados estavam bagunçados ou quando os pontos de partida eram complicados. Por exemplo, em um conjunto de dados 2D com alta variância, o novo método alcançou uma precisão de 0,9801, comparado a 0,9508 para o método tradicional. No conjunto de dados Iris, atingiu 0,8420 de precisão contra 0,7751 do método antigo.

O artigo também destaca que o novo método é melhor em lidar com "outliers" — aqueles convidados da festa que estão parados um pouco afastados de todo mundo. No conjunto de dados de Vinho, o método tradicional às vezes classificava incorretamente esses pontos distantes, enquanto o novo método os identificava corretamente. No entanto, os autores são cuidadosos ao notar que, embora o novo método seja uma melhoria, ele não é uma solução mágica que resolve todos os problemas. Ele ainda tem certa dificuldade com as posições iniciais de partida dos grupos, e seu desempenho em dados de altíssima dimensão (como o conjunto de Câncer de Mama de 9 dimensões) foi apenas ligeiramente melhor que o do método tradicional. O estudo sugere que adicionar esta segunda medida de distância torna o agrupamento "mais sólido e robusto", mas continua sendo um trabalho em progresso que abre as portas para pesquisas ainda mais sofisticadas no futuro.

Resumo Técnico: Uma Nova Abordagem de Agrupamento k-means Utilizando Duas Medidas de Distância para Dados Gaussianos

Definição do Problema
A análise de agrupamento (clustering) é uma técnica fundamental de aprendizado não supervisionado utilizada para identificar homogeneidade em dados não estruturados e não rotulados. Entre vários métodos, o agrupamento k-means é amplamente utilizado devido à sua eficiência computacional em comparação com abordagens hierárquicas. No entanto, o k-means tradicional sofre de duas limitações primárias:

Sensibilidade à Inicialização: O algoritmo é altamente sensível às posições iniciais dos centros dos clusters, frequentemente causando a convergência para mínimos locais em vez do ótimo global.
Otimização de Métrica Única: O algoritmo padrão minimiza apenas a Distância Intra-Cluster (WCD - Within-Cluster Distance) para garantir a homogeneidade dentro dos grupos. Ele não maximiza explicitamente a separação entre diferentes grupos (Distância Inter-Cluster ou ICD - Inter-Cluster Distance).
Dependência de um $k$ Pré-determinado: O número de clusters ( $k$ ) deve ser especificado antecipadamente, o que é difícil para dados de alta dimensão onde a visualização é impraticável.

A literatura existente tentou abordar esses problemas por meio de vários métodos de inicialização (ex: algoritmos genéticos, simulated annealing) e medidas de distância alternativas (ex: Manhattan, Chebyshev). No entanto, muitos estudos dependem fortemente de dados sintéticos, carecem de quantificação rigorosa usando métricas como o F1-score ou sensibilidade, ou falham em incorporar uma métrica de distância especificamente projetada para maximizar a separação inter-cluster.

Metodologia
O artigo propõe uma nova modificação ao algoritmo k-means padrão que incorpora tanto a Distância Intra-Cluster (WCD) quanto a Distância Inter-Cluster (ICD) como métricas de distância.

Determinação de Clusters: O número de clusters ( $k$ ) não é escolhido arbitrariamente, mas determinado pelo índice Calinski-Harabasz, com o método do Cotovelo (Elbow method) sendo utilizado para validação.
Lógica do Algoritmo:
- Inicialização: Os centros dos clusters são inicializados via uma permutação aleatória de índices do conjunto de dados.
- Otimização de Métrica Dupla: Diferente do k-means tradicional, que minimiza a soma das distâncias euclidianas ao quadrado dos pontos em relação aos seus centroides (WCD), o algoritmo proposto otimiza uma função de custo relativo. Esta função é definida como a razão entre o WCD total e o ICD total.
- Definição de WCD: A soma das distâncias ao quadrado do centro de um cluster a todos os pontos dentro desse cluster.
- Definição de ICD: A soma das distâncias ao quadrado entre um ponto no cluster $i$ e todos os pontos não pertencentes ao cluster $i$ , somada sobre todos os clusters.
- Iteração: O algoritmo atualiza iterativamente os centroides minimizando este custo relativo. O processo continua até que os centroides se estabilizem.
Métricas de Avaliação: Para quantificar o desempenho, o estudo utiliza uma Matriz de Confusão para calcular a Acurácia Global (OA), Precisão (Valor Preditivo Positivo), Recall (Sensibilidade) e o F1 Score.

Configuração Experimental
O algoritmo foi avaliado em duas categorias de conjuntos de dados:

Dados Sintéticos: Quatro conjuntos de dados gerados a partir de distribuições normais com dimensões variadas (2D e 3D) e variâncias (0,5 e 1,0). Estes foram projetados para testar o desempenho em clusters bem definidos e sobrepostos (mal definidos).
Dados de Referência (Benchmark): Três conjuntos de dados do repositório UCI Machine Learning:
- Iris: 150 instâncias, 4 atributos, 3 classes.
- Wine: 178 instâncias, 13 atributos químicos, 3 classes.
- Breast Cancer (Wisconsin): 569 instâncias, 9 atributos, 2 classes (Benigno/Maligno).

Todos os experimentos foram executados por 100 iterações com sementes de inicialização aleatória idênticas tanto para o algoritmo proposto quanto para o algoritmo k-means tradicional para garantir uma comparação justa.

Principais Resultados
O algoritmo proposto superou consistentemente o k-means tradicional em todos os conjuntos de dados, embora a magnitude da melhoria tenha variado:

Dados Sintéticos:
- Em dados 2D com variância de 0,5, o método proposto alcançou 97,05% de acurácia contra 96,07% do k-means tradicional.
- Em dados 2D com variância de 1,0 (clusters mais sobrepostos), a lacuna aumentou para 98,01% vs 95,08%.
- Em dados 3D, o método proposto mostrou robustez significativa, particularmente em cenários de variância 0,5, onde a acurácia do k-means tradicional caiu para ~60% em certas iterações devido à má inicialização, enquanto o método proposto permaneceu próximo a 100%.
Dados de Referência (Benchmark):
- Iris: Acurácia proposta de 84,20% vs 77,51% (tradicional). O método proposto também identificou corretamente outliers específicos que o método tradicional classificou incorretamente.
- Wine: Acurácia proposta de 75,16% vs 66,37%. O método proposto demonstrou significativamente menor volatilidade entre as iterações.
- Breast Cancer: A diferença foi mínima (96,12% vs 95,82%), mas o método proposto permaneceu ligeiramente mais consistente e menos volátil.

Significância e Alegações
O artigo afirma que a inclusão da métrica de Distância Inter-Cluster (ICD) ao lado da métrica WCD padrão cria um algoritmo de agrupamento mais robusto. As principais contribuições são:

Melhoria da Robustez: A abordagem de métrica dupla reduz a sensibilidade às posições iniciais dos centros dos clusters, resultando em uma convergência mais consistente e menos casos de o algoritmo ficar preso em mínimos locais ruins.
Tratamento de Outliers: O método proposto demonstra uma capacidade superior de classificar corretamente outliers em seus clusters verdadeiros em comparação ao método tradicional.
Validação Quantificável: Ao contrário de muitos estudos anteriores que dependem apenas de dados sintéticos ou avaliações qualitativas, este trabalho valida o algoritmo em conjuntos de dados reais de referência usando um conjunto abrangente de métricas (Acurácia, Precisão, Recall, F1).
Viabilidade em Alta Dimensão: Embora o algoritmo tenha sido concebido para dados gaussianos de baixa dimensão, o teste de estresse no conjunto de dados de 9 dimensões do Breast Cancer sugere que a abordagem é robusta o suficiente para aplicações de alta dimensão.

Os autores concluem que, embora os ganhos de acurácia possam ser modestos em alguns casos de alta dimensão, a redução da volatilidade e a melhoria no tratamento de estruturas de dados ambíguas validam a hipótesia de que a otimização tanto para a homogeneidade intra-cluster quanto para a heterogeneidade inter-cluster produz uma solução de agrupamento superior. O trabalho estabelece um precedente para pesquisas futuras em métodos numéricos matizados para abordar a sensibilidade de inicialização do k-means.

Mais como este