KNN (K-Nearest Neighbors) #1

Como funciona?

Italo José
Jul 1, 2018 · 7 min read

O que é o KNN?

KNN(K — Nearest Neighbors) é um dos muitos algoritmos ( de aprendizagem supervisionada ) usado no campo de data mining e machine learning, ele é um classificador onde o aprendizado é baseado “no quão similar” é um dado (um vetor) do outro. O treinamento é formado por vetores de n dimensões.

Como ele funciona?

O funcionamento do KNN é bem simples, imagine que você tem dados de:

  • imagens de bolinhas roxas
  • imagens de bolinhas amarelas
  • Uma imagem de uma bolinha que você não sabe se é roxa ou amarela, mas tem todos os dados sobre ela.

Eai, como você vai fazer pra saber a cor dessa bolinha cuja a cor é desconhecida? Se ponha no lugar da máquina, imagine que você só tem os dados, você não está vendo as imagens de fato, você só está vendo o número RGB das cores de cada pixel (que são os dados que você tem da sua imagem).

obs: Vamos supor que dados com número 1 são referentes às bolinhas roxas e os dados com número 2 são referentes à bolinhas amarelas, isso apenas para facilitar a explicação, depois vamos trabalhar com dados reais.

Cada linha se refere a uma imagem e cada coluna se refere a um pixel dessa imagem, na última coluna nós temos a classe (cor) de cada uma das bolinhas, R ->roxo, e A -> amarelo, temos lá 5 imagens (5 linhas) de bolinhas, cada uma com sua classificação, você pode tentar descobrir a cor (no caso a classe) da nova imagem (uma imagem de uma bolinha que você não sabe a cor) de N maneiras, uma dessas N maneiras é ficar comparando essa nova imagem com todas as outras, e ver com qual ela se parece mais, se os dados dessa nova imagem (que você não sabe a classe dela) são mais próximos dos dados das imagens de bolinhas amarelas, então a cor da imagem nova que não está classificado é amarela, se os dados da imagem nova, forem mais parecidos com os dados das imagens de bolinha roxa, então essa a cor da bolinha da imagem nova é roxa, parece bobo mas é quase isso que o knn faz, só que de uma forma mais sofisticada.

