Statistische Tests für räumliche Linienmuster?

Es gibt viele Tests für räumliche Punktmuster, mit denen festgestellt werden kann, ob Punkte zufällig verteilt sind oder nicht. Gibt es jedoch etablierte Tests für räumliche Linienmuster? (Ich denke gerade Linien, mit nur Start- und Endpunkt und ohne Zwischenknoten.)

Die Daten, die ich analysieren möchte, sind OD-Linien (Ursprung-Ziel-Linien) der menschlichen und tierischen Bewegung. (Ähnlich wie im Beispiel unter Clustering ungerichteter Linien .)

Bisher bestand eine Idee darin, Linien wie 4D-Punkte zu behandeln und Punktmustertests zu verwenden, aber ich bin mir nicht sicher, ob dies angemessen ist.

Der ideale Test würde es ermöglichen, festzustellen, ob es Gruppen von Linien gibt oder nicht.

Instinktiv würde ich sagen, dass viele Linien, die am selben Ursprung beginnen, aber alle möglichen unterschiedlichen Ziele haben, nicht als Cluster betrachtet werden sollten. Auf der anderen Seite wären viele Linien, die über einen längeren Zeitraum (nahezu) parallel verlaufen, ein Cluster.

Dies ist eine schwierige Frage, da für Linienmerkmale nur wenige, wenn überhaupt, räumliche Prozessstatistiken entwickelt wurden. Ohne sich ernsthaft mit Gleichungen und Code zu befassen, sind Punktprozessstatistiken nicht ohne weiteres auf lineare Features anwendbar und daher statistisch ungültig. Dies liegt daran, dass die Null, gegen die ein bestimmtes Muster getestet wird, auf Punktereignissen und nicht auf linearen Abhängigkeiten im Zufallsfeld basiert. Ich muss sagen, dass ich nicht einmal weiß, was die Null wäre, was Intensität und Anordnung / Ausrichtung noch schwieriger machen würde.

Ich spucke hier nur herum, aber ich frage mich, ob eine mehrskalige Bewertung der Liniendichte in Verbindung mit dem euklidischen Abstand (oder dem Hausdorff-Abstand, wenn die Linien komplex sind) kein kontinuierliches Maß für die Häufung bedeuten würde. Diese Daten könnten dann unter Verwendung von Varianz zur Berücksichtigung von Längenunterschieden zu den Linienvektoren zusammengefasst werden (Thomas 2011) und unter Verwendung einer Statistik wie K-means einem Clusterwert zugewiesen werden. Ich weiß, dass Sie nicht nach zugewiesenen Clustern sind, aber der Clusterwert kann Clusterungsgrade aufteilen. Dies würde natürlich eine optimale Anpassung von k erfordern, so dass keine willkürlichen Cluster zugewiesen werden. Ich denke, dass dies ein interessanter Ansatz für die Bewertung der Kantenstruktur in graphentheoretischen Modellen wäre.

Hier ist ein Beispiel in R, sorry, aber es ist schneller und reproduzierbarer als ein QGIS-Beispiel und liegt mehr in meiner Komfortzone :)

Fügen Sie Bibliotheken hinzu und verwenden Sie das Kupfer-PSP-Objekt von spatstat als Linienbeispiel

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

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

Berechnen Sie die standardisierte Liniendichte 1. und 2. Ordnung und zwingen Sie sie dann zu Objekten der Rasterklasse

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

Standardisieren Sie die Dichte 1. und 2. Ordnung zu einer skalierten Dichte

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

Berechnen Sie die standardisierte invertierte euklidische Distanz und errechnen Sie sie für die Rasterklasse

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

Erzwingen Sie die Verwendung von spatstat psp in einem sp SpatialLinesDataFrame-Objekt, das in raster :: extract verwendet werden soll

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

Plot-Ergebnisse

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) 

Extrahieren Sie Rasterwerte und berechnen Sie zusammenfassende Statistiken für jede Zeile

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

