2024年3月15日发(作者：)

第47卷

Vol.47

第4期

No.4

计算机工程

ComputerEngineering

文章编号：1000-3428（2021）04-0100-08文献标志码：A

2021年4月

April2021

中图分类号：TP391

·人工智能与模式识别·

基于群组与密度的轨迹聚类算法

222

俞庆英

1，

，赵亚军

1，

，叶梓彤

1，

，胡

2

凡

1，

，夏

2

芸

1，

（1.安徽师范大学计算机与信息学院，安徽芜湖241002；

2.安徽师范大学网络与信息安全安徽省重点实验室，安徽芜湖241002）

摘要：现有基于密度的聚类方法主要用于点数据的聚类，不适用于大规模轨迹数据。针对该问题，提出一种利用

群组和密度的轨迹聚类算法。根据最小描述长度原则对轨迹进行分段预处理找出具有相似特征的子轨迹段，通过

两次遍历轨迹数据集获取基于子轨迹段的群组集合，并采用群组搜索代替距离计算减少聚类过程中邻域对象集合

搜索的计算量，最终结合群组和密度完成对轨迹数据集的聚类。在大西洋飓风轨迹数据集上的实验结果表明，与

基于密度的TRACLUS轨迹聚类算法相比，该算法运行时间更短，聚类结果更准确，在小数据集和大数据集上的运

行时间分别减少73.79%和84.19%，且运行时间的减幅随轨迹数据集规模的扩大而增加。

关键词：群组；密度；群组可达；邻域搜索；轨迹聚类

开放科学（资源服务）标志码（OSID）：

中文引用格式：俞庆英，赵亚军，叶梓彤，等.基于群组与密度的轨迹聚类算法［J］.计算机工程，2021，47（4）：100-107.

英文引用格式：YUQingying，ZHAOYajun，YEZitong，toryclusteringalgorithmbasedongroupanddensity［J］.

ComputerEngineering，2021，47（4）：100-107.

TrajectoryClusteringAlgorithmBasedonGroupandDensity

22222

YUQingying

1，

，ZHAOYajun

1，

，YEZitong

1，

，HUFan

1，

，XIAYun

1，

rovincialKeyLaboratoryofNetworkandInformationSecurity，AnhuiNormalUniversity，Wuhu，Anhui241002，China）

（ofComputerandInformation，AnhuiNormalUniversity，Wuhu，Anhui241002，China；

【Abstract】Theexistingdensity-basedclusteringmethodsaremainlyusedforpointdataclustering，andnotsuitableforlarge-

esstheproblem，thispaperproposesatrajectoryclusteringalgorithmbasedongroupanddensity.

AccordingtotheprincipleofMinimumDescriptionLength（MDL），thetrajectoriesarepreprocessedbysegmentstofind

upsetbasedonthesubtrajectoriesisobtainedbytraversingthe

trajectoriesdatasettwice，andthegroupsearchisusedtoreplacethedistancecalculationtoreducethecalculationamount

y，thetrajectorydatasetisclusteredby

mentalresultsonAtlantichurricanetrackdatasetshowthat，comparedwiththedensity-

basedTRACLUStrackclusteringalgorithm，therunningtimeoftheproposedalgorithmislessandtheclusteringresultsare

ningtimeonthesmalldatasetandlargedatasetisreducedby73.79%and84.19%respectively，and

thereductionofrunningtimeincreaseswiththeexpansionoftrackdataset.

【Keywords】group；density；groupreachability；neighborhoodsearch；trajectoryclustering

DOI：10.19678/.1000-3428.0057425

0概述

随着定位、通信和存储技术的快速发展，车辆行

驶轨迹数据、用户活动轨迹数据以及飓风轨迹数据

等大量移动对象的轨迹数据可被搜集和存储。轨迹

数据中包含丰富的时空语义信息，从中可挖掘出众

基金项目：国家自然科学基金（61702010，61972439）。

多有价值的信息

［1-2］

。聚类分析是常用的数据挖掘方

法，其被广泛用于图像分析

［3］

、模式识别

［4］

、知识发

［5］［6］

现以及生物信息学等领域。近年来，研究人员针

对不同的应用领域提出多种聚类算法，主要包括以

BIRCH为代表的基于层次的聚类算法

［7］

、以STING

［8］

为代表的基于网格的聚类算法、以K-means为代表

作者简介：俞庆英（1980—），女，副教授、博士，主研方向为空间数据处理、信息安全；赵亚军，本科生；叶梓彤、胡

讲师、硕士。

收稿日期：2020-02-19修回日期：2020-03-24E⁃mail：****************.cn

凡，硕士研究生；夏芸，

第47卷第4期俞庆英，赵亚军，叶梓彤，等：基于群组与密度的轨迹聚类算法

