GPS轨迹聚类算法TRACLUS介绍（一）

算法TRACLUS介绍（一）"/>

GPS轨迹聚类算法TRACLUS介绍（一）

在自研众包地图方案过程中，作为主机厂，会获得大量的车辆GPS轨迹，这些轨迹信息可是众包地图的重要数据来源之一，整体策略是在图商的底图基础上再结合车辆GPS轨迹进行引导线更新。实际自动驾驶L4场景开发过程中发现：实车跑过的轨迹线远比算法生成的引导线合理，尤其是转弯掉头等场景引导线。
这篇文章，将对论文 Trajectory Clustering: A Partition-and-Group Framework（轨迹聚类：一种分段归组的框架）做出解读。

综述

聚类是将一组物理对象或抽象对象分组为相似对象的类的过程。具有代表性的算法有K-means、DBSCAN、BIRCH、OPTICS和STING。而以往的研究主要都是关于点云数据的聚类。随着对车辆轨迹、飓风轨迹等研究，对轨迹聚类算法的研究越来越多。
现有的轨迹聚类算法是将相似的轨迹作为一个整体进行聚类，从而发现共同的轨迹。但是这样容易错过一些共同的子轨迹（sub-trajectories）。而在实际中，当我们对特殊感兴趣的区域进行分析时，子轨迹就特别重要。以下图为例

图中有五条轨迹，在矩形中有一个共同的行为，用粗箭头表示。然而，如果我们将这些轨迹作为一个整体来聚类，我们就无法发现共同的行为，因为它们向完全不同的方向移动；因此，我们错过了这些有价值的信息。
本文的解决方法“分段归组框架”（TRACLUS算法）是先将轨迹分段成线段，然后再对线段进行聚类，可以更准确地发现子轨迹。
算法步骤：分段（partitioning）和归组（grouping）。

1. 分段阶段。利用最小描述长度（minimum description length MDL）原理实现轨迹分段，将每一条轨迹最优的分为一组线段，这些线段输入到下一阶段。
2. 归组阶段。利用基于密度的线段聚类算法实现相似线段聚类。仔细地设计了一个距离函数来定义线段的密度。此外，还提供了一个简单而有效的启发式方法来确定该算法的参数值。

基于密度的聚类方法是最适合用于线段的，因为它们可以发现任意形状的聚类，并可以滤波出噪声。我们可以很容易地看到，线段簇通常是任意形状的，而轨迹数据库通常包含大量的噪声（即异常值）。

在后面的博客中，将针对介绍论文算法的三个部分：
TRACLUS轨迹聚类算法的概要GPS轨迹聚类算法TRACLUS介绍（二）
第一阶段的轨迹分段算法GPS轨迹聚类算法TRACLUS介绍（三）
第二阶段的线段聚类算法GPS轨迹聚类算法TRACLUS介绍（四）