Verwenden Sie Cluster-Silhouette-Werte, um das optimale k (Anzahl der Cluster) mit der Funktion optimal.k zu ermitteln, und weisen Sie dann den Zeilen Cluster-Werte zu. Anschließend können wir jedem Cluster und Plot über dem Dichteraster Farben zuweisen.

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)

An diesem Punkt könnte man eine Randomisierung der Linien durchführen, um zu testen, ob die resultierende Intensität und Entfernung vom Zufall signifikant sind. Sie können die Funktion "rshift.psp" verwenden, um Ihre Zeilen nach dem Zufallsprinzip neu auszurichten. Sie können auch einfach die Start- und Stoppunkte zufällig sortieren und jede Linie neu erstellen.

Man fragt sich auch, "was wäre, wenn" Sie gerade eine Punktmusteranalyse mit einer univariaten oder Kreuzanalyse-Statistik für die Start- und Stoppunkte durchgeführt haben, die nicht mit den Linien übereinstimmen. In einer univariaten Analyse würden Sie die Ergebnisse der Start- und Stoppunkte vergleichen, um festzustellen, ob die Clusterbildung zwischen den beiden Punktmustern konsistent ist. Dies könnte über einen F-Hut, einen G-Hut oder einen Ripley's-K-Hut erfolgen (für nicht markierte Punktprozesse). Ein anderer Ansatz wäre eine Kreuzanalyse (z. B. Kreuz-K), bei der die Zweipunktprozesse gleichzeitig getestet werden, indem sie als [Start, Stopp] markiert werden. Dies würde die Entfernungsbeziehungen im Clustering-Prozess zwischen Start- und Stoppunkt angeben. Jedoch, Die räumliche Abhängigkeit (Nonstaionarity) von einem zugrunde liegenden Intensitätsprozess kann bei diesen Modelltypen ein Problem darstellen, das sie inhomogen macht und ein anderes Modell erfordert. Ironischerweise wird ein inhomogener Prozess mit einer Intensitätsfunktion modelliert, die uns den vollen Kreis zurück zur Dichte bringt und die Idee unterstützt, eine maßstabsintegrierte Dichte als Maß für die Clusterbildung zu verwenden.

Hier ist ein kurzes Beispiel dafür, ob die Ripleys K (Besags L) -Statistik für die Autokorrelation eines nicht markierten Punktprozesses die Start- und Stopppositionen einer Linien-Feature-Class verwendet. Das letzte Modell ist ein Cross-K, bei dem sowohl Start- als auch Stopp-Positionen als nominal markierter Prozess verwendet werden.

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

Verweise

Thomas JCR (2011) Ein neuer Clustering-Algorithmus basierend auf K-Mitteln unter Verwendung eines Liniensegments als Prototyp. In: San Martin C., Kim SW. (Hrsg.) Fortschritte bei der Mustererkennung, Bildanalyse, Computer Vision und Anwendungen. CIARP 2011. Lecture Notes in Computer Science, Bd. 7042. Springer, Berlin, Heidelberg

Vielleicht möchten Sie einen Blick auf die Entfernung von Fréchet werfen . Dies habe ich erst kürzlich nach einer kürzlich gestellten Frage nach einer Python-Implementierung herausgefunden.

Dies ist eine Metrik zum Ermitteln der räumlichen Ähnlichkeit von Linienfolgen . Es ist eine ähnliche Idee wie bei Hausdorff, das Äquivalent für Polygonähnlichkeitsmaße, aber für Linienfolgen mit einer Richtung.

Die Fréchet-Distanz ist definiert als die minimale Länge einer Leine, die einen Hund auf einer Flugbahn mit seinem Besitzer auf einer zweiten Flugbahn verbindet, wobei sich beide niemals rückwärts bewegen

Diese Metrik hat einen kleinen Wert für zwei Kurven, die nahe beieinander liegen, nahezu parallel, gleich ausgerichtet und von ähnlicher Länge sind.

Dies beantwortet jedoch nicht den Teil zur Clusteridentifizierung.

