Идентификация зараженных людей с помощью пересечения GPS-треков

Автор оригинала: Florian Nadler
  • Перевод
В преддверии старта курса «PostgreSQL» подготовили перевод интересной статьи.





Во времена пандемии COVID-19 правительства предусматривают жесткие меры по выявлению и отслеживанию инфицированных людей. Эти меры включают использование данных мобильных телефонов для отслеживания зараженных людей и их контактов с целью обуздать эпидемию. Эта статья рассказывает, как функции PostGIS можно использовать для выявления пересекающихся участков путей зараженных и здоровых людей посредством пространственно-временного анализа треков.

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

Структура статьи выглядит следующим образом:

  1. Настройка структур данных в PostgreSQL.
  2. Формирование выборки треков с помощью QGIS
  3. Сегментация выборки треков для извлечения отдельных точек.
  4. Нахождение пересечений зараженных и здоровых людей для определения возможных контактов.

Структуры данных


Начнем с определения таблиц, представляющих треки и их точки.

Таблица mobile_tracks является вспомогательной таблицей, хранящей смоделированные треки людей, которые были отобраны с помощью QGIS.

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

Тестовая зона находится в Вене/Австрия; поэтому я выбрал MGI/Austria 34 (EPSG равный 31286) в качестве подходящей проекции.

create table if not exists mobile_tracks
(
   gid serial not null
      constraint mobile_tracks_ok
         primary key,
   customer_id integer,
   geom geometry(LineString,31286),
   infected boolean default false
);
 
create index if not exists mobile_tracks_geom_idx
   on mobile_tracks using gist (geom);
 
create unique index if not exists mobile_tracks_customer_id_uindex
    on mobile_tracks (customer_id);
 
create table if not exists mobile_points
(
   gid serial not null
      constraint mobile_points_ok
         primary key,
   customer_id integer,
   geom geometry(Point,31286),
   infected boolean,
   recorded timestamp
);
 
create index if not exists mobile_points_geom_idx
   on mobile_points using gist (geom);

Треки и точки


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


Рисунок 1. GPS-треки здоровых и инфицированных людей.

Для нашего простого примера я сделал следующие допущения:

  • Все люди движутся с одинаковой скоростью.
  • Треки всех людей стартуют одновременно.

Для выделения отдельных точек для треков я использовал функцию PostGIS ST_Segmentize следующим образом:

with dumpedPoints as (
    select (st_dumppoints(st_segmentize(geom, 1))).geom,
           ((st_dumppoints(st_segmentize(geom, 1))).path[1]) as path,
           customer_id,
           infected,
           gid
    from mobile_tracks),
     aggreg as (
         select *, now() + interval '1 second' * row_number() over (partition by customer_id order by path) as tstamp
         from dumpedPoints)
insert
into mobile_points(geom, customer_id, infected, recorded)
select geom, customer_id, infected, tstamp
from aggreg;

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


Рисунок 2. Полученные GPS-точки.

Определение точек пересечения.


Теперь настало время начать анализ. Встречал ли наш инфицированный человек кого-нибудь?

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

SELECT distinct on (m1.gid) m1.customer_id infectionSourceCust,
                            m2.customer_id infectionTargetCust,
                            m1.gid,
                            m1.recorded,
                            m2.gid,
                            m2.recorded
FROM mobile_points m1
         inner join
     mobile_points m2 on st_dwithin(m1.geom, m2.geom, 2)
where m1.infected = true
  and m2.infected = false
  and m1.gid < m2.gid AND (m2.recorded >= m1.recorded - interval '1seconds' and
       m2.recorded <= m1.recorded + interval '1seconds')
order by m1.gid, st_dwithin(m1.geom, m2.geom, 2) asc

На 3 и 4 рисунках показаны результаты данного запроса, где точки контактов наших индивидов выделены синим цветом. Как упоминалось ранее, этот запрос представляет самое простое решение для идентификации людей, которые встречались.

