Gerando um conjunto de dados de alta dimensão onde o vizinho mais próximo se torna sem sentido

7

No artigo " Quando o 'vizinho mais próximo' é significativo? ", Lemos que,

Mostramos que, sob certas condições amplas (em termos de distribuição de dados e consultas ou carga de trabalho), à medida que a dimensionalidade aumenta, a distância do vizinho mais próximo se aproxima da distância do vizinho mais distante. Em outras palavras, o contraste nas distâncias para diferentes pontos de dados se torna inexistente. As condições que identificamos nas quais isso acontece são muito mais amplas do que as dimensões independentes e identicamente distribuídas (IID) pressupõem que outro trabalho assume.

Minha pergunta é: como devo gerar um conjunto de dados que produz esse efeito?

Criei três pontos, cada um com 1000 dimensões, com números aleatórios que variam de 0 a 255 para cada dimensão, mas os pontos criam distâncias diferentes e não reproduzem o que é mencionado acima. Parece que mudar as dimensões (por exemplo, 10 ou 100 ou 1000 dimensões) e os intervalos (por exemplo [0,1]) não mudam nada. Ainda obtenho distâncias diferentes, o que não deve ser problema para, por exemplo, algoritmos de agrupamento!

Edit: Eu tentei mais amostras, com base nos meus experimentos, as distâncias entre os pontos não convergem para nenhum número; pelo contrário, as distâncias máxima e mínima entre os pontos ficam mais aparentes. Isso também contraria o que está escrito no primeiro post de Precisa de mais intuição para a maldição da dimensionalidade e também muitos outros lugares que reivindicam a mesma coisa como https://en.wikipedia.org/wiki/Clustering_high-dimensional_data#Problems . Eu ainda apreciaria se alguém pudesse me mostrar com um pedaço de código ou conjunto de dados real que esse efeito existe em cenários práticos.

U66
fonte
100 dimensões já contariam com dimensões muito altas (comparadas às aplicações do mundo real de 2, 3 ou talvez 4 dimensões para as quais as distâncias euclidianas são originalmente usadas). Não espere muita mudança entre 100 e 1000. As distâncias são diferentes, ok, mas em quanto?
David Ernst
A distância é diferente em termos significativos, mesmo para 1 milhão de dimensões. Agora que penso nisso, talvez minha geração de números aleatórios seja o problema. No momento, estou simplesmente gerando números aleatórios em um intervalo específico e dedicando-os a cada dimensão, mas acho que uma abordagem mais precisa é usar algo como distribuição normal multivariada para produzir números aleatórios.
U66
Usei distribuição normal multivariada do apache comum e ainda não consigo replicar o efeito !!!
U66

Respostas:

4

Leia alguns dos artigos mais recentes de acompanhamento, como:

Houle, ME, Kriegel, HP, Kröger, P., Schubert, E., & Zimek, A. (2010, junho). As distâncias entre vizinhos podem derrotar a maldição da dimensionalidade? . Na Conferência Internacional sobre Gerenciamento de Banco de Dados Científico e Estatístico (pp. 482-500). Springer Berlin Heidelberg.

e

Zimek, A., Schubert, E., & Kriegel, HP (2012). Uma pesquisa sobre detecção externa não supervisionada em dados numéricos de alta dimensão. Análise Estatística e Mineração de Dados, 5 (5), 363-387.

Se bem me lembro, eles mostram as propriedades do efeito teórico da concentração à distância (o que é comprovado) e as limitações pelas quais a realidade pode se comportar muito diferente. Se esses artigos não forem úteis, faça ping em mim e eu verifico novamente as referências (apenas digitei o que lembrei no Google Scholar, não baixei os trabalhos novamente).

Cuidado que a "maldição" não diz que a diferença de distâncias para os vizinhos mais próximos e mais distantes se aproxima de 0; nem que as distâncias convergissem para algum número. mas antes que a diferença relativa em relação ao valor absoluto se torne pequena. Desvios aleatórios podem fazer com que os vizinhos sejam classificados incorretamente.

Nesta equação, não ignore a fração, o valor esperado e : d

limdE(distmax(d)distmin(d)distmin(d))0
Possui QUIT - Anony-Mousse
fonte
Olá, obrigado pelas informações, a principal questão ainda permanece sem resposta, porém, de que maneira podemos gerar uma amostra que se assemelha a esse efeito? Além disso, não entendi bem essa frase "diferença relativa em relação ao valor absoluto", você pode explicar mais?
U66
hmmm ... acho que poderia replicar o efeito com sucesso, o ponto está na divisão (por exemplo, é a distância relativa de (max-min) ao ponto mínimo e não as distâncias simples). À medida que aumentava as dimensões, a distância relativa fica menor. Isso vale para a origem e também quaisquer outros pontos no conjunto de dados.
U66
"Distância relativa" refere-se exatamente a esta divisão. É bastante claro que os valores absolutos não convergem para uma constante.
parou - anony-Mousse
2

Também não tinha ouvido falar disso antes, então estou um pouco na defensiva, pois vi que conjuntos de dados reais e sintéticos em grandes dimensões realmente não suportam a alegação do artigo em questão.

Como resultado, o que eu sugeriria, como primeira tentativa suja, desajeitada e talvez não boa, é gerar uma esfera em uma dimensão de sua escolha (eu faço assim ) e, em seguida, colocar uma consulta no centro de a esfera.

Nesse caso, cada ponto fica na mesma distância do ponto de consulta, portanto, o vizinho mais próximo tem uma distância igual ao vizinho mais distante.

É claro que isso é independente da dimensão, mas foi o que surgiu depois de examinar as figuras do artigo. Deve ser o suficiente para você ser visto, mas certamente, melhores conjuntos de dados podem ser gerados, se houver.


Editar sobre:

distâncias para cada ponto ficou maior com mais dimensões !!!!

isso é esperado, pois quanto maior o espaço dimensional, menor o espaço, maior a distância. Além disso, isso é esperado, se você pensar, por exemplo, na distância euclidiana, que fica mais alta à medida que as dimensões crescem.

gsamaras
fonte