algorithm - vecinos - vecino mas cercano vba

Algoritmo aproximado e incremental del vecino más cercano para cuerpos en movimiento

Question

Generosidad

Esta pregunta plantea varias cuestiones. La recompensa irá a una respuesta que los aborde de manera holística.

Aquí hay un problema con el que he estado jugando.

NOTA Estoy especialmente interesado en las soluciones que no están basadas en el espacio euclidiano.

Hay un conjunto de Actores que forman una multitud de tamaño K. La distancia d(ActorA,ActorB) es fácilmente computable para cualquiera de los dos actores (las soluciones deberían funcionar para varias definiciones de ''distancia'') y podemos encontrar el conjunto de N más cercano vecinos para cualquier Actor dado que utilizan cualquiera de una serie de algoritmos establecidos.

Este conjunto de vecinos es correcto en el primer instante, pero los Actores siempre se están moviendo y quiero mantener la lista en evolución de N vecinos más cercanos para cada Actor. Lo que me interesa son las soluciones aproximadas que son más eficientes que las soluciones perfectas.

1. Las soluciones deben converger para ser correctas después de que se hayan introducido los errores.
2. Es aceptable a veces realizar una recálputo total si los errores son demasiado grandes, pero la detección de estos errores debería ser barata .

Hasta ahora he estado usando un algoritmo de amigo-a-amigo :

recompute_nearest (Actor A)
{
    Actor f_o_f [N*N];
    for each Actor n in A.neighbours
        append n to f_o_f if n != A and n not in f_o_f

    Distance distances [N*N];
    for 0 <= i < f_o_f.size
        distances [i] = distance (A, f_o_f [i])

    sort (f_o_f, distances)
    A .neighbours = first N from f_o_f
}

Esto se realiza razonablemente bien cuando la multitud se mueve lentamente y N es adecuadamente grande. Converge después de pequeños errores, satisfaciendo los primeros criterios, pero

• No tengo una buena manera de detectar grandes errores,
• No tengo una descripción cuantitativa del tamaño y la frecuencia de los errores,
• converge en la práctica, pero no puedo demostrar que siempre lo hará.

¿Puedes ayudar con alguno de estos puntos?

Además, ¿conoce algún enfoque alternativo que funcione bien?

• cuando la multitud se mueve rápido,
• cuando algunos actores se mueven rápidamente,
• cuando N es pequeña,
• cuando la multitud es escasa en algunos lugares y densa en otros,
• ¿O con algoritmos de indexación espacial particulares?

La extensión en la que estoy trabajando en este momento es generalizar al amigo de un amigo para que se lleve al amigo de un amigo de un amigo en los casos en que un vecino se está moviendo rápidamente. Sospecho que esto no se adapta bien y es difícil derivar los parámetros correctos sin una cuantificación de los errores.

¡Doy la bienvenida a todas las sugerencias! Es un pequeño problema divertido :-)

Sugerencias notables hasta ahora

Fexvez: muestra vecinos adicionales aleatorios, tamaño de muestra dependiendo de la velocidad del Agente. Tomar muestras del área en la que se va a mudar probablemente también ayudaría.

Vuelva a muestrear a los vecinos cuando la speed*delta_time un agente speed*delta_time supera la distancia al vecino más lejano conocido.

Mantenga la triangulación de Delaunay que es un superconjunto del gráfico del vecino más cercano. Sólo cuentas para un vecino más cercano.

La biblioteca ANN de David Mount no parece manejar cuerpos en movimiento .

Answer 1

¿Has intentado usar un árbol quad ?

Es decir, dividir recursivamente el "mundo" en un gráfico con cuatro subnodos cada uno. El árbol puede entonces verificar rápidamente qué objetos están dentro de un cuadrado particular del mundo y descartar el resto. Una técnica de selección muy efectiva que se usa a menudo para mejorar el rendimiento de la detección de colisiones en los juegos.

Si esto es 3D, extiéndelo a un octárbol.

Answer 2

