O que é K-Vizinho Mais Próximo? Um algoritmo de ML para classificar dados

Os algoritmos impulsionam o mundo do aprendizado de máquina.

Eles são frequentemente elogiados por suas capacidades preditivas e chamados de trabalhadores dedicados que consomem grandes quantidades de dados para produzir resultados instantâneos.

Entre eles, há um algoritmo frequentemente rotulado como preguiçoso. Mas é um grande executor quando se trata de classificar os pontos de dados. É chamado de algoritmo de k-vizinhos mais próximos e é frequentemente citado como um dos mais importantes   aprendizado de máquina   algoritmos.

Qual é o algoritmo de k-vizinhos mais próximos?

O algoritmo de k-vizinhos mais próximos (KNN) é um método de classificação de dados para estimar a probabilidade de um ponto de dados se tornar um membro de um grupo ou outro com base no grupo ao qual os pontos de dados mais próximos pertencem.

O algoritmo k-vizinho mais próximo é um tipo de   aprendizado de máquina supervisionado   algoritmo usado para resolver problemas de classificação e regressão. No entanto, é usado principalmente para problemas de classificação.

KNN é um algoritmo de aprendizado preguiçoso e não paramétrico .

É chamado de algoritmo de aprendizado preguiçoso ou aprendiz preguiçoso porque não realiza nenhum treinamento quando você fornece os dados de treinamento. Em vez disso, ele apenas armazena os dados durante o tempo de treinamento e não realiza nenhum cálculo. Ele não cria um modelo até que uma consulta seja executada no conjunto de dados. Isso torna o KNN ideal para   mineração de dados.

É considerado um método não paramétrico porque não faz suposições sobre a distribuição de dados subjacente. Simplificando, o KNN tenta determinar a qual grupo um ponto de dados pertence observando os pontos de dados ao seu redor.

Considere que existem dois grupos, A e B.

Para determinar se um ponto de dados está no grupo A ou no grupo B, o algoritmo analisa os estados dos pontos de dados próximos a ele. Se a maioria dos pontos de dados estiver no grupo A, é muito provável que o ponto de dados em questão esteja no grupo A e vice-versa.

Em resumo, KNN envolve classificar um ponto de dados observando o ponto de dados anotado mais próximo, também conhecido como vizinho mais próximo .

Não confunda a classificação K-NN com o agrupamento K-means. KNN é um algoritmo de classificação supervisionado que classifica novos pontos de dados com base nos pontos de dados mais próximos. Por outro lado, o agrupamento K-means é uma   sem supervisão   algoritmo de agrupamento que agrupa dados em um número K de agrupamentos.

Como funciona o KNN?

Como mencionado acima, o algoritmo KNN é predominantemente usado como classificador. Vamos dar uma olhada em como o KNN funciona para classificar os pontos de dados de entrada não vistos.

Ao contrário da classificação usando redes neurais artificiais, a classificação de k-vizinhos mais próximos é fácil de entender e simples de implementar. É ideal em situações em que os pontos de dados são bem definidos ou não lineares.

Em essência, KNN executa um mecanismo de votação para determinar a classe de uma observação invisível. Isso significa que a classe com a maioria dos votos se tornará a classe do ponto de dados em questão.

Se o valor de K for igual a um, usaremos apenas o vizinho mais próximo para determinar a classe de um ponto de dados. Se o valor de K for igual a dez, usaremos os dez vizinhos mais próximos e assim por diante.

Para colocar isso em perspectiva, considere um ponto de dados X não classificado. Existem vários pontos de dados com categorias conhecidas, A e B, em um gráfico de dispersão.

Suponha que o ponto de dados X seja colocado próximo ao grupo A.

Como você sabe, classificamos um ponto de dados observando os pontos anotados mais próximos. Se o valor de K for igual a um, usaremos apenas um vizinho mais próximo para determinar o grupo do ponto de dados.