101

的基于划分的聚类算法

［9-10］

，以及以DBSCAN为代

表的基于密度的聚类算法

［11-12］

。然而上述算法主要

用于点数据的聚类，不能直接用于轨迹数据的聚类。

对轨迹数据聚类可获得移动对象的代表性路

径，从而掌握其周期性行为规律

［13］

。由于轨迹数据

中包含大量时间、空间和形状等固有特征信息，因此

大部分轨迹聚类方法先进行基于轨迹数据对象的相

似性度量，再通过改进传统聚类算法来实现轨迹数

据聚类。例如，目前使用最广泛的TRACLUS

［14］

轨迹

聚类算法先基于轨迹分段进行相似性度量，再利用

传统DBSCAN算法实现轨迹聚类。DBSCAN算法

可形成任意形状的簇并能有效处理噪声点，但由于

该算法在执行过程中会重复遍历整个数据集来搜索

某个样本的邻域集合，因此处理大数据集的耗时较

长，时间复杂度为O（n

2

），并需要较大内存和I/O开

销。针对该问题，研究人员采用R-树

［15］

、KD-树

［16］

等

空间索引方法降低邻域集合搜索所需计算次数来减

少算法的时间开销，但空间索引方法实现较困难，且

不适用于高维数据集。

针对上述问题，本文提出一种基于改进邻域搜

索技术的聚类算法。对轨迹进行分段预处理找出具

有较高相似度的子轨迹段，通过遍历整个轨迹数据

集将其分为不同的群组，采用群组搜索代替距离计

算减少邻域对象搜索的计算次数，以缩短算法在海

量轨迹数据集上的运行时间。

1相关工作

本文以TRACLUS算法中相似性度量方法为基

础，通过改进DBSCAN算法来实现轨迹聚类，以下

对DBSCAN算法的相关工作进行介绍。

DBSCAN算法是一种基于密度的空间聚类算

法，其本质是寻找密度相连点的最大集合，能有效滤

除低密度点区域，将高密度区域划分为簇，并在具有

噪声点的数据中发现任意形状的簇。研究人员基于

DBSCAN算法的上述特性，对其不断改进与创新，并

将研究成果应用于多个领域。

DBSCAN算法需要人为确定半径参数

ε

和邻域

密度阈值MinPts，这两个参数能否合理选取对聚类

结果影响较大，然而目前DBSCAN算法无法在多密

度情况下设置参数。对此，文献［17］提出一种初始

点优化与参数自适应的改进DBSCAN算法，其能为

不同密度的簇自适应设置不同参数，并优先对高密

度簇进行聚类，即实现对多密度数据集的聚类。文

献［18］通过改进DBSCAN算法得到EXDBSCAN聚

类算法，可用于多密度数据集且只需输入一个参数。

文献［19］结合DBSCAN算法和粒子群算法提出改

进算法，其可基于数据集自动生成参数并有效进行

空间热点识别。

将DBSCAN算法及其改进算法应用于轨迹数

据集的处理也是研究热点之一。由于大部分轨迹数

据集规模庞大且数据量丰富，因此提高DBSCAN算

法的计算效率非常重要。文献［20］提出一种可用于

多密度数据集的RNN-DBSCAN聚类算法，利用逆

邻域计数和权值剪枝方法使算法的时间复杂度由

O（n

2

）降为O（n）。文献［21］开发出DBSCAN算法的

分布式应用，在不影响聚类效果的情况下，使该算法

在大规模数据集上实用性更强。文献［22］在提高

DBSCAN算法实时性的基础上，使用KD-树和

SparkGraphX分布式图处理框架，能显著减少数据

集中样本之间距离的计算量，在大规模数据集上耗

时更短。文献［23］结合MapReduce分布式计算框架

和Hadoop平台，有效提高DBSCAN算法在大规模

数据集上的运行效率。文献［24］提出一种用于处理

时空轨迹数据的HDBSCAN算法，其考虑到传统聚

类算法未考虑的轨迹先后性和内在层次，所得聚类

结果更合理。文献［25］提出一种基于轨迹数据密度

分区的分布式并行聚类算法，构建可分布式并行聚

类的局部数据集，在不同服务器上执行DBSCAN算

法进行局部聚类，然后对聚类结果进行合并和整合，

通过并行处理提高了聚类分析效率。

在上述基于DBSCAN的改进算法中，分布式图

处理框架和KD-树等空间索引方法均较难实现，且

空间索引树较难应用于高维轨迹数据集。为此，

本文提出一种基于群组和密度的轨迹聚类算法

TraG-DBSCAN，以DBSCAN算法为基础，使用群组

划分方法减少聚类算法中邻域对象搜索所需时间，

