基于QuickBundles算法的轨迹聚类方法

刘峰

摘  要： 随着卫星定位传感器的普及应用，形成了海量移动对象的轨迹数据。轨迹数据含有丰富的时空特征信息，通过对相关数据聚类处理，可以挖掘出移动对象的活动场景、位置等属性信息。通过借鉴神经成像学领域中的QuickBundles算法，介绍算法原理和实现，并基于此算法实现了一种轨迹聚类方法，通过使用实际GPS数据对此方法进行验证，从对聚类结果的可视化展示表明，本方法能够有效挖掘原始数据，完成对轨迹数据的聚类。

关键词： 轨迹数据挖掘; 聚类; 可视化; 应用

中图分类号：TP311.1          文献标识码：A     文章编号：1006-8228（2022）04-43-04

Trajectory clustering method based on QuickBundles algorithm

Liu Feng

（Jiangsu Automation Research Institute， Lianyungang， Jiangsu 222002， China）

Abstract： With the popularization of satellite positioning sensors， a large number of trajectory data of moving objects have been formed. The trajectory data contains rich spatio-temporal feature information. By clustering the relevant data， the attribute information such as activity scene and location of moving objects can be mined. By referring to the QuickBundles algorithm in the field of neuroimaging， the principle and implementation of the algorithm are introduced， and a trajectory clustering method is implemented based on this algorithm. This method is verified by using the actual GPS data. Through the visual display of the clustering results， this method can effectively mine the original data and complete the clustering of trajectory data.

Key words： trajectory data mining; clustering; visualization; application

0 引言

在互聯网高速发展的今天，无时无刻不在产生轨迹数据，海量的轨迹数据具有很大的研究价值，通过对于轨迹数据的聚类分析，能够为交通路线优化、船舶AIS导航[3]、路网预测[6]等提供很好的解决方案。

经典的轨迹聚类算法有基于中心搜索的K-Means算法、基于密度的DBSCAN算法[2]以及基于层次的BIRCH算法等[8]，但是K-Means算法中需要选择起始中心点和聚类的个数，并且不同的中心点的选取对最后的结果影响很大，而DBSCAN算法对均匀密度的样本效果很好，但是对线性样本则效果不佳。

大多数的聚类算法的时间复杂度为O（N2），其中N是需要进行聚类的轨迹数量，而本文则借鉴神经成像学领域中，用于对磁共振成像中得到的白质纤维进行聚类所采用的QuickBundles算法[1]，把需要进行聚类的轨迹视为蛋白质纤维，然后在同一个聚类中合并相似度高的轨迹。

1 QuickBundles算法简介

QuickBundles是一种非常的简单和快速的算法，它可以在线性时间内将N条轨迹进行聚类。在QB算法中，每个轨迹都被定义成固定长度的有序点序列，使用比较函数和合并来进行轨迹聚类。通过计算此条轨迹与当前存在的轨迹集群之间的距离，来判单是否需要将这条轨迹加入此集群，同时轨迹集群保存在一个根据需要扩展的列表中。与其他聚类算法不同，如k-Means或BIRCH，QB中没有重新分配或更新阶段，一旦一条轨迹被分配到一个集群，它就停留在那里，并且集群不会合并，QB的速度和效率正是源于这个思想。

1.1 轨迹距离度量

轨迹距离度量是整个轨迹聚类的基础，这里我们使用了一个相当简单的对称距离函数，简称为最小平均直接翻转距离（MDF），我们定义轨迹S=[S1，S2，…，SK]等价于两条有序折线：S =[S1，S2，…，SK]和它的翻转版本SF=（SK， SK−1，…，S1），在这种表示法下，直接距离、翻转距离和MDF距离计算方式如下：

|x−y|表示两个经纬度点x和y之间的距离，直接距离d（s，t）是指两条轨迹s和t对应点之间距离的均值。

不过只有当两条轨迹具有相同的轨迹点数量时，才可以使用MDF距离进行计算。使用MD来计算两点轨迹之间距离时，需要先通过简单的线性插值算法，使得任意两条轨迹具有相同的数量轨迹点，并且使得每条轨迹的所有段具有相等的长度。

