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.
Respostas:
Leia alguns dos artigos mais recentes de acompanhamento, como:
e
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→∞
fonte
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:
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.
fonte