Entendendo o Algoritmo de Agrupamento K-means em Machine Learning
Agrupamento K-means ou algoritmo K-means ou, algoritmo de agrupamento K-means—bem, antes de mergulharmos no que são os algoritmos de agrupamento, precisamos entender o quão essenciais eles são para as empresas modernas darem sentido aos dados—dados sobre produtos, dados sobre clientes, dados sobre transações e assim por diante.
Em um mundo onde a tecnologia está redefinindo o cenário dos negócios, as empresas gastam milhões de dólares analisando dados para desenvolver padrões que as ajudem a se tornar mais eficientes e aumentar seus lucros. Agrupar objetos com base em atributos é uma das primeiras tarefas envolvidas nesse processo de criação de tais padrões.
Agrupar objetos ajuda as empresas a criar várias estratégias para diversas situações. Clientes, produtos e transações são objetos de interesse central nesses processos. Agrupar clientes com base em seu comportamento ajuda as empresas a criar ofertas personalizadas. Agrupar produtos as ajuda a oferecer escolhas alternativas aos clientes. E agrupar transações as ajuda a identificar padrões incomuns que exigem atenção mais detalhada.
É aqui que entra o agrupamento. O agrupamento é um algoritmo de aprendizado de máquina (ML) não supervisionado que agrupa objetos com base em atributos.
Este artigo abrangente da Zilliz, uma empresa líder em banco de dados vetorial para IA pronta para produção, vai aprofundar você no que é o algoritmo de agrupamento K-means em aprendizado de máquina e como você pode implementá-lo usando Python. Ele também explorará quando usar o algoritmo de agrupamento K-means e dará um exemplo real de agrupamento K-means.
O que é agrupamento?
Agrupamento é o processo de agrupar pontos de dados de modo que cada elemento em um grupo específico seja mais semelhante aos elementos desse grupo do que aos elementos de outros grupos. Agrupamento não se refere a um algoritmo específico. É uma tarefa genérica que pode ser resolvida usando muitos algoritmos. Algoritmos de agrupamento geralmente definem uma métrica para quantificar a similaridade de forma sistemática. O agrupamento é usado em muitos campos, como processamento de imagens, recuperação de informações, mecanismos de recomendação e compressão de dados.
O agrupamento estabelece similaridade com base nos atributos dos objetos que agrupa. Os atributos diferem de acordo com o domínio. Por exemplo, no caso de uma imagem, os atributos são valores de pixels. No caso de um perfil de usuário, os atributos são detalhes como idade, gênero e histórico de compras. No caso de um produto, os atributos são categoria, cor, preço etc. O agrupamento é chamado de tarefa não supervisionada porque não há um processo de treinamento monitorado pelo usuário que envolva a preparação de dados rotulados.
Como funcionam os algoritmos de agrupamento?
A maioria dos algoritmos de agrupamento funciona calculando a similaridade entre todos os pares de amostras. Cada ponto de dados é atribuído ao centroide mais próximo com base em cálculos de distância, o que é uma etapa fundamental no processo de agrupamento.
A capacidade de escalar para o volume do conjunto de dados é um fator essencial a considerar ao decidir sobre o algoritmo de agrupamento para um problema. O tempo de execução aumenta com o número de pares de elementos. Em casos extremos, ele pode variar proporcionalmente ao quadrado do volume de dados.
Quatro abordagens para agrupamento
Existem quatro abordagens comuns para agrupamento: baseada em centroides, baseada em densidade, hierárquica e baseada em distribuição. Vamos analisá-las, uma por uma.
1. Agrupamento baseado em centroides
Este método organiza pontos de dados em clusters individuais sem qualquer hierarquia com base no centroide de todos os pontos de dados no cluster. O centroide é o centro geométrico de um objeto. Em palavras simples, é a média aritmética de todos os pontos que constituem esse objeto em um espaço n-dimensional. Aqui, um cluster é uma coleção de pontos localizados ao redor de um centroide. O clustering baseado em centroide sofre com problemas relacionados a atribuições iniciais e outliers.
2. Clustering Baseado em Densidade
Como o nome sugere, ele calcula a densidade de pontos em uma área e então atribui pontos de dados a clusters onde quer que uma alta densidade seja encontrada. Nesse caso, os clusters podem assumir qualquer forma. O clustering baseado em densidade enfrenta problemas quando os dados têm inerentemente uma alta variância de densidade. Ele não apresenta bom desempenho quando a dimensão dos dados é alta, pois pode ter dificuldade para distinguir entre clusters e clusters vizinhos.
3. Clustering Hierárquico
Este método fornece uma árvore de clusters com a possibilidade de clusters localizados dentro de clusters maiores. Este método se encaixa bem quando os dados exibem uma hierarquia inerente. O clustering hierárquico permite escolher qualquer número de clusters diferentes após a execução, já que o analista pode dividir a árvore no ponto necessário e considerar apenas os clusters após esse ponto.
4. Clustering Baseado em Distribuição
Este método usa o conceito de distribuições de probabilidade para encontrar clusters. Ele assume que a probabilidade de um ponto estar em um cluster diminui quando a distância em relação ao centro do cluster aumenta. Os desenvolvedores devem conhecer a distribuição de seus dados para usar este método de forma eficaz.
O que é K-means Clustering?
O algoritmo de clustering K-means é um algoritmo de clustering baseado em centroide. É um algoritmo de aprendizado não supervisionado, pois não depende de dados rotulados. O ‘K’ em um algoritmo de clustering K-means representa o número de clusters.
K-means é um algoritmo iterativo que calcula a média ou centroide muitas vezes antes de convergir. O tempo para convergir depende da atribuição inicial e do número ideal de clusters usado. Geralmente, a complexidade de tempo do K-means é
onde d é o número de dimensões, k é o número de clusters, e n é o número de k clusters de elementos de dados.
O algoritmo de clustering K-means funciona calculando a distância de cada elemento de dados em relação ao centro geométrico de um cluster. Em seguida, ele reconfigura o cluster se encontrar um ponto pertencente a um cluster específico mais próximo do centroide de outro cluster. Depois disso, ele recalcula o centroide do cluster e repete o processo até que não haja mais reatribuição de clusters.
Vejamos como o algoritmo funciona.
Como funciona o algoritmo de clustering K-means?
O algoritmo de clustering K-means é um processo iterativo que envolve quatro etapas principais. Para entender essas etapas, consideremos um problema de clustering bidimensional. Vamos assumir que os pontos são (x1,y1),(x2,y2), e assim por diante. Vamos começar com um tamanho de cluster de 2.
Atribuição Inicial
Esta etapa atribui cada ponto a um cluster arbitrário. Uma opção é atribuir pontos aleatórios como centroides de cluster e calcular as distâncias entre cada ponto de dados e os centroides.
Os pontos são atribuídos ao cluster cujo centroide está mais próximo deles. A distância entre dois clusters é calculada usando a fórmula da distância euclidiana. Por exemplo, se x3,y3 é um dos centroides atribuídos aleatoriamente, pode-se calcular a distância entre x1,y1 e x3,y3 usando esta fórmula:
Y vs. X
Y vs. X
Os pontos vermelhos e verdes denotam as atribuições iniciais aleatórias de centroides. Com base apenas nesses centroides iniciais dos clusters, a atribuição inicial de clusters aparecerá como mostrado abaixo:
Y vs. X
Y vs. X
Calculando Centroides
Esta etapa envolve recalcular os centroides para cada cluster. O centroide de um cluster é calculado usando a média aritmética de todos os elementos nesse cluster. Por exemplo, digamos que x1,y1, x2,y2 e x3,y3 pertençam a um cluster. O centroide desse cluster é calculado como:
Os pontos em forma de losango, como mostrado abaixo, tornam-se os novos centroides.
Y vs. X
Y vs. X
Reatribuindo Clusters
Uma vez encontrados os novos centroides para todos os três clusters, a distância entre cada ponto e os novos centroides é recalculada. Se algum dos pontos estiver localizado mais perto do centroide de um cluster ao qual está atualmente atribuído, os pontos são reatribuídos.
Y vs. X
Y vs. X
Convergência
Após a reatribuição dos clusters, os centroides são calculados novamente, e o processo se repete. O cálculo dos centroides e a reatribuição dos clusters são executados até que não haja mais novas reatribuições. A tarefa de clustering convergida, neste caso, aparecerá como mostrado abaixo:
Y vs. X
Y vs. X
Escolhendo o Número De Clusters
Dois métodos comumente usados para escolher o número ideal de clusters são o método do cotovelo e o método da silhueta.
Método do Cotovelo
O Método do Cotovelo calcula uma métrica chamada WCSS (Within Cluster Sum of Squares). WCSS é a soma dos quadrados da distância de cada ponto ao centroide de seu cluster mais próximo acima. O gráfico de WCSS em relação ao número de clusters é usado como indicação para selecionar o número ideal de clusters.
Os desenvolvedores executam o clustering K-means para contagens de clusters de 1 a n e, em seguida, calculam o WCSS para cada uma dessas execuções. O WCSS será mais alto para uma execução com um único cluster e diminui quando o número de clusters aumenta. O ponto em que o WCSS exibe uma curva acentuada, como o cotovelo de um braço, é considerado o número ótimo ideal de clusters.
Elbow Method
Método do Cotovelo
Método da silhueta
Este método tenta entender a extensão da similaridade de um objeto com outros membros do mesmo cluster e a extensão da separação dos objetos de outros clusters. A pontuação de silhueta para um ponto é calculada combinando a distância média desse ponto em relação a outros pontos no cluster (a) e a distância média desse ponto em relação a todos os pontos que pertencem a outros clusters (b), incluindo clusters vizinhos. Uma vez que a e b são encontrados, a pontuação de silhueta para um ponto é calculada como
A pontuação de cada ponto é então calculada em média para encontrar a pontuação de silhueta. A pontuação é calculada para todos os candidatos à contagem ideal e, então, aquele com os k pontos e a pontuação mais alta é selecionado como a contagem ideal.
Silhouette Method
Método da Silhueta
Um Exemplo Real do Algoritmo de Clustering K-means (Implementando Clustering K-means com Python)
Este tutorial demonstra como implementar clustering K-means usando Python e encontrar o tamanho ideal do cluster. Para fazer isso, vamos assumir uma declaração de problema comum no domínio de e-commerce. Agrupar clientes com base em seus atributos demográficos e hábitos de consumo é uma tarefa comum no domínio de e-commerce. Para simplificar o exemplo de clustering K-means, usaremos dois atributos aqui: a idade do cliente e o valor médio gasto por mês.
- Para fazer isso, vamos usar uma biblioteca de machine learning em Python chamada scikit-learn e uma biblioteca de plotagem chamada matplotlib. Primeiro, inicialize as bibliotecas usando as instruções de importação fornecidas abaixo:
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette\_score
from sklearn.preprocessing import StandardScaler
- O próximo passo é definir o quadro de dados de entrada. Aqui, o primeiro atributo é a idade e o segundo atributo é o gasto médio mensal em rúpias indianas (INR). Para simplificar, vamos inicializar o array no próprio código. Temos 16 pontos de dados aqui:
raw\_features = np.array([[22,200],[24,200],[24,200],[20,800],[24,800],[24,800],[25,200],[54,200],[24,200],[54,200],[50,800],[53,800],[24,800],[55,800],[53,800],[50,800]])
- Em seguida, você normalizará os pontos de dados, para que a variação em um atributo não sobreponha as variações em outros atributos.
scaler = StandardScaler()
features = scaler.fit\_transform(raw\_features)
- Implemente um loop for para testar o agrupamento K-means para o número de clusters variando de 2 a 6. Em seguida, calcularemos a soma dos quadrados e a plotaremos em relação ao número de clusters para identificar o número ideal de clusters.
sse = []
s\_scores=[]
for i in range(2,6):
kmeans = KMeans(init = **"random"** ,n\_clusters = i,n\_init = 10,max\_iter = 300,random\_state = 42)
kmeans.fit(features)
sse.append(kmeans.inertia\_)
s\_scores.append(silhouette\_score(features, kmeans.labels\_))
- Use a biblioteca matplotlib para plotar a soma dos quadrados em relação ao número de clusters.
plt.style.use( **"fivethirtyeight"** )
plt.plot(range(1, 6), sse)
plt.xticks(range(1, 6))
plt.xlabel( **"Number of Clusters"** )
plt.ylabel( **"SSE"** )
plt.show()
- Executar o código acima resultará em um gráfico que podemos usar para identificar o número ideal de clusters.
Agrupamento K-means
Algoritmo de agrupamento K-means
O gráfico de dispersão acima mostra um 'cotovelo' distinto em 4. Portanto, o número ideal de clusters aqui é 4. Com algum conhecimento de domínio, um cientista de dados pode explicar esse número como quatro combinações - clientes de Baixa Idade Alto Gasto, Baixa Idade Baixo Gasto, Alta Idade Alto Gasto e Alta Idade Baixo Gasto. Mas tais explicações nem sempre são possíveis, e o número ideal de clusters varia com base nas especificações do problema.
Isso é tudo o que há para executar o agrupamento K-means em Python. Os frameworks scikit-learn e matplotlib tornam muito fácil usar agrupamento em Python.
Quando usar o Algoritmo de Agrupamento K-Means
Então, como aprendemos, o agrupamento é um algoritmo de aprendizado de máquina não supervisionado que ajuda a agrupar objetos com base na similaridade. Ele é amplamente usado em muitos domínios da indústria para análise exploratória de dados.
Ele é útil em áreas como segmentação de clientes, mecanismos de recomendação e busca por similaridade. Dito isso, o algoritmo de agrupamento K-means não é a única técnica que pode ser usada para resolver esses problemas. Outra maneira de resolver tal problema é gerar embeddings vetoriais para cada objeto com base em seus atributos.
Redes de treinamento baseadas em deep learning podem gerar embeddings multidimensionais para objetos com um grande número de atributos. Esses embeddings, combinados com um bom banco de dados vetorial, podem resolver problemas baseados em similaridade com muito mais controle.
Se você está trabalhando em tais problemas, confira a Zilliz. Ela oferece uma solução completa para desafios no tratamento de dados não estruturados, especialmente para empresas que criam aplicações de IA/ML que aproveitam a busca por similaridade vetorial.
A Zilliz criou o Milvus, um popular banco de dados vetorial de código aberto amplamente reconhecido por mais de mil usuários empresariais em todo o mundo. A empresa também oferece um serviço de banco de dados vetorial totalmente gerenciado, Zilliz Cloud, que permite às empresas experimentar todo o poder do Milvus sem o incômodo de criar e gerenciar infraestrutura.
Se você quer saber: o que é um banco de dados vetorial? - você pode conferir o guia detalhado. Procurando mais informações sobre tópicos relacionados? Confira esta explicação sobre Busca Aproximada do Vizinho Mais Próximo (ANNS). Quer saber mais sobre como a Zilliz pode ajudar você? Tudo o que você precisa fazer é clicar aqui e perguntar!
Continue lendo
Expanding Our Global Reach: Zilliz Cloud Launches in Azure Central India
Zilliz Cloud expands to Azure Central India. This new region helps customers meet compliance, reduce latency, and optimize cloud costs when building AI applications.
Demystifying the Milvus Sizing Tool
Explore how to use the Sizing Tool to select the optimal configuration for your Milvus deployment.
Optimizing Embedding Model Selection with TDA Clustering: A Strategic Guide for Vector Databases
Discover how Topological Data Analysis (TDA) reveals hidden embedding model weaknesses and helps optimize vector database performance.