从而提高算法实时性，并利用邻域相似性度量提升

轨迹聚类准确性。

2本文算法

2.1相关定义与符号

定义1（轨迹距离）轨迹距离是评价轨迹样本

之间相似性的度量值，是轨迹聚类效果的重要指标

之一。两个轨迹样本之间距离越大，其相似度越小，

反之亦然。

本文采用文献［14］中的距离计算方法实现轨迹

段之间的相似性度量，如图1所示。

102

计算机工程

2021年4月15日

图1距离计算示意图

Fig.1Schematicdiagramofdistancecalculation

在图1中，两个轨迹段

tra

i

和

tra

j

之间的距离

dist(tra

i

tra

j

)

包含垂直距离

d

^

、平行距离

d



和角度距

离

d

θ

3个部分，

2

相关计算公式如下：

d

^

=

tra

^1

+tra

2

^2

tra

^1

+tra

（1）

^2

d



=min(tra

1

tra

2

)

（2）

d

θ

=



tra

j



´sin(θ)

（3）

dist(tra

i

tra

j

)=w

^

´d

^

+w



´d



+w

θ

´d

θ

（4）

其中，

w

^

中均设置为

、w



和w

θ

分别为

d

^

、

d



和

d

θ

的权重，在本文

1/3。

定义2（群组）群组是一条核心轨迹和若干条

非核心轨迹组成的集合，核心轨迹与任意非核心轨

迹之间距离不大于距离阈值

ε

。群组形状与最大半

径为

ε

的圆类似。

定义3（边界距离）边界距离

T

s

和

T

w

分别为群

组中s和w的核心轨迹到非核心轨迹的最大距离，其

值不大于

ε

。

定义4（群组可达）设

C

s

和

C

w

分别为不同群组

s和w的核心轨迹，当满足



C

s

-C

w



≤T

s

+T

w

+ε

时，

称s和w为群组可达，群组s

i

的可达群组集合记为

R(s

i

)

。

2.2算法框架

在对轨迹数据集中一条轨迹进行聚类时，通常会

忽略部分具有较高相似度的子轨迹段。因此，本文在

对轨迹数据集聚类前，根据信息学中最小描述长度

MinimumDescriptionLength，MDL）

［14］

原则对轨迹进

行分段预处理。假设一条轨迹

TR

i

=p

1

p

2

p

len

i

，特征

点集合

points={p

1

p

2

p

len

i

}

，计算公式如下：

par

i

-1

L(H)=

∑

lb(len(p

c

）

j=1

j

p

c

j+1

))

（5

par

i

-1

c

j+1

-1

L(D|H)=

∑

j=1

∑

{lb(d

^

(p

c

k=c

j

p

c

j+1

p

k

p

k+1

))+

j

lb(d

θ

(p

c

j

p

c

j+1

p

k

p

k+1

))}

（6）

其中，

len(p

c

j

p

c

j+1

)

为两点之间的欧几里得距离，

d

^

和

d

θ

分别由式（1）和式（3）计算得到。

图2为TraG-DBSCAN算法流程，该算法包括两个

阶段：1）通过2次遍历轨迹数据集获得基于子轨迹段

的群组集合；2）对子轨迹段进行聚类，并利用群组集合

减少聚类算法中搜索轨迹样本邻域集合所需时间。

图2TraG-DBSCAN算法流程

Fig.2ProcedureofTraG-DBSCANalgorithm

2.3群组的建立

在群组建立阶段，通过2次遍历整个轨迹数据

集将其划分为不同群组，符合相应条件的群组之间

相互可达。

本，若群组数为

1）在第1次遍历轨迹数据集时

0或不存在任意一个群组的核心轨迹

，对于每个轨迹样

与该轨迹样本之间距离不大于

2ε

，则以该轨迹样本为

核心轨迹建立新群组；若存在一个群组的核心轨迹与

该轨迹样本之间距离不大于

ε

，则将该轨迹样本划分到

此群组中；若上述两种情况均不符合，则将该轨迹样本

标记为未处理轨迹，等待进行第2次遍历过程。

遍历中被标记为未处理的轨迹样本

2）在第2次遍历轨迹数据集时，对于每个在第

，计算其与所产

1次

生群组中核心轨迹之间的距离。若存在一条核心轨

迹与该轨迹样本的距离不大于

ε

，则将该轨迹样本划

分到相应群组；否则以该轨迹样本为核心轨迹建立

新群组。

值得注意的是，以不同顺序处理轨迹样本会产生

不同群组，但并不影响最终聚类结果。当一个新轨迹

样本加入群组时，群组的边界距离需进行更新。通过

计算两个群组中核心轨迹之间的距离可判断群组之间

是否可相互抵达，当两者之间距离不大于两个群组的

