KNN (K-Nearest Neighbors) #1

Como funciona?

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/