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

Alguns dias atrás, fiz uma pergunta 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 da Matemática, estou começando a me perguntar algumas questões fundamentais:

• A distância euclidiana é uma boa métrica para encontrar os vizinhos mais próximos em primeiro lugar? Caso contrário, quais são minhas opções?
• Além disso, como decidir sobre o limite certo para determinar os k-vizinhos? Existe alguma análise que possa ser feita para descobrir esse valor?
• Anteriormente, me sugeriram usar o kd-Trees, mas a página da Wikipedia diz claramente que, para grandes 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 conjunto de dados de um milhão de pontos com eficiência?

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

Atualmente, estudo esses problemas - classificação, busca por vizinhos mais próximos - pela recuperação de informações musicais.

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

Entre os algoritmos da 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 caixas, ou seja, uma tabela de hash [1] [3]. Mas, diferentemente dos hashes tradicionais, um hash sensível à localidade coloca pontos próximos na mesma lixeira.

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

Segundo, há uma teoria rigorosa que apóia seu desempenho. Pode-se mostrar que o tempo de consulta é sublinear no tamanho do banco de dados, ou seja, mais rápido que a pesquisa linear. Quanto mais rápido depende da quantidade de aproximação que 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 com a métrica de distância de Manhattan (L1). Existem também variantes para distância de Hamming e semelhança de cosseno.

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

O LSH foi aplicado aparentemente em todos os lugares. Você pode tentar.

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

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

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

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

I. A métrica da distância

Primeiro, o número de recursos (colunas) em um conjunto de dados não é um fator na seleção de uma métrica de distância para uso em kNN. Existem alguns estudos publicados direcionados exatamente a essa questão, e as bases usuais para comparação são:

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

