Testy statystyczne wzorów linii przestrzennych?

Istnieje wiele testów wzorców punktów przestrzennych, które można wykorzystać do ustalenia, czy punkty są rozmieszczone losowo, czy nie, ale czy istnieją ustalone testy wzorców linii przestrzennych? (Myślę o liniach prostych, z punktem początkowym i końcowym, bez węzłów pośrednich).

Dane, które chcę przeanalizować, to linie OD (pochodzenie-miejsce docelowe) ruchu ludzi i zwierząt. (Podobnie jak w przykładzie w przypadku grupowania niekierowanych linii .)

Jak dotąd jednym pomysłem było traktowanie linii jak punktów 4D i stosowanie testów wzoru punktowego, ale nie jestem pewien, czy jest to właściwe.

Idealny test pozwoliłby ustalić, czy istnieją skupiska linii, czy nie.

Instynktownie powiedziałbym, że wiele linii, które zaczynają się od tego samego źródła, ale mają różne rodzaje miejsc docelowych, nie powinny być uważane za klaster. Z drugiej strony wiele linii, które biegną (blisko) równolegle przez dłuższy czas, byłoby klastrem.

To trudne pytanie, ponieważ po prostu nie opracowano wielu, jeśli w ogóle, statystyk procesu przestrzennego dla cech linii. Bez poważnego zagłębiania się w równania i kod, statystyki procesu punktowego nie mają łatwego zastosowania do cech liniowych, a zatem są statystycznie niepoprawne. Jest tak, ponieważ zero, na którym testowany jest dany wzorzec, opiera się na zdarzeniach punktowych, a nie liniowych zależnościach w polu losowym. Muszę powiedzieć, że nawet nie wiem, jaka byłaby wartość zerowa, o ile intensywność i układ / orientacja byłyby jeszcze trudniejsze.

Po prostu tutaj kulę pluć, ale zastanawiam się, czy wieloskalowa ocena gęstości linii w połączeniu z odległością euklidesową (lub odległości Hausdorffa, jeśli linie są złożone) nie wskazywałaby na ciągłą miarę skupiania. Dane te można następnie podsumować do wektorów liniowych, używając wariancji, aby uwzględnić rozbieżności długości (Thomas 2011), i przypisać wartość skupienia za pomocą statystyki, takiej jak K-średnie. Wiem, że nie jesteś po przypisanych klastrach, ale wartość klastra może podzielić stopnie klastrowania. Wymagałoby to oczywiście optymalnego dopasowania k, więc arbitralne klastry nie są przypisywane. Myślę, że byłoby to interesujące podejście do oceny struktury krawędzi w teoretycznych modelach graficznych.

Oto działający przykład w R, przepraszam, ale jest szybszy i bardziej powtarzalny niż dostarczanie przykładu QGIS i jest bardziej w mojej strefie komfortu :)

Dodaj biblioteki i użyj miedzianego obiektu psp ze spatstat jako przykładu linii

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

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

Oblicz standaryzowaną gęstość linii pierwszego i drugiego rzędu, a następnie wymusz na obiektach klasy rastrowej

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

Standaryzuj gęstość pierwszego i drugiego rzędu do gęstości zintegrowanej ze skalą

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

Oblicz znormalizowaną odwróconą odległość euklidesową i przymus do klasy rastrowej

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

Wymuś spatstat psp na obiekt SpatialLinesDataFrame do użycia w 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)) )

Wykreśl wyniki

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) 

Wyodrębnij wartości rastrowe i oblicz statystyki podsumowujące związane z każdą linią

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

Użyj wartości sylwetki klastra, aby ocenić optymalną wartość k (liczbę klastrów), z funkcją optimum.k, a następnie przypisz wartości klastra do linii. Następnie możemy przypisać kolory do każdego skupienia i narysować na górze rastra gęstości.

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)

W tym momencie można przeprowadzić randomizację linii, aby sprawdzić, czy uzyskana intensywność i odległość są znaczące w stosunku do losowości. Możesz użyć funkcji „rshift.psp”, aby losowo zmienić orientację linii. Możesz także po prostu randomizować punkty początkowe i końcowe oraz odtworzyć każdą linię.