Aquí hay un contraejemplo simple que muestra que el algoritmo de un amigo de amigo a veces extrañará a los vecinos: comience con una línea recta larga de muchos (al menos más de 3 * N) actores separados de manera equidistante, y doble gradualmente la línea en un círculo. Si la línea es lo suficientemente larga, los actores en ella no detectarán ningún cambio local en sus vecindarios; en particular, los actores en los extremos no se darán cuenta cuando se encuentren.

Edición: En realidad, pensé en un contraejemplo aún más simple: tomar dos grupos compactos aislados de N o más actores cada uno, y enviarlos a un curso de colisión entre sí.

Answer 3

Cuando la distancia que un Actor se mueve en un paso de tiempo dado supera la distancia a su vecino más lejano conocido, vuelva a muestrear a todos los vecinos.

Otro disparador: cuando la distancia que un Actor ha movido desde la última remuestreación excede la distancia hasta el vecino más lejano conocido, remuestrea.

La optimización trivial va bien aquí, si hay un índice espacial jerárquico, busque un nodo que contenga a) una esfera de radio igual al tamaño del salto, yb) al menos N Actores.

Answer 4

Lo que yo intentaría.

1. Cubrir árboles como la estructura de datos base para hacer kNN. Características: no necesita una métrica euclidiana, el uso del espacio lineal, kNN / Insertar / Eliminar son todos O (log n) cuando la dimensionalidad intrínseca de los datos es fija. No característica: movimiento.

2. Para manejar objetos en movimiento, periódicamente, para cada objeto, elimine su posición anterior, inserte su nueva posición y encuentre el kNN.

Si establecemos el período de un objeto inversamente proporcional a la velocidad, entonces sabemos que la discrepancia máxima entre el árbol de la cubierta y la realidad está limitada por una constante.

Answer 5

Los árboles KD le permiten buscar de manera eficiente dentro de un radio fijo de un punto. Si todos los puntos de un vecino están dentro de las unidades d1 y el desplazamiento máximo de cualquier punto de la medición anterior es d2 , entonces solo necesita buscar dentro de las unidades d1 + d2 del punto.

Si estuvieras tratando con una distancia de Minkowski, entonces podrías haber usado la biblioteca ANN de David Mount . No estoy seguro, si hay una biblioteca que tomaría funciones de distancia arbitrarias, sin embargo.

Answer 6

Tengo algo que parece una solución.

En cada paso de "recompilación", toma un tiempo lineal, lo que supongo que no es tanto un problema como lo hace recompute_nearest (Actor A) para cada actor.

Vayamos al punto: la idea es para cada actor, agregue un cierto número de amigos al azar justo antes de calcular recompute_nearest (Actor A) . Este número no debe ser demasiado pequeño, de lo contrario nunca detectará errores. No debería ser demasiado grande, ya que la computación de los vecinos de los vecinos es cuadrática, será computacionalmente demasiado costosa.

Pero, ¿qué significa "no demasiado pequeño" o "no demasiado grande"? Comenzaremos con un actor A y veremos cómo se actualizará su lista de vecinos. Supongamos que para cada punto, agregas el p por ciento de los K actores originales. Luego, si otro punto B se acerca a A pero no es amigo de un amigo, deberíamos agregarlo "rápidamente" a través de la opción "amigos aleatorios". En cada iteración, hay una posibilidad (1-p) de no elegirlo.

Un cálculo rápido muestra que si desea detectar este punto en 10 iteraciones o menos en el 90% del caso, necesitará p=20% . Esto es terriblemente caro.

...

¡Sin embargo, no todo está perdido! El primer punto que quiero hacer es que si los errores tienden a "ir juntos", ¡el rendimiento aumenta dramáticamente! Imagina dos manchas que inicialmente están muy alejadas (personas que chatean, cúmulos de estrellas, etc ...) Si estas manchas chocan, el amigo-amigo nunca verá que hay un problema. Pero, con mi algoritmo, si detecta un solo error, y adapta correctamente su lista de vecinos, entonces, el algoritmo de amigo-amigo corregirá todos los errores restantes.

Si tiene K=1.000 y dos pequeños blobs que contienen cada uno solo el 1% de los puntos y desea detectar 10 iteraciones o menos con un 99% de certeza, puede calcular que solo necesitará p=1% . (¡Cuanto más grande es K, más p debe ser!) Bueno, eso supone que algunos puntos "van juntos".

