Lee_Trajectory Clustering_2007

标题：Trajectory Clustering: A Partition-and-Group Framework
作者：Jae-Gil Lee, Jiawei Han, Kyu-Young Whang
机构：SIGMOD '07: 2007 年 ACM SIGMOD 国际数据管理会议论文集
引用：Lee J G, Han J, Whang K Y. Trajectory clustering: a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data. 2007: 593-604.

研究问题Research Question

科学问题Science Question

• 轨迹聚类时，若将轨迹作为一个整体进行聚类，则难以发现轨迹的某些共同行为，从而可能错过一些有价值的信息。所以，该如何挖掘出这一类信息？

• 作者开发了一种基于划分和分组架构的高效聚类算法。给定一组轨迹，该算法可以生成一组聚类以及每个类的代表性轨迹。轨迹、聚类和代表性轨迹的定义如下：

  • 轨迹是一个多维点序列，表示为$T R_{i}=p_{1} p_{2} p_{3} \cdots p_{j} \cdots p_{l e n_{i}}\left(1 \leq i \leq n u m_{t r a}\right)$，其中， $p_{j}(1≤j≤len_{i})$是一个 $d$ 维的点，每条轨迹的长度 $len_{i}$可以互不相同，一条轨迹$p_{c_{1}} p_{c_{2}} \cdots p_{c_{k}}\left(1 \leq c_{1}<c_{2}\cdots<c_{k} \leq l e n_{i})\right.$被称为一条子轨迹$T R_{i}$。
  • 集群是一组轨迹分区。轨迹分割的结果是一条线段 $p_{i}p_{j}(i<j)$，其中 $p_{i}$和 $p_{j}$是从同一轨迹中选择的点。根据距离度量，属于同一簇的线段彼此接近。
    一条轨迹可以属于多个簇，因为在该算法中，轨迹被划分成多个线段，并且在这些线段上执行聚类
  • 代表性轨迹是像普通轨迹一样的点序列。它是一个假想的轨迹，用于表示属于集群的轨迹分区（即线段）的主要行为。
    一个代表性轨迹表示一个共同的子轨迹

研究核心Core of the research

• 基于分区和分组架构（将轨迹划分为一组线段，然后将相似的轨迹聚为一个类）的轨迹聚类算法，整体过程如下图：
  
  • 首先，每个轨迹被划分成一组线段；
  • 其次，根据距离度量，彼此接近的线段被分组成一个簇；
  • 最后，为每个簇生成一个有代表性的轨迹；

研究意义Research significance

1. 考虑下图中的五个轨迹，可以发现，在虚线矩形中五条轨迹有一个共同的行为（用粗箭头表示）。然而，如果把这些轨迹以一个整体进行聚类，则无法发现其共同的行为，因为它们向完全不同的方向移动，因此将错过一些有价值的信息。
   
   本文提出的分区与分组架构，是将一条轨迹分割成一组线段，然后将相似的线段进行分组，这样可以从一个轨迹集中发现共同的子轨迹。
   共同子轨迹的实际应用价值：

   1. 飓风的登陆预报
      气象学家正试图提高预测飓风登陆地点和时间的能力。准确的登陆位置预测是至关重要的，因为它对减少飓风造成的损失至关重要。
      海岸线附近（即登陆时）或海上（即登陆前）飓风的常见行为可以帮助气象学家提高飓风登陆预测的准确性，而飓风在这一阶段的常见行为就是它们的子轨迹。
   2. 道路和交通对动物运动的影响
      动物学家正在调查不同程度的交通状况对动物的运动、分布和对栖息地的使用的影响。他们主要测量道路和动物之间的平均距离，他们会对交通速度不同的道路附近动物的常见行为感兴趣。因此，发现共同的子轨迹有助于揭示道路和交通对动物的影响。

2. 考虑下图中的动物栖息地和道路（粗线代表道路，且它们有着不同的交通速率）。Wisdom等人探讨了骡鹿和麋鹿与不同交通速率的道路之间的空间格局。更具体地说，其中一个目标是评估骡鹿和麋鹿避开道路附近地区的程度（这些区域用实心矩形表示）。因此，本文提出的框架对这类研究确实很有用。
   
   有人提出，可以修剪轨迹中无用的部分，而只保留有价值的部分，再使用传统的聚类算法——将轨迹作为一个整体进行聚类。然而，与本文提出的分区和分组框架相比，上述方案有两个主要的缺点：首先，难以确定轨迹的哪一部分是无用的。其次，修剪轨迹中“无用的”部分，使我们无法发现意外的聚类结果。

