📊 statistics

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

Questo articolo propone un nuovo algoritmo di clustering k-means per dati gaussiani che utilizza metriche di distanza sia intra-cluster che inter-cluster insieme al criterio di Calinski-Harabasz per ottenere una convergenza più robusta e una migliore gestione degli outlier rispetto ai metodi tradizionali.

Autori originali: Naitik Gada (Rochester Institute of Technology)

Pubblicato 2026-07-31

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Naitik Gada (Rochester Institute of Technology)

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di entrare in una festa enorme e caotica dove migliaia di persone si mescolano, ma nessuno sa chi appartenga a quale gruppo. Non ci sono targhette con i nomi, non ci sono leader di gruppo e non ci sono cartelli che indicano i diversi tavoli. Il tuo compito è capire quali persone frequentano naturalmente le stesse persone. Questo è il mondo dell'apprendimento non supervisionato (unsupervised learning), un ramo dell'informatica in cui gli algoritmi cercano di trovare schemi nascosti in dati disordinati senza che gli venga comunicata la risposta in anticipo. Uno degli strumenti più popolari per questo lavoro è chiamato k-means clustering. Pensalo come a un gioco di sedie musicali in cui il computer cerca di raggruppare elementi simili insieme, trovando un "centro" per ogni gruppo e attirando tutti più vicino a quel centro. L'obiettivo è fare in modo che tutti in un gruppo siano molto simili tra loro, pur essendo molto diversi dalle persone degli altri gruppi. Tuttavia, questo gioco ha un difetto complicato: il computer spesso rimane bloccato in una soluzione "abbastanza buona" ma locale, perché parte da un tentativo casuale su dove dovrebbero essere i centri. Se sceglie il punto di partenza sbagliato, l'intero raggruppamento può andare storto. Questo è importante perché nel mondo reale, dall'organizzazione dei dati dei clienti all'analisi delle immagini mediche, ottenere questi gruppi correttamente è fondamentale per prendere decisioni intelligenti.

Questo articolo introduce una nuova variante al classico gioco del k-means per renderlo più affidabile. L'autore, Naitik H. Gada, suggerisce che il metodo tradizionale guarda solo a quanto le persone siano vicine al centro del proprio gruppo (chiamato distanza intra-cluster o within-cluster distance). Il nuovo approccio aggiunge una seconda regola: controlla anche quanto i diversi gruppi siano distanti tra loro (chiamata distanza inter-cluster o inter-cluster distance). Immagina se, mentre raggruppi i partecipanti alla festa, non chiedessi solo: "Sei vicino ai tuoi amici?", ma anche: "Sei abbastanza lontano dagli altri tavoli?". Bilanciando queste due misurazioni, l'algoritmo cerca di creare gruppi che non siano solo compatti, ma anche chiaramente separati l'uno dall'altro.

I ricercatori hanno testato questa idea utilizzando due tipi di dati. Per prima cosa, hanno creato set di dati finti che sembravano nuvole di punti rotonde e ordinate (simulando dati gaussiani) con diversi livelli di "disordine" o varianza. Hanno anche testato l'algoritmo su set di dati benchmark del mondo reale, inclusi i famosi dati del fiore Iris, un'analisi chimica del Vino e un set di dati medici sul Cancro al Seno. I risultati hanno mostrato che il nuovo metodo, che utilizza entrambe le misurazioni di distanza, è costantemente superiore al tradizionale k-means. Nei test sui dati finti, il nuovo algoritmo è stato più accurato e meno propenso a commettere errori quando i dati erano disordinati o quando i punti di partenza erano complicati. Ad esempio, su un set di dati 2D con alta varianza, il nuovo metodo ha raggiunto un'accuratezza di 0,9801, rispetto allo 0,9508 del metodo tradizionale. Sul set di dati Iris, ha raggiunto un'accuratezza di 0,8420 contro lo 0,7751 del vecchio modo.

Il documento evidenzia anche che il nuovo metodo è migliore nel gestire gli "outlier" (gli elementi anomali), ovvero quei membri della festa che si trovano un po' lontani da tutti gli altri. Nel set di dati del Vino, il metodo tradizionale a volte classificava erroneamente questi punti distanti, mentre il nuovo metodo li identificava correttamente. Tuttavia, gli autori sottolineano con cautela che, sebbene il nuovo metodo sia un miglioramento, non è una bacchetta magica che risolve ogni problema. Esso fatica ancora un po' con le posizioni di partenza iniziali dei gruppi, e le sue prestazioni sui dati ad altissima dimensionalità (come il set del Cancro al Seno a 9 dimensioni) sono state solo leggermente migliori rispetto al metodo tradizionale. Lo studio suggerisce che l'aggiunta di questa seconda misura di distanza rende il clustering "solido e più robusto", ma rimane un lavoro in corso che apre la porta a ricerche ancora più sofisticate in futuro.

Sintesi Tecnica: Un nuovo approccio di clustering k-means utilizzando due misure di distanza per dati gaussiani

Definizione del Problema
L'analisi di clustering è una tecnica fondamentale di apprendimento non supervisionato utilizzata per identificare l'omogeneità all'interno di dati non strutturati e non etichettati. Tra i vari metodi, il clustering k-means è ampiamente utilizzato grazie alla sua efficienza computazionale rispetto agli approcci gerarchici. Tuttavia, il k-means tradizionale soffre di due limitazioni primarie:

Sensibilità all'Inizializzazione: L'algoritmo è altamente sensibile alle posizioni iniziali dei centri dei cluster, causando spesso la convergenza verso minimi locali piuttosto che verso l'ottimo globale.
Ottimizzazione a Metrica Singola: L'algoritmo standard minimizza solo la Distanza Intra-Cluster (WCD) per garantire l'omogeneità all'interno dei gruppi. Non massimizza esplicitamente la separazione tra i diversi gruppi (Distanza Inter-Cluster o ICD).
Dipendenza da un $k$ Predeterminato: Il numero di cluster ( $k$ ) deve essere specificato preventivamente, il che è difficile per i dati ad alta dimensionalità dove la visualizzazione è impraticabile.

La letteratura esistente ha tentato di affrontare questi problemi attraverso vari metodi di inizializzazione (ad esempio, algoritmi genetici, simulated annealing) e misure di distanza alternative (ad esempio, Manhattan, Chebyshev). Tuttavia, molti studi si basano pesantemente su dati sintetici, mancano di una rigorosa quantificazione tramite metriche come l'F1-score o la sensibilità, o non riescono a incorporare una metrica di distanza specificamente progettata per massimizzare la separazione inter-cluster.

Metodologia
Il documento propone una nuova modifica all'algoritmo k-means standard che incorpora sia la Distanza Intra-Cluster (WCD) che la Distanza Inter-Cluster (ICD) come metriche di distanza.

Determinazione dei Cluster: Il numero di cluster ( $k$ ) non è scelto arbitrariamente ma è determinato tramite l'indice di Calinski-Harabasz, con il metodo dell'Elbow utilizzato per la validazione.
Logica dell'Algoritmo:
- Inizializzazione: I centri dei cluster sono inizializzati tramite una permutazione casuale degli indici del dataset.
- Ottimizzazione a Doppia Metrica: A differenza del k-means tradizionale che minimizza la somma delle distanze euclide al quadrato dai punti ai loro centroidi (WCD), l'algoritmo proposto ottimizza una funzione di costo relativo. Questa funzione è definita come il rapporto tra la WCD totale e l'ICD totale.
- Definizione di WCD: La somma delle distanze al quadrato dal centro di un cluster a tutti i punti all'interno di quel cluster.
- Definizione di ICD: La somma delle distanze al quadrato tra un punto nel cluster $i$ e tutti i punti non nel cluster $i$ , sommata su tutti i cluster.
- Iterazione: L'algoritmo aggiorna iterativamente i centroidi minimizzando questo costo relativo. Il processo continua finché i centroidi non si stabilizzano.
Metriche di Valutazione: Per quantificare le prestazioni, lo studio utilizza una Matrice di Confusione per calcolare l'Accuratezza Complessiva (OA), la Precisione (Valore Predittivo Positivo), il Richiamo (Sensibilità) e il punteggio F1.

Configurazione Sperimentale
L'algoritmo è stato valutato su due categorie di dataset:

Dati Sintetici: Quattro dataset generati da distribuzioni normali con diverse dimensioni (2D e 3D) e varianze (0,5 e 1,0). Questi sono stati progettati per testare le prestazioni sia su cluster ben definiti che su quelli sovrapposti (mal definiti).
Dati Benchmark: Tre dataset dal repository UCI Machine Learning:
- Iris: 150 istanze, 4 feature, 3 classi.
- Wine: 178 istanze, 13 attributi chimici, 3 classi.
- Breast Cancer (Wisconsin): 569 istanze, 9 feature, 2 classi (Benigno/Maligno).

Tutti gli esperimenti sono stati eseguiti per 100 iterazioni con identici seed di inizializzazione casuale sia per l'algoritmo proposto che per l'algoritmo k-means tradizionale per garantire un confronto equo.

Risultati Chiave
L'algoritmo proposto ha superato costantemente il k-means tradizionale in tutti i dataset, sebbene l'entità del miglioramento variasse:

Dati Sintetici:
- In dati 2D con varianza 0,5, il metodo proposto ha raggiunto il 97,05% di accuratezza rispetto al 96,07% del k-means tradizionale.
- In dati 2D con varianza 1,0 (cluster più sovrapposti), il divario si è ampliato al 98,01% rispetto al 95,08%.
- Nei dati 3D, il metodo proposto ha mostrato una robustezza significativa, in particolare negli scenari con varianza 0,5, dove l'accuratezza del k-means tradizionale è scesa a circa il 60% in alcune iterazioni, mentre il metodo proposto è rimasto vicino al 100%.
Dati Benchmark:
- Iris: Accuratezza proposta dell'84,20% rispetto al 77,51% (tradizionale). Il metodo proposto ha anche identificato correttamente specifici outlier che il metodo tradizionale aveva classificato erroneamente.
- Wine: Accuratezza proposta del 75,16% rispetto al 66,37%. Il metodo proposto ha dimostrato una volatilità significativamente inferiore tra le iterazioni.
- Breast Cancer: La differenza è stata minima (96,12% vs 95,82%), ma il metodo proposto è rimasto leggermente più costante e meno volatile.

Significato e Rivendicazioni
Il documento sostiene che l'inclusione della metrica della Distanza Inter-Cluster (ICD) insieme alla standard WCD crea un algoritmo di clustering più robusto. I principali contributi sono:

Robustezza Migliorata: L'approccio a doppia metrica riduce la sensibilità alle posizioni iniziali dei centri dei cluster, portando a una convergenza più costante e a meno casi in cui l'algoritmo rimane bloccato in scarsi minimi locali.
Gestione degli Outlier: Il metodo proposto dimostra una capacità superiore di classificare correttamente gli outlier nei loro veri cluster rispetto al metodo tradizionale.
Validazione Quantificabile: A differenza di molti studi precedenti che si basano solo su dati sintetici o valutazioni qualitative, questo lavoro valida l'algoritmo su dataset reali di benchmark utilizzando un set completo di metriche (Accuratezza, Precisione, Richiamo, F1).
Viabilità ad Alta Dimensionalità: Sebbene l'algoritmo sia stato concettualizzato per dati gaussiani a bassa dimensionalità, il test di stress sul dataset Breast Cancer a 9 dimensioni suggerisce che l'approccio è abbastanza robusto per applicazioni ad alta dimensionalità.

Gli autori concludono che, sebbene i guadagni di accuratezza possano essere modesti in alcuni casi ad alta dimensionalità, la riduzione della volatilità e la migliore gestione delle strutture dati ambigue validano l'ipotesi che l'ottimizzazione sia sia dell'omogeneità intra-cluster che dell'eterogeneità inter-cluster produca una soluzione di clustering superiore. Il lavoro stabilisce un precedente per ulteriori ricerche su metodi numerici sfumati per affrontare la sensibilità all'inizializzazione del k-means.

Articoli simili