边界距离与

ε

之和时，这两个群组为可相互抵达。由于

群组的边界距离在算法结束前才可确定，边界距离取

最大值

ε

作为替代值，因此当两条核心轨迹之间距离不

大于

3ε

时，这两个群组可相互抵达。以下分别为建立

群组算法Group和CreateGroups（S，tra）函数算法的伪

代码。

算法1建立群组算法Group

输入轨迹数据集

D={tra

1

，tra

2

，⋯，tra

n

}

，半径参数

ε

输出群组

S={s

1

，s

2

，⋯，s

num

groups

}

1.标记轨迹数据集中的所有轨迹样本为assigned

2.

S=null

（

第47卷第4期俞庆英，赵亚军，叶梓彤，等：基于群组与密度的轨迹聚类算法

103

htrainD

中存在一个s使得

‖C

s

5.

s=s∪{tra}

−tra‖<ε

6.

S=S∪s

S为空orS中不存在任何一个s使得

‖C

s

−

8.S

tra‖

=

<

CreateGroups

2×ε

（S，tra）

10.将tra标记为unassigned

hunassignedtrainD

中存在一个s使得‖

C

s

16.

s=s∪{tra}

−tra

‖

<ε

17.

S=S∪s

19.S=CreateGroups（S，tra）；

S

算法2CreateGroups（S，tra）函数算法

1.建立一个新的群组

s={tra}

2.

R(s)=null

3.

C

s

=tra

huinS

‖

C

u

6.

R(s)=

−

R

C

s

(s

‖

)

≤

∪

3

u

×ε

9.

S=S∪s

S

2.4轨迹聚类

TraG-DBSCAN算法中的轨迹聚类算法以传统

DBSCAN算法为基础，采用群组搜索方法代替距离

计算方法，以减少搜索邻域集合所需计算次数和算

法在规模较大的轨迹数据集上的时间开销。

2.4.1

在传统

改进的邻域搜索算法

DBSCAN算法中，搜索邻域集合主要通过

计算该样本与数据集中其他样本之间的距离来实现，

其在大规模轨迹数据集上时间开销较大，建立群组可

减少搜索邻域集合所需计算次数。在搜索轨迹样本时，

首先判断该样本所在群组的边界距离，若边界距离不

大于

ε2

，则该群组中所有样本都处于该样本的邻域内，

否则再分别计算；若边界距离在（

ε2

，

ε

）范围内，则将

样本添加至邻域内。然后选取该群组的可抵达群组中

的样本。邻域搜索算法FindNeighbours的伪代码见

算法3。

算法3邻域搜索算法FindNeighbours

输入待处理轨迹样本tra，半径参数

ε

，群组

S=

{s

1

，s

2

，⋯，s

num

groups

}

输出

N

ε

(tra)

1.

N

ε

(tra)=∅

2.获取tra所在的群组CurrentGroup

T

ε

CurrentGroup

≤

2

4.将CurrentGroup中的所有轨迹样本都添加进

N

ε

(tra)

hiinCurrentGroup

‖i−tra‖≤ε

8.

N

ε

(tra)=N

ε

(tra)∪{i}

hsinR（CurrentGroup）



C

CurrentGroup

−C

s



≤T

s

+ε+



C

CurrentGroup

−tra



hiins

‖i−tra‖≤ε

16.

N

ε

(tra)=N

ε

(tra)∪{i}

N

2.4.2

ε

(tra)

基于

轨迹聚类算法

上述邻域搜索算法进行轨迹聚类，以下分

别为轨迹聚类算法ClusterTra和ExpandCluster（Q，

C，

εMinPtsS

）函数算法的伪代码。

算法4轨迹聚类算法ClusterTra

输入轨迹数据集

D={tra

1

，tra

2

，⋯，tra

n

}

，半径参数

ε

，

邻域密度阈值

MinPts

，群组

S={s

1

，s

2

，⋯，s

num

groups

}

输出簇

O=

{

C

1

，C

2

，⋯，

C

clu

}

1.标记所有样本轨迹为unclassified

存在标记为unclassified的样本轨迹do

3.随机选择一个unclassified样本tra

4.标记tra为classified

ighbours（tra，

ε

，S）

|

N

ε

(tra)

|

≥MinPts

7.创建一个新簇C

8.

C=C∪{tra}

9.将tra邻域集合中的所有轨迹样本添加进队列Q中

Cluster（Q，C，

ε，MinPts，S

）

12.标记tra为噪声点

le

104

计算机工程

2021年4月15日

算法5ExpandCluster（Q，C，

εMinPtsS

）函数算法

Q≠∅

2.M为Q中的第一个样本

是噪声点

4.

C=C∪{M}

6.

N