现有算法的不足Shortcomings of existing algorithm

• 现有算法将相似的轨迹作为一个整体进行分组，从而发现相似的轨迹，但可能会错过常见的子轨迹。

结论Conclusion

• 基于分区和分组架构，开发了一轨迹聚类算法，该算法包括以下两个阶段：
  1. 分区阶段——每个轨迹都被最优地划分为一组线段，这些线段将被提供给下一阶段
     本文提出了一基于最小描述长度( $MDL$)原则的形式化轨迹划分算法。
  2. 分组阶段——将类似的线段分组为一个集群
     • 本文提出了一基于密度的线段聚类算法。
     • 基于密度的聚类方法是最适合用于线段的，因为它们可以发现任意形状的聚类，并可以过滤出噪声。
     • 线段簇通常是任意形状的，且轨迹数据库通常包含大量的噪声（即异常值）。
• 结果表明，从真实轨迹数据中发现了常见的子轨迹。

---

理论与方法Theory and Method

距离函数

• 三个组成部分：垂直距离$d_{⊥}$、平行距离$d_{k}$和角距离$d_{\theta}$
  
• 假设：$L_{i} = s_{i}e_{i}$和 $L_{j} = s_{j}e_{j}$为两条 $d$ 维的线段，其中， $s_{i},\ e_{i},\ s_{j}和e_{j}$为$d$维的点，且在不失一般性的前提下，令$L_{i}≥L_{j}$
• 垂直距离$d_{\perp}\left(L_{i}, L_{j}\right)=\frac{l_{\perp 1}^{2}+l_{\perp 2}^{2}}{l_{\perp 1}+l_{\perp 2}}$(1)
  假设点 $s_{j}和e_{j}$在 $L_{i}$上的投影点分别为 $p_{s}和p_{e}$， $l_{⊥1}$为 $s_{j}$和 $p_{s}$之间的欧氏距离，同理 $l_{⊥2}$是 $e_{j}$和 $p_{e}$之间的欧式距离
• 平行距离$d_{\|}\left(L_{i}, L_{j}\right)=\operatorname{MIN}\left(l_{\| 1}, l_{\| 2}\right)$(2)
  假设点 $s_{j}$和 $e_{j}$在 $L_{i}$上的投影点分别为 $p_{s}$和 $p_{e}$。 $l_{\| 1}$为$p_{s}$到$s_{i}$和$e_{i}$的欧氏距离的最小值。同理 $l_{\| 2}$为 $p_{e}$到 $s_{i}$和 $e_{i}$的欧氏距离的最小值
  平行距离被设计为对检测误差（尤其是断线段）是鲁棒的。如果使用 $MAX(l_{\| 1}，l_{\| 2})$而不是 $MIN(l_{\| 1}，l_{\| 2})$，平行距离可能会受到折线段的显著干扰
• 角距离$d_{\theta}\left(L_{i}, L_{j}\right)= \begin{cases}\left\|L_{j}\right\| \times \sin (\theta), & \text { if } 0^{\circ} \leq \theta<90^{\circ} \\ \left\|L_{j}\right\|, & \text { if } 90^{\circ} \leq \theta \leq 180^{\circ}\end{cases}$(3)，其中 $\| L_{j}\|$为 $L_{j}$的长度， $\theta$角为 $L_{i}和L_{j}$之间较小的那个角
  角度距离是针对有方向的轨迹而设计的。当方向差异显著时，整个长度将对角距离有贡献，即会对夹角距离产生影响。如果处理的是没有方向的轨迹，则角距离被简单地定义为 $\|k_{j}\|×sin(\theta)$
• 向量表示
  用$\overrightarrow{a b}$表示 $a,\ b$两点构成的向量
  公式(1)和(2)中的投影点可以用公式 $p_{s}=s_{i}+u_{1} \cdot \overrightarrow{s_{i} e_{i}}, \quad p_{e}=s_{i}+u_{2} \cdot \overrightarrow{s_{i} e_{i}}$，
  其中$u_{1}=\frac{\overrightarrow{s_{i} s_{j}} \cdot \overrightarrow{s_{i} e_{i}}}{\left\|\overrightarrow{s_{i} e_{i}}\right\|^{2}}, \quad u_{2}=\frac{\overrightarrow{s_{i} e_{j}} \cdot \overrightarrow{s_{i} e_{i}}}{\left\|\overrightarrow{s_{i} e_{i}}\right\|^{2}}$计算公式(3)中的角度 $\theta$可以用公式 $\cos (\theta)=\frac{\overrightarrow{s_{i} e_{i}} \cdot \overrightarrow{s_{j} e_{j}}}{\left\|\overrightarrow{s_{i} e_{i}}\right\|\left\|\overrightarrow{s_{j} e_{j}}\right\|}$计算
