Pesquisa de vizinho mais próximo - Nearest neighbor search

A busca por vizinho mais próximo ( NNS ), como forma de busca por proximidade , é o problema de otimização de encontrar o ponto em um determinado conjunto que está mais próximo (ou mais semelhante) de um determinado ponto. A proximidade é normalmente expressa em termos de uma função de dissimilaridade: quanto menos semelhantes os objetos, maiores os valores da função.

Formalmente, o problema de busca do vizinho mais próximo (NN) é definido como segue: dado um conjunto S de pontos em um espaço M e um ponto de consulta q  ∈  M , encontre o ponto mais próximo em S para q . Donald Knuth em vol. O artigo 3 de The Art of Computer Programming (1973) chamou-o de problema dos correios , referindo-se a um pedido de designar para uma residência a estação de correio mais próxima. Uma generalização direta desse problema é uma busca k -NN, onde precisamos encontrar os k pontos mais próximos.

Mais comumente, M é um espaço métrico e a dissimilaridade é expressa como uma métrica de distância , que é simétrica e satisfaz a desigualdade do triângulo . Ainda mais comum, M é considerado o espaço vetorial d- dimensional onde a dissimilaridade é medida usando a distância euclidiana , distância de Manhattan ou outra métrica de distância . No entanto, a função de dissimilaridade pode ser arbitrária. Um exemplo é a divergência assimétrica de Bregman , para a qual a desigualdade do triângulo não é válida.

Formulários

O problema de pesquisa do vizinho mais próximo surge em vários campos de aplicação, incluindo:

Métodos

Várias soluções para o problema de NNS foram propostas. A qualidade e a utilidade dos algoritmos são determinadas pela complexidade do tempo das consultas, bem como pela complexidade do espaço de quaisquer estruturas de dados de pesquisa que devem ser mantidas. A observação informal geralmente referida como a maldição da dimensionalidade afirma que não existe uma solução exata de propósito geral para NNS em espaço euclidiano de alta dimensão usando pré-processamento polinomial e tempo de pesquisa polilogarítmica.

Métodos exatos

Pesquisa linear

A solução mais simples para o problema de NNS é calcular a distância do ponto de consulta a todos os outros pontos do banco de dados, mantendo o controle do "melhor até agora". Este algoritmo, por vezes referida como a abordagem ingénuo, tem um tempo de corrida de S ( dN ), onde N é a cardinalidade de S e d é a dimensionalidade de M . Não há estruturas de dados de pesquisa para manter, portanto, a pesquisa linear não tem complexidade de espaço além do armazenamento do banco de dados. A pesquisa ingênua pode, em média, superar as abordagens de particionamento de espaço em espaços de dimensões superiores.

Particionamento de espaço

Desde a década de 1970, a metodologia de ramificação e limite tem sido aplicada ao problema. No caso do espaço euclidiano, essa abordagem abrange o índice espacial ou métodos de acesso espacial. Vários métodos de particionamento de espaço foram desenvolvidos para resolver o problema de NNS. Talvez a mais simples seja a árvore kd , que divide iterativamente o espaço de busca em duas regiões contendo metade dos pontos da região pai. As consultas são realizadas por meio do percurso da árvore da raiz até uma folha, avaliando o ponto de consulta em cada divisão. Dependendo da distância especificada na consulta, ramificações vizinhas que podem conter ocorrências também podem precisar ser avaliadas. Para o tempo de consulta dimensão constante, a complexidade média é O (log  N ), no caso de pontos distribuídos aleatoriamente, complexidade de pior caso é S ( kN ^ (1-1 / k )) Em alternativa, o R-árvore estrutura de dados foi concebido para suportar mais próxima busca de vizinhos em contexto dinâmico, pois possui algoritmos eficientes para inserções e exclusões como a árvore R * . As árvores-R podem produzir vizinhos mais próximos não apenas para a distância euclidiana, mas também podem ser usadas com outras distâncias.

No caso do espaço métrico geral, a abordagem de ramificação e limite é conhecida como abordagem da árvore métrica . Exemplos particulares incluem métodos vp-tree e BK-tree .

