Vizinhos mais próximos em dados de alta dimensão?

Eu fiz uma pergunta alguns dias atrás sobre como encontrar os vizinhos mais próximos para um determinado vetor. Meu vetor agora tem 21 dimensões e antes de prosseguir, porque não sou do domínio do Machine Learning nem do Math, começo a me fazer algumas perguntas fundamentais:

  • A distância euclidiana é uma boa métrica para encontrar os vizinhos mais próximos? Se não, quais são minhas opções?
  • Além disso, como se decide sobre o limite certo para determinar os vizinhos-k? Existe alguma análise que pode ser feita para descobrir esse valor?
  • Anteriormente, foi sugerido usar o kd-Trees, mas a página da Wikipedia diz claramente que para as altas dimensões, o kd-Tree é quase equivalente a uma pesquisa de força bruta. Nesse caso, qual é a melhor maneira de encontrar os vizinhos mais próximos em um dataset de um milhão de pontos de maneira eficiente?

Alguém pode esclarecer algumas (ou todas) as perguntas acima?

Eu atualmente estudo tais problemas – sorting, busca de vizinhos mais próximos – para recuperação de informações musicais.

Você pode estar interessado em Algoritmos Aproximados de Vizinho Mais Próximo ( ANN ). A ideia é que você permita que o algoritmo retorne vizinhos suficientemente próximos (talvez não o vizinho mais próximo); Ao fazer isso, você reduz a complexidade. Você mencionou a tree-kd ; esse é um exemplo. Mas como você disse, a kd-tree funciona mal em altas dimensões. De fato, todas as técnicas de indexação atuais (baseadas no particionamento de espaço) degradam a busca linear por dimensões suficientemente altas [1] [2] [3].

Entre os algoritmos de RNA propostos recentemente, talvez o mais popular seja o Hashing sensível à localidade ( LSH ), que mapeia um conjunto de pontos em um espaço de alta dimensão em um conjunto de checkboxs, isto é, uma tabela de hash [1] [3]. Mas, diferentemente dos hashes tradicionais, um hash sensível à localidade coloca pontos próximos na mesma posição.

O LSH tem algumas vantagens enormes. Primeiro, é simples. Você apenas calcula o hash para todos os pontos em seu database e, em seguida, cria uma tabela de hash a partir deles. Para consultar, basta calcular o hash do ponto de consulta e, em seguida, recuperar todos os pontos no mesmo bin da tabela de hash.

Em segundo lugar, há uma teoria rigorosa que suporta seu desempenho. Pode ser mostrado que o tempo de consulta é sublinear no tamanho do database, ou seja, mais rápido que a pesquisa linear. Quão mais rápido depende de quanta aproximação podemos tolerar.

Finalmente, o LSH é compatível com qualquer norma Lp para 0 < p <= 2 . Portanto, para responder sua primeira pergunta, você pode usar o LSH com a métrica de distância Euclidiana, ou você pode usá-lo com a métrica de distância Manhattan (L1). Existem também variantes para a distância de Hamming e similaridade de cosseno.

Uma visão geral decente foi escrita por Malcolm Slaney e Michael Casey para a revista IEEE Signal Processing Magazine em 2008 [4].

O LSH foi aplicado aparentemente em todos os lugares. Você pode querer experimentá-lo.


[1] Datar, Indyk, Immorlica, Mirrokni, "Esquema de Hashing Sensível a Localidade Baseado em Distribuições p-Stable," 2004.

[2] Weber, Schek, Blott, "Uma análise quantitativa e estudo de desempenho para methods de busca de similaridade em espaços de alta dimensão", 1998.

[3] Gionis, Indyk, Motwani, "Pesquisa de similaridade em altas dimensões via hashing", 1999.

[4] Slaney, Casey, "hash sensível à localidade para encontrar vizinhos mais próximos", 2008.

I. A métrica de distância

Primeiro, o número de resources (colunas) em um dataset não é um fator na seleção de uma métrica de distância para uso no kNN. Existem alguns estudos publicados voltados precisamente para essa questão, e as bases usuais para comparação são:

  • a distribuição estatística subjacente de seus dados;

  • o relacionamento entre os resources que compõem seus dados (eles são independentes – ou seja, como é a matriz de covariância); e

  • o espaço de coordenadas a partir do qual seus dados foram obtidos.

