Explicando o Algoritmo Iterativo K-Means Clustering

Introdução

Neste artigo, examinaremos o algoritmo iterativo de clusterização K-means.

Então, o que exatamente é clustering?

Podemos pensar nisso como um amplo conjunto de técnicas que agrupam certas observações, por exemplo: poderia ser a criação de subgrupos dentro de um determinado conjunto de dados. Este algoritmo procura agrupar as observações em grupos distintos, de modo que, em teoria, as observações no mesmo grupo devem ser semelhantes entre si, enquanto as observações dentro de grupos diferentes são classificadas como dissimilares entre si.

K-Clustering

K-means clustering é um método bem conhecido usado no aprendizado de máquina e reside no ramo da aprendizagem não supervisionada, o que significa essencial que você extraia inferências de dados com respostas não rotuladas.

Dado um conjunto de observações, o agrupamento K-means tentará agrupar as observações em um número pré-especificado de k clusters distintos e não sobrepostos. Para realizar o clustering K-means, devemos primeiro decidir o número de clusters que queremos. Isso permitirá que o algoritmo atribua cada observação a exatamente um dos k clusters.

Vamos dar uma olhada em como o algoritmo iterativo de clusterização K-means funciona passo a passo:

Defina o número de k clusters que você deseja e gere aleatoriamente seus respectivos pontos centrais dentro do domínio de dados.

Calcule a distância entre a observação e cada ponto central e, em seguida, classifique essa observação em um grupo cujo centro é mais próximo a ela.

Com base nessas observações classificadas, recalculamos o centro do grupo tomando a média de todos os vetores no grupo.

As etapas 2 e 3 são repetidas para um número definido de iterações ou quando a convergência é atingida. Vejamos um exemplo para entender melhor esse conceito.

Onde devo configurar minhas novas cafeterias?
Digamos que queremos abrir três novas cafeterias em uma cidade chamada George – tudo isso é hipoteticamente pensante. No entanto, precisamos definir os principais locais para que os nossos cafés prosperem.

Descrito abaixo, temos um conjunto de dados de todas as pessoas que fazem uso de cafeterias regularmente na área circundante:

Embora isso fosse relativamente fácil de detectar com o olho humano, o computador não pode ver isso, e nem sempre pode ser um conjunto de dados tão simples. Portanto, nós plotamos aleatoriamente os 3 pontos centrais no conjunto de dados (representado pelas estrelas).

Agora que plotamos os pontos centrais, podemos passar para a etapa 2. Na etapa 2, precisamos agrupar cada observação para um determinado ponto central, e fazemos isso calculando a distância entre cada observação e cada ponto central. Feito isso, classificaremos a observação colocando-a em um grupo cujo centro esteja mais próximo dela. Ao fazer isso, acabamos com algo como o seguinte:

• NB: Por favor, note que isto pode não ser completamente preciso e que é apenas para fins de demonstração.

Da imagem acima, podemos ver que não eram exatamente os agrupamentos que tínhamos em mente. Com base nesses grupos classificados, podemos agora passar para a etapa 3 e recalcular o centro do grupo, tomando a média de todos os vetores do grupo. Basicamente, nós movemos nossas estrelas (pontos centrais) para o meio de nossos agrupamentos atuais

Looking at our results above, it shows that some of the observations might now be closer to another centre point than their previous positions. For example, let’s hone in on some of the blue observations – we can see clearly that it now belongs to the yellow star and some of the red observations clearly belong to the blue star.

Now, we can repeat steps 2 – 3 for a set number of iterations or when convergence has been reached.

Starting at step 2 again, we group each observation to a certain centre point, by computing the distance between each observation and each centre point. Following this, we will classify the observation to be in the group whose centre is closest to it (please refer back to the second image). Finally, we re-compute the group centre by taking the mean of all the vectors in the group, and move the stars (please refer back to the third image).

Fizemos esse processo mais uma vez (veja a imagem acima) e podemos ver que ainda não chegamos lá e, portanto, temos que repetir as etapas 2 a 3 novamente.

Finalmente, podemos ver agora que o agrupamento final das observações faz mais sentido do que o nosso ponto de partida inicial, então podemos dizer com sucesso que chegamos ao final do algoritmo K-means. A partir disso, identificamos com sucesso três locais definidos para nossas três novas cafeterias, localizadas no café central.

Conclusão
Para finalizar, aprendemos que o K-mean clustering é um método particularmente útil ao tentar localizar grupos que não foram explicitamente rotulados no conjunto de dados. Espero que agora você tenha uma compreensão muito melhor do que é o K-mean clustering e de como o seu algoritmo iterativo funciona.

Fonte : Tradução do site http://blog.keyrus.co.uk/