O que é a pesquisa ANN (Approximate Nearest Neighbor)?

O que é a pesquisa ANN (Approximate Nearest Neighbor)?

A pesquisa do vizinho mais próximo aproximado é uma técnica poderosa em pipelines de aprendizagem automática (ML) e de ciência de dados que permite uma pesquisa eficiente de semelhança semântica em grandes conjuntos de dados frequentemente encontrados em bases de dados vectoriais como Zilliz. ANNS é um método para encontrar o vizinho mais próximo de um determinado ponto de consulta num grande conjunto de dados de pontos, utilizando vários algoritmos de vizinho mais próximo aproximado. O objetivo do ANNS é encontrar um vizinho mais próximo aproximado com elevada probabilidade, minimizando o custo computacional. O ANNS navega de forma inteligente no espaço de pesquisa para localizar correspondências aproximadas de forma eficiente, melhorando significativamente o desempenho em comparação com pesquisas exaustivas.

O algoritmo padrão de pesquisa do vizinho mais próximo (pesquisa NN) é uma pesquisa exaustiva que verifica a distância entre o ponto de consulta e todos os outros pontos do conjunto de dados. No entanto, isto pode ser computacionalmente dispendioso e inviável para grandes conjuntos de dados. O ANNS é uma solução para este problema que utiliza uma estrutura de dados ou um algoritmo para reduzir os cálculos de distância necessários.

Introdução ao ANNS

Approximate Nearest Neighbor Search (ANNS) é uma técnica utilizada em pipelines de aprendizagem automática e de ciência de dados para uma pesquisa eficiente de semelhanças semânticas em grandes conjuntos de dados. A ANNS funciona num espaço vetorial, que é uma representação matemática de dados de elevada dimensão utilizada para efetuar pesquisas de semelhança eficientes. O ANNS visa encontrar um vizinho mais próximo aproximado com alta probabilidade, minimizando o custo computacional. Esta abordagem é particularmente útil quando se lida com dados de elevada dimensão, onde a pesquisa exacta do vizinho mais próximo pode tornar-se computacionalmente dispendiosa e impraticável. Ao utilizar o ANNS, podemos alcançar um equilíbrio entre precisão e eficiência, tornando-o uma ferramenta valiosa para aplicações que requerem uma pesquisa de semelhanças rápida e fiável.

Evolução dos algoritmos de pesquisa

A evolução dos algoritmos de pesquisa tem sido um processo contínuo, com várias técnicas surgindo para enfrentar os desafios de lidar com conjuntos de dados grandes e complexos. Os métodos de pesquisa tradicionais, como a pesquisa exacta do vizinho mais próximo, foram inicialmente utilizados para encontrar os pontos de dados mais próximos de um determinado ponto de consulta. No entanto, estes métodos eram computacionalmente dispendiosos e pouco práticos para dados de elevada dimensão. O desenvolvimento de algoritmos de pesquisa do vizinho mais próximo aproximado (ANN) constituiu um marco significativo na evolução dos algoritmos de pesquisa. Os algoritmos ANN, como o locality-sensitive hashing (LSH) e as árvores KD, foram concebidos para procurar eficientemente os vizinhos mais próximos aproximados em espaços de elevada dimensão. Estes algoritmos têm sido amplamente adoptados em várias aplicações, incluindo o reconhecimento de imagens, o processamento de linguagem natural e os sistemas de recomendação.

Diferenças entre NN, ANN e KNN

A seguir, serão esclarecidas as diferenças entre Vizinho mais próximo (NN), Vizinho mais próximo aproximado (ANN) e K-Nearest Neighbors (KNN):

Vizinho mais próximo (NN):

NN é um algoritmo básico usado para tarefas de classificação e regressão.
Funciona encontrando o único ponto de dados mais próximo (vizinho) de um determinado ponto de consulta com base numa métrica de distância (por exemplo, distância euclidiana).
A classe ou valor do ponto de consulta é determinado pela classe ou valor do seu vizinho mais próximo.
O NN é um algoritmo simples e intuitivo, mas pode ser computacionalmente dispendioso para grandes conjuntos de dados.

Vizinho mais próximo aproximado (ANN):

ANN é uma variante do algoritmo do vizinho mais próximo que visa encontrar vizinhos mais próximos aproximados em vez de vizinhos exactos.
É utilizado quando o conjunto de dados é muito grande e encontrar os vizinhos mais próximos exactos é computacionalmente dispendioso ou inviável.
Os algoritmos ANN trocam alguma precisão por maior velocidade e eficiência.
Utilizam técnicas como o hashing sensível à localidade (LSH) ou estruturas baseadas em árvores para encontrar rapidamente os vizinhos mais próximos aproximados.
Os algoritmos ANN pesquisam várias partições com base no vetor de consulta para reduzir a perda de precisão.
A ANN é útil em cenários em que um resultado aproximado é suficiente e o conjunto de dados é demasiado grande para a pesquisa exacta do vizinho mais próximo.