Se você não tem conhecimento prévio da (s) distribuição (ões) de onde seus dados foram amostrados, pelo menos um estudo (bem documentado e minucioso) conclui que a distância euclidiana é a melhor escolha.

YEuclidean métrica utilizada em mega escala Web Recommendation Engines, bem como na pesquisa acadêmica atual. As distâncias calculadas por Euclideanos têm sentido intuitivo e as escalas de cálculo – isto é, a distância euclidiana é calculada da mesma maneira, quer os dois pontos sejam em duas dimensões ou em vinte e duas dimensões.

Só falhou algumas vezes para mim, e cada um desses casos falhou a distância euclidiana porque o sistema de coordenadas subjacente (cartesiano) era uma má escolha. E você normalmente reconhecerá isso porque, por exemplo, os comprimentos de caminho (distâncias) não são mais aditivos – por exemplo, quando o espaço métrico é um tabuleiro de xadrez, a distância de Manhattan é melhor que Euclideana, da mesma forma quando o espaço métrico é Terra e suas distâncias são trans -continental vôos, uma métrica de distância adequada para um sistema de coordenadas polares é uma boa idéia (por exemplo, Londres para Viena é de 2,5 horas, Viena para São Petersburgo é mais 3 horas, mais ou menos na mesma direção, ainda Londres para St Petersburgo não é 5,5 horas, em vez disso, é um pouco mais de 3 horas.)

