Por que a distância euclidiana não é uma boa métrica em grandes dimensões?

240

Li que "a distância euclidiana não é uma boa distância em grandes dimensões". Acho que essa afirmação tem algo a ver com a maldição da dimensionalidade, mas o que exatamente? Além disso, o que são 'altas dimensões'? Tenho aplicado clustering hierárquico usando distância euclidiana com 100 recursos. Até quantos recursos é 'seguro' usar essa métrica?

teaLeef
fonte
5
Intimamente relacionado: a distância euclidiana geralmente não é boa para dados esparsos? como apontado por facuq .
cardeal
5
Isso provavelmente é básico demais para você; Escrevi uma série de postagens de blog sobre o tema da métrica euclidiana em dimensões mais altas e como isso afeta a pesquisa em espaços vetoriais para as correspondências mais próximas. blogs.msdn.com/b/ericlippert/archive/tags/…
Eric Lippert
1
@ HorstGrünbusch veja as respostas abaixo para algumas referências. A variação das distâncias se torna pequena comparada à média. Então, em algum momento, você encontra problemas para escolher limites, pesos, pedidos; e você também pode ter problemas de precisão numérica. Mas se seus dados são escassos, é provável que tenham uma dimensionalidade intrínseca muito menor .
Anony-Mousse
3
"altas dimensões" parece ser um termo enganador - algumas respostas tratam 9-12 como "altas dimensões", mas em outras áreas a alta dimensionalidade significaria milhares ou um milhão de dimensões (por exemplo, medir ângulos entre vetores de palavras-chave onde cada dimensão é a frequência de alguma palavra em um dicionário) e 100 dimensões seriam chamadas de baixa, não alta.
Peteris 20/05
2
Esta questão poderia realmente ter algum contexto. Não é bom para quê?
Szabolcs 20/05

Respostas:

243

Um ótimo resumo de resultados não intuitivos em dimensões mais altas vem de " Algumas coisas úteis para saber sobre aprendizado de máquina ", de Pedro Domingos, da Universidade de Washington:

Nossas intuições, que vêm de um mundo tridimensional, geralmente não se aplicam às de alta dimensão. Em altas dimensões, a maior parte da massa de uma distribuição gaussiana multivariada não está próxima da média, mas em uma "concha" cada vez mais distante à sua volta; e a maior parte do volume de uma laranja de alta dimensão está na pele, não na polpa. Se um número constante de exemplos é distribuído uniformemente em um hipercubo de alta dimensão, além de alguma dimensionalidade, a maioria dos exemplos está mais próxima de uma face do hipercubo do que de seu vizinho mais próximo. E se aproximamos uma hiperesfera inscrevendo-a em um hipercubo, em altas dimensões quase todo o volume do hipercubo está fora da hiperesfera. Isso é uma má notícia para o aprendizado de máquina, onde formas de um tipo são frequentemente aproximadas por formas de outro.

O artigo também está cheio de muitas pérolas de sabedoria adicionais para aprendizado de máquina.

Outra aplicação, além do aprendizado de máquina, é a busca por vizinhos mais próximos: dada uma observação de interesse, encontre seus vizinhos mais próximos (no sentido de que esses são os pontos com a menor distância do ponto de consulta). Mas em altas dimensões, surge um fenômeno curioso: a relação entre os pontos mais próximos e os mais distantes se aproxima de 1, ou seja, os pontos se tornam essencialmente uniformemente distantes um do outro. Esse fenômeno pode ser observado para uma grande variedade de métricas de distância, mas é mais pronunciado para a métrica euclidiana do que, por exemplo, a métrica de distância de Manhattan. A premissa da busca por vizinhos mais próximos é que os pontos "mais próximos" são mais relevantes do que os pontos "mais distantes", mas se todos os pontos estiverem essencialmente uniformemente distantes um do outro, a distinção não terá sentido.

De Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim, " Sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão ":

Foi argumentado em [Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, " Quando é 'o vizinho mais próximo' é significativo? "] Que, sob certas suposições razoáveis ​​sobre a distribuição de dados, a proporção das distâncias dos vizinhos mais próximos e mais distantes para um determinado destino no espaço de alta dimensão é quase 1 para uma ampla variedade de distribuições de dados e funções de distância. Nesse caso, o problema do vizinho mais próximo fica mal definido, pois o contraste entre as distâncias para os diferentes pontos de dados não existe. Nesses casos, mesmo o conceito de proximidade pode não ser significativo do ponto de vista qualitativo: um problema que é ainda mais fundamental do que a degradação do desempenho de algoritmos de alta dimensão.

