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

这篇具有很好参考价值的文章主要介绍了论文笔记: Trajectory Clustering: A Partition-and-Group Framework。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

07 Sigmoid

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

1 intro

1.1 轨迹聚类

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

1.2  本文的思路

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

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

2 问题定义

  • 输入一组轨迹
    • 一条轨迹是一组点的集合,其中每一个点pj是一个d维的点(坐标),leni是这条轨迹的长度(点的数量)
    • 轨迹TRi的一条子轨迹是
  • 输出:一组线段聚类和每个线段聚类Ci的代表性轨迹
    • 一个cluster中是一组轨迹分段
      • 一个轨迹分段是一条线段,其中pi和pj都是从同一条轨迹中选择的点
    • 一条轨迹中的轨迹分段可能属于不同的多个聚类

3 模型

3.1 整体模型

3.2 轨迹距离函数

  • 对点集做聚类时,常用方法就是根据两点之间的欧氏距离来判断是否一类。
  • 在线段聚类时,论文使用的距离函数是由三个部分组成
    • 垂直距离
    • 平行距离
    • 角度距离

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

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

 3.2 轨迹分段

  • 轨迹分段的首要目标是找到轨迹行为迅速变化的点(就是角度变化大的点),称之为特征点。
    • 从轨迹中确定了一组特征点
    • 然后轨迹TRi分每个特征点分段,每个分段用两个连续特征点所连的线段表示
    • ——>TRi被分成一组(pari-1)个轨迹分段
  • 论文笔记: Trajectory Clustering: A Partition-and-Group Framework

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)是描述利用压缩模型所编码的数据所需要的长度
  • 类比到轨迹分段中,如下:
    • 论文笔记: Trajectory Clustering: A Partition-and-Group Framework
    • L(D|H)只考虑角度距离和垂直距离,不考虑平行距离
  •  假设一条轨迹,一组特征点

    • L(H)表示为论文笔记: Trajectory Clustering: A Partition-and-Group Framework

    • L(D|H)表示为:论文笔记: Trajectory Clustering: A Partition-and-Group Framework

      ——>因此,要得到最优的分段策略,那就是要最小MDL= L(H)+L(D|H),这能够准确平衡简洁性和准确性

3.2.3 近似计算方法

  • 但是因为要考虑到轨迹点的每一个子集,所以计算量是非常大
    • 论文引入一个近似计算的方法,关键思想是将局部最优的集合视为全局最优
  • 记表示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

算法如下

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

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

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

3.3 聚类 

3.3.1 基于密度聚类的概念

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

  • 几个notation:
    • D是所有线段的集合
    • epsilon是两个线段距离的一个阈值
    • MinLns是聚类集合的最小线段数量
线段的ε邻域

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

核心线段

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

核心线段就是,和线段Li相距小于ε的线段数量 大于MinLns条

对比DBSCAN相应概念:如果数据点周围至少包含“minPoints”个点,则该数据点是核心点

直接密度可达

Lj是核心线段+Li在Lj的ε邻域内——>Li直接密度可达Lj

对比DBSCAN相应概念:

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

密度可达

存在一组线段论文笔记: Trajectory Clustering: A Partition-and-Group Framework

其中Lk直接密度可达论文笔记: Trajectory Clustering: A Partition-and-Group Framework(即论文笔记: Trajectory Clustering: A Partition-and-Group Framework是核心线段)

那么Li密度可达Lj

对比DBSCAN相应概念:

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

密度连接

当存在一个核心点Lk,使得线段Li和线段Lj都密度可达Lk

那么Li 密度连接Lj

对比DBSCAN概念:

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

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

 

3.3.2 密度连接集

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

3.3.3 线段聚类方法

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

  • 有别于DBSCAN的就是14~16行,即并非所有的密度连接集都是一个线段聚类
    • 需要考虑这一簇的线段是从几条轨迹中得来的,如果小于阈值,那么这一簇线段不能被视为一个聚类
      • 举一个极端情况,一个簇中所有的线段都是从一个轨迹中提取出来的
    • ——>14~16行就是校验一个簇中轨迹的基数

3.3.4 聚类算法的扩展

  • 每条线段可以有自己的权重
    • ——>此时可以修改 确定ε邻域基数 的方法,不再是简单地计算线段数量,而是计算线段的加权数量

 

参考内容:

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

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

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

GPS轨迹聚类算法TRACLUS介绍(四)_NieBP的博客-CSDN博客文章来源地址https://www.toymoban.com/news/detail-456517.html

