Testes estatísticos para padrões de linhas espaciais?

Existem muitos testes para padrões de pontos espaciais que podem ser usados ​​para determinar se os pontos são distribuídos aleatoriamente ou não, mas existem testes estabelecidos para padrões de linhas espaciais? (Estou pensando em linhas retas, com apenas ponto inicial e final e sem nós intermediários.)

Os dados que eu quero analisar são linhas OD (destino de origem) de movimento humano e animal. (Semelhante ao exemplo no clustering não dirigida linhas ).

Até agora, uma idéia era tratar linhas como pontos 4D e usar testes de padrão de pontos, mas não tenho certeza se isso é apropriado.

O teste ideal tornaria possível determinar se existem grupos de linhas ou não.

Instintivamente, eu diria que muitas linhas que começam na mesma origem, mas têm todos os tipos de destinos diferentes, não devem ser consideradas um cluster. Por outro lado, muitas linhas que correm (próximas a) paralelamente por mais tempo seriam um cluster.

Essa é uma pergunta difícil, pois simplesmente não existem muitas estatísticas de processo espacial, se houver alguma, desenvolvidas para recursos de linha. Sem investigar seriamente as equações e o código, as estatísticas do processo pontual não são prontamente aplicáveis ​​a recursos lineares e, portanto, estatisticamente inválidas. Isso ocorre porque o nulo, contra o qual um determinado padrão é testado, é baseado em eventos pontuais e não em dependências lineares no campo aleatório. Devo dizer que nem sei qual seria o nulo na medida em que intensidade e arranjo / orientação seriam ainda mais difíceis.

Estou apenas cuspindo aqui, mas estou imaginando se uma avaliação em escala múltipla da densidade da linha acoplada à distância euclidiana (ou distância de Hausdorff se as linhas forem complexas) não indicaria uma medida contínua de agrupamento. Esses dados podem então ser resumidos aos vetores de linha, usando a variação para explicar a disparidade nos comprimentos (Thomas 2011), e atribuídos um valor de cluster usando uma estatística como K-means. Eu sei que você não está atrás de clusters atribuídos, mas o valor do cluster pode particionar graus de cluster. Obviamente, isso exigiria um ajuste ideal de k, portanto, clusters arbitrários não são atribuídos. Estou pensando que essa seria uma abordagem interessante na avaliação da estrutura de arestas em modelos teóricos de gráficos.

Aqui está um exemplo trabalhado em R, desculpe, mas é mais rápido e mais reproduzível do que fornecer um exemplo QGIS, e está mais na minha zona de conforto :)

Adicione bibliotecas e use o objeto psp de cobre do spatstat como exemplo de linha

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

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

Calcular a densidade de linha padronizada de 1ª e 2ª ordem e coagir a objetos de classe raster

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

Padronize a densidade de 1ª e 2ª ordem em uma densidade integrada na balança

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

Calcular a distância euclidiana invertida padronizada e coagir à classe raster

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

Coerce o spatstat psp para um objeto SpatialLinesDataFrame para usar no 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 do 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) 

Extraia valores de varredura e calcule estatísticas resumidas associadas a cada linha

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 silhueta de cluster para avaliar k ideal (número de clusters), com a função ideal.k, depois atribua valores de cluster a linhas. Podemos então atribuir cores a cada cluster e plotar em cima da varredura de densidade.

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)

Nesse ponto, pode-se realizar uma randomização das linhas para testar se a intensidade e a distância resultantes são significativas em relação ao aleatório. Você pode usar a função "rshift.psp" para reorientar suas linhas aleatoriamente. Você também pode randomizar os pontos de início e parada e recriar cada linha.