因此对于包含K个点的两条轨迹，MDF距离只需要进行2K点的距离计算。MDF距离是对两条轨迹的相似度进行空间上的度量，显然MDF距离是非负的，并且当且仅当两条轨迹相同且对称时，计算的MDF距离为零。

MDF距离的主要优点是计算效率高，通过对两条轨迹的直接距离和翻转距离的计算，来对轨迹的相似度进行度量，可以非常轻松地解决从最简单的平行轨迹到最复杂的发散轨迹的情况。

1.2 算法实现

QB算法在聚类节点中存储关于轨迹聚类的信息，我们将轨迹从1到N进行编号，其中Si是代表第i条轨迹。聚类节点被定义为三元组c=（I，h，n），其中I是整数索引i=1到N的列表，n为该聚类中的轨迹数量，h为轨迹距离和。h是一个K×3矩阵，当一条轨迹被添加到一个聚类时，它可以在线更新，并且等于：

在算法的任何一步，我们都有M个clusters（集合）。选择第一条轨迹S1并将其放在第一个clusters，C1←（{1}，S1，1）;此时M=1，对于每个剩余的轨迹，依次i=2，…，N：

i. 计算轨迹 Si与所有当前聚类 Ce 的质心轨迹Ve之间的MDF距离，其中e=1，…，M，这里定义群集节点的质心轨迹为V，其中V=h/n;

ii. 如果任何距离的值Me小于聚类阈值θ，将轨迹i添加到聚类e中，最小值为Me;Ce=（I，h，n），并更新Ce←（append（I，i），h+s，n+1）; 否则创建一个新的cluster CM+1←（[i]，si，1），M←M+1。

具体算法伪代码如下：

输入：T = {s，…，s，…，s}，θ

输出：C = [c，…，c，…，c]

# 创建第一个聚类

c1 ← （[1]，s1，1）

C ← [c1]

M ← 1

for i = 2 to Ndo

t ← s

alld ←infinity（M） #距离缓冲区

flip ← zeros（M） #MDF检查缓冲区

for k = 1 to M do

v ← c·h/c·n

d ← d（t，v）

f ← d（t，v）

# 計算MDF距离

if f < d then

d ← f

flipk← 1

end if

alldk← d

end for

m ← min（alld）

l ← argmin（alld）

if m < θ then

# 加入当前聚类

if flip is 1 then

cl·h ← c·h + tF

else

cl·h ← c·h + t

end if

cl·n ← cl·n + 1

append（cl·I，i）

else

# 创建新的聚类

c ← （[i]，t，1）

append（C，c）

M ← M+1

end if

end for

2 轨迹聚类方法实现

原始数据采用微软亚洲研究院发布的GeoLife GPS Trajectories数据集，来进行轨迹聚类，考察用QB算法的运行效果，这里我们选择Geolife Trajectories 1.3＼Data＼010＼Trajectory数据。

2.1 数据清理

首先我们需要对获得的数据进行清理，GeoLife GPS Trajectories数据集里数据组织如图1所示。

定义相关标签，并读取所有数据文件，将获取到的GPS经纬度点信息保存：

names=['lat'，'lng'，'zero'，'alt'，'days'，'date'，'time']

streams=[]

index=0

userdata='./Geolife Trajectories 1.3/Data/'+'010'+'/Trajectory/'

filelist=os.listdir（userdata）

for file in filelist：

df_list=[pd.read_csv（userdata+file，header=6，

names=names，index_col=False）]

df=pd.concat（df_list， ignore_index=True）

df.drop（['zero'，'alt'，'days'，'date'，'time']，axis=1，inplace=True）

df_min=df.iloc[：：， ：]

lat_lng_data=np.c_[df_min['lat'].values，df_min['lng'].values]

streams.append（lat_lng_data）

print（streams[0][0，0]， streams[0][0，1]）

聚类之前先绘制原始轨迹，这里采用gmplot包来进行轨迹点绘制：

#绘制原始轨迹

from gmplot import gmplot

gmap=gmplot.GoogleMapPlotter（streams[0][0，0]，

streams[0][0，1]，12）

color=randomcolor（）

for i in range（0， len（streams））：

gmap.plot（streams[i][：，0]，