Tengo otra optimización: adaptar el número y la calidad de los puntos aleatorios. En pocas palabras, los actores rápidos deberían tener más amigos aleatorios que actores lentos. Y deberías aleatorizar a estos amigos prefiriendo otros actores rápidos. No puedo cuantificarlo, ¡pero puedes adivinar por qué mejorará el rendimiento!

Una pequeña edición sobre tu pregunta: "¿Qué hago cuando los actores son rápidos"? Puedes traducir la velocidad de los actores con la cantidad de pasos que te das para detectar un error. Lo que quiero decir es que si puedes considerar que cada actor tiene un círculo alrededor de sus amigos. Ese círculo teórico corresponde a su lista de amigos. Si la mayoría de los actores no pueden cruzar completamente este círculo en 10 iteraciones, pero sí en 15, entonces debes considerar que te das 10 iteraciones para detectar el problema. Si sus actores son tan rápidos que pueden cruzar este "círculo" en 3 pasos, entonces ... bueno, este algoritmo no es para usted (y creo que es ilusorio tratar de mantener una lista de vecinos sin volver a calcularla en cada paso)

Fundamentalmente, mantener una lista de vecinos sugiere que existe cierta estructura (es decir, algo más o menos igual entre dos iteraciones). La velocidad es lo contrario, los actores rápidos significan que no tienes estructura. En el caso de actores muy rápidos, mantener una lista de vecinos es probablemente una mala idea.

Detalle técnico de las manchas.

Tiene dos manchas que contienen cada s% de los actores (tamaño sK ) (el ejemplo es s = 1% )

Te das un margen de error de e% (el ejemplo es 1% ) y n pasos (el ejemplo es 10)

Luego hay un límite superior para p: p <= [log(1-e^(1/n))]/[s*K²*log(1-s)]

¡El valor verdadero de mi ejemplo es p <= 0.989% !

Tienes p = [log(1-e^(1/n))]/[s*K²*log(1-s)] si s es pequeño y K es grande. Si no es el caso, p es mucho más pequeño!

Answer 7

Un método muy simple y muy rápido de las estadísticas es utilizar proyecciones lineales aleatorias. Estos pueden ayudarlo a determinar los grupos y vecinos muy rápidamente. Con más proyecciones, obtendrá más precisión (creo que su pregunta sobre errores).

Este documento ofrece un extenso análisis cuantitativo de varios métodos, incluido un nuevo método (DPES) relacionado con el RLP.

Este documento aborda el uso de RLP, incluida la preservación de la distancia, incluso en el contexto de puntos móviles .

Este documento aborda el RLP para la planificación del movimiento y detalla varias heurísticas.

Los métodos de RLP son:

1. Muy rapido
2. Conduce a aproximaciones que son sintonizables para precisión y velocidad
3. Conservación de la distancia y del ángulo (demostrable)
4. Se escala fácilmente a grandes dimensiones y grandes #s de objetos
5. Útil para la reducción de la dimensionalidad.
6. Liderar a proyecciones compactas (por ejemplo, uno podría proyectar en una partición binaria jerárquica)
7. Flexible: puede proyectar en cualquier espacio que crea que sería bueno para usted, generalmente R ^ d, pero también se permite proyectar en 2 ^ d (es decir, espacio binario de dimensión d), solo sujeto a una reducción en la precisión para un # dado de proyecciones.
8. Estadisticamente interesante

Después de incrustar en un espacio dimensional inferior, los cálculos de los vecinos son muy sencillos, ya que las proyecciones que están, por ejemplo, agrupadas en las mismas regiones (si se agrupan las proyecciones en una cuadrícula) es muy probable que estén cerca del espacio original.

Aunque la dimensionalidad de los datos originales es pequeña (incluso 10 es pequeña), la capacidad de proyectar rápidamente en una cuadrícula preseleccionada es muy útil para identificar y contar vecinos.

Finalmente, solo necesita actualizar los objetos cuya ubicación (o ubicación relativa, si está centrando y escalando los datos) ha cambiado.

Para trabajos relacionados, mira el lema de Johnson-Lindenstrauss.