... Muitas estruturas e algoritmos de indexação de alta dimensão usam a métrica de distância [E] uclidean como uma extensão natural de seu uso tradicional em aplicações espaciais bidimensionais ou tridimensionais. ... Neste artigo, fornecemos alguns resultados teóricos e experimentais surpreendentes na análise da dependência da norma no valor de . Mais especificamente, mostramos que os contrastes relativos das distâncias até um ponto de consulta dependem muito da métrica usada. Isso fornece evidências consideráveis ​​de que a significância da norma piora mais rapidamente dentro da crescente dimensionalidade para valores mais altos de . Assim, para um dado problema com um valor fixo (alto) para a dimensionalidade k L k L k k d k L 1 L 2LkkLkLkkd, pode ser preferível usar valores mais baixos de . Isso significa que a métrica de distância (métrica de distância de Manhattan) é a mais preferível para aplicações de alta dimensão, seguida pela métrica euclidiana ( ). ...kL1L2

Os autores do artigo "Surprising Behavior" propõem o uso de normas com . Eles produzem alguns resultados que demonstram que essas "normas fracionárias" exibem a propriedade de aumentar o contraste entre os pontos mais distantes e os mais próximos. Isso pode ser útil em alguns contextos, mas há uma ressalva: essas "normas fracionárias" não são métricas de distância adequadas porque violam a desigualdade do triângulo. Se a desigualdade do triângulo é uma qualidade importante em sua pesquisa, as métricas fracionárias não serão tremendamente úteis. k < 1Lkk<1

Sycorax
fonte
7
esta referência é impressionante
Antoine
1
Ler mais uma vez ... Lindo ...
Richard Hardy
113

A noção de distância euclidiana, que funciona bem nos mundos bidimensionais e tridimensionais estudados por Euclides, tem algumas propriedades em dimensões superiores que são contrárias à nossa (talvez apenas minha ) intuição geométrica, que também é uma extrapolação de duas e três dimensões.

Considere um quadrado com vértices em . Desenhe quatro círculos de raio unitário centralizados em . Estes "preenchem" o quadrado, com cada círculo tocando os lados do quadrado em dois pontos, e cada círculo tocando seus dois vizinhos. Por exemplo, o círculo centralizado em toca os lados do quadrado em e e os círculos vizinhos em e . Em seguida, desenhe um pequeno círculo centrado na origem( ± 2 , ± 2 ) ( ± 1 , ± 1 ) ( 1 , 1 ) ( 2 , 1 ) ( 1 , 2 ) ( 1 , 0 ) ( 0 , 1 )4×4(±2,±2)(±1,±1)(1,1)(2,1)(1,2)(1,0)(0,1)r2=21(±r2/2,±r2/2)(r2,0)(2,0,0)(1,0,0)(1,1)(1,1)

4×4×4(±2,±2,±2)8(±1,±1,±1)r3=31<1(r3,0,0)(2,0,0)

n42n(±1,±1,,±1)

(1)rn=n1
(rn,0,0,,0)(1)n=4rn=1n4n>9(1)rn>2(rn,0,0,,0)4 mesmo que esteja "completamente cercado" pelas hiperesferas de raio unitário que "preenchem" o hipercubo (no sentido de compactá-lo). A esfera central "incha" fora do hipercubo no espaço de alta dimensão. Acho isso muito contra-intuitivo, porque minhas traduções mentais da noção de distância euclidiana para dimensões superiores, usando a intuição geométrica que desenvolvi a partir dos espaços 2 e 3 com os quais estou familiarizado, não descrevem a realidade de espaço de alta dimensão.

n9

Dilip Sarwate
fonte
9
@ stackoverflowuser2010: Se esta resposta é completamente incompreensível, como você pode saber se ela resolve ou tenta resolver a pergunta original? Uma abordagem mais construtiva pode ser a elucidação de quaisquer pontos que você achar incerto, em vez de descartar tudo de imediato.
Scortchi
8
@ stackoverflowuser2010 Como essa resposta tem muitas dezenas de votos positivos, parece que muitas pessoas sentem que é razoavelmente compreensível e responde de alguma maneira aceitável à pergunta. Talvez você possa tentar uma crítica mais construtiva - como, especificamente, você acha que essa resposta seria melhorada? O que deve incluir que não?
Glen_b
1
@ Scortchi: Talvez eu esteja esperando demais, mas uma resposta clara a essa pergunta que poderia ajudar a comunidade seria algo como "Distância euclidiana não é uma boa métrica porque <X>".
stackoverflowuser2010
7
@ stackoverflow2010 Você nunca verá uma resposta "boa" assim porque <as coisas são muito mais complicadas do que as declarações if-then>. Se você quer uma resposta fácil, provavelmente é falsa. Assim como malditos mentirosos do Brexit, eles eram bons em oferecer respostas fáceis (falsas, mas fáceis).
Anony-Mousse
42

