Revenir au contenu principal

TensorFlow™ sur Databricks

Illustration

Clusters et k-moyennes

Nous allons maintenant nous aventurer dans notre première application : créer des clusters à l'aide de l'algorithme de k-moyennes. Le clustering est un exercice d'exploration de données qui consiste à trouver des groupes de points de données similaires au sein d'un ensemble de données. L'algorithme de k-moyennes est très efficace pour trouver des clusters dans de nombreux types de datasets.

Pour en savoir plus sur les clusters et les k-moyennes, consultez la documentation de scikit-learn sur son algorithme de k-moyennes ou regardez cette vidéo :

Génération d'échantillons

Nous allons d'abord avoir besoin de générer des échantillons. Nous pourrions le faire de façon aléatoire, mais cela ne nous donnerait probablement que des points très épars ou un gros groupe – rien d'idéal pour le clustering.

Nous allons donc plutôt commencer par générer trois centroïdes, puis choisir de façon aléatoire (avec une distribution normale) autour de ces points. Voici déjà une méthode pour réaliser cette étape :

 

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

 

Ajoutez ce code à functions.py

Ce code crée n_clusters centroïdes différents de façon aléatoire (à l'aide de np.random.random((1, n_features))) et les utilise comme points centraux pour tf.random_normal. La fonction tf.random_normal génère des valeurs aléatoires normalement distribuées, que nous ajoutons au point central actuel. Cela crée un blob de points autour de ce centre. Nous enregistrons ensuite les centroïdes (centroids.append) et les échantillons générés (slices.append(samples)). Il ne nous reste plus qu'à créer « Une grande liste d'échantillons » à l'aide de tf.contat et à convertir les centroïdes en variables TensorFlow, toujours avec tf.concat.

En enregistrant cette méthode create_samples dans un fichier appelé functions.py, nous pouvons l'importer dans les scripts de cette leçon (et de la prochaine !). Créez un nouveau fichier appelé  generate_samples.py qui contient le code suivant :

 

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)

 

Ce code définit simplement le nombre de clusters et de fonctionnalités, ainsi que le nombre d'échantillons à produire. Je recommande de ne pas dépasser 2 comme nombre de fonctionnalités, cela nous permettra de les visualiser par la suite. Si vous augmentez embiggen_factor, vous augmenterez l'étendue – ou la taille – des clusters. Je choisis une valeur qui nous aidera à bien comprendre le principe en générant des clusters faciles à identifier visuellement.

Pour visualiser les résultats, nous créons une fonction de représentation graphique à l'aide de matplotlib. Ajoutez ce code à 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()

 

Ajoutez ce code à functions.py

Ce code a une fonction simple : il représente les échantillons de chaque cluster dans une couleur différente et ajoute un grand X magenta à l'endroit du centroïde. Le centroïde est donné en tant qu'argument, ce qui va nous rendre service par la suite.

Mettez à jour generate_samples.py pour importer cette fonction en ajoutant from functions import plot_clusters en haut du fichier. Ajoutez ensuite cette ligne de code en bas :

 

plot_clusters(sample_values, centroid_values, n_samples_per_cluster)

 

L'exécution de generate_samples.pydoit maintenant vous donner le graphique suivant :

Initialisation

L'algorithme de k-moyennes commence par le choix des centroïdes initiaux, qui ne sont que des conjectures aléatoires concernant les centroïdes réels des données. La fonction suivante choisit aléatoirement un certain nombre d'échantillons dans le dataset pour les utiliser comme conjecture initiale :

 

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

 

Ajoutez ce code à functions.py

Le code commence par créer un index de chaque échantillon (avec tf.range(0, n_samples) puis le mélange de façon aléatoire. Nous choisissons ensuite un nombre fixe (n_clusters) d'index à l'aide de tf.slice. Ces index, corrélés à nos centroïdes initiaux, sont ensuite groupés à l'aide de tf.gather pour former notre ensemble de centroïdes initiaux.

Ajoutez cette nouvelle fonction choose_random_centorids à functions.py et créez un nouveau script (ou modifiez le précédent) comme suit :

 

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)

 

