基于车辆互联网动态表示学习的车辆轨迹聚类

基于车辆互联网动态表示学习的车辆轨迹聚类汇报人：秦能能

周恒茹目录CONTENTS0102基本框架实验结果随着物联网、通信技术的发展和数据采集能力的提高，我们能够获得大量的空间轨迹数据目标可以通过研究车辆轨迹数据的不同特征来表征道路上车辆的时间和空间信息来实现这些轨迹数据对于探索人类的运动模式和活动模式具有重要意义。解决城市问题检测异常行为计算从位置A到位置B的最优路径监控城市交通流预测目标的下一个位置提出了车辆轨迹聚类算法第一部分PART

01基本框架(c)有效的车辆聚类(b)动态车辆网络表示(a)基于k近邻的车联网建设将车辆轨迹数据基于k近邻的方法组织成网络，从网络的角度对车辆轨迹进行聚类动态汽车网络建设我们将车辆视为网络中的节点，得到节点集V。对于V中的每两个节点

和

，为了确定它们之间是否有一条边

，我们根据经纬度将区域划分为许多长宽为0.001°的小正方形。如果

和

在同一个小正方形中，则

和

之间有一条边

，反之亦然。每行正方形的数量动态汽车网络建设由于车辆的位置是不断变化的，因此车辆网络是一个动态网络。我们取一个小时作为时间步长。考虑到车辆的位置在一小时内也可能非常不同，我们在每小时的0分钟、20分钟和40分钟为网络中的节点建立边，并将这三个时刻的边保留在当前小时的网络中。我们将t时刻的车辆网络表示为

，那么我们构造的动态网络可以表示为动态汽车网络建设动态汽车网络建设动态网络表示学习随着网络规模的不断扩大，传统的聚类方法已经无法有效地完成。近年来，随着网络表示学习技术的发展，更高效、更准确地实现节点聚类成为可能。我们提出通过对之前构建的基于k近邻的车辆网络进行动态网络表示学习来学习车辆的嵌入向量。我们将这种动态网络表示学习方法命名为DynWalks。动态网络表示学习Word2Vec从大量的文本语料中以无监督方式学习语义知识的一种模型，它被大量的用在自然语言处理中。Word2Vec模型主要有Skip-Gram和CBOW两种模型。Skip-Gram给定inputword预测上下文，该模型一共分为两部分：第一部分为建立模型，基于训练数据构建一个神经网络第二部分是通过模型获取嵌入向量动态网络表示学习例：AdogbarkedatthemanThepuppybarkedallthetime如果我们拥有10000个单词表，我们想嵌入300维的词向量，那么我们就会有10000×300=300万个权重，Word2Vec是一个超级大的神经网络，训练一个神经网络，它每经过一个训练样本的训练，权重就会调整一次，这样会非常消耗资源和时间，负采样（negativesampling）解决了这个问题，它是用来提高训练速度的一种方法。不同于原本每个训练样本更新所有的权重，负采样每次让一个训练样本仅仅更新一小部分的权重，这样就会降低计算量。动态网络表示学习DeepWalk将执行截断随机游走获得的节点看作一个序列，重复多次，得到多个序列，将得到的序列当作自然语言处理中的一个个句子，作为word2vec的输入，进而得到节点的嵌入向量。DynWalks类似地，DynWalks在每个选定节点上执行长度为l的截断随机游走r次。通过使用长度为w的滑动窗口对每个随机游走序列进行滑动，形成由

组成的训练对集D，其中i∈[−w，+w]，i

0。DynWalks使用Skip-Gram负采样模型(SGNS)训练D中每个节点对上的节点嵌入向量动态网络表示学习同时，在之前修改的DeepWalk的基础上，DynWalks采用在线方式捕捉网络的动态，可以表示为:由于DynWalks在网络上进行随机行走，所以每个时间步长上的车辆网络必须是一个连通网络。因此，在构建车辆网络之后，我们应该取最大连通子图。其中

为上一步的学习结果，

为时间t的嵌入矩阵。当t=0时，DynWalks对

的所有节点进行随机游走，得到所有节点的嵌入向量。当t

0时，DynWalks只对所选节点进行随机游走，更新所选节点的嵌入向量。其他节点的嵌入向量保持不变。因为新节点没有相应的嵌入向量，所以必须选择它们。除新节点外，在时间步长t上选择的节点数为

