¿Pruebas estadísticas para patrones de líneas espaciales?

Hay muchas pruebas para patrones de puntos espaciales que se pueden usar para determinar si los puntos se distribuyen al azar o no, pero ¿hay alguna prueba establecida para patrones de líneas espaciales? (Estoy pensando en líneas rectas, con solo inicio y punto final y sin nodos intermedios).

Los datos que quiero analizar son líneas OD (origen-destino) de movimiento humano y animal. (Similar al ejemplo en Agrupación de líneas no dirigidas ).

Hasta ahora, una idea era tratar líneas como puntos 4D y usar pruebas de patrones de puntos, pero no estoy seguro de si eso es apropiado.

La prueba ideal permitiría determinar si hay grupos de líneas o no.

Instintivamente, diría que muchas líneas que comienzan en el mismo origen pero tienen todo tipo de destinos diferentes, no deberían considerarse un clúster. Por otro lado, muchas líneas que se ejecutan (cerca de) en paralelo durante más tiempo serían un clúster.

Esta es una pregunta difícil, ya que no se han desarrollado muchas estadísticas de procesos espaciales, si es que hay alguna, para las características de línea. Sin profundizar en las ecuaciones y el código, las estadísticas de proceso puntual no son fácilmente aplicables a las características lineales y, por lo tanto, estadísticamente inválidas. Esto se debe a que el valor nulo, contra el que se prueba un patrón determinado, se basa en eventos puntuales y no en dependencias lineales en el campo aleatorio. Tengo que decir que ni siquiera sé cuál sería el valor nulo en la medida en que la intensidad y la disposición / orientación serían aún más difíciles.

Aquí solo estoy escupiendo, pero me pregunto si una evaluación a gran escala de la densidad de la línea junto con la distancia euclidiana (o la distancia de Hausdorff si las líneas son complejas) no indicaría una medida continua de agrupamiento. Estos datos podrían resumirse luego en los vectores de línea, utilizando la varianza para tener en cuenta la disparidad en las longitudes (Thomas 2011), y se les asignó un valor de agrupación utilizando una estadística como K-medias. Sé que no buscas los clústeres asignados, pero el valor del clúster podría dividir los grados de clúster. Obviamente, esto requeriría un ajuste óptimo de k, por lo que no se asignan grupos arbitrarios. Estoy pensando que este sería un enfoque interesante para evaluar la estructura de borde en modelos teóricos gráficos.

Aquí hay un ejemplo trabajado en R, lo siento, pero es más rápido y más reproducible que proporcionar un ejemplo de QGIS, y está más en mi zona de confort :)

Agregue bibliotecas y use objetos psp de cobre desde spatstat como ejemplo de línea

library(spatstat)
library(raster)
library(spatialEco)

data(copper)
l <- copper$Lines
l <- rotate.psp(l, pi/2)

Calcule la densidad de línea estandarizada de primer y segundo orden y luego coaccione a objetos de clase ráster

d1st <- density(l)
  d1st <- d1st / max(d1st)
  d1st <- raster(d1st)  
d2nd <- density(l, sigma = 2)
  d2nd <- d2nd / max(d2nd)
  d2nd <- raster(d2nd)  

Estandarice la densidad de primer y segundo orden en una densidad integrada en la escala

d <- d1st + d2nd
d <- d / cellStats(d, stat='max')  

Calcule la distancia euclidiana invertida estandarizada y la coerción a la clase de trama

euclidean <- distmap(l)
euclidean <- euclidean / max(euclidean)
euclidean <- raster.invert(raster(euclidean))

Coaccione el psp de spstastat a un objeto sp SpatialLinesDataFrame para usar en raster :: extract

as.SpatialLines.psp <- local({
     ends2line <- function(x) Line(matrix(x, ncol=2, byrow=TRUE))
     munch <- function(z) { Lines(ends2line(as.numeric(z[1:4])), ID=z[5]) }
     convert <- function(x) {
        ends <- as.data.frame(x)[,1:4]
        ends[,5] <- row.names(ends)
        y <- apply(ends, 1, munch)
        SpatialLines(y)
     }
     convert
})
l <- as.SpatialLines.psp(l)
l <- SpatialLinesDataFrame(l, data.frame(ID=1:length(l)) )

Resultados de la trama

par(mfrow=c(2,2))
  plot(d1st, main="1st order line density")
    plot(l, add=TRUE)
  plot(d2nd, main="2nd order line density")
    plot(l, add=TRUE) 
  plot(d, main="integrated line density")
    plot(l, add=TRUE)   
  plot(euclidean, main="euclidean distance")
    plot(l, add=TRUE) 

Extraiga valores ráster y calcule estadísticas de resumen asociadas con cada línea

l.dist <- extract(euclidean, l)
l.den <- extract(d, l)
l.stats <- data.frame(min.dist = unlist(lapply(l.dist, min)),
                      med.dist = unlist(lapply(l.dist, median)),
                      max.dist = unlist(lapply(l.dist, max)),
                      var.dist = unlist(lapply(l.dist, var)),
                      min.den = unlist(lapply(l.den, min)),
                      med.den = unlist(lapply(l.den, median)),
                      max.den = unlist(lapply(l.den, max)),
                      var.den = unlist(lapply(l.den, var)))

Use valores de silueta de clúster para evaluar k óptimo (número de clústeres), con la función óptima.k, luego asigne valores de clúster a las líneas. Luego podemos asignar colores a cada grupo y trazar en la parte superior del ráster de densidad.

clust <- optimal.k(scale(l.stats), nk = 10, plot = TRUE)                      
  l@data <- data.frame(l@data, cluster = clust$clustering) 

kcol <- ifelse(clust$clustering == 1, "red", "blue")
plot(d)
  plot(l, col=kcol, add=TRUE)

En este punto, se podría realizar una aleatorización de las líneas para probar si la intensidad y la distancia resultantes son significativas respecto al azar. Puede usar la función "rshift.psp" para reorientar sus líneas aleatoriamente. También podría aleatorizar los puntos de inicio y finalización y recrear cada línea.

Uno también se pregunta "qué pasaría si" acaba de realizar un análisis de patrón de puntos utilizando una estadística de análisis univariado o cruzado en los puntos de inicio y finalización, invariante de las líneas. En un análisis univariante, compararía los resultados de los puntos de inicio y finalización para ver si existe consistencia en la agrupación entre los dos patrones de puntos. Esto podría hacerse mediante un f-hat, G-hat o Ripley's-K-hat (para procesos de puntos sin marcar). Otro enfoque sería un análisis cruzado (por ejemplo, cross-K) donde los procesos de dos puntos se prueban simultáneamente marcándolos como [inicio, parada]. Esto indicaría las relaciones de distancia en el proceso de agrupación entre los puntos inicial y final. Sin embargo, La dependencia espacial (no estacionaria) de un proceso de intensidad subyacente puede ser un problema en este tipo de modelos, haciéndolos no homogéneos y requiriendo un modelo diferente. Irónicamente, el proceso no homogéneo se modela utilizando una función de intensidad que nos devuelve el círculo completo a la densidad, lo que respalda la idea de utilizar una densidad integrada en la escala como medida de agrupamiento.

Aquí hay un ejemplo rápido y trabajado de si la estadística Ripleys K (Besags L) para la autocorrelación de un proceso de puntos sin marcar utilizando las ubicaciones de inicio y detención de una clase de entidad de línea. El último modelo es un cross-k que usa las ubicaciones de inicio y parada como un proceso marcado nominal.

library(spatstat)
  data(copper)
  l <- copper$Lines
  l <- rotate.psp(l, pi/2)

Lr <- function (...) {
 K <- Kest(...)
  nama <- colnames(K)
   K <- K[, !(nama %in% c("rip", "ls"))]
   L <- eval.fv(sqrt(K/pi)-bw)
  L <- rebadge.fv(L, substitute(L(r), NULL), "L")
 return(L)
}

### Ripley's K ( Besag L(r) ) for start locations
start <- endpoints.psp(l, which="first")
marks(start) <- factor("start")
W <- start$window
area <- area.owin(W)
lambda <- start$n / area
 ripley <- min(diff(W$xrange), diff(W$yrange))/4
   rlarge <- sqrt(1000/(pi * lambda))
     rmax <- min(rlarge, ripley)
( Lenv <- plot( envelope(start, fun="Lr", r=seq(0, rmax, by=1), nsim=199, nrank=5) ) )

### Ripley's K ( Besag L(r) ) for end locations
stop <- endpoints.psp(l, which="second")
  marks(stop) <- factor("stop")
W <- stop$window
area <- area.owin(W)
lambda <- stop$n / area
 ripley <- min(diff(W$xrange), diff(W$yrange))/4
   rlarge <- sqrt(1000/(pi * lambda))
     rmax <- min(rlarge, ripley)
( Lenv <- plot( envelope(start, fun="Lr", r=seq(0, rmax, by=1), nsim=199, nrank=5) ) )

### Ripley's Cross-K ( Besag L(r) ) for start/stop
sdata.ppp <- superimpose(start, stop)
( Lenv <- plot(envelope(sdata.ppp, fun="Kcross", r=bw, i="start", j="stop", nsim=199,nrank=5, 
                 transform=expression(sqrt(./pi)-bw), global=TRUE) ) )

Referencias

Thomas JCR (2011) Un nuevo algoritmo de agrupamiento basado en K-medias utilizando un segmento de línea como prototipo. En: San Martin C., Kim SW. (eds) Progreso en reconocimiento de patrones, análisis de imágenes, visión por computadora y aplicaciones. CIARP 2011. Lecture Notes in Computer Science, vol 7042. Springer, Berlín, Heidelberg

Es posible que desee mirar a la distancia de Fréchet . Hace poco me enteré de esto después de una pregunta reciente en busca de una implementación de Python.

Esta es una métrica para encontrar similitud espacial de cadenas lineales . Es una idea similar a la distancia de Hausdorff, el equivalente para las medidas de similitud de polígonos, pero para las cadenas lineales con una dirección.

La distancia de Fréchet se define como la longitud mínima de una correa que conecta a un perro en una trayectoria con su dueño en una segunda trayectoria, ambas nunca se mueven hacia atrás

Esta métrica tendrá un valor pequeño para dos curvas que se encuentran cerca, casi paralelas, alineadas de la misma manera y con una longitud similar.

Sin embargo, eso no responde a la parte de identificación del clúster.

Hay una presentación completa aquí . Su situación suena como algunos de los casos de uso mencionados en las secciones 46-49

Esta métrica tiene muchos usos no geoespaciales como

• Detectando subpatrones comunes en la secuenciación de genes
• Reconocimiento de escritura a mano
• detectar períodos correlacionados en series de tiempo como historiales de precios de acciones

Entonces, si bien muchos artículos en la bibliografía cubren este tema, la mayoría de ellos no son geoespaciales. Además, la mayoría de estos trabajos se encuentran en algoritmos / matemáticas / ciencias de la computación en lugar de geoespaciales / geociencias y están dirigidos en consecuencia.

Sin embargo, este documento parecía prometedor:

Buchin, K., Buchin, M. y Wang, Y. (2009). Algoritmos exactos para la correspondencia parcial de curvas a través de la distancia de Fréchet. En Actas del XX Simposio ACM-SIAM sobre Algoritmos discretos, páginas 645–654

Algunos de los otros documentos suenan más cercanos en la intención de lo que está buscando: identificación de grupos y asignación de trayectorias a grupos, pero se ilustran utilizando datos de series de tiempo u otros ejemplos no geoespaciales. Sin embargo, pueden apuntar en direcciones interesantes.

Sugiero utilizar un enfoque similar al que se explica aquí .

ALGORITMO y denominación:

a) NODOS de capa de línea de nombre. Calcular rodamientos

b) unirse espacialmente a sí mismo (uno a muchos) utilizando la tolerancia a la distancia Nombre de la capa ENLACES

c) eliminar de LINKS se une a sí mismo, es decir, NAME = NAME_1

d) dentro de los ENLACES encontrar pares de direcciones "iguales". Solía:

def theSame(aList,tol):
    maxB=max(aList);minB=min(aList)
    if abs(maxB-minB)<tol:return 1
    if abs(maxB-minB-180)<tol:return 1
    return 0
#-----------
theSame( [!BEARING!, !BEARING_1!],15)

es decir, las líneas supuestas que van en dirección opuesta son similares en términos de dirección

d) eliminar pares no similares (0) de ENLACES.

e) calcular grupos de ENLACES conectados a través de NODES y transferir números de grupo a la tabla NODES:

Desafortunadamente:

Sin embargo, estadísticas simples de rodamientos dentro del grupo, por ejemplo, desviación estándar de:

abs(tan(bearing))

no muestra desviación en el primer caso y muy grande en el segundo. Del mismo modo, las estadísticas de longitudes podrían ayudar a "correr en paralelo durante mucho tiempo".

Si lo anterior es de interés, puedo actualizar la respuesta con el script que calcula grupos de enlaces conectados. Está utilizando el módulo arcpy y networkx.

No sé cómo tratar un par de líneas que van desde el mismo punto en direcciones opuestas ...

Hay en mis ojos un problema con la definición de las líneas, una que determinará qué enfoques usar (algunos de los mencionados anteriormente). Si se trata de pares OD y la geometría no juega un papel, abordaría esto en base a la agrupación en red. Usted dice que las redes no forman una red; que así sea, pero es probable que los orígenes y destinos caigan en regiones significativas, y por lo tanto, puede tratarla como una red.

Si la geometría tiene algo que decir (estas son, digamos, trayectorias GPS y desea considerar la geometría), entonces tendrá que trabajar realmente en un espacio (x, y, t): geometría similar de la huella del movimiento pero a diferente los tiempos pueden no evaluarse de la misma manera; esto no se especifica en la pregunta.

Algunas posibilidades de lo que puedes mirar:

1. Lo más cercano a su necesidad es Dodge, Weibel, Forootan (2009), aquí http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Si se puede simplificar la geometría, quizás los parámetros mencionados aquí puedan ser útiles: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Pero finalmente, releyendo una vez más su pregunta inicial, podría ser más simple: puede calcular en pares (entre segmentos) la distancia entre la intersección de la extensión lineal de los segmentos y sus puntos más cercanos, normalizar de alguna manera (tal vez en función de la longitud del segmento en sí) y usar un algoritmo de agrupamiento matricial? Razonamiento: los segmentos que se cruzan lejos son más similares (paralelos) que los que se cruzan cerca. En los dibujos, no dice cómo tratar los segmentos co-lineales o paralelos que están en un desplazamiento (largo frechet dist). Supongo que esto daría problemas a la solución anterior. (editado para mayor claridad, indicando explícitamente "extensión lineal" arriba)

Nota (enero de 2018): Recientemente me topé con esto:

1. Cai, Yuhan y Raymond Ng. "Indización de trayectorias espacio-temporales con polinomios de Chebyshev". Actas de la conferencia internacional ACM SIGMOD 2004 sobre gestión de datos. ACM, 2004.

Lo que se relaciona con la similitud de trayectoria y, por lo tanto, permitiría la cuantificación de similitud hasta cierto punto. Esto se basa en la aproximación polinómica de curvas y el cálculo de una distancia de Chebyshev.

¿Puede dar un poco más de detalles sobre el tipo de datos con los que está trabajando? ¿Son solo una serie de líneas disjuntas o forman una red? ¿Ha utilizado alguna de las herramientas de ArcGIS para el análisis de patrones espaciales? Muchos de los métodos de ArcGIS (Ripley's K, NN index, Morans I) solo usan el centroide de las líneas / polígonos cuando se usan en datos que no son puntos. Sin embargo, es posible que deba considerar dividir cada línea en secciones iguales para evitar que no se consideren líneas muy largas debido a que su centroide está muy lejos.

La otra cosa para pensar es, conceptualmente, ¿qué es un grupo de líneas? Puede tener muchas líneas que se originan una cerca de la otra, pero luego sus puntos finales podrían dispersarse. Del mismo modo, puede obtener muchas líneas que comienzan y terminan muy cerca una de la otra, pero luego se dispersan entre sus puntos de inicio / finalización.

Sin embargo, un enfoque podría ser simplemente realizar un análisis de densidad de línea para que las áreas con más líneas (que podrían considerarse agrupadas en algún sentido) tengan valores de cuadrícula altos, mientras que las áreas con baja densidad tendrán valores bajos. Entonces obtienes un poco de salida de punto caliente; Sin embargo, esto no le da una estadística única como Morans I o el NNI. Tampoco diferenciará entre densidad como resultado de una línea muy irregular (es decir, una espiral apretada) frente a muchas líneas.

Lo sentimos, esta no es una respuesta completa a su problema, pero creo que encontrar el concepto completo de lo que está tratando de lograr puede proporcionar algunas mejores soluciones.

ACTUALIZAR

Según el ejemplo que dio, creo que la sugerencia de FelixlP de crear un punto con atributo de marcación de línea para usar con medidas de patrones de puntos es probablemente una buena manera de hacerlo. Excepto que dividiría los puntos en segmentos iguales y tendría un punto con el rumbo de línea en cada vértice de línea. Luego, debe observar las medidas que analizarán la proximidad de cada punto y la similitud entre los rumbos (para detectar líneas más cercanas a la perpendicular).

Por lo tanto, usar el Getis-Ord GI (análisis de puntos de acceso) sería una buena herramienta para visualizar dónde están los grupos; y luego un Moran's I global para evaluar el nivel global de agrupamiento.

Sin embargo, la distancia a la que segmenta las líneas afectará el grado de agrupamiento encontrado. Si está buscando grupos en la escala de 1 km, entonces necesitaría segmentar las líneas alrededor de eso. Del mismo modo, si está buscando grupos en la escala de 100 m, necesitaría segmentar las líneas en consecuencia. Esto es para que no pierda líneas y también para que no detecte cada línea como un clúster.

Gracias por los ejemplos.

No he visto ningún método establecido para calcular lo que está buscando, sin embargo, este sería mi enfoque. Es una especie de solución de fuerza bruta.

Calcule un rectángulo de límite mínimo, luego expanda una cantidad arbitraria, pero igual de grande en cada una de las cuatro esquinas.

Encuentre el centro de masa del rectángulo de creación, calcule la distribución azimutal y de distancia para los puntos OD para cada línea, y haga lo mismo usando las esquinas de su rectángulo delimitador, junto con comparar los acimutes de las líneas.

Pruebe el paralelismo desde cada una de las cuatro esquinas hasta el final de cada rayo. Pruebe el paralelismo desde el centro de masa hasta el final de cada rayo.

Al hacer esto, podría comparar la desviación de las esquinas a los extremos. En el ejemplo (a), tendría líneas casi paralelas desde dos de las esquinas a cada uno de los tres grupos de líneas. También tendría líneas casi paralelas desde el centro de masa hasta los extremos de los extremos lejanos de las líneas.

Ejemplo (b) no tendría líneas paralelas cercanas al calcular desde las esquinas hasta los extremos de cada línea, pero las líneas no parecen aleatorias, se conducen entre sí con ligeras desviaciones.

El ejemplo (c) parece ser aleatorio

El ejemplo (d) no es aleatorio, es radial.

Al observar esto más, realizaría las pruebas que describí anteriormente, así como crearía pruebas de solución de triángulos desde las esquinas del rectángulo envolvente creado hasta los extremos de los rayos. Ángulos interiores y áreas similares ayudarían a verificar la agrupación a menos que una de las líneas en el grupo sea significativamente más corta que las otras.

Lo anterior es solo la opinión de un tonto, y probablemente estoy equivocado.

Siguiendo su descripción instintiva, ¿cuál es el criterio para que 2 líneas sean paralelas?

Básicamente, puede hacer una prueba en sus puntos de inicio o finalización:
Sea Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2)
y Ex, Ey lo mismo pero para sus puntos finales.

Entonces, si sqrt (Sx² + Sy²) AND sqrt (Ex² + Ey²) está debajo de un cierto umbral, puede considerar estas líneas como paralelas.