Tests statistiques pour les modèles de lignes spatiales?

Il existe de nombreux tests pour les modèles de points spatiaux pouvant être utilisés pour déterminer si les points sont distribués de manière aléatoire ou non, mais existe-t-il des tests établis pour les modèles de lignes spatiales? (Je pense aux lignes droites, avec juste les points de départ et d'arrivée et pas de nœuds intermédiaires.)

Les données que je souhaite analyser sont les lignes OD (origine-destination) du mouvement humain et animal. (Similaire à l'exemple de la mise en cluster de lignes non dirigées .)

Jusqu'ici, une idée était de traiter des lignes comme des points 4D et d'utiliser des tests de configuration de points, mais je ne sais pas si cela convient.

Le test idéal permettrait de déterminer s’il existe ou non des grappes de lignes.

Instinctivement, je dirais que beaucoup de lignes qui commencent par la même origine mais qui ont toutes sortes de destinations différentes ne doivent pas être considérées comme un cluster. Par ailleurs, de nombreuses lignes qui fonctionnent (presque) en parallèle pendant une période plus longue constitueraient un cluster.

C'est une question difficile, car il n'y a pas eu beaucoup, s'il en est, de statistiques de processus spatiales développées pour les entités linéaires. Sans creuser sérieusement dans les équations et le code, les statistiques de processus ponctuelles ne sont pas facilement applicables aux entités linéaires et sont donc statistiquement non valides. En effet, le caractère NULL contre lequel un modèle donné est testé est basé sur des événements ponctuels et non sur des dépendances linéaires dans le champ aléatoire. Je dois dire que je ne sais même pas ce que le zéro serait en ce qui concerne l'intensité et l'arrangement / l'orientation serait encore plus difficile.

Je ne fais que cracher les pieds ici, mais je me demande si une évaluation à plusieurs échelles de la densité de lignes couplée à une distance euclidienne (ou une distance de Hausdorff si les lignes sont complexes) n'indiquerait pas une mesure continue du regroupement. Ces données pourraient ensuite être résumées en vecteurs de ligne, en utilisant la variance pour tenir compte de la disparité de longueurs (Thomas 2011), puis en attribuant une valeur de cluster à l'aide d'une statistique telle que K-moyennes. Je sais que vous ne recherchez pas les clusters mais la valeur de cluster peut partitionner les degrés de clustering. Cela nécessiterait évidemment un ajustement optimal de k, de sorte que des grappes arbitraires ne sont pas attribuées. Je pense que ce serait une approche intéressante pour évaluer la structure des contours dans les modèles théoriques de graphes.

Voici un exemple travaillé en R, désolé, mais il est plus rapide et plus reproductible que de fournir un exemple QGIS, et il est plus dans ma zone de confort :)

Ajouter des bibliothèques et utiliser un objet cuivre psp de spatstat comme exemple de ligne

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

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

Calculer la densité de ligne normalisée des premier et deuxième ordres, puis contraindre les objets de la classe de trame

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

Normaliser les densités des premier et deuxième ordres dans une densité intégrée à l'échelle

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

Calculer la distance euclidienne inversée normalisée et le contraindre à la classe de trame

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

Contraint spatstat psp en un objet sp SpatialLinesDataFrame à utiliser dans 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)) )

Résultats de la parcelle

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) 

Extraire des valeurs de raster et calculer des statistiques récapitulatives associées à chaque ligne

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)))

Utilisez les valeurs de silhouette de cluster pour évaluer k optimal (nombre de clusters), avec la fonction optimal.k, puis affectez des valeurs de cluster à des lignes. Nous pouvons ensuite affecter des couleurs à chaque cluster et tracer par-dessus le raster de densité.

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)

À ce stade, il est possible d'effectuer une randomisation des lignes pour vérifier si l'intensité et la distance résultantes sont significatives à partir de façon aléatoire. Vous pouvez utiliser la fonction "rshift.psp" pour réorienter vos lignes de manière aléatoire. Vous pouvez également simplement randomiser les points de début et de fin et recréer chaque ligne.

On peut également se demander "si" vous venez d'effectuer une analyse de configuration de points à l'aide d'une statistique d'analyse univariée ou croisée sur les points de début et de fin, invariants des lignes. Dans une analyse univariée, comparez les résultats des points de départ et d’arrêt pour vérifier s’il existe une cohérence dans la mise en cluster des modèles de deux points. Cela pourrait être fait via un f-hat, un G-hat ou un Ripley's-K-hat (pour les processus ponctuels non marqués). Une autre approche serait une analyse croisée (par exemple, cross-K) où les deux processus ponctuels sont testés simultanément en les marquant comme [start, stop]. Cela indiquerait les relations de distance dans le processus de regroupement entre les points de départ et d'arrêt. cependant, La dépendance spatiale (non staionarité) sur un processus d'intensité sous-jacent peut être un problème dans ces types de modèles, ce qui les rend non homogènes et nécessite un modèle différent. Ironiquement, le processus inhomogène est modélisé à l'aide d'une fonction d'intensité, ce qui nous ramène à la densité, ce qui conforte l'idée d'utiliser une densité intégrée à l'échelle comme mesure de la classification.

Voici un exemple rapide d'utilisation de la statistique Ripleys K (Besags L) pour l'autocorrélation d'un processus ponctuel non marqué à l'aide des emplacements de début et d'arrêt d'une classe d'entités linéaires. Le dernier modèle est un modèle croisé utilisant les emplacements de départ et d’arrêt en tant que processus marqué 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) ) )

Les références

Thomas JCR (2011) Un nouvel algorithme de clustering basé sur K-Means utilisant un segment de ligne comme prototype. Dans: San Martin C., Kim SW. (eds) Progrès en reconnaissance de formes, analyse d’images, vision par ordinateur et applications. CIARP 2011. Notes de cours en informatique, vol 7042. Springer, Berlin, Heidelberg

Vous voudrez peut-être examiner la distance de Fréchet . Ce n'est que récemment que j'ai appris l'existence d'une question posée récemment à la recherche d'une implémentation en python.

Il s'agit d'une métrique permettant de rechercher la similarité spatiale des chaînes de lignes . C'est une idée similaire à la distance de Hausdorff, l'équivalent pour les mesures de similarité de polygones, mais pour les chaînes de lignes avec une direction.

La distance de Fréchet est définie comme la longueur minimale d'une laisse reliant un chien sur une trajectoire à son propriétaire sur une seconde trajectoire, les deux ne se déplaçant jamais en arrière

Cette métrique aura une petite valeur pour deux courbes proches, presque parallèles, alignées de la même manière et ayant une longueur similaire.

Cela ne répond pas à la partie d'identification du cluster, cependant.

Il y a une présentation complète ici . Votre situation ressemble à celle de certains des cas d'utilisation mentionnés dans les sections 46 à 49.

Cette métrique a beaucoup d'utilisations non géospatiales telles que

• détecter les sous-modèles communs dans le séquençage des gènes
• reconnaissance de l'écriture
• détecter des périodes corrélées dans une série chronologique, comme l'historique des cours des actions

Ainsi, bien que de nombreux articles de la bibliographie traitent de ce sujet, la plupart d’entre eux ne sont pas géospatiaux. La plupart de ces articles relèvent également de l'algorithmique / des mathématiques / de l'informatique plutôt que du géospatial / des géosciences et sont donc conçus en conséquence.

Cependant, cet article semblait prometteur: -

Buchin, K., Buchin, M. et Wang, Y. (2009). Algorithmes exacts pour l'appariement partiel des courbes via la distance de Fréchet. Dans Actes du vingtième symposium ACM-SIAM sur les algorithmes discrets, pages 645–654

Certains des autres documents semblent plus proches de l'intention que vous recherchez - l'identification des grappes et l'attribution de trajectoires aux grappes - mais ils sont illustrés à l'aide de données chronologiques ou d'autres exemples non géospatiaux. Cependant, ils pourraient indiquer des directions intéressantes.

Je suggère d'utiliser une approche similaire à celle expliquée ici .

ALGORITHME et nommage:

a) Nom de la couche de lignes NODES Calculer les roulements

b) se joindre spatialement à lui-même (un à plusieurs) en utilisant la tolérance de distance. Couche de noms LIENS

c) retirer de LINKS se joint à lui-même, c'est-à-dire NAME = NAME_1

d) À l'intérieur des LIENS, trouvez les "mêmes" paires de directions. J'ai utilisé:

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)

c'est-à-dire que les lignes supposées dans la direction opposée sont similaires en termes de direction

d) supprimer les paires non similaires (0) de LINKS.

e) calculer des groupes de liens connectés via NODES et transférer les numéros de groupe dans la table NODES:

Malheureusement:

Cependant, de simples statistiques sur les roulements au sein du groupe, par exemple l’écart type de:

abs(tan(bearing))

montré aucun écart dans le premier cas et un très grand en second. De même, des statistiques sur les longueurs pourraient aider à «fonctionner en parallèle pendant longtemps».

Si ce qui précède est intéressant, je peux mettre à jour answer avec le script qui calcule les groupes de liens connectés. Il utilise les modules arcpy et networkx.

Je ne sais pas comment traiter une paire de lignes partant du même point dans des directions opposées ...

Il y a dans mes yeux un problème avec la définition des lignes, un problème qui déterminera quelles approches utiliser (certaines de celles mentionnées ci-dessus). Si ce sont des paires OD et que la géométrie ne joue pas un rôle, j'approcherais cela en se basant sur le clustering de réseau. Vous dites que les réseaux ne forment pas un réseau - ainsi soit-il, mais il est probable que les origines et les destinations se situent dans des régions significatives et vous pouvez donc le traiter comme un réseau.

Si la géométrie a quelque chose à dire (ce sont, par exemple, des trajectoires GPS et que vous souhaitez prendre en compte la géométrie), il vous faudra réellement travailler dans un espace (x, y, t): une géométrie similaire de l’empreinte du mouvement mais à des angles différents. les temps peuvent ne pas être évalués comme identiques - cela n’est pas précisé dans la question.

Quelques possibilités que vous pouvez regarder:

1. Le plus proche de vos besoins est Dodge, Weibel, Forootan (2009), ici http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Si la géométrie peut être simplifiée, les paramètres mentionnés ici peuvent être utiles: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Mais finalement, en relisant une fois de plus votre question initiale, cela pourrait être plus simple: pouvez-vous calculer par paire (entre les segments) la distance entre l’intersection de l’extension linéaire des segments et leurs points les plus proches, normaliser du segment lui-même) et utiliser un algorithme de classification matricielle? Raisonnement: les segments qui se croisent loin sont plus similaires (parallèles) que ceux qui se croisent à proximité. Dans les dessins, vous ne dites pas comment traiter les segments colinéaires ou parallèles qui se trouvent dans un décalage (long frechet dist). Je suppose que cela donnerait des problèmes à la solution ci-dessus. (édité pour plus de clarté, en mentionnant explicitement "extension linéaire" ci-dessus)

Note (janvier 2018): Je suis récemment tombé sur ceci:

1. Cai, Yuhan et Raymond Ng. "Indexation des trajectoires spatio-temporelles avec les polynômes de Chebyshev." Actes de la conférence internationale ACM SIGMOD de 2004 sur la gestion des données. ACM, 2004.

Ce qui concerne la similarité de trajectoire et permettrait ainsi une quantification de similarité dans une certaine mesure. Ceci est basé sur une approximation polynomiale des courbes et le calcul d'une distance de Chebyshev.

Pouvez-vous donner un peu plus de détails sur le type de données avec lequel vous travaillez? S'agit-il simplement d'une série de lignes disjointes ou forment-elles un réseau? Avez-vous utilisé l'un des outils ArcGIS pour l'analyse de modèle spatial? De nombreuses méthodes ArcGIS (index K, NN de Ripley, Morans I) utilisent uniquement le centroïde des lignes / polygones lorsqu'elles sont utilisées sur des données non ponctuelles. Cependant, dans ce cas, vous devrez peut-être diviser chaque ligne en parties égales pour éviter que de très longues lignes ne soient considérées, car leur centre de gravité est très éloigné.

L'autre chose à considérer est, conceptuellement, qu'est-ce qu'un groupe de lignes? Vous pouvez avoir plusieurs lignes proches les unes des autres, mais leurs extrémités peuvent ensuite être dispersées. De même, vous pouvez obtenir de nombreuses lignes commençant et finissant très proches les unes des autres, mais devenant ensuite très dispersées entre leurs points de départ et d'arrivée.