。所选节点包含随机选择生成的

最受影响节点和

多样性节点。α和β是作者引入的两个超参数。基于机器学习的节点聚类在动态车辆网络上使用DynWalks，我们就可以得到各车辆的嵌入向量。为了找到行为模式相似的车辆，可以使用各种聚类方法对节点的嵌入向量进行聚类。在这里，我们主要研究K-means，GMM，K-mediods三种聚类方法。基于机器学习的节点聚类动态车辆网络的聚类结果最大连通子图动态车辆网络节点的嵌入向量第二部分PART

02实验结果数据集在本文中，作者选取中国杭州出租车数据集进行实验。我们选择30.07°N~30.47°N,120.0°E~120.4°E作为动态车辆网络的地理区域选取2014年3月1日早8点至晚7点的杭州市所有出租车的车牌号、GPS时间、经纬度等信息构成数据集按照时间步长为1小时构建每小时的动态车辆网络数据集为简单起见，我们只将每种方法的聚类结果与动态车辆网络的最后一个网络(晚上7点)进行比较。这意味着DeepWalk和LINE只学习最后一个车辆网络上节点的嵌入向量，因为它们是静态网络表示算法。评价指标轮廓系数a(i)为节点与同簇中其他节点的平均距离，称为凝聚度b(i)为节点与最近簇中所有节点的平均距离，称为分离度取值范围为[-1,1]簇内样本距离越近，簇间样本距离越远，轮廓系数越大，聚类效果越好评价指标Davies-Bouldin指数其中，

是簇i中节点到簇

i

质心的平均距离，

为簇

i

质心，N为簇数DBI值是任意两簇内平均距离之和与两簇质心间的距离之比的最大值的平均值簇内样本距离越近，簇间样本距离越远，DBI值越小，聚类效果越好任意两簇内平均距离之和任意两簇质心间的距离评价指标Calinski-Harabaz指数m为节点数，k为簇数，

为簇间协方差矩阵，

为簇内协方差矩阵CHI是簇间方差与簇内方差的比值簇内样本距离越近，簇间样本距离越远，CHI值越大，聚类效果越好簇间方差簇内方差参数敏感性分析为了研究DynWalks参数对聚类结果的影响，我们还通过改变超参数的值进行了实验。为简单起见，我们固定行走长度(l=80)和窗口大小(w=10)，并改变选择节点的比例α，最受影响节点的比例β，嵌入向量的维数d，每个节点上的行走次数r来研究参数的影响。我们从参数敏感性、聚类方法敏感性和准确率比较三个方面展示实验结果。参数敏感性分析随着α的增加，聚类结果会更好。增加所选节点的比例α意味着我们将在更多的节点上执行随机游走。参数敏感性分析当受影响节点的比例β增大时，聚类结果曲线呈现波动状态，没有明显的上升或下降趋势。因此，β对聚类结果的影响是不确定的。我们需要通过调整参数找到一个合适的β。参数敏感性分析我们发现聚类结果并没有随着节点行走次数

r

的增加而增加。当

r增大到一定值时，聚类结果最好。参数敏感性分析当嵌入向量维数

d增大时，聚类结果逐渐减小。这意味着较小的嵌入向量维数更适合于动态车辆网络。聚类算法灵敏度本文使用的算法是K-means算法，为了验证K-means算法在车辆网络中的聚类性能，我们将其与k-medoids（K-中心点）和高斯混合模型(GMM)进行了比较。同时，为了避免比较结果的偶然性，我们分别使用DynWalks、DeepWalk、LINE学习到的嵌入向量进行聚类。聚类算法灵敏度聚类算法灵敏度所以K-means更适合动态车辆网络性能比较为了验证我们使用的网络表示学习算法的性能，我们将DynWalks与DeepWalk和LINE在同一车辆网络上进行比较。固定参数：r(行走次数)=20,l(行走长度)=80,w(窗口大小)=10,d(嵌入向量维数)=128此外，DynWalks的α和β分别设为0.2和0.5性能比较性能比较DynWalks在所有三个指标和三种聚类算法上都比LINE表现得更好。与DeepWalk相比，DynWalks在DB指数上的表现具有竞争力。它在CH指数中的表现也优于DeepWalk。在轮廓系数中，当小于5