Bilden von Gruppen von räumlich-zeitlich nahen Trajektorien in R oder PostgreSQL

Question

Ich mache eine Trajektorienanalyse mit R und PostgreSQL. Um Gruppen von Trajektoriensegmenten zu bilden, in denen aufeinanderfolgende Positionen räumlich-zeitlich nahe sind, habe ich die folgende Tabelle erstellt. Was mir noch fehlt ist die Spalte group_id, worum geht es in meiner Frage.

bike_id1 datetime    bike_id2 near  group_id 
     1 2016-05-28 11:00:00   2 TRUE   1 
     1 2016-05-28 11:00:05   2 TRUE   1 
     1 2016-05-28 11:00:10   2 FALSE   NA 
[...] 
     2 2016-05-28 11:00:05   3 TRUE   1 
     2 2016-05-28 11:00:10   3 TRUE   1 

Dies ist das Ergebnis von Mehrfachvergleiche zwischen jeder Trajektorie mit jedem anderen (alle Kombinationen ohne Wiederholungen) und eine innere Verknüpfung auf datetime (immer auf ein Vielfaches von 5 Sekunden abgetastet). Es zeigt, dass für bestimmte Positionen Fahrrad 1 und 2 gleichzeitig abgetastet wurden und räumlich nahe beieinander liegen (eine beliebige Schwelle).

Jetzt möchte ich einzigartige IDs für die Segmente geben, wo zwei Fahrräder räumlich-zeitlich nahe sind (group_id). Hier stecke ich fest: Ich möchte die group_id Gruppen mit mehreren Trajektorien zu respektieren. Die Methode zum Zuweisen der group_id sollte erkennen, dass, wenn Fahrrad 1 und 2 in einer Gruppe unter 2016-05-28 11:00:05 sind, dann 3 zu der gleichen Gruppe gehört, wenn es in der Nähe von 2 bei demselben Zeitstempel ist (2016-05-28 11:00:05).

Gibt es Tools in R oder PostgreSQL, die mir bei dieser Aufgabe helfen würden? Eine Schleife durch den Tisch zu führen, scheint der falsche Weg zu sein.

EDIT: Wie @wildplasser darauf hingewiesen, dies scheint ein Lücke-und-Inseln Problem zu sein, die traditionell unter Verwendung von SQL gelöst. Er hat freundlicherweise einige Beispieldaten erstellt, die ich etwas erweitert habe und in die Frage einbeziehen werde.

CREATE TABLE nearness 
     -- (seq SERIAL NOT NULL UNIQUE -- surrogate for conveniance 
     (bike1 INTEGER NOT NULL 
     , bike2 INTEGER NOT NULL 
     , stamp timestamp NOT NULL 
     , near boolean 
     , PRIMARY KEY(bike1,bike2,stamp) 
     ); 
INSERT INTO nearness(bike1,bike2,stamp,near) VALUES 
(1,2, '2016-05-28 11:00:00', TRUE) 
,(1,2, '2016-05-28 11:00:05', TRUE) 
,(1,2, '2016-05-28 11:00:10', TRUE) 
,(1,2, '2016-05-28 11:00:20', TRUE) -- <<-- gap here 
,(1,2, '2016-05-28 11:00:25', TRUE) 
,(1,2, '2016-05-28 11:00:30', FALSE) 
,(4,5, '2016-05-28 11:00:00', FALSE) 
,(4,5, '2016-05-28 11:00:05', FALSE) 
,(4,5, '2016-05-28 11:00:10', TRUE) 
,(4,5, '2016-05-28 11:00:15', TRUE) 
,(4,5, '2016-05-28 11:00:20', TRUE) 
,(2,3, '2016-05-28 11:00:05', TRUE) -- <<-- bike 1, 2, 3 are in one grp @ 11:00:05 
,(2,3, '2016-05-28 11:00:10', TRUE) -- <<-- no group here 
,(6,7, '2016-05-28 11:00:00', FALSE) 
,(6,7, '2016-05-28 11:00:05', FALSE) 
     ; 

Answer 1

UPDATE: [nach der eigentlichen Frage zu verstehen; -], um die Gleichwertigkeit Gruppen von Fahrrädern zu finden (gesetzt, bike_set) ist in der Tat ein relationalen Teilungs Problem. Das Finden von Anfang und Ende der Segmente (Clust) innerhalb einer Reihe von Fahrrädern ist im Grunde das gleiche wie im ersten Versuch.

• Die Cluster werden in Arrays gespeichert: (I auf den Clustern Vertrauen nicht zu groß wird)
• Das Array durch eine rekursive Abfrage aufgebaut ist: jedes Paar von Fahrrädern, die mit dem aktuellen Cluster gemeinsam ein Mitglied haben ist darin verschmolzen.
• Am Ende enthalten die Arrays alle bike_id's, die gerade zu diesem Zeitpunkt erreichbar waren.
• (plus einige Zwischenzeilen, die später durch die uniq CTE unterdrückt werden müssen)
• Der Rest ist mehr oder weniger Standardlückenerkennung in Zeitreihen.

HINWEIS: Der Code vertraut auf (bike2 > bike1). Dies wird benötigt, um das Array sortiert und somit kanonisch zu halten. Der tatsächliche Inhalt ist nicht garantiert kanonisch, da die Reihenfolge der Addition in der rekursiven Abfrage nicht garantiert werden kann. Dies kann etwas zusätzliche Arbeit erfordern.

---

CREATE TABLE nearness 
     (bike1 INTEGER NOT NULL 
     , bike2 INTEGER NOT NULL 
     , stamp timestamp NOT NULL 
     , near boolean 
     , PRIMARY KEY(bike1,bike2,stamp) 
     ); 
INSERT INTO nearness(bike1,bike2,stamp,near) VALUES 
(1,2, '2016-05-28 11:00:00', TRUE) 
,(1,2, '2016-05-28 11:00:05', TRUE) 
,(1,2, '2016-05-28 11:00:10', TRUE) 
,(1,2, '2016-05-28 11:00:20', TRUE) -- <<-- gap here 
,(1,2, '2016-05-28 11:00:25', TRUE) 
,(1,2, '2016-05-28 11:00:30', FALSE) -- <<-- these False-records serve no pupose 
,(4,5, '2016-05-28 11:00:00', FALSE) -- <<-- result would be the same without them 
,(4,5, '2016-05-28 11:00:05', FALSE) 
,(4,5, '2016-05-28 11:00:10', TRUE) 
,(4,5, '2016-05-28 11:00:15', TRUE) 
,(4,5, '2016-05-28 11:00:20', TRUE) 
,(2,3, '2016-05-28 11:00:05', TRUE) -- <<-- bike 1, 2, 3 are in one grp @ 11:00:05 
,(2,3, '2016-05-28 11:00:10', TRUE) -- <<-- no group here 
,(6,7, '2016-05-28 11:00:00', FALSE) 
,(6,7, '2016-05-28 11:00:05', FALSE) 
     ; 


     -- Recursive union-find to glue together sets of bike_ids 
     -- ,occuring at the same moment. 
     -- Sets are represented as {ordered,unique} arrays here 
WITH RECURSIVE wood AS (
     WITH omg AS (
       SELECT bike1 ,bike2,stamp 
       , row_number() OVER(ORDER BY bike1,bike2,stamp) AS seq 
       , ARRAY[bike1,bike2]::integer[] AS arr 
       FROM nearness n WHERE near = True 
       ) 
     -- Find all existing combinations of bikes 
     SELECT o1.stamp, o1.seq 
       , ARRAY[o1.bike1,o1.bike2]::integer[] AS arr 
     FROM omg o1 
     UNION ALL 
     SELECT o2.stamp, o2.seq -- avoid duplicates inside the array 
       , CASE when o2.bike1 = ANY(w.arr) THEN w.arr || o2.bike2 
       ELSE w.arr || o2.bike1 END AS arr 
     FROM omg o2 
     JOIN wood w 
       ON o2.stamp = w.stamp AND o2.seq > w.seq 
       AND (o2.bike1 = ANY(w.arr) OR o2.bike2 = ANY(w.arr)) 
       AND NOT (o2.bike1 = ANY(w.arr) AND o2.bike2 = ANY(w.arr)) 
     ) 
, uniq AS ( -- suppress partial sets caused by the recursive union-find buildup 
     SELECT * FROM wood w 
     WHERE NOT EXISTS (SELECT * FROM wood nx 
       WHERE nx.stamp = w.stamp 
       AND nx.arr @> w.arr AND nx.arr <> w.arr -- contains but not equal 
       ) 
     ) 
, xsets AS ( -- make unique sets of bikes 
     SELECT DISTINCT arr 
     -- , MIN(seq) AS grp 
     FROM uniq 
     GROUP BY arr 
     ) 
, sets AS ( -- enumerate the sets of bikes 
     SELECT arr 
     , row_number() OVER() AS setnum 
     FROM xsets 
     ) 
, drag AS (   -- Detect beginning and end of segments of consecutive observations 
     SELECT u.*  -- within a constant set of bike_ids 
     -- Edge-detection begin of group 
     , NOT EXISTS (SELECT * FROM uniq nx 
       WHERE nx.arr = u.arr 
       AND nx.stamp < u.stamp 
       AND nx.stamp >= u.stamp - '5 sec'::interval 
       ) AS is_first 
     -- Edge-detection end of group 
     , NOT EXISTS (SELECT * FROM uniq nx 
       WHERE nx.arr = u.arr 
       AND nx.stamp > u.stamp 
       AND nx.stamp <= u.stamp + '5 sec'::interval 
       ) AS is_last 
     , row_number() OVER(ORDER BY arr,stamp) AS nseq 
     FROM uniq u 
     ) 
, top AS (-- id and groupnum for the start of a group 
     SELECT nseq 
     , row_number() OVER() AS clust 
     FROM drag 
     WHERE is_first 
     ) 
, bot AS (-- id and groupnum for the end of a group 
     SELECT nseq 
     , row_number() OVER() AS clust 
     FROM drag 
     WHERE is_last 
     ) 
SELECT w.seq as orgseq -- results, please ... 
     , w.stamp 
     , g0.clust AS clust 
     , row_number() OVER(www) AS rn 
     , s.setnum, s.arr AS bike_set 
     FROM drag w 
     JOIN sets s ON s.arr = w.arr 
     JOIN top g0 ON g0.nseq <= w.seq 
     JOIN bot g1 ON g1.nseq >= w.seq AND g1.clust = g0.clust 
     WINDOW www AS (PARTITION BY g1.clust ORDER BY w.stamp) 
     ORDER BY g1.clust, w.stamp 
     ; 

---

Ergebnis:

---

orgseq |  stamp  | clust | rn | setnum | bike_set 
--------+---------------------+-------+----+--------+---------- 
     1 | 2016-05-28 11:00:00 |  1 | 1 |  1 | {1,2} 
     4 | 2016-05-28 11:00:20 |  3 | 1 |  1 | {1,2} 
     5 | 2016-05-28 11:00:25 |  3 | 2 |  1 | {1,2} 
     6 | 2016-05-28 11:00:05 |  4 | 1 |  3 | {1,2,3} 
     7 | 2016-05-28 11:00:10 |  4 | 2 |  3 | {1,2,3} 
     8 | 2016-05-28 11:00:10 |  4 | 3 |  2 | {4,5} 
(6 rows)