É uma questão de sinal-ruído . A distância euclidiana, devido aos termos ao quadrado, é particularmente sensível ao ruído; mas mesmo a distância de Manhattan e as distâncias "fracionárias" (não métricas) sofrem.

Eu achei os estudos neste artigo muito esclarecedores:

Zimek, A., Schubert, E. e Kriegel, H.‑P. (2012),
Uma pesquisa sobre detecção externa não supervisionada em dados numéricos de alta dimensão.
Statistical Analy Data Mining, 5: 363–387. doi: 10.1002 / sam.11161

Ele revisita as observações feitas, por exemplo, sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão de Aggarwal, Hinneburg e Keim mencionados por @Pat. Mas também mostra como os experimentos sintéticos são enganosos e que, de fato , dados de alta dimensão podem se tornar mais fáceis . Se você possui muito sinal (redundante) e as novas dimensões adicionam pouco ruído.

x,yx,y,x,y,x,y,x,y,...,x,y

Portanto, no final, ainda depende dos seus dados. Se você tem muitos atributos inúteis, a distância euclidiana se tornará inútil. Se você pode incorporar facilmente seus dados em um espaço de dados de baixa dimensão, a distância euclidiana também deve funcionar em todo o espaço dimensional. Em particular para dados esparsos , como vetores TF do texto, parece que os dados têm uma dimensionalidade muito menor do que o modelo de espaço vetorial sugere.

Algumas pessoas acreditam que a distância do cosseno é melhor que a euclidiana em dados de alta dimensão. Eu não penso assim: distância cosseno e distância euclidiana estão intimamente relacionadas; então devemos esperar que eles sofram dos mesmos problemas. No entanto, dados textuais em que o cosseno é popular geralmente são escassos , e o cosseno é mais rápido em dados esparsos - portanto, para dados esparsos, existem boas razões para usar o cosseno; e como os dados são escassos, a dimensionalidade intrínseca é muito menor que a dimensão do espaço vetorial.

Veja também esta resposta que dei a uma pergunta anterior: https://stats.stackexchange.com/a/29647/7828

Anony-Mousse
fonte
[1,1]nn
E qual seria a conclusão disso? Em [-1; 1] ^ d, não se deve usar Cosine porque não está definido como 0, a média não nos diz nada sobre a maldição, e dados uniformes são irrealistas.
Anony-Mousse
Eu não tentei até agora, mas acho que os ângulos parecem semelhantes para dados reais. O fato de não estar definido como 0 não deve realmente importar, pois é apenas um ponto. Minha conclusão é semelhante à sua: distância Cosine não é adequado para espaços de alto-dimensional (embora possa haver domínios foram ainda funciona)
Martin Thoma
Um cenário mais realista seria o de pontos na esfera da unidade não-negativa. E a medida de interesse provavelmente seria variação, não média.
Anony-Mousse
Para chegar à esfera unitária não negativo você só tem que adicionar +1 e dividir por 2 ...
Martin Thoma
34

O melhor lugar para começar é provavelmente ler Sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão de Aggarwal, Hinneburg e Keim. Existe um link atualmente em funcionamento aqui (pdf) , mas deve ser muito acessível para o Google, caso isso ocorra. Em resumo, à medida que o número de dimensões aumenta, a distância euclidiana relativa entre um ponto em um conjunto e seu vizinho mais próximo, e entre esse ponto e seu vizinho mais distante, muda de maneiras não óbvias. Se isso afetará ou não seus resultados depende muito do que você está tentando alcançar e da aparência de seus dados.

Pat
fonte
6

A distância euclidiana raramente é uma boa distância para se escolher no Machine Learning e isso se torna mais óbvio em dimensões mais altas. Isso ocorre porque na maioria das vezes no Machine Learning você não está lidando com um Espaço Métrico Euclidiano, mas com um Espaço Métrico Probabilístico e, portanto, você deve usar funções de distância teórica probabilística e de informação, por exemplo, baseadas em entropia.

Os seres humanos gostam do espaço euclidiano porque é fácil de conceituar, além disso, é matematicamente fácil por causa das propriedades de linearidade que significam que podemos aplicar álgebra linear. Se definirmos distâncias em termos de, digamos, divergência de Kullback-Leibler, será mais difícil visualizar e trabalhar matematicamente.

samthebest
fonte
2
Pode ser problemático, pois o KL Divergence não é uma métrica. :-)
agarie
2
Se precisar de simetria, você pode usar Informações Mútuas, que, como sugerido, podem ser definidas em termos de KL.
samthebest
3

Como analogia, imagine um círculo centrado na origem. Os pontos são distribuídos uniformemente. Suponha que um ponto selecionado aleatoriamente esteja em (x1, x2). A distância euclidiana da origem é ((x1) ^ 2 + (x2) ^ 2) ^ 0,5

Agora, imagine pontos distribuídos uniformemente sobre uma esfera. Esse mesmo ponto (x1, x2) agora será provavelmente (x1, x2, x3). Como em uma distribuição par, apenas alguns pontos têm uma das coordenadas como zero, assumiremos que [x3! = 0] para o nosso ponto distribuído uniformemente selecionado aleatoriamente. Assim, nosso ponto aleatório é mais provável (x1, x2, x3) e não (x1, x2, 0).

O efeito disso é: qualquer ponto aleatório está agora a uma distância de ((x1) ^ 2 + (x2) ^ 2 + (x3) ^ 2) ^ 0,5 a partir da origem da esfera 3D. Essa distância é maior que a de um ponto aleatório próximo à origem de um círculo 2D. Esse problema piora em dimensões mais altas, e é por isso que escolhemos métricas diferentes das dimensões euclidianas para trabalhar com dimensões mais altas.

EDIT: Há um ditado que me lembro agora: "A maior parte da massa de uma laranja de maior dimensão está na pele, não na polpa", o que significa que em dimensões mais altas os pontos distribuídos uniformemente são mais "próximos" (distância euclidiana) do limite que a origem.

Nota lateral: A distância euclidiana não é MUITO ruim para problemas do mundo real devido à 'bênção da não uniformidade', que basicamente afirma que, para dados reais, seus dados provavelmente NÃO serão distribuídos uniformemente no espaço dimensional mais alto, mas ocupará um pequeno subconjunto coberto de espaço. Isso faz sentido intuitivamente: se você está medindo 100 quantidades sobre seres humanos, como altura, peso, etc., uma distribuição uniforme no espaço da dimensão simplesmente não faz sentido, por exemplo, uma pessoa com (altura = 65 polegadas, peso = 150 libras, avg_calorie_intake = 4000), o que simplesmente não é possível no mundo real.

Abhishek Divekar
fonte
Se algum leitor futuro estiver interessado na citação "laranja / polpa" ou na observação "bênção da não uniformidade", ambas aparecerão em "Algumas coisas úteis para aprender sobre aprendizado de máquina", as quais estão ligadas na minha resposta fio.
Sycorax 17/07
1

Outra faceta dessa pergunta é a seguinte:

Muitas vezes, as altas dimensões em problemas (aprendizado de máquina / estatística) são resultado de recursos excessivamente restritos.

Isso significa que as dimensões NÃO são independentes (ou não correlacionadas), mas as métricas euclidianas assumem (pelo menos) não correlação e, portanto, podem não produzir melhores resultados

Portanto, para responder à sua pergunta, o número de "altas dimensões" está relacionado a quantos recursos são interdependentes ou redundantes ou com excesso de restrições

Além disso: é um teorema de Csiszar (et al.) Que as métricas euclidianas são candidatas "naturais" à inferência quando os recursos são de certas formas

Nikos M.
fonte
3
As métricas euclidianas não "assumem ... não correlação". As distâncias euclidianas funcionam pior em altas dimensões com variáveis ​​não correlacionadas. Considere o caso extremo: você tem muitas dimensões perfeitamente correlacionadas, r = 1, agora seus dados são de fato unidimensionais e a distância euclidiana funciona bem com dados unidimensionais.
gung
Não, eu não penso assim, distância euclidiana, por definição, assume dados un-correllated (exceto se estiver usando generalizada distância euclidiana com a matriz correllation)
Nikos M.
Características com correlação total (r = 1) é um exemplo trivial e equivalente a uma "matriz de correlação trivial", mas talvez eu sou errado
Nikos M.
@gung Você pode interpretar uma perda euclidiana como uma perda de entropia cruzada de Gaussianos com matriz de variação isotrópica de unidade fixa. Eu acho que esse é um bom argumento, mas poderia ser melhor explicado.
21416 Neil G
1
(0,0)(1,1)dE=j(x2jx1j)22X1=X212cor(X1,X2)=02
0

Este artigo pode ajudá-lo também "Medição de similaridade de sqrt-cosseno aprimorada", visite https://journalofbigdata.springeropen.com/articles/10.1186/s40537-017-0083-6 Este artigo explica por que a distância euclidiana não é uma boa métrica em alta dimensão dados e qual é o melhor substituto para a distância euclidiana em dados de alta dimensão. A distância euclidiana é a norma L2 e, ao diminuir o valor de k na norma Lk, podemos aliviar o problema da distância em dados de alta dimensão. Você também pode encontrar as referências neste artigo.

Sahar
fonte
2
Bem vindo ao site. Estamos tentando construir um repositório permanente de informações estatísticas de alta qualidade na forma de perguntas e respostas. Portanto, temos receio de respostas somente para links, devido ao linkrot. Você pode postar uma citação completa e um resumo das informações no link, caso elas desapareçam?
gung