K-Nearest Neighbors (KNN):

KNN é uma extensão do algoritmo do vizinho mais próximo que considera os K vizinhos mais próximos em vez de apenas um.
Funciona identificando os K pontos de dados mais semelhantes no espaço de caraterísticas, onde a semelhança é medida usando uma função de distância escolhida.
A classe ou o valor do ponto de consulta é determinado pela classe maioritária ou pelo valor médio dos seus K vizinhos mais próximos.
O KNN é um algoritmo não paramétrico e pode ser utilizado tanto para tarefas de classificação como de regressão.
A escolha de K é importante e pode afetar o desempenho e a generalização do algoritmo.

As principais diferenças entre esses algoritmos são:

O NN considera apenas o único vizinho mais próximo, enquanto o KNN considera K vizinhos mais próximos.
ANN concentra-se em encontrar os vizinhos mais próximos aproximados de forma eficiente, sacrificando alguma precisão pela velocidade.
KNN é um algoritmo mais geral que pode ser usado tanto para classificação quanto para regressão, enquanto NN e ANN são usados principalmente para pesquisa de vizinhos mais próximos.

Basicamente, o NN encontra o único vizinho mais próximo, o ANN encontra os vizinhos mais próximos de forma eficiente e o KNN considera K vizinhos mais próximos para tarefas de classificação ou regressão.

Motivação dos vizinhos mais próximos

O vizinho mais próximo é um conceito fundamental na aprendizagem automática e na ciência dos dados, utilizado em várias aplicações, como o reconhecimento de imagens, o processamento de linguagem natural e os sistemas de recomendação. Estes algoritmos utilizam vectores de consulta para representar os pedidos de pesquisa, que são depois comparados com os pontos de dados no conjunto de dados para encontrar os mais semelhantes. A motivação subjacente aos algoritmos do vizinho mais próximo é encontrar os pontos de dados mais semelhantes a um determinado ponto de consulta, que podem ser utilizados para classificação, regressão e outras tarefas. No entanto, à medida que os conjuntos de dados crescem em tamanho e dimensionalidade, a pesquisa exacta do vizinho mais próximo torna-se cada vez mais difícil. O custo computacional de verificar cada ponto de dados num grande conjunto de dados pode ser proibitivo, tornando o ANNS uma solução valiosa. A ANNS fornece uma forma eficiente de encontrar pontos de dados semelhantes sem a necessidade de pesquisa exaustiva, permitindo assim aplicações de aprendizagem automática escaláveis e de elevado desempenho.

Mecânica dos vizinhos mais próximos aproximados

Os algoritmos de pesquisa ANN (Approximate Nearest Neighbours) funcionam mapeando pontos de dados em um espaço de alta dimensão e identificando rapidamente os pontos mais próximos de um ponto de consulta. A chave para a eficiência do ANN está no uso de algoritmos como o hashing sensível à localidade (LSH), que coloca itens semelhantes no mesmo intervalo, reduzindo significativamente o tempo de pesquisa. Ao contrário dos métodos de pesquisa exaustiva que avaliam todos os outros pontos do conjunto de dados, a RNA utiliza uma abordagem mais eficiente. Esta abordagem envolve frequentemente métodos baseados em grafos, em que os pontos de dados são nós num grafo, e a procura dos vizinhos mais próximos torna-se um problema de procura de caminhos dentro deste grafo. A mecânica da pesquisa ANN envolve vários componentes-chave, incluindo o pré-processamento de dados, a criação de índices e a execução de consultas.

Quando utilizar a pesquisa do vizinho mais próximo aproximado?

As técnicas de pesquisa do vizinho mais próximo aproximado têm aplicação em vários domínios, incluindo sistemas de recomendação, reconhecimento de imagem e áudio, processamento de linguagem natural (NLP) e Retrieval Augmented Generation (RAG). As pesquisas vectoriais são cruciais nestas aplicações, permitindo a recuperação eficiente de itens semelhantes com base nas suas representações vectoriais. Os métodos ANNS podem fornecer soluções aproximadas que são suficientemente exactas para muitas aplicações, mesmo quando se trata de grandes conjuntos de dados.

Algoritmos ANNS comuns

