E2DTC：通过自训练实现的端到端深度轨迹聚类框架

时空实验室 2022-08-22

1676

轨迹聚类在轨迹数据挖掘中有重要作用，现有的聚类算法通常利用轨迹的时空特征在传统的聚类算法基础上扩展，这会存在不能捕获隐藏信息、依赖于手工相似度指标、算法不灵活等问题。本文带来国际顶级会议ICDE 2021上的论文：《E²DTC: An End to End Deep Trajectory Clustering Framework via Self-Training》

一．背景

随着GPS设备和移动计算服务的普及，大量的轨迹数据被收集以捕捉事物的移动性。而轨迹聚类在轨迹挖掘任务中发挥了重要作用，它服务于广泛的现实生活应用，包括交通、基于位置的服务、行为研究等。为了支持轨迹聚类分析，人们提出了大量的轨迹聚类方法，但主要是利用轨迹的时空特征来扩展传统的聚类算法。这种算法首先采用现有的或修改过的距离度量来计算轨迹之间的相似性，然后再应用经典的聚类技术(如k-means)来进行轨迹聚类。然而，它存在以下三个问题：一是不能捕获轨迹数据中隐藏的空间信息。传统的轨迹聚类方法受限于基于原始轨迹的表示（如轨迹点，轨迹段等），而轨迹在生活中以GPS坐标的形式采集，当采样率较低或不均匀时，GPS点不足以表示形式为连续曲线的真实轨迹。二是高度依赖于手工相似度指标。对于距离的度量方式，有的只关注局部特征（即基于点），或只关注轨迹之间的全局关系（即基于形状），这使得应用于不同数据集会有相差很大的性能效果。三是聚类效率低且不灵活，不同数据集有不同的空间特征，传统的轨迹聚类无法支持各种各样的轨迹数据集。

本文提出了一种通过自训练实现的端到端深度轨迹聚类框架，称为E²DTC。受到深度神经网络数据驱动能力的启发，它使用基于神经网络的深度学习表示的轨迹，将原始轨迹嵌入向量，捕获轨迹数据的隐藏信息。而且E²DTC不需要任何额外的手动特征提取操作，还可以很容易地应用于任何轨迹数据集上的轨迹聚类分析。本文最后在三个真实数据集上进行了广泛实验，评估结果表明，E²DTC框架性能优越，可伸缩性好，稳定性强。

二．基本框架

图1 E²DTC基本框架

1.原始轨迹数据的嵌入

流程：原始轨迹->离散的元素序列->空间嵌入的向量

轨迹通常表示为GPS点的时间序列T = {p₁, p₂, . . . , p_|_T_|}，点p_i由空间坐标（即经纬度）及时间戳组成。首先，将轨迹T转换为离散元素的序列，此过程称为轨迹离散化。离散化策略是轨迹数据分析中一种常见方法，即将整个空间划分为不相交的等大小单元格，每个单元格用一个词汇ID标记，所有的单元格构成空间词汇表V。于是，每个GPS点被转换为其所在单元格的ID，原始轨迹T则被转换为一系列词汇ID。

然后，用skip-gram模型学习这些点的表示，并使得

最大。其中，g_t为当前单元格，g_t+j为g_t的相邻单元格，c为相邻单元格数。而两个相邻的单元格应该具有相似的表示形式，该概率可以使用softmax函数计算为

,其中，v_gt表示g_t的向量表示。

至此，原始轨迹T可以转换为空间嵌入向量v_T，即T→v={v_g1，···，v_gt，···，v_g_|_T_|}。

2.预训练

首先使用编码器将轨迹转化进潜在空间(即T→v_T)，然后使用解码器将深度轨迹表示重构到自然数据空间(即v_T→T')。这里，T和T'分别表示输入和学习目标。

本文遵循t2vec方法，在训练过程中减少数据点并增加噪声，这种方法已被证明能有效地捕获复杂轨迹的空间依赖性。具体来说，给定一个轨迹Ta，先以采样率r₁从Ta中随机抽取采样点，得到一个低采样的轨迹Tc。后以扭曲率r₂对Tc进行畸变，得到T'a。畸变是指以r₂在Tc中采样点，然后对每个采样点添加一个高斯噪声。至此，可以得到一个轨迹对的集合(T'a，Ta)。将T'a作为为输入，Ta为学习目标。

因为要考虑轨迹数据的空间关系，这里运用的损失函数是基于单元格权重的空间接近度感知损失Lr：

。其中，W^T是将h_t从潜在空间投射到词汇表空间的投影矩阵，W_gt为单元格权重，计算公式为

，g_t和g'_t表示预测的单元格和真实单元格。v_gt和v_g't是他们对应的向量表示。为了在不影响性能的情况下降低计算成本，这里使用的范围是g'_t的k个最近邻，而不是词汇表V中的所有单元格。

