Modelos de Predição | KNN

Descreva um ponto pela sua vizinhança.

Escrito por Felipe Azank.

Você conhece a frase “Diga-me com quem andas e direi quem tu és”? Esse ditado, regularmente dito por pais com medo de determinadas influências, nos faz refletir o quanto as características das pessoas mais próximas a você podem te definir de alguma maneira. Nesse Turing Talk veremos em detalhe um algoritmo de classificação e predição que parte justamente dessa ideia, utilizando ferramentas matemáticas para comparar dados semelhantes entre si com o objetivo de inferir uma determinada característica sobre um ponto desconhecido.

Método Geral

Para que o algoritmo consiga classificar o dataset com base nos dados fornecidos e prever a característica desejada para um item, o modelo deve seguir 3 passos essenciais:

1. Calcular a distância entre o item a ser classificado e todos os outros itens do dataset de treino (uma parte dos dados recebidos que servirá de referência para o programa “entender” a relação entre as variáveis e as respostas esperadas).
2. Identificar os K itens mais próximos do item a ser classificado. Esse número será dado pelo usuário do algoritmo, em outras palavras, você (também veremos como escolher esse número mais adiante).
3. Calcular a moda dentre as características (característica mais presente entre os K itens). Essa será a classificação final dada para o item com característica desconhecida.

Modelo gráfico 2D das ações básicas do modelo, sendo os eixos x e y características normalizadas presentes no dataset

Cálculo das distâncias

Para que todo o mecanismo de comparação entre itens e o estudo das semelhanças ocorra, é necessário transformar, de alguma maneira, as informações e características presentes no dataset em elementos matematicamente manipuláveis, portanto, o primeiro passo a se tomar nesse sentido é normalizar os dados quantitativos, colocando as features em uma base apropriada (valores transformados para uma escala entre 0 e 1). Isso pode ser facilmente realizado utilizando a classe StandardScaler da scikit-learn (que será explorado no exemplo ao final).

Após normalizar os dados, é possível calcular as distâncias entre os itens. E para fazer isso é só usar aquela fórmula padrão da distância entre dois pontos que vemos no ensino médio, certo? Nem sempre. Dependendo da situação pode ser vantajoso utilizar outras métricas de distância. O próprio scikit-learn disponibiliza várias métricas, como: Distância Euclidiana, Cosine Similarity, Manhattan Distance, Minkowski e Distância Ponderada, sendo as duas primeiras, as mais utilizadas.

Distância Euclidiana

Essa métrica, também conhecida como distância simples, trata-se da raiz quadrada da soma das diferenças de cada característica ao quadrado. Embora, a primeira vista soe um pouco complicada, basta notar que trata-se da distância simples entre dois pontos (aprendida no ensino médio) só que com mais “dimensões”, sendo, cada dimensão, uma característica da base de treino.

Fórmula geral da distância euclidiana

Exemplo mais familiar de aplicação da distância euclidiana para um espaço de duas dimensões (duas características)

Cosine Similarity

Essa métrica vale ser destacada pela sua crescente utilização em problemas nos quais a direção dos vetores é mais importante que a magnitude, como é o caso dos word vectors, que não serão discutidos nesse post :(

Para entender a como funciona essa métrica observe a imagem abaixo, na qual cada observação é representada como um vetor.

No caso da esquerda, os dois vetores apontam para a direita e o cosseno do ângulo entre eles é positivo. No caso do meio, em que os vetores apontam em sentidos quase opostos, o cosseno é negativo. E no último caso, em que os vetores são perpendiculares, o cosseno é nulo. Dessa forma, percebemos que o cosseno de θ indica quão próximos estão os sentidos de A e B. Por isso, definimos a métrica cossine similarity como:

Fórmula da cosine similarity, onde θ é o ângulo entre A e B. Os valores da direita (em termos de A e B) podem ser obtidos usando álgebra linear.

Manhattan Distance

A última métrica a ser destacada, consiste em uma métrica de distância muito intuitiva para aqueles que moram em regiões com quarteirões bem delimitados. A Manhattam Distance (também conhecida como geometria do Taxi) consiste na computação da distância entre pontos como a soma da diferença absoluta entre as coordenadas. Em outras palavras, o quanto é necessário percorrer em X e em Y para chegar de um ponto a outro.

Exemplo evidenciando a Distância Manhattan (fonte): todos os traços evidenciam o mesmo valor de distância (5 unidades em Y e 7 unidades em X)

Matematicamente, a distânica pode ser computada da seguinte forma (já expandindo para mais de duas dimensões). Abaixo, n representa o número de dimensões dos pontos, x e y dois pontos distintos, e x_i e y_i , cada um dos valores das dimensões.

Fórmula para o cálculo da distância

Melhor valor do K para se usar

Ok, já sabemos o que o algoritmo faz e como ele funciona no geral, mas quantos vizinhos K seriam necessários para o meu programa classificar e predizer com eficiência?

Bom, há muitas formas de escolher o valor do K, entre as mais utilizadas seriam: fazer uma validação cruzada, que faria com que o próprio programa encontrasse o melhor valor a se utilizar, ou simplesmente usar a raiz quadrada aproximada do número total de de dados da base de teste que você está analisando (técnica usada em datasets pequenos). Contudo, não existe um método que define com confiança o melhor valor.

Importância de escolher o melhor valor de k: a decisão perante a classificação de um item pode mudar totalmente, como no exemplo acima

Underfitting e Overfitting no KNN

Como já explicado em detalhe no Turing Talks #10, os problemas de Underfitting e Overfitting são de grande preocupação para qualquer pessoa que utiliza algum algoritmo de predição, nesse sentido, o KNN não é uma exceção.

Uma ação que gera Overfitting no modelo seria a escolha de um K muito pequeno. O algoritmo, ao considerar uma pequena quantidades de vizinhos, acabará predizendo características de determinados data points com base no ruído, o que aumentará o erro das previsões. Já uma atitude que gera Underfitting seria a escolha de um K muito grande. Nesse caso, o algoritmo passará a considerar data points muito distantes, o que dificultará, ou até impossibilitará uma identificação de padrões mais condizente para o ponto.

Enquanto ao lado esquerdo, o modelo desloca a identificação do padrão para todo e qualquer ruído, dificultando uma classificação baseada no dataset (overfitting), o lado direito mostra-se o oposto, falhando em identificar um padrão na distribuição dos data points (underfitting)

KNN Lazy Learner — Prós e Contras

O algoritmo KNN é considerado um lazy algoritm, isso significa que esse modelo não utiliza a base de treino para desenvolver uma função de discriminação, ao invés, disso, ele apenas realiza as predições calculando todas as distâncias relativas dos itens e prevendo as características por meio da moda. Portando, podemos perceber que o KNN não possui uma “fase de treino” seguida ao pé da letra, o que traz aspectos positivos e negativos para a implementação do algoritmo.

Aspectos positivos

Por ser uma técnica não paramétrica, sem assumir nada do dataset, o KNN é bom para dados que não sabemos muitas informações sobre, além de ser bem versátil para dados não lineares, tornando-o muito bom para qualquer problema de classificação de características em datasets pequenos.

Aspectos negativos

Contudo, o fato do algoritmo não desenvolver uma função de discriminação faz com que este tenha que memorizar todo o dataset de treino e tenha que calcular todas as distâncias entre os data points para promover uma classificação/predição. Esses fatores são responsáveis por dificultar, ou até impossibilitar, o uso do KNN em datasets muito grandes, uma vez que encontramos limitações de tempo e de eficiência das máquinas, nos fazendo recorrer a outros algoritmos que de fato desenvolvem uma função de discriminação (eager algorithms).

Exemplo Básico de uso do KNN

Agora que já vimos como o algoritmo funciona, como calcula a semelhança entre itens e como classifica data points novos, está na hora de vermos o resultado disso na prática em um exemplo bem simples, atentando-se para as bibliotecas que importaremos e as ações tomadas antes da implementação do algoritmo em si.

Conclusão

Após tratarmos das características principais do algoritmo K Nearest Neighbors, podemos concluir que trata-se de um modelo não paramétrico que classifica com base na similaridade entre elementos, sendo assim, muito versátil para datasets pequenos e com relações não lineares. Ademais, por ser um lazy learning algoritm devemos destacar que esse modelo não é adequado para datasets muito grandes devido a limitações de tempo e de eficiência tecnológica.

Entretanto, uma observação final sobre o KNN deve ser levantada: como o modelo se baseia no processo do cálculo de distâncias entre pontos, a performance do modelo pode ser comprometida com a chama Maldição da Dimensionalidade, fator esse que será explicado em mais detalhes em um próximo Turing Talks.

Enfim, esperamos que tenha gostado dessa breve explicação sobre um dos algoritmos mais triviais da área de aprendizagem supervisionada, perfeito para aqueles que querem começar a mexer em Machine Learning. Para saber mais, acompanhe o Grupo Turing no Facebook e Linkedin e nossos post no Medium.