Passa al contenuto principale

TensorFlow™ su Databricks

Illustration

Clustering e k-means

Affrontiamo ora la nostra prima applicazione, il clustering con l'algoritmo k-means. Il clustering è un esercizio di data mining nel quale si prende un insieme di dati e si individuano gruppi di punti simili fra loro. L'algoritmo k-means è ottimo per trovare cluster all'interno di molti tipi di set di dati.

Per maggiori informazioni su cluster e k-means, consulta la documentazione di Scikit-Learn sull'algoritmo k-means o guarda questo video:

Generare campioni

Come prima cosa dovremo generare alcuni campioni. Potremmo generare i campioni in modo casuale, ma questo probabilmente restituirebbe punti molto sparsi, oppure un unico grande gruppo, entrambi scenari poco interessanti per il clustering.

Cominceremo invece generando tre centroidi e poi scegliendo a caso (con una distribuzione normale) intorno a quel punto. Ecco un metodo con cui procedere:

 

import tensorflow as tf
import numpy as np


def create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed):
    np.random.seed(seed)
    slices = []
    centroids = []
    # Create samples for each cluster
    for i in range(n_clusters):
        samples = tf.random_normal((n_samples_per_cluster, n_features),
                                   mean=0.0, stddev=5.0, dtype=tf.float32, seed=seed, name="cluster_{}".format(i))
        current_centroid = (np.random.random((1, n_features)) * embiggen_factor) - (embiggen_factor/2)
        centroids.append(current_centroid)
        samples += current_centroid
        slices.append(samples)
    # Create a big "samples" dataset
    samples = tf.concat(slices, 0, name='samples')
    centroids = tf.concat(centroids, 0, name='centroids')
    return centroids, samples

 

Inserisci questo codice in functions.py

Questo codice crea diversi n_clusters centroidi casuali (usando np.random.random((1, n_features))) e li usa come punti centrali per tf.random_normal. La funzione tf.random_normal  genera valori casuali distribuiti normalmente, che poi noi aggiungiamo al punto centrale corrente. Questo crea un blob di punti intorno a quel centro. Poi registriamo i centroidi (centroids.append) e i campioni generati (slices.append(samples)). Infine creiamo “un grande elenco di campioni” usando tf.concat e convertiamo anche i centroidi in una variabile TensorFlow, utilizzando ancora tf.concat.

Salvando questo metodo create_samples in un file chiamato functions.py possiamo importare questi metodi nei nostri script e usarli per questa (e la prossima!) lezione. Crea un nuovo file chiamato generate_samples.py, che contiene il codice seguente:

 

import tensorflow as tf
import numpy as np

from functions import create_samples

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70

np.random.seed(seed)

centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    centroid_values = session.run(centroids)

 

Questo codice imposta il numero di cluster e feature (raccomando di mantenere il numero di feature a 2, per poterle visualizzare successivamente) e il numero di campioni da generare. Aumentando embiggen_factor si aumenta lo “spread” o la dimensione dei cluster. In questo caso ho scelto un valore che offre buone opportunità di apprendimento, poiché genera cluster identificabili visivamente.

Per visualizzare i risultati, creiamo una funzione di plottaggio usando matplotlib. Aggiungiamo questo codice a functions.py:

 

def plot_clusters(all_samples, centroids, n_samples_per_cluster):
     import matplotlib.pyplot as plt
    #Plot out the different clusters
     #Choose a different colour for each cluster
     colour = plt.cm.rainbow(np.linspace(0,1,len(centroids)))
    for i, centroid in enumerate(centroids):
         #Grab just the samples fpr the given cluster and plot them out with a new colour
         samples = all_samples[i*n_samples_per_cluster:(i+1)*n_samples_per_cluster]
         plt.scatter(samples[:,0], samples[:,1], c=colour[i])
         #Also plot centroid
         plt.plot(centroid[0], centroid[1], markersize=35, marker="x", color='k', mew=10)
         plt.plot(centroid[0], centroid[1], markersize=30, marker="x", color='m', mew=5)
     plt.show()

 

Inserisci questo codice in functions.py

Quello che fa il codice è plottare i campioni da ogni cluster usando un colore diverso e creare una grande X in color magenta nel punto in cui si trova il centroide. Il centroide è definito come argomento, che sarà utile in seguito.

Aggiorna generate_samples.py per importare questa funzione aggiungendo from functions import plot_clusters all'inizio del file. Poi aggiungi questa riga di codice in fondo:

 

plot_clusters(sample_values, centroid_values, n_samples_per_cluster)

 

Eseguendo generate_samples.py si dovrebbe ora ottenere il diagramma seguente:

Inizializzazione

L'algoritmo k-means parte dalla scelta dei centroidi iniziali, che sono solo ipotesi casuali dei centroidi effettivi presenti nei dati. La funzione seguente sceglie casualmente un numero di campioni dal set di dati da utilizzare come ipotesi iniziale:

 

def choose_random_centroids(samples, n_clusters):
    # Step 0: Initialisation: Select `n_clusters` number of random points
    n_samples = tf.shape(samples)[0]
    random_indices = tf.random_shuffle(tf.range(0, n_samples))
    begin = [0,]
    size = [n_clusters,]
    size[0] = n_clusters
    centroid_indices = tf.slice(random_indices, begin, size)
    initial_centroids = tf.gather(samples, centroid_indices)
    return initial_centroids

 

Inserisci questo codice in functions.py