• a relação entre os recursos que compõem seus dados (eles são independentes - isto é, 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 das distribuições das quais seus dados foram amostrados, pelo menos um estudo (bem documentado e completo) conclui que a distância euclidiana é a melhor escolha.

Métrica YEuclidiana usada em Mecanismos de Recomendação da Web em grande escala, bem como em pesquisas acadêmicas atuais. As distâncias calculadas por Euclidiano têm significado intuitivo e as escalas de computação - ou seja, a distância euclidiana é calculada da mesma maneira, independentemente de os dois pontos estarem em duas dimensões ou em vinte e duas dimensões.

Só falhou algumas vezes, cada um desses casos a distância euclidiana falhou porque o sistema de coordenadas (cartesiano) subjacente era uma má escolha. E você geralmente reconhece isso porque, por exemplo, os comprimentos do 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 a Euclidiana, da mesma forma quando o espaço métrico é a Terra e suas distâncias são trans - vôos continentais, 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, mas Londres para St Petersburg não é de 5,5 horas, é 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 quadrado do chi fornece 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 os vizinhos mais próximos - Mahalanobis (essencialmente euclidiano normalizado para explicar a covariância da dimensão) foi o melhor neste estudo.

Uma condição importante: para que os cálculos da métrica à distância sejam significativos, você deve redimensionarseus dados - raramente é possível criar um modelo kNN para gerar previsões precisas sem fazer isso. Por exemplo, se você está construindo um modelo de kNN para prever o desempenho atlético, e suas variáveis ​​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. Dito de outra forma, se os dados fossem informados de maneira diferente, de modo que o peso corporal estivesse em gramas em vez de quilogramas, o valor original de 86,1 seria 86.100, o que teria um grande efeito sobre os resultados, exatamente o que você não usa. não quero.

X_new = (X_old - mu) / sigma

II A estrutura de dados

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

Essa não é a maneira mais comum de persistir os dados de treinamento de kNN, embora a aplicação do VT para esse fim, bem como as consequentes vantagens de desempenho, estejam bem documentadas (consulte, 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 Índice TIOBE ), você deverá encontrar uma biblioteca para executar a TV. Eu sei que em Python e R, existem várias opções para cada idioma (por exemplo, o pacote voronoi para R disponível no CRAN )

O uso de um VT para kNN funciona assim:

A partir dos seus dados, selecione aleatoriamente w points - esses são os seus centros Voronoi. Uma célula 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, para que cada ponto atribuído a um determinado centro seja pintado dessa cor. Contanto que você tenha uma densidade suficiente, isso mostrará muito bem os limites de cada centro de Voronoi (como o limite que separa duas cores.

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

Imagine que você tenha um milhão de pontos de dados ... Se os pontos persistissem em uma estrutura de dados 2D comum ou em uma árvore kd, você executaria, em média, alguns milhões de cálculos de distância para cadanovos pontos de dados cuja variável de resposta você deseja prever. Obviamente, esses cálculos são realizados em um único conjunto de dados. Com um V / T, a busca pelo vizinho mais próximo é realizada em duas etapas, uma após a outra, contra duas populações diferentes de dados - primeiro contra os centros Voronoi, depois que o centro mais próximo é encontrado, os pontos dentro da célula correspondentes a esse centro é pesquisado para encontrar o vizinho mais próximo real (por cálculos sucessivos de distância) Combinados, essas duas pesquisas são muito mais rápidas que uma única pesquisa de força bruta. É fácil ver: para 1 milhão de pontos de dados, suponha que você selecione 250 centros Voronoi para otimizar seu espaço de dados. Em média, cada célula Voronoi terá 4.000 pontos de dados. Portanto, em vez de realizar em média 500.000 cálculos de distância (força bruta), você realiza muito menos, em média apenas 125 + 2.000.

III Cálculo do resultado (a variável de resposta prevista)

Há duas etapas para calcular o valor previsto a partir de um conjunto de dados de treinamento kNN. O primeiro é 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.

Com o primeiro componente, é possível 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 apenas usa n = 3. De qualquer forma, é simples executar o algoritmo kNN em 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 função de n. Se você quer apenas um valor plausível para n começar, novamente, basta usar 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 1 / (dist * K), ou o inverso da distância desse vizinho à instância de teste, frequentemente multiplicado por alguma constante derivada empiricamente, K. I não sou fã dessa técnica porque geralmente sobrecarrega demais os vizinhos mais próximos (e concomitantemente sobrecarrega os vizinhos 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 função de ponderação deve melhor, que evita substancialmente essa limitação é a função 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, identifique os n vizinhos mais próximos do ponto de dados cuja variável de resposta deseja prever ('instância de teste') e chame a função weight_gauss, uma vez para cada um dos n vizinhos, passando na distância entre cada vizinho, o ponto de teste. Essa função retornará o peso para cada vizinho, que será usado como coeficiente desse 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 garantir que você realmente precise de todas as 21 dimensões e possivelmente encontre uma transformação linear que permita usar menos de 21 com aproximadamente a mesma qualidade de resultado.

Atualização: Encontrei-os em um livro chamado Processamento de sinais biomédicos de Rangayyan (espero lembrar corretamente). O ICA não é uma técnica trivial, mas foi desenvolvida por pesquisadores na Finlândia e acho que o código do Matlab está disponível publicamente para download. O PCA é uma técnica mais amplamente usada e acredito que você deve encontrar seu R ou outra implementação de software. O PCA é realizado resolvendo equações lineares iterativamente. Eu fiz isso há muito tempo para lembrar como. =)

A idéia é que você divida seus sinais em autovetores independentes (funções autógenas discretas, na verdade) e seus autovalores, 21 no seu caso. Cada valor próprio mostra a quantidade de contribuição que cada função própria fornece a cada uma de suas medidas. Se um valor próprio é pequeno, você pode representar muito de perto os sinais sem usar sua função própria correspondente, e é assim que você se livra de uma dimensão.

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

Como já foi 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 árvore kd, sejam tão lentas quanto uma abordagem de força bruta. Como resultado, voltamos nosso interesse para a Pesquisa Aproximada por Vizinho Mais Próximo (ANNS) , que, a favor de alguma precisão, acelera o processo. Você obtém uma boa aproximação do NN exato, com uma boa propabilidade.

Tópicos importantes que podem ser úteis:

1. Abordagens modernas do LSH , como as de Razenshteyn .
2. Floresta RKD : floresta (s) de árvores kd aleatórias (RKD), conforme descrito na FLANN , ou em uma abordagem mais recente da qual eu fazia parte, kd-GeRaF .
3. LOPQ, que significa Quantization Optimized Locally Product, como descrito aqui . É muito semelhante à nova abordagem de Babenko + Lemptitsky .

Você também pode verificar minhas respostas relevantes:

1. Dois conjuntos de pontos dimensionais altos: Encontre o vizinho mais próximo no outro conjunto
2. Comparação do tempo de execução de consultas de Vizinho Mais Próximo em Estruturas de Dados Diferentes
3. Implementação da árvore kd PCL extremamente lenta

Para responder suas perguntas uma a uma:

• Não, a distância euclidiana é uma métrica ruim no espaço de alta dimensão. Basicamente, em altas dimensões, os pontos de dados têm grandes diferenças entre si. Isso diminui a diferença relativa na distância entre um dado ponto de dados e seu vizinho mais próximo e mais distante.
• Muitos trabalhos / pesquisas existem em dados de alta dimensão, mas a maioria das coisas requer muita sofisticação matemática.
• A árvore KD é ruim para dados de alta dimensão ... evite-a 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 tudo.

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

A similaridade do 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á-la e não minimizá-la. Você também pode usar uma maneira específica de domínio para comparar os dados; por exemplo, se os dados forem sequências de DNA, poderá usar uma semelhança de sequência que leve em consideração as probabilidades de mutações, etc.

O número de vizinhos mais próximos a usar varia de acordo com o tipo de dados, a quantidade de ruído existente, etc. Não há regras gerais, basta encontrar o que funciona melhor para seus dados e problemas específicos, tentando todos os valores dentro de um intervalo . As pessoas têm um entendimento intuitivo de que quanto mais dados houver, menos vizinhos serão necessários. Em uma situação hipotética em que você tem todos os dados possíveis, basta procurar o único vizinho mais próximo a ser classificado.

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.

O kd-trees realmente não funcionará muito bem em dados de alta dimensão. Como a etapa de poda não ajuda muito, pois a borda mais próxima - um desvio unidimensional - quase sempre será menor que o desvio total para os vizinhos mais próximos conhecidos.

Além disso, as árvores kd só funcionam bem com as normas Lp, pelo que sei, e existe o efeito de concentração à 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 ler sobre a maldição da dimensionalidade e suas várias variantes (há mais de um lado!)

Não estou convencido de que haja muita utilidade em aproximar cegamente os vizinhos mais próximos euclidianos, por exemplo, usando LSH ou projeções aleatórias. Pode ser necessário usar uma função de distância muito mais sintonizada em primeiro lugar!

Depende muito do motivo pelo qual você deseja conhecer os vizinhos mais próximos. Você pode procurar no algoritmo de deslocamento médio http://en.wikipedia.org/wiki/Mean-shift se o que você realmente deseja é encontrar os modos do seu conjunto de dados.

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

O iDistance é provavelmente o melhor para recuperação exata do knn em dados de alta dimensão. Você pode vê-lo como um teste aproximado de Voronoi.

Eu experimentei o mesmo problema e posso dizer o seguinte.

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

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 / recuperação para encontrar um valor aceitável.

3. As distâncias euclidiana e Manhattan respeitam a desigualdade do triângulo , portanto você pode usá-las em árvores métricas. De fato, as árvores KD têm seu desempenho severamente degradado quando os dados têm mais de 10 dimensões (eu mesmo experimentei esse problema). Eu achei as árvores VP uma opção melhor.

As árvores KD funcionam bem para 21 dimensões, se você sair mais cedo, depois de analisar, digamos, 5% de todos os pontos. A FLANN faz isso (e outras acelerações) para corresponder aos vetores SIFT de 128 dim. (Infelizmente, a 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.) É claro que existe uma troca de precisão de velocidade aqui.

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

Adicionado em 26 de abril, os tempos de execução do cKDTree com cutoff no meu antigo ppc do mac, para fornecer uma idéia muito rude 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ê pode tentar uma curva de ordem z. É fácil para 3 dimensões.

A distância euclidiana é uma boa métrica para encontrar os vizinhos mais próximos em primeiro lugar? Caso contrário, quais são minhas opções?

Eu sugeriria o agrupamento suave de subespaços , uma abordagem bastante comum atualmente, onde os pesos dos recursos são calculados para encontrar as dimensões mais relevantes. Você pode usar esses pesos ao usar a distância euclidiana, por exemplo. Veja a maldição da dimensionalidade para problemas comuns e também este artigo pode esclarecê-lo de alguma forma:

Um algoritmo de agrupamento do tipo k-means para agrupamento de subespaços de conjuntos de dados numéricos e categóricos mistos