ε

(tra)

=FindNeighbours（tra，

ε

，S）

|

N

ε

(tra)

|

8.将邻域集合中的所有轨迹添加进

≥MinPts

Q中

还不是任何簇的成员

11.

C=C∪{M}

13.将M移出队列

le

2.5时间复杂度

TraG-DBSCAN算法的时间复杂度包含以下

集，处理每条轨迹并获得待处理的子轨迹段

1）轨迹分段处理的时间复杂度。遍历整个数据

3个部分：

，此部分

时间复杂度为O（n）

。

整个子轨迹段集合进行群组初步划分

2）基于子轨迹段建立群组的时间复杂度

，未被划分到

。遍历

任何群组的子轨迹段在第2次遍历中进行处理。假

设p为最初群组划分后剩余的子轨迹段数目，则基

于子轨迹段建立群组的时间复杂度为O（n+p），由于

pn

杂度。

3

，

）

因此该部分时间复杂度也为

该部分耗时主要集中在对每个子轨迹段的邻域

基于划分的群组对子轨迹段进行聚类的时间复

O（n）。

搜索上。在对子轨迹段样本进行邻域集合搜索时，需

计算该样本与所有可达群组中全部轨迹段样本之间的

距离，以及该样本与数据集中所有其他轨迹样本的距

离。如果未做任何改进，则该部分的时间复杂度为O（n

2

）。

实际上，TraG-DBSCAN算法在该部分做了相应改进，

需计算子轨迹段样本与可达群组中轨迹样本之间距离。

此外，对于待处理的子轨迹段样本，算法会对该样本的

可达群组进行相应的剪枝处理，从而减少时间开销。

假设d为数据集中邻域集合搜索所需最大计算次数，

则聚类阶段的时间复杂度为O（nd）。

综上所述，TraG-DBSCAN算法的时间复杂度为

上述各部分时间复杂度之和O（n）+O（n）+O（nd），其

总体时间复杂度为O（nd）。对于可行的邻域参数

ε

，

d通常很小且受到样本对象处理顺序的影响。

3实验与结果分析

本文在不同轨迹数据集上验证TraG-DBSCAN算

法（以下称为本文算法）的有效性和准确性，将本文算

法与TRACLUS算法的运行时间和聚类结果准确性进

行对比分析。本文算法和TRACLUS算法均由Matlab

语言实现，实验环境为AMDFX-7600PRadeonR74核

处理器

2016b运行平台

，8GB内存

。

，Windows7操作系统以及Matlab

3.1实验数据集

本文实验采用BestTrack大西洋飓风轨迹数据集，

其记录了大西洋飓风发生的时间、经纬度、最大持续风

速和每6小时的中心气压。本文从该轨迹集中选取飓

风发生的时间和经纬度轨迹数据进行实验。每条轨迹

数据的存储格式

T={Tidloc

1

loc

2



⋯

loc

n

}

，其中Tid

为轨迹标识符，

loc

i

=

i

lat

i

long

i

>(i=12n)

为

每个时刻的位置点，其中包含时间、纬度和经度信息。

将1990年至2013年的大西洋飓风轨迹数据作为数据

集DS1，该数据集包含152条飓风轨迹，共6557个轨

迹点。将1851年至2013年的大西洋飓风轨迹数据作

为

30

数据集DS2，该数据集包含855条飓风轨迹，

3.2

146

共

3.2.1

评价指标

个轨迹点。

本文采用以下轮廓系数评价算法的聚类效果

轮廓系数

值越小说明样本

1）计算样本i

i

到同簇中其他样本的平均距离

更应被聚类到该簇。将a（i）称为样本

a（

：

i），该

i

的簇内不相似度

2）计算样本

。



i

b

到其他某簇C

j

中所有样本的平均距

离b

ij

，将

min{b

i1i2



⋯

b

ik

}

（k为其他簇的个数）定义

为样本

3）样本

i的簇间不相似度

i的轮廓系数值记为

，记为b（i）。

s(i)=

b(i)-a(i)

（si）并定义如下：

max{a(i)b(i)}

（7）

其中，若s（i）接近1则说明样本i聚类更合理，若s（i）接

近−1则说明样本i更应分类到另外的簇，若（si）近似为0

则说明样本

3.2.2

i在两个簇的边界上。

为进一步验证本文算法的可行性

总平方误差和

，采用总平方误

差和（TotalSumofSquaredError，TSSE）作为算法聚类

效果的评价指标，其计算公式如下：

num

c

TSSE=

∑

i=1

(

1

2´

|

C

i

|

T

∑

)

2

x

ÎC

i

T

∑

dist(T

x

T

y

y

ÎC

i

)

（8）

其中，num

c

表示簇的个数，|C

