10. Algoritmo de Agrupamento K-Means
Atualizado em: 25 de marços de 2024
Por: Nelson H. Koshoji
10.1 Definição
O algoritmo K-means é uma das técnicas de aprendizado de máquina não supervisionado mais utilizadas para realizar a tarefa de agrupamento (clustering). O objetivo principal do K-means é dividir um conjunto de dados em K grupos distintos, de modo que os pontos de dados dentro de cada grupo sejam o mais semelhantes possível, enquanto os grupos são o mais diferentes possível entre si. Esta semelhança é frequentemente calculada usando a distância Euclidiana, embora outras métricas também possam ser aplicadas.
Funcionamento do Algoritmo
O funcionamento do algoritmo K-means pode ser descrito nas seguintes etapas:
Inicialização: Primeiramente, são escolhidos K centros de clusters (centroides) aleatoriamente dentre os pontos de dados. A escolha desses pontos pode afetar significativamente os resultados do algoritmo, e existem métodos como o K-means++ que procuram otimizar essa escolha inicial.
Atribuição: Cada ponto de dado é atribuído ao centroide mais próximo, com base na distância Euclidiana. Isso forma K clusters preliminares.
Atualização: Com os grupos formados, calcula-se o centroide de cada um deles, que é o ponto médio de todos os pontos no cluster. Esse novo centroide se torna o novo centro do cluster.
Iteração: Os passos 2 e 3 são repetidos até que uma condição de parada seja atingida. Geralmente, o algoritmo termina quando os centroides não mudam significativamente entre as iterações, ou após um número pré-definido de iterações, ou ainda quando a mudança na soma dos quadrados das distâncias dentro dos grupos é menor que um limiar.
Características e Desafios
Escolha de K: Um dos maiores desafios ao utilizar o K-means é decidir o valor de K, ou seja, o número de clusters. Métodos como o “Elbow Method” (Método do Cotovelo) ou análises de silhueta são frequentemente utilizados para ajudar nessa escolha.
Sensibilidade a Outliers: O K-means pode ser sensível a outliers, pois eles podem distorcer significativamente a posição dos centroides.
Inicialização: A escolha inicial dos centroides pode levar a resultados diferentes, o que significa que o algoritmo pode encontrar mínimos locais. Métodos como o K-means++ procuram mitigar esse problema.
Limitações: O K-means assume que os clusters são esféricos e de tamanho similar, o que pode não ser verdadeiro para todos os conjuntos de dados.
Aplicações
O K-means tem uma ampla gama de aplicações, incluindo:
- Segmentação de mercado: agrupar clientes com características similares.
- Organização de bibliotecas de documentos: agrupar documentos com temas similares.
- Detecção de anomalias: identificar padrões de dados que não se encaixam nos clusters formados.
- Compressão de imagem: reduzir o número de cores em uma imagem agrupando cores similares.
10.2 Exemplo
# Bibliotecas
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
# Gerando um conjunto de dados sintético
n_samples = 300
random_state = 42
X, _ = make_blobs(n_samples=n_samples, centers=4, cluster_std=0.60, random_state=random_state)
# Aplicando o K-means
k = 4 # Número de clusters
kmeans = KMeans(n_clusters=k, random_state=random_state)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
# Visualizando os pontos e os centros dos clusters
plt.figure(figsize=(12, 8))
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap=’viridis’)
centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c=’red’, s=200, alpha=0.5, marker=’X’)
plt.title(‘Visualização dos Clusters e Centroides’)
plt.xlabel(‘Feature 1’)
plt.ylabel(‘Feature 2’)
plt.show()