论文笔记： Trajectory Clustering: A Partition-and-Group Framework

07 Sigmoid

使用类DBSCAN的思路对轨迹聚类

1 intro

1.1 轨迹聚类

现有的轨迹聚类算法是将相似的轨迹作为一个整体进行聚类，从而发现共同的轨迹。
- 但是这样容易错过一些共同的子轨迹（sub-trajectories）。
- 而在实际中，当我们对特殊感兴趣的区域进行分析时，子轨迹就特别重要。
- 图中有五条轨迹，在矩形中有一个共同的行为，用粗箭头表示。
- 如果我们将这些轨迹作为一个整体来聚类，我们就无法发现共同的行为，因为它们最终向完全不同的方向移动
  - ——》作为一个整体来聚类会错过很多有价值的信息。

本文提出TRACLUS算法，先将轨迹分段成线段，然后再对线段进行聚类，可以更准确地发现子轨迹。
算法步骤分为分段（partitioning）和归组（grouping）
- 分段利用最小描述长度（minimum description length MDL）原理实现轨迹分段，将每一条轨迹最优的分为一组线段，这些线段输入到下一阶段。
- 归组利用基于密度的线段聚类算法实现相似线段聚类。设计了一个距离函数来定义线段的密度。
  - ——>基于密度的聚类方法是最适合用于线段的，因为它们可以发现任意形状的聚类，并可以滤波出噪声。可以很容易地看到，线段簇通常是任意形状的，而轨迹数据库通常包含大量的噪声

输入一组轨迹
- 一条轨迹是一组点的集合 $TR_i=p_1p_2\cdots p_{len_i}$ ，其中每一个点pj是一个d维的点（坐标），leni是这条轨迹的长度（点的数量）
- 轨迹TRi的一条子轨迹是 $\mathrm{p}_{\mathrm{c}_1} \mathrm{p}_{\mathrm{c}_2} \cdots \mathrm{p}_{\mathrm{c}_{\mathrm{k}}}\left(1 \leq \mathrm{c}_1<\mathrm{c}_2<\cdots<\mathrm{c}_{\mathrm{k}}<\operatorname{len}_{\mathrm{i}}\right)$
输出：一组线段聚类和每个线段聚类Ci的代表性轨迹
- 一个cluster中是一组轨迹分段
  - 一个轨迹分段是一条线段 $p_ip_j (i<j)$ ,其中pi和pj都是从同一条轨迹中选择的点
- 一条轨迹中的轨迹分段可能属于不同的多个聚类

轨迹分段的首要目标是找到轨迹行为迅速变化的点（就是角度变化大的点），称之为特征点。
- 从轨迹 $TR_i=p_1p_2\cdots p_{len_i}$ 中确定了一组特征点 $\left\{\mathrm{p}_{\mathrm{c}_1}, \mathrm{p}_{\mathrm{c}_2}, \mathrm{p}_{\mathrm{c}_3}, \cdots, \mathrm{p}_{\mathrm{c}_{\mathrm{par}}}\right\}\left(\mathrm{c}_1<\mathrm{c}_2<\mathrm{c}_3<\cdots<\mathrm{c}_{\mathrm{par}_{\mathrm{i}}}\right)$
- 然后轨迹TRi分每个特征点分段，每个分段用两个连续特征点所连的线段表示
- ——>TRi被分成一组(pari-1)个轨迹分段 $\{p_{c_1}p_{c_2},p_{c_2}p_{c_3},\cdots,p_{c_{par_{i-1}}c_{par}}\}$

最小描述长度( MDL) 原理是通用编码领域研究的内容。
- 基本原理是对于一组给定的数据 D ，如果要对其进行保存，为了节省存储空间，一般采用某种模型对其进行编码压缩，然后再保存压缩后的数据。
- 同时，为了以后正确恢复这些实例数据，将所用的模型也保存起来。
- ——>所以需要保存的数据长度( 比特数) 等于 数据进行编码压缩后的长度 加上 保存模型所需的数据长度，将该数据长度称为总描述长度。
- 最小描述长度( MDL) 原理就是要求选择总描述长度最小的模型
MDL的代价有两部分L(H)和L(D|H)
- H代表压缩模型，D代表数据
- L(H)是描述压缩模型（或编码方式）所需要的长度
- L(D∣H)是描述利用压缩模型所编码的数据所需要的长度
类比到轨迹分段中，如下：
- L(D|H)只考虑角度距离和垂直距离，不考虑平行距离
假设一条轨迹 $TR_i=p_1p_2\cdots p_{len_i}$ ，一组特征点 $\left\{\mathrm{p}_{\mathrm{c}_1}, \mathrm{p}_{\mathrm{c}_2}, \mathrm{p}_{\mathrm{c}_3}, \cdots, \mathrm{p}_{\mathrm{c}_{\mathrm{par}}}\right\}\left(\mathrm{c}_1<\mathrm{c}_2<\mathrm{c}_3<\cdots<\mathrm{c}_{\mathrm{par}_{\mathrm{i}}}\right)$
- L(H)表示为
- L(D|H)表示为：
  
  ——>因此，要得到最优的分段策略，那就是要最小MDL= L(H)+L(D|H)，这能够准确平衡简洁性和准确性

但是因为要考虑到轨迹点的每一个子集，所以计算量是非常大
- 论文引入一个近似计算的方法，关键思想是将局部最优的集合视为全局最优
记 $MDL_{par}(p_i,p_j)$ 表示pi和pj是路径分段pipj之间仅有特征点时（也就是pipj之间的子线段都划归到pipj线段上了），pipj二者之间轨迹的MDL
记表示pi和pj之间没有特征点时的MDL
- 此时pipj之间就是原始轨迹，所以只有L(H)，没有L(D|H)
局部最优解是：当满足对于任意i<k≤j的k，都有时的最长pipj
- 不等式的意思是：pi~pk的点，视作pipk轨迹分段对应的MDL，比pipk的点保持为原始轨迹对应的MDL小
  - 也就是说pipk是一个最优分段
  - 换句话说就是pk作为特征点的MDL比不作为特征点的代价小，那么pk可以成为一个特征点
- 局部最优解找的就是距离i最远的、可以作为特征点的点j

算法如下

所以此时p4就是局部最优解

将DBSCAN中关于点的聚类扩展到关于线段的聚类

线段 $L_i \in D$ 的ε邻域
核心线段	核心线段就是，和线段Li相距小于ε的线段数量大于MinLns条对比DBSCAN相应概念：如果数据点周围至少包含“minPoints”个点，则该数据点是核心点
直接密度可达	Lj是核心线段+Li在Lj的ε邻域内——>Li直接密度可达Lj 对比DBSCAN相应概念：
密度可达	存在一组线段 $L_i,L_{i+1},L_{i+2},\cdots,L_{j-1},L_j$ 其中Lk直接密度可达 $L_{k+1}$ （即 $L_{k+1}$ 是核心线段）那么Li密度可达Lj 对比DBSCAN相应概念：
密度连接	当存在一个核心点Lk，使得线段Li和线段Lj都密度可达Lk 那么Li 密度连接Lj 对比DBSCAN概念： ,mn

有别于DBSCAN的就是14~16行，即并非所有的密度连接集都是一个线段聚类
- 需要考虑这一簇的线段是从几条轨迹中得来的，如果小于阈值，那么这一簇线段不能被视为一个聚类
  - 举一个极端情况，一个簇中所有的线段都是从一个轨迹中提取出来的
- ——>14~16行就是校验一个簇中轨迹的基数
  - $|PTR(C_i)|=|\{TR(Lj)| \forall Lj \in C_i\}|$