Usando um conjunto de pontos retirados de um espaço tridimensional e colocados em uma árvore BSP , e dado um ponto de consulta retirado do mesmo espaço, uma possível solução para o problema de encontrar o ponto de nuvem mais próximo ao ponto de consulta é fornecida na seguinte descrição de um algoritmo. (Estritamente falando, esse ponto pode não existir, porque pode não ser único. Mas, na prática, geralmente nos preocupamos apenas em encontrar qualquer um do subconjunto de todos os pontos de nuvem de pontos que existem na distância mais curta de um determinado ponto de consulta. ) A ideia é, para cada ramificação da árvore, supor que o ponto mais próximo na nuvem reside no meio-espaço que contém o ponto de consulta. Pode não ser o caso, mas é uma boa heurística. Depois de ter recursivamente passado por todo o trabalho de resolver o problema para o meio-espaço adivinhado, agora compare a distância retornada por esse resultado com a distância mais curta do ponto de consulta ao plano de partição. Esta última distância é aquela entre o ponto de consulta e o ponto mais próximo possível que poderia existir no meio-espaço não pesquisado. Se essa distância for maior do que a retornada no resultado anterior, então claramente não há necessidade de pesquisar a outra metade do espaço. Se houver tal necessidade, você deve passar pelo trabalho de resolver o problema para a outra metade do espaço e, em seguida, comparar seu resultado com o resultado anterior e, em seguida, retornar o resultado adequado. O desempenho deste algoritmo está mais próximo do tempo logarítmico do que do tempo linear quando o ponto de consulta está perto da nuvem, porque como a distância entre o ponto de consulta e o ponto de nuvem mais próximo se aproxima de zero, o algoritmo precisa apenas realizar uma pesquisa usando o ponto de consulta como uma chave para obter o resultado correto.

Métodos de aproximação

Um algoritmo de pesquisa de vizinho mais próximo aproximado pode retornar pontos, cuja distância da consulta é, na maioria das vezes, a distância da consulta aos pontos mais próximos. O apelo dessa abordagem é que, em muitos casos, um vizinho mais próximo aproximado é quase tão bom quanto o exato. Em particular, se a medida de distância capturar com precisão a noção de qualidade do usuário, então pequenas diferenças na distância não devem importar.

Pesquisa gananciosa em gráficos de vizinhança

Os métodos de gráfico de proximidade (como HNSW) são considerados o estado da arte atual para a pesquisa aproximada de vizinhos mais próximos.

Os métodos são baseados em travessias gananciosas em grafos de vizinhança em que cada ponto é associado exclusivamente ao vértice . A pesquisa dos vizinhos mais próximos de uma consulta q no conjunto S assume a forma de pesquisa do vértice no gráfico . O algoritmo básico - pesquisa gulosa - funciona da seguinte maneira: a pesquisa começa a partir de um vértice de ponto de entrada calculando as distâncias da consulta q a cada vértice de sua vizinhança e, em seguida, encontra um vértice com o valor de distância mínimo. Se o valor da distância entre a consulta e o vértice selecionado for menor que o valor entre a consulta e o elemento atual, o algoritmo se moverá para o vértice selecionado e ele se tornará um novo ponto de entrada. O algoritmo para quando atinge um mínimo local: um vértice cuja vizinhança não contém um vértice mais próximo da consulta do que o próprio vértice.

A ideia de gráficos de vizinhança de proximidade foi explorada em várias publicações, incluindo o artigo seminal de Arya e Mount, no sistema VoroNet para o avião, no sistema RayNet para o , e nos algoritmos Metrized Small World e HNSW para o caso geral de espaços com função de distância. Esses trabalhos foram precedidos por um artigo pioneiro de Toussaint, no qual ele introduziu o conceito de grafo de vizinhança relativa .

Hash sensível à localidade

Hash sensível à localidade (LSH) é uma técnica para agrupar pontos no espaço em 'baldes' com base em alguma métrica de distância operando nos pontos. Os pontos próximos uns dos outros na métrica escolhida são mapeados para o mesmo intervalo com alta probabilidade.

Pesquisa de vizinho mais próximo em espaços com pequena dimensão intrínseca

A árvore de cobertura tem um limite teórico que se baseia na constante de duplicação do conjunto de dados . O limite no tempo de pesquisa é O ( c 12  log  n ), onde c é a constante de expansão do conjunto de dados.

Pesquisa radial projetada

No caso especial em que os dados são um mapa 3D denso de pontos geométricos, a geometria de projeção da técnica de detecção pode ser usada para simplificar drasticamente o problema de pesquisa. Esta abordagem requer que os dados 3D sejam organizados por uma projeção em uma grade bidimensional e assume que os dados são espacialmente uniformes nas células vizinhas da grade, com exceção dos limites do objeto. Essas suposições são válidas ao lidar com dados do sensor 3D em aplicações como levantamento topográfico, robótica e visão estereoscópica, mas podem não ser válidas para dados desorganizados em geral. Na prática, essa técnica tem um tempo médio de busca de O ( 1 ) ou O ( K ) para o problema do vizinho mais próximo k quando aplicada a dados de visão estéreo do mundo real.

