Cos'è il k-means clustering?

È uno dei metodi di clustering più popolari utilizzati nel machine learning. A differenza dell'apprendimento supervisionato, i dati di addestramento utilizzati da questo algoritmo non sono etichettati, il che significa che i punti dati non hanno una struttura di classificazione definita.

Sebbene esistano vari tipi di algoritmi di clustering, tra cui esclusivi, sovrapposti, gerarchici e probabilistici, l'algoritmo di k-means clustering è un esempio di metodo di clustering esclusivo o "rigido". Questa forma di raggruppamento stabilisce che un punto dati può esistere in un solo cluster. Questo tipo di analisi dei cluster è comunemente utilizzato nella data science per la segmentazione del mercato, il clustering di documenti, la segmentazione di immagini e la compressione di immagini. L'algoritmo k-means è un metodo ampiamente utilizzato nell'analisi dei cluster perché è efficiente, efficace e semplice.

K-means è un algoritmo di clustering basato su centroidi iterativo che suddivide un set di dati in gruppi simili sulla base della distanza tra i loro centroidi. Il centroide, o centro del cluster, è la media o la mediana di tutti i punti all'interno del cluster a seconda delle caratteristiche dei dati.

Il k-means clustering è un processo iterativo per ridurre al minimo la somma delle distanze tra i punti dati e i relativi centroidi di cluster.

L'algoritmo di k-means clustering opera categorizzando i punti dati in cluster utilizzando una misura di distanza matematica, solitamente euclidea, dal centro del cluster. L'obiettivo è minimizzare la somma delle distanze tra i punti dati e i cluster assegnati. I punti dati più vicini a un centroide vengono raggruppati all'interno delle stesse categorie. Un valore k più alto, o il numero di cluster, indica cluster più piccoli con maggiori dettagli, mentre un valore k più basso si traduce in cluster più grandi con meno dettagli.

L'algoritmo di k-means clustering convenzionale richiede alcune fasi. La prima fase consiste nell'inizializzare k centroidi dove k è uguale al numero di cluster scelti per un set di dati specifico. Questo approccio utilizza metodi di selezione casuale o di campionamento iniziale del centroide.

La fase successiva comprende un processo iterativo in due fasi basato sull'algoritmo di machine learning per la massimizzazione dell'aspettativa.¹ La fase di aspettativa assegna ogni punto dati al suo centroide più vicino in base alla distanza (di nuovo, solitamente euclidea). La fase di massimizzazione calcola la media di tutti i punti per ogni cluster e riassegna il centro del cluster, o centroide. Questo processo si ripete fino a quando le posizioni del centroide non raggiungono la convergenza o fino a quando non viene raggiunto il numero massimo di iterazioni.

Il k-means clustering è semplice ma sensibile alle condizioni iniziali e agli outlier. È importante ottimizzare l'inizializzazione del centroide e il numero di cluster k, per ottenere i cluster più significativi. Esistono diversi modi per valutare e ottimizzare i componenti di clustering dell'algoritmo utilizzando le metriche di valutazione e i metodi di campionamento iniziale del centroide.

I cluster di qualità contengono almeno due proprietà: 

1. Tutti i punti dati all'interno di un cluster devono essere simili.
   
2. I cluster devono essere distinti l'uno dall'altro.

Queste proprietà si ottengono minimizzando la distanza intracluster e massimizzando la distanza intercluster di tutti i punti dati in un set di dati. In altre parole, più un cluster è compatto e isolato dagli altri cluster, meglio è. L'obiettivo dell'algoritmo di k-means clustering è quello di minimizzare la somma degli errori quadratici (SSE).² Il calcolo dell'SSE del quadrato della distanza euclidea di ciascun punto dal suo centroide più vicino valuta la qualità delle assegnazioni dei cluster misurando la variazione totale all'interno di ciascun cluster.

Le metriche di valutazione dei cluster controllano la qualità e forniscono diverse prospettive per analizzare i risultati del clustering. Questo aiuta a selezionare il numero ottimale di cluster e l'inizializzazione del centroide. Le seguenti metriche di valutazione sono metodi comuni per misurare le distanze intracluster e intercluster nel clustering.

L'algoritmo di k-means clustering mira a scegliere centroidi, o centri di cluster, che minimizzano l'inerzia, una metrica di valutazione che misura quanto bene un set di dati è stato raggruppato in base alle metriche di distanza. L'inerzia viene calcolata misurando la distanza tra un punto dati e il suo centroide, elevando al quadrato la distanza e sommando quei quadrati per ogni punto dati nel cluster. La somma o il valore inerziale è la distanza intracluster. Più bassa è la somma, meglio è, perché significa che i punti dati all'interno del cluster sono compatti o più simili.³

