FAVORITAR
FecharPlease loginn

O Algoritmo Dos K Vizinhos Mais Próximos

Bom dia galera! Hoje vamos estudar um dos algoritmos mais conhecidos das tarefas preditivas do aprendizado de máquina, o k-NN. O conceito básico deste algoritmo é o de que dados similares tendem a estar concentrados em uma mesma região. Então, vamos lá entender um pouco mais sobre isso.

Introdução

O k-NN é considerado um algoritmo LAZY, isto é, preguiçoso. Isto porque ele não aprende um modelo compacto para os dados, mas sim memoriza as instâncias do conjunto de treinamento. A grande vantagem deste método é que ele pode ser usado tanto para regressão, quanto para classificação, justamente porque não gera um modelo. Portanto, uma instância do conjunto de teste pode ser classificada com base nas instâncias do conjunto de treinamento próximas a ela. Em suma, o objetivo é encontrar os k-vizinhos mais próximos da instância de teste. Veja a Figura 1.

Figura 1: Exemplo k-NN

A Figura 1 mostra um conjunto de dados simples, onde matematicamente falando cada instância representa um ponto. Neste exemplo os dados podem ser classificados em laranja, verde ou rosa e existe uma nova instância que precisa ser classificada em um desses grupos. Para fazermos isso precisamos calcular a distância da instância de teste ? com relação a todas as outras. Assim, se o dataset possui 1 milhão de instâncias, teremos de calcular a distância da instância de teste ? com relação a 1 milhão de instâncias. Bom, deu pra notar que isto pode ser uma desvantagem né?!

Para que esse cálculo seja possível de ser realizado, os valores dos atributos devem ser numéricos e também deve ser feito em pares. A Equação 1 generaliza esse cálculo, onde d indica distância, a indica atributo, i e j são iteradores, e x é o espaço de instâncias.

Equação 1: Generalização do cálculo da distância entre 2 pontos (instâncias) no k-NN. 

Uma medida muito comum usada pelo k-NN é a distância euclidiana, mas outras medidas podem ser utilizadas. Pode-se também entender que a fase de memorização é a fase de treinamento, e a fase de teste é justamente calcular a distância da instância ? com as instâncias memorizadas. Como é decidido para qual grupo a instância de teste ? vai? Bom, o rótulo da classe associado à instância de treino mais próximo da instância ? é usado para classificá-la. Vamos então desenrolar o exemplo da Figura 1.

Exemplo

Para entender o conceito, considere que foi realizado um cálculo de distância qualquer e chegamos nos resultados apresentados na Figura 2. Agora, vamos considerar k=1, isto é, apenas um vizinho, no caso, o vizinho com o menor valor mais próximo, ou o vizinho com a menor distância. Quando k=1, a menor distância é 0,1, que é verde, portanto, a nossa instância de teste será classificada como verde. 

Quando k=2 temos um problema pois os dois menores valores pertencem a grupos diferentes: 0,1 = verde, 0,2 = rosa. Como decidir? Neste caso, pode ir para qualquer um dos dois grupos, mas é preciso definir um critério de decisão. Um desses critérios poderia ser o de classificar a instância na menor distância entre os k-vizinhos. Em nosso exemplo, 0,1 é uma distância menor que 0,2, então a instância será classificada no verde. Outro critério poderia ser o de escolher um dos dois aleatoriamente.

Quando k=3, temos que as menores distâncias são 0,1, 0,2 e 0,3, onde duas distâncias são do grupo verde, e uma do grupo rosa. Neste caso, o critério de decisão é a respeito da quantidade total de instâncias de uma classe dentro da vizinhança, portanto, a nova instância de teste será classificada no grupo verde. E é desta forma, resumidamente, que funciona o k-NN.

Quando k=4, as menores distâncias são 0,1 (verde), 0,2 (rosa), 0,3 (verde) e 0,35 (laranja). Mas observe que novamente a instância será classificada no grupo verde. Muito dificilmente a instância de teste será classificada no grupo laranja, basta observar os valores de distância, são muito altos. Eu dei uma exagerada neste exemplo pra gente poder enxergar melhor as coisas. Observem que, quanto mais distante, menos similar, portanto, será muito difícil uma instância se associar com outra que tem um valor de distância muito alto. 

Figura 2: Funcionamento do k-NN

Por este mesmo motivo o k costuma não ser muito alto pois, idealmente, queremos encontrar apenas os vizinhos mais similares, e não todos! O valor costuma ser 3 ou 5, e sempre um número ímpar, pois assim lida-se com os empates. Infelizmente, o desempenho do algoritmo k-NN é afetado pela medida de distância utilizada. Usando medidas diferentes, teremos resultados diferentes. 

Normalização

É importante ressaltar que, para usufruir com qualidade deste algoritmo, é necessário fazer a normalização dos dados. Imagine calcular distâncias entre alturas e pesos? Os resultados serão assustadores. Por isto, preste sempre muita atenção aos dados e aplique algum tipo de normalização, para que a distância seja calculada corretamente. Com isso também encontramos outra desvantagem do k-NN. 

Superfícies De Decisão Para 1-Knn

Lembram que falamos sobre retas, curvas e hiperplanos de fronteiras de decisão no artigo sobre Classificação X Regressão? Pois bem, quando k=1 essas superfícies são poliedros convexos com centro em cada instância de treinamento. Mas o que é um poliedro e mais, o que é convexo e não convexo? Vejamos a Figura 3.

Um poliedro, portanto, é um conjunto de planos. Observe nas Figuras que cada imagem geométrica é composta por várias faces, portanto, várias superfícies. Diz-se que um poliedro é convexo se há um segmento de reta que liga 2 pontos contidos no poliedro, e é não convexo quando isto não ocorre. No caso do k-NN, as fronteiras de decisão são essas! Para cada instância há um poliedro convexo, interessante não?! Dessa forma, ao final, temos um conjunto de poliedros, já que temos muitas instâncias em cada conjunto de dados. 

Algoritmo

Podemos entender o k-nn formalmente da seguinte forma:

Equação 2: Dataset (m é o total de instâncias, y é a classe)

Equação 3: instância de teste (t é teste, xt é a instância de teste e yt é a classe)

Equação 4: medida de distância entre duas instâncias de D

No processo de classificação, quando k>=1 temos que cada vizinho vota em uma classe e as predições são agregadas para classificar a instância de teste, concluindo, portanto que a instância de teste é classificada na classe mais votada. O que podemos usar aqui como critério de decisão é a MODA. Lembram-se da MODA? Que vimos no artigo de estatística básica? Então, é ela mesma!  No processo de regressão pode-se utilizar ou a média ou a mediana. Segue um passo a passo mais detalhado do k-nn:

  1. Carregue os dados de treinamento;
  2. Prepare os dados: escalonamento, normalização, tratamento de valores ausentes, redução de dimensionalidade, etc;
  3. Estime um valor ideal para K (por tentativa e erro);
  4. Preveja um valor de classe para novos dados:
    1. Calcule a distância;
    2. Coloque essas distâncias em ordem crescente junto com os dados do conjunto de treinamento correspondentes;
    3. Nesta lista classificada, selecione as k primeiras linhas;
    4. Encontre a classe mais frequente nesses linhas k escolhidas; (esta será a classe/valor para a instância)

Função De Custo

Para entender melhor o k-nn com relação ao seu funcionamento na classificação e regressão, precisamos entender um pouco sobre função de custo. Mas que cargas d’água é uma função de custo? No contexto do aprendizado de máquina, é uma função que calcula a diferença entre as classes/valores reais do problema e as classes/valores preditas. Como já mencionei antes, enquanto que na Classificação encontramos fronteiras de decisão, na Regressão ajustamos curvas ou superfícies. Então a nossa função precisa minimizar o custo da reta ou da curva! Dessa forma, na classificação a moda é a função que minimiza a função de custo, enquanto que na regressão a média ou a mediana são as funções que minimizam o custo!

Finalizando

O k-NN é um algoritmo simples e que obtém bons resultados. No entanto, como pudemos observar, existe uma relação complexa entre os atributos. Quando k é muito pequeno, outliers presentes nos dados podem prejudicar o resultado, e quando k é grande pode ocorrer o overfitting. Além disso, o processo de predição também é muito lento. Se a dimensão for muito alta, o desempenho geral pode ser prejudicado pois um ponto pode estar muito distante de outros. Nesse caso, precisamos pensar em maneiras de reduzir a dimensionalidade, como já mencionado em artigos anteriores. 

Bom, não vamos nos esquecer também da preparação e limpeza dos dados que é extremamente importante para que este algoritmo funcione bem. O k-NN pode ser considerado um daqueles algoritmos interpretáveis, isto é, o resultado é fácil de entender e explicar para outras pessoas! 

Então, quando você deve usar este algoritmo? Vai depender do problema, mas aqui vai um exemplo bem tradicional: uma pessoa que gostou do filme O Senhor dos Anéis, provavelmente também vai gostar do filme O Hobbit. Onde você já viu isso? Sim, é o que você está pensando! Netflix, Spotify, Amazon, sistemas de e-commerce usam muito dessa estratégia que, na verdade, é um conceito bem fundamental de sistemas de recomendação: encontrar itens similares para recomendar. Legal né? 

Então é isso gente! Espero que vocês tenham gostado do artigo. Se tiverem dúvidas, deixem ai nos comentários tá bom! A gente se vê no próximo artigo.

Leitura Recomendada

Outros artigos da série

<< Classificação X RegressãoRegressão Linear – Parte 1 >>
Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.
Home » Conceito de Engenharia » O Algoritmo Dos K Vizinhos Mais Próximos

WEBINARS

LEIA TAMBÉM

JUNTE-SE HOJE À COMUNIDADE EMBARCADOS

Comentários:
Notificações
Notificar
guest

0 Comentários
Inline Feedbacks
View all comments
Talvez você goste: