T-DBSCAN - 实现 STOP 逻辑

数据挖掘 数据挖掘 数据库扫描 研究 执行
2022-02-14 18:16:58

我正在尝试实现T-DBSCAN: A Spatiotemporal Density Clustering for GPS Trajectory Segmentation中描述的 T-DBSCAN 算法。我已经能够实现定义(第 3 页)和伪代码(第 4 页)之间的大部分逻辑,但我无法实现确定集群是否stop为定义 9 中描述的逻辑纸(第 3 页)。具体来说,我无法理解定义 9 中引用的定义 7“时间连续”:

定义 7. 时间连续 (TC)。让集群的最小和最大时间戳C(D)mintmaxt, 分别。C被称为是“时间连续的”,如果,对于ptDmint<t<maxt, ptC.

在哪里D是轨迹,并且pt是一个时间点t.

当我阅读定义7时,如果集群中的点在轨迹中,并且如果集群中点的所有时间戳都在集群中的最小时间和最大时间戳之间,这听起来意味着集群是时间连续的,这是没有意义的,因为集群中的所有点将始终位于同一集群中的最小和最大时间戳之间,从而使所有集群在时间上是连续的。

有人愿意为我指出如何解释本节的正确方向吗?定义 9 的逻辑也不包含在伪代码中,所以我只有定义本身。

我已经阅读了Github上的一个现有实现,它也没有实现这个逻辑,这让我相信这部分是微不足道的,不需要实现,或者我不是唯一一个在实现时遇到问题的人算法的最后一部分。

感谢您提供的任何帮助。我愿意提供更多有用的信息。

1个回答

只是为了指出措辞中似乎存在的一个小混乱:暂时和暂时地混合使用了这两个词。[OP 已更正此问题]

我们真的只关心最终的结果,即与时间相关的时间,或集群中点的时间戳。暂时意味着只在很短的一段时间内,这与暂时的“与时间有关”的含义略有不同。

我理解定义的方式,如果最小和最大时间戳包括该集群,则集群被定义为停止集群(一世n一种X)

此外,似乎定义 9暗示了定义 7的使用,所以我假设您需要实现它。If 将用于判断候选集群是否为C一世被定义为一个停止簇。所以最终的伪代码将是这样的:

stop_clusters = []    # empty list
for candidate in candidate_cluster:    # iterate over each stop cluster candidate 
    TC = cluster_is_tc(cluster)        # check cluster is Temporally Continuous
    TO = cluster_is_not_to(cluster)    # check cluster is Temporally Overlapping

    if (TC & TO):                      # if both criteria are met...
        stop_clusters.append(cluster)  # assign to stop clusters

根据定义,您如何实现这两个检查功能将非常简单,假设您拥有每个点的时间戳,您可以简单地检查所有点是否包含在时间范围内。只是略读第 3 页,恐怕这篇论文并没有让我完全清楚地了解这些时间范围,但我希望在您实施它时对您来说很清楚。

时间重叠标准也是如此:您检查两个集群中的时间戳没有重叠 - 如果存在重叠(即交集不是空集),那么您不能将当前候选集群称为停止集群。

编辑:

查看您链接的那个实现,可能是在这一行执行检查时间重叠检查,以防if重叠,而这一else用于其他情况,它们确实在时间上重叠(假设索引值idx是时间戳);他们正在检查最大时间戳是否小于前一个集群的最小时间戳。

我看不到检查集群时间连续性的证据。