K-means

Na aprendizagem de máquina não supervisionada temos algoritmos que trabalham com dados que não possuem classificações prévias para treinamento. Assim, uma das formas de extrair informações desses dados é através da procura por grupos de dados que são semelhantes entre si. Chamamos esse tipo de tarefa de clusterização e os grupos encontrados de clusters.

O K-means é um dos algoritmos de clusterização mais populares. Ele procura por um número predeterminado de clusters através da definição dos seus centroides (centros geométricos dos clusters).

Dados

Para entender o funcionamento do algoritmo, vamos utilizar o dataset apresentado a seguir. Nele temos exemplos com duas características, uma representada pelo eixo X e outra pelo eixo Y.

In [1]:
from sklearn.datasets.samples_generator import make_blobs
from bokeh.io import show, output_notebook
from bokeh.plotting import figure
output_notebook()

X, _ = make_blobs(n_samples=300, centers=4, random_state=20)

x = X[:, 0]
y = X[:, 1]

p = figure(plot_width=600, plot_height=360)
p.circle(x, y, radius=0.1)
show(p, notebook_handle=True)
Loading BokehJS ...
Out[1]:

<Bokeh Notebook handle for In[1]>

No gráfico acima, todos os pontos são da cor azul, ou seja, não existe identificação nos dados que separem os exemplos em grupos. Entretanto, note que visualmente é possível enxergar quatro diferentes agrupamentos de pontos. Assim, mesmo todos os pontos sendo iguais (cor azul) a semelhança de acordo com as características nos traz uma informação potencialmente valiosa para o entendimento dos dados.

Algoritmo

O primeiro passo para execução do algoritmo K-means é definir quantos clusters deverão ser descobertos. Usando os dados apresentados anteriormente, vamos definir a procura por 4 clusters. Cada cluster é representado pelo seu centroide, assim, teremos 4 centroides. No início do algoritmo os centroides são posicionados aleatoriamente no espaço onde estão representados os dados de treinamento.

O gráfico a seguir mostra os dados com 4 centroides posicionados aleatoriamente. Os centroides são representados por triângulos.

In [2]:
import numpy as np

np.random.seed(1)  # definindo o seed para tornar os resultados do notebook sempre iguais
centroids_x = np.random.uniform(-10, 10, 4)

np.random.seed(3)  # definindo o seed para tornar os resultados do notebook sempre iguais
centroids_y = np.random.uniform(-2, 10, 4)

centroids = []
for i in range(len(centroids_x)):
    centroids.append((centroids_x[i], centroids_y[i]))

p = figure(plot_width=600, plot_height=360)
p.circle(x, y, radius=0.1)
p.triangle(centroids[0][0], centroids[0][1], size=12, color="red", line_color="black")
p.triangle(centroids[1][0], centroids[1][1], size=12, color="green", line_color="black")
p.triangle(centroids[2][0], centroids[2][1], size=12, color="orange", line_color="black")
p.triangle(centroids[3][0], centroids[3][1], size=12, color="purple", line_color="black")
show(p, notebook_handle=True)
Out[2]:

<Bokeh Notebook handle for In[2]>

Com os centroides inicializados, no passo número 2 do algoritmo, verifica-se para cada ponto, qual o centroide mais próximo. Assim, é definido que o ponto pertence ao grupo representado pelo centroide mais próximo.

Para calcular a proximidade entre um ponto e um centroide, basta calcular a distância euclidiana entre eles. Para pontos em duas dimensões como os representados no nosso exemplo, a fórmula da distância euclidiana é:

$$d(a, b) = \sqrt{(a_x - b_x)^2 + (a_y - b_y)^2}$$

Onde $a$ e $b$ são dois pontos, $a_x$ é a coordenada X do ponto $a$ e $a_y$ é a coordenada Y do ponto $a$, e $b_x$ é a coordenada X do ponto $b$ e $b_y$ é a coordenada Y do ponto $b$.

A função a seguir calcula a distância entre um ponto e um centroide:

In [3]:
import math

def distance(centroid, point):
    x_diff = centroid[0] - point[0]
    y_diff = centroid[1] - point[1]
    
    return math.sqrt(x_diff**2 + y_diff**2)

distance(centroids[0], X[0])
Out[3]:
10.862127336783487