i

|表示第i个簇中轨迹样本

的个数，dist（T

x

，T

y

）表示轨迹样本T

x

和T

y

之间的距离。

TSSE值越小，算法聚类效果越好。

3.3参数设置

人为选取的半径参数和邻域密度阈值通常不准

确，需耗费较多时间确定合适的参数值。本文在参数

设置上避免人为干预，采用启发式搜索方法

［14］

确定

ε

，再

通过最佳的

ε

确定MinPts，相关计算公式如下：

n

H(x)=

∑

p(tra

1

n

i

)lb

=-

p(tra

i

)lbp

i=1

p(tra

(tra

i

)

（9）

i

)

∑

i=1

p(tra

|

N

ε

(tra

i

)

|

i

)=

∑

n

（10）

|

N

ε

(tra

i

)

|

j=1

第47卷第4期俞庆英，赵亚军，叶梓彤，等：基于群组与密度的轨迹聚类算法

105

其中,

N

ε

(tra

i

)

为轨迹样本tra

i

的邻域集合,

|

N

ε

(tra

i

)

|

为tra

i

邻域集合中的轨迹样本个数。

由式（9）和式（10）可确定使H（x）最小的半径参

数，即最佳半径参数

ε

。在此基础上，计算数据集的

邻域轨迹样本数的平均值

avg

|N(tra)|

，MinPts的取值范

围为

[

avg

|N

ε

(tra

i

)|

+1

]

~

[

εi

avg

|N

ε

(tra

i

)|

+3

]

。

3.4

3.4.1

结果分析

表1

运行时间的对比

和表2分别为不同半径参数和邻域密度阈

值下本文算法和TRACLUS算法在DS1数据集上的

运行时间。可以看出，2种算法的运行时间均随着参

数值变化而改变，本文算法在数据集DS1上的运行

时间远短于TRACLUS算法。

表1不同

ε

值下2种算法在DS1数据集上的运行时间

Table1Runningtimeoftwoalgorithmson

DS1datasetwithdifferent

ε

values

s

算法

ε=281ε=284=287ε=

本文算法

943

293

TRACLUS算法

3670

999

3605

965

ε

3645

969

ε=290

3619

965

3646

表2不同MinPts值下2种算法在DS1数据集上的运行时间

Table2Runningtimeoftwoalgorithmson

DS1datasetwithdifferentMinPtsvalues

s

算法

MinPis=6MinPis=7MinPis=8MinPis=9MinPis=10

本文算法

9329

TRACLUS

算法

35443547352435343536

表3和表4分别为在不同半径参数和邻域密度

阈值下本文算法和TRACLUS算法在DS2数据集上

的运行时间。可以看出，在规模较大的轨迹数据集

上进行聚类时2种算法的运行时间均较长，本文算

法在数据集DS2上的运行时间远短于TRACLUS算

法，其在不同参数下时间开销更少。

表3不同

ε

值下2种算法在DS2数据集上的运行时间

Table3Runningtimeoftwoalgorithmson

DS2datasetwithdifferent

ε

values

h

算法

ε=

3

190ε=205ε=

本文算法

3

210

TRACLUS算法

17.

.

3

7

ε=

3

95

16.

.

8

5

ε=

3

200

16.

.

5

3

16

3

.

.

7

3

17.

.

1

2

表4不同MinPts值下2种算法在DS2数据集上的运行时间

Table4Runningtimeoftwoalgorithmson

DS2datasetwithdifferentMinPtsvalues

h

算法

MinPts=

13

MinPts=

14

MinPts=MinPts=MinPts=

1.9

15

1.9

16

2.2

17

本文算法

2.12.0

TRACLUS

算法

16.817.117.317.517.6

由上述分析结果可知，本文算法在DS2数据集上运

行时间较TRACLUS算法的减幅比DS1数据集更显著。

由此可知，本文算法可有效地应用于海量的轨迹数据集。

3.4.2

图3

聚类结果准确性的对比

为不同半径参数和不同邻域密度阈值下本文

算法和TRACLUS算法在DS1数据集上聚类结果的

TSSE值对比情况。可以看出，本文算法的TSSE值较

TRACLUS算法更小，其在DS1数据集上聚类效果更好。

图32种算法在DS1数据集上聚类结果的TSSE值对比

Fig.3ComparisonofTSSEvaluesofclusteringresultsof

twoalgorithmsonDS1dataset

图4为不同半径参数和不同邻域密度阈值下本

文算法和TRACLUS算法在DS1数据集上聚类结果

的轮廓系数值对比情况。可以看出，本文算法的轮

廓系数值较TRACLUS算法更接近1，表明其在DS1

数据集上聚类结果更准确。

图42种算法在DS1数据集上聚类结果的轮廓系数值对比