No caso do KNN, ele não “compara” o seu novo dado (não classificado) com todos os outros de fato, na verdade ele executa um cálculo matemático para medir a distância entre os dados para fazer sua classificação, (que é quaaaaaaaaaaaase a mesma coisa #soqnao). Esse cálculo que estou falando pode ser qualquer um que meça a distância entre dois pontos, como por exemplo: Euclidiana, Manhattan, Minkowski, Ponderada e etc.

As etapas de um algoritmo KNN são:

1 — Recebe um dado não classificado;

2 — Mede a distância (Euclidiana, Manhattan, Minkowski ou Ponderada) do novo; dado com todos os outros dados que já estão classificados;

3 — Obtém as X(no caso essa variável X é o parâmetro K) menores distâncias;

4 — Verifica a classe de cada da um dos dados que tiveram a menor distância e conta a quantidade de cada classe que aparece;

5 — Toma como resultado a classe que mais apareceu dentre os dados que tiveram as menores distâncias;

6 — Classifica o novo dado com a classe tomada como resultado da classificação

Abaixo há uma imagem com esse processo, você tem um dado não classificado (em vermelho) e todos os seus outros dados já classificados(amarelo e roxo) cada um com sua classe (A e B). Então você calcula a distância do seu novo dado com todos os outros pra saber quais estão mais próximos(quais tem as menores distâncias), feito isso você você pega 3(ou 6) dos dados mais próximos e verifica qual é a classe que mais aparece, no caso da imagem abaixo, os dados mais próximos do novo dado são aqueles que estão dentro do primeiro círculo (de dentro pra fora), e ali dentro há 3 outros dados (já classificados), com isso vamos verificar qual é a classe predominante ali dentro, olha só, é o roxo, pois há 2 bolinhas roxas e apenas 1 amarela, looooogo esse novo dado que antes não estava classificado, agora ele será classificado como roxo.

Calculando a distancia:

Para calcular a distância entre dois pontos (sua nova amostra e todos os outros dados que você tem no seu dataset) é muito simples, como dito anteriormente, há várias formas de obter esse valor, neste artigo vamos usar a distância euclidiana, pois é uma das mais usadas.

A forma da distância euclidiana se encontra logo abaixo :

Espere, não se assuste, não é tão complicado quanto parece, depois de ler esse artigo e continuar achando complexo, quando chegarmos no código você vai ver o quão simples isso tudo é.

É com essa fórmula que você vai verificar a distância entre 1 ponto(sua amostra nao classificada) e 1 outro ponto do seu dataset(1 outro dado já classificado) para então ver a similaridade dos dois, quanto menor é o resultado dessa “continha” mais é a similaridade entre esses dois dados. E sim, você vai rodar esse cálculo vaaaarias vezes, até ter rodados em todos os dados, quando você fizer isso, você vai ter um array(vamos usar um array como exemplo) com o resultado de cada vez que você calculou a distância(no caso, a similaridade) do seu dado não classificado para um outro dado já classificado.

Agora vamos pro calculo de fato, é simples mas leia com calma essa parte, basicamente você vai tirar a raiz quadrada da soma dos resultados da subtração de cada característica do ponto1(amostra não classificada) para o ponto2(amostra já classificada. Confuso? Vamos fazer isso em uma planilha então

Vamos usar o exemplo da planilha anterior mas agora com 1 dado sem classificação, que é a informação que queremos classificar.

Temos 5 dados(linhas) nesse exemplo, cada amostra(dado) com seus respectivos atributos(características), vamos IMAGINAR que tudo isso fossem imagens, cada linha seria uma imagem e cada coluna seria um pixel dessa imagem, ou então vamos supor que cada registro seja relacionado a um tumor, e cada coluna a uma característica desse tumor, como tamanho, raio, peso e etc.

Vamos entao calcular, seguindo aquela explicação confusa acima, vamos começar pelo final, vamos começar pela subtração, queremos verificar a distancia da linha 1 da planilha pra todas as outras linhas, entao vamos começar!

Vamos pegar a primeira linha, que é o dado que queremos classificar e vamos medir a distancia euclidiana pra linha 2

1 — Subtração

Vamos subtrair cada atributo(coluna) da linha 1 com os atributos da linha 2,exemplo:

(1–2) = -1

2 — Exponenciação:

Depois de ter feito a subtração da coluna 1 da linha 1, com a coluna 1 da linha 2, vamos elevar isso ao quadrado para que os números fiquem positivos exemplo:

(1–2)² = (-1 )²(-1)² = 1

3 — Soma

Depois de ter feito o passo 2 para todas as colunas da linha 1 e linha 2, vamos somar todos esses resultados, se fizermos isso pras colunas lá da imagem da planilha, vamos ter o seguinte resultado:

(1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² + (1–2)² = 8

Note que temos 8 colunas de atributos, tanto na linha 1 como na linha 2, e nós executamos o passo 2 para cada atributo do nosso dataset, no final o resultado foi 8, por que 8? Porque cada vez que rodamos o passo 2, o resultado deu 1, isso porque por uma “coincidência” nós temos os dados de todas as colunas iguais e o resultado de (1–2)² é igual à 1, usei esses valores para facilitar na hora de fazer as contas, mas não, seus atributos não precisam ser sempre o mesmo número, mais tarde vamos ver isso melhor na implementação do código com esse algoritmo.

4 — Raiz quadrada:

Após ter feito o passo 3, vamos agora tirar a raiz quadrada do resultado da soma das subtrações elevadas ao quadrado. No passo 3, o resultado foi 8, então vamos tirar a raiz quadrada de 8:

√8 = 2,83 ou 8^(½) = 2,83

Pronto, agora você tem a distância euclidiana da linha 1 para a linha 2, viu, não foi tão difícil, deu pra fazer até na mão!

Agora você só precisa fazer esses pra todas as linhas, da linha 1 para todas as outras linhas, quando você fizer isso, você terá a distância Euclidiana da linha 1 para todas as outras linhas, aí você vai ordená-las do menor pro maior, verificar quais são as K(3 por exemplo) menores distâncias e verificar qual é a classe que aparece mais, a classe que mais aparecer vai ser a classe que você vai usar para classificar a linha 1 (que desde o início não estava classificada) .

Simples não é? Nos próximos artigos nós vamos começar a fazer a implementação desse algoritmo em GO! Mas não se preocupem, a sintaxe do Go é tão simples que você ira ira seguir acompanhar e aplicar isso na sua linguagem.

[Momento jabá]

Não deixe de se tornar membro da nossa comunidade (AI BRASIL) que está ganhando o brasil, já estamos em São Paulo em no Rio de Janeiro (por enquanto!), fazemos meetups todos os meses, e em todos os meetups temos hands-ons, falando de assuntos como o desse artigo, só que de uma forma mais aprofundada e com “tira duvidas” !.

Link: https://meetup.com/pt-BR/ai-brasil/

aibrasil

Italo José

Written by

Computer vision Engineer at Nextcode https://www.linkedin.com/in/italojs https://www.instagram.com/italo.js

aibrasil

aibrasil

Publicação ligada à comunidade AI Brasil (https://www.meetup.com/pt-BR/ai-brasil) focada em IA na prática. Tem por objetivo a democratização do uso da Inteligência Artificial, unindo a comunidade a empresas, indivíduos e instituições tendo em vista disseminação de conhecimento.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade