algoritmo de k- vizinhos mais próximos - k-nearest neighbors algorithm

Em estatística , o algoritmo de vizinhos k- mais próximos ( k -NN ) é um método de classificação não paramétrico desenvolvido pela primeira vez por Evelyn Fix e Joseph Hodges em 1951, e posteriormente expandido por Thomas Cover . É usado para classificação e regressão . Em ambos os casos, a entrada consiste nos k exemplos de treinamento mais próximos em um conjunto de dados . A saída depende se k -NN é usado para classificação ou regressão:

  • Na classificação k-NN , a saída é uma associação de classe. Um objeto é classificado por uma pluralidade de votos de seus vizinhos, com o objeto sendo atribuído à classe mais comum entre seus k vizinhos mais próximos ( k é um número inteiro positivo , tipicamente pequeno). Se k  = 1, então o objeto é simplesmente atribuído à classe daquele único vizinho mais próximo.
  • Na regressão k-NN , a saída é o valor da propriedade do objeto. Este valor é a média dos valores dos k vizinhos mais próximos.

k -NN é um tipo de classificação onde a função é aproximada apenas localmente e todos os cálculos são adiados até a avaliação da função. Como esse algoritmo depende da distância para classificação, se os recursos representarem unidades físicas diferentes ou vierem em escalas muito diferentes, a normalização dos dados de treinamento pode melhorar drasticamente sua precisão.

Tanto para classificação quanto para regressão, uma técnica útil pode ser atribuir pesos às contribuições dos vizinhos, de modo que os vizinhos mais próximos contribuam mais para a média do que os mais distantes. Por exemplo, um esquema de ponderação comum consiste em dar a cada vizinho um peso de 1 / d , onde d é a distância ao vizinho.

Os vizinhos são obtidos de um conjunto de objetos para os quais a classe (para classificação k -NN) ou o valor da propriedade do objeto (para regressão k -NN) é conhecido. Isso pode ser considerado o conjunto de treinamento para o algoritmo, embora nenhuma etapa de treinamento explícita seja necessária.

Uma peculiaridade do algoritmo k -NN é que ele é sensível à estrutura local dos dados.

Configuração estatística

Suponha que temos pares recebendo valores , onde Y é o rótulo de classe de X , de modo que para (e distribuições de probabilidade ). Dada alguma norma sobre e um ponto , vamos ser uma reordenação dos dados de treinamento de tal forma que .

Algoritmo

Exemplo de classificação k- NN. A amostra de teste (ponto verde) deve ser classificada em quadrados azuis ou triângulos vermelhos. Se k = 3 (círculo de linha sólida), ele é atribuído aos triângulos vermelhos porque há 2 triângulos e apenas 1 quadrado dentro do círculo interno. Se k = 5 (círculo de linha tracejada), é atribuído aos quadrados azuis (3 quadrados vs. 2 triângulos dentro do círculo externo).

Os exemplos de treinamento são vetores em um espaço de recursos multidimensional, cada um com um rótulo de classe. A fase de treinamento do algoritmo consiste apenas em armazenar os vetores de recursos e rótulos de classe das amostras de treinamento.

Na fase de classificação, k é uma constante definida pelo usuário, e um vetor não rotulado (uma consulta ou ponto de teste) é classificado atribuindo o rótulo que é mais frequente entre as k amostras de treinamento mais próximas desse ponto de consulta.

Uma métrica de distância comumente usada para variáveis ​​contínuas é a distância euclidiana . Para variáveis ​​discretas, como para classificação de texto, outra métrica pode ser usada, como a métrica de sobreposição (ou distância de Hamming ). No contexto de dados de microarray de expressão gênica, por exemplo, k -NN foi empregado com coeficientes de correlação, como Pearson e Spearman, como uma métrica. Freqüentemente, a precisão da classificação de k -NN pode ser melhorada significativamente se a métrica de distância for aprendida com algoritmos especializados, como a análise de componentes do Vizinho Mais Próximo de Margem Grande ou Vizinhança .

Uma desvantagem da classificação básica de "votação majoritária" ocorre quando a distribuição de classes é distorcida. Ou seja, exemplos de uma classe mais frequente tendem a dominar a previsão do novo exemplo, pois tendem a ser comuns entre os k vizinhos mais próximos devido ao seu grande número. Uma forma de contornar esse problema é ponderar a classificação, levando em consideração a distância do ponto de teste a cada um de seus k vizinhos mais próximos. A classe (ou valor, em problemas de regressão) de cada um dos k pontos mais próximos é multiplicada por um peso proporcional ao inverso da distância daquele ponto ao ponto de teste. Outra maneira de superar a distorção é por abstração na representação de dados. Por exemplo, em um mapa de auto-organização (SOM), cada nó é um representante (um centro) de um cluster de pontos semelhantes, independentemente de sua densidade nos dados de treinamento originais. K -NN pode então ser aplicado ao SOM.

Seleção de parâmetros

A melhor escolha de k depende dos dados; geralmente, valores maiores de k reduzem o efeito do ruído na classificação, mas tornam os limites entre as classes menos distintos. Um bom k pode ser selecionado por várias técnicas heurísticas (consulte otimização de hiperparâmetros ). O caso especial em que se prevê que a classe seja a classe da amostra de treinamento mais próxima (ou seja, quando k = 1) é chamado de algoritmo do vizinho mais próximo.

A precisão do algoritmo k -NN pode ser severamente degradada pela presença de recursos ruidosos ou irrelevantes, ou se as escalas de recursos não forem consistentes com sua importância. Muito esforço de pesquisa foi colocado na seleção ou dimensionamento de recursos para melhorar a classificação. Uma abordagem particularmente popular é o uso de algoritmos evolutivos para otimizar o dimensionamento de recursos. Outra abordagem popular é dimensionar recursos pelas informações mútuas dos dados de treinamento com as classes de treinamento.

Em problemas de classificação binária (duas classes), é útil escolher k como um número ímpar, pois isso evita votos empatados. Uma maneira popular de escolher o k empiricamente ideal nessa configuração é por meio do método de bootstrap.

O classificador de 1 vizinho mais próximo

O classificador de tipo vizinho mais próximo mais intuitivo é o classificador de um vizinho mais próximo que atribui um ponto x à classe de seu vizinho mais próximo no espaço de características, isto é .

À medida que o tamanho do conjunto de dados de treinamento se aproxima do infinito, o classificador de um vizinho mais próximo garante uma taxa de erro não pior do que duas vezes a taxa de erro de Bayes (a taxa de erro mínima alcançável dada a distribuição dos dados).

O classificador de vizinho mais próximo ponderado

O classificador de k- vizinhos mais próximos pode ser visto atribuindo aos k vizinhos mais próximos um peso e a todos os outros 0 peso. Isso pode ser generalizado para classificadores de vizinhos mais próximos ponderados. Ou seja, onde o i ésimo vizinho mais próximo recebe um peso , com . Um resultado análogo sobre a consistência forte dos classificadores de vizinhos mais próximos ponderados também é válido.

Deixe denotar o classificador mais próximo ponderado com pesos . Sujeito às condições de regularidade nas distribuições de classe, o excesso de risco tem a seguinte expansão assintótica

para constantes e onde e .

O esquema de ponderação ideal , que equilibra os dois termos na tela acima, é dado da seguinte forma: conjunto ,

para e
para .

Com pesos ótimos, o termo dominante na expansão assintótica do risco excessivo é . Resultados semelhantes são verdadeiros ao usar um classificador de vizinho mais próximo empacotado .

Propriedades

k -NN é um caso especial de uma largura de banda variável, estimador de "balão" de densidade de kernel com um kernel uniforme .

A versão ingênua do algoritmo é fácil de implementar calculando as distâncias do exemplo de teste a todos os exemplos armazenados, mas é computacionalmente intensivo para grandes conjuntos de treinamento. Usar um algoritmo de busca por vizinho mais próximo aproximado torna k- NN tratável computacionalmente, mesmo para grandes conjuntos de dados. Muitos algoritmos de busca do vizinho mais próximo foram propostos ao longo dos anos; geralmente buscam reduzir o número de avaliações à distância realmente realizadas.

k- NN tem alguns resultados de consistência forte . À medida que a quantidade de dados se aproxima do infinito, o algoritmo k- NN de duas classes garante uma taxa de erro não pior do que duas vezes a taxa de erro de Bayes (a taxa de erro mínima alcançável dada a distribuição dos dados). Várias melhorias na velocidade k -NN são possíveis usando gráficos de proximidade.

Para a classificação k- NN multiclasse , Cover e Hart (1967) provam uma taxa de erro de limite superior de

onde é a taxa de erro de Bayes (que é a taxa de erro mínima possível), é a taxa de erro k- NN e M é o número de classes do problema. Para e à medida que a taxa de erro bayesiana se aproxima de zero, esse limite se reduz a "não mais do que duas vezes a taxa de erro bayesiana".

Taxas de erro

Existem muitos resultados sobre a taxa de erro dos k classificadores de vizinhos mais próximos. O classificador de k- vizinho mais próximo é fortemente (ou seja, para qualquer distribuição conjunta em ) consistente, desde que diverja e converge para zero como .

Vamos denotar o classificador k vizinho mais próximo com base em um conjunto de treinamento de tamanho n . Sob certas condições de regularidade, o excesso de risco produz a seguinte expansão assintótica

para algumas constantes e .

A escolha oferece uma compensação entre os dois termos na tela acima, para a qual o erro do vizinho mais próximo converge para o erro de Bayes na taxa ótima ( minimax ) .

Aprendizagem métrica

O desempenho da classificação K-vizinho mais próximo pode muitas vezes ser significativamente melhorado por meio do aprendizado de métricas ( supervisionado ). Os algoritmos populares são a análise de componentes de vizinhança e o vizinho mais próximo de grande margem . Algoritmos de aprendizado de métricas supervisionados usam as informações do rótulo para aprender uma nova métrica ou pseudo-métrica .


Extração de recursos

Quando os dados de entrada para um algoritmo são muito grandes para serem processados ​​e suspeita-se que sejam redundantes (por exemplo, a mesma medição em pés e metros), os dados de entrada serão transformados em um conjunto de representação reduzido de recursos (também denominado vetor de recursos ) A transformação dos dados de entrada no conjunto de recursos é chamada de extração de recursos . Se os recursos extraídos forem escolhidos cuidadosamente, espera-se que o conjunto de recursos extraia as informações relevantes dos dados de entrada para executar a tarefa desejada usando esta representação reduzida em vez da entrada de tamanho completo. A extração de recursos é realizada em dados brutos antes de aplicar o algoritmo k -NN nos dados transformados no espaço de recursos .

Um exemplo de um pipeline de computação de visão computacional típico para reconhecimento facial usando k -NN incluindo extração de recursos e etapas de pré-processamento de redução de dimensão (geralmente implementado com OpenCV ):

  1. Detecção de rosto Haar
  2. Análise de rastreamento de deslocamento médio
  3. Projeção PCA ou Fisher LDA no espaço de recursos, seguida pela classificação k -NN

Redução de dimensão

Para dados de alta dimensão (por exemplo, com número de dimensões maior que 10), a redução da dimensão é geralmente realizada antes da aplicação do algoritmo k -NN para evitar os efeitos da maldição da dimensionalidade .

A maldição da dimensionalidade no contexto k- NN basicamente significa que a distância euclidiana é inútil em dimensões altas porque todos os vetores são quase equidistantes ao vetor de consulta de pesquisa (imagine vários pontos situados mais ou menos em um círculo com o ponto de consulta no centro; a distância da consulta a todos os pontos de dados no espaço de pesquisa é quase a mesma).

Extração de característica e redução de dimensão podem ser combinadas em uma etapa usando análise de componente principal (PCA), análise discriminante linear (LDA) ou técnicas de análise de correlação canônica (CCA) como uma etapa de pré-processamento, seguida por agrupamento por k -NN no recurso vetores no espaço de dimensão reduzida. Este processo também é chamado de incorporação de baixa dimensão .

Para conjuntos de dados dimensionais muito elevados (por exemplo, ao realizar uma pesquisa de similaridade em streams de vídeo ao vivo, dados de DNA ou séries temporais de alta dimensão ) executando uma pesquisa k- NN aproximada rápida usando hash sensível à localidade , "projeções aleatórias", "esboços" ou outras técnicas de pesquisa de similaridade de alta dimensão da caixa de ferramentas VLDB podem ser a única opção viável.

Limite de decisão

As regras do vizinho mais próximo em vigor calculam implicitamente o limite de decisão . Também é possível computar o limite de decisão explicitamente e de forma eficiente, de modo que a complexidade computacional seja função da complexidade do limite.

Redução de dados

A redução de dados é um dos problemas mais importantes para trabalhar com grandes conjuntos de dados. Normalmente, apenas alguns dos pontos de dados são necessários para uma classificação precisa. Esses dados são chamados de protótipos e podem ser encontrados da seguinte forma:

  1. Selecione os outliers de classe , ou seja, dados de treinamento que são classificados incorretamente por k -NN (para um determinado k )
  2. Separe o resto dos dados em dois conjuntos: (i) os protótipos que são usados ​​para as decisões de classificação e (ii) os pontos absorvidos que podem ser classificados corretamente por k -NN usando protótipos. Os pontos absorvidos podem então ser removidos do conjunto de treinamento.

Seleção de outliers de classe

Um exemplo de treinamento cercado por exemplos de outras classes é chamado de outlier de classe. As causas de outliers de classe incluem:

  • erro aleatório
  • exemplos insuficientes de treinamento desta classe (um exemplo isolado aparece em vez de um cluster)
  • faltando recursos importantes (as classes são separadas em outras dimensões que não conhecemos)
  • muitos exemplos de treinamento de outras classes (classes não balanceadas) que criam um pano de fundo "hostil" para a pequena classe fornecida

Outliers de classe com k -NN produzem ruído. Eles podem ser detectados e separados para análise futura. Dados dois números naturais, k> r> 0 , um exemplo de treinamento é chamado de (k, r) NN outlier de classe se seus k vizinhos mais próximos incluem mais de r exemplos de outras classes.

Vizinho mais próximo condensado para redução de dados

O vizinho mais próximo condensado (CNN, o algoritmo de Hart ) é um algoritmo projetado para reduzir o conjunto de dados para a classificação k -NN. Ele seleciona o conjunto de protótipos U dos dados de treinamento, de modo que 1NN com U possa classificar os exemplos quase tão precisamente quanto 1NN o faz com todo o conjunto de dados.

Cálculo da relação de fronteira.
Três tipos de pontos: protótipos, outliers de classe e pontos absorvidos.

Dado um conjunto de treinamento X , a CNN funciona iterativamente:

  1. Faça a varredura de todos os elementos de X , procurando um elemento x cujo protótipo mais próximo de U tenha um rótulo diferente de x .
  2. Remova x de X e adicione-o a U
  3. Repita o exame até que não haja mais protótipos são adicionados ao U .

Use U em vez de X para classificação. Os exemplos que não são protótipos são chamados de pontos "absorvidos".

É eficiente examinar os exemplos de treinamento em ordem decrescente da proporção da borda. A proporção da borda de um exemplo de treinamento x é definida como

a ( x ) = | | x'-y | |/| | xy | |

onde | | xy | | é a distância para o exemplo mais próximo y tendo uma cor diferente de x , e | | x'-y | | é a distância de y até seu exemplo mais próximo x ' com o mesmo rótulo de x .

A proporção da borda está no intervalo [0,1] porque | | x'-y | | nunca excede | | xy | | . Esta ordenação dá preferência às fronteiras das classes para inclusão no conjunto de protótipos U . Um ponto com um rótulo diferente de x é chamado externo a x . O cálculo da proporção da borda é ilustrado pela figura à direita. Os pontos de dados são rotulados por cores: o ponto inicial é x e seu rótulo é vermelho. Os pontos externos são azuis e verdes. O ponto externo mais próximo de x é y . O ponto vermelho mais próximo de y é x ' . A proporção da borda a ( x ) = | | x'-y | | / | | xy | | é o atributo do ponto inicial x .

Abaixo está uma ilustração da CNN em uma série de números. Existem três classes (vermelho, verde e azul). Fig. 1: inicialmente são 60 pontos em cada aula. A Fig. 2 mostra o mapa de classificação 1NN: cada pixel é classificado por 1NN usando todos os dados. A Fig. 3 mostra o mapa de classificação 5NN. As áreas brancas correspondem às regiões não classificadas, onde a votação 5NN está empatada (por exemplo, se houver dois pontos verdes, dois vermelhos e um azul entre os 5 vizinhos mais próximos). A Fig. 4 mostra o conjunto de dados reduzido. Os cruzamentos são os outliers de classe selecionados pela regra (3,2) NN (todos os três vizinhos mais próximos dessas instâncias pertencem a outras classes); os quadrados são os protótipos e os círculos vazios são os pontos absorvidos. O canto inferior esquerdo mostra os números dos outliers de classe, protótipos e pontos absorvidos para todas as três classes. O número de protótipos varia de 15% a 20% para diferentes classes neste exemplo. A Fig. 5 mostra que o mapa de classificação 1NN com os protótipos é muito semelhante ao do conjunto de dados inicial. As figuras foram produzidas usando o miniaplicativo Mirkes.

regressão k -NN

Na regressão k -NN, o algoritmo k -NN é usado para estimar variáveis ​​contínuas. Um desses algoritmos usa uma média ponderada dos k vizinhos mais próximos, ponderada pelo inverso de sua distância. Este algoritmo funciona da seguinte maneira:

  1. Calcule a distância Euclidiana ou Mahalanobis do exemplo de consulta aos exemplos rotulados.
  2. Ordene os exemplos etiquetados aumentando a distância.
  3. Encontre um número heuristicamente ótimo k de vizinhos mais próximos, com base no RMSE . Isso é feito usando validação cruzada.
  4. Calcule uma média ponderada da distância inversa com os k vizinhos multivariados mais próximos.

k -NN outlier

A distância até o k- ésimo vizinho mais próximo também pode ser vista como uma estimativa de densidade local e, portanto, também é uma pontuação de outlier popular na detecção de anomalias . Quanto maior a distância para k -NN, quanto menor a densidade local e mais provável que o ponto de consulta seja um outlier. Embora bastante simples, este modelo de outlier, junto com outro método clássico de mineração de dados, o fator de outlier local , funciona muito bem também em comparação com abordagens mais recentes e mais complexas, de acordo com uma análise experimental em grande escala.

Validação de resultados

Uma matriz de confusão ou "matriz de correspondência" é freqüentemente usada como uma ferramenta para validar a precisão da classificação k- NN. Métodos estatísticos mais robustos, como o teste da razão de verossimilhança, também podem ser aplicados.

Veja também

Referências

Leitura adicional