O que é o algoritmo k-nearest neighbors (KNN)?

Embora o algoritmo KNN possa ser usado para problemas de regressão ou classificação, ele é tipicamente utilizado como um algoritmo de classificação, partindo do pressuposto de que pontos semelhantes podem ser encontrados próximos uns dos outros.

Para os problemas de classificação, um rótulo de classe é atribuído com base em uma votação majoritária. Ou seja, o rótulo mais frequentemente representado em torno de um dado ponto de dados é utilizado. Embora isso seja tecnicamente considerado uma "votação por pluralidade", o termo "voto majoritário" é mais amplamente usado na literatura. A distinção entre esses termos é que "votação majoritária" tecnicamente requer uma maioria de mais de 50%, o que funciona principalmente quando há apenas duas categorias. Quando se tem várias classes, por exemplo, quatro categorias, você não precisa necessariamente de 50% dos votos para fazer uma conclusão sobre uma classe; você poderia atribuir um rótulo de classe com mais de 25% de votos. A Universidade de Wisconsin-Madison resume isso bem com este exemplo.

Problemas de regressão usam um conceito semelhante ao problema de classificação, mas nesse caso, a média dos k vizinhos mais próximos é usada para fazer uma previsão sobre uma classificação. A principal distinção aqui é que a classificação é usada para valores discretos, enquanto a regressão é usada com valores contínuos. No entanto, antes que uma classificação possa ser feita, a distância precisa ser definida. A distância euclidiana é a mais comumente utilizada, sobre a qual vamos nos aprofundar mais abaixo.

Também vale observar que o algoritmo KNN faz parte de uma família de modelos de "aprendizado preguiçoso", o que significa que ele apenas armazena um conjunto de dados de treinamento, em vez de passar por uma fase de treinamento. Isso também significa que toda a computação ocorre quando uma classificação ou previsão está sendo feita. Como ele depende bastante da memória para armazenar todos os seus dados de treinamento, também é chamado de método de aprendizado baseado em instância ou em memória.

Evelyn Fix e Joseph Hodges são creditados com as ideias iniciais em torno do modelo KNN neste artigo de 1951, enquanto Thomas Cover expande o conceito em sua pesquisa "Nearest Neighbor Pattern Classification." Embora não seja tão popular quanto já foi, ainda é um dos primeiros algoritmos que se aprende em ciência de dados devido à sua simplicidade e precisão. No entanto, à medida que um conjunto de dados cresce, o KNN se torna cada vez mais ineficiente, comprometendo o desempenho geral do modelo. É comumente utilizado para sistemas de recomendação simples, reconhecimento de padrões, mineração de dados, previsões de mercados financeiros, detecção de intrusões e muito mais.

Recapitulando, o objetivo do algoritmo k-nearest neighbors (KNN) é identificar os vizinhos mais próximos de um determinado ponto de consulta, para que possamos atribuir uma classe a esse ponto. Para fazer isso, o KNN tem alguns requisitos:

Para determinar quais pontos de dados estão mais próximos de um determinado ponto de consulta, é necessário calcular a distância entre o ponto de consulta e os outros pontos de dados. Essas métricas de distância ajudam a formar limites de decisão, que particionam os pontos de consulta em diferentes regiões. É comum visualizar esses limites de decisão com diagramas de Voronoi.

Embora existam várias medidas de distância que você pode escolher, este artigo abordará apenas as seguintes:

Distância Euclidiana (p=2): esta é a medida de distância mais comumente utilizada, sendo limitada a vetores com valores reais. Usando a fórmula abaixo, ela mede uma linha reta entre o ponto de consulta e o outro ponto sendo medido.

Distância de Manhattan (p=1): esta é outra métrica de distância popular, que mede o valor absoluto entre dois pontos. Também é chamada de distância de táxi ou distância de quarteirão, pois geralmente é visualizada com uma grade, ilustrando como alguém poderia navegar de um endereço a outro pelas ruas da cidade.

Distância de Minkowski: esta métrica de distância é a forma generalizada das métricas de distância euclidiana e de Manhattan. O parâmetro p, na fórmula abaixo, permite a criação de outras métricas de distância. A distância Euclidiana é representada por esta fórmula quando p é igual a dois, e a distância de Manhattan é denotada com p igual a um.

Distância de Hamming: esta técnica é normalmente usada com vetores booleanos ou de strings, identificando os pontos onde os vetores não correspondem. Como resultado, também é conhecida como métrica de sobreposição. Isso pode ser representado com a seguinte fórmula:

Por exemplo, se você tiver as seguintes strings, a distância de Hamming seria 2, já que apenas dois dos valores são diferentes.

O valor de k no algoritmo k-NN define quantos vizinhos serão verificados para determinar a classificação de um ponto de consulta específico. Por exemplo, se k=1, a instância será atribuída à mesma classe que seu vizinho mais próximo.