streams[i][：，1]， color， edge_width=1）

gmap.draw（"normal_map.html"）

待处理的原始轨迹如图2所示。

2.2 距离计算

我们现在可以从定义两个GPS轨迹之间的距离函数开始，我们将使用大地坐标系计算公式来代替QuickBundle算法中的经典欧几里得距离计算公式，计算两个经纬度点之间的距离。

#距离计算

from math import radians， cos， sin， asin， sqrt

#公式计算两点间距离（m）

def geodistance（lat1，lng1，lat2，lng2）：

lng1， lat1， lng2， lat2=map（radians， [float（lng1），

float（lat1）， float（lng2）， float（lat2）]） #经纬度转换成弧度

dlon=lng2-lng1

dlat=lat2-lat1

a=sin（dlat/2）**2 + cos（lat1）*cos（lat2）*sin（dlon/2）**2

distance=2*asin（sqrt（a））*6371*1000

#地球平均半径，6371km

distance=round（distance/1000，3）

return distance

2.3 QB算法实现

我们计算了两个轨迹之间的平均点的实际距离。这种计算距离的方法可以在且仅当两个轨迹具有相同数量的点时使用，因此我们需要重新采样所有轨迹，采样点数量可以根据轨迹数据集里每条轨迹平均点数量来确定。使用上面我们定义的两条轨迹之间的距离计算函数geodistance，这里我们就可以运行QuickBundle聚类算法进行轨迹聚类，聚类阈值θ可以根据需要聚类效果灵活选取。

#qb聚类

import geopy.distance

from dipy.segment.metric import Metric

from dipy.segment.metric import ResampleFeature

import numpy as np

from dipy.segment.clustering import QuickBundles

class GPSDistance（Metric）：

def __init__（self）：

super（GPSDistance， self）.__init__（feature=

ResampleFeature（nb_points=256））

def are_compatible（self， shape1， shape2）：

return len（shape1）==len（shape2）

def dist（self， v1， v2）：

x=[geodistance（p[0][0]， p[0][1]， p[1][0]， p[1][1]）

for p in list（zip（v1， v2））]

currD=np.mean（x）

return currD

THERSHOLD=10   #km

metric=GPSDistance（）

qb=QuickBundles（threshold=THERSHOLD， metric=metric）

clusters=qb.cluster（streams）

print（"Nb.clusters："， len（clusters））

2.4 聚类结果

如图3所示，对θ分别选择5、10、25、100得到的聚类结果，通过对轨迹结果的可视化展示[9]，可见，θ越大，得到的聚类数量越少，对轨迹压缩效果也越高，同时损失的原始轨迹数据也越多。

3 结束语

本文借鑒了神经成像学领域中的QuickBundles算法，提出一种应用该算法对海量轨迹点进行聚类的方法，同时采用微软亚洲研究院发布的GeoLife GPS Trajectories数据集对聚类的方法进行验证，通过对聚类结果的可视化分析，该方法能够有效地对轨迹进行聚类，得到的结果和实际物体轨迹相符合。

参考文献（References）：

[1] Garyfallidis Eleftherios，Brett Matthew，Correia MartaMorgado，Williams Guy B，Nimmo-Smith Ian. QuickBundles， a Method for Tractography Simplification[J]. Frontiers in neuroscience，2012，6

[2] 陈艳君.面向海量轨迹数据的聚类算法研究[D].北京交通大学，2015

[3] 肖潇.基于AIS信息的船舶轨迹聚类模型研究[D].集美大学，2015

[4] 魏照坤.基于AIS的船舶轨迹聚类与应用[D].大连海事大学，2015

[5] 程智源.基于轨迹聚类的交通热点分析[D].电子科技大学，2018

[6] 冯琦森.基于出租车轨迹的居民出行热点路径和区域挖掘[D].重庆大学，2016

[7] 甘波.基于海量物流轨迹数据的分析挖掘系统[D].武汉理工大学，2014

[8] 许佳捷，郑凯，池明旻，等.轨迹大数据：数据、应用与技术现状[J].通信学报，2015（12）：97−105

[9] 王祖超，袁晓如.轨迹数据可视分析研究.计算机辅助设计与图形学学报，2015（1）：9−25