至此，我们可以得到形成深度轨迹表示v的非线性映射（即fθ：O→Z，将每个原始轨迹T∈O转换为轨迹表示v_T∈ Z的映射）的初始估计。基于初始轨迹嵌入，在特征空间Z中应用标准的k-means聚类算法，得到k个初始簇质心

。

3.自训练

有了第二阶段的非线性映射fθ和簇质心

的初始估计，第三阶段通过自我训练，我们可以迭代地改进整体聚类，细化轨迹聚类分配，使聚类更具鉴别性。主要由以下四个部分构成。

（1）软分配。计算每个深度嵌入轨迹v_T的软分配，即分配到每个簇的概率，并使用t-分布来衡量每个v_T和簇质心C_j之间的相似性，公式如下：

，q_ij表示将轨迹T_i分配给簇j的概率。

（2）目标计算。计算比软分配概率分布q更严格的辅助目标分布p。目的是提高聚类纯度和置信度，这可以防止大簇扭曲隐藏的特性空间，计算公式如下：

。

（3）聚类目标损失。借助辅助目标分布，学习高置信度分配来迭代地优化集群。也就是说，E²DTC是通过匹配软分配到目标分布来训练的。因此，将软分配q和辅助目标分布p之间的发散度作为聚类目标损失Lc：

。并且，利用Adam随机梯度下降联合优化聚类质心C_j和神经网络参数θ，以最小化聚类损失。

（4）三元组损失。为了生成更多分离的簇，同时使同一簇中的元素更紧密，本文进一步应用三元组损失来提高聚类质量。三元组即给定三个样本（anchor， positive，negative），使相似身份（anchor， positive）之间的特征距离应该尽可能小，不同身份（anchor，negative）之间的特征距离应该尽可能大。这是第一次尝试在轨迹聚类任务中使用三元组损失，其公式为：

。其中，v_i^a是嵌入轨迹作为anchor，v_i^p是v_i^a周围的噪声点作为positive，v_iⁿ是其余的点作为negative。

最终，E²DTC整体损失函数为：

，L_r捕获了输入的隐藏特征，L_c促进了形成聚类结构的表示，而L_t增强了编码器的聚类能力。

三．实验

1.地面真实生成算法

现有的轨迹聚类方法多注重提高效率和可伸缩性，很少关注对聚类质量的评价，而目前还没有带有空间聚类标签的公共轨迹数据集。因此，本文设计了一个地面真实生成算法，包含簇中心选择和簇标签分配两个步骤。首先，可视化所有的轨迹，选择某些最常访问的POI作为簇中心。由于轨迹在不同时间下可能不同，由此设置了两个参数，半径比σ控制集群的边界，阈值λ用来决定一个轨迹是否属于一个集群。分配时若轨迹Ti位于簇区域Cj中的百分比超过λ，就将该轨迹分配给簇Cj。

2.实验设置

本文将E²DTC模型与经典方法K-Medoids（EDR + KM，LCSS + KM，DTW + KM，Hausdorff + KM），基于神经网络的方法t2vec + k-means 五者进行比较。使用GeoLife（GPS信息），Porto（出租车旅行数据），Hangzhou（出租车轨迹）三个数据集，并用地面生成算法生成带聚类标签的地面真实数据集。衡量标准为无监督聚类精度UACC（度量聚类结果和地面真实之间的差异）、归一化交互信息NM（接近1表示聚类质量高)和rand指数RI（聚类正确预测的百分比）。

3.实验结果

（1）性能：E²DTC与其他方法相比性能最好，如在GeoLife上的UACC提高了近34%，在Hangzhou上提高了6.5%，在Porto上平均提高了26%。经典方法在不同的数据集上表现有所不同，原因是不同轨迹数据集具有不同的空间属性，为一个数据集设计的聚类方法对另一个数据集可能不是最优。

图2 性能评估表格

（2）可伸缩性：通过聚类时间来评估，E²DTC方法比经典方法有两个数量级的性能改进，并略优于t2vec+k-means。E²DTC和t2vec+k-means随着数据的增长更加稳定。

图3 可伸缩性性评估对比图

（3）稳定性：通过鲁棒性分析来探索模型的稳定性。从数据集中创建了均衡和不均衡两个子集进行实验，E²DTC性能很高，并且在平衡和不平衡的数据集中都具有稳定的UACC和NMI，而传统的聚类方法不能处理数据分布的不平衡问题，会导致性能迅速下降。

图4 E²DTC在数据分布不同下的对比图

四. 总结

本文提出用端到端深度轨迹聚类框架E²DTC来学习深度轨迹表示并同时执行聚类。在三个真实数据集上进行的大量实验证实，E²DTC是一种高效的聚类框架，在准确性和效率方面都具有高质量的结果。并且，本文还提出了一种有效的空间聚类标记地面生成算法，以鼓励轨迹聚类的进一步研究。

聚类端到端空间数据无监督学习单元格

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

E2DTC：通过自训练实现的端到端深度轨迹聚类框架

评论