Une approche pourrait toutefois consister simplement à effectuer une analyse de la densité de lignes afin que les zones comportant plus de lignes (pouvant être considérées comme regroupées dans un sens) aient des valeurs de grille élevées, tandis que les zones de faible densité ont des valeurs faibles. Donc, vous obtenez un peu d'une sortie hot-spot; Cependant, cela ne vous donne pas une seule statistique comme Morans I ou NNI. Cela ne fera pas non plus la différence entre la densité résultant d’une ligne très irrégulière (c’est-à-dire d’une spirale serrée) et de plusieurs lignes.

Désolé, ce n’est pas une réponse complète à votre problème, mais je pense que définir le concept complet de ce que vous essayez d’obtenir pourrait fournir de meilleures solutions.

MISE À JOUR

Sur la base de l'exemple que vous avez donné, je pense que la suggestion de FelixPl de créer un attribut de point avec une ligne à utiliser avec des mesures de motifs de points est probablement une bonne solution. Sauf que je voudrais diviser les points en segments égaux et avoir un point avec la ligne qui se trouve à chaque sommet de la ligne. Ensuite, vous devez examiner les mesures qui vont examiner la proximité de chaque point et la similarité entre les relèvements (afin de détecter les lignes les plus proches de la perpendiculaire).

Donc, utiliser l’indication Getis-Ord GI (analyse des points chauds) serait un bon outil pour visualiser où se trouvent les clusters; et ensuite un Moran I global pour évaluer le niveau global de regroupement.

La distance à laquelle vous segmentez les lignes aura toutefois un effet sur le degré de classification trouvé. Si vous recherchez des groupes à l’échelle de 1 km, il vous faudra segmenter les lignes en fonction de cela. De même, si vous recherchez des groupes à l’échelle de 100 m, vous devrez segmenter les lignes en conséquence. C'est pour que vous ne manquiez pas de lignes et que vous ne détectiez pas chaque ligne comme un cluster.

Merci pour les exemples.

Je n'ai pas vu de méthodes établies pour calculer ce que vous recherchez, mais ce serait mon approche. C'est une sorte de solution de force brute.

Calculez un rectangle de délimitation minimal, puis développez-le de manière arbitraire, mais égale, à chacun des quatre coins.

Recherchez le centre de masse du rectangle de création, calculez la distribution d'azimutal et de distance pour les points OD de chaque ligne, puis procédez de la même manière à l'aide des coins de votre rectangle de contour, tout en comparant les azimuts des lignes.

Testez le parallélisme de chacun des quatre coins à la fin de chaque rayon. Testez le parallélisme du centre de masse à la fin de chaque rayon.

En faisant cela, vous pouvez comparer les écarts entre les coins et les extrémités. Dans l'exemple (a), vous auriez des lignes presque parallèles de deux des angles à chacun des trois groupes de lignes. Vous auriez également des lignes presque parallèles allant du centre de gravité aux extrémités des lignes.

Exemple (b) vous n'aurez pas de lignes quasi parallèles lors du calcul des angles aux extrémités de chaque ligne, mais les lignes ne semblent pas aléatoires, elles se séparent légèrement.

Exemple (c) semble être aléatoire

L'exemple (d) n'est pas aléatoire, il est radial.

En regardant cela plus en détail, je lancerais les tests que j'ai décrits ci-dessus, ainsi que créer des tests de solution de triangle depuis les coins du rectangle de fermeture créé jusqu'aux extrémités des rayons. Des angles intérieurs et des zones similaires aideraient à vérifier le regroupement sauf si l'une des lignes du groupe est nettement plus courte que les autres.

Ce qui précède n’est que l’opinion d’un imbécile, et j’ai probablement tort.

Après votre description instinctive, quel est le critère pour que 2 lignes soient parallèles?

Vous pouvez en principe faire un test sur leurs points de départ ou d'arrivée:
Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2)
et Ex, Ey de la même manière, mais pour leurs points finaux.

Donc, si sqrt (Sx² + Sy²) ET sqrt (Ex² + Ey²) est en dessous d’un certain seuil, vous pouvez considérer ces lignes comme étant parallèles.