Generar un conjunto de datos multidimensional donde el vecino más cercano se vuelve sin sentido

Question

En el artículo "Cuando Es "Vecino más Cercano' Significativas?" leemos que,

Se demuestra que, bajo ciertas condiciones amplias (en términos de datos y la consulta de las distribuciones, o la carga de trabajo), como dimensionalidad aumenta, la distancia al vecino más cercano, los enfoques de la distancia al vecino más lejano. En otras palabras, el contraste de las distancias a los diferentes puntos de datos se vuelve inexistente. Las condiciones que hemos identicado en el que esto ocurre son mucho más amplio que el de los independientes e idénticamente distribuidas (IID) dimensiones de la suposición de que otro trabajo que supone.

Mi pregunta es, ¿cómo debo generar un conjunto de datos que se produce este efecto?

He creado tres puntos cada uno con 1000 dimensiones con números aleatorios que van de 0 a 255 para cada dimensión, pero los puntos de crear diferentes distancias y no reproducir lo que se ha mencionado anteriormente. Parece que el cambio de las dimensiones (por ejemplo, 10 o 100 o 1000 dimensiones) y rangos (por ejemplo, [0,1]) no cambiar nada. Todavía puedo obtener diferentes distancias, que no debe ser ningún problema para, por ejemplo, algoritmos de clustering!

Edit: he intentado más muestras, basado en mis experimentos distancias entre los puntos no convergen a cualquier número, por el contrario, el max y min distancias entre los puntos más evidente. Esto también es contrario a lo que está escrito en el primer post de la Necesidad más que la intuición de la maldición de la dimensionalidad y también en muchos otros lugares que dicen la misma cosa como https://en.wikipedia.org/wiki/Clustering_high-dimensional_data#Problems. Todavía les agradecería si alguien me puede mostrar con un pedazo de código real o conjunto de datos que a tal efecto existen en escenarios prácticos.

Answer 1

La lectura de algunos de los más recientes de seguimiento de artículos, tales como:

Houle, M. E., Kriegel, H. P., Kröger, P., Schubert, E., & Zimek, A. (2010, Junio). Puede compartido vecino distancias vencer la maldición de la dimensionalidad?. En la Conferencia Internacional de Estadísticos y Científicos de la Base de datos de Gestión (pp 482-500). Springer Berlin Heidelberg.

y

Zimek, A., Schubert, E., & Kriegel, H. P. (2012). Una encuesta sin supervisión en la detección de valores atípicos en alto‐dimensional de datos numéricos. Análisis estadístico y Minería de Datos, 5(5), 363-387.

Si recuerdo correctamente, se muestran las propiedades de los teóricos de la distancia de la concentración de efecto (que está demostrado) y las limitaciones por qué realidad puede comportarse de manera muy diferente. Si estos artículos no son útiles, ping y me vuelva a comprobar las referencias (que acaba de escribir lo que yo recordaba en Google Scholar, no me descarga los papeles de nuevo).

Ten en cuenta que la "maldición" no decir la diferencia de distancias a los más cercanos y más lejanos vecinos se aproxima a 0; ni que las distancias convergían para algún número. pero en lugar de que la diferencia relativa en comparación con el valor absoluto se vuelve pequeño. A continuación, desviaciones aleatorias pueden causar a los vecinos a ser incorrectamente clasificados.

En este equartion, no ignore la fracción, el valor esperado, y $d\rightarrow\infty$: $$ \lim_{d \to \infty} E\left(\frac{\operatorname{dist}_{\max} (d) - \operatorname{dist}_{\min} (d)}{\operatorname{dist}_{\min} (d)}\right) \a 0 $$

Answer 2

Yo no había oído hablar de esto antes, así que estoy poco a la defensiva, ya que han visto que reales y sintéticas conjuntos de datos de alta dimensión en la que realmente no apoyan la afirmación de que el papel en cuestión.

Como resultado, lo que yo sugeriría, como un primer, sucio, torpe y tal vez no sea bueno primero que se intenta es generar una esfera en una dimensión de su elección (yo hago como en el caso de este) y, a continuación, coloque una consulta en el centro de la esfera.

En ese caso, cada punto se encuentra en la misma distancia con la consulta punto, por lo tanto el más Cercano Vecino tiene una distancia igual a la del Vecino más Lejano.

Esto, por supuesto, es independiente de la dimensión, pero es lo que me vino un pensamiento después de mirar las figuras de papel. Debería ser suficiente para obtener miró fijamente, pero sin duda, el mejor de los conjuntos de datos se pueden generar, si los hubiere.

---

Editar acerca de:

distancias de cada punto se hizo más grande con más dimensiones!!!!

esto es el esperado, ya que la mayor de las dimensiones del espacio, el más escaso el espacio es, por lo tanto mayor es la distancia. Por otra parte, se espera que esto, si usted piensa que por ejemplo, la distancia Euclidiana, la cual se rallador como las dimensiones de crecer.