Come funziona k-means clustering

K-means è un algoritmo che esegue l’addestramento di un modello che raggruppa oggetti simili. L'algoritmo k-means ottiene ciò mappando ogni osservazione nel set di dati di input a un punto nello n-spazio bidimensionale (dove n è il numero di attributi dell'osservazione). Ad esempio, il set di dati può contenere osservazioni di temperatura e umidità in una determinata posizione, che sono mappate a punti (t, h) in uno spazio bidimensionale.

Nota

Gli algoritmi clustering sono supervisionati. Nell'apprendimento non supervisionato, le etichette che possono essere associate con gli oggetti nel set di dati di addestramento non verranno utilizzate. Per ulteriori informazioni, consulta Apprendimento non supervisionato.

In k-means clustering, ogni cluster ha un centro. Durante l’addestramento del modello, l'algoritmo k-means utilizza la distanza del punto che corrisponde a ogni osservazione nel set di dati per i centri del cluster come base per il clustering. Tu scegli il numero di cluster (k) da creare.

Ad esempio, supponiamo che desideri creare un modello per riconoscere cifre scritte a mano e scegli il set di dati MNIST per l’addestramento. Il set di dati fornisce migliaia di immagini di cifre scritte a mano (da 0 a 9). In questo esempio, puoi scegliere di creare 10 cluster, uno per ogni cifra (0, 1,..., 9). Come parte del modello di addestramento, l'algoritmo k-means raggruppa le immagini in ingresso in 10 cluster.

Ogni immagine nel set di dati MNIST è un'immagine a 28 x 28 pixel, con un totale di 784 pixel. Ogni immagine corrisponde a un punto in un spazio a 784 dimensioni, simile a un punto in uno spazio bidimensionale (x, y). Per trovare un cluster a cui appartiene un punto, l'algoritmo k-means rileva la distanza di quel punto, da tutti i centri di cluster. Poi sceglie il cluster con il centro più vicino come il cluster a cui appartiene l'immagine.

Nota

Amazon SageMaker utilizza una versione personalizzata dell'algoritmo in cui, invece di specificare che l'algoritmo crea k cluster, puoi scegliere di migliorare la precisione del modello specificando centri cluster aggiuntivi (K = k*x). Tuttavia, l'algoritmo li riduce sostanzialmente a cluster k.

In SageMaker, specifichi il numero di cluster durante la creazione di un processo di formazione. Per ulteriori informazioni, consulta CreateTrainingJob. Nel corpo della richiesta, la mappa di stringhe HyperParameters per specificare le stringhe k e extra_center_factor.

Di seguito è riportato un riepilogo di come k-means funziona per la formazione dei modelli in: SageMaker

1. Determina i centri di cluster iniziali K.

   Nota

   Nei seguenti argomenti, i cluster K si riferiscono a k* x, dove specifichi k e x durante la creazione di un processo di addestramento del modello.

2. Itera sui dati di addestramento di input e ricalcola i centri di cluster.

3. Riduce i cluster risultanti per k (se il tecnico addetto alla gestione dei dati ha specificato la creazione di cluster k*x nella richiesta).

Le seguenti sezioni spiegano anche alcuni dei parametri che un tecnico addetto alla gestione dei dati può specificare i dati per configurare un processo di addestramento del modello come parte della mappa di stringhe HyperParameters.

Fase 1: determinare i centri di cluster iniziali

Quando si utilizza k-means in SageMaker, i centri di cluster iniziali vengono scelti tra le osservazioni in un piccolo lotto campionato casualmente. Scegli una delle seguenti strategie per determinare come questi centri di cluster iniziali sono selezionati:

• L'approccio casuale: scegli casualmente K osservazioni nel tuo set di dati di input come centri di cluster. Ad esempio, puoi scegliere un centro di cluster che punta allo spazio a 784 dimensioni che corrisponde a qualsiasi 10 immagini nel set di dati di addestramento MNIST.

• L'approccio k-means++, che funziona come segue:

  1. Inizia con un cluster e determina il suo centro. Selezioni casualmente un'osservazione dal tuo set di dati di addestramento e utilizzi il punto corrispondente all'osservazione come il centro di cluster. Ad esempio, nel set di dati MNIST, scegli casualmente un'immagine di cifre scritte a mano. Poi scegli il punto nello spazio a 784 dimensioni che corrisponde all'immagine come tuo centro di cluster. Si tratta del centro di cluster 1.

  2. Determina il centro per il cluster 2. Dalle osservazioni rimanenti nel set di dati di addestramento, scegli un'osservazione a caso. Scegli uno che è diverso rispetto a quello selezionato in precedenza. Questa osservazione corrisponde a un punto lontano dal centro di cluster 1. Utilizzando il set di dati MNIST come esempio, esegui le operazioni seguenti:

     • Per ognuna delle immagini rimanenti, trova la distanza del punto corrispondente dal centro di cluster 1. Pareggia la distanza e assegna una probabilità che è proporzionale al quadrato della distanza. In questo modo, un'immagine che è diversa da quella selezionata in precedenza ha una maggiore probabilità di essere selezionata come centro di cluster 2.

     • Scegli una delle immagini casualmente, in base alla probabilità assegnate nella fase precedente. Il punto che corrisponde all'immagine è il centro di cluster 2.

  3. Ripeti la fase 2 per trovare il centro di cluster 3. Questa volta trova le distanze delle immagini rimanenti dal centro di cluster 2.

  4. Ripeti il processo finché non disponi dei centri di cluster K.

Per addestrare un modello SageMaker, si crea un lavoro di formazione. Nella richiesta, fornisci informazioni sulla configurazione specificando le seguenti mappe di stringa HyperParameters:

• Per specificare il numero di cluster da creare, aggiungi la stringa k.

• Per maggiore accuratezza, aggiungi la stringa opzionale extra_center_factor.

• Per specificare la strategia che desideri utilizzare per determinare i centri di cluster iniziali, aggiungi la stringa init_method e imposta il valore su random o k-means++.

Per ulteriori informazioni sullo stimatore SageMaker k-means, consulta K-means nella documentazione di Amazon Python SageMaker SDK.

Adesso hai un set iniziale di centri di cluster.

Fase 2: iterare i set di dati di addestramento e calcolare i centri di cluster

I centri di cluster che hai creato nella fase precedente sono per lo più casuali, con un po' di considerazione per il set di dati di addestramento. In questa fase, utilizzi i set di dati di addestramento per spostare questi centri verso i veri centri di cluster. L'algoritmo itera sul set di dati di addestramento e ricalcola i centri di cluster K.

1. Leggi un mini-batch di osservazioni (un sottoinsieme piccolo e scelto casualmente di tutti i record) dal set di dati di addestramento ed esegui le seguenti operazioni.

   Nota

   Quando crei un processo di addestramento del modello, specifichi le dimensioni del batch nella stringa mini_batch_size nella mappa di stringhe HyperParameters.

   1. Assegna tutte le osservazioni nel mini batch a uno dei cluster con il centro del cluster più vicino.

   2. Calcola il numero di osservazioni assegnate a ogni cluster. Poi calcola la proporzione dei nuovi punti assegnati per cluster.

      Ad esempio, considera i seguenti cluster:

      Cluster c1 = 100 punti assegnati in precedenza. Hai aggiunto 25 punti dal mini-batch in questa fase.

      Cluster c2 = 150 punti assegnati in precedenza. Hai aggiunto 40 punti dal mini-batch in questa fase.

      Cluster c3 = 450 punti assegnati in precedenza. Hai aggiunto 5 punti dal mini-batch in questa fase.

      Calcola la proporzione di nuovi punti assegnati a ogni cluster come segue:

      p1 = proportion of points assigned to c1 = 25/(100+25)
      p2 = proportion of points assigned to c2 = 40/(150+40)
      p3 = proportion of points assigned to c3 = 5/(450+5)

   3. Calcola il centro dei nuovi punti aggiunti a ogni cluster:

      d1 = center of the new points added to cluster 1
      d2 = center of the new points added to cluster 2
      d3 = center of the new points added to cluster 3

   4. Calcola la media ponderata per trovare i centri di cluster aggiornati come segue:

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1)
      Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2)
      Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)

2. Leggi il prossimo mini-batch e ripeti la fase 1 per ricalcolare i centri del cluster.

3. Per ulteriori informazioni su mini-batch k-means, consulta Web-Scale k-means Clustering).

Fase 3: ridurre i cluster da K a k

Se l'algoritmo ha creato K cluster, (K = k* x), dove x è maggiore di 1, riduce i cluster K a cluster k. (Per ulteriori informazioni, consulta extra_center_factor nella discussione precedente.) Ciò avviene tramite l'applicazione del metodo di Lloyd con l'inizializzazione di kmeans++ ai centri di cluster K. Per ulteriori informazioni sulle modalità di Lloyd's, consulta k-significa clustering.