Também se pergunta "e se" você acabou de executar uma análise de padrão de pontos usando uma estatística de análise cruzada ou univariada nos pontos de partida e parada, invariáveis ​​nas linhas. Em uma análise univariada, você compararia os resultados dos pontos inicial e final para verificar se há consistência no agrupamento entre os dois padrões de pontos. Isso pode ser feito via f-hat, G-hat ou Ripley's-K-hat (para processos pontuais não marcados). Outra abordagem seria uma análise cruzada (por exemplo, cross-K), na qual os dois processos pontuais são testados simultaneamente, marcando-os como [iniciar, parar]. Isso indicaria as relações de distância no processo de armazenamento em cluster entre os pontos de partida e parada. Contudo, a dependência espacial (não estacionalidade) de um processo de intensidade subjacente pode ser um problema nesses tipos de modelos, tornando-os não homogêneos e exigindo um modelo diferente. Ironicamente, o processo não homogêneo é modelado usando uma função de intensidade que nos leva a um círculo completo de volta à densidade, apoiando a idéia de usar uma densidade integrada na balança como uma medida de agrupamento.

Aqui está um exemplo rápido de se a estatística Ripleys K (Besags L) para autocorrelação de um processo de ponto não marcado usando o início, para locais de uma classe de recurso de linha. O último modelo é um cruzamento usando os locais de partida e parada como um processo 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) ) )

Referências

Thomas JCR (2011) Um novo algoritmo de agrupamento baseado em meios K usando um segmento de linha como protótipo. In: San Martin C., Kim SW. (eds) Progresso no reconhecimento de padrões, análise de imagens, visão computacional e aplicativos. CIARP 2011. Notas de aula em Ciência da Computação, vol 7042. Springer, Berlim, Heidelberg

Você pode procurar a distância de Fréchet . Só descobri recentemente isso depois de uma pergunta recente procurando uma implementação em python.

Essa é uma métrica para encontrar semelhança espacial de cadeias de linhas . É uma idéia semelhante à distância de Hausdorff, o equivalente a medidas de similaridade de polígono, mas para cadeias de linhas com uma direção.

A distância Fréchet é definida como o comprimento mínimo de uma trela que conecta um cachorro em uma trajetória ao dono em uma segunda trajetória, ambos nunca se movendo para trás

Essa métrica terá um valor pequeno para duas curvas que estão próximas, quase paralelas, alinhadas da mesma maneira e com um comprimento semelhante.

Isso não responde à parte de identificação do cluster.

Há uma apresentação abrangente aqui . Sua situação parece alguns dos casos de uso mencionados nas seções 46-49

Essa métrica possui muitos usos não geoespaciais, como

• detecção de sub-padrões comuns no sequenciamento de genes
• reconhecimento de caligrafia
• detectar períodos correlatos em séries temporais, como histórico de preços das ações

portanto, embora muitos trabalhos na bibliografia cubram esse tópico, a maioria deles não é geoespacial. Além disso, a maioria desses artigos se enquadra em algoritmos / matemática / ciência da computação em vez de geoespacial / geociências e são direcionados de acordo.

No entanto, este documento parecia promissor:

Buchin, K., Buchin, M. e Wang, Y. (2009). Algoritmos exatos para correspondência parcial de curvas através da distância de Fréchet. Em Anais do 20º Simpósio ACM-SIAM sobre Algoritmos Discretos, páginas 645–654

Alguns dos outros documentos parecem mais próximos do que você procura - identificação de cluster e alocação de trajetórias para clusters - mas são ilustrados usando dados de séries temporais ou outros exemplos não geoespaciais. No entanto, eles podem apontar em direções interessantes.

Estou sugerindo usar uma abordagem semelhante à explicada aqui .

ALGORITMO e nomeação:

a) Nome da camada de linha NODES. Computar rolamentos

b) juntar-se espacialmente a si próprio (um a muitos) usando tolerância à distância. Camada de nome LINKS

c) remover do LINKS se une a si mesmo, ou seja, NAME = NAME_1

d) dentro do LINKS encontre pares de direção "mesmos". Eu usei:

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)

