移动对象轨迹与地理传感器网络的数据挖掘探索

### 移动对象轨迹与地理传感器网络的数据挖掘探索 在地理数据挖掘领域，移动对象轨迹的周期性模式发现以及地理传感器网络的分布式数据挖掘是两个重要的研究方向。下面将详细介绍相关的技术和方法。 #### 移动对象轨迹的周期性模式发现 在移动对象轨迹的研究中，主要聚焦于周期性模式的发现，这有助于捕捉对象在特定时间周期性访问特定地点的运动规律。 ##### 候选模式与最大有效时代计算 首先，会生成候选的1 - 模式。对于每个候选模式P，其初始时代为 [bmin, emax]，最大有效时代是 [bmin, emax] 的一个子集 [b, e]，且 [b, e] 的任何超集都不能使P有效。计算最大有效时代的方法是从较长长度的时代到较短长度的时代递归检查 [bmin, emax] 的子集，第一个报告的有效时代就是最大的。 为了找到更长的时代模式，采用了STPMine2 - V2算法。通过组合有效的1 - 模式形成最大子模式Pmax，其时代是定义P的1 - 模式的时代的并集。例如，一组时代 {[b1, e1], [b2, e2], …, [bk, ek]} 的并集定义为 [min(bi), max(ei)]。并且，形成最大子模式P的1 - 模式的时代必须有非空交集，否则P没有有效的实例。从候选的最大模式中，EPMine为每个模式构建最大子模式树，按广度优先顺序遍历这些树并报告具有有效最大时代的较长模式。 ##### 移位和扭曲模式 在序列模式挖掘中，还涉及到移位和扭曲模式的概念。 - **移位模式实例**：给定序列S和整数V（0 ≤ V ≤ ⌈T/2⌉），如果一个段sj[d]（ - V ≤ d ≤ V）符合模式P，即P在S中的出现相对于其预期位置j·T最多向前或向后移动V个时间戳，则称sj[d]是模式P的移位模式实例。例如，当T = 5，序列S = r0r1r2r3r4 r0r0r1r4r3 r2r0r1r3r3时，模式r0r1 * r3 * 有一个非移位实例s0（从位置0开始）和两个移位模式实例s1[1]（从位置6开始）和s2[1]（从位置11开始）。 - **扭曲模式实例**：对于长度为Plen的模式P = r0r1…rT - 1，如果在段sj[d]（ - V ≤ d ≤ V）中存在Plen个有序位置，满足这些位置遵循P中非 * 元素的顺序，并且对于P中的每个非 * 元素，其周期偏移与sj[d]中相关位置的周期偏移最多相差V，则称sj[d]是模式P相对于V的扭曲实例。例如，当V = 1，段s0 = l0l1l2l3l4，若l1 ∈ r0，l2 ∈ r2，l4 ∈ r3，则s0是模式P = r0 * r2r3 * 的扭曲实例。 当两个模式实例（段）有一些共同位置时，它们会重叠。如果模式P在S中有超过min_sup·m个（移位/扭曲）模式实例，且没有两个实例重叠，则称P是具有移位/扭曲实例的频繁模式。发现具有移位/扭曲实例的频繁模式分为两个阶段： 1. **第一阶段**：采用类似于之前的程序来查找1 - 模式。不同的是，此阶段会为对象位置在偏移位置i的所有V - 邻居位置R(i - V) mod T, R(i - V + 1) mod T, …, R(i + V) mod T生成点。例如，假设V = 1，在图15.3a中第1天的第5个位置，算法会生成一个‘/’点（到文件R5）、一个‘+’点（到文件R4）和一个‘×’点（到文件R6）。 2. **第二阶段**：采用STPMine2 - V2算法来促进对更长（移位/扭曲）模式实例的计数。该算法从最大子模式Pmax开始进行模式验证，逐层检查Pmax的子模式。对于每个候选子模式P，算法会为每个非 *