Arquivos de aproximação vetorial

Em espaços de alta dimensão, as estruturas de indexação de árvore se tornam inúteis porque uma porcentagem crescente de nós precisa ser examinada de qualquer maneira. Para acelerar a pesquisa linear, uma versão compactada dos vetores de recursos armazenados na RAM é usada para pré-filtrar os conjuntos de dados em uma primeira execução. Os candidatos finais são determinados em uma segunda etapa usando os dados descompactados do disco para o cálculo da distância.

Pesquisa baseada em compactação / clustering

A abordagem do arquivo VA é um caso especial de pesquisa baseada em compactação, em que cada componente de recurso é compactado de maneira uniforme e independente. A técnica de compressão ideal em espaços multidimensionais é a quantização vetorial (VQ), implementada por meio de agrupamento. O banco de dados é agrupado e os clusters mais "promissores" são recuperados. Grandes ganhos em relação ao arquivo VA, índices baseados em árvore e varredura sequencial foram observados. Observe também os paralelos entre clustering e LSH.

Variantes

Existem numerosas variantes do problema NNS e as duas mais conhecidas são a pesquisa de vizinho mais próximo k e a pesquisa de vizinho mais próximo ε aproximada .

k- vizinhos mais próximos

A pesquisa de k- vizinho mais próximoidentifica os k principais vizinhos mais próximos da consulta. Essa técnica é comumente usada em análises preditivas para estimar ou classificar um ponto com base no consenso de seus vizinhos. Os gráficos de k- vizinhos mais próximos são gráficos em que cada ponto está conectado aos seus k vizinhos mais próximos.

Aproximar o vizinho mais próximo

Em alguns aplicativos, pode ser aceitável recuperar um "bom palpite" do vizinho mais próximo. Nesses casos, podemos usar um algoritmo que não garante retornar o vizinho mais próximo real em todos os casos, em troca de maior velocidade ou economia de memória. Freqüentemente, esse algoritmo encontrará o vizinho mais próximo na maioria dos casos, mas isso depende fortemente do conjunto de dados que está sendo consultado.

Os algoritmos que suportam a pesquisa aproximada do vizinho mais próximo incluem hashing sensível à localidade , melhor bin primeiro e pesquisa baseada em árvore de decomposição de caixa balanceada .

Proporção de distância do vizinho mais próximo

A proporção da distância do vizinho mais próximo não se aplica ao limite na distância direta do ponto original ao vizinho desafiador, mas em uma proporção dependendo da distância ao vizinho anterior. É usado no CBIR para recuperar imagens por meio de uma "consulta por exemplo" usando a similaridade entre características locais. De modo mais geral, ele está envolvido em vários problemas de correspondência .

Raio fixo perto de vizinhos

Raio fixo próximo a vizinhos é o problema em que se deseja encontrar com eficiência todos os pontos dados no espaço euclidiano dentro de uma determinada distância fixa de um ponto especificado. A distância é considerada fixa, mas o ponto de consulta é arbitrário.

Todos os vizinhos mais próximos

Para algumas aplicações (por exemplo, estimativa de entropia ), podemos ter N pontos de dados e desejar saber qual é o vizinho mais próximo para cada um desses N pontos . Isso poderia, é claro, ser alcançado executando uma pesquisa de vizinho mais próximo uma vez para cada ponto, mas uma estratégia melhorada seria um algoritmo que explora a redundância de informações entre essas N consultas para produzir uma pesquisa mais eficiente. Como um exemplo simples: quando encontramos a distância do ponto X ao ponto Y , isso também nos diz a distância do ponto Y ao ponto X , de forma que o mesmo cálculo pode ser reutilizado em duas consultas diferentes.

Dada uma dimensão fixa, uma norma positiva semi-definida (incluindo assim cada norma L p ), e n pontos neste espaço, o vizinho mais próximo de cada ponto pode ser encontrado no tempo O ( n  log  n ) e nos m vizinhos mais próximos de cada ponto pode ser encontrado em tempo O ( mn  log  n ).

Veja também

Referências

Citações

Origens

Leitura adicional

  • Shasha, Dennis (2004). Descoberta de alto desempenho em séries temporais . Berlim: Springer. ISBN 978-0-387-00857-8.

links externos