ou seja, linhas assumidas indo na direção oposta sendo semelhantes em termos de direção

d) remova pares não semelhantes (0) do LINKS.

e) calcular grupos de LINKS conectados através do NODES e transferir números de grupos para a tabela NODES:

Infelizmente:

No entanto, estatísticas simples de rolamentos dentro do grupo, por exemplo, desvio padrão de:

abs(tan(bearing))

não mostrou desvio no primeiro caso e muito grande no segundo. Da mesma forma, estatísticas de comprimentos podem ajudar a "correr em paralelo por um longo tempo".

Se acima for de interesse, posso atualizar a resposta com o script que calcula grupos de links conectados. Ele está usando o módulo arcpy e networkx.

Não sei como tratar um par de linhas que vão do mesmo ponto em direções opostas ...

Há aos meus olhos um problema com a definição das linhas, uma que determinará quais abordagens usar (algumas das mencionadas acima). Se esses pares são OD, e a geometria não desempenha um papel, eu abordaria isso com base no cluster de rede. Você diz que as redes não formam uma rede - assim seja, mas é provável que as origens e destinos caiam em regiões significativas e, portanto, você pode tratá-lo como uma rede.

Se a geometria tem algo a dizer (digamos, trajetórias de GPS e você deseja considerar a geometria), será necessário realmente trabalhar em um espaço (x, y, t) - geometria semelhante da pegada de movimento, mas em diferentes os horários podem não ser avaliados da mesma forma - isso não está especificado na pergunta.

Algumas possibilidades que você pode olhar:

1. O mais próximo de sua necessidade é Dodge, Weibel, Forootan (2009), aqui http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Se a geometria puder ser simplificada, talvez os parâmetros mencionados aqui possam ser úteis: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Mas, finalmente, relendo novamente sua pergunta inicial, poderia ser mais simples: você pode calcular em pares (entre segmentos) a distância entre a interseção da extensão linear dos segmentos e seus pontos mais próximos, normalizar de alguma forma (talvez com base no comprimento do próprio segmento) e usa um algoritmo de agrupamento de matrizes? Raciocínio: os segmentos que se cruzam muito são mais semelhantes (paralelos) do que os que se cruzam por perto. Nos desenhos, você não diz como tratar segmentos co-lineares ou paralelos que estão em um deslocamento (long frechet dist). Suponho que isso daria problemas à solução acima. (editado para maior clareza, declarando explicitamente "extensão linear" acima)

Nota (janeiro de 2018): Eu recentemente deparei com isso:

1. Cai, Yuhan e Raymond Ng. "Indexando trajetórias espaço-temporais com polinômios de Chebyshev." Anais da conferência internacional ACM SIGMOD de 2004 sobre Gerenciamento de dados. ACM, 2004.

O que se relaciona com a similaridade da trajetória e, portanto, permitiria a quantificação da similaridade até certo ponto. Isso é baseado na aproximação polinomial de curvas e no cálculo da distância de Chebyshev.

Você pode dar um pouco mais de detalhes sobre o tipo de dados com os quais está trabalhando? São apenas uma série de linhas disjuntas ou formam uma rede? Você já usou alguma das ferramentas do ArcGIS para análise de padrões espaciais? Muitos dos métodos do ArcGIS (índice K, NN de Ripley, Morans I) apenas usam o centróide das linhas / polígonos quando usados ​​em dados não pontuais. No entanto, aqui você pode precisar dividir cada linha em seções iguais para evitar que linhas muito longas não sejam consideradas devido ao fato de o centróide estar muito distante.

A outra coisa a se pensar é, conceitualmente, o que é um cluster de linhas? Você pode ter muitas linhas originárias próximas umas das outras, mas seus pontos finais podem ser dispersos. Da mesma forma, você pode obter muitas linhas que começam e terminam muito próximas umas das outras, mas depois ficam muito dispersas entre os pontos de início / fim.

Uma abordagem, no entanto, poderia ser simplesmente realizar uma análise de densidade de linha para que áreas com mais linhas (que poderiam ser consideradas agrupadas em algum sentido) tenham altos valores de grade, enquanto áreas com baixa densidade terão valores baixos. Então você obtém um pouco de saída de hot-spot; no entanto, isso não fornece uma estatística única como Morans I ou o NNI. Também não diferencia a densidade como resultado de uma linha muito irregular (isto é, uma espiral fechada) versus muitas linhas.

Desculpe, essa não é uma resposta completa para o seu problema, mas acho que a fixação do conceito completo do que você está tentando alcançar pode fornecer algumas soluções melhores.

ATUALIZAR

Com base no exemplo que você deu, acho que a sugestão de FelixlP de criar um ponto com atributo de linha para usar com medidas de padrão de pontos é provavelmente um bom caminho a percorrer. Exceto que eu dividiria os pontos em segmentos iguais e teria um ponto com a linha em cada vértice da linha. Em seguida, é necessário observar as medidas que examinarão a proximidade de cada ponto e a semelhança entre os rolamentos (para detectar linhas mais próximas da perpendicular).

Portanto, usar o Getis-Ord GI (análise de hotspot) seria uma boa ferramenta para visualizar onde estão os clusters; e então um I de Moran global para avaliar o nível global de agrupamento.

A distância na qual você segmenta as linhas, no entanto, afeta o grau de agrupamento encontrado. Se você estiver procurando clusters na escala de 1 km, será necessário segmentar as linhas para isso. Da mesma forma, se você estiver procurando por clusters na escala de 100m, precisará segmentar as linhas de acordo. Isso é para que você não perca as linhas e também para não detectar cada linha como um cluster.

Obrigado pelos exemplos.

Eu não vi nenhum método estabelecido para calcular o que você está procurando, no entanto, essa seria a minha abordagem. É uma espécie de solução de força bruta.

Calcule um retângulo delimitador mínimo e expanda-o de forma arbitrária, mas igual a uma quantidade grande em cada um dos quatro cantos.

Encontre o centro de massa do retângulo de criação, calcule a distribuição azimutal e de distância para os pontos OD de cada linha e faça o mesmo usando os cantos do seu retângulo delimitador, além de comparar os azimutes das linhas.

Teste o paralelismo de cada um dos quatro cantos até o final de cada raio. Teste o paralelismo do centro de massa até o final de cada raio.

Ao fazer isso, você pode comparar o desvio dos cantos até as extremidades. No exemplo (a), você teria linhas paralelas próximas de dois dos cantos a cada um dos três grupos de linhas. Você também teria linhas paralelas próximas do centro de massa até as extremidades das extremidades distantes das linhas.

Exemplo (b) você não teria linhas paralelas próximas ao calcular a partir dos cantos até o final de cada linha, mas as linhas não parecem aleatórias, elas levam uma à outra com pequenos desvios.

O exemplo (c) parece ser aleatório

O exemplo (d) não é aleatório, é radial.

Examinando isso mais, eu executaria os testes que descrevi acima, além de criar testes de solução triangular a partir dos cantos do retângulo anexo criado até as extremidades dos raios. Ângulos interiores e áreas semelhantes ajudariam a verificar o agrupamento, a menos que uma das linhas no agrupamento seja significativamente menor que as outras.

O exposto acima é apenas a opinião de um tolo, e provavelmente estou errado.

Seguindo sua descrição instintiva, qual é o critério para duas linhas serem paralelas?

Basicamente, você pode fazer um teste sobre os pontos de partida ou de destino:
Seja Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2)
e Ex, Ey, o mesmo, exceto os pontos finais.

Portanto, se sqrt (Sx² + Sy²) E sqrt (Ex² + Ey²) estiver abaixo de um certo limite, você pode considerar essas linhas como paralelas.