La seconda proprietà viene misurata con l'indice di Dunn. L'indice di Dunn rappresenta la relazione tra la distanza minima intercluster e la distanza massima intracluster. I cluster con un'elevata distanza intercluster indicano una migliore qualità, perché significa che i cluster sono il più possibile diversi tra loro.⁴

L'ottimizzazione è importante quando si utilizza k-means per ottenere i migliori risultati di clustering.

L'algoritmo k-means è non deterministico a causa della sua fase di inizializzazione casuale. Questo metodo implica che se l'algoritmo viene eseguito due volte su dati identici, le assegnazioni del cluster potrebbero differire. Per ottenere risultati ottimali di clustering, la selezione corretta dei centroidi iniziali e del numero ottimale di cluster migliora l'accuratezza e la velocità dell'algoritmo k-means.

Ogni cluster è rappresentato da un centroide, un punto dati che rappresenta il centro del cluster. K-means raggruppa i punti di dati simili in cluster minimizzando la distanza tra i punti di dati in un cluster con il loro centroide o il valore medio k. L'obiettivo principale dell'algoritmo k-means è ridurre al minimo le distanze totali tra i punti e il centroide del cluster assegnato. L'algoritmo funziona in modo iterativo e la selezione iniziale della partizione può influire notevolmente sui cluster risultanti.

L'inizializzazione casuale rischia di produrre risultati incoerenti. Esistono metodi di inizializzazione del centroide per mitigare questi rischi. Uno studio di NUS Computing spiega e confronta metodi come il celebre k-means++ con l'inizializzazione casuale.⁵

K-means++ è un algoritmo k-means che ottimizza la selezione del centroide o dei centroidi iniziali del cluster. Sviluppato dai ricercatori Arthur e Vassilvitskii, k-means++ migliora la qualità dell'assegnazione finale del cluster.⁶

La prima fase per l'inizializzazione utilizzando il metodo k-means++ consiste nello scegliere un centroide dal set di dati. Per ogni centroide successivo, calcola la distanza di ciascun punto dati dal centro del cluster più vicino. Il centroide successivo viene selezionato considerando la probabilità che un punto si trovi a una distanza proporzionale dal centroide più vicino scelto in precedenza. Il processo esegue le iterazioni fino a quando non viene inizializzato il numero scelto di centri di cluster.

Ecco un tutorial di IBM Developer che utilizza il metodo k-means++ per l'inizializzazione.

Idealmente, l'algoritmo k-means esegue l'iterazione fino a raggiungere il numero ottimale di cluster. Il numero massimo di iterazioni viene raggiunto una volta che i centroidi hanno raggiunto la convergenza.

Un metodo per ottenere il numero ottimale di cluster è il metodo del gomito. Il metodo a gomito (elbow) è un metodo grafico per trovare il numero ottimale di cluster all'interno di un algoritmo di k-means clustering. Misura la distanza euclidea tra ogni punto dati e il centro del cluster e sceglie il numero di cluster in base al livello in cui la modifica della somma dei quadrati all'interno del cluster (WCSS) viene disattivata. Questo valore rappresenta la varianza totale all'interno di ogni cluster che viene tracciata rispetto al numero di cluster.⁷

La prima fase del metodo a gomito consiste nel calcolare la WCSS per ogni cluster (k). Quindi, il valore WCSS viene tracciato lungo l'asse y e il numero di cluster viene tracciato sull'asse x. Con l'aumento del numero di cluster, i punti del grafico dovrebbero formare un modello coerente. Da questo schema risulta un intervallo per il numero ottimale di cluster.⁸ Quando si decide il numero di cluster, bisogna considerare i costi computazionali. Maggiore è il numero di cluster, maggiore è la potenza di elaborazione necessaria, soprattutto con set di dati di grandi dimensioni.

Questo metodo non è necessariamente il migliore, soprattutto per i set di dati con elevata dimensionalità o forma irregolare. Un altro metodo per scegliere il numero ottimale di cluster è l'analisi della silhouette.⁹

L'algoritmo di k-means clustering viene utilizzato in quasi tutti i domini e settori. In genere viene applicato ai dati di machine learning che hanno poche dimensioni, sono numerici e possono essere facilmente suddivisi in porzioni.

I ricercatori hanno integrato il k-means clustering con metodi di deep learning come CNN e RNN per migliorare le prestazioni di varie attività di machine learning, come computer vision, NLP e molti altri domini. Di seguito è riportato un elenco di applicazioni comuni del k-means clustering:

Segmentazione dei clienti: la pratica di dividere i clienti di un'azienda in gruppi in base a caratteristiche comuni che riflettono la somiglianza. Questa strategia consente alle aziende di rivolgersi a specifici cluster o gruppi di clienti per campagne pubblicitarie specifiche.

Classificazione dei documenti: una procedura per assegnare varie classi o categorie ai documenti. Questo metodo è utilizzato da molte organizzazioni per moderare i contenuti. Consulta questa documentazione di Watson Discover per creare un classificatore di documenti.

Segmentazione delle immagini: una tecnica di computer vision che divide un'immagine digitale in gruppi distinti di pixel. Questa ricerca approfondisce il modo in cui i modelli k-means vengono utilizzati per aiutare a identificare i confini nelle immagini mediche.¹⁰

Motori di raccomandazione: le applicazioni in tutto il web utilizzano motori di raccomandazione. L'analisi delle componenti principali e le tecniche di k-means clustering vengono utilizzate per creare raccomandazioni di prodotto per le aziende di e-commerce.¹¹

Per un'esperienza di apprendimento pratica, consulta il tutorial che spiega i fondamenti dell'esecuzione del k-means clustering in Python utilizzando IBM Watson Studio su watsonx.ai.

Questa esercitazione usa un modulo della libreria scikit-learn (sklearn) che esegue il k-means clustering. Il modulo include tecniche di ottimizzazione integrate che vengono manipolate dai suoi parametri di classe. La classe per il modulo è simile a questa:

class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')12

I parametri includono il numero di cluster da formare e il numero di centroidi da generare (n_clusters). Sono disponibili due metodi di inizializzazione: k-means++ e casuale. Include anche gli attributi per impostare il numero massimo di iterazioni. Ogni iterazione inizia con la suddivisione del set di dati nel valore del parametro n_cluster.

Le seguenti librerie vengono utilizzate per generare un set di dati di test ed eseguire il clustering:

import pandas as pd 
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns
import numpy

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

Alcuni benefici comuni del k-means clustering nelle applicazioni di machine learning includono:

Semplice: il k-means clustering è semplice da capire e da mettere in pratica. È la tecnica di machine learning non supervisionato più popolare.

Veloce: il k-means clustering è progettato con un approccio iterativo computazionalmente semplice. L'algoritmo di k-means clustering è più veloce del clustering gerarchico, che comporta la costruzione di una struttura ad albero di cluster e richiede il calcolo della distanza a coppie tra tutti i punti dati.

Scalabile: k-means è anche facilmente scalabile su set di dati di grandi dimensioni e si generalizza a cluster di diverse forme e dimensioni, il che è ideale per l'analisi dei cluster. Poiché l'algoritmo è così efficiente dal punto di vista computazionale, è più scalabile e adatto a set di dati di grandi dimensioni rispetto ad altri metodi.

Alcune sfide comuni associate al k-means clustering includono:

Dipendenza dai parametri di input: il k-means clustering dipende dai parametri di input impostati correttamente. L'inizializzazione del centroide e del numero di cluster corretti è impeccabile per ottenere risultati significativi sui cluster. Un'inizializzazione errata del centroide potrebbe causare un aumento del tempo di esecuzione e assegnazioni di cluster di bassa qualità. Molte ricerche sono state condotte per migliorare la procedura di inizializzazione del centroide per ottenere migliori risultati di clustering e tempi di convergenza più rapidi.

Possibili prestazioni insoddisfacenti su alcuni set di dati: k-means funziona in modo efficace quando il set di dati contiene cluster di dimensioni simili e non ci sono outlier o variazioni di densità degne di nota. K-means offre prestazioni insoddisfacenti quando il set di dati contiene molte variazioni o è altamente dimensionale. I dati che non sono allineati con alcune ipotesi del set di dati potrebbero causare la produzione di cluster di bassa qualità da parte di k-means.¹³ Ad esempio, i cluster di dimensioni non uniformi potrebbero inclinare i centroidi verso i cluster più grandi, causando distorsioni e classificazioni errate tra i cluster più piccoli. Per risolvere questo problema, k-means può essere generalizzato utilizzando modelli probabilistici come il nodo Gaussian Mixture.

Impatto significativo dei outlier: gli outlier hanno un impatto significativo sui risultati del k-means clustering. I diversi cluster dovrebbero essere distanti, ma non così distanti da distorcere i punti dati. È importante considerare le ipotesi dei dati prima di applicare k-means. K-means è particolarmente sensibile agli outlier poiché mira a determinare i centroidi calcolando la media dei valori con un cluster. Questa sensibilità rende i dati inclini all'overfitting per includere questi outlier.