• 综上，两线段之间的距离定义为 $(L_{i}，L_{j}) = w_{⊥}·d_{⊥}(L_{i},\ L_{j})+w_{\|}·d_{\|}(L_{i},\ L_{j})+w_{\theta}·d_{\theta}(L_{i},\ L_{j})$
  其中，权重 $w_{k}和w_{\theta}$根据实际应用而定，其值平均设置为1

轨迹划分

理想属性

• 轨迹行为中快速变化的点，称之为特征点。
  轨迹划分过程：首先，从轨迹$T R_{i}=p_{1} p_{2} p_{3} \cdots p_{j} \cdots p_{l e n_{i}}$中确定一组特征点$\left\{p_{c_{1}}, p_{c_{2}}, p_{c_{3}}, \cdots, p_{c_{\text {pari }}}\right\}$$(c_{1}<c_{2}<c_{3}<···<c_{par_{i}})$。然后，对轨迹 $TR_{i}$的每个特征点进行分割，每个分割由两个连续特征点之间的一条线段表示，即 $TR_{i}$被划分为一组（$par_{i}$−1）线段$\left\{p_{c_{1}} p_{c_{2}}, p_{c_{2}} p_{c_{3}}, \cdots, p_{c_{p a r_{i}}-1} p_{c_{p a r_{i}}}\right\}$，这样的线段称为轨迹划分
  
• 轨迹的最优划分应该具有两个理想的特性——精确性和简洁性，精确性意味着轨迹与其一组轨迹分区之间的差异应该尽可能小，简洁性意味着轨迹分区的数量应该尽可能少。
• 实验发现，实现精确性要求每一处轨迹分区其行为是迅速变化的。否则，就无法达到精确性。如在上图中若没有选择 $p_{c2}$，由于 $TR_{i}$和 $p_{c1}\ p_{c3}$之间的差异很大，精度会降低。
• 精确性和简洁性是相互矛盾的。例如，如果选择一个轨迹中的所有点都作为特征点（即 $par_{i}=len_{i}$），则精度是最大化的，但简洁性却是最小的。相比之下，如果只选择轨迹的起点和结束点作为特征点（即 $par_{i}=2$），简洁性是最大化的，但精度却是最小化的。因此，需要在这两个属性之间找到一个最优的权衡。

使用MDL原理进行形式化

• $MDL$由两个部分组成： $L(H)和L(D|H)$。其中， $H$表示假设， $D$表示数据。
  $H和D$非正式地表述如下：“$L(H)$是假设描述的长度，以位表示；$L(D|H)$ 是根据假设编码数据描述时的长度，以位表示。”用来解释$D$的最佳假设$H$是将$L(H)和L(D|H)$的和最小化的假设。
• 在轨迹划分问题中，一个假设对应于一组特定的轨迹划分。因此，找到最优划分可以转化为使用$MDL$原则找到最佳假设。
• 假设一个轨迹 $TR_{i}=p_{1}p_{2}p_{3}···p_{j}···p_{len_{i}}$ 和一组特征点 $={p_{c1}、p_{c2}、p_{c3}、···、p_{c_{par_{i}}}}$，有如下两个公式：
  • $L(H)=\sum_{j=1}^{p a r_{i}-1} \log _{2}\left(\operatorname{len}\left(p_{c_{j}} p_{c_{j+1}}\right)\right)$(6)
    其中，$len(p_{c_{j}}p_{c_{j+1}})$ 表示线段 $p_{c_{j}}p_{c_{j+1}}$ 的长度，即 $p_{c_{j}}$ 与 $p_{c_{j+1}}$ 之间的欧氏距离。因此，$L(H)$ 表示所有轨迹分区的长度之和。
  • $L(D \mid H)=\sum_{j=1}^{p a r_{i}-1} \sum_{k=c_{j}}^{c_{j+1}-1}\left\{\log _{2}\left(d_{\perp}\left(p_{c_{j}} p_{c_{j+1}}, p_{k} p_{k+1}\right)\right)+\log _{2}\left(d_{\theta}\left(p_{c_{j}} p_{c_{j+1}}, p_{k} p_{k+1}\right)\right)\}\right.$(7)
    $L(D|H)$表示一段轨迹与其所属轨迹分区之间的差值之和，即对于每个轨迹分区$p_{c_{j}}p_{c_{j+1}}$，将该轨迹分区与属于该分区的线段$p_{k}p_{k+1}(c_{j}≤k≤c_{j+1}−1)$之间的差异相加。
    使用垂直距离和角度距离的和来衡量差异。不考虑平行距离是因为一个轨迹包含了它的轨迹分区
    
• 长度和距离都是实数。在实践中，对实数 $x$ 进行编码，假设其精度为$δ$，以便编码的数字$x_{δ}$满足$|x−x_{δ}|<δ$。如果 $x$ 很大且$x≈x_{δ}$，则$L(x)=log_{2}x−log_{2}δ$。在本文，将$δ$设为1。因此，$L(x)$仅简单地等于$log_{2}x$。
• 线段的长度而不是线段的端点来定义$L(H)$的原因如下：
  • 首先，我们的任务是根据线段（子轨迹）的相对距离对它们进行聚类。长度（反映在$L(H)$）和距离函数，即线段之间的垂直、平行和角度距离（反映在$L(D|H)$），比线段的端点更好地测量相对距离。也就是说，新的定义更适合于子轨迹聚类的任务。
  • 其次，不使用端点的一个非常重要的原因是为了使聚类结果不受线段的坐标值的影响。也就是说，一堆线段可以从低坐标位置移动到高坐标位置，但距离函数应该仍然能够正确地测量相对距离。如果用两个端点的坐标值来表示$L(H)$，聚类结果可能会因为这种移动而被扭曲。
• 注意到，$L(H)$测量的是简洁度，而$L(D|H)$测量的是精确度。由于三角形不等式，$L(H)$会随着轨迹分割的数量的增加而增加，而$L(D|H)$会随着一组轨迹分区偏离轨迹程度的增加而增加。
• 如前所述，需要找到使$L(H)+L(D|H)$最小化的最优划分，这也是精确和简洁之间的权衡。
  寻找最优分区的代价是高昂的，因为需要考虑一个轨迹中点的每个子集。

近似解

• 关键思想是将局部最优的集合视为全局最优
• $MDL\ cost =L(H)+L(D|H)$
• 设 $MDL_{par}(p_{i}, p_{j})$ 表示在假设 $p_{i}$ 和 $p_{j}$ 只是特征点时 $p_{i}$ 和 $p_{j}(i<j)$ 之间轨迹的 $MDL\ cost$。
  设 $MDL_{nopar}(p_{i}, p_{j})$ 表示在假设 $p_{i}$和$p_{j}$ 之间没有特征点时的 $MDL\ cost$，即在保持原始轨迹时。
• $MDL_{nopar}(p_{i}, p_{j})$ 中的 $L(D|H)$ 为零，且局部最优是每 $k$ 个满足 $MDL_{par}(p_{i}，p_{k})≤MDL_{nopar}(p_{i}，p_{k})$ 的最长轨迹分区 $p_{i}p_{k}$，即 $i<k≤j$。如果前者小于后者，选择 $p_{k}$ 作为一个特征点会使 $MDL\ cost$ 比不选择它更小。此外，为了简洁，需尽可能地增加这个轨迹分割的长度。
• 下图显示了近似轨迹划分算法。
  先计算轨迹中每个点的 $MDLpar$ 和 $MDLnopar$（行5∼6），如果 $MDLpar$ 大于 $MDLnopar$，则将前面的点 $p_{currIndex−1}$ 插入到特征点的集合 $CP_{i}$ 中（第8行），然后从该点开始重复相同的过程（第9行）。否则，将增加候选轨迹分区的长度（第11行）。
  
• 定理1。上图中算法的时间复杂度为 $O(n)$ ，其中 $n$ 是一个轨迹$TR_{i}$的长度（即点的数量）。
  证明：所需的$MDL$计算次数等于轨迹$TR_{i}$中的线段数(即 $n−1$)。
