数据挖掘中的模式发现（八）轨迹模式挖掘、空间模式挖掘
这是模式挖掘、数据挖掘的一部分应用。
空间模式挖掘(Mining Spatiotemporal Patterns)
两个空间实体之间存在若干拓扑关系，这些关系基于两个实体的位置：
- 分离
- 相交
- 包含
如图所示地表示位置信息，可以提取类似下面的规则：
is\_a(x, large\_town) \bigwedge intersect(x, highway) → adjacent\_to(x, water) [7\%, 85\%]
逐步求精(Progressive Refinement)
我们可知语言中存在许多二义性的词语，并可在不同情况下采用多种表达方式来呈现相同或相近的概念。
例如，在表征空间关系时, 我们可以选择使用Progressive Refinement这一方法。进而实现一个更为精细或粗糙的空间层次结构。
Step 1
粗略计算，用于筛选
使用MBR(Minimum Bounding Rectangle)或者R-tree粗略估计。
Step2
该算法通过深入的细节处理实现精确操作
仅限于对满足一定条件的粗放计算数据进行处理（其数值不低于最小支持度），从而节省时间和空间资源
共置模式(Colocation pattern)
现有拓扑结构以图形形式呈现，并用数值标示各个节点及其类别。
co-located patterns refer to multiple spatial events or objects that frequently occur in the same or similar spatial regions. In the topology graph, these events are represented by lines connecting them.
其中{3, 6, 17}, {4, 7, 10, 16}, {2, 8, 11, 14, 15}, {2, 9}就是一个Colocation pattern。
rowset集合
While rowset(SET) denotes that all elements of SET are present in the colocation pattern.
条件概率
Condition Probability
定义如下
计算条件概率必须按照定义来。
不是恒等于的。
例如，求cp(A\rightarrow B)。
其中Rowset(A) = \{1,5,6,7,14\}，Rowset(\{A,B\})如上文的例子。
在中包含14的有两个元素，但是根据定义也只能计算一次。
所以cp(A\rightarrow B) = {3\over 5}
Participation Ratio
定义如下
the participation ratio pr(C, f) represents the likelihood that C is observed within the neighborhood where feature f exists.
在f发生的情况下，在这种情况下属于类别C的比例是多少？
例如，
我们可以看到总共有5个A，但是只有2个发生在\{A,B,C,D\}的情况下。
类Apriori算法
算法思想和Apriori算法是一致的。
产生候选集的理论依据是Participation Ratio的单调性：
考虑两个Co-location instance：其中C'是C的一个子集，则Irradiation for any case can achieve pr(C',f)\geq pr(C,f)。
轨迹模式分析（包括从多条轨迹中收集和分析数据模式）
轨迹的挖掘任务
轨迹聚类：基于空间／时空的几何估计进行分组
轨迹联合：给定两个轨迹数据库，检索所有的相似对
通过挖掘能够处理多种问题，包括，路线规划、城市规划、识别物体、模式分类。
基本定义
基本运动模式
描述移动事件，不考虑绝对位置
- Constance:连续时间序列中的恒定运动特征，在此过程中方向始终保持一致。
- Concurrence:在同一时间段内具有相同移动方向的不同物体。
- Trendsetter:基于共同目标形成的统一形状模式（通过constance与concurrence共同体现）。
上图中箭头表示运动方向，横坐标表示时间，纵坐标表示物体。
空间运动模式
基本运动模式＋空间约束
- Track：单一目标维持其一致运动（稳定性与空间限制）
- Group：一群生物共同遵循同一路径（一致性与空间限制）
- Leadership：一队生物由引领者带领共同前进（趋势引导者与空间限制）
- Flock(m, k, r):位于半径r范围内共有m个实体，并包含k个连续的点
- Meet(m, k):至少包含m个体，并且在半径r范围内包括K及以上的连续点
聚合／分离运动模式
描述聚合和分离对象的运动
- Encounter(m, r): 至少m个对象共同抵达半径为r的区域内
- Convergence(m, r): 至少m个对象抵达半径为r的区域内（无需共同抵达）
- Divergence: 即使如此
- Breakup: 同样如此
基于密度的轨迹模式
-
TRACLUS
- 密度相连轨迹段的聚类
- 不考虑时间
-
Moving Cluster
- 在一个时间段内，一组对象相互靠近
-
Convoy
- 基于密度链接的 “Flock (m,k,r).”
-
Swarm
- Time-relaxed convoy. 对象在时间上的倒数
挖掘语义丰富的运动模式(Mining Semantics-Rich Movement Patterns)
-
常驻移动模式：在输入轨迹数据库中反复出现的运动片段
- 常驻移动模式与常驻连续模式：
-
分别在输入序列数据库内查找常见的子序列。
-
为了发现常见运动模式，类似的区域（如下图中的功能分类部分）可能需要将这些区域进行分组以便于发现相关的子序列。
-
语义丰富的运动模式：
-
除了了解人们如何在不同区域之间移动外，在我们还想进一步了解每个区域的功能。
-
举例来说，在同一个位置上办公室和家庭空间可能具有相似的功能；但也有可能位于不同的位置并展现出各自独特的功能。如上图左图所示。
Step1
识别出一组能够表征人们在语义层面不精确转换的趋势。例如，在办公场所到饮食场所的转变中可见一斑；而居住空间与健康场所之间的转换则更为明显。
粗线条语义在先前讨论的"逐步精炼法"中提到过，并属于一些粗线条语义定义。例如，在办公室、办公场所等场景下使用较为普遍。然而，在某些情况下也可能会涉及更为具体的名词如政府办等。
Step2
通过分组，将每个粗糙分类的相似图案分成几个细粒度图案运动片段。
C. Zhang et al., Data miner: Extracting Fine-Grained Ordered Sequences from Meaningful Paths, VLDB 2014