Nesse caso, o ponto de dados X pertence ao grupo A, pois seu vizinho mais próximo está no mesmo grupo. Se o grupo A tiver mais de dez pontos de dados e o valor de K for igual a 10, o ponto de dados X ainda pertencerá ao grupo A, pois todos os seus vizinhos mais próximos estão no mesmo grupo.

Suponha que outro ponto de dados não classificado Y seja colocado entre o grupo A e o grupo B. Se K for igual a 10, escolhemos o grupo que obtiver mais votos, o que significa que classificamos Y para o grupo em que possui o maior número de vizinhos. Por exemplo, se Y tem sete vizinhos no grupo B e três vizinhos no grupo A, ele pertence ao grupo B.

O fato de o classificador atribuir a categoria com maior número de votos é verdadeiro independentemente do número de categorias presentes.

Você pode estar se perguntando como a métrica de distância é calculada para determinar se um ponto de dados é um vizinho ou não.

Existem quatro maneiras de calcular a distância medida entre o ponto de dados e seu vizinho mais próximo: distância euclidiana , distância de Manhattan , distância de Hamming e distância de Minkowski . Das três, a distância euclidiana é a função ou métrica de distância mais comumente usada.

Para validar a precisão da classificação KNN, um   matriz de confusão   é usado. Outros métodos estatísticos, como o teste de razão de verossimilhança, também são usados ​​para validação.

No caso da regressão KNN, a maioria das etapas é a mesma. Em vez de atribuir a classe com os votos mais altos, a média dos valores dos vizinhos é calculada e atribuída ao ponto de dados desconhecido.

Por que usar o algoritmo KNN?

A classificação é um problema crítico em ciência de dados e aprendizado de máquina. O KNN é um dos algoritmos mais antigos e precisos usados ​​para classificação de padrões e modelos de regressão.

Aqui estão algumas das áreas onde o algoritmo k-vizinho mais próximo pode ser usado:

• Classificação de crédito: O algoritmo KNN ajuda a determinar a classificação de crédito de um indivíduo comparando-os com aqueles com características semelhantes.
• Aprovação de empréstimo: Semelhante à classificação de crédito, o algoritmo k-vizinho mais próximo é benéfico para identificar indivíduos com maior probabilidade de inadimplência em empréstimos, comparando suas características com indivíduos semelhantes.
• Pré-processamento de dados: os conjuntos de dados podem ter muitos valores ausentes. O algoritmo KNN é usado para um processo chamado de imputação de dados ausentes que estima os valores ausentes.
• Reconhecimento de padrões: A capacidade do algoritmo KNN de identificar padrões cria uma ampla gama de aplicações. Por exemplo, ele ajuda a detectar padrões no uso de cartão de crédito e identificar padrões incomuns. A detecção de padrões também é útil para identificar padrões no comportamento de compra do cliente.
• Previsão de preço de ações: como o algoritmo KNN tem um talento para prever os valores de entidades desconhecidas, é útil para prever o valor futuro das ações com base em dados históricos.
• Sistemas de recomendação: como o KNN pode ajudar a encontrar usuários com características semelhantes, ele pode ser usado em sistemas de recomendação. Por exemplo, ele pode ser usado em uma plataforma de streaming de vídeo online para sugerir conteúdo que um usuário provavelmente assistirá analisando o que usuários semelhantes assistem.
• Visão computacional: O algoritmo KNN é usado para classificação de imagens. Como é capaz de agrupar pontos de dados semelhantes, por exemplo, agrupar gatos e cães em uma classe diferente, é útil em vários   visão computacional   formulários.

Como escolher o valor ótimo de K

Não existe uma forma específica de determinar o melhor valor K – em outras palavras – o número de vizinhos em KNN. Isso significa que você pode ter que experimentar alguns valores antes de decidir qual deles seguir em frente.