• 当然，该算法可能无法找到最优的分区。
  如下图所示，假设具有最小 $MDL\ cost$ 的最优划分为 $\{ p_{1}p_{5} \}$ 。但该算法无法找到精确的解，因为它在 $p_{4}$处$MDL_{par}$ 大于 $MDL_{nopar}$ 时停止扫描。
  然而，该算法的精度相当高。经验表明，算法精度平均约为80%，这意味着80%的近似解也出现在精确解中。
  

线段聚类

线段密度

距离函数回顾

• 距离函数是三种距离的加权和。
  • 垂直距离主要测量从不同轨迹中提取的线段之间的位置差异
  • 平行距离主要测量从同一轨迹中提取的线段之间的位置差异。在一个轨迹中，两个相邻的线段之间的平行距离始终为零
  • 角度距离测量线段之间的方向差
• 距离函数的对称性是避免聚类结果的模糊性的重要方法。如果一个距离函数是不对称的，则根据处理顺序的不同可以得到不同的聚类结果。以下是对本文提出的距离函数的对称性的证明：
  距离函数 $dist(L_{i}，L_{j})$ 是对称的，即 $dist(L_{i}，L_{j})=dist(L_{j}，L_{i})$。证明：为了使 $dist(L_{i}，L_{j})$ 对称，可以将一个较长的线段分配给$L_{i}$，将一个较短的线段分配给$L_{j}$。（可以通过比较线段的内部标识符来打破联系）因此，可以认为$dist(L_{i}，L_{j})$是对称的。

基于密度的聚类的概念

• 设$D$表示所有线段的集合
• 直线段$L_{i}∈D$的 $ε-$ 邻域$N_{ε}(L_{i})$由$N_{ε}(L_{i})={\{ L_{j}∈D|dist(L_{i}，L_{j})≤ε \}}$定义
• 如果$|N_{ε}(L_{i})|≥MinLns$，则线段$L_{i}∈D$被称为一个关于 $ε$ 和 $M$ 的核心线段
• 线段$L_{i}∈D$可以关于 $\varepsilon\ 和\ MinLns$从线段$L_{j}∈D$直接密度可达，当且仅当 $L_{i} \in N_{\varepsilon}(L_{j})$且 $|N_{ε}(L_{i})|≥MinLns$
• 线段$L_{i}∈D$可以从关于 $\varepsilon\ 和\ MinLns$的线段$L_{j}∈D$直接密度可达，当且仅当存在一组线段 $L_{j} , L_{j−1}, · · · , L_{i+1}, L_{i} ∈ D$使得 $L_{k}$可以关于 $\varepsilon\ 和\ MinLns$由直接密度可达
• 如果有一个线段$L_{k}∈D$，使得从 $L_{k}$关于 $\varepsilon\ 和\ MinLns$到$L_{i}$和$L_{j}$密度可达，则一个线段$L_{i}∈D$关于 $\varepsilon\ 和\ MinLns$到一个线段$L_{j}∈D$密度可达
• 一个非空的子集$C⊆D$被称为关于 $\varepsilon\ 和\ MinLns$的密度连接集当且仅当 $C$ 满足如下两个条件：
  1. 连通性：$∀L_{i}，L_{j}∈C$，$L_{i}$ 都关于 $\varepsilon$ 和 $\ MinLns$ 与 $L_{j}$ 密度连接
  2. 极大性：$∀L_{i}，L_{j}∈D$，如果$L_{i}∈C$且$L_{j}$可以从$L_{i}$关于$ε\ 和\ MinLns$直接密度可达，则有$L_{j}∈C$
• 密度可达性是直接密度可达性的传递闭包。
  密度可达性是不对称的，其只有核心线段是相互密度可达的；而密度-连通性是一种对称的关系。
• 考虑下图中的线段。设 $MinLns$为3，粗线段表示核心线段，$ε-$ 邻域用不规则的椭圆表示，则有
  • $L_{1}、L_{2}、L_{3}、L_{4}和L_{5}$为核心线段
  • $L_{2}$（或$L_{3}$）从$L_{1}$直接到达密度
  • $L_{6}$ 从 $L_{1}$ 直接密度可达，但反之则不然
  • $L_{1}$、$L_{4}$ 和 $L_{5}$都是相互密度可达的
    

观察

