K-means, Python e um treino de basquete

Nos é recomendado (e faz bem!) praticar algum tipo de esporte. Como nunca tive muito talento para o futebol, escolhi e gostei do basquete. Há um tempo voltei a treinar, parei e agora voltei novamente. Quem já jogou basquete na escola ou na rua conhece o famoso "reloginho", que é treinar os arremessos em posições específicas ao redor da cesta. Mais conhecido do que ele são os lances livres. 

Pois bem! Organizei meu treino com base nessas duas "modalidades" e comecei a registrar minha "performance". Como não ia muito bem, após o 4º dia de treino procurei um vídeo no youtube que mostrasse como treinar arremessos. Adotei a nova técnica e notei alguma melhora. Eis que no último treino pensei: "Será que consigo achar algo que realmente evidencie minha melhora?".

Cada registro dos meus treinos é composto do tempo que levo para realizar 2 voltas no "reloginho" (quanto menor melhor) e da quantidade de lances livres que acerto (em 70 tentativas, quanto mais, melhor). Ou seja, tenho um par de pontos [lance livre, tempo relogio] para cada dia que treino. Assim, em ordem cronológica minha base de dados é (não é difícil nota que sou diametralmente oposto ao Jordan):

Antes do vídeo -> [7,20],[15,22],[19,20],[16,24]
Após o vídeo -> [12,15],[15,10],[20,15],[19,14]

Ok, mas e o K-means?

Para quem não está familiarizado, o K-means é um dos mais simples algoritmos de aprendizagem não supervisionada. Porém, é muito útil para resolver problemas de agrupamento (clustering). Dado um número fixo de clusters (k), fixados a priori, o algoritmo agrupa os dados ao redor dos k centróides de cada grupo. Cada centróide é colocado na maior distância possível do outro, para que cada ponto possa ser associado com o centróide mais próximo. Esta lógica tem como objetivo minimizar a função do erro quadrático médio (J), dada por

 ,

onde  é a distância entre o ponto e o centróide.

O algoritmo é descrito a seguir:

Especifique k
Selecione os k objetos que serão os centróides dos agrupamentos
para todos os objetos restantes faça
  Calcule a distância entre o elemento e os centróides
  Adicione o elemento ao agrupamento que possuir a menor distância
  Recalcule o centróide do agrupamento
fim para
para todos os k agrupamentos faça 
  Calcule a Soma de Quadrados Residual
fim para 
repita
  para todos os n elementos faça
   Mova o elemento para os outros agrupamentos
   Recalcule a Soma de Quadrados Residual
      se soma dos Quadrados Residual diminuiu então
     O objeto passa a fazer parte do grupo que produzir maior ganho
     Recalcule a Soma de Quadrados Residual dos grupos alterados
      fim se
  fim para
até Número de interações = i ou Não ocorra mudança de objetos

Fonte

Felizmente, no Python, utilizando a biblioteca scipy, podemos executar este agrupamento em apenas 1 linha de código. No Git do Arte dos Dados está disponível o código completo - arquivo kmeans.py. 

Para entender melhor a lógica do código, temos algumas funções bem interessantes que utilizamos para preparação dos dados. Começando pela linha 18, temos a função vstack(). Ela "emplilha" os dados do array na vertical, ou seja

>>> a = np.array([1, 2, 3])
>>> b = np.array([2, 3, 4])
>>> np.vstack((a,b))
array([[1, 2, 3],
       [2, 3, 4]])

Na sequência, temos na linha 24 a função vq que faz a "quantização" do vetor de dados, passo que é necessário pois o vetor de observações é classificado de acordo com sua distância do centróide mais próximo. Este passo também é útil para classificarmos novas observações de acordo com os clusters já definidos. Seria uma etapa fundamental na utilização desta segmentação como variáveis categóricas de um modelo, por exemplo.

Voltando ao nosso conjunto de dados do treino de basquete, após a execução do K-means temos a seguinte saída:

Analisando o gráfico e comparando os pontos que foram atribuídos a cada centróide (em verde) temos de fato uma distinção antes e depois de assistir ao vídeo no youtube. Todos os pontos do grupo destacado em azul pertencem ao grupo de dados coletados no "pós vídeo".

Foi uma aplicação bem interessante e que conseguiu mostrar o poder de segmentação do algoritmo.

Um abraço e até o próximo post!