Uma maneira de fazer isso é considerar (ou fingir) que uma parte das amostras de treinamento é "desconhecida". Em seguida, você pode categorizar os dados desconhecidos no conjunto de teste usando o algoritmo de k-vizinhos mais próximos e analisar quão boa é a nova categorização comparando-a com as informações que você já possui nos dados de treinamento.

Ao lidar com um problema de duas classes, é melhor escolher um valor ímpar para K. Caso contrário, pode surgir um cenário em que o número de vizinhos em cada classe seja o mesmo. Além disso, o valor de K não deve ser um múltiplo do número de classes presentes.

Outra maneira de escolher o valor ideal de K é calculando o sqrt(N), onde N denota o número de amostras no conjunto de dados de treinamento.

No entanto, K com valores mais baixos, como K=1 ou K=2, podem ser ruidosos e sujeitos aos efeitos de outliers. A chance de overfitting também é alta nesses casos.

Por outro lado, K com valores maiores, na maioria dos casos, dará origem a limites de decisão mais suaves, mas não deve ser muito grande. Caso contrário, grupos com um número menor de pontos de dados sempre serão derrotados por outros grupos. Além disso, um K maior será computacionalmente caro.

Vantagens e desvantagens do KNN

Uma das vantagens mais significativas de usar o algoritmo KNN é que não há necessidade de construir um modelo ou ajustar vários parâmetros. Como é um algoritmo de aprendizado preguiçoso e não um aprendiz ansioso, não há necessidade de treinar o modelo; em vez disso, todos os pontos de dados são usados ​​no momento da previsão.

Claro, isso é computacionalmente caro e demorado. Mas se você tiver os recursos computacionais necessários, poderá usar o KNN para resolver problemas de regressão e classificação. No entanto, existem vários algoritmos mais rápidos por aí que podem produzir previsões precisas.

Claro, KNN não é um algoritmo de aprendizado de máquina perfeito. Como o preditor KNN calcula tudo desde o início, pode não ser ideal para grandes conjuntos de dados.

KNN e a maldição da dimensionalidade

Quando você tem grandes quantidades de dados em mãos, pode ser bastante desafiador extrair informações rápidas e diretas deles. Para isso, podemos usar algoritmos de redução de dimensionalidade que, em essência, fazem com que os dados "cheguem diretamente ao ponto".

O termo "maldição da dimensionalidade" pode dar a impressão de que saiu direto de um filme de ficção científica. Mas o que isso significa é que os dados têm muitos recursos.

Se os dados tiverem muitos recursos, haverá um alto risco de ajuste excessivo do modelo, levando a modelos imprecisos. Muitas dimensões também dificultam o agrupamento de dados, pois todas as amostras de dados no conjunto de dados parecerão equidistantes umas das outras.

O algoritmo de k-vizinhos mais próximos é altamente suscetível a overfitting devido à maldição da dimensionalidade. No entanto, este problema pode ser resolvido com a   implementação de força bruta   do algoritmo KNN. Mas não é prático para grandes conjuntos de dados.

O KNN não funciona bem se houver muitos recursos. Portanto, técnicas de redução de dimensionalidade como análise de componentes principais (PCA) e seleção de recursos devem ser realizadas durante a fase de preparação dos dados.

KNN: o algoritmo preguiçoso que ganhou corações

Apesar de ser o mais preguiçoso entre os algoritmos, o KNN construiu uma reputação impressionante e é um algoritmo para vários problemas de classificação e regressão. Obviamente, devido à sua preguiça, pode não ser a melhor escolha para casos envolvendo grandes conjuntos de dados. Mas é um dos algoritmos mais antigos, simples e precisos que existem.

Treinar e validar um algoritmo com uma quantidade limitada de dados pode ser uma tarefa hercúlea. Mas há uma maneira de fazer isso com eficiência. É chamado de validação cruzada e envolve a reserva de uma parte dos dados de treinamento como o conjunto de dados de teste.