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

8

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.(x1,x2,,xn)

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

Existem métricas que sofrem menos com esse efeito?

Gerenuk
fonte

Respostas:

11

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 .UMAEuN(0 0;1)BEuN(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.eup

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
10
  • 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 dizereuknormas. Portanto, a questão é se existe algum localizador de similaridade simples que faça um trabalho melhor do queeuknormas.
Gerenuk
1
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
2

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