¿Cómo agrupar los puntos de latitud/longitud que están 'cercanos' entre sí?

Question

Tengo una base de datos de puntos de latitud/longitud enviados por el usuario y estoy tratando de agrupar puntos de 'cierre'. 'Cerrar' es relativo, pero por ahora parece ~ 500 pies.

Al principio me pareció que podía agrupar por filas que tienen la misma latitud/longitud para los primeros 3 lugares decimales (aproximadamente una caja de 300x300, entendiendo que cambia a medida que se aleja del ecuador).

Sin embargo, ese método parece ser bastante deficiente. 'Cercanía' no puede ser significativamente diferente de la distancia que representa cada lugar decimal. No tiene en cuenta que dos ubicaciones pueden tener diferentes dígitos en la tercera (o cualquier) posición decimal, pero aún estar dentro de la distancia que representa el lugar (33.1239 y 33.1240).

También he reflexionado sobre la situación en la que el Punto A y el Punto C están ambos "cerca" del Punto B (pero no entre sí) - ¿deberían estar agrupados? Si es así, ¿qué sucede cuando el Punto D está "cerca" del punto C (y no hay otros puntos)? ¿Debería agruparse también? Ciertamente, debo determinar el comportamiento deseado, pero ¿cómo se implementará?

¿Alguien puede indicarme la dirección correcta de cómo se puede hacer esto y qué métodos/enfoques diferentes se pueden utilizar?

Me siento un poco como si me falta algo obvio.

Actualmente los datos son una base de datos MySQL, utilizada por una aplicación PHP; sin embargo, estoy abierto a otros métodos de almacenamiento si son una parte clave para lograr esto. aquí.

Answer 1

Existen varias formas de determinar la distancia entre dos puntos, pero para trazar puntos en un gráfico en 2-D es probable que desee el Euclidean distance. Si (x1, y1) representa el primer punto y (x2, y2) representa el segundo, la distancia es

d = sqrt((x2-x1)^2 + (y2-y1)^2) 

En cuanto a la agrupación, es posible que desee utilizar algún tipo de 2-D significa determinar cómo "cerrar" las cosas son el uno al otro. Por ejemplo, si tiene tres puntos, (x1, y1), (x2, y2), (x3, y3), se encuentra el centro de estos tres puntos al promedio simple:

x(mean) = (x1+x2+x3)/3 
y(mean) = (y1+y2+y3)/3 

Se puede ver entonces lo cerca que cada uno es al centro para determinar si debería ser parte del "grupo".

---

Hay un número de maneras que uno puede definir agrupaciones, todos los cuales utilizan alguna variante de un clustering algorithm. Tengo prisa ahora y no tengo tiempo para resumir, pero revisa el enlace y los algoritmos, y con suerte otras personas podrán brindarte más detalles. ¡Buena suerte!

Answer 2

Si fuera a abordarlo, comenzaría con una grilla. Pon cada punto en un cuadrado en la cuadrícula. Busque redes que están densamente pobladas. Si las cuadrículas adyacentes no están pobladas, entonces tienes un grupo decente.

Si tiene cuadrículas adyacentes densamente pobladas, siempre puede colocar un círculo en el centro de cada cuadrícula y optimizar el área del círculo frente a (número de puntos en el círculo * algún peso ajustable). No es perfecto, pero fácil. Mejores agrupaciones son problemas de optimización mucho más complicados.

Answer 3

Tal vez exagerado, pero me parece un clustering problem: la distancia measure determinará cómo se calcula la similitud de dos elementos. Si necesita una solución menos ingenuo tratar Data Mining: Practical Machine Learning Tools and Techniques, y utilizar Weka o Orange

Answer 4

uso algo similar con el método que se indica en su pregunta para obtener un conjunto aproximado de resultados, a continuación, reducir gradualmente que se aproximan dejó al hacer los cálculos adecuados. Si elige el tamaño de su cuadrícula (es decir, cuánto redondea sus coordenadas) correctamente, al menos puede esperar reducir la cantidad de trabajo a realizar a un nivel aceptable, aunque debe administrar el tamaño de la cuadrícula.

Por ejemplo, el earthdistance extensión a PostgreSQL funciona mediante la conversión de pares de latitud/longitud a (x, y, z) coordenadas cartesianas, el modelado de la Tierra como una esfera uniforme. PostgreSQL tiene un sofisticado sistema de indexación que permite indexar estas coordenadas, o casillas que las rodean, en árboles R, pero puede combinar algo que aún es útil sin eso.

Si toma su (x, y, z) triple y redondea, es decir, multiplica por un factor y trunca a entero, tiene tres enteros que puede concatenar para producir un "nombre de cuadro", que identifica un cuadro en su "cuadrícula" donde está el punto.

Si desea buscar todos los puntos dentro de X km de un punto objetivo, genera todos los "nombres de recuadro" alrededor de ese punto (una vez que haya convertido su apuntar también a un (x, y, z) triple, eso es fácil) y eliminar todas las casillas que no se cruzan con la superficie de la Tierra (tricker, pero el uso de la fórmula x^2+y^2+z^2=R^2 en cada esquina te dirá) terminas con una lista de recuadros, los puntos de destino pueden ser solo búsqueda de todos los puntos que coincidan con uno de esos recuadros, lo que también te devolverá un poco más puntos. Así que, como etapa final, debes calcular la distancia real hasta tu punto objetivo y eliminar algo (de nuevo, esto se puede acelerar trabajando en coordenadas cartesianas y convirtiendo el radio de distancia del círculo máximo objetivo en distancia secante).

El juguete se trata de asegurarse de que no tenga que buscar demasiadas cajas, pero al mismo tiempo no traiga demasiados puntos extra. Me pareció útil indexar cada punto en varias cuadrículas diferentes (por ejemplo, resoluciones de 1Km, 5Km, 25Km, 125Km, etc.). Lo ideal es que solo busque una casilla, recuerde que se expande a por lo menos 27 tan pronto como su radio de destino exceda el tamaño de su cuadrícula.

He utilizado esta técnica para construir un índice espacial utilizando Lucene en lugar de hacer cálculos en bases de datos SQL. Funciona, aunque hay algunos ajustes para configurarlo, y los índices tardan un poco en generar y son bastante grandes. Usar un R-tree para contener todas las coordenadas es un enfoque mucho más agradable, pero requeriría más codificación personalizada: esta técnica básicamente requiere una búsqueda rápida de tablas hash (por lo que probablemente funcione bien con todas las bases de datos NoSQL que son furia en estos días, y debería ser utilizable en una base de datos SQL también).

Answer 5

Si está considerando la latitud y la longitud, hay varios factores que deben tenerse en cuenta en los datos en tiempo real: obstrucciones, como ríos y lagos, e instalaciones, como puentes y túneles. No puedes agruparlos simplemente; si usa el algoritmo simple como k significa que no podrá agruparlos. Creo que deberías optar por los métodos de agrupación espacial como método de partición CLARANS.