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

31

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

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

Hasta ahora, una idea era tratar las 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 deben considerarse un grupo. Por otro lado, muchas líneas que se ejecutan (cerca de) en paralelo durante un tiempo más largo serían un clúster.

    
pregunta underdark 10.06.2017 - 20:55

7 respuestas

16

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

Aquí simplemente estoy escupiendo bolas, pero me pregunto si una evaluación de escala múltiple de la densidad de 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 luego resumirse en los vectores de línea, utilizando la varianza para tener en cuenta la disparidad en las longitudes (Thomas 2011), y asignarle un valor de agrupación usando una estadística como K-medias. Sé que no le interesan los clústeres asignados, pero el valor del clúster podría dividir los grados de agrupamiento. 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 bordes en modelos teóricos de gráficos.

Este es un ejemplo práctico 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 el objeto de cobre psp de 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 de primer y segundo orden estandarizada y luego coaccione para rasterizar objetos de clase

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

Estandarizar la densidad del primer y segundo orden en una densidad integrada a la escala

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

Calcular la distancia euclidiana invertida estandarizada y obligar a la clase ráster

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

Coerce spatstat psp a un objeto 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 del gráfico

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 los valores de la silueta del clúster para evaluar k óptimo (número de clústeres), con la función óptimo.k, luego asigne valores de clúster a las líneas. Luego podemos asignar colores a cada grupo y trazar encima del ráster de densidad.

clust <- optimal.k(scale(l.stats), nk = 10, plot = TRUE)                      
  [email protected] <- data.frame([email protected], 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 al azar. Podría usar la función "rshift.psp" para reorientar aleatoriamente sus líneas. También podría aleatorizar los puntos de inicio y parada y recrear cada línea.

Uno también se pregunta "qué pasaría si" usted acaba de realizar un análisis de patrón de puntos utilizando un estadístico de análisis cruzado o univariado en los puntos de inicio y parada, invariante de las líneas. En un análisis univariado, compararía los resultados de los puntos inicial y final para ver si existe coherencia en la agrupación entre los dos patrones de puntos. Esto se puede hacer a través de un f-hat, G-hat o Ripley's-K-hat (para procesos de puntos sin marcar). Otro enfoque sería un análisis cruzado (p. Ej., K cruzado) 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 de inicio y parada. Sin embargo, la dependencia espacial (no estabilidad) en un proceso de intensidad subyacente puede ser un problema en este tipo de modelos, lo que los hace no homogéneos y requieren un modelo diferente. Irónicamente, el proceso no homogéneo se modela utilizando una función de intensidad que, por lo tanto, nos devuelve a la totalidad del círculo a la densidad, apoyando así la idea de utilizar una densidad integrada a la escala como medida del agrupamiento.

Este es un ejemplo rápido de si la estadística de Ripleys K (Besags L) para la autocorrelación de un proceso de puntos sin marcar usando las ubicaciones de inicio y parada de una clase de entidad de línea. El último modelo es un cross-k que usa tanto la ubicación de inicio como la de 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 J.C.R. (2011) Un nuevo algoritmo de agrupamiento basado en K-medias que usa un segmento de línea como prototipo. En: San Martin C., Kim SW. (eds) Progreso en el reconocimiento de patrones, análisis de imágenes, visión artificial y aplicaciones. CIARP 2011. Lecture Notes in Computer Science, vol 7042. Springer, Berlín, Heidelberg

    
respondido por el Jeffrey Evans 13.06.2017 - 22:32
14

Es posible que desee consultar distancia Fréchet . Hace poco me enteré de este 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 de líneas . Es una idea similar a la distancia de Hausdorff, el equivalente para medidas de similitud de polígonos, pero para líneas 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, ambos nunca se mueven hacia atrás

Esta métrica tendrá un valor pequeño para dos curvas que están ubicadas de manera cercana, 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

  • detectar subpatrones comunes en secuenciación de genes
  • reconocimiento de escritura a mano
  • detectar periodos correlacionados en series de tiempo como historiales de precios de acciones

así que mientras 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 artículos están incluidos en algoritmos / matemáticas / ciencias de la computación en lugar de geoespaciales / geociencias y están orientados en consecuencia.

Sin embargo, este documento parecía prometedor: -

Buchin, K., Buchin, M., y Wang, Y. (2009). Algoritmos exactos para la coincidencia de curvas parciales 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 parecen más cercanos a 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.

    
respondido por el Steven Kay 13.06.2017 - 14:02
4

¿Puede dar más detalles sobre el tipo de datos con los que está trabajando? ¿Se trata solo de una serie de líneas discontinuas 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 (K de Ripley, índice NN, Morans I) solo usan el centroide de las líneas / polígonos cuando se usan en datos no puntuales. 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 en que pensar es, conceptualmente, ¿qué es un grupo de líneas? Puede tener muchas líneas que se originan cerca unas de otras, pero entonces sus puntos finales podrían dispersarse. De manera similar, puede obtener muchas líneas que comienzan y terminan muy cerca unas de otras, pero luego se dispersan entre sus puntos de inicio / final.

Sin embargo, un enfoque podría ser simplemente realizar un análisis de densidad de líneas 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. Así que obtienes un poco de salida de punto caliente; Sin embargo, esto no le proporciona una estadística única como Morans I o NNI. Tampoco diferenciará la densidad como resultado de una línea muy irregular (es decir, una espiral cerrada) frente a muchas líneas.

Lo siento, esta no es una respuesta completa a tu problema, pero creo que el hecho de tener una idea completa de lo que estás tratando de lograr puede proporcionarte 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 forma de proceder. Excepto que dividiría los puntos en segmentos iguales y tendría un punto con la línea marcada en cada vértice de línea. Luego, debe observar las medidas que van a observar la proximidad de cada punto y la similitud entre los rodamientos (para detectar líneas que están más cerca de la perpendicular).

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

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

    
respondido por el Liam G 11.06.2017 - 15:23
4

Sugiero usar un enfoque similar al explicado aquí .

ALGORITMO y denominación:

a) Nombre de la capa de línea NODES. Rodamientos de cálculo

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

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

