在自研众包地图方案过程中，作为主机厂，会获得大量的车辆GPS轨迹，这些轨迹信息可是众包地图的重要数据来源之一，整体策略是 在图商的底图基础上再结合车辆GPS轨迹进行引导线更新。实际自动驾驶L4场景开发过程中发现： 实车跑过的轨迹线远比算法生成的引导线合理，尤其是转弯掉头等场景引导线。
这篇文章，将对论文 Trajectory Clustering: A Partition-and-Group Framework（轨迹聚类：一种分段归组的框架）做出解读。
综述
聚类是将一组物理对象或抽象对象分组为相似对象的类的过程。具有代表性的算法有 K-means、 DBSCAN、 BIRCH、 OPTICS_和 _STING。而以往的研究主要都是关于点云数据的聚类。随着对车辆轨迹、飓风轨迹等研究，对轨迹聚类算法的研究越来越多。
现有的轨迹聚类算法是 将相似的轨迹作为一个整体进行聚类，从而发现共同的轨迹。但是这样 容易错过一些共同的子轨迹（ sub-trajectories）。而在实际中，当我们对特殊感兴趣的区域进行分析时，子轨迹就特别重要。以下图为例
图中有五条轨迹，在矩形中有一个共同的行为，用粗箭头表示。然而，如果我们将这些轨迹作为一个整体来聚类，我们就无法发现共同的行为，因为它们向完全不同的方向移动；因此，我们错过了这些有价值的信息。
本文的解决方法” 分段归组框架“（ TRACLUS算法）是 先将轨迹分段成线段，然后再对线段进行聚类，可以更准确地发现子轨迹。
算法步骤： 分段（ partitioning ）和归组（ grouping ）。
- 分段阶段。利用 最小描述长度（ minimum description length MDL）原理实现轨迹分段，将每一条轨迹最优的分为一组线段，这些线段输入到下一阶段。
- 归组阶段。利用 基于密度的线段聚类算法实现相似线段聚类。仔细地设计了一个 距离函数来定义线段的密度。此外，还提供了一个简单而有效的 启发式方法来确定该算法的参数值。
基于密度的聚类方法是最适合用于线段的，因为它们可以发现任意形状的聚类，并可以滤波出噪声。我们可以很容易地看到，线段簇通常是任意形状的，而轨迹数据库通常包含大量的噪声（即异常值）。
在后面的博客中，将针对介绍论文算法的三个部分：
TRACLUS轨迹聚类算法的概要GPS轨迹聚类算法TRACLUS介绍（二）
第一阶段的轨迹分段算法GPS轨迹聚类算法TRACLUS介绍（三）
第二阶段的线段聚类算法GPS轨迹聚类算法TRACLUS介绍（四）
Original: https://blog.csdn.net/weixin_43891708/article/details/121374396
Author: NieBP
Title: GPS轨迹聚类算法TRACLUS介绍（一）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/597690/
转载文章受原作者版权保护。转载请注明原作者出处！