Zastanawia się także „co jeśli” właśnie wykonałeś analizę wzoru punktowego za pomocą statystyki analizy jednowymiarowej lub krzyżowej na punktach początkowym i końcowym, niezmiennej dla linii. W analizie jednoczynnikowej porównywałbyś wyniki punktów początkowych i końcowych, aby sprawdzić, czy istnieje spójność w grupowaniu między dwoma wzorcami punktowymi. Można to zrobić za pomocą f-hat, G-hat lub Ripley's-K-hat (dla nieoznaczonych procesów punktowych). Innym podejściem byłaby analiza krzyżowa (np. Cross-K), w której dwa procesy punktowe są testowane jednocześnie poprzez oznaczenie ich jako [start, stop]. Oznaczałoby to relacje odległości w procesie grupowania między punktami początkowym i końcowym. Jednak, zależność przestrzenna (niestacjonarność) od leżącego u podstaw procesu intensywności może stanowić problem w tego typu modelach, czyniąc je niejednorodnymi i wymagającymi innego modelu. Jak na ironię, niejednorodny proces jest modelowany za pomocą funkcji intensywności, która przywraca nam pełne koło z powrotem do gęstości, wspierając w ten sposób ideę wykorzystania gęstości zintegrowanej ze skalą jako miary skupienia.

Oto szybko działający przykład, czy statystyka Ripleys K (Besags L) do autokorelacji procesu nieoznaczonego punktu przy użyciu lokalizacji początkowej i końcowej klasy obiektów liniowych. Ostatni model to cross-k wykorzystujący zarówno lokalizację początkową, jak i końcową jako proces oznaczony nominalnie.

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

Referencje

Thomas JCR (2011) Nowy algorytm grupowania oparty na środkach K przy użyciu segmentu linii jako prototypu. W: San Martin C., Kim SW. (eds) Postępy w rozpoznawaniu wzorów, analizie obrazu, wizji komputerowej i aplikacjach. CIARP 2011. Uwagi do wykładu z informatyki, tom 7042. Springer, Berlin, Heidelberg

Możesz spojrzeć na odległość Frécheta . Dopiero niedawno dowiedziałem się o tym po ostatnim pytaniu dotyczącym implementacji języka Python.

Jest to miara umożliwiająca znalezienie przestrzennego podobieństwa oznaczeń linii . Jest to podobny pomysł jak odległość Hausdorffa, odpowiednik miar podobieństwa wielokątów, ale dla linii z kierunkiem.

Odległość Frécheta definiuje się jako minimalną długość smyczy łączącej psa na jednej trajektorii z jego właścicielem na drugiej trajektorii, przy czym oba nigdy nie cofają się

Ta metryka będzie miała niewielką wartość dla dwóch krzywych, które są blisko położone, prawie równoległe, wyrównane w ten sam sposób i o podobnej długości.

To jednak nie odpowiada części identyfikującej klaster.

Tutaj jest kompleksowa prezentacja . Twoja sytuacja wygląda jak niektóre przypadki użycia wymienione w sekcjach 46-49

Ta metryka ma wiele zastosowań niegeosprzestrzennych, takich jak

• wykrywanie typowych wzorców w sekwencjonowaniu genów
• rozpoznawanie pisma odręcznego
• wykrywanie skorelowanych okresów w szeregach czasowych, takich jak historie cen akcji

więc chociaż wiele artykułów w bibliografii dotyczy tego tematu, większość z nich nie ma charakteru geoprzestrzennego. Również większość tych artykułów jest objęta algorytmiką / matematyką / informatyką, a nie geoprzestrzennością / naukami przyrodniczymi i są odpowiednio ukierunkowane.

Jednak ten dokument wyglądał obiecująco:

Buchin, K., Buchin, M., i Wang, Y. (2009). Dokładne algorytmy częściowego dopasowania krzywej za pomocą odległości Frécheta. W materiałach XX Sympozjum ACM-SIAM na temat algorytmów dyskretnych, strony 645–654

Niektóre inne artykuły brzmią bliżej tego, czego szukasz - identyfikacji klastra i przydzielania trajektorii do klastrów - ale są one zilustrowane przy użyciu danych szeregów czasowych lub innych niegeosprzestrzennych przykładów. Mogą one jednak wskazywać ciekawe kierunki.

Proponuję zastosować podejście podobne do wyjaśnionego tutaj .

ALGORYTM i nazewnictwo:

a) Nazwij warstwę linii NODES. Łożyska obliczeniowe

b) połączyć się przestrzennie ze sobą (jeden do wielu), stosując tolerancję odległości. Warstwa nazw LINKI