Mas, além dos casos em que seus dados pertencem a um sistema de coordenadas não-cartesiano, a escolha da métrica de distância geralmente não é material. (Veja esta postagem de blog de um estudante de CS, comparando várias métricas de distância examinando seu efeito no classificador kNN – o qui quadrado dá os melhores resultados, mas as diferenças não são grandes; Um estudo mais abrangente está no artigo acadêmico, Estudo Comparativo de Funções de distância para vizinhos mais próximos – Mahalanobis (essencialmente euclidiano normalizado por considerar a covariância de dimensão) foi o melhor neste estudo.

Uma condição importante: para que os cálculos de métricas à distância sejam significativos, você deve resize seus dados – raramente é possível construir um modelo kNN para gerar previsões precisas sem fazer isso. Por exemplo, se você está construindo um modelo kNN para prever o desempenho atlético, e suas variables ​​de expectativa são altura (cm), peso (kg), gordura corporal (%) e pulso em repouso (batimentos por minuto), um ponto de dados típico pode algo parecido com isto: [180.4, 66.1, 11.3, 71]. Claramente, o cálculo da distância será dominado pela altura, enquanto a contribuição por% de gordura corporal será quase insignificante. Em outras palavras, se os dados fossem reportados de forma diferente, de modo que o peso corporal fosse em gramas em vez de quilogramas, o valor original de 86,1 seria 86.100, o que teria um grande efeito em seus resultados, que é exatamente o que você faz não quer. Provavelmente, a técnica de dimensionamento mais comum é subtrair a média e dividir pelo desvio padrão (média e sd referem-se calculados separadamente para cada coluna ou recurso nesse dataset; X refere-se a uma input / célula individual em uma linha de dados):

 X_new = (X_old - mu) / sigma 

II. A estrutura de dados

Se você está preocupado com o desempenho da estrutura kd-tree, A Voronoi Tessellation é um contêiner conceitualmente simples, mas que melhorará drasticamente o desempenho e melhorará as escalas do que o kd-Trees.

dat

Esta não é a forma mais comum de persistir os dados de treinamento do kNN, embora a aplicação do VT para esse propósito, bem como as consequentes vantagens de desempenho, estejam bem documentadas (ver, por exemplo, este relatório da Microsoft Research ). O significado prático disso é que, desde que você esteja usando uma linguagem ‘mainstream’ (por exemplo, no TIOBE Index ), então você deve encontrar uma biblioteca para realizar VT. Eu sei em Python e R, existem várias opções para cada idioma (por exemplo, o pacote voronoi para R disponível no CRAN )

Usando um VT para kNN funciona assim ::

A partir de seus dados, selecione aleatoriamente w pontos – esses são os seus centros de Voronoi. Uma célula de Voronoi encapsula todos os pontos vizinhos que estão mais próximos de cada centro. Imagine se você atribuir uma cor diferente a cada um dos centros de Voronoi, de modo que cada ponto atribuído a um determinado centro seja pintado dessa cor. Contanto que você tenha uma densidade suficiente, fazer isso mostrará bem os limites de cada centro de Voronoi (como o limite que separa duas colors.

Como selecionar os centros de Voronoi? Eu uso duas diretrizes ortogonais. Após selecionar aleatoriamente os pontos w, calcule o VT para os seus dados de treinamento. Em seguida, verifique o número de pontos de dados atribuídos a cada centro de Voronoi – esses valores devem ser os mesmos (dada a densidade de pontos uniforme em todo o espaço de dados). Em duas dimensões, isso causaria um VT com blocos do mesmo tamanho. Essa é a primeira regra, eis a segunda. Selecione w por iteração – execute seu algoritmo kNN com w como um parâmetro variável e meça o desempenho (tempo necessário para retornar uma previsão consultando o VT).

Então imagine que você tem um milhão de pontos de dados … Se os pontos fossem persistidos em uma estrutura de dados 2D comum, ou em uma tree kd, você executaria em média alguns milhões de cálculos de distância para cada novo ponto de dados cuja variável de resposta você deseja prever. Naturalmente, esses cálculos são realizados em um único dataset. Com uma V / T, a busca do vizinho mais próximo é realizada em duas etapas, uma após a outra, contra duas populações diferentes de dados – primeiro contra os centros de Voronoi e, depois que o centro mais próximo é encontrado, os pontos dentro da célula correspondem a esse centro é procurado para encontrar o vizinho mais próximo real (por cálculos de distâncias sucessivos) Combinados, esses dois vislumbres são muito mais rápidos do que um único exame de força bruta. Isso é fácil de ver: para pontos de dados de 1 milhão, suponha que você selecione 250 centros de Voronoi para configurar seu espaço de dados. Em média, cada célula de Voronoi terá 4.000 pontos de dados. Então, ao invés de realizar em média 500.000 cálculos de distância (força bruta), você executa muito menos, em média apenas 125 + 2.000.

III Calculando o resultado (a variável de resposta prevista)

Há duas etapas para calcular o valor previsto de um dataset de treinamento kNN. A primeira é identificar n, ou o número de vizinhos mais próximos a serem usados ​​para esse cálculo. A segunda é como ponderar sua contribuição para o valor previsto.

W / r / t o primeiro componente, você pode determinar o melhor valor de n resolvendo um problema de otimização (muito semelhante à otimização de mínimos quadrados). Essa é a teoria; na prática, a maioria das pessoas usa apenas n = 3. Em qualquer caso, é simples executar o algoritmo kNN sobre um conjunto de instâncias de teste (para calcular valores previstos) para n = 1, n = 2, n = 3, etc. e plotar o erro como uma function de n. Se você quer apenas um valor plausível para n começar, novamente, use n = 3.

O segundo componente é como ponderar a contribuição de cada um dos vizinhos (assumindo n> 1).

A técnica de ponderação mais simples é apenas multiplicar cada vizinho por um coeficiente de ponderação, que é apenas o 1 / (dist * K), ou o inverso da distância daquele vizinho à instância de teste multiplicada frequentemente por alguma constante derivada empiricamente, K. não sou fã dessa técnica porque muitas vezes sobrecarrega os vizinhos mais próximos (e concomitantemente subestima os mais distantes); O significado disso é que uma determinada previsão pode ser quase inteiramente dependente de um único vizinho, o que, por sua vez, aumenta a sensibilidade do algoritmo ao ruído.

Uma function de ponderação melhor, que evita substancialmente essa limitação, é a function gaussiana , que em python se parece com isso:

 def weight_gauss(dist, sig=2.0) : return math.e**(-dist**2/(2*sig**2)) 

Para calcular um valor previsto usando seu código kNN, você identificaria os n vizinhos mais próximos do ponto de dados cuja variável de resposta você deseja prever (‘instância de teste’), então chama a function weight_gauss, uma vez para cada um dos n vizinhos, passando na distância entre cada vizinho o ponto de teste. Esta function retornará o peso para cada vizinho, que é então usado como o coeficiente daquele vizinho no cálculo da média ponderada.

O que você está enfrentando é conhecido como a maldição da dimensionalidade . Às vezes é útil executar um algoritmo como PCA ou ICA para certificar-se de que você realmente precisa de todas as 21 dimensões e possivelmente encontrar uma transformação linear que permita usar menos de 21 com aproximadamente a mesma qualidade de resultado.

Update: Encontrei-os em um livro chamado Biomedical Signal Processing por Rangayyan (espero que eu me lembre corretamente). O ICA não é uma técnica trivial, mas foi desenvolvido por pesquisadores na Finlândia e acho que o código do Matlab para ele está disponível publicamente para download. O PCA é uma técnica mais amplamente usada e acredito que você deve ser capaz de encontrar sua implementação de software R ou outro. O PCA é realizado resolvendo equações lineares iterativamente. Eu fiz isso há muito tempo para lembrar como. =)

A ideia é que você divida seus sinais em autovetores independentes (autofunções discretas, na verdade) e seus autovalores, 21 no seu caso. Cada autovalor mostra a quantidade de contribuição que cada autofunction fornece a cada uma de suas medições. Se um autovalor é pequeno, você pode representar muito de perto os sinais sem usar sua function autogênica correspondente, e é assim que você se livra de uma dimensão.

Para responder às suas perguntas, uma por uma:

  • Não, a distância euclidiana é uma métrica ruim no espaço dimensional alto. Basicamente em altas dimensões, há pouca diferença entre o vizinho mais próximo e o mais distante.
  • Muitos trabalhos / pesquisas existem em dados de alta dimensão, mas a maioria das coisas requer muita sofisticação matemática.
  • A tree de KD é ruim para dados dimensionais altos … evite isto por todos os meios

Aqui está um bom artigo para você começar na direção certa. ” Quando no vizinho mais próximo significativo ?” por Beyer et all.

Eu trabalho com dados de texto de dimensões 20K e acima. Se você quiser algum conselho relacionado a texto, talvez eu possa ajudá-lo.

As respostas principais são boas, mas antigas, então gostaria de adicionar uma resposta de 2016 .


Como dito, em um espaço dimensional alto, a maldição da dimensionalidade espreita ao virar da esquina, fazendo com que as abordagens tradicionais, como a popular tree kd, sejam tão lentas quanto uma abordagem de força bruta. Como resultado, voltamos nosso interesse na Busca Aproximada de Vizinho Mais Próximo (ANNS) , que em favor de alguma precisão, acelera o processo. Você obtém uma boa aproximação do NN exato, com uma boa propensão.


Tópicos quentes que podem valer a pena:

  1. Abordagens modernas de LSH , como as de Razenshteyn .
  2. Floresta RKD : Floresta (s) de Árvores Randomizadas kd (RKD), como descrito em FLANN , ou em uma abordagem mais recente da qual eu fiz parte, kd-GeRaF .
  3. LOPQ que significa Quantificação de Produto Otimizada Localmente, como descrito aqui . É muito semelhante à nova abordagem de Babenko + Lemptitsky.

Você também pode verificar minhas respostas relevantes:

  1. Dois conjuntos de pontos de alta dimensão: Encontre o vizinho mais próximo no outro conjunto
  2. Comparação do tempo de execução de consultas vizinhas mais próximas em diferentes estruturas de dados
  3. Implementação PCL kd-tree extremamente lenta

A semelhança de cosseno é uma maneira comum de comparar vetores de alta dimensão. Observe que, como é uma semelhança e não uma distância, você deseja maximizá-lo e não minimizá-lo. Você também pode usar uma maneira específica de domínio para comparar os dados, por exemplo, se seus dados fossem sequências de DNA, você poderia usar uma similaridade de seqüência que leva em conta as probabilidades de mutações, etc.

O número de vizinhos mais próximos a utilizar varia consoante o tipo de dados, o nível de ruído, etc. Não existem regras gerais, apenas tem de encontrar o que funciona melhor para os seus dados e problemas específicos ao tentar todos os valores dentro de um intervalo . As pessoas têm uma compreensão intuitiva de que quanto mais dados houver, menos vizinhos você precisará. Em uma situação hipotética na qual você tem todos os dados possíveis, você só precisa procurar pelo vizinho mais próximo para classificar.

O método k vizinho mais próximo é conhecido por ser computacionalmente caro. É uma das principais razões pelas quais as pessoas recorrem a outros algoritmos, como máquinas de vetores de suporte.

Depende muito de por que você quer conhecer os vizinhos mais próximos. Você pode olhar para o algoritmo de deslocamento médio http://en.wikipedia.org/wiki/Mean-shift se o que você realmente quer é encontrar os modos do seu dataset.

De fato, as trees-kd não funcionam muito bem em dados de alta dimensão. Porque a etapa de remoção não ajuda muito, já que a borda mais próxima – um desvio de 1 dimensão – será quase sempre menor que o desvio de dimensão completa para os vizinhos mais próximos conhecidos.

Mas, além disso, as kd-trees só funcionam bem com as normas Lp, pelo que sei, e existe o efeito de concentração de distância que faz com que os algoritmos baseados na distância se degradem com o aumento da dimensionalidade.

Para mais informações, você pode querer ler sobre a maldição da dimensionalidade, e as várias variantes dela (há mais de um lado para isso!)

Eu não estou convencido de que há muito uso apenas para cegamente aproximar os vizinhos mais próximos de Euclides, por exemplo, usando LSH ou projeções aleatórias. Pode ser necessário usar uma function de distância muito mais precisa em primeiro lugar!

iDistance é provavelmente o melhor para recuperação exata de knn em dados de alta dimensão. Você pode visualizá-lo como uma tese de Voronoi aproximada.

KD Trees funciona bem para 21 dimensões, se você sair cedo, depois de olhar para dizer 5% de todos os pontos. O FLANN faz isso (e outras acelerações) para corresponder aos vetores SIFT de 128 dim. (Infelizmente o FLANN faz apenas a métrica Euclidiana, e o rápido e sólido scipy.spatial.cKDTree faz apenas métricas de Lp; elas podem ou não ser adequadas para seus dados.) Há, naturalmente, uma troca de precisão de velocidade aqui.

(Se você pudesse descrever sua distribuição de dados Ndata, Nquery, isso poderia ajudar as pessoas a tentar dados semelhantes.)

Adicionado 26 de abril, tempos de execução para o cKDTree com limite no meu antigo mac ppc, para dar uma ideia muito aproximada de viabilidade:

 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 % 3.5 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.253 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 % 15 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.245 

Você poderia tentar uma curva de ordem az. É fácil para 3 dimensões.

Eu acho que cosseno em tf-idf de resources booleanos funcionaria bem para a maioria dos problemas. Isso porque sua heurística comprovada pelo tempo é usada em muitos mecanismos de busca como o Lucene. A distância euclidiana na minha experiência mostra resultados ruins para qualquer dado semelhante a um texto. A seleção de diferentes pesos e exemplos-k pode ser feita com dados de treinamento e seleção de parâmetros de força bruta.

Eu experimentei o mesmo problema e posso dizer o seguinte.

  1. A distância euclidiana é uma métrica de boa distância, no entanto, é computacionalmente mais cara que a distância de Manhattan e, às vezes, produz resultados um pouco mais fracos, portanto, eu escolheria a última.

  2. O valor de k pode ser encontrado empiricamente. Você pode tentar valores diferentes e verificar as curvas ROC resultantes ou alguma outra medida de precisão / rechamada para encontrar um valor aceitável.

  3. Ambas as distâncias Euclidiana e de Manhattan respeitam a desigualdade do Triângulo , assim você pode usá-las em trees métricas. De fato, as trees KD têm seu desempenho severamente degradado quando os dados têm mais de 10 dimensões (já passei por esse problema). Eu encontrei VP-trees para ser uma opção melhor.

A distância euclidiana é uma boa métrica para encontrar os vizinhos mais próximos? Se não, quais são minhas opções?

Eu sugeriria clustering de subespaço flexível , uma abordagem bastante comum hoje em dia, em que pesos de resources são calculados para encontrar as dimensões mais relevantes. Você pode usar esses pesos ao usar a distância euclidiana, por exemplo. Veja maldição de dimensionalidade para problemas comuns e também este artigo pode esclarecer de alguma forma:

Um algoritmo de clusterização do tipo k-means para clustering de subespaço de conjuntos de dados numéricos e categóricos mistos