A seguir temos uma função que itera sobre os dados de treinamento para definir o grupo de cada ponto de acordo com centroide mais próximo.

In [4]:
def get_groups(centroids, points):
    groups = []

    for x_i in points:
        distances = []

        for c_i in centroids:
            distances.append(distance(c_i, x_i))

        groups.append(np.argmin(distances))
        
    return groups
    
groups = get_groups(centroids, X)
print(groups)
[1, 1, 1, 1, 1, 3, 1, 0, 1, 1, 1, 3, 0, 1, 1, 1, 2, 2, 1, 2, 3, 2, 3, 3, 2, 2, 2, 0, 3, 1, 0, 2, 2, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 3, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 1, 3, 2, 1, 1, 3, 1, 0, 2, 3, 1, 2, 1, 3, 2, 1, 1, 3, 3, 2, 1, 0, 0, 3, 1, 0, 1, 1, 1, 2, 2, 3, 1, 1, 0, 3, 3, 2, 3, 1, 3, 3, 1, 0, 1, 3, 1, 1, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 3, 2, 2, 1, 0, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 0, 1, 1, 1, 2, 3, 3, 1, 1, 2, 1, 3, 2, 0, 2, 3, 2, 2, 0, 3, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 0, 1, 1, 3, 1, 2, 0, 0, 3, 2, 1, 2, 1, 3, 0, 1, 0, 3, 1, 2, 1, 3, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 3, 3, 2, 1, 1, 1, 1, 2, 2, 1, 1, 3, 0, 1, 3, 3, 1, 1, 3, 1, 0, 3, 1, 2, 2, 1, 2, 3, 0, 3, 1, 0, 2, 0, 3, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1, 1, 2, 3, 1, 3, 1, 1, 1, 1, 3, 0, 3]

A lista groups contém a informação sobre a que centroide os pontos foram atribuídos. Cada centroide possui um número, sendo o vermelho o 0, o verde o 1, o laranja o 2 e o roxo o 3.

Assim, um número $J$ na posição $I$ da lista representa que o ponto $I$ foi atribuído ao grupo do centroide $J$. Por exemplo, no resultado acima, a posição 0 da lista tem o valor 1, ou seja, o ponto 0 do dataset faz parte do cluster 1.

Com esses dados em mãos, vamos agora mostrar o gráfico com os pontos coloridos de acordo com os seus centroides.

In [5]:
def plot_chart(points, centroids, groups):
    colors = ["red", "green", "orange", "purple"]
    chart_colors = [colors[x] for x in groups]
    
    x = points[:, 0]
    y = points[:, 1]

    p = figure(plot_width=600, plot_height=360)
    p.circle(x, y, radius=0.1, color=chart_colors)
    p.triangle(centroids[0][0], centroids[0][1], size=12, color="red", line_color="black")
    p.triangle(centroids[1][0], centroids[1][1], size=12, color="green", line_color="black")
    p.triangle(centroids[2][0], centroids[2][1], size=12, color="orange", line_color="black")
    p.triangle(centroids[3][0], centroids[3][1], size=12, color="purple", line_color="black")
    show(p, notebook_handle=True)
    
plot_chart(X, centroids, groups)

O passo número 3 do algoritmo é o reposicionamento dos centroides. Para cada centroide, vamos calcular a média dos pontos que fazem parte do grupo que ele determina. O valor encontrado é a nova posição do centroide.

O código a seguir calcula a nova posição dos centroides. A função points_mean calcula a média dos pontos e a função move_centroids itera sobre os dados de treinamento e calcula a nova posição dos centroides.

In [6]:
def points_mean(points):
    sum_x = 0
    sum_y = 0
    total = len(points)

    for point in points:
        sum_x += point[0]
        sum_y += point[1]

    return (sum_x/total, sum_y/total)


def move_centroids(centroids, points, groups):
    points_in_groups = [[] for i in range(len(centroids))]

    for index, group in enumerate(groups):
        points_in_groups[group].append(points[index])
    
    moved_centroids = []
    for p in points_in_groups:
        moved_centroids.append(points_mean(p))
    
    return moved_centroids

centroids = move_centroids(centroids, X, groups)

O gráfico a seguir mostra os centroides reposicionados:

In [7]:
plot_chart(X, centroids, groups)

O resultado não está muito bom, os grupos parecem misturados, entretanto a execução do algoritmo ainda não terminou.

O K-means continua sua execução repetindo o passo 2 (atribuição dos grupos) e o passo 3 (reposicionamento dos centroides), até que no passo 2 não existam mudanças nas atribuições dos grupos.

Vamos repetir o passo 2:

In [8]:
groups = get_groups(centroids, X)
plot_chart(X, centroids, groups)

Note que alguns pontos mudaram de cor, ou seja, eles foram atribuídos a grupos diferentes. Com isso, os centroides também mudarão de posição.

In [9]:
centroids = move_centroids(centroids, X, groups)
plot_chart(X, centroids, groups)

Executando os passos 2 e 3 mais 4 vezes, temos:

In [10]:
from bokeh.layouts import gridplot

plots_grid = [[]]
for i in range(4):
    groups = get_groups(centroids, X)
    centroids = move_centroids(centroids, X, groups)
    
    colors = ["red", "green", "orange", "purple"]
    chart_colors = [colors[x] for x in groups]
    
    p = figure(plot_width=450, plot_height=270)
    p.circle(x, y, radius=0.1, color=chart_colors)
    p.triangle(centroids[0][0], centroids[0][1], size=12, color="red", line_color="black")
    p.triangle(centroids[1][0], centroids[1][1], size=12, color="green", line_color="black")
    p.triangle(centroids[2][0], centroids[2][1], size=12, color="orange", line_color="black")
    p.triangle(centroids[3][0], centroids[3][1], size=12, color="purple", line_color="black")
    
    if (len(plots_grid[-1]) == 2):
        plots_grid.append([])
    
    plots_grid[-1].append(p)
    
p = gridplot(plots_grid)
show(p)

Nos últimos dois gráficos, chegamos a um ponto de convergência. Note que os grupos não mudam nos dois gráficos de baixo. Com isso, o K-means pode ser terminado e os quatro clusters foram encontrados.

Limitações

Inicialização aleatória

O resultado final do K-means é dependente da inicialização aleatória dos centroides. Por isso, o seu resultado pode variar a cada execução. No exemplo anterior, os quatro clusters encontrados são coerentes, mas não podemos garantir que esses quatro clusters sempre serão encontrados.

Vamos inicializar os centroides de uma maneira diferente:

In [11]:
np.random.seed(4)
centroids_x = np.random.uniform(-10, 10, 4)

np.random.seed(10)
centroids_y = np.random.uniform(-2, 10, 4)

centroids2 = []
for i in range(len(centroids_x)):
    centroids2.append((centroids_x[i], centroids_y[i]))

p = figure(plot_width=600, plot_height=360)
p.circle(x, y, radius=0.1)
p.triangle(centroids2[0][0], centroids2[0][1], size=12, color="red", line_color="black")
p.triangle(centroids2[1][0], centroids2[1][1], size=12, color="green", line_color="black")
p.triangle(centroids2[2][0], centroids2[2][1], size=12, color="orange", line_color="black")
p.triangle(centroids2[3][0], centroids2[3][1], size=12, color="purple", line_color="black")
show(p, notebook_handle=True)
Out[11]:

<Bokeh Notebook handle for In[11]>

Abaixo temos a evolução dos clusters a cada iteração do algoritmo:

In [12]:
plots_grid = [[]]
for i in range(4):
    groups2 = get_groups(centroids2, X)
    centroids2 = move_centroids(centroids2, X, groups2)
    
    colors = ["red", "green", "orange", "purple"]
    chart_colors = [colors[x] for x in groups2]
    
    p = figure(plot_width=450, plot_height=270)
    p.circle(x, y, radius=0.1, color=chart_colors)
    p.triangle(centroids2[0][0], centroids2[0][1], size=12, color="red", line_color="black")
    p.triangle(centroids2[1][0], centroids2[1][1], size=12, color="green", line_color="black")
    p.triangle(centroids2[2][0], centroids2[2][1], size=12, color="orange", line_color="black")
    p.triangle(centroids2[3][0], centroids2[3][1], size=12, color="purple", line_color="black")
    
    if (len(plots_grid[-1]) == 2):
        plots_grid.append([])
    
    plots_grid[-1].append(p)
    
p = gridplot(plots_grid)
show(p)

Perceba que foi criado um grande grupo verde os grupos vermelho e laranja passaram a dividir os pontos do que na execução anterior era um grupo sozinho.

