Algoritmos de Clustering - Algoritmo K-means

Introdução ao Algoritmo K-Means

O algoritmo de agrupamento K-means calcula os centróides e itera até encontrar o centróide ideal. Ele assume que o número de clusters já é conhecido. Também é chamadoflat clusteringalgoritmo. O número de clusters identificados a partir de dados por algoritmo é representado por 'K' em K-médias.

Nesse algoritmo, os pontos de dados são atribuídos a um cluster de forma que a soma da distância quadrada entre os pontos de dados e o centróide seja mínima. Deve ser entendido que menos variação dentro dos clusters levará a mais pontos de dados semelhantes dentro do mesmo cluster.

Trabalho de algoritmo K-Means

Podemos entender o funcionamento do algoritmo de agrupamento K-Means com a ajuda das seguintes etapas -

Step 1 - Primeiro, precisamos especificar o número de clusters, K, que precisam ser gerados por este algoritmo.
Step 2- Em seguida, selecione aleatoriamente K pontos de dados e atribua cada ponto de dados a um cluster. Em palavras simples, classifique os dados com base no número de pontos de dados.
Step 3 - Agora ele irá calcular os centróides do cluster.
Step 4 - Em seguida, continue repetindo o seguinte até encontrarmos o centróide ideal, que é a atribuição de pontos de dados aos clusters que não estão mais mudando -

4.1 - Primeiro, a soma da distância quadrada entre os pontos de dados e os centróides seria calculada.

4.2 - Agora, temos que atribuir cada ponto de dados ao cluster que está mais próximo do que outro cluster (centróide).

4.3 - Por fim, calcule os centróides para os clusters, tomando a média de todos os pontos de dados desse cluster.

K-means segue Expectation-Maximizationabordagem para resolver o problema. A etapa de expectativa é usada para atribuir os pontos de dados ao cluster mais próximo e a etapa de maximização é usada para calcular o centróide de cada cluster.

Ao trabalhar com o algoritmo K-means, precisamos cuidar das seguintes coisas -

Ao trabalhar com algoritmos de agrupamento incluindo K-Means, é recomendado padronizar os dados porque tais algoritmos usam medição baseada em distância para determinar a similaridade entre pontos de dados.
Devido à natureza iterativa de K-Means e inicialização aleatória de centróides, K-Means pode ficar em um ótimo local e pode não convergir para o ótimo global. É por isso que é recomendado usar inicializações diferentes de centróides.

Implementação em Python

Os dois exemplos a seguir de implementação do algoritmo de agrupamento K-Means nos ajudarão em seu melhor entendimento -

Exemplo 1

É um exemplo simples para entender como funciona o k-means. Neste exemplo, vamos primeiro gerar um conjunto de dados 2D contendo 4 blobs diferentes e depois aplicar o algoritmo k-means para ver o resultado.

Primeiro, começaremos importando os pacotes necessários -

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeans

O código a seguir irá gerar o 2D, contendo quatro blobs -

from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=400, centers=4, cluster_std=0.60, random_state=0)

A seguir, o código a seguir nos ajudará a visualizar o conjunto de dados -

plt.scatter(X[:, 0], X[:, 1], s=20);
plt.show()

Em seguida, faça um objeto de KMeans juntamente com o número de clusters, treine o modelo e faça a previsão da seguinte maneira -

kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)

Agora, com a ajuda do código a seguir, podemos plotar e visualizar os centros do cluster escolhidos pelo estimador Python k-means -

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=20, cmap='summer')
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='blue', s=100, alpha=0.9);
plt.show()

Exemplo 2

Vamos passar para outro exemplo em que vamos aplicar o agrupamento K-means em um conjunto de dados de dígitos simples. K-means tentará identificar dígitos semelhantes sem usar as informações do rótulo original.

Primeiro, começaremos importando os pacotes necessários -

%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np
from sklearn.cluster import KMeans

Em seguida, carregue o conjunto de dados de dígitos do sklearn e faça dele um objeto. Também podemos encontrar o número de linhas e colunas neste conjunto de dados da seguinte forma -

from sklearn.datasets import load_digits
digits = load_digits()
digits.data.shape

Resultado

(1797, 64)

A saída acima mostra que este conjunto de dados está tendo 1797 amostras com 64 recursos.

Podemos realizar o agrupamento como fizemos no Exemplo 1 acima -

kmeans = KMeans(n_clusters=10, random_state=0)
clusters = kmeans.fit_predict(digits.data)
kmeans.cluster_centers_.shape

Resultado

(10, 64)

A saída acima mostra que K-means criou 10 clusters com 64 recursos.

fig, ax = plt.subplots(2, 5, figsize=(8, 3))
centers = kmeans.cluster_centers_.reshape(10, 8, 8)
for axi, center in zip(ax.flat, centers):
   axi.set(xticks=[], yticks=[])
   axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)

Resultado

Como saída, obteremos a imagem a seguir mostrando os centros de clusters aprendidos por k-means.

As seguintes linhas de código corresponderão aos rótulos de cluster aprendidos com os rótulos verdadeiros encontrados neles -

from scipy.stats import mode
labels = np.zeros_like(clusters)
for i in range(10):
   mask = (clusters == i)
   labels[mask] = mode(digits.target[mask])[0]

Em seguida, podemos verificar a precisão da seguinte maneira -

from sklearn.metrics import accuracy_score
accuracy_score(digits.target, labels)

Resultado

0.7935447968836951

A saída acima mostra que a precisão está em torno de 80%.

Vantagens e desvantagens

Vantagens

A seguir estão algumas vantagens dos algoritmos de agrupamento K-Means -

É muito fácil de entender e implementar.
Se tivermos um grande número de variáveis, então, K-médias seria mais rápido do que o agrupamento hierárquico.
No recálculo de centróides, uma instância pode alterar o cluster.
Clusters mais compactos são formados com K-médias em comparação com o clustering hierárquico.

Desvantagens

A seguir estão algumas desvantagens dos algoritmos de agrupamento K-Means -

É um pouco difícil prever o número de clusters, ou seja, o valor de k.
A saída é fortemente impactada por entradas iniciais, como número de clusters (valor de k).
A ordem dos dados terá um forte impacto na produção final.
É muito sensível ao redimensionamento. Se redimensionarmos nossos dados por meio de normalização ou padronização, a saída mudará completamente. A saída final.
Não é bom fazer um trabalho de cluster se os clusters têm uma forma geométrica complicada.

Aplicações do algoritmo de clustering K-Means

Os principais objetivos da análise de cluster são -

Para obter uma intuição significativa dos dados com os quais estamos trabalhando.
Agrupe e preveja onde diferentes modelos serão construídos para diferentes subgrupos.

Para cumprir os objetivos mencionados acima, o agrupamento K-means está funcionando bem o suficiente. Ele pode ser usado nas seguintes aplicações -

Segmentação de mercado
Clustering de documentos
Segmentação de imagem
Compressão de imagem
Segmentação de clientes
Analisando a tendência de dados dinâmicos

↰ Previous page Next page ↱