Questo codice dapprima crea un indice per ogni campione (usando tf.range(0, n_samples) e poi lo mischia in modo casuale. A questo punto scegliamo un numero fisso (n_clusters) di indici usando tf.slice. Questi indici sono correlati ai nostri centroidi iniziali, che vengono poi raggruppati usando tf.gather per formare il nostro array di centroidi iniziali.

Aggiungi questa nuova funzione choose_random_centorids a functions.py e crea un nuovo script (o aggiorna quello precedente) nel modo seguente:

 

import tensorflow as tf
import numpy as np

from functions import create_samples, choose_random_centroids, plot_clusters

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70

centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)
initial_centroids = choose_random_centroids(samples, n_clusters)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    updated_centroid_value = session.run(initial_centroids)

plot_clusters(sample_values, updated_centroid_value, n_samples_per_cluster)

 

Il cambiamento principale in questo caso è che creiamo una variabile per questi centroidi iniziali e calcoliamo il suo valore nella sessione. Poi plottiamo queste prime ipotesi in plot_cluster, invece dei centroidi che abbiamo usato per generare i dati.

Eseguendo questo codice si otterrà un'immagine simile a quella precedente, ma i centroidi saranno in posizioni casuali. Prova a eseguire questo script alcune volte e osserva come i centroidi si spostino notevolmente.

Aggiornamento dei centroidi

Dopo aver fatto alcune ipotesi sulle posizioni dei centroidi, l'algoritmo k-means aggiorna tali ipotesi sulla base dei dati. Il processo consiste nell'assegnare a ogni campione un numero di cluster, che rappresenta il centroide a cui è più vicino. Successivamente i centroidi vengono aggiornati in modo che corrispondano alla media di tutti i campioni assegnati a quel cluster. Il codice seguente gestisce il passaggio assign to nearest cluster:

 

def assign_to_nearest(samples, centroids):
    # Finds the nearest centroid for each sample

    # START from https://esciencegroup.com/2016/01/05/an-encounter-with-googles-tensorflow/
    expanded_vectors = tf.expand_dims(samples, 0)
    expanded_centroids = tf.expand_dims(centroids, 1)
    distances = tf.reduce_sum( tf.square(
               tf.subtract(expanded_vectors, expanded_centroids)), 2)
    mins = tf.argmin(distances, 0)
    # END from https://esciencegroup.com/2016/01/05/an-encounter-with-googles-tensorflow/
    nearest_indices = mins
    return nearest_indices

 

Da notare che ho preso in prestito un po' di codice da questa pagina che ha un diverso tipo di algoritmo k-means e molte altre informazioni utili.

La procedura consiste nel calcolare la distanza fra ogni campione e ogni centroide, operazione svolta con la riga distances =. Il calcolo della distanza in questo caso è la distanza euclidea. È importante notare che tf.subtract espande automaticamente le dimensioni dei due argomenti. Questo significa che, avendo i nostri campioni come matrice e i centroidi come vettore colonna, si otterrà la sottrazione a coppia fra di essi. Per farlo, usiamo tf.expand_dims per creare una dimensione extra sia per i campioni sia per i centroidi, forzando questo comportamento di tf.subtract.

La porzione di codice seguente riguarda l'aggiornamento dei centroidi:

def update_centroids(samples, nearest_indices, n_clusters):
    # Updates the centroid to be the mean of all samples associated with it.
    nearest_indices = tf.to_int32(nearest_indices)
    partitions = tf.dynamic_partition(samples, nearest_indices, n_clusters)
    new_centroids = tf.concat([tf.expand_dims(tf.reduce_mean(partition, 0), 0) for partition in partitions], 0)
    return new_centroids

 

Questo codice preleva gli indici più vicini per ogni campione e li estrae come gruppi separati usando tf.dynamic_partition. A questo punto usiamo tf.reduce_mean su un singolo gruppo per trovare la media di quel gruppo, formando il suo nuovo centroide. Da qui, usiamo semplicemente tf.concat per raggrupparli formando i nostri nuovi centroidi.

Ora che tutto pronto, possiamo aggiungere queste chiamate al nostro script (o crearne uno nuovo):

 

import tensorflow as tf
import numpy as np

from functions import *

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70


data_centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)
initial_centroids = choose_random_centroids(samples, n_clusters)
nearest_indices = assign_to_nearest(samples, initial_centroids)
updated_centroids = update_centroids(samples, nearest_indices, n_clusters)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    updated_centroid_value = session.run(updated_centroids)
    print(updated_centroid_value)

plot_clusters(sample_values, updated_centroid_value, n_samples_per_cluster)

 

Questo codice svolgerà le seguenti operazioni:

  1. Genera campioni dai centroidi iniziali.
  2. Sceglie i centroidi iniziali in maniera casuale.
  3. Associa ogni campione al centroide più vicino.
  4. Aggiorna ogni centroide in modo che corrisponda alla media dei campioni ad esso associati.

Questa è una singola iterazione di k-means! Prova ora a eseguire gli esercizi, che trasformano tutto quello che abbiamo visto in una procedura iterativa.

1) L'opzione seed passata a generate_samples assicura che i campioni generati "casualmente" siano omogenei ogni volta che viene eseguito lo script. Non abbiamo passato il seed alla funzione choose_random_centroids; questo significa che i centroidi iniziali sono diversi ogni volta che si esegue lo script. Aggiorna lo script per includere un nuovo seed per centroidi casuali.

2) L'algoritmo k-means viene eseguito in modo iterativo, usando i centroidi aggiornati dall'iterazione precedente per assegnare i cluster, che vengono poi usati per aggiornare i centroidi, e così via. In altri termini, l'algoritmo alterna le chiamate assign_to_nearest e update_centroids. Aggiorna il codice per eseguire questa iterazione 10 volte, prima di arrestare il processo. Noterai che i centroidi risultanti sono molto più vicini in media con più iterazioni di k-means. (Per chi ha esperienza di k-means, un altro tutorial illustrerà le funzioni di convergenza e altri criteri di arresto.)