Definir k pode ser um ato de equilíbrio, pois diferentes valores podem levar a overfitting ou underfitting. Valores mais baixos de k podem ter alta variância, mas baixa tendência, e valores maiores de k podem levar a alta tendência e menor variância. A escolha de k dependerá amplamente dos dados de input, já que dados com mais outliers ou ruído provavelmente terão melhor desempenho com valores mais altos de k. No geral, recomenda-se um número ímpar para k, a fim de evitar empates na classificação, e táticas de validação cruzada podem ajudar a escolher o k ideal para seu conjunto de dados.

Para se aprofundar, você pode aprender mais sobre o algoritmo k-NN usando Python e scikit-learn (também conhecido como sklearn). Nosso tutorial no Watson Studio ajuda você a aprender a sintaxe básica desta biblioteca, que também contém outras bibliotecas populares, como NumPy, pandas e Matplotlib. O código a seguir é um exemplo de como criar e prever com um modelo KNN:

O algoritmo k-NN tem sido utilizado em uma variedade de aplicações, principalmente dentro da classificação. Alguns desses casos de uso incluem:

• Pré-processamento de dados: os conjuntos de dados frequentemente têm valores ausentes, mas o algoritmo KNN pode estimar esses valores em um processo conhecido como imputação de dados ausentes.
  
  
• Mecanismos de recomendação: usando dados de cliques de sites, o algoritmo KNN tem sido utilizado para fornecer recomendações automáticas aos usuários sobre conteúdo adicional. Esta pesquisa mostra que um usuário é atribuído a um determinado grupo e, com base no comportamento do usuário desse grupo, ele recebe uma recomendação. No entanto, dadas as questões de escalabilidade com o KNN, essa abordagem pode não ser ideal para grandes conjuntos de dados.
  
  
• Finanças: o KNN também foi utilizado em uma variedade de casos de uso nos setores financeiro e econômico. Por exemplo, um artigo mostra como o uso do KNN em dados de crédito pode ajudar os bancos a avaliar o risco de um empréstimo a uma organização ou indivíduo. Ele é usado para determinar a confiabilidade de crédito de um solicitante de empréstimo. Outro periódico destaca seu uso na previsão do mercado de ações, taxas de câmbio, negociações de futuros e análises de lavagem de dinheiro.
  
  
• Saúde: o KNN também teve aplicação no setor de saúde, fazendo previsões sobre o risco de ataques cardíacos e câncer de próstata. O algoritmo funciona calculando as expressões genéticas mais prováveis.
  
  
• Reconhecimento de padrões: o KNN também auxiliou na identificação de padrões, como na classificação de texto e dígitos. Isso tem sido especialmente útil para identificar números manuscritos que você pode encontrar em formulários ou envelopes de correspondência.

Assim como qualquer algoritmo de aprendizado de máquina, o k-NN tem seus pontos fortes e fracos. Dependendo do projeto e da aplicação, ele pode ou não ser a escolha certa.

• Fácil de implementar: dada a simplicidade e precisão do algoritmo, ele é um dos primeiros classificadores que um novo cientista de dados aprenderá.
  
  
• Adapta-se facilmente: à medida que novas amostras de treinamento são adicionadas, o algoritmo se ajusta para incluir os novos dados, uma vez que todos os dados de treinamento são armazenados na memória.
  
  
• Poucos hiperparâmetros: o KNN requer apenas um valor de k e uma métrica de distância, o que é baixo em comparação com outros algoritmos de aprendizado de máquina.

• Não tem uma boa escalabilidade: como o KNN é um algoritmo preguiçoso, ele consome mais memória e armazenamento de dados em comparação com outros classificadores. Isso pode ser caro do ponto de vista de tempo e dinheiro. Mais memória e armazenamento aumentam as despesas de negócios e mais dados podem demorar mais para serem processados. Embora diferentes estruturas de dados, como Ball-Tree, tenham sido criadas para lidar com as ineficiências computacionais, um classificador diferente pode ser mais ideal, dependendo do problema de negócios.
  
  
• Maldição da dimensionalidade: o algoritmo KNN costuma ser vítima da maldição da dimensionalidade, o que significa que ele não se sai bem com inputs de dados de alta dimensionalidade. Isso às vezes também é chamado de fenômeno de pico, onde, após o algoritmo atingir o número ideal de funcionalidades, a adição de mais delas aumenta a quantidade de erros de classificação, especialmente quando o tamanho da amostra é menor.
  
  
• Propenso a excesso de ajuste: devido à "maldição da dimensionalidade", o KNN também é mais propenso a se ajustar em excesso. Embora as técnicas de seleção de recursos e redução de dimensionalidade sejam aproveitadas para evitar que isso ocorra, o valor de k também pode afetar o comportamento do modelo. Valores mais baixos de k podem ajustar demais os dados, enquanto valores mais altos de k tendem a "suavizar" os valores de previsão, pois a média dos valores é calculada em uma área maior, ou vizinhança. No entanto, se o valor de k for muito alto, ele poderá não se ajustar aos dados.