Aula 02 - K-means Clustering

1- Introdução


Nessa aula iremos discutir o que é o k-means e como implementar um exemplo simples utilizando o scikit-learn. Em mineração de dados, agrupamento k-means é um método de Clustering que objetiva particionar n observações dentre k grupos onde cada observação pertence ao grupo mais próximo da média. Isso resulta em uma divisão do espaço de dados em um Diagrama de Voronoi.

O problema é computacionalmente difícil (NP-difícil), no entanto, existem algoritmos heurísticos eficientes que são comumente empregados e convergem rapidamente para um local optimum. Estes são geralmente semelhantes ao algoritmo de maximização da expectativa para misturas de distribuições gaussianas através de uma abordagem de refinamento iterativo utilizado por ambos os algoritmos. Além disso, ambos usam os centros de clusters para modelar dados, no entanto, a clusterização k-means tende a encontrar clusters de extensão espacial comparáveis enquanto o mecanismo de maximização da expectativa permite ter diferentes formas.

2- Breve história do algoritmo


O termo "k-means" foi empregado primeiramente por James MacQueen em 1967, embora a ideia remonta a Hugo Steinhaus em 1957. O "Standard algorithm" foi proposto primeiramente por Stuart Lloyd em 1957 como uma técnica para modulação por código de pulso, embora não tenha sido publicada fora dos laboratórios Bell até 1982. Em 1965, E.W.Forgy publicou essencialmente o mesmo método, é por isso que é por vezes referido também como Lloyd-Forgy. Uma versão mais eficiente foi proposta e publicada em Fortran por Hartigan e Wong, no período entre 1975 e 1979.


Esse trecho foi retirado do site de Diego Nogare

3- Ideia geral do algoritmo

Para entender o funcionamento vamos separar em 2 clusters e entender os passos que o algoritmo K-Means faz como os dados para convergir em um resultado. Neste caso o K será igual a 2, criando os 2 clusters que estamos buscando. O K, de K-Means, é a quantidade de centróides (pontos centrais dos grupos) que serão criados e ajudará a encontrará a similaridade dos dados.

Uma das formas de iniciar o processo é o algoritmo inserir o K pontos (centróides) aleatórios iniciais. Pode ser qualquer lugar do plano, para em seguida começar as iterações e encontrar os resultados.

Veja dois pontos aleatórios criados no gráfico, e uma linha tracejada que é calculada aproximadamente na metade da distância dos pontos Vermelho e Azul. Com este segmento, os ítens que estão plotados acima da linha tracejada fazem parte do grupo vermelho e os de baixo da linha fazem parte do grupo azul.



A primeira iteração do algoritmo é calcular a distância média de todos os pontos que estão atrelados ao centróide, e então mudar a posição do centróide para o novo ponto que foi calculado, que é a distância média de todos os pontos que se ligaram à aquele centróide. Essa mudança de posição do centróide pode alterar os itens que fazem parte daquele grupo. Veja isso na imagem abaixo:







Reparem que após a iteração do cálculo da média, alguns pontos mudaram de centróide, os pontos que estão marcados em verde passaram do centróide azul para o vermelho, e o que está marcado em azul passou do centróide vermelho para o azul. Essa iteração de cálculo da média da distância dos pontos até o centróide ocorre em loop até que nenhum ponto mude de centróide, isso acontece quando os centróides param de se mover porque já estão na posição central da distância entre os pontos.







Veja que entre a penúltima iteração e esta não ouve mais mudança de pontos entre o gráfico e o centróide, fazendo com que o algoritmo K-Means pare sua execução chegando ao resultado esperado e criando dois grupos. Assim, quando um novo item for incluído no gráfico, ele já terá um grupo que atende aquela região e o computador já saberá do que se trata o dado novo.

Escolhendo a quantidade de K (clusters) no algoritmo
Como falado alguns parágrafos atrás, o Elbow Method é uma das formas usadas. Ele tem esse nome por se parecer com o formato de um “braço” e nós sempre procurarmos o “cotovelo” pra definir que este é o número aceitável de K (clusters) a serem criados com base nos dados da amostra. Este método vai crescendo a quantidade de clusters a partir de 1 e analisando o resultado melhorado a cada incremento. Quando o benefício parar de ser relevante (um salto entre uma quantidade de cluster e a próxima quantidade) ele entra em um modelo platô, no qual a diferença da distância é quase insignificante. É neste momento que entende-se que o algoritmo é relevante com aquela quantidade de K e então ele deve ser usado pra segmentar os dados do gráfico.

Depois de executar o código do algoritmo do Elbow Method e olhando para os dados que estamos apresentando como exemplo, um bom número de K para ele é o número 4.



Rodando o algoritmo com 4 centróides, é possível ver a transformação acontecendo nesta segmentação:




4- Implementando um exemplo do K-means em python

A implementação mais básica do k-means que contém um vetor [X] que contém os pontos amostrados. O objetivo é classificar os pontos amostrados em clusters indicados pela variável K.

from sklearn.cluster import KMeans
import numpy as np

X = np.array([[1, 2], [1, 4], [1, 0],[4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_
array([0, 0, 0, 1, 1, 1])
kmeans.predict([[0, 0], [4, 4]])
array([0, 1])
kmeans.cluster_centers_
array([[1., 2.],
       [4., 2.]])


5- Qual a diferença entre o K-means e o KNN

O KNN faz parte do tipo de aprendizado denominado "supervisionado", esse aprendizado precisa de exemplos previamente classificados para prever qual será a classificação de uma nova amostra.  O K-means busca dividir em grupos amostras de acordo com um número de clusters pré-determinado, sendo assim, não precisa de exemplos pré-classificados.




Aula 02 - K-means Clustering Aula 02 - K-means Clustering Reviewed by Vinicius dos Santos on 06:17:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!