高效统一的时空模式挖掘：从理论到实践

### 高效统一的时空模式挖掘：从理论到实践 在当今数据爆炸的时代，移动对象数据呈现出爆发式增长。无论是野生动物的迁徙轨迹，还是汽车的行驶路径，这些数据中蕴含着丰富的时空模式。挖掘这些模式对于理解移动对象的行为、规划路线以及控制车辆等应用具有重要意义。然而，现有的挖掘方法往往只能针对特定类型的模式，且在处理新数据时效率低下。本文将介绍一种高效统一的时空模式挖掘算法——GeT Move，以及相关的理论基础和实验结果。 #### 1. 时空模式概述 随着定位技术的进步，移动对象数据大量涌现。为了从这些数据中提取有价值的信息，研究人员定义了多种时空模式，如群（swarm）、护航队（convoy）、移动集群（moving clusters）、组模式（group pattern）和周期性模式（periodic patterns）等。 - **群（Swarm）**：是一组至少包含 ε 个个体的移动对象，它们在至少 mint 个时间戳内彼此靠近。为了避免冗余，引入了封闭群（closed swarm）的概念，即当固定时间时，对象集合不能再扩大；当固定对象时，时间集合不能再扩大。 - **护航队（Convoy）**：是一组对象，它们在至少 mint 个连续时间点内彼此靠近。 - **移动集群（Moving Clusters）**：可以看作是护航队的特殊情况，需要在两个连续时间戳之间共享一些对象。 - **组模式（Group Pattern）**：本质上是不相交护航队的封闭群，需要满足一定的权重和数量条件。 - **周期性模式（Periodic Patterns）**：是指对象在规则的时间间隔内大致遵循相同的路线，可通过对轨迹进行分解后应用封闭群的性质来挖掘。 这些模式的定义可以通过以下表格和公式来更清晰地表示： | 模式名称 | 定义公式 | | ---- | ---- | | 群（Swarm） | (1) : ∀tai ∈T, ∃c s.t. O ⊆c, c 是一个集群；(2) : \|O\| ≥ε 且 \|T\| ≥mint | | 封闭群（Closed Swarm） | (1) : ∄O′ s.t. (O′, T) 是一个群且 O ⊂O′；(2) : ∄T′ s.t. (O, T′) 是一个群且 T ⊂T′ | | 护航队（Convoy） | (1) : (O, T) 是一个群；(2) : ∀i, 1 ≤i < \|T\|, tai,tai+1 是连续的 | | 组模式（Group Pattern） | (1) : (O, TS) 是一个封闭群，其中 \|TS\| ≥minc；(2) : ∑_\|TS\|ⁱ⁼¹ \|si\| / \|TDB\| ≥minwei | 为了更好地理解这些模式，我们可以通过以下 mermaid 流程图来展示它们之间的关系： ```mermaid graph LR A[移动对象数据] --> B[群（Swarm）] B --> C[封闭群（Closed Swarm）] B --> D[护航队（Convoy）] D --> E[移动集群（Moving Clusters）] C --> F[组模式（Group Pattern）] A --> G[周期性模式（Periodic Patterns）] ``` #### 2. 相关工作回顾 在时空模式挖掘领域，已经有许多研究提出了不同的算法来提取特定类型的模式。例如，Gudmundsson 和 Van Kreveld 定义了 flock 模式，Kalnis 等人提出了移动集群的概念，Jeung 等人定义了护航队模式并提出了相关算法，Zhenhui Li 等人提出了群和封闭群的概念以及 ObjectGrowth 算法，Hwang 等人提出了组模式的挖掘算法。 然而，这些方法大多只能提取特定类型的模式，当面对一个数据集时，决策者很难提前知道数据中包含哪些类型的模式。因此，需要一种能够自动提取所有不同类型模式的统一方法。 #### 3. 时空模式在项集上下文中的表示 为了更有效地挖掘时空模式，将其表示在项集上下文中。通过将时空数据转换为集群矩阵（Cluster Matrix），每个对象作为一个事务，每个集群作为一个项。项集可以由多个集群组成，其支持度是指所有项中共同对象的数量。 - **集群矩阵（Cluster Matrix）**：是一个大小为 \|ODB\| × \|CDB\| 的矩阵，其中每一行代表一个对象，每一列代表一个集群。矩阵元素的值为 1 表示对象属于该集群，为空表示不属于。 - **项集（Itemset）**：可以表示为 Υ = {cta1, cta2, ..., ctap}，其生命周期为 TΥ = {ta1, ta2, ..., tap}。项集的支持度 σ(Υ) 是指所有项中共同对象的数量，长度 \|Υ\| 是指项的数量或时间戳的数量。 通过这种表示方法，可以定义一些有用的属性来从频繁项集中提取模式： - **封闭群属性（Closed Swarm Property）**：给定一个频繁项集 Υ，如果满足一定条件，则 (O(Υ), TΥ) 是一个封闭群。 - **组模式属性（Group Pattern Property）**：给定一个频繁项集 Υ 和一组连续时间段 TS，如果满足一定条件，则 (O(Υ), TS) 是一个组模式。 这些属性的证明可以通过数学推导来完成，具体过程可以参考原文。通过这些属性，可以证明所有的群和组模式都可以从频繁项集中提取出来。 #### 4. FCI 基于的时空模式挖掘算法 为了高效地提取时空模式，提出了两种方法：GeT Move 和 Incremental GeT Move。 - **GeT Move 算法**：首先在每个时间戳应用聚类方法将对象分组为不同的集群，然后将时空数据转换为集群矩阵。接着，应用 LCM 算法从集群矩阵中提取所有的频繁封闭项集（Frequent Closed Itemsets，FCIs）。在提取过程中，会丢弃一些无用的候选项集，以减少计算时间。最后，通过扫描 FCIs 并检查其属性，提取出时空模式。 GeT Move 算法的伪代码如下： ```plaintext Algorithm 1. GeT Move Input : int ε, int ```