Os algoritmos ANNS usam uma variedade de estruturas de dados e algoritmos de vizinho mais próximo aproximado que são projetados para otimizar o processo de pesquisa. Alguns algoritmos ANNS populares incluem KD-trees, locality-sensitive hashing (LSH), e product quantization. As árvores KD são normalmente utilizadas em espaços de baixa dimensão, enquanto o LSH é preferido para espaços de alta dimensão. A [Product quantization] (https://zilliz.com/learn/scalar-quantization-and-product-quantization) é uma técnica que divide o espaço de caraterísticas em subespaços e comprime cada subespaço num pequeno livro de códigos.

O conjunto de dados é dividido numa estrutura em forma de árvore em KD-trees, em que cada nó representa uma região de pontos. O algoritmo percorre a árvore durante o processo de pesquisa, verificando as áreas mais próximas do ponto de consulta. Em contraste, o LSH agrupa pontos semelhantes no mesmo balde, permitindo uma recuperação rápida dos vizinhos mais próximos. A quantização de produtos verifica os códigos de cada subespaço para encontrar o vizinho mais próximo aproximado.

A eficiência com que os algoritmos ANNS podem encontrar o vizinho mais próximo aproximado torna-os populares em várias aplicações. Nos sistemas de recomendação, os algoritmos ANNS podem ser utilizados para encontrar itens ou utilizadores semelhantes de forma eficiente. Os algoritmos ANNS podem ajudar a encontrar imagens e sons correspondentes no reconhecimento de imagem e áudio. No processamento de linguagem natural, os algoritmos ANNS podem encontrar documentos ou frases semelhantes.

Escolhendo o algoritmo ANNS correto

A escolha dos algoritmos de vizinho mais próximo aproximado adequados depende de vários factores, incluindo a dimensão e o tamanho do conjunto de dados, o nível de precisão pretendido e os recursos computacionais disponíveis. Alguns algoritmos ANNS populares incluem KD-trees, Locality-Sensitive Hashing (LSH) e Product Quantization. As KD-trees são adequadas para dados de baixa dimensão e consultas baseadas na distância euclidiana, enquanto a LSH é preferida para dados de alta dimensão e consultas baseadas em [cosine similarity] (https://zilliz.com/blog/similarity-metrics-for-vetor-search). A Quantização de Produtos é uma técnica que divide o espaço de caraterísticas em subespaços e comprime cada subespaço num pequeno livro de códigos. Cada um destes algoritmos tem as suas vantagens e desvantagens, pelo que a seleção do algoritmo adequado requer uma análise cuidadosa dos requisitos específicos da sua aplicação.

Implementando ANNS em sua aplicação

A implementação do ANNS na sua aplicação envolve várias etapas, incluindo o pré-processamento de dados, a criação de índices e a execução de consultas. O pré-processamento de dados envolve a transformação dos dados em um formato adequado para ANNS, como a normalização dos vetores ou a [redução da dimensionalidade] (https://zilliz.com/glossary/dimensionality-reduction). A construção do índice envolve a criação de uma estrutura de dados que permita uma pesquisa eficiente, como uma árvore KD ou uma tabela de hash. A execução da consulta envolve a pesquisa no índice para encontrar os vizinhos mais próximos de um determinado ponto de consulta utilizando vectores de consulta. Várias bibliotecas e estruturas, como FAISS e Annoy, fornecem implementações eficientes de algoritmos ANNS que podem ser facilmente integrados na sua aplicação. Seguindo estas etapas, é possível aproveitar o poder do ANNS para criar sistemas de pesquisa por similaridade escalonáveis e eficientes.

Quando usar a pesquisa aproximada do vizinho mais próximo?

Ao lidar com dados de alta dimensão, encontrar o vizinho mais próximo exato pode se tornar computacionalmente caro e desnecessário. Na pesquisa vetorial, os dados são representados em um espaço vetorial, o que permite pesquisas de similaridade eficientes em conjuntos de dados de alta dimensão. Nestes casos, a pesquisa do vizinho mais próximo aproximado reduz significativamente o tempo de pesquisa, ao mesmo tempo que fornece um resultado razoavelmente exato. A pesquisa do vizinho mais próximo aproximado é normalmente utilizada em aplicações como o reconhecimento de imagem e de voz, sistemas de recomendação e processamento de linguagem natural.

Importância da ANNS na pesquisa vetorial

A pesquisa vetorial é um componente crítico de muitas aplicações de aprendizagem automática, em que os dados são representados como vectores densos em espaços de elevada dimensão. As pesquisas vectoriais são parte integrante destas aplicações, permitindo a recuperação rápida e precisa de itens semelhantes com base nas suas representações vectoriais. O ANNS desempenha um papel crucial na pesquisa vetorial, permitindo a recuperação rápida e eficiente de vectores semelhantes em conjuntos de dados maciços. Utilizando ANNS, os programadores podem criar sistemas de pesquisa vetorial escaláveis e de elevado desempenho que podem tratar grandes volumes de dados e fornecer resultados precisos em tempo real. Esta capacidade é essencial para aplicações como sistemas de recomendação, reconhecimento de imagem e áudio e processamento de linguagem natural, onde a pesquisa de semelhanças rápida e fiável é fundamental.

Pesquisa do vizinho mais próximo aproximado em aplicações do mundo real

A pesquisa aproximada do vizinho mais próximo (ANN) tem inúmeras aplicações em cenários do mundo real. No reconhecimento de imagens, a ANN pode identificar rapidamente imagens com caraterísticas semelhantes a partir de um vasto conjunto de dados. Nos serviços de streaming de música, a ANN pode ser utilizada para recomendar canções que correspondam às preferências de um utilizador, mesmo que não sejam exatamente iguais. Nos cuidados de saúde, as RNA ajudam a identificar rapidamente imagens de diagnóstico semelhantes a uma consulta, melhorando a velocidade e a precisão dos diagnósticos dos pacientes. As RNA são também utilizadas no processamento de linguagem natural, em sistemas de recomendação e na geração aumentada de recuperação (RAG). A eficácia da pesquisa ANN nestas aplicações é demonstrada pelo seu tratamento de estruturas de dados complexas e pela sua adaptabilidade a dados de dimensões crescentes.

Melhores práticas para implementar a pesquisa de vizinho mais próximo aproximado

A implementação da busca aproximada do vizinho mais próximo (ANN) requer uma consideração cuidadosa de vários fatores. Primeiro, é essencial escolher o algoritmo ANN correto para o caso de uso específico. Diferentes algoritmos, como LSH e KD-trees, têm os seus pontos fortes e desvantagens, e a seleção do algoritmo adequado requer uma análise cuidadosa dos requisitos específicos da aplicação. Em segundo lugar, o pré-processamento dos dados é crucial para a pesquisa de RNA. Isto envolve a transformação dos dados num formato adequado para a RNA, como a normalização dos vectores ou a redução da dimensionalidade. Em terceiro lugar, a criação de índices é um passo fundamental na pesquisa de RNAs. Isso envolve a criação de uma estrutura de dados que permita uma pesquisa eficiente, como uma árvore KD ou uma tabela de hash. Finalmente, a execução da consulta envolve a pesquisa do índice para encontrar os vizinhos mais próximos de um determinado ponto de consulta.

Futuro da pesquisa do vizinho mais próximo aproximado

O futuro da pesquisa do vizinho mais próximo aproximado (ANN) é promissor, com pesquisas e desenvolvimentos em andamento no campo. Uma área de pesquisa é o desenvolvimento de algoritmos ANN mais eficientes que podem lidar com conjuntos de dados ainda maiores e mais complexos. Outra área de investigação é a aplicação da pesquisa ANN em domínios emergentes, como os veículos autónomos e a robótica. Além disso, espera-se que a utilização crescente da pesquisa vetorial em várias aplicações impulsione a procura de algoritmos ANN mais eficientes e escaláveis. À medida que o campo continua a evoluir, podemos esperar ver mais aplicações inovadoras da pesquisa ANN em várias indústrias e domínios.

Resumo da pesquisa do vizinho mais próximo aproximado

Em conclusão, os algoritmos de vizinho mais próximo aproximado são ferramentas valiosas na ciência de dados e nos pipelines de aprendizado de máquina. Usando estruturas de dados e algoritmos inteligentes, os ANNS podem fornecer soluções computacionalmente viáveis que ainda são suficientemente precisas para muitas aplicações. Além disso, as técnicas ANNS são amplamente aplicáveis e permitem uma pesquisa eficiente do vizinho mais próximo em grandes conjuntos de dados.

Conteúdo

Comece grátis, escale facilmente

Experimente o banco de dados totalmente gerenciado, construído para seus aplicativos GenAI.

Experimente o Zilliz Cloud grátis

Compartilhar este artigo

Recursos relacionados

DiskANN: Uma solução ANNS baseada em disco

com elevada recuperação e elevado QPS num conjunto de dados à escala de milhares de milhões

Pesquisa do vizinho mais próximo com base em gráficos de proximidade

Como funciona o ANNS baseado no PG?

Zilliz triunfou no desafio de pesquisa ANN em bilhões de escalas do NeurIPS 2021

A equipa de investigação Zilliz obteve o primeiro lugar.