Fig.4Comparisonofsilhouettecoefficientvaluesof

clusteringresultsoftwoalgorithmsonDS1dataset

图5和图6分别为不同半径参数和不同邻域密

度阈值下本文算法和TRACLUS算法在DS2数据集

上聚类结果的TSSE值和轮廓系数值对比情况。可

以看出，2种算法的TSSE值和轮廓系数值随着半径

参数和不同邻域密度阈值的变化相应改变，本文算

法的聚类评价结果较TRACLUS算法更优。

106

计算机工程

2021年4月15日

图52种算法在DS2数据集上聚类结果的TSSE值对比

Fig.5ComparisonofTSSEvaluesofclusteringresultsof

twoalgorithmsonDS2dataset

图62种算法在DS2数据集上聚类结果的轮廓系数值对比

Fig.6Comparisonofsilhouettecoefficientvaluesof

clusteringresultsoftwoalgorithmsonDS2dataset

3.4.3

由上

聚类结果的可视化

述对聚类结果准确性分析可知，在DS1数

据集上，当

ε

=281且MinPts=10时，本文算法聚类效

果最好，选择该条件下的聚类结果进行可视化显示。

类似地，在DS2数据集上，当

ε

=190且MinPts=17时，

本文算法聚类效果也最好，选择该条件下的聚类结

果进行可视化显示。图7和图8分别为本文算法在

DS1数据集和DS2数据集上的可视化聚类结果（彩

色效果参见《计算机工程》官网HTML版）。

图7本文算法在DS1数据集上的可视化聚类结果

Fig.7Visualclusteringresultsoftheproposedalgorithm

onDS1dataset

图8本文算法在DS2数据集上的可视化聚类结果

Fig.8Visualclusteringresultsoftheproposedalgorithm

onDS2dataset

4结束语

本文提出一种结合群组和密度的聚类算法。根

据MDL原则将一整条轨迹划分为若干条轨迹段，通

过遍历轨迹数据集将所有轨迹段划分到相应的群组

中，以减少聚类时邻域集合搜索过程中冗余的计算

次数，最终利用群组和密度对轨迹数据集进行聚类。

实验结果表明，与基于密度的TRACLUS算法相比，

该算法运行时间更短且聚类准确性更高，运行时间

的减幅随轨迹数据集规模的扩大而增加。后续将结

合并行和分布式计算框架，进一步缩短该算法在海

量轨迹数据集上的运行时间并提升聚类准确性。

参考文献

1］torydatamining：anoverview［J］.

ACMTransactionsonIntelligentSystemsandTechnology，

2］LÜ

2015

Mingqi

，6（3）：1

，

-41

CHEN

.

Ling，XUZhenxing，

discoveryofpersonallysemanticplacesbasedontrajectory

datamining［J］.Neurocomputing，2016，173（10）：1142-

3］GUREVICH

1153.

IB，ptiveapproach

toimageanalysis：imageformalizationspace［J］.Pattern

RecognitionandImageAnalysis，2012，22（4）：495-518.

4］SHARAFMA，KOWALSKIBR，WEINSTEINB.

Constructionofphylogenetictreesbypatternrecognition

procedures［J］.ZeitschriftFurNaturforschung，1980，35（5）：

5］COMAS

508-513.

DS，MESCHINOGJ，NOWEA，etal.

Discoveringknowledgefromdataclusteringusing

automatically-definedintervaltype-2fuzzypredicates［J］.

ExpertSystemswithApplications，2017，68（2）：136-150.

6］PIRAYREA，COUPRIEC，DUVALL，

clust：cluster-assistedgeneregulatorynetworkinference

refinement［J］.IEEE/ACMTransactionsonComputational

BiologyandBioinformatics，2018，15（3）：850-860.

［

［

［

［

［

［

第47卷第4期俞庆英，赵亚军，叶梓彤，等：基于群组与密度的轨迹聚类算法

107

［7］CHENGQiming，ZHANGQiang，CHENGYinman，etal.

Short-termphotovoltaicpowerpredictionmodelbasedon

hierarchicalclusteringofdensitypeaksalgorithm［J］.High

VoltageEngineering，2017，43（4）：1214-1222.

［8］WANGZengfeng，ZHANGHao，LUTinging，-

basedlocalizationalgorithmforwirelesssensornetworks

usingconnectivityandRSSrank［J］.IEEEAccess，2018，

［9］VISSER

6：8426-8439

E，NIJHUIS

.

EH，BUITELAARJK，ion-

basedmassclusteringoftractographystreamlines［J］.

Neuroimage，2011，54（1）：303-312.

［10］GUOGongde，CHENLifei，YEYanfang，r

validationmethodfordeterminingthenumberofclusters

