Статистические тесты для пространственных линий?

Существует множество тестов для шаблонов пространственных точек, которые можно использовать для определения случайного распределения точек или нет, но существуют ли какие-либо проверенные тесты для шаблонов пространственных линий? (Я имею в виду прямые линии, только с начальной и конечной точкой и без промежуточных узлов.)

Данные, которые я хочу проанализировать, представляют собой OD (линии отправления-назначения) движения людей и животных. (Аналогично примеру в кластеризации неориентированных линий .)

До сих пор одной идеей было рассматривать линии как 4-мерные точки и использовать тесты точечных паттернов, но я не уверен, что это уместно.

Идеальный тест позволил бы определить, есть ли группы линий или нет.

Инстинктивно, я бы сказал, что многие строки, начинающиеся с одного и того же источника, но имеющие все виды различных назначений, не должны рассматриваться как кластер. С другой стороны, многие линии, которые проходят (близко к) параллельно в течение более длительного времени, будут кластером.

Это сложный вопрос, так как статистических данных о пространственных процессах, разработанных для линейных объектов, было немного. Без серьезного изучения уравнений и кода статистика точечных процессов не всегда применима к линейным объектам и, следовательно, статистически неверна. Это связано с тем, что значение null, с которым проверяется данный шаблон, основано на точечных событиях, а не на линейных зависимостях в случайном поле. Я должен сказать, что я даже не знаю, каким будет ноль, поскольку интенсивность и расположение / ориентация будет еще сложнее.

Я здесь просто плевок, но мне интересно, не будет ли многомерная оценка плотности линий в сочетании с евклидовым расстоянием (или расстоянием Хаусдорфа, если линии сложные) не будет указывать на непрерывную меру кластеризации. Затем эти данные можно суммировать с векторными линиями, используя дисперсию для учета несоответствия длин (Thomas 2011), и назначить значение кластера с использованием статистики, такой как K-средних. Я знаю, что вы не после назначенных кластеров, но значение кластера может разделить степени кластеризации. Это, очевидно, потребовало бы оптимального соответствия k, поэтому произвольные кластеры не назначаются. Я думаю, что это был бы интересный подход при оценке структуры ребер в теоретических моделях графа.

Вот проработанный пример на R, извините, но он быстрее и более воспроизводим, чем пример QGIS, и больше в моей зоне комфорта :)

Добавьте библиотеки и используйте медный объект psp из spatstat в качестве примера строки

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

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

Вычислить стандартизированную плотность линий 1-го и 2-го порядка, а затем привести к объектам класса растра

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

Стандартизировать плотность 1-го и 2-го порядка в масштабированную плотность

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

Рассчитать стандартизированное инвертированное евклидово расстояние и привести к классу растра

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

Принуждение spatstat psp к объекту sp SpatialLinesDataFrame для использования в 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)) )

Результаты участка

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) 

Извлечение растровых значений и вычисление сводной статистики, связанной с каждой строкой

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

Используйте значения силуэта кластера для оценки оптимального k (количества кластеров) с помощью функции optim.k, а затем присвойте значения кластера строкам. Затем мы можем назначить цвета для каждого кластера и нанести график поверх растра плотности.

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)

В этот момент можно выполнить рандомизацию линий, чтобы проверить, являются ли результирующая интенсивность и расстояние значимыми от случайных. Вы можете использовать функцию rshift.psp, чтобы случайным образом переориентировать ваши строки. Вы также можете просто рандомизировать начальную и конечную точки и воссоздать каждую строку.

Также возникает вопрос: «Что, если» вы только что выполнили точечный анализ с использованием однофакторной или перекрестной статистики анализа начальных и конечных точек, инвариантных линий. В одномерном анализе вы сравниваете результаты начальной и конечной точек, чтобы увидеть, есть ли согласованность в кластеризации между двумя точечными образцами. Это можно сделать с помощью f-hat, G-hat или Ripley's-K-hat (для немаркированных точечных процессов). Другим подходом может быть перекрестный анализ (например, перекрестный К), где два точечных процесса проверяются одновременно, помечая их как [начало, остановка]. Это будет указывать на отношения расстояний в процессе кластеризации между начальной и конечной точками. Тем не мение, пространственная зависимость (нестационарность) от лежащего в основе процесса интенсивности может быть проблемой в моделях такого типа, делая их неоднородными и требующими другой модели. По иронии судьбы, неоднородный процесс моделируется с использованием функции интенсивности, которая возвращает нас к плотности, тем самым поддерживая идею использования интегрированной по масштабу плотности в качестве меры кластеризации.

Вот быстрый пример использования статистики Ripleys K (Besags L) для автокорреляции процесса без опознавательных точек с использованием начальных и конечных положений класса линейных объектов. Последняя модель представляет собой кросс-к, использующий места начала и остановки в качестве номинально отмеченного процесса.

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

Ссылки

Thomas JCR (2011) Новый алгоритм кластеризации на основе K-средних с использованием линейного сегмента в качестве прототипа. В кн .: Сан Мартин С., Ким С.В. (eds) Прогресс в распознавании образов, анализе изображений, компьютерном зрении и приложениях. CIARP 2011. Конспект лекций в области компьютерных наук, том 7042. Springer, Берлин, Гейдельберг

Возможно, вы захотите посмотреть на расстояние Фреше . Я только недавно узнал об этом после недавнего вопроса, ищущего реализацию Python.

Это показатель для поиска пространственного сходства линий линий . Это похоже на расстояние Хаусдорфа, эквивалентное мерам подобия многоугольников, но для линейных линий с направлением.

Расстояние Фреше определяется как минимальная длина поводка, соединяющего собаку на одной траектории с ее владельцем на второй траектории, причем оба никогда не движутся назад

Эта метрика будет иметь небольшое значение для двух кривых, которые расположены близко, почти параллельно, выровнены одинаковым образом и имеют одинаковую длину.

Это не отвечает части идентификации кластера, хотя.

Здесь есть исчерпывающая презентация . Ваша ситуация звучит как некоторые из случаев использования, упомянутых в разделах 46-49

Эта метрика имеет много не геопространственных применений, таких как

• обнаружение общих подшаблонов в секвенировании генов
• распознавание почерка
• обнаружение коррелированных периодов во временных рядах, таких как истории цен на акции

поэтому, хотя многие статьи в библиографии охватывают эту тему, большинство из них не являются геопространственными. Кроме того, большинство из этих статей относятся к алгоритму / математике / информатике, а не к геопространственным / наукам о Земле и нацелены соответственно.

Однако эта статья выглядела многообещающе:

Бучин К., Бучин М. и Ван Ю. (2009). Точные алгоритмы для частичного сопоставления кривой через расстояние Фреше. В материалах 20-го симпозиума ACM-SIAM по дискретным алгоритмам, стр. 645–654

Некоторые из других работ звучат ближе к тому, что вам нужно - идентификации кластеров и распределению траекторий по кластерам - но они иллюстрируются с использованием данных временных рядов или других не геопространственных примеров. Однако они могут указывать на интересные направления.

Я предлагаю использовать подход, аналогичный описанному здесь .

АЛГОРИТМ и наименование:

а) Имя строки слоя NODES. Вычислить подшипники

б) пространственно присоединиться к себе (один ко многим), используя допуск на расстояние. Имя слоя ССЫЛКИ

c) удалить из LINKS присоединяется к себе, т.е. NAME = NAME_1

г) внутри ССЫЛКИ найти «одинаковые» пары направлений. Я использовал:

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)

то есть предполагаемые линии, идущие в противоположном направлении, являются одинаковыми с точки зрения направления

г) удалить не похожие (0) пары из ссылок.

e) вычислить группы ССЫЛК, подключенных через NODES, и перенести номера групп в таблицу NODES:

К несчастью:

Однако простая статистика подшипников внутри группы, например, стандартное отклонение:

abs(tan(bearing))

не показал отклонения в первом случае и очень большое во втором. Точно так же статистика длин может помочь с «параллельной работой в течение длительного времени».

Если выше представляет интерес, я могу обновить ответ с помощью скрипта, который вычисляет связанные группы ссылок. Используется модуль arcpy и networkx.

Не знаю, как относиться к паре линий, идущих из одной точки в разные стороны ...

На мой взгляд, есть проблема с определением линий, которая определит, какие подходы использовать (некоторые из упомянутых выше). Если это пары OD, а геометрия не играет роли, я бы подошел к этому на основе кластеризации сети. Вы говорите, что сети не образуют сеть - пусть будет так, но вполне вероятно, что источники и места назначения попадают в значимые регионы, и, таким образом, вы можете рассматривать это как сеть.

Если геометрии есть, что сказать (это, скажем, GPS-траектории, и вы хотите рассмотреть геометрию), то вам нужно будет по-настоящему работать в (x, y, t) пространстве - подобная геометрия следа движения, но на разных времена не могут быть оценены как одинаковые - это не указано в вопросе.

Некоторые возможности, на которые вы можете посмотреть:

1. Наиболее близким к вашим потребностям является Dodge, Weibel, Forootan (2009), здесь http://orca.cf.ac.uk/94865/1/PhysicsMovement.pdf
2. Если геометрия может быть упрощена, возможно, упомянутые здесь параметры могут быть полезны: http://www.tandfonline.com/doi/full/10.1080/17445647.2017.1313788

Но, наконец, перечитав еще раз ваш первоначальный вопрос, это может быть проще: можете ли вы попарно вычислить (между сегментами) расстояние между пересечением линейного продолжения сегментов и их ближайшими точками, как-то нормализовать (возможно, исходя из длины самого сегмента) и использовать матричный алгоритм кластеризации? Причина: сегменты, которые пересекаются далеко, более похожи (параллельны), чем сегменты, которые пересекаются близко На чертежах вы не говорите, как обрабатывать коллинеарные или параллельные сегменты, которые находятся в смещении (длинное расстояние frechet). Я предполагаю, что это вызовет проблемы с решением выше. (отредактировано для ясности, явно указав «линейное расширение» выше)

Примечание (январь 2018): я недавно наткнулся на это:

1. Cai, Yuhan и Raymond Ng. «Индексирование пространственно-временных траекторий полиномами Чебышева». Материалы международной конференции ACM SIGMOD 2004 года по управлению данными. ACM, 2004.

Что относится к траектории сходства и, таким образом, позволит в некоторой степени дать количественную оценку сходства. Это основано на полиномиальной аппроксимации кривых и вычислении чебышевского расстояния.

Можете ли вы дать немного больше информации о типе данных, с которыми вы работаете? Это просто ряд разрозненных линий или они образуют сеть? Использовали ли вы какие-либо инструменты ArcGIS для анализа пространственных образов? Многие из методов ArcGIS (Ripley's K, NN index, Morans I) просто используют центроид линий / многоугольников при использовании на неточечных данных. Однако здесь вам может понадобиться разбить каждую линию на равные участки, чтобы избежать того, что очень длинные линии не будут рассматриваться, поскольку их центроид очень далеко.

Другая вещь, о которой стоит подумать, это концептуально, что такое группа линий? У вас может быть много линий, расположенных близко друг к другу, но тогда их конечные точки могут быть рассеяны. Точно так же вы можете получить много линий, которые начинаются и заканчиваются очень близко друг к другу, но затем становятся очень рассредоточенными между их начальной / конечной точками.

Один из подходов, однако, может заключаться в том, чтобы просто выполнить анализ плотности линий, чтобы области с большим количеством линий (которые в некотором смысле можно считать кластеризованными) будут иметь высокие значения сетки, тогда как области с низкой плотностью будут иметь низкие значения. Таким образом, вы получаете немного горячей точки; однако это не дает вам ни единой статистики, как Моран I или NNI. Это также не будет дифференцировать плотность в результате одной очень нерегулярной линии (то есть жесткой спирали) против многих линий.

Извините, это не полный ответ на вашу проблему, но я думаю, что полное понимание того, что вы пытаетесь достичь, может дать некоторые лучшие решения.

ОБНОВИТЬ

Основываясь на приведенном вами примере, я думаю, что предложение FelixlP о создании точки с атрибутом линейного подшипника для использования с показателями точечного рисунка, вероятно, является хорошим способом. За исключением того, что я разделил бы точки на равные сегменты и имел бы точку с прямой линией в каждой вершине линии. Затем вам нужно посмотреть на меры, которые будут учитывать близость каждой точки и сходство между подшипниками (чтобы вы могли обнаружить линии, которые ближе к перпендикуляру).

Так что использование Getis-Ord GI (анализ горячих точек) было бы хорошим инструментом для визуализации кластеров; а затем глобальный Моран I для оценки глобального уровня кластеризации.

Однако расстояние, на котором вы сегментируете линии, будет влиять на степень найденной кластеризации. Если вы ищете кластеры в масштабе 1 км, вам нужно будет разделить линии вокруг этого. Точно так же, если вы ищете кластеры в масштабе 100 м, вам нужно будет сегментировать линии соответственно. Это делается для того, чтобы вы не пропускали линии, а также чтобы вы не определяли каждую линию как кластер.

Спасибо за примеры.

Я не видел каких-либо установленных методов для расчета того, что вы ищете, однако это мой подход. Это своего рода решение грубой силы.

Вычислите минимальный ограничивающий прямоугольник, затем растяните его произвольным, но равным большим количеством в каждом из четырех углов.

Найдите центр масс прямоугольника создания, рассчитайте азимутальное и дистанционное распределение для точек OD для каждой линии и сделайте то же самое, используя углы ограничивающего прямоугольника, а также сравните азимуты линий.

Проверьте параллельность от каждого из четырех углов до конца каждого луча. Проверьте параллельность от центра масс до конца каждого луча.

Делая это, вы можете сравнить отклонения от углов до концов. В примере (а) у вас будут почти параллельные линии от двух углов до каждого из трех линейных кластеров. Вы также должны иметь почти параллельные линии от центра масс до концов дальних концов линий.

В примере (б) у вас не будет почти параллельных линий при расчете от углов до концов каждой линии, но линии не кажутся случайными, они ведут друг к другу с небольшими отклонениями.

Пример (с) кажется случайным

Пример (d) не случайный, это радиальный.

Рассматривая это подробнее, я бы запустил тесты, которые я описал выше, а также создал тесты решения треугольника от углов созданного вмещающего прямоугольника до концов лучей. Подобные внутренние углы и области помогут проверить кластеризацию, если только одна из линий в кластере не будет значительно короче, чем другие.

Вышесказанное - только мнение одного дурака, и я, вероятно, ошибаюсь.

Следуя вашему инстинктивному описанию, каков критерий параллельности двух линий?

Вы можете сделать тест на начальную или конечную точки:
пусть Sx = (start_x_line_1 - start_x_line_2),
Sy = (start_y_line_1 - start_y_line_2),
и Ex, Ey одинаковы, но для их конечных точек.

Поэтому, если sqrt (Sx² + Sy²) AND sqrt (Ex² + Ey²) ниже определенного порога, вы можете считать эти линии параллельными.