论文笔记： Trajectory Clustering: A Partition

您所在的位置：网站首页 › 轨迹最准确的运动手表软件 › 论文笔记： Trajectory Clustering: A Partition

论文笔记： Trajectory Clustering: A Partition

2023-06-01 23:40| 来源: 网络整理| 查看: 265

07 Sigmoid

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

1 intro 1.1 轨迹聚类现有的轨迹聚类算法是将相似的轨迹作为一个整体进行聚类，从而发现共同的轨迹。但是这样容易错过一些共同的子轨迹（sub-trajectories）。而在实际中，当我们对特殊感兴趣的区域进行分析时，子轨迹就特别重要。

图中有五条轨迹，在矩形中有一个共同的行为，用粗箭头表示。如果我们将这些轨迹作为一个整体来聚类，我们就无法发现共同的行为，因为它们最终向完全不同的方向移动 ——》作为一个整体来聚类会错过很多有价值的信息。

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

2 问题定义输入一组轨迹 $L=\{TR_1,\cdots,TR_{num_{tra}}\}$ 一条轨迹是一组点的集合 $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)$ 输出：一组线段聚类 $O=\{C_1,\cdots,C_{num_{clus}}\}$ 和每个线段聚类Ci的代表性轨迹一个cluster中是一组轨迹分段一个轨迹分段是一条线段 $p_ip_j (ij)$ ,其中pi和pj都是从同一条轨迹中选择的点一条轨迹中的轨迹分段可能属于不同的多个聚类 3 模型 3.1 整体模型 3.2 轨迹距离函数对点集做聚类时，常用方法就是根据两点之间的欧氏距离来判断是否一类。在线段聚类时，论文使用的距离函数是由三个部分组成垂直距离 $d_\perp$ 平行距离 $d_{||}$ 角度距离 $d_\theta$

3.2 轨迹分段轨迹分段的首要目标是找到轨迹行为迅速变化的点（就是角度变化大的点），称之为特征点。从轨迹 $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}}\}$

3.2.1 轨迹分段原则一个轨迹的最优分段要具有两个属性：准确性轨迹与其一组轨迹分段之间的差异应该尽可能小 ——>特征点不能太少。简洁性轨迹分段的数量应该尽可能少这两个属性在确定特征点数目时是相互矛盾的，这就需要调整算法以达到平衡 3.2.2 最小描述长度原则（Minimum Description Length，MDL）最小描述长度( 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)，这能够准确平衡简洁性和准确性

3.2.3 近似计算方法但是因为要考虑到轨迹点的每一个子集，所以计算量是非常大论文引入一个近似计算的方法，关键思想是将局部最优的集合视为全局最优记 $MDL_{par}(p_i,p_j)$ 表示pi和pj是路径分段pipj之间仅有特征点时（也就是pipj之间的子线段都划归到pipj线段上了），pipj二者之间轨迹的MDL记 $MDL_{nopar}(p_i,p_j)$ 表示pi和pj之间没有特征点时的MDL 此时pipj之间就是原始轨迹，所以只有L(H)，没有L(D|H)局部最优解是：当满足对于任意iLi直接密度可达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

3.3.2 密度连接集

3.3.3 线段聚类方法

有别于DBSCAN的就是14~16行，即并非所有的密度连接集都是一个线段聚类需要考虑这一簇的线段是从几条轨迹中得来的，如果小于阈值，那么这一簇线段不能被视为一个聚类举一个极端情况，一个簇中所有的线段都是从一个轨迹中提取出来的——>14~16行就是校验一个簇中轨迹的基数 $|PTR(C_i)|=|\{TR(Lj)| \forall Lj \in C_i\}|$ 3.3.4 聚类算法的扩展每条线段可以有自己的权重 ——>此时可以修改确定ε邻域基数 $|N_\epsilon(L)|$ 的方法，不再是简单地计算线段数量，而是计算线段的加权数量

参考内容：

GPS轨迹聚类算法TRACLUS介绍（一）_NieBP的博客-CSDN博客

GPS轨迹聚类算法TRACLUS介绍（二）_traclus-master_NieBP的博客-CSDN博客

GPS轨迹聚类算法TRACLUS介绍（三）_NieBP的博客-CSDN博客

GPS轨迹聚类算法TRACLUS介绍（四）_NieBP的博客-CSDN博客

【本文地址】

论文笔记： Trajectory Clustering: A Partition

论文笔记： Trajectory Clustering: A Partition

今日新闻

推荐新闻