Métrica de distância e maldição de dimensões

Em alguns lugares, li uma observação de que, se você tiver muitos parâmetros e tentar encontrar uma "métrica de similaridade" entre esses vetores, poderá ter uma "maldição da dimensioalidade". Acredito que isso significou que a maioria das pontuações de similaridade será igual e não fornecerá nenhuma informação útil. Em outras palavras, quase todos os vetores parceiros terão uma pontuação de média distância que não é útil para categorização ou agrupamento, etc. $(x_1, x_2, \ldots, x_n)$

Você sabe onde eu posso aprender mais em detalhes sobre isso?

Existem métricas que sofrem menos com esse efeito?

distance similarities metric Gerenuk
fonte

Respostas:

Algumas observações clássicas sobre distâncias em dados de alta dimensão:

K. Beyer, J. Goldstein, R. Ramakrishnan e U. Shaft, ICDT 1999: "Quando os vizinhos mais próximos são significativos?"
CC Aggarwal, A. Hinneburg e DA Keim, ICDT 2001: "Sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão"

Algumas pesquisas mais recentes sobre isso, que envolvem vizinhos mais próximos compartilhados e hubness:

ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert e A. Zimek, SSDBM 2010: "As distâncias entre vizinhos podem derrotar a maldição da dimensionalidade?"
T. Bernecker, ME Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert e A. Zimek, SSTD 2011: "Qualidade das classificações de similaridade nas séries temporais"
N. Tomašev, M. Radovanović, D. Mladenić e M. Ivanović. Adv. KDDM 2011: "O papel do hubness no agrupamento de dados de alta dimensão"
Não se lembre dos outros, procure por "Hubness", essa foi a observação em alta dimensão

Isso é interessante, pois apontam alguns mal - entendidos populares sobre a maldição da dimensionalidade. Em essência, eles mostram que os resultados teóricos - que assumem que os dados são iid - geralmente não podem ser verdadeiros para dados que possuem mais de uma distribuição. A maldição leva a problemas numéricos e a uma perda de discriminação em uma única distribuição, enquanto pode facilitar ainda mais a diferenciação de duas distribuições bem separadas.

Parte disso deve ser bastante óbvio. Digamos que você tenha objetos iid em cada dimensão e outro conjunto de objetos que sejam iid em cada dimensão. A diferença entre objetos de dois conjuntos diferentes sempre será magnitudes maiores que a distância em um único conjunto, e o problema ficará ainda mais fácil com o aumento da dimensionalidade . $A_i\sim \mathcal{N}(0;1)$ $B_i\sim \mathcal{N}(100;1)$

Eu recomendo a leitura deste trabalho de Houle et al., Em grande parte porque mostra que, ao afirmar "esses dados são de alta dimensão e, devido à maldição da dimensionalidade, eles não podem ser analisados", você pode facilitar demais as coisas. Ainda assim, essa é uma linha que está sendo usada em todo o lugar. "Nosso algoritmo funciona apenas para dados de baixa dimensão, devido à maldição da dimensionalidade". "Nosso índice funciona apenas para até 10 dimensões, devido à maldição da dimensionalidade." Yadda yadda yadda. Aparentemente, muitas dessas declarações mostram apenas que esses autores não entenderam o que acontece em alta dimensionalidade em seus dados e algoritmo (ou precisavam de uma desculpa). Houle et al. não resolvem completamente o quebra-cabeça (ainda? isso é bastante recente), mas pelo menos reconsideram muitas das declarações populares.

Afinal, se a alta dimensionalidade era um problema tão grande, como as pessoas na mineração de texto usam alegremente as dimensões na ordem de 10000-100000, enquanto em outros domínios as pessoas desistem em apenas 10 dimensões?!?

Quanto à segunda parte da sua pergunta: a semelhança de cosseno parece sofrer menos com a dimensionalidade . Além disso, contanto que você queira diferenciar distribuições diferentes, controle a precisão numérica e não confie nos limites escolhidos à mão (como você pode precisar fornecer muitos dígitos significativos), o -Norms clássico ainda deve ser bom. $L_p$

No entanto, o cosseno também é afetado pela maldição da dimensionalidade , conforme discutido em:

M. Radovanović, A. Nanopoulos e M. Ivanović, SIGIR 2010. "Sobre a existência de resultados obstinados em modelos de espaço vetorial."

Possui QUIT - Anony-Mousse
fonte

Aggarwal CC, Hinneburg A., Keim, DA (2001), "Sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão"
Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999), “Quando os vizinhos mais próximos são significativos?”, Procedimentos da Conferência do ICDE.

user603
fonte

Parece interessante :) Espero conseguir uma cópia deles. Você sabe se existem resoluções para esse problema com métricas comuns?

Gerenuk

(+1) isso parece muito interessante.

Elvis

@ Gerenuk: o que você quer dizer com métricas "comuns"? Além disso, ambos os documentos estão disponíveis. on-line, ungated, como pdfs

user603

Obrigado. Eu acho que os encontrei pelo nome do título. Por métrica comum (eu acho), quero dizer

L_{k}

$L_k$ normas. Portanto, a questão é se existe algum localizador de similaridade simples que faça um trabalho melhor do que

L_{k}

$L_k$ normas.

Gerenuk

As normas L_p fracionárias apenas ocultam o problema. Acredito que o resultado tende a algo como a diferença mínima de atributo, que para um número alto de dimensões se torna igualmente sem sentido na prática. Ele apenas resolve o problema dos números cada vez maiores. A redução de dimensão funciona em alguns casos, mas considere o caso quando ele não o levar mais longe. O que então? Além disso, a redução de dimensão é essencialmente "dimensões de 640k devem ser suficientes para qualquer pessoa". O texto geralmente está no intervalo de 10 ^ 5. E o vídeo?

QuIT - Anony-Mousse

Além disso:

Robert J. Durrant, Ata Kabán: Quando o 'vizinho mais próximo' é significativo: um teorema inverso e implicações. J. Complexity 25 (4): 385-397 (2009)
Ata Kabán: Sobre a concentração à distância, conhecimento de certas técnicas de redução de dados. Reconhecimento de Padrões 44 (2): 265-277 (2011)
Ata Kabán: Detecção não paramétrica de distâncias sem sentido em dados de alta dimensão. Statistics and Computing 22 (2): 375-385 (2012)

axk
fonte