work way the many how hashtags for choose better best algorithm nearest-neighbor

algorithm - way - algoritmo de vecino más rápido más cercano



how to find the best hashtags for instagram (9)

¿Cuál es la forma más rápida de encontrar el punto más cercano al punto dado en la matriz de datos?

Por ejemplo, tengo espacio 3D, matriz de puntos (coordenadas - (x, y, z)) y punto (xp, yp, zp). Necesito encontrar el punto más cercano al (xp, yp, zp).

Que yo sepa, la forma más lenta de hacerlo es utilizar la búsqueda lineal. ¿Hay mejores soluciones?

La adición de cualquier información auxiliar es posible.

A menos que no estén organizados en una estructura de datos adecuada, la única forma será la búsqueda lineal.

Es mi comprensión quadtree es para 2d, pero se puede calcular algo para 3d que es muy similar. Esto acelerará su búsqueda, pero requerirá mucho más tiempo para calcular el índice si se hace sobre la marcha. Sugeriría calcular el índice una vez y luego almacenarlo. En cada búsqueda, averiguas todos los quads exteriores y luego trabajas a tu manera en busca de éxitos ... se vería como pintar una naranja. La velocidad aumentará considerablemente a medida que los quads se hagan más pequeños. Todo tiene un intercambio.

La forma "más rápida" de hacerlo, considerando SOLAMENTE la búsqueda, sería usar los voxels . Con un mapa de vóxel de 1: 1, el tiempo de acceso es constante y muy rápido, simplemente cambie las coordenadas para centrar el origen de los puntos en el origen del vóxel (si es necesario) y luego redondee la posición y acceda a la matriz de vóxeles con ese valor Para algunos casos, esta es una buena opción. Como expliqué antes, los octrees son mejores cuando es difícil obtener un mapa 1: 1 (demasiados puntos, muy poca resolución de vóxeles, demasiado espacio libre).

Necesitaba hacer esto bastante fuerte para la búsqueda de muchos vecinos más cercanos en un entorno de tiempo real, y acertar en un mejor algoritmo, tanto en términos de simplicidad y velocidad.

Tome todos sus puntos y coloque una copia en las listas donde d es la dimensionalidad del espacio. En su caso 3. Ordene esas tres listas de acuerdo a su dimensión. Esto cuesta d (nlog (n)) tiempo. Y eso es todo por la estructura de datos.

Mantenemos estas listas debidamente ordenadas en cada dimensión para todos los puntos en cuestión. El truco es que, por definición, la distancia en una dirección debe ser menor o igual que la distancia euclidiana. Entonces, si la distancia en una dirección es mayor que nuestra distancia actual más cercana al punto conocido más cercano, entonces ese punto no puede estar más cerca, y lo que es más importante, todos los puntos en esa dirección no pueden ser mayores. Una vez que esto sea cierto para las direcciones 2 * d, tenemos, por definición, tenemos el punto más cercano.

Para cada elemento en particular, podemos buscar binariamente en las listas ordenadas para encontrar la posición más cercana donde el punto requerido podría estar en las dos dimensiones diferentes. Matemáticamente, sabemos que si la distancia en las direcciones + x -x + y -y (otras dimensiones son fáciles de agregar) excede la distancia euclidiana más pequeña conocida hasta un punto, ese punto debe exceder la distancia, y como es una matriz ordenada, por definición, cuando excedemos esa distancia en esa dirección, sabemos que podemos abortar esa dirección, porque no puede haber mejor respuesta en esa dirección. Pero, a medida que nos expandimos en estas cuatro direcciones, podemos reducir nuestro valor de m porque es igual a la distancia euclidiana del punto más cercano que encontramos.

Por lo tanto, solo necesitamos listas ordenadas para cada eje ordenado de acuerdo con ese eje. Que es bastante simple.

Luego para consultar la lista:

  • Realizamos búsquedas binarias en cada una de las listas (dlog (n)).
  • Encontramos nuestra distancia mínima actual, m. (inicialmente puede ser infinito)
  • Para cada lista, viajamos en las direcciones positiva y negativa.
  • Para cada una de las direcciones 2 * d tenemos,
    • Atravesamos las listas, bajando m cuando encontramos puntos más cercanos.
  • Cuando una dirección demuestra ser matemáticamente infructuosa, dejamos de buscar de esa manera.
  • Cuando no queda ninguna dirección, hemos encontrado nuestro punto más cercano.