Para resolver o problema da dependência da inicialização dos centroides, uma estratégia utilizada é executar o K-means várias vezes. Após o fim de todas as execuções é possível medir a qualidade do resultado final através da equação de distorção. Quanto menor a distorção, melhores foram os agrupamentos.

Dado que $x^{(i)}$ é o i-ésimo ponto do dataset, que $c_j^{(i)}$ é o centróide $j$ atribuído ao i-ésimo ponto e que existem $m$ pontos no dataset. A distorção é definida por:

$$distorção = \frac{1}{m} \sum_{i=1}^{m} d(x^{(i)}, c_j^{(i)})^2$$

Lembrando que $d(a, b)$ é a distância entre os pontos $a$ e $b$.

Dados os pontos, os centroides e a informação sobre quais pontos fazem parte de quais grupos, a função abaixo calcula a distorção:

In [13]:
def distortion(centroids, points, groups):
    result = 0
    for index, group in enumerate(groups):
        result += (distance(points[index], centroids[group]))**2
        
    return result/len(points)

Os centroides e os grupos atribuídos aos pontos do nosso primeiro exemplo estão armazenados nas variáveis centroids e groups respectivamente. Os centroides e grupos do segundo exemplo estão armazenados nas variáveis centroids2 e groups2 respectivamente.

Calculando a distorção para os dois exemplos temos:

In [14]:
print(distortion(centroids, X, groups))
print(distortion(centroids2, X, groups2))
1.888723131110457
9.215098905694967

Confirmando o que foi analisado visualmente, a distorção do primeiro exemplo é menor que a do segundo. Com isso podemos concluir que os agrupamentos do primeiro exemplo são melhores que o do segundo.

Fronteiras lineares

Ao definir os clusters, o K-means utiliza fronteiras lineares para separar os pontos. Assim, dependendo da organização dos pontos de um dataset, pode ser impossível encontrar grupos de pontos de forma satisfatória.

Abaixo temos um conjunto de pontos, no qual, visualmente, podemos identificar dois grupos. Entretanto, esses grupos não podem ser separados linearmente.

In [15]:
from sklearn.datasets.samples_generator import make_moons

X, _ = make_moons(n_samples=300, noise=0.07, random_state=0)

x = X[:, 0]
y = X[:, 1]

p = figure(plot_width=600, plot_height=360)
p.circle(x, y, radius=0.015)
show(p, notebook_handle=True)
Out[15]:

<Bokeh Notebook handle for In[15]>

Inicializando dois centroides aleatoriamente, temos:

In [16]:
np.random.seed(0)
centroids_x = np.random.uniform(-1, 2, 2)

np.random.seed(0)
centroids_y = np.random.uniform(-0.5, 1, 2)

centroids3 = []
for i in range(len(centroids_x)):
    centroids3.append((centroids_x[i], centroids_y[i]))

p = figure(plot_width=600, plot_height=360)
p.circle(x, y, radius=0.015)
p.triangle(centroids3[0][0], centroids3[0][1], size=12, color="red", line_color="black")
p.triangle(centroids3[1][0], centroids3[1][1], size=12, color="green", line_color="black")
show(p, notebook_handle=True)
Out[16]:

<Bokeh Notebook handle for In[16]>

Executando quatro iterações do algoritmo, temos a seguinte evolução dos grupos encontrados:

In [17]:
plots_grid = [[]]
for i in range(4):
    groups3 = get_groups(centroids3, X)
    centroids3 = move_centroids(centroids3, X, groups3)
    
    colors = ["red", "green"]
    chart_colors = [colors[x] for x in groups3]
    
    p = figure(plot_width=450, plot_height=270)
    p.circle(x, y, radius=0.015, color=chart_colors)
    p.triangle(centroids3[0][0], centroids3[0][1], size=12, color="red", line_color="black")
    p.triangle(centroids3[1][0], centroids3[1][1], size=12, color="green", line_color="black")
    
    if (len(plots_grid[-1]) == 2):
        plots_grid.append([])
    
    plots_grid[-1].append(p)
    
p = gridplot(plots_grid)
show(p)

Note que os clusters encontrados não são exatamente o que era esperado. O K-means limitou-se a dividir os conjuntos através de uma reta. Assim, dependendo do dataset, o K-means pode não ser adequado para encontrar os grupos desejados.