轨迹聚类(一)：分段及归组框架(Trajectory Clustering:A Partition-and-Group Framework))

1.综述

现有的轨迹聚类算法可分为两类：一种是基于整体的轨迹聚类，即将一条轨迹视为一个整体而对其不做分段，通过定义轨迹的相似度函数将其聚类，这样一条轨迹只能属于一个簇；另一种是基于分段的轨迹聚类，即将一条轨迹分为多段，分段的轨迹之和不一定是原轨迹，也可以是原轨迹特征的抽取。之后再进行轨迹聚类，这样同一条轨迹可能分属于多个簇，可视的结果会出现分流与聚流的效果。
基于不同的应用场景会运用不同的算法，如果只从准确度上评价而不考虑其它因素，基于分段的轨迹聚类相对更好一此。因为它研究的粒度更细，而基于整体的轨迹聚类会丢失一些细节信息，举一个例子：
An example of a common sub-trajectory
如上图，有五条轨迹 $TR_i(i = 1, 2,...5)$ ，如果运用基于分段的聚类算法，则方框内的轨迹将聚为一簇；而如果是基于整体的聚类算法，由于五条轨迹最终的走向各不相同，因而很有可能五条轨迹归属于不同的类。然而忽略掉起始时的聚集状态是不合理的，显然在这种情况下基于分段的轨迹聚类更好一些。
基于此，原文提出了“分段及归组”的轨迹聚类框架，正如其名，算法分为两大步：
1. 分段：将轨迹进行分段以作为下一阶段的输入；
2. 归组：相似的线段归为一类。归类的算法采用基于密度的聚类算法，本文采用的是DBSCAN算法，若不熟悉该算法可查看我的前一篇博客。
http://blog.csdn.net/jsc9410/article/details/51004057
An example of trajectory clustering in the PGF

2. 轨迹聚类

2.1 TRACLUS算法

原文将该算法概括如下：
Algorithm TRACLUS

2.2轨迹距离函数

由于DBSCAN算法是基于密度的算法，对于散点的聚类利用欧氏距离衡量就可以，但轨迹就不同如此。因此必须事先定义轨迹之间的距离。
给定任意的两条线段，其长度及方向不一定相同，如何衡量它们之间的相似度？
先从简单的开始，情况一：给定两条同等长度相互平行且两起点的连线或两终点的连线与这两条线段垂直，那么我们可以用它们之间的垂直距离 $d_{\perp}$ 来衡量它们的相似度，距离越近就越相似，如果这两条线段完全重合就意味着其完全相同。
若在上面的基础上，情况二：将两条线段沿其方向错位或改变其中一条线段的长度，在同等 $d_{\perp}$ 的情况一和二下，显然它们的相似度只用垂直距离是不够的，需要用水平方向的差别来衡量，即水平距离 $d_{\parallel}$
若在情况二的基础上，情况三：将其中一条线段沿某一方向旋转，则两条线段的夹角越大，其相似度越小，因此又需要引入夹角距离 $d_{\theta}$ 的概念。
原文对距离的定义就基于这种思想。
Distance Function
三者的定义如下：

d ⊥ (L i, L j) = l 2 ⊥ 1 + l 2 ⊥ 2 l ⊥ 1 + l ⊥ 2

$d_{\perp} (L_i, L_j) = \frac{l_{\perp1} ^ 2 + l_{\perp2} ^ 2}{l_{\perp1} + l_{\perp2}}$

d ∥ (L i, L j) = M I N (l ∥ 1, l ∥ 2)

$d_{\parallel}(L_i, L_j) = MIN(l_{\parallel1}, l_{\parallel2})$
formula3

第三个公式考虑了轨迹的方向，当夹角大于90度时可视为极不相似，如果不考虑轨迹的方向时，可以用

||Lj||×sin(θ) $||L_j|| \times sin(\theta)$ 来衡量。
将三个部分综合起来就是：

d i s t (L i, L j) = w ⊥ ? d ⊥ (L i, L j) + w ∥ ? d ∥ (L i, L j) + w θ ? d θ (L i, L j)

$dist(L_i, L_j) = w_{\perp} \cdot d_{\perp}(L_i, L_j) + w_{\parallel}\cdot d_{\parallel}(L_i, L_j) + w_{\theta}\cdot d_{\theta}(L_i, L_j)$

w⊥ $w_{\perp}$ ，

w∥ $w_{\parallel}$ ，

wθ $w_{\theta}$ 分别为三部分的权重。原文中设定权重均为1。

3.轨迹分段

trajectory and its trajectory partitions
轨迹分段是在原轨迹中选取一些特征点，利用特征点的连线来近似原轨迹。特征点是多指轨迹中角度变化较大的点。
对轨迹的分段要保证两个性质：准确性和简洁性。
准确性是指特征点不能太少，否则不足以概括轨迹特征；
简洁性是指特征点要利用尽可能少的点来概括轨迹特征。
这两个特性相互矛盾，因此算法要能够很好地平衡这两个特性。

3.1 MDL原则

原文采用信息压缩中广泛采用的标准来平衡：MDL(Minimum Description Length)原则。
最小描述长度( MDL) 原理是 Rissane 在研究通用编码时提出的。其基本原理是对于一组给定的实例数据 D ，如果要对其进行保存，为了节省存储空间，一般采用某种模型H对其进行编码压缩，然后再保存压缩后的数据。同时，为了以后正确恢复这些实例数据，将所用的模型也保存起来。所以需要保存的数据长度( 比特数) 等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度，将该数据长度称为总描述长度。最小描述长度( MDL) 原理就是要求选择总描述长度最小的模型。
MDL原则包含两个部分：
1. $L(H)$ : 描述压缩模型（或编码方式）所需要的长度
2. $L(D|H)$ : 描述利用压缩模型所编码的数据所需要的长度
原文中对两部分的定义如下：
MDL Formula
L(D|H)中没有包含水平距离是因为对于闭合的两条线段，其水平距离为零。
例如：
Formulation of the MDL cost

3.2 算法描述

完整的算法描述如下：
Algorithm Approximate Trajectory Partitioning
其中 $MDL_{par}(p_i,p_j)$ 代表若点 $p_i$ 及 $p_j$ 为特征点时所需要的MDL开销，即 $L(H) + L(D|H)$ ; $MDL_{nopar}(p_i, p_j)$ 代表点 $p_i$ 及点 $p_j$ 之间没有特征点时的MDL开销。对于给定的一条线段，算法选择其特征点的标准是该点为特征点的MDL开销要小于不选择其作为特征点的MDL开销。通过逐次检查每个点是否满足该条件来选择特征点，因此算法复杂度为 $\mathcal{O}(n)$
Reference:
Trajectory Clustering: A Partition-and-Group Framework，Jae-Gil Lee, Jiawei Han，Kyu-Young Whang