Hemos ordenado las listas y necesitamos encontrar el punto que estamos buscando en cada dirección de la lista. Realizamos búsquedas binarias para mantener nuestro registro de complejidad de tiempo (n). Entonces tenemos nuestra mejor distancia actual (posiblemente infinito) y luego nos movemos en cada dirección que tenemos disponible para nosotros. A medida que encontramos nuevos puntos, actualizamos el punto más cercano que tenemos hasta ahora. El truco es que nos damos por vencidos tan pronto como la distancia en solo esa dirección es más allá de nuestro punto más cercano conocido actual.

Entonces, si tenemos un punto a una distancia más cercana conocida de 13, podemos abortar el control en las direcciones + x, -x, + y, -y tan pronto como la distancia en esa dirección exceda nuestra distancia más cercana conocida. Porque si es más + x que nuestra m actual, se puede demostrar matemáticamente que todos los valores restantes de + x están más lejos. A medida que obtenemos mejores y mejores puntos, la cantidad de espacio que necesitamos para buscar se hace cada vez más pequeña.

Si nos quedamos sin puntos en una dirección, esa dirección está terminada. Si la distancia a un punto a lo largo de esa única dimensión de la línea es en sí mayor que m, esa dirección está terminada.

La solución es m cuando se ha demostrado que todas las direcciones solo tienen puntos que deben estar más lejos que nuestro mejor punto hasta ahora.

- Dado que reducimos progresivamente m, la distancia en cada dimensión necesaria en conjunto disminuye rápidamente, aunque como todos los algoritmos, disminuye menos rápidamente en dimensiones más altas. Pero, si la distancia en una sola dimensión es mayor que la mejor que tenemos hasta ahora, necesariamente debe darse el caso de que el resto de esos puntos, en esa dirección, no puedan ser mejores.

En el tiempo la complejidad parece estar a la par con las mejores. Pero, en la simplicidad de las estructuras de datos, este algoritmo claramente gana. Hay muchas otras propiedades que hacen de este algoritmo un competidor serio. Cuando actualizas cosas, puedes recurrir a las listas con muy buen rendimiento porque a menudo estás clasificando listas ya ordenadas o listas casi ordenadas. Estás iterando matrices. En términos reales de rendimiento real, la mayoría de las estructuras de datos apestan. En general, debido al almacenamiento en caché y la forma en que se presenta la memoria, se supone que somos agnósticos sobre tales cosas, pero es muy importante. Los datos justo al lado de sus datos relevantes actuales son mucho más rápidos de acceder realmente. Si ya sabemos dónde está el punto que vamos a buscar en las listas, podemos resolverlo aún más rápido (ya que no tendríamos que encontrarlo con una búsqueda binaria). Y otros trucos permitidos reutilizando la información de la iteración anterior aquí y allá. Y las dimensiones adicionales son básicamente gratuitas (salvo que el valor no converge más rápido, pero eso se debe a que hay más puntos distribuidos aleatoriamente en una esfera que un círculo del mismo radio).