c) usuń z łączy LINKI do siebie, tj. NAZWA = NAZWA_1

d) wewnątrz LINKI znajdź „te same” pary kierunków. Użyłem:

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)

tzn. zakładane linie idące w przeciwnym kierunku są podobne pod względem kierunku

d) usuń niepowiązane (0) pary z LINKÓW.

e) oblicz grupy grup LINK połączone przez NODES i przenieś numery grup do tabeli NODES:

Niestety:

Jednak proste statystyki łożysk w grupie, np. Odchylenie standardowe:

abs(tan(bearing))

nie wykazał odchylenia w pierwszym przypadku i bardzo duży w drugim. Podobnie statystyki długości mogą pomóc w „równoległym bieganiu przez długi czas”.

Jeśli powyższe jest interesujące, mogę zaktualizować odpowiedź za pomocą skryptu, który oblicza połączone grupy łączy. Wykorzystuje moduł arcpy i networkx.

Nie wiem, jak traktować parę linii biegnących z tego samego punktu w przeciwnych kierunkach ...

Moim zdaniem istnieje problem z definicją linii, który określa, które podejścia należy zastosować (niektóre z wyżej wymienionych). Jeśli są to pary OD, a geometria nie odgrywa roli, podchodziłbym do tego w oparciu o klastrowanie sieci. Mówisz, że sieci nie tworzą sieci - niech tak będzie, ale prawdopodobne jest, że początki i miejsca docelowe mieszczą się w znaczących regionach, a zatem możesz traktować je jako sieć.

Jeśli geometria ma coś do powiedzenia (są to np. Trajektorie GPS i chcesz wziąć pod uwagę geometrię), musisz naprawdę pracować w przestrzeni (x, y, t) - podobna geometria śladu ruchu, ale w innym czasy nie mogą być ocenione tak samo - nie zostało to określone w pytaniu.

Niektóre możliwości, na które możesz spojrzeć:

1. Najbliżej Twojej potrzeby jest Dodge, Weibel, Forootan (2009), tutaj http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Jeśli geometrię można uprościć, być może wymienione tutaj parametry mogą być przydatne: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Ale na koniec, ponownie czytając pierwsze pytanie, może być prostsze: czy możesz obliczyć parami (między segmentami) odległość między przecięciem liniowego przedłużenia segmentów i ich najbliższych punktów, jakoś normalizować (być może na podstawie długości samego segmentu) i zastosować algorytm klastrowania macierzy? Uzasadnienie: segmenty, które przecinają się daleko, są bardziej podobne (równoległe) niż te, które przecinają się w pobliżu. Na rysunkach nie podano, jak traktować segmenty współliniowe lub równoległe, które są przesunięte (długa odległość frecheta). Zakładam, że spowodowałoby to kłopoty z powyższym rozwiązaniem. (zredagowane dla zachowania przejrzystości, poprzez wyraźne określenie „rozszerzenia liniowego” powyżej)

Uwaga (styczeń 2018 r.): Ostatnio natknąłem się na to:

1. Cai, Yuhan i Raymond Ng. „Indeksowanie trajektorii czasoprzestrzennych za pomocą wielomianów Czebeszewa”. Materiały z międzynarodowej konferencji ACM SIGMOD 2004 w sprawie zarządzania danymi. ACM, 2004.

Co odnosi się do podobieństwa trajektorii, a zatem umożliwiłoby do pewnego stopnia kwantyfikację podobieństwa. Jest to oparte na przybliżeniu wielomianowym krzywych i obliczeniu odległości Czebyszewa.

Czy możesz podać nieco więcej szczegółów na temat rodzaju danych, z którymi pracujesz? Czy to tylko seria rozłącznych linii, czy tworzą one sieć? Czy korzystałeś z któregokolwiek z narzędzi ArcGIS do analizy wzorów przestrzennych? Wiele metod ArcGIS (K Ripleya, indeks NN, Morans I) po prostu wykorzystuje środek ciężkości linii / wielokątów, gdy jest stosowany w danych niepunktowych. Jednak tutaj może być konieczne rozważenie podziału każdej linii na równe sekcje, aby uniknąć bardzo długich linii, ponieważ ich środek ciężkości jest bardzo daleko.