В качестве альтернативы, здесь также могут использоваться функции PostGIS ST_CPAWithin и ST_ClosestPointOfApproach для решения этой проблемы аналогичным образом. Для этого наши точки должны быть смоделированы как траектории.


Рисунок 3. Точки контактов.


Рисунок 4. Точки контактов в увеличении.

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

Шаг 1 — aggregStep1


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


Рисунок 5. Временные промежутки между GPS-точками.

Шаг 2 — aggregStep2.


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

Шаг 3 — aggregStep3.


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


Рисунок 6. Когерентные сегменты + время совместного пути зараженного/здорового человека.

Шаг 4


Наконец, для каждой комбинации зараженного/здорового человека извлекается сегмент с максимальным временем совместного пути, и с помощью st_makeline генерируется lineString (см. Рисунок 7).


Рисунок 7. Максимальное время совместного пути зараженного/здорового человека.

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

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

with points as
         (
             SELECT distinct on (m1.gid) m1.customer_id infectionSourceCust,
 
                                         m2.customer_id infectionTargetCust,
                                         m1.gid,
                                         m1.geom,
                                         m1.recorded	m1rec,
                                         m2.gid,
                                         m2.recorded
             FROM mobile_points m1
                      inner join
                  mobile_points m2 on st_dwithin(m1.geom, m2.geom, 2)
             where m1.infected = true
               and m2.infected = false
               and m1.gid < m2.gid AND (m2.recorded >= m1.recorded - interval '1seconds' and
                    m2.recorded <= m1.recorded + interval '1seconds') order by m1.gid, m1.recorded), aggregStep1 as ( SELECT *, (m1rec - lag(m1rec, 1) OVER (partition by infectionSourceCust,infectionTargetCust ORDER by m1rec ASC)) as lag from points), aggregStep2 as (SELECT *, SUM(CASE WHEN extract('epoch' from lag) > 1 THEN 1 ELSE 0 END)
                 OVER (partition by infectionSourceCust,infectionTargetCust ORDER BY m1rec ASC) AS legSegment
          from aggregStep1),
     aggregStep3 as (
         select *,
                min(m1rec) OVER w   minRec,
                max(m1rec) OVER w   maxRec,
                (max(m1rec) over w) -
                (min(m1rec) OVER w) recDiff
         from aggregStep2
             window w as (partition by infectionSourceCust,infectionTargetCust,legSegment)
     )
select distinct on (infectionsourcecust, infectiontargetcust) infectionsourcecust,
                                                              infectiontargetcust,
                                                              (extract('epoch' from (recdiff))) passageTime,
                                                              st_makeline(geom) OVER (partition by infectionSourceCust,infectionTargetCust,legSegment)
from aggregStep3
order by infectionsourcecust, infectiontargetcust, passageTime desc



Успеть на курс.


OTUS. Онлайн-образование
Цифровые навыки от ведущих экспертов