到了这里,关于论文笔记: Trajectory Clustering: A Partition-and-Group Framework的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 论文笔记:TRANSIT: Fine-grained human mobility trajectory inference at scalewith mobile network signalin

    Type C 2021 来自移动网络运营商的通话详单(CDR)作为一种较新的移动性数据,已经被用来: 推导人类移动的一般法则 建立OD 矩阵 推断人口密度变化 理解城市土地使用情况 CDR呈现了一种独特的可取特性组合: 提供了前所未有的渗透率,因为它们适用于网络提供商的整个订户

    2024年02月19日
    浏览(35)
  • 论文阅读1--A Survey on Incomplete Multi-view Clustering(不完全多视图聚类的调查)阅读笔记

    目录 写在前面(知识补充) 0.Abstract 1.Introduction 2. FUNDAMENTALS AND PRELIMINARY CONCEPTS 3. MATRIX FACTORIZATION BASED IMC(基于矩阵分解的IMC) 4. KERNEL LEARNING BASED IMC(基于内核学习的IMC) 5.GRAPH LEARNING BASED IMC(基于图学习的IMC) 6.DEEP LEARNING BASED IMC(基于深度学习的IMC) 7. EXPERIMENTS(实验部分)

    2024年02月05日
    浏览(60)
  • Geometrically Constrained Trajectory Optimization for Multicopters 论文解析

    《Geometrically Constrained Trajectory Optimization for Multicopters》一文由浙江大学博士 汪哲培 2022年发表在IEEE, 涉及到这篇论文地内容,由汪哲培在 Bilibili 做了介绍:论文相关介绍 关于几何约束多旋翼轨迹规划,属于路径规划地后端优化,论文的实验实现比现有的其他路径生成算法的

    2024年02月16日
    浏览(42)
  • GPT学习笔记-聚类(clustering)

    聚类是一种非常有用的无监督学习技术,它的主要目的是发现数据的内在结构和模式。在许多实际应用中,我们可能没有明确的目标变量或预测目标,但我们仍希望了解数据的组织方式,或者找出数据中的特定模式或组。这就是聚类的价值所在。 尽管聚类是无监督的(即我们

    2024年02月06日
    浏览(39)
  • Trajectory-guided Control Prediction for End-to-end Autonomous Driving论文学习

    端到端自动驾驶方法直接将原始传感器数据映射为规划轨迹或控制信号,范式非常简洁,从理论上避免了多模块设计的错误叠加问题和繁琐的人为规则设计。当前的端到端自动驾驶方法主要有两条独立的研究路线,要么基于规划轨迹来运行控制器,要么直接预测控制信号。端

    2024年02月05日
    浏览(55)
  • 吴恩达机器学习笔记:第 8 周-13 聚类(Clustering)13.1-13.2

    在这个视频中,我将开始介绍聚类算法。这将是一个激动人心的时刻,因为这是我们学习的第一个非监督学习算法。我们将要让计算机学习无标签数据,而不是此前的标签数据。 那么,什么是非监督学习呢?在课程的一开始,我曾简单地介绍过非监督学习,然而,我们还是有

    2024年04月22日
    浏览(52)
  • 论文阅读Point Transformer V2: Grouped Vector Attention and Partition-based Pooling

    Point transformer v2。 香港大学2022 在PCT的基础上进一步改进的点云处理方法,通过分组向量注意力(Grouped Vector Attention)和基于划分的池化机制,提高了对点云特征的提取和聚合能力,并在轻量级上有了新的突破。 总体来看: 1.点云网格化:将点云划分成大小相等的小块,对每个小

    2024年01月22日
    浏览(42)
  • 知识笔记(八十九)———链式语句中partition和strict用法

    partition 方法用于是数据库水平分表 注意:不要使用任何 SQL 语句中会出现的当表名、字段名,例如 order 等。会导致数据模型拼装 SQL 语句语法错误。 partition 方法用法如下: 再者就是: strict 方法用于设置是否严格检查字段名,用法如下: 注意,系统默认值是由数据库

    2024年01月21日
    浏览(41)
  • 分层聚类(Hierarchical clustering)

    简介 分层聚类算法试图建立一个聚类的层次结构,有两类: 聚合型(agglomerative)和分裂型(divisive) 。聚合法最初将每个数据点作为一个单独的聚类,然后迭代合并,直到最后的聚类中包含所有的数据点。它也被称为自下而上的方法。分裂聚类遵循自上而下的流程,从一个拥有所

    2024年02月05日
    浏览(37)
  • 22 谱聚类——Spectral Clustering

    我们在一般的聚类过程中,普遍理性而言会有两种思想: 将聚集在一起的点进行聚类(离得近的为同一类数据),例如可以线性分类的一组数据。 将具有联通性的一堆点进行聚类,如环形等线性不可分的数据。(这种其实在一定情况下也可以通过Kernel+K-Mean实现——进行非线

    2024年02月10日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包