Es gibt hier eine umfassende Präsentation . Ihre Situation klingt nach einigen der in den Abschnitten 46-49 genannten Anwendungsfälle

Diese Metrik hat viele nicht-räumliche Verwendungen wie

• Detektion gemeinsamer Submuster bei der Gensequenzierung
• Handschrifterkennung
• Ermittlung korrelierter Zeiträume in Zeitreihen wie Aktienkursverläufen

Viele Veröffentlichungen in der Bibliographie befassen sich mit diesem Thema, die meisten sind jedoch nicht räumlich. Auch die meisten dieser Arbeiten fallen eher unter Algorithmus / Mathematik / Informatik als unter Geospatial / Geowissenschaften und sind dementsprechend ausgerichtet.

Dieses Papier sah jedoch vielversprechend aus:

Buchin, K., Buchin, M. und Wang, Y. (2009). Genaue Algorithmen zur Teilkurvenanpassung über die Fréchet-Distanz. In Proceedings of the 20th ACM-SIAM-Symposium über diskrete Algorithmen, S. 645–654

Einige der anderen Veröffentlichungen sind eher auf das ausgerichtet, wonach Sie streben - die Identifizierung von Clustern und die Zuordnung von Trajektorien zu Clustern -, werden jedoch anhand von Zeitreihendaten oder anderen nicht-räumlichen Beispielen veranschaulicht. Sie könnten jedoch in interessante Richtungen weisen.

Ich schlage vor, einen Ansatz zu verwenden, der dem hier erläuterten ähnelt .

ALGORITHMUS und Benennung:

a) Name Line Layer NODES. Lager berechnen

b) räumlich mit sich selbst verbinden (eins zu viele) unter Verwendung von Abstandstoleranz. Namensschicht LINKS

c) Entferne von LINKS Joins zu sich selbst, dh NAME = NAME_1

d) Innerhalb von LINKS finden Sie "gleiche" Richtungspaare. Ich benutzte:

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)

dh angenommene Linien, die in entgegengesetzter Richtung verlaufen, sind in Bezug auf die Richtung ähnlich

d) entferne nicht ähnliche (0) Paare von LINKS.

e) Berechnen Sie Gruppen von LINKS, die über NODES verbunden sind, und übertragen Sie die Gruppennummern in die NODES-Tabelle:

Unglücklicherweise:

Einfache Statistik der Lager innerhalb der Gruppe, zB Standardabweichung von:

abs(tan(bearing))

zeigte keine Abweichung im ersten Fall und eine sehr große Abweichung im zweiten. In ähnlicher Weise könnte eine Längenstatistik helfen, wenn man lange Zeit parallel läuft.

Wenn dies von Interesse ist, kann ich die Antwort mit dem Skript aktualisieren, das verbundene Linkgruppen berechnet. Es verwendet das arcpy- und das networkx-Modul.

Ich weiß nicht, wie ich Linienpaare behandeln soll, die vom selben Punkt in entgegengesetzte Richtungen verlaufen ...

In meinen Augen gibt es ein Problem mit der Definition der Linien, eines, das bestimmt, welche Ansätze verwendet werden sollen (einige der oben genannten). Wenn dies OD-Paare sind und die Geometrie keine Rolle spielt, würde ich dies auf der Grundlage von Netzwerkclustern angehen. Sie sagen, die Netzwerke bilden kein Netzwerk - also sei es, aber es ist wahrscheinlich, dass die Ursprünge und Ziele in bedeutungsvolle Regionen fallen, und Sie können es daher als Netzwerk behandeln.

Wenn die Geometrie etwas zu sagen hat (dies sind z. B. GPS-Trajektorien und Sie möchten die Geometrie berücksichtigen), müssen Sie in einem (x, y, t) Raum wirklich arbeiten - ähnliche Geometrie des Bewegungsgrundrisses, aber mit unterschiedlicher Geometrie Zeiten dürfen nicht als gleich gewertet werden - dies ist in der Frage nicht angegeben.

Einige Möglichkeiten, was Sie sehen können:

1. Am nächsten an Ihrem Bedarf liegt Dodge, Weibel, Forootan (2009), hier http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Wenn die Geometrie vereinfacht werden kann, können möglicherweise die hier genannten Parameter von Nutzen sein: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Wenn Sie Ihre ursprüngliche Frage aber noch einmal durchlesen, könnte es einfacher sein: Können Sie den Abstand zwischen dem Schnittpunkt der linearen Ausdehnung der Segmente und ihren nächsten Punkten paarweise (zwischen den Segmenten) berechnen und irgendwie normalisieren (möglicherweise basierend auf der Länge) des Segments selbst) und verwenden Sie einen Matrix-Clustering-Algorithmus? Begründung: Segmente, die sich weit schneiden, sind ähnlicher (paralleler) als solche, die sich in der Nähe schneiden. In den Zeichnungen wird nicht angegeben, wie kolineare oder parallele Segmente behandelt werden sollen, die versetzt sind (langer Abstand). Ich gehe davon aus, dass dies der obigen Lösung Probleme bereiten würde. (Der Übersichtlichkeit halber bearbeitet, indem oben explizit "lineare Ausdehnung" angegeben wird)

Anmerkung (Januar 2018): Ich bin kürzlich auf Folgendes gestoßen:

1. Cai, Yuhan und Raymond Ng. "Indizieren von räumlich-zeitlichen Trajektorien mit Chebyshev-Polynomen." Tagungsband der internationalen ACM SIGMOD-Konferenz 2004 zum Thema Datenmanagement. ACM, 2004.

Was sich auf die Ähnlichkeit der Flugbahn bezieht und somit eine gewisse Quantifizierung der Ähnlichkeit ermöglichen würde. Dies basiert auf der polynomialen Approximation von Kurven und der Berechnung eines Chebyshev-Abstandes.

Können Sie die Art der Daten, mit denen Sie arbeiten, etwas genauer beschreiben? Sind dies nur eine Reihe von getrennten Linien oder bilden sie ein Netzwerk? Haben Sie eines der ArcGIS-Tools für die räumliche Musteranalyse verwendet? Bei vielen ArcGIS-Methoden (Ripleys K, NN-Index, Morans I) wird bei Nicht-Punkt-Daten nur der Schwerpunkt der Linien / Polygone verwendet. Hier müssen Sie jedoch möglicherweise in Betracht ziehen, jede Zeile in gleiche Abschnitte zu unterteilen, um zu vermeiden, dass sehr lange Zeilen aufgrund ihres sehr weit entfernten Schwerpunkts nicht berücksichtigt werden.

Die andere Sache, über die man nachdenken sollte, ist konzeptionell, was ist eine Ansammlung von Linien? Möglicherweise haben Sie viele Linien, die nahe beieinander liegen, aber dann könnten ihre Endpunkte verstreut sein. In ähnlicher Weise erhalten Sie möglicherweise viele Linien, die sehr nahe beieinander beginnen und enden, sich jedoch zwischen ihren Start- / Endpunkten stark verteilen.

Ein Ansatz könnte jedoch darin bestehen, einfach eine Liniendichteanalyse durchzuführen, damit Bereiche mit mehr Linien (die in gewissem Sinne als gruppiert angesehen werden können) hohe Rasterwerte aufweisen, während Bereiche mit geringer Dichte niedrige Werte aufweisen. Sie erhalten also eine Art Hot-Spot-Ausgabe. Dies gibt Ihnen jedoch keine einzige Statistik wie Morans I oder die NNI. Es wird auch nicht zwischen der Dichte aufgrund einer sehr unregelmäßigen Linie (dh einer engen Spirale) und vielen Linien unterschieden.

Tut mir leid, dass dies keine vollständige Antwort auf Ihr Problem ist, aber ich denke, dass das vollständige Konzept dessen, was Sie erreichen möchten, einige bessere Lösungen bieten kann.

AKTUALISIEREN

Anhand des von Ihnen gegebenen Beispiels denke ich, dass FelixlPs Vorschlag, einen Punkt mit einem Attribut zur Linienführung zu erstellen, der mit Punktmustermaßen verwendet werden kann, wahrscheinlich ein guter Weg ist. Es sei denn, ich würde die Punkte in gleiche Segmente unterteilen und einen Punkt mit der Linienpeilung an jedem Linienscheitelpunkt haben. Dann müssen Sie Maßnahmen untersuchen, die die Nähe jedes Punkts und die Ähnlichkeit zwischen den Peilungen untersuchen (damit Sie Linien erkennen, die näher an der Senkrechten liegen).

Die Verwendung der Getis-Ord-GI (Hotspot-Analyse) ist daher ein gutes Werkzeug, um die Position der Cluster zu visualisieren. und dann das I eines globalen Morans, um die globale Ebene der Clusterbildung zu bewerten.

Der Abstand, in dem Sie die Linien segmentieren, wirkt sich jedoch auf den Grad der gefundenen Clusterbildung aus. Wenn Sie nach Clustern im Maßstab 1 km suchen, müssten Sie die Linien so segmentieren, dass sie ungefähr so ​​lang sind. Wenn Sie nach Clustern auf der 100-m-Skala suchen, müssen Sie die Linien entsprechend segmentieren. Auf diese Weise verpassen Sie keine Zeilen und erkennen auch nicht jede Zeile als Cluster.

Danke für die Beispiele.

Ich habe keine etablierten Methoden gesehen, um zu berechnen, wonach Sie suchen. Dies wäre jedoch mein Ansatz. Es ist eine Art Brute-Force-Lösung.

Berechnen Sie ein minimales Begrenzungsrechteck und erweitern Sie es an jeder der vier Ecken um einen beliebigen, aber gleich großen Betrag.

Ermitteln Sie den Massenmittelpunkt des erstellten Rechtecks, berechnen Sie die Azimut- und Abstandsverteilung für die OD-Punkte für jede Linie und verwenden Sie dazu die Ecken des umgebenden Rechtecks ​​und vergleichen Sie die Azimutwerte der Linien.

Prüfen Sie die Parallelität von jeder der vier Ecken bis zum Ende jedes Strahls. Prüfen Sie die Parallelität vom Massenmittelpunkt bis zum Ende jedes Strahls.

Auf diese Weise können Sie die Abweichung von den Ecken zu den Enden vergleichen. In Beispiel (a) hätten Sie nahezu parallele Linien von zwei der Ecken zu jedem der drei Liniencluster. Sie würden auch nahezu parallele Linien vom Massenmittelpunkt bis zu den Enden der fernen Enden der Linien haben.

Beispiel (b) Wenn Sie von den Ecken bis zu den Enden jeder Linie rechnen, würden Sie keine nahezu parallelen Linien haben, aber die Linien scheinen nicht zufällig zu sein, sie führen mit leichten Abweichungen zueinander.

Beispiel (c) scheint zufällig zu sein

Beispiel (d) ist nicht zufällig, es ist radial.

Wenn ich mir das genauer anschaue, führe ich die oben beschriebenen Tests aus und erstelle Dreieckslösungstests von den Ecken des erstellten umschließenden Rechtecks ​​bis zu den Enden der Strahlen. Ähnliche Innenwinkel und Flächen würden zur Überprüfung der Clusterbildung beitragen, es sei denn, eine der Linien im Cluster ist erheblich kürzer als die anderen.

Das Obige ist nur die Meinung eines Narren, und ich liege wahrscheinlich falsch.

Was ist nach Ihrer instinktiven Beschreibung das Kriterium für die Parallelität von 2 Linien?

Grundsätzlich können Sie einen Test an den Start- oder Endpunkten durchführen:
Lassen Sie Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2)
und Ex, Ey dasselbe, aber an den Endpunkten.

Wenn also sqrt (Sx² + Sy²) UND sqrt (Ex² + Ey²) unter einem bestimmten Schwellenwert liegen, können Sie diese Linien als parallel betrachten.