Комментарии 4

    +3
    Какое-то двоякое чувство… С одной стороны интересные алгоритмы могут получаться. А с другой стороны программисты сами своими руками создают будущее цифровое рабство.
    Дальше будет хуже. Распознавание лиц на улицах в и публичных местах, обязательное отслеживание местоположения каждого… автоматические штрафы уже придуманы…
    Куда идем?
      –1

      Тут, мне кажется, как с атомной бомбой. Задержка технологического прогресса в целом и конкретных технологий в частности не решит проблем, которые этот прогресс и эти технологии потенциально могут породить. Скорее даже наоборот, усугубит. На этот счет есть много доводов: табуирование технологий провоцируют однобокое их развитие (те, кому очень нужны эти технологии, всё равно будут их разрабатывать и применять, а остальные будут в уязвлённом положении); чем раньше мы ворвёмся в технологическое будущее, тем больше у нас будет времени эффективно разрабатывать решения проблем, прежде чем мы убьём себя старыми технологиями.


      Идём вперёд. Не остаёмся в стороне. Не даём нечистым на руку органам и структурам без нашего разрешения оперировать нашими данными.
      Я понимаю, что это "ящик пандоры", но мы его приоткрыли ещё со времён первой идеи использовать палку, чтобы достать бананы. Теперь у нас нет выбора: нужно выбираться в космос и огребать проблемы поважнее и поинтереснее, чем тотальная слежка и реализация антиутопии на отдельно взятой планетке.

      0

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


      А ведь можно было бы сделать шажок в сторону практики и реальности, и всё бы заиграло куда более интересными красками.
      Итак, у вас есть "треки" без временной привязки. Вы на их основе сделали себе фейковые тестовые данные протрассировав во времени и пространстве. Окей, ничего не имею против.
      Записать пару реальных треков в городе не сложно, но сложнее, чем их сочинить. С другой стороны, нужно всего лишь попросить коллег прокатиться/пройтись домой/на работу с включенным трекером. Можно также взять треки маршрутов по городу с ресурсов вроде такого (первый нагуглившийся, но их много). Можно задвинуть их по датам в рамки одного или нескольких дней. Это даст вам реалистичные данные, а не такие, как у вас.


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


      Следующим этапом я бы порезал треки по таймаутам: если трек не писался пару десятков минут, то мы не можем что-то предполагать по поводу точной траектории агента.
      Я бы выделил непрерывные сегменты (далее "Сегменты") треков в отдельную таблицу, возможно зачем-то стоило бы сохранить и эти "пробелы" (далее "Разрывы"). Делается это с помощью оконных функций, например.


      Далее, чисто для оптимизации, разбил бы Сегменты на Чанки, выровненные по временнОй сетке, например, десятиминутной или часовой (подобрать эмпирически по соображениям эффективности индексации и джойна). Каждый такой Чанк получил бы у меня AA-BB границы, немного "раздутые" пропорционально максимальной скорости в рамках чанка. Это чтобы не потерять коллизии на концах из-за точности.


      Далее можно делать джойн таблицы Чанков на себя пересекая Чанки геометрически в рамках своего тайм-слота. Таким образом мы достаточно быстро и эффективно найдём все потенциальные коллизии. По-хорошему, конечно было бы обработать две серии чанков, чтобы вторая была сформирована со сдвигом на пол периода сетки. Но это уже детали.


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


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


      Альтернативой трассировки можно предложить решение системы параметрических уравнений: каждый промежуток между двумя точками траектории имеет трёхмерные координаты краёв (x, y, t). Определяем метрику в пространство-времени для оценки сближения этих отрезков и получаем некий пространственно-временной эллипсоид контакта. Именно этот эллипсоид получит дознаватель для перекрёстного допроса нарушителей карантина=).


      Ещё совершенно напрасно не рассмотрены важные корреляции, которые можно отследить по трекам:


      1. признаки перемещения агентов в одном транспортном средстве: можно потом найти на дорожных камерах наблюдения ТС и записать в Контактные его водителя;
      2. признаки пребывания в одном помещении: если в точке длительного пребывания агентов мало иных мест возможного длительного пребывания за исключением кафе, заправки или других POI, следует добавить в Контакт это POI и запросить записи с релевантных камер наблюдения.

      UPD:
      Забыл добавить про Разрывы. Их тоже следует добавлять в отчет, чтобы дознаватель мог отдельно опросить агентов об их перемещениях в этих промежутках. Иначе эти временные интервалы могли остаться забытыми, а между тем COVID-положительный и опасный человек мог ехать несколько перегонов в метро и заражать всех подряд в вагоне.

        0
        Интересно кто и как в реальном мире и стране не называющейся Китай добудет закрытую медицинскую информацию о диагнозе человека по которому писался трек?

        Кто понесёт административную и уголовную ответственность за последствия недостоверного предупреждения о заражении? Допустим какому-то чувствительному человеку придёт письмо о его возможном заражении и это приведёт к печальным последствиям.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое