4

R と PostgreSQL を使用して軌跡分析を行っています。連続する位置が時空間的に近い軌道セグメントのグループを形成するために、次の表を作成しました。私がまだ欠けているのは、group_id私の質問の内容である column です。

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

これは、各軌跡と他のすべての軌跡 (繰り返しのないすべての組み合わせ) と内部結合datetime(常に 5 秒の倍数でサンプリング) との間の複数の比較の結果です。特定の位置で、バイク 1 と 2 が同時にサンプリングされ、空間的に近い (何らかの任意のしきい値) ことを示しています。

ここで、2 台の自転車が時空間的に近いセグメントに一意の ID を割り当てたいと思います ( group_id)。これは私が立ち往生している場所ですgroup_id:複数の軌道を持つグループを尊重したいと思います。を割り当てるメソッドではgroup_id、自転車 1 と 2 が のグループに2016-05-28 11:00:05属している場合、同じタイムスタンプ ( ) で自転車が 2 に近い場合、3 は同じグループに属していることを認識する必要があり2016-05-28 11:00:05ます。

このタスクに役立つ R または PostgreSQL 内のツールはありますか? テーブルでループを実行するのは、これを行うには間違った方法のようです。

編集: @wildplasser が指摘したように、これは伝統的に SQL を使用して解決されるギャップと島の問題のようです。彼は、私が少し拡張したいくつかのサンプルデータを親切に作成し、質問に含めます.

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

1 に答える 1

1

更新: [本当の質問を理解した後 ;-] 自転車の等価グループ ( set、bike_set ) を見つけることは、実際には関係分割の問題です。バイクのセット内のセグメント ( clust ) の開始と終了を見つけることは、基本的に最初の試行と同じです。

  • クラスターは配列に格納されます: (クラスターが大きくなりすぎないことを信頼しています)
  • 配列は再帰クエリによって構築されます。現在のクラスターと共通のメンバーを 1 つ持つ自転車のすべてのペアが、そのクラスターにマージされます。
  • 最後に、配列には、特定の時間にたまたま手の届く範囲にあったすべての bike_id が含まれています。
  • (さらに、後でuniqCTE によって抑制する必要があるいくつかの中間行)
  • 残りは、時系列で多かれ少なかれ標準的なギャップ検出です。

注: コードは を信頼してい(bike2 > bike1)ます。これは、配列をソートして正規化するために必要です。再帰クエリでの追加の順序を保証できないため、実際のコンテンツが正規のものであるとは限りません。これには追加の作業が必要になる場合があります。

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
        ;

結果：

 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)
于 2016-05-28T16:22:04.977 に答える