Entendendo como funciona o algoritmo de Cluster K-Means

Fala galera, uma das formas que existe para se trabalhar com aprendizado de máquinas (machine learning) é o aprendizado não supervisionado. Diferente do aprendizado supervisionado onde você informa o computador o que ele deve procurar e aprender, no aprendizado não supervisionado a gente não sabe exatamente o que estamos tentando ensinar o computador a aprender, então precisamos recorrer à agrupadores lógicos de segmentação para encontrar similaridade entre os dados da amostra e com isso, definir um padrão e assumir que este padrão encontrado é o que estamos tentando ensinar o computador, que por sua vez, vai aprender a encontrar esse padrão sempre quando for solicitado. Depois de descoberto o padrão, qualquer item novo que tenha uma similaridade com aquele segmento (cluster) pode ser inferido que ele “faz parte daquilo”.

A proposta deste post é mostrar com um certo nível de detalhes como segmentar a amostragem em grupos e descobrir padrões nos dados, usando tanto o Azure Machine Learning quanto a linguagem R. Vamos comerçar entendendo o algoritmo, em seguida vou publicar explicando a aplicação disso com códigos em R e em outro post faremos o mesmo processo no AzureML.

 

Agrupando os dados

Para exemplificar, pense em um dataset com algumas amostras dispostas nos eixo X e Y, como o gráfico abaixo. Seu objetivo é agrupar estes dados baseado em sua similaridades. Consegue fazer isso?

É possível bater o olho neste gráfico e ver a separação em alguns grupos. Cada um de nós que olhar o gráfico pode tentar criar um número diferente de cluster, ou até mesmo quando a quantidade de cluster for igual, pode-se pensar em agrupamentos de formas diferentes. Por exemplo, alguns podem ver a separação com apenas 2 clusters, e o gráfico poderia ser assim:



Qual é o certo? Todos estão certos! Isso pode acontecer de acordo com a interpretação de cada um dos observadores que encontraram apenas 2 grupos nestes dados. Outros podem encontrar 3 grupos, e não apenas dois, podendo chegar a definições como estas:



E aqui, qual dos gráficos é o certo? O certo é com 2 grupos ou com 3 grupos? Mais uma vez isso é dificil de responder, todos os 6 gráficos estão corretos de acordo com a visão de cada observador. Para ajudar a responder esta questão, existem alguns métodos usados e bem aceitos no meio científico, leia mais sobre eles aqui: https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set. Um destes métodos é o Elbow Method, que voltaremos a falar sobre ele mais pra frente.

Entendendo como funciona o 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:



Neste cenário, quando qualquer item novo for adicionado na base de dados, o algoritmo saberá classificar a qual grupo este novo item pertence. Nos próximos posts vou mostrar uma implementação em R e depois outro post com a implementação em Azure Machine Learning.

Compartilhe o post:
RSS
Follow by Email
Facebook
YOUTUBE
YOUTUBE
LinkedIn

Comentários

comments