Cette fois, et c'est le principal changement, nous créons une variable pour ces centroïdes initiaux, et nous calculons leur valeur dans la session. Ce sont ces premières conjectures que nous représentons dans plot_cluster, et non les centroïdes réels utilisés pour générer les données.

Nous obtenons ainsi une image semblable à la précédente, mais les centroïdes occuperont des positions aléatoires. Essayez d'exécuter ce script plusieurs fois de suite pour observer le déplacement des centroïdes.

Mise à jour des centroïdes

Après avoir tenté de conjecturer l'emplacement des centroïdes, l'algorithme de k-moyennes actualise ces conjectures en fonction des données. Le processus consiste à attribuer à chaque échantillon un numéro de cluster représentant le centroïde dont il est le plus proche. Ensuite, les centroïdes sont mis à jour afin qu'ils prennent la valeur moyenne de tous les échantillons qui leur sont attribués. Le code suivant réalise l'étape attribution au cluster le plus proche :

 

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

 

Notez que j'ai emprunté du code à cette page, qui utilise un autre type d'algorithme de k-moyennes et contient beaucoup d'informations utiles.

Il s'agit cette fois de calculer la distance qui sépare chaque échantillon de chaque centroïde, ce dont se charge la ligne distances =. Le calcul de la distance utilise la distance euclidienne. Soulignons que tf.substract étend automatiquement la taille des deux arguments. Par conséquent, si nos échantillons sont une matrice et si les centroïdes sont un vecteur de colonne, nous obtenons une soustraction par paire entre les deux. Pour y parvenir, nous utilisons tf.expand_dims pour ajouter une dimension supplémentaire aux échantillons et aux centroïdes. Cela permet de forcer ce comportement de tf.substract.

Le code suivant se charge de mettre à jour les centroïdes :

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

 

Il prend les index les plus proches de chaque échantillon et s'en sert pour composer des groupes distincts à l'aide de tf.dynamic_partition. Nous utilisons ensuite tf.reduce_mean sur un groupe unique pour en déterminer la moyenne. C'est ce qui nous donne son nouveau centroïde. Après cette étape, il nous suffit d'utiliser tf.concat pour former les nouveaux centroïdes.

Tout est en place : nous pouvons ajouter ces appels à notre script (ou en créer un nouveau) :

 

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)

 

Ce code va :

  1. Générer des échantillons à partir des centroïdes initiaux
  2. Choisir des centroïdes initiaux de façon aléatoire
  3. Associer chaque échantillon à son centroïde le plus proche
  4. Donner à chaque centroïde la valeur de la moyenne des échantillons qui y sont associés

Voilà une seule itération de k-moyennes ! Je vous encourage à essayer les exercices qui en font une version itérative.

1) L'option de graine passée dans generate_samples veille à ce que les échantillons générés « aléatoirement » soient cohérents à chaque fois que vous exécutez le script. Nous n'avons pas passé la graine à la fonction choose_random_centroids, ce qui signifie que les centroïdes initiaux sont différents à chaque fois que le script est exécuté. Modifiez le script pour inclure une nouvelle graine et obtenir des centroïdes aléatoires.

2) L'algorithme de k-moyennes est exécuté de manière itérative : les centroïdes mis à jour à l'itération précédente sont utilisés pour créer des clusters, qui sont ensuite utilisés pour mettre à jour les centroïdes, et ainsi de suite. En d'autres termes, l'algorithme alterne entre deux fonctions : assign_to_nearest et update_centroids. Modifiez le code pour exécuter cette itération 10 fois de suite avant d'arrêter. Vous découvrirez que les centroïdes obtenus sont bien plus proches en moyenne quand le nombre d'itérations de k-moyennes augmente. Pour celles et ceux qui ont de l'expérience avec les k-moyennes, un prochain tutoriel se penchera sur les fonctions de convergence et d'autres critères d'arrêt.