• 线段由于同时具有方向和长度，因此具有一些与基于密度的聚类相关的有趣特征：
  • 线段的$ε$-邻域的形状不是一个圆或球体，相反，它的形状非常依赖于数据，很可能是一个椭圆或一个椭球体，主要受核心线段和边界线段的方向和长度的影响。
  • 一个短线段可能会大大降低聚类质量。一个线段的长度代表其方向强度，即如果一个线段较短，则它的方向强度较低。这意味着，如果其中一个线段非常短，那么无论实际的角度如何，角度距离都很小。
    如下图所示两组线段，其唯一的区别是$l_{2}$的长度。在（a）图中，$L_{1}$可以通过$L_{2}$从$L_{3}$密度可达（反之亦然）；而在图（b）中，则不然。
    图（a）中的结果是违反直觉的，因为$L_{1}$和$L_{3}$相距很远。
    因此，一个短线段可能会导致过度聚类。
    
    这个问题的一个简单解决方案是通过调整划分轨迹的近似算法中的分区标准来使轨迹分区变长，即以牺牲精确性为代价来抑制划分。具体而言，为了抑制划分，可以在划分轨迹的近似算法的第6行的$cost_{nopar}$中增加一个小常数。实验表明，将轨迹分区的长度增加20∼30%，通常可以提高聚类质量。

聚类算法

• 本文所提出的基于密度的线段聚类算法：给定一个线段集合$D$，基于两个参数$ε$和$MinLns$，该算法生成一组簇 $O$。其中，将一个集群定义为一个密度连接集。
• 该算法与$DBSCAN$算法有许多相似的特征，所不同的是并不是所有的密度连接集都可以成为集群。我们需要考虑从线段中提取出的轨迹的数量，而这个轨迹的数量通常比线段的数量要小。例如，在极端情况下，密度连接集中的所有线段都可以是从一个轨迹中提取的。应避免这样的集群，因为它们不能解释足够数量的轨迹的行为。
  由此，引出如下“轨迹基数”的概念：
  一个簇$C_{i}$的参与轨迹集由$PTR(C_{i}) ={\{ TR(L_{j})|∀L_{j}∈C_{i} \}}$定义。其中，$TR(L_{j})$表示从$L_{j}$中提取的轨迹，而$|PTR(C_{i})|$被称为簇$C_{i}$的轨迹基数。
• 最初，假定所有的线段都是未分类的。随着算法的进行，它们被分为簇或噪声。该算法包括如下三个步骤：
  • 第一步（第1∼12行）
    计算每个未分类线段$L$的$ε$邻域。如果$L$被确定为核心线段（第7∼10行），则算法执行第二步以展开簇（第9行）。当前的集群只包含$N_{ε}(L)$。
  • 第二步（第17∼28行）
    计算核心线段的密度连接集。$ExplandCluster ()$计算直接密度可达的线段（第19∼21行），并将它们添加到当前的集群（第22∼24行）。如果新添加的线段未分类，则它将被添加到队列$Q$中以获得更多的扩展，因为它可能是一个核心线段（第25∼26行）；否则，它不会被添加到$Q$中，因为它不可能是一个核心线段。
  • 第三步（第13∼16行）
    检查每个簇的轨迹基数。如果其轨迹基数低于阈值，则将过滤掉相应的聚类。
    
• 时间复杂度分析： 如果使用空间索引，该算法的时间复杂度为$O(nlogn)$，其中$n$是数据库中的线段总数。否则，对于高维$（≥2）$，该算法的时间复杂度为$O（n^{2}）$。
  分析该算法的第5行和第20行可得对每个线段都会执行一次$ε$-邻域查询。因此，该算法的时间复杂度为$n×（一次ε-邻域查询的时间复杂度）$。
• 该算法可以很容易地进行扩展，以支持带有权重的轨迹。例如，一个更强的飓风将有更大的质量，因此需要修改决定一个$ε$-邻域（即$|N_{ε}(L)|$）的基数的方式，通过计算线段的权重来计算加权计数。

本文的距离函数不是一个度量，因为它不服从三角形不等式，即存在$dist(L_{1}, L_{3}) > dist(L_{1}, L_{2}) + dist(L_{2}, L_{3})$。这使得直接应用传统的空间指标变得困难。本文没有提出该问题的解决方法。

一个集群的代表性轨迹

• 一个集群的代表性轨迹描述了属于该集群的轨迹分区的整体运动。它可以被认为是集群的一个模式。

  我们需要提取关于集群内运动的定量信息，以便领域专家能够理解轨迹中的运动。因此，为了从轨迹聚类中获得充分的实际潜力，绝对需要具有这种代表性的轨迹。