Inną rzeczą do przemyślenia jest koncepcyjnie, czym jest skupisko linii? Możesz mieć wiele linii rozpoczynających się blisko siebie, ale wtedy ich punkty końcowe mogą być rozproszone. Podobnie, możesz uzyskać wiele linii, które zaczynają się i kończą bardzo blisko siebie, ale potem stają się bardzo rozproszone między punktami początkowymi / końcowymi.

Jednym podejściem może być jednak po prostu wykonanie analizy gęstości linii, aby obszary z większą liczbą linii (które w pewnym sensie można uznać za skupione) będą miały wysokie wartości siatki, podczas gdy obszary o niskiej gęstości będą miały niskie wartości. Więc otrzymujesz trochę gorącego wyjścia; nie daje to jednak ani jednej statystyki, jak Morans I lub NNI. Nie rozróżnia również gęstości w wyniku jednej bardzo nieregularnej linii (tj. Ciasnej spirali) w porównaniu do wielu linii.

Niestety, nie jest to pełna odpowiedź na twój problem, ale myślę, że przybicie pełnej koncepcji tego, co próbujesz osiągnąć, może zapewnić lepsze rozwiązania.

AKTUALIZACJA

Na podstawie podanego przez ciebie przykładu uważam, że propozycja FelixlP, aby utworzyć punkt z atrybutem namiaru linii do użycia z miarami wzoru punktu, jest prawdopodobnie dobrym rozwiązaniem. Tyle że podzieliłbym punkty na równe segmenty i miałbym punkt z linią namiaru na każdym wierzchołku linii. Następnie musisz spojrzeć na miary, które będą analizować bliskość każdego punktu i podobieństwo między łożyskami (aby wykryć linie, które są bliższe prostopadłości).

Dlatego użycie Getis-Ord GI (analiza Hotspot) byłoby dobrym narzędziem do wizualizacji, gdzie znajdują się klastry; a następnie globalny I Morana, aby ocenić globalny poziom klastrowania.

Odległość, na której segmentujesz linie, będzie jednak wpływać na stopień znalezionego skupienia. Jeśli szukasz klastrów w skali 1 km, musisz segmentować linie wokół tego. Podobnie, jeśli szukasz klastrów w skali 100 m, musisz odpowiednio segmentować linie. Dzieje się tak, aby nie przegapić linii, a także aby nie wykryć każdej linii jako skupienia.

Dzięki za przykłady.

Nie widziałem żadnych ustalonych metod obliczania tego, czego szukasz, ale takie byłoby moje podejście. To rodzaj brutalnej siły.

Oblicz minimalny prostokąt ograniczający, a następnie rozwiń go dowolną, ale równą dużą ilość w każdym z czterech rogów.

Znajdź środek masy tworzonego prostokąta, oblicz rozkład azymutalny i odległości dla punktów OD dla każdej linii i zrób to samo, używając narożników prostokąta ograniczającego, porównując azymuty linii.

Przetestuj równoległość od każdego z czterech rogów do końca każdego promienia. Sprawdź równoległość od środka masy do końca każdego promienia.

W ten sposób możesz porównać odchylenie od narożników do końców. W przykładzie (a) miałbyś prawie równoległe linie od dwóch rogów do każdego z trzech klastrów linii. Miałbyś również prawie równoległe linie od środka masy do końców odległych końców linii.

Przykład (b) nie będziesz mieć prawie równoległych linii podczas obliczania od narożników do końców każdej linii, ale linie nie wydają się losowe, prowadzą do siebie z niewielkimi odchyleniami.

Przykład (c) wydaje się losowy

Przykład (d) nie jest przypadkowy, jest promieniowy.

Przyglądając się temu więcej, przeprowadziłbym testy, które opisałem powyżej, a także stworzyłem testy rozwiązania trójkąta od narożników utworzonego otaczającego prostokąta do końców promieni. Podobne kąty wewnętrzne i obszary pomogłyby zweryfikować grupowanie, chyba że jedna z linii w klastrze jest znacznie krótsza niż inne.

Powyższe jest tylko opinią jednego głupca i prawdopodobnie się mylę.

Po twoim instynktownym opisie, jakie jest kryterium równoległości dwóch linii?

Zasadniczo możesz wykonać test na punktach początkowych lub końcowych:
Niech Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2)
i Ex, Ey to samo, ale ich punkty końcowe.

Więc jeśli sqrt (Sx² + Sy²) AND sqrt (Ex² + Ey²) jest poniżej pewnego progu, możesz uznać te linie za równoległe.