4.5 Algoritmo K-Means

O algoritmo k-médias

O nome "k-médias" é um nome invulgar para um algoritmo. Continua a ler para descobrires o que está por detrás desta escolha.

Para facilitar o acompanhamento da explicação do algoritmo x-médias, vamos utilizar o conjunto de dados mostrado na figura abaixo. Consiste em 100 pares de pontos — imagina que estes representam os valores de dois atributos numéricos.

Esta secção esta associada ao Jupyter Notebook 12-k-means.ipynb. Para acompanhar o conteúdo, clique no link e, em seguida, clique  no botão para abrir o conteúdo no ambiente do Google Colab. Se estiveres a visualizar os notebooks no teu computador local, procura o notebook com o mesmo nome entre os ficheiros e executa-o. Para instruções mais detalhadas, consulta a secção Hands-on Zone e a lição sobre o Jupyter Exercise Notebook.

No material de apoio, poderás gerar tu próprio todas as imagens e animações.

O algoritmo k-médias (k-means) tem como objetivo encontrar k grupos (ou clusters) no conjunto de dados. Os grupos que este algoritmo procura são determinados pelo centróide, uma instância que representa o centro do grupo.

O primeiro passo do algoritmo é a inicialização. Nesta fase, precisamos de selecionar aleatoriamente x centróides. Depois, repetimos os seguintes passos. Para cada instância, calculamos a distância euclidiana até cada um dos x centróides, e associamos a instância ao grupo cujo centróide estiver mais próximo. Após atribuir todas as instâncias, passamos ao passo seguinte. Para cada um dos x grupos, selecionamos novos centróides. Fazemo-lo calculando a média das instâncias que pertencem a cada grupo e declarando esse valor como o novo centróide. Depois disso, voltamos ao passo 1.

O algoritmo de agrupamento termina quando os valores dos centróides estabilizam. Isto significa que, em duas iterações sucessivas, os centróides variam muito pouco — menos do que uma precisão previamente definida.

O próprio algoritmo k-médias não é difícil de programar, por isso vamos fazê-lo juntos. Antes disso, vamos considerar alguns detalhes técnicos:

Uma instância de um conjunto de dados é um par de números, por exemplo (2, -3). Isto significa que um centróide também será um par de números e terá duas coordenadas;

Se (10, 2) e (4, -4) forem duas instâncias de um conjunto de dados, calcularemos a média delas como (10 + 42, 2 − 42) = (7, -1);

Se (0, 0) e (3, 4) forem duas instâncias de um conjunto de dados, calcularemos a distância euclidiana entre elas será (3 − 0)2 + (4 − 0)2.

No conjunto de dados, procuraremos quatro grupos. Mais à frente discutiremos porque escolhemos este número. Por agora, vamos preparar-nos para programar o algoritmo.

A variável k representa o número de grupos. Neste caso, k = 4. Vamos representar os centróides com a variável centroide. Como temos k grupos, isto será um array de comprimento k. Cada centróide, como dissemos, é um par de números, portanto os elementos deste array serão pares de números.

Durante o processo de agrupamento, é necessário registar a que grupo está associada cada instância. Para isso, usaremos rótulos (labels), tal como nas tarefas de classificação. Estes podem ser os valores 0, 1, 2 e 3 — em geral, os valores 0, 1, 2, ..., k-1. Guardaremos todos os rótulos numa série chamada labele_klastera.

Vamos agora introduzir a função generisi_centroide(X, k), que gera os centróides iniciais. Os seus argumentos são o conjunto de instâncias X e o número de grupos k, e a função seleciona aleatoriamente k números do intervalo de 0 a 100 e devolve as instâncias que se encontram nessas posições.

def generate_centroids(X, k):
    N = X.shape[0]
    indices = np.random.randint(low=0, high=N, size=k)
    return X[indices]

Na figura abaixo, os centróides gerados são mostrados. Cada um deles está na cor do aglomerado que representa.

Valores iniciais dos centróides

Agora vamos escrever uma função podeli_podatke(X, centróides, k) para dividir um conjunto de instâncias em clusters. Esta função recebe como argumentos o conjunto de instâncias X, os centróides atuais (centroide) e o número de grupos k. Para cada instância, calculamos a distância até cada um dos centróides, selecionamos o centróide mais próximo e concluímos que a instância pertence ao grupo correspondente a esse centróide.

def divide_data(X, centroids, k):

  # initialize the list of cluster labels
  cluster_labels = []

  # iterate through the dataset instance by instance
  for x in X:

    # initialize the list of distances to centroids
    distances_to_centroids = []

    # then for each centroid ...
    for centroid in centroids:
      # ... calculate the distance between the instance and the centroid
      d = calculate_distance(x, centroid)

      # ... and add it to the list of distances
      distances_to_centroids.append(d)

    # when we have visited all centroids,
    # choose the centroid closest to the instance x
    label = np.argmin(distances_to_centroids)

    # conclude that the instance belongs to the cluster
    # determined by that centroid
    cluster_labels.append(label)

  # the result of the function is an array of cluster labels
  return np.array(cluster_labels)

Na imagem abaixo, podes ver a primeira iteração da divisão de instâncias em grupos (clusters).

Agora vamos escrever uma função izracunaj_nove_centroide(X, labele_klastera, k) que pode calcular os valores de novos centróides com base na divisão atual de instâncias em grupos (clusters). Os seus argumentos são o conjunto de instâncias X, as etiquetas atuais (labele_klastera) e o número de grupos k. Para cada um dos grupos, esta função deve extrair as instâncias que lhe pertencem e, em seguida, calcular a sua média.

def calculate_new_centroids(X, cluster_labels, k):

  # initialize the list of new centroids
  new_centroids = []

  # for each cluster
  for i in range(0, k):

    # ... extract the instances that belong to it
    instance_indices = cluster_labels == i
    instances_in_cluster = X[instance_indices]

    # then calculate the new centroid value
    # by averaging all instances in the cluster
    new_centroid = np.average(instances_in_cluster, axis=0)

    # add the calculated new centroid to the list of all centroids
    new_centroids.append(new_centroid)

  # the result of the function is an array of new centroids
  return np.array(new_centroids)

Os novos centróides são agora apresentados na imagem abaixo. Vais notar que os centróides dos grupos amarelo e roxo se "afastaram" um do outro.

Fica agora por consolidar as tarefas de cada um dos passos numa única função que as repita um número suficiente de vezes. Essa função será chamada izvrsi_klasterovanje(X, k, epsilon = 1e-4, broj_iteracija = 300) em que X representa o conjunto de instâncias, k o número de grupos (clusters), epsilon define a proximidade mínima entre centróides para que o algoritmo pare (isto é, quando os centróides mudam menos do que este valor). Há também um número máximo de iterações max_broj_iteracija que adicionalmente fornecemos um critério de paragem adicional.

def execute_clustering(X, k, epsilon=1e-4, max_iterations=300):

  # step of initializing centroids
  centroids = generate_centroids(X, k)

  # in each iteration of the loop
  for i in range(0, max_iterations):

    # step 1: dividing instances into clusters
    cluster_labels = divide_data(X, centroids, k)

    # step 2: calculating new centroids
    new_centroids = calculate_new_centroids(X, cluster_labels, k)

    # checking stopping criteria
    # if they are met, we stop the algorithm
    if np.linalg.norm(new_centroids - centroids) < epsilon:
      break
    # otherwise, we move to the next iteration
    centroids = new_centroids.copy()

  # the result of the function is the final cluster labels and centroid values
  return cluster_labels, new_centroids

A execução desta função leva-nos também à divisão final do conjunto de instâncias em grupos (clusters), que está representada na figura abaixo.

No caderno de código que acompanha este material, podes também ver uma animação que acompanha esta divisão. Alguns passos dependem de decisões aleatórias (por exemplo, se uma instância estiver igualmente próxima de vários centróides), por isso não te preocupes se alguns valores diferirem ligeiramente.