• 一个具有代表性的轨迹是一个点序列$RTR_{i}=p_{1}p_{2}p_{3}···p_{j}···p_{len_{i}}(1≤i≤num_{clus})$。这些点是通过使用扫描线的方法来确定的。当在集群的主轴方向上扫描一条横跨线段的垂直线时，计算到达扫描线的线段的数量，这个值只有当扫描线通过一个起点或一个终点时才会发生变化。如果这个数字等于或大于$MinLns$，则计算这些线段相对于主轴的平均坐标，并将平均值插入代表性轨迹；否则，跳过当前点（如下图中的第5和第6位置）。此外，如果前面的点位置太近（如下图中的第3位置），则跳过当前点来平滑具有代表性的轨迹。
  

• 为了表示集群的主轴，定义如下平均方向向量：

  • 假设一组向量$V={\{\overrightarrow{v_{1}}, \overrightarrow{v_{2}}, \overrightarrow{v_{3}}, \cdots, \overrightarrow{v_{n}}\}}$。$V$的平均方向向量$\overrightarrow{V}$的定义公式如下。其中，$|V|$是$V$的基数

    $$\overrightarrow{\mathcal{V}}=\frac{\overrightarrow{v_{1}}+\overrightarrow{v_{2}}+\overrightarrow{v_{3}}+\cdots+\overrightarrow{v_{n}}}{|\mathcal{V}|}$$

  上述公式将向量而不是它们的方向向量（即单位向量）相加，并对结果进行归一化处理，是一个很好的启发式方法，可以使一个较长的向量对平均方向向量贡献更大的效果。我们计算代表簇中每个线段的向量集合上的平均方向向量。

• 如上所述，我们计算相对于平均方向向量的平均坐标。为了便于计算，通过$\left[\begin{array}{l}x^{\prime} \\ y^{\prime}\end{array}\right]=\left[\begin{array}{cc}\cos \phi & \sin \phi \\ -\sin \phi & \cos \phi\end{array}\right]\left[\begin{array}{l}x \\ y\end{array}\right]$（旋转矩阵^[1]）旋转轴使X轴平行于平均方向向量。通过平均方向向量与单位向量$\hat{x}$之间的内积得到角$φ$。
  如下图所示，在计算出$X'Y'$坐标系中的平均值后，它被转换回$XY$坐标系中的一个点
  

• 具有代表性的轨迹生成算法
  首先，计算平均方向向量，并暂时旋转轴（第1∼2行）。
  然后，根据旋转轴的坐标（第3∼4行）对起点和终点进行排序。在按排序的顺序扫描起点和终点时，计算线段的数量，并计算这些线段的平均坐标（第5∼12行）。
  

关于参数值选择的启发式方法

在信息论中，熵与与给定概率分布相关的事件的不确定性量有关。如果所有的结果都是等可能的，那么熵应该是最大的。

• 作者通过观察发现：在最差的聚类中，$|N_{ε}(L)|$趋向于一致。也就是说，对于太小的$ε$，$|N_{ε}(L)|$对于几乎所有的线段都变成1；对于太大的$ε$，$|N_{ε}(L)|$对于几乎所有的线段都变成$num_{ln}$，其中，$num_{ln}$为行段总数。因此，熵成为最大的。相反，在一个较好的聚类中，$|N_{ε}(L)|$倾向于偏离的。因此，熵就变小了。

• 熵通过如下公式定义，

  $$\begin{gathered} H(X)=\sum_{i=1}^{n} p\left(x_{i}\right) \log_{2} \frac{1}{p\left(x_{i}\right)}=-\sum_{i=1}^{n} p\left(x_{i}\right) \log_{2} p\left(x_{i}\right) \\ \text { where } p\left(x_{i}\right)=\frac{\left|N_{\varepsilon}\left(x_{i}\right)\right|}{\sum_{j=1}^{n}\left|N_{\varepsilon}\left(x_{j}\right)\right|} \text { and } n=n u m_{l n} \end{gathered}$$

  通过模拟退火技术得到时$H(X)$最小化的$ε$的值

• 选择参数$MinLns$值的启发式方法过程： 首先，计算最优$ε$下$|N_{ε}(L)|$的平均$avg_{|N_{ε}(L)|}$。该操作不会产生额外的成本，因为它可以在计算$H(X)$时完成。然后，确定最优的$MinLns$为$(avg_{|N_{ε}(L)|}+1∼3)$，之所以如此，是因为$MinLns$应该大于$avg|N_{ε}(L)|$以发现有意义的集群。