public class EuclideanNeighborSearch2D { public static final int INVALID = -1; static final Comparator<Point> xsort = new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return Double.compare(o1.x, o2.x); } }; static final Comparator<Point> ysort = new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return Double.compare(o1.y, o2.y); } }; ArrayList<Point> xaxis = new ArrayList<>(); ArrayList<Point> yaxis = new ArrayList<>(); boolean dirtySortX = false; boolean dirtySortY = false; public Point findNearest(float x, float y, float minDistance, float maxDistance) { Point find = new Point(x,y); sortXAxisList(); sortYAxisList(); double findingDistanceMaxSq = maxDistance * maxDistance; double findingDistanceMinSq = minDistance * minDistance; Point findingIndex = null; int posx = Collections.binarySearch(xaxis, find, xsort); int posy = Collections.binarySearch(yaxis, find, ysort); if (posx < 0) posx = ~posx; if (posy < 0) posy = ~posy; int mask = 0b1111; Point v; double vx, vy; int o; int itr = 0; while (mask != 0) { if ((mask & (1 << (itr & 3))) == 0) { itr++; continue; //if that direction is no longer used. } switch (itr & 3) { default: case 0: //+x o = posx + (itr++ >> 2); if (o >= xaxis.size()) { mask &= 0b1110; continue; } v = xaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vx > findingDistanceMaxSq) { mask &= 0b1110; continue; } break; case 1: //+y o = posy + (itr++ >> 2); if (o >= yaxis.size()) { mask &= 0b1101; continue; } v = yaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vy > findingDistanceMaxSq) { mask &= 0b1101; continue; } break; case 2: //-x o = posx + ~(itr++ >> 2); if (o < 0) { mask &= 0b1011; continue; } v = xaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vx > findingDistanceMaxSq) { mask &= 0b1011; continue; } break; case 3: //-y o = posy + ~(itr++ >> 2); if (o < 0) { mask = mask & 0b0111; continue; } v = yaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vy > findingDistanceMaxSq) { mask = mask & 0b0111; continue; } break; } double d = vx + vy; if (d <= findingDistanceMinSq) continue; if (d < findingDistanceMaxSq) { findingDistanceMaxSq = d; findingIndex = v; } } return findingIndex; } private void sortXAxisList() { if (!dirtySortX) return; Collections.sort(xaxis, xsort); dirtySortX = false; } private void sortYAxisList() { if (!dirtySortY) return; Collections.sort(yaxis,ysort); dirtySortY = false; } /** * Called if something should have invalidated the points for some reason. * Such as being moved outside of this class or otherwise updated. */ public void update() { dirtySortX = true; dirtySortY = true; } /** * Called to add a point to the sorted list without needing to resort the list. * @param p Point to add. */ public final void add(Point p) { sortXAxisList(); sortYAxisList(); int posx = Collections.binarySearch(xaxis, p, xsort); int posy = Collections.binarySearch(yaxis, p, ysort); if (posx < 0) posx = ~posx; if (posy < 0) posy = ~posy; xaxis.add(posx, p); yaxis.add(posy, p); } /** * Called to remove a point to the sorted list without needing to resort the list. * @param p Point to add. */ public final void remove(Point p) { sortXAxisList(); sortYAxisList(); int posx = Collections.binarySearch(xaxis, p, xsort); int posy = Collections.binarySearch(yaxis, p, ysort); if (posx < 0) posx = ~posx; if (posy < 0) posy = ~posy; xaxis.remove(posx); yaxis.remove(posy); } }

Actualización: Respecto a, en los comentarios, el problema de los puntos k. Notarás que muy poco ha cambiado. Lo único relevante es que si el punto v se encuentra que es menor que el m actual (findingDistanceMaxSq), entonces ese punto se agrega al montón, y el valor de m se establece para que sea igual a la distancia euclidiana entre la posición de búsqueda y la kth elemento. La versión regular del algoritmo puede verse como el caso donde k = 1. Buscamos el elemento 1 que queremos y actualizamos m para que sea igual al único elemento (k = 1) cuando v se encuentra más cerca.

Tenga en cuenta que solo hago comparaciones de distancia en la forma cuadrada de distancia, ya que solo necesito saber si está más lejos, y no pierdo ciclos de reloj en las funciones de raíz cuadrada.

Y sé que hay una estructura de datos perfecta para almacenar los k-elementos en un montón de tamaño limitado. Obviamente, una inserción de matriz no es óptima para eso. Pero, aparte de demasiadas apis dependientes de Java, simplemente no había una para esa clase en particular, aunque aparentemente Google Guava la fabrica. Pero, en realidad no se dará cuenta dado que las probabilidades son buenas, su k probablemente no sea tan grande. Pero, hace que la complejidad del tiempo para una inserción en puntos almacenados en k-time. También hay cosas como almacenar en caché la distancia desde el punto de búsqueda para los elementos.

Finalmente, y probablemente lo más apremiante, el proyecto que usaría para probar el código está en transición, así que no he logrado probar esto. Pero, sin duda, muestra cómo se hace esto: se almacenan los mejores resultados k hasta el momento, y se m igual a la distancia hasta el punto k más cercano. - Todo lo demás sigue igual.

Fuente de ejemplo

public static double distanceSq(double x0, double y0, double x1, double y1) { double dx = x1 - x0; double dy = y1 - y0; dx *= dx; dy *= dy; return dx + dy; } public Collection<Point> findNearest(int k, final float x, final float y, float minDistance, float maxDistance) { sortXAxisList(); sortYAxisList(); double findingDistanceMaxSq = maxDistance * maxDistance; double findingDistanceMinSq = minDistance * minDistance; ArrayList<Point> kpointsShouldBeHeap = new ArrayList<>(k); Comparator<Point> euclideanCompare = new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return Double.compare(distanceSq(x, y, o1.x, o1.y), distanceSq(x, y, o2.x, o2.y)); } }; Point find = new Point(x, y); int posx = Collections.binarySearch(xaxis, find, xsort); int posy = Collections.binarySearch(yaxis, find, ysort); if (posx < 0) posx = ~posx; if (posy < 0) posy = ~posy; int mask = 0b1111; Point v; double vx, vy; int o; int itr = 0; while (mask != 0) { if ((mask & (1 << (itr & 3))) == 0) { itr++; continue; //if that direction is no longer used. } switch (itr & 3) { default: case 0: //+x o = posx + (itr++ >> 2); if (o >= xaxis.size()) { mask &= 0b1110; continue; } v = xaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vx > findingDistanceMaxSq) { mask &= 0b1110; continue; } break; case 1: //+y o = posy + (itr++ >> 2); if (o >= yaxis.size()) { mask &= 0b1101; continue; } v = yaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vy > findingDistanceMaxSq) { mask &= 0b1101; continue; } break; case 2: //-x o = posx + ~(itr++ >> 2); if (o < 0) { mask &= 0b1011; continue; } v = xaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vx > findingDistanceMaxSq) { mask &= 0b1011; continue; } break; case 3: //-y o = posy + ~(itr++ >> 2); if (o < 0) { mask = mask & 0b0111; continue; } v = yaxis.get(o); vx = x - v.x; vy = y - v.y; vx *= vx; vy *= vy; if (vy > findingDistanceMaxSq) { mask = mask & 0b0111; continue; } break; } double d = vx + vy; if (d <= findingDistanceMinSq) continue; if (d < findingDistanceMaxSq) { int insert = Collections.binarySearch(kpointsShouldBeHeap, v, euclideanCompare); if (insert < 0) insert = ~insert; kpointsShouldBeHeap.add(insert, v); if (k < kpointsShouldBeHeap.size()) { Point kthPoint = kpointsShouldBeHeap.get(k); findingDistanceMaxSq = distanceSq(x, y, kthPoint.x, kthPoint.y); } } } //if (kpointsShouldBeHeap.size() > k) { // kpointsShouldBeHeap.subList(0,k); //} return kpointsShouldBeHeap; }

Puedes organizar tus puntos en un Octree. Entonces solo necesitas buscar un pequeño subconjunto.

Ver: en.wikipedia.org/wiki/Octree

Esta es una estructura de datos bastante simple que puede implementar usted mismo (lo que sería una valiosa experiencia de aprendizaje), o puede encontrar algunas bibliotecas útiles para comenzar.

Nota: Originalmente dije Quadtree (que es para 2D) por accidente. Gracias @marcog por la corrección.

Si está haciendo una consulta de vecino más cercano una vez, entonces una búsqueda lineal es realmente lo mejor que puede obtener. Esto es, por supuesto, asumiendo que los datos no están pre-estructurados.

Sin embargo, si va a hacer muchas consultas, hay algunas estructuras de datos de partición de espacio . Éstas requieren un proceso previo para formar la estructura, pero luego pueden responder las consultas de los vecinos más cercanos muy rápidamente.

Como se trata de espacio tridimensional, recomiendo observar en.wikipedia.org/wiki/Octree o kd-trees . Los árboles-kd son más genéricos (funcionan para dimensiones arbitrarias) y pueden ser más eficientes que los octetos si implementa un algoritmo de equilibrio adecuado (por ejemplo, la mediana funciona bien), pero los octetos son más fáciles de implementar.

ANN es una gran biblioteca que utiliza estas estructuras de datos, pero también permite consultas aproximadas al vecino más cercano que son significativamente más rápidas pero tienen un pequeño error, ya que son solo aproximaciones. Si no puede tomar ningún error, establezca el error vinculado a 0.

Sugiero que KD-Tree funcionará bien. También es bueno para las búsquedas de vecinos más cercanos.

Yo usaría un árbol KD para hacer esto en el tiempo O (log (n)), suponiendo que los puntos están distribuidos aleatoriamente o tiene una forma de mantener el árbol equilibrado.

kd-trees

Los árboles KD son excelentes para este tipo de consulta espacial, e incluso le permiten recuperar los k vecinos más cercanos a un punto de consulta.