Ir para o conteúdo principal

TensorFlow™ no Databricks

Illustration

Clustering e k-means

Agora, vamos nos aventurar em nossa primeira aplicação, que é o clustering com o algoritmo k-means. Clustering é um exercício de mineração de dados em que tentamos encontrar grupos de pontos semelhantes entre um conjunto de dados. K-means é um algoritmo excelente para encontrar clusterings em muitos tipos de conjuntos de dados.

Para saber mais sobre cluster e k-means, consulte a documentação de scikit-learn sobre o algoritmo k-means ou assista a este vídeo:

Gerando amostras

Primeiro, precisamos gerar algumas amostras. Poderíamos gerar as amostras aleatoriamente, mas é provável que o resultado sejam pontos muito esparsos ou apenas um grande grupo, o que não é muito interessante para o clustering.

Em vez disso, vamos começar gerando três centroides e, em seguida, escolher aleatoriamente (com uma distribuição normal) em torno desse ponto. Veja um método para fazer isso:

 

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

 

Coloque esse código em functions.py

A forma como isso funciona é criar centroides diferentes n_clusters aleatoriamente (usando np.random.random((1, n_features))) e usar os pontos centrais para tf.random_normal. A função tf.random_normal gera valores aleatórios distribuídos normalmente, que adicionamos ao ponto central atual. Isso cria um blob de pontos ao redor desse centro. Em seguida, registramos os centroides (centroids.append) e as amostras geradas (slices.append(samples)). Por fim, criamos "Uma grande lista de amostras" usando tf.concat e convertemos os centroides em uma variável do TensorFlow, também usando tf.concat.

Salve esse método create_samples em um arquivo chamado functions.py para importar esses métodos em nossos scripts para esta lição (e para a próxima!). Crie um novo arquivo chamado generate_samples.py, com o seguinte código:

 

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)

 

Isso apenas configura o número de clusters e recursos (recomendo manter o número de recursos em 2, permitindo-nos visualizá-los mais tarde) e o número de amostras a serem geradas. Aumentar o embiggen_factor aumentará o "spread" ou o tamanho dos clusters. Escolhi um valor aqui que oferece uma boa oportunidade de aprendizagem, pois gera clusters visualmente identificáveis.

Para visualizar os resultados, vamos criar uma função de plotagem usando matplotlib. Adicione este código 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()

 

Coloque esse código em functions.py

Esse código traça as amostras de cada cluster usando uma cor diferente e cria um grande X magenta onde está o centroide. O centroide é fornecido como argumento, o que será útil mais tarde.

Atualize o generate_samples.py para importar essa função adicionando da importação de funções plot_clusters à parte superior do arquivo. Em seguida, adicione esta linha de código à parte inferior:

 

plot_clusters(sample_values, centroid_values, n_samples_per_cluster)

 

A execução de generate_samples.py agora deve gerar o seguinte gráfico:

Inicialização

O algoritmo k-means começa com a escolha dos centroides iniciais, que são apenas suposições aleatórias dos centroides reais nos dados. A seguinte função escolherá aleatoriamente uma série de amostras do conjunto de dados para agir com base nessa suposição inicial:

 

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

 

Coloque esse código em functions.py

Primeiro, esse código cria um índice para cada amostra (usando tf.range(0, n_samples) e depois o embaralha aleatoriamente. A partir daí, escolhemos um número fixo (n_clusters) de índices usando tf.slice. Esses índices estão correlacionados aos nossos centroides iniciais, que são então agrupados usando tf.gather para formar nossa matriz de centroides iniciais.

Adicione essa nova função choose_random_centorids ao arquivo functions.py e crie um novo script (ou atualize o anterior) da seguinte forma:

 

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)

 

A principal mudança aqui é que criamos uma variável para esses centroides iniciais e calculamos seu valor na sessão. Em seguida, traçamos essas primeiras suposições para plot_cluster, em vez dos centroides reais que foram usados para gerar os dados.

A execução desse código gera uma imagem semelhante à acima, mas os centroides estarão em posições aleatórias. Tente executar este script algumas vezes, observando que os centroides se movem um pouco.

Atualização de centroides

Depois de começar com algumas suposições para os locais do centroide, o algoritmo k-means atualiza essas suposições com base nos dados. O processo é atribuir um número de cluster a cada amostra, representando o centroide ao qual está mais próximo. Depois disso, os centroides são atualizados para serem as médias de todas as amostras atribuídas a esse cluster. O seguinte código lida com a etapa de atribuir ao cluster mais próximo:

 

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

 

Observe que usei código desta página, que tem um tipo diferente de algoritmo k-means e muitas outras informações úteis.

Isso funciona calculando a distância entre cada amostra e cada centroide, o que ocorre por meio da linha distances =. O cálculo da distância aqui é a distância euclidiana. Um ponto importante aqui é que o tf.subtract expandirá automaticamente o tamanho dos dois argumentos. Isso significa que ter nossas amostras como uma matriz e os centroides como um vetor de coluna produzirá a subtração de pares entre eles. Para fazer isso, usamos o tf.expand_dims para criar uma dimensão extra para as amostras e os centroides, forçando esse comportamento do tf.subtract.

O próximo trecho de código faz a atualização dos centroides:

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

 

Esse código pega os índices mais próximos para cada amostra e os seleciona como grupos separados usando tf.dynamic_partition. A partir daqui, usamos tf.reduce_mean em um único grupo para encontrar a média desse grupo, formando seu novo centroide. A partir daqui, acabamos de agrupá-los com tf.concat para formar os novos centroides.

Agora, que temos a peça pronta, podemos adicionar essas chamadas ao nosso script (ou criar uma nova):

 

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)

 

Este código irá:

  1. Gerar amostras a partir de centroides iniciais
  2. Escolher aleatoriamente os centroides iniciais
  3. Associar cada amostra ao seu centroide mais próximo
  4. Atualizar cada centroide para ser a média das amostras associadas a ele

Esta é apenas uma única iteração de k-means! Recomendo praticar com os exercícios, que transformam isso em uma versão iterativa.

1) A opção seed passada para generate_samples garante que as amostras geradas "aleatoriamente" sejam consistentes sempre que você executar o script. Não passamos a seed para a função choose_random_centroids, o que significa que esses centroides iniciais são diferentes sempre que o script é executado. Atualize o script para incluir uma nova seed para centroides aleatórios.

2) O algoritmo k-means é executado iterativamente, onde os centroides atualizados da iteração anterior são usados para atribuir clusters, que são então usados para atualizar os centroides, e assim por diante. Em outras palavras, o algoritmo alterna entre chamar assign_to_neophyllum e update_centroids. Atualize o código para executar essa iteração 10 vezes antes de parar. Você descobrirá que os centroides resultantes estão muito mais próximos, em média, com mais iterações de k-means. (Para quem tiver experiência com k-means, um próximo tutorial analisará as funções de convergência e outros critérios de interrupção.)