通过本文的启发式方法估计的这些参数值是否是真正最优的是不明显的，但该启发式方法提供了一个合理的范围，其中可能存在最优值。可以尝试估计值附近的一些值，并通过目测选择最优值。

---

实验Experiment

实验设置

• 数据集： 飓风轨迹数据集和动物运动数据集

• 聚类质量度量： 平方误差和+噪声惩罚^[2]，公式如下：

  $$\begin{aligned} \text { QMeasure }=& \text { Total } S S E+\text { Noise Penalty } \\ =& \sum_{i=1}^{n u m_{clus}}\left(\frac{1}{2\left|C_{i}\right|} \sum_{x \in C_{i}} \sum_{y \in C_{i}} \operatorname{dist}(x, y)^{2}\right)+\\ & \frac{1}{2|\mathcal{N}|} \sum_{w \in \mathcal{N}} \sum_{z \in \mathcal{N}} \operatorname{dist}(w, z)^{2} \end{aligned}$$

  其中，$\mathcal{N}$表示所有噪声线段的集合，目的是获得聚类质量

实验结果

飓风跟踪数据的结果

• 下图显示了$ε$变化时熵的变化，在$ε=31$时达到了最小值，$avg|N_{ε}(L)|=4.39$。
  根据启发式方法，对$ε=31$和$MinLns=5∼7$附近的参数值进行尝试，利用目测和领域知识，得到最优的参数值为$ε=30$和$MinLns=6$。注意到，最优值$ε=30$非常接近于估计值$ε=31$。
  
• 下图显示了$ε$和$MinLns$变化时质量度量的变化。质量度量越小，聚类质量就越好。
  实际的集群质量和作者的度量结果之间有一点差异。目测结果显示，最好的聚类是在$MinLns=6$时，而不是在$MinLns=5$。然而，作者的度量被证明在相同的$MinLns$值内是一个很好的实际聚类质量的指标。也就是说，如果只考虑$MinLns=6$的结果，可以看到，当使用$ε$的最优值时，度量结果几乎变得最小。
  
• 下图显示了使用最优参数值进行的聚类结果。其中，绿色的细线表示轨迹，粗的红色线表示代表性轨迹。
  这些具有代表性的轨迹正是共同的子轨迹，而集群的数量即为红线的数量。
  
  该结果与现实中飓风的移动情况较为贴切，是相当合理的。

动物运动数据的结果

1993年的麋鹿运动

• 下图显示了$ε$变化时熵的变化。在$ε=25$处达到最小值，$avg|N_{ε}(L)|=7.63$。
  在视觉上，得到的最优参数值为$ε=27$和$MinLns=9$。同样，最优值$ε=27$非常接近于估计值$ε=25$。
  
• 下图显示了$ε$和$MinLns$变化时质量度量的变化。
  由图可知：当使用最优参数值时，度量结果几乎变得最小；实际集群质量与度量之间的相关性比飓风数据的更强。
  
• 下图显示了使用最优参数值进行的聚类结果。
  虽然右上角的区域看起来很密集，但麋鹿实际上是沿着不同的路径移动的。因此，在该区域中没有集群的结果被验证是正确的。
  

1995年的鹿运动

• 下图显示了使用最优参数值（$ε=29和MinLns=8$）的聚类结果。
  结果表明，在两个最密集的区域中发现了两个集群，该结果正是所期望的。
  

参数值的影响

• 如果使用更小的$ε$或更大的$MinLns$，该算法会发现更多的更小的集群（即有更少的线段）。相反，如果使用更大的$ε$或更小的$MinLns$，该算法会发现更少的更大的集群。

---

讨论Discussion

该算法的一些可能拓展：

• 可扩展性： 支持无向的或加权的轨迹，使用简化角距离来处理无向轨迹，使用$ε$邻域的扩展基数处理加权轨迹。
• 参数不敏感性： 使该算法对参数值更不敏感。如将$OPTICS$算法应用于轨迹数据。
• 效率： 通过使用索引来进行$ε$-邻域查询以提高聚类性能。主要的困难是本文的距离函数不是一个度量标准。
• 运动模式： 扩展该算法以支持各种类型的运动模式，特别是圆周运动。该扩展可以通过增强生成一个具有代表性的轨迹的方法来实现。
• 时间信息： 在聚类过程中考虑时间信息。

---

1. 1.为了便于阐述，假设为两个维度，该方法也可以应用于三维空间 ↩
2. 2.惩罚错误分类 ↩