incategoricalsequences［J］.IEEETransactionsonNeural

NetworksandLearningSystems，2017，28（12）：2936-2948.

［11］HEXiongxiong，GUANJunyi，YEXuanzuo，etal.A

density-basedandgrid-basedclustercentersdetermination

clusteringalgorithm［J］.ControlandDecision，2017，32（5）：

913

何熊熊

-919

，

.（

管俊轶

inChinese）

，叶宣佐，等.一种基于密度和网格的簇

心可确定聚类算法［J］.控制与决策，2017，32（5）：913-919.

［12］ESTERM，KRIEGELHP，SANDERJ，ty-

basedalgorithmfordiscoveringclustersinlargespatial

databaseswithnoise［C］//Proceedingsofthe2ndInternational

ConferenceonKnowledgeDiscoveryandDataMining.

NewYork，USA：ACMPress，1996：226-231.

［13］GAOQiang，ZHANGFengli，WANGRuijin，etal.

Trajectorybigdata：areviewofkeytechnologiesindata

processing［J］.JournalofSoftware，2017，28（4）：959-

992

高强

.（

，

in

张凤荔

Chinese）

，王瑞锦，等.轨迹大数据：数据处理关键

技术研究综述［J］.软件学报，2017，28（4）：959-992.

［14］LEEJG，HANJ，toryclustering：a

partitionandgroupframework［C］//Proceedingsof2007

k，

USA：ACMPress，2007：593-605.

［15］GUTTMANA.R-trees：adynamicindexstructurefor

spatialsearching［C］//Proceedingsof1984International

k，USA：

ACMPress，1984：47-57.

［16］PROCOPIUCO，AGARWALPK，ARGEL，-

tree：adynamicscalablekd-tree［C］//Proceedingsof

2003

Databases.

International

Berlin，Germany：

Symposium

Springer，

onSpatial

2003

and

：46

Temporal

-65.

［17］DAIYangyang，LIChaofeng，yclustering

algorithmwithinitialpointoptimizationandparameterself-

adaption［J］.ComputerEngineering，2016，42（1）：203-209.

（inChinese）

戴阳阳，李朝锋，徐华.初始点优化与参数自适应的密

度聚类算法［J］.计算机工程，2016，42（1）：203-209.

［18］GHANBARPOURA，AN：an

extensionofDBSCANtodetectclustersinmulti-density

datasets［C］//Proceedingsof2014IranianConferenceon

gtonD.C.，USA：IEEEPress，

［19］ANKITA，

2014：1-5.

edDBSCANusingparticle

swarmoptimizationforspatialhotspotidentification［C］//

Proceedingsof2018InternationalConferenceonCon-

gtonD.C.，USA：IEEEPress，

［20］BRYANT

2018：1-3.

AC，-DBSCAN：adensity-based

clusteringalgorithmusingreversenearestneighbordensity

estimates［J］.IEEETransactionsonKnowledgeandData

Engineering，2018，30（6）：1109-1121.

［21］MERKA，CALP，WOŹbutedDBSCAN

algorithm-conceptandexperimentalevaluation［C］//

Proceedingsofthe10thInternationalConferenceon

，Germany：Springer，

［22］GAO

2017：

Xu，

472

GUI

-480

Zhipeng，

.

LONGXi，-DBSCAN：

ahighperformanceDBSCANalgorithmbasedonK-DTree

andSparkGraphX［J］.GeographyandGeo-Information

Science，2017，33（6）：1-7.（inChinese）

高旭，桂志鹏，隆玺，等.KDSG-DBSCAN：一种基于K-DTree

和SparkGraphX的高性能DBSCAN算法［J］.地理与地

理信息科学，2017，33（6）：1-7.

［23］CHENZhihua，GUOJianming，

algorithmclusteringformassiveaisdatabasedonthe

hadoopplatform［C］//Proceedingsof2017International

ConferenceonIndustrialInformatics-ComputingTechno-

logy，IntelligentTechnology，IndustrialInformation

gtonD.C.，USA：IEEEPress，2017：

［24］ZHANG

25-28.

D，LEEK，chicaltrajectoryclustering

forspatio-temporalperiodicpatternmining［J］.Expert

SystemswithApplications，2018，92（2）：1-11.

［25］WANGJiayu，ZHANGZhenyu，CHUZheng，etal.A

trajectorydatadensitypartitionbaseddistributedparallel

clusteringmethod［J］.JournalofUniversityofScienceand

TechnologyofChina，2018，48（1）：47-56.（inChinese）

王佳玉，张振宇，褚征，等.一种基于轨迹数据密度分

区的分布式并行聚类方法［J］.中国科学技术大学学

报，2018，48（1）：47-56.

编辑宋圆