在R或PostgreSQL中形成时空相近轨迹的组

Question

在R或PostgreSQL中形成时空相近轨迹的组

rpostgresqlgaps-and-islandsrelational-divisiongaps-in-data

4

我正在使用R和PostgreSQL进行一些轨迹分析。为了形成轨迹段的群组，其中连续位置在时空上靠近，我创建了以下表格。我还缺少的是group_id列，这就是我的问题所在。

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同时被采样且空间接近（某些任意阈值）。

现在，我想为两辆自行车在时空上接近的段落分配唯一的id (group_id)。这是我的难点：我希望group_id尊重具有多个轨迹的组。分配group_id的方法应该意识到，如果自行车1和2在2016-05-28 11:00:05的一个组中，则3属于同一组，如果它在同一时间戳(2016-05-28 11:00:05)附近与2接近。

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

- Ratnanil

你需要检测间隙，因此你首先必须定义什么是间隙。之后你可以列举非间隙。 - wildplasser

你的意思是使用类似于这种方法中的cumsum吗？那么问题的核心仍然存在：如何枚举并仍然尊重已分配给组的bike_id-datetime组合的情况（特别是因为bike_id可以位于bike_id1或bike_id2列中）。 - Ratnanil

你的邻域/关联表的自然键似乎是{bike_id1，bike_id2，datetime}。你的“segments”结果将具有{bike_id1，bike_id2，begintime(->endtime)}作为键。即使它们重叠["cumsum":抱歉，我不会读R]，你也可以枚举这些键（在检测到它们之后）。 - wildplasser

你是在尝试进行某种路径的时空聚类吗？这更多地是一个方法问题（目前）而不是一个编程问题吗？那就把它转到stats.stackexchange.com上去。 - Spacedman

@Spacedman：不需要统计数据（附近检测已完成）。但是它确实需要一些更高级别的抽象（数据间隙+组枚举），不过我认为可以用普通的SQL完成。针对OP：你有更多的测试数据吗？只有两个组有点琐碎... - wildplasser

是的，我同意。我已经决定了我的方法论路径，我需要的是编程方法。 "数据中的空缺 + 组的枚举" 似乎是关键词，在 SQL 新手中我从未听说过这个，但我会立即深入研究它。 - Ratnanil

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wildplasser · Accepted Answer

更新：[在理解了真正的问题后;-] 找到自行车（set，bike_set）的等价组实际上是一个关系除法问题。在一组自行车中找到段的开始和结束（clust）基本上与第一次尝试相同。

聚类存储在数组中：（我相信聚类不会变得太大）
该数组由递归查询构建：将具有当前聚类中的一个成员的每对自行车合并到其中。
最后，数组包含所有在特定时间内发生的自行车ID。
（加上一些需要通过uniq CTE稍后抑制的中间行）
其余部分基本上是时间序列中标准的间隙检测。

注意：代码信任(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)