d) dentro de los ENLACES, se encuentran "iguales" pares de direcciones. Yo utilicé:

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) compute los grupos de ENLACES conectados a través de NODES y transfiera los números de grupo a la tabla NODES:

Lamentablemente:

Sinembargo,lasestadísticassimplesderodamientosdentrodelgrupo,porejemplo.desviaciónestándarde:

abs(tan(bearing))

nomostróningunadesviaciónenelprimercasoyunamuygrandeenelsegundo.Demanerasimilar,lasestadísticasdelongitudespodríanayudara"ejecutar en paralelo durante mucho tiempo".

Si lo anterior es interesante, puedo actualizar la respuesta con el script que calcula los 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 ...

    
respondido por el FelixIP 17.06.2017 - 06:21
4

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

Si la geometría tiene algo que decir (esto es, digamos trayectorias de GPS y usted desea considerar la geometría), entonces tendrá que trabajar realmente en un espacio (x, y, t) - geometría similar de la huella de movimiento pero en momentos diferentes no se pueden evaluar como iguales, esto no se especifica en la pregunta.

Algunas posibilidades de lo que puedes ver:

  1. Lo más cercano a su necesidad es Dodge, Weibel, Forootan (2009), aquí enlace
  2. Si se puede simplificar la geometría, tal vez los parámetros aquí mencionados pueden ser útiles: enlace

Pero finalmente, al volver a leer tu pregunta inicial, podría ser más simple: ¿puedes 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 en la longitud del segmento en sí) y utilizar un algoritmo de agrupamiento de matriz? Razonamiento: los segmentos que se intersecan 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 una desviación (distancia larga del borde). Supongo que esto daría problemas a la solución anterior. (editado para mayor claridad, expresando explícitamente la "extensión lineal" arriba)

Nota (enero de 2018): Recientemente me he topado con esto:

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

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

    
respondido por el MartinT 18.06.2017 - 13:36
3

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 delimitación mínimo, luego amplíelo de forma 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 la comparación de los azimuts de las líneas.

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

Al hacer esto, puedes 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 hasta 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 de las líneas.

Ejemplo (b) no tendría líneas casi paralelas al calcular desde las esquinas hasta los extremos de cada línea, pero las líneas no parecen ser aleatorias, conducen unas a otras con pequeñas desviaciones.

El ejemplo (c) parece ser aleatorio

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

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

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

    
respondido por el jbgramm 13.06.2017 - 06:01
-1

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

Básicamente, puede realizar una prueba en los puntos de inicio o final:
Deje Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2),
y Ex, Ey lo mismo pero por sus puntos finales.

Entonces, si sqrt (Sx² + Sy²) Y sqrt (Ex² + Ey²) se encuentran por debajo de un cierto umbral, puede considerar estas líneas como paralelas.

    
respondido por el s.k 13.06.2017 - 07:37

Lea otras preguntas en las etiquetas