基于Spark 并行化的改进K-means 轨迹聚类的方法

中国科学技术大学先进技术研究院 孙明悦 马胤垚

本文设计了一种对K-means 初始化改进的Canopy+Kmeans++聚类方法，提高上轨迹聚类算法的效率，为进一步提升轨迹大数据聚类的迭代计算效率，本文利用Spark计算架构的可伸缩性和分布式等特，实现Canopy+Kmeans++轨迹聚类算法的并行化，并通过对比实验来证明该并行化聚类方案的有效性。

1 模型与方法

1.1 LCSS 距离归一化设计

LCSS(A,B)为两条轨迹间的最长公共子序列长度，表示轨迹间匹配相似点的对数情况[1]。相似点对数占整条轨迹的比值越大，则两条轨迹距离越近，相似度越高。为实现海量轨迹聚类时各轨迹间的距离判定能够统一，对上述LCSS 距离做了改进，进行归一化处理，设计了Jaccard\_L 轨迹相似性度量方法，定义计算如公式（1）所示：

Jaccard_L(A,B)相似度表示将A和B的LCSS距离转化为相似性度量值，|N|和|M|表示两条轨迹的长度。相似度J(A,B)取值范围为[0,1]，是对相似距离的归一化。其中0 表示两条轨迹完全不具有相似性，1 表示两条轨迹完全一致，经过计算，若两条轨迹的J(A,B)值超过阈值T，认为两条待测轨迹相似。

1.2 基于初始化改进的轨迹聚类

K-means 是一种经典的基于划分的聚类算法，其优化目标函数如公式（2）所示：

其中，K是设定好的聚类数量，p表示样本点，dist是样本点与中心点的距离，本文用轨迹相似度Jaccard_L表示，C是聚类中心轨迹，用矩阵表示，J是最小目标函数，通过迭代找到最优解。

1.2.1 确定聚类数目K 值

本课题利用Canopy 算法解决K-means 的K 值无法确定问题。Canopy 算法不需要事先指定最终聚类数目，可以利用此算法对海量大数据进行聚类。

1.2.2 改进后的算法

改进后的Canopy+K-means++主要步骤如下：

（1）读取历史轨迹数据集，指定两个轨迹相似度阈值T1、T2（T1>T2），T1、T2由测试结果调整。

（2）在轨迹数据集中随机选取1 个样本轨迹P，然后计算P 与所有其他Canopy 集合中心之间的轨迹相似度Jaccard_L（如果没有集合就把P 点当作新的Canopy，为其创建Buffer），如果该相似度小于T1，则将轨迹P 加入到这个集合的Buffer。如果轨迹P 与集合中心距离小于T2，则将P 从这个集合的Buffer 中删除，如果到所有集合中心的距离都大于T2，把P 点当作新的Canopy，为其创建新Buffer。

（3）迭代执行步骤（2），直到轨迹数据集内数目为空。汇总所有Canopy 集合个数,也就得到了K-means聚类K 值。

（4）计算待测轨迹集X 相对于聚类中心轨迹N 的轨迹相似度矩阵，采用上述提出的Jaccard_L 方法。

（5）计算待测轨迹被选为聚类中心点的概率，将概率最大的样本轨迹作为聚类中心轨迹N+1，将N 替换为N+1，重复（4）直到聚类中心轨迹数目等于K。概率计算公式如公式（3）所示，D(x,N)表示待测轨迹x到聚类中心N的相似度。

（6）汇总聚类中心点，得到初始聚类中心轨迹。

（7）基于初始聚类中心轨迹和聚类K 值，以Jaccard_L 作为轨迹相似度，迭代执行K-means 聚类算法，直至聚类簇收敛。

1.3 Spark 分布式计算架构

为了能够在集群上运行应用程序，首先创建Spark Context，然后连接到多种Cluster Manager，例如Standlone或YARN,用于应用程序资源调度。连接上Cluster Manager后，Cluster Manager 会在集群中为各个Slave 节点应用程序申请执行器，最后数据节分成多个Task 任务分发给各个执行器执行，多个Executor 按照DAG 任务图独立执行任务，开展任务具体的数据处理和计算工作，实现程序的分布式及并行化执行。

1.4 轨迹聚类的并行化实现

Step1：创建Spark 对象SparkContext，各分区Exctuor节点完成初始化并通过SparkContext 向资源管理器(Cluster Manager)申请分配资源。

Step2：使SparkSQL 算子对迹数仓数据dwd\_track\_summary\_db 表格先后按照Geohash 编码对轨迹起点进行粗聚类得到地理位置分块索引表格，以一个位置分区数据为例，通过轨迹索引表格从数仓文件中读取轨迹原始数据至缓存中，对原始轨迹数据做解压缩、ETL 等一系列预处理。并利用TransFormation 转换成为RDD[Vector]格式，后对每个分区做Canopy+Kmeans++并行聚类操作。

Step3：采用Canopy-kmeans++改进算法，获得类簇个数K 值和首次参与计算的聚类中心轨迹。并将聚类中心轨迹广播到各个分区，用mapPartitions 算子将轨迹分发至不同的Executor 节点，以下一个分区代码对所有分区适用。

Step4：计算轨迹间的Jaccard_L 相似度矩阵，遍历分区轨迹，计算轨迹与哪个聚类簇中心轨迹相似度最高，并加入该聚类簇的case 类CenterInfo 中，CenterInfo 数据格式为（聚类簇编号id,单个轨迹向量）。

Step5：以CenterInfo 的聚类簇编号id 作为Key,单个轨迹向量作为Value,对各个Executor 节点轨迹数据用ReduceByKey 进行聚合计算。

Step6：计算新的聚类簇中心轨迹。找到每个聚类簇中到其他簇内成员Jaccard_L 相似度距离平均值最小的轨迹，得到最新的聚类中心轨迹，并拉回至Driver 中。

Step7：判断各个簇的聚类中心轨迹是否已经收敛不变或者与原来的中心轨迹距离小于阈值，如果不满足则去除已经收敛的聚类簇，剩下的继续返回Step2 进行迭代，如果满足则得到最终聚类结果。

Step8：迭代结束后返回Canopy+K-means++模型生成的簇，完成轨迹聚类，并从每个簇中选取与簇中其他轨迹Jaccard 相似度最高的一条轨迹作为特征模型轨迹。

2 实验结果与分析

2.1 实验环境和实验数据

实验环境:首先在本地自建Spark 集群，包括3台服务器。其中1 台服务器作为驱动器（Master）节点，2 台服务器作为执行器(Worker)节点。操作系统是Centos7，Spark 版本为Spark-2.2.0-bin-hadoop3.1，Scala 版本为scala-2.11.8。

实验数据:本文通过智能可穿戴设备采集数据，并通过采集和同步，将数据存入Hive 数据库系统，从Hive数据库利用SQL 引擎查询某城市的一个区数据集H_Data共4043 条轨迹，每条轨迹由100-1000 个个数不等的轨迹点构成，每个轨迹点P=(lat,lng,t)，分别表示经纬度和时间戳；提取轨迹数据的环形轨迹至实验集群中，首先按照Geohash 编码前缀对轨迹进行粗聚类，然后以Jaccard_L为相似性度量再对粗聚类簇根据本文所提出算法进行详细聚类。

2.2 Canopy+K-means++聚类性能测试。

在轨迹聚类算法中，簇内的轨迹到中心轨迹的相似距离越小，到其他簇的距离越大，聚类的质量越高[2]。本文利用轨迹间Jaccard_L 的轮廓系数来表示轨迹的聚类质量，定义计算公式如式（4）所示：

其中a表示某一轨迹到簇内中心轨迹的Jaccard_L相似度，b表示该轨迹到其他轨迹簇中心轨迹的相似度，Si表示第i个轨迹的轮廓系数，S表示所有轨迹轮廓系数，代表聚类质量，取值范围为（-1，1），当轮廓系数接近1时，说明轨迹聚类相似度较高，且不同聚类簇之间相似度较低，轨迹质量越好。

本文在其他条件不变的情况下，将Canopy+Kmeans++算法改成其他聚类算法，QuickBundles 设置为与Canopy+K-means++相同K 值，OPTICS 参数ε=0.85，MinPts=8 时，与本文K 值最为接近。将多个实验进行准确率比较，定义运行时间比表示为FT=Ti/TL，TL表示应用Canopy+Kmeans++算法聚类运行时间[3]，当FT＞1时，该算法运行时间复杂度比Canopy+Kmeans++算法高,结果可知，OPTICS 和Canopy+Kmeans++方法准确率较高，且聚类质量高，OPTICS 是对DBSCAN 的一种改进，但是OPTICS 的时间复杂度最高，且需要调节ε、MinPts 两个参数；QuickBundles 是一种快速聚类，时间复杂度低，但是一旦划分到某个簇就不会改变，精确度较低；而层次聚类虽然不用提前设定K 值，但聚类终止条件不好设定，且只适合小型数据聚类迭代，在海量轨迹聚类中，算法时间复杂度快速增长，聚类质量差进而影响后续轨迹挖掘效果。Canopy+K-means++算法可以提前确定聚类数目，且对初始化聚类中心轨迹做了优化，聚类质量也相对较高，相比较DBSCAN 和OPTICS，K-means 本身是一种比较快速的聚类方式。

2.3 Spark 并行化计算性能实验

为测试Spark 并行化后性能是否提高，提取了某城市地区的轨迹数据分别导入单机（串行计算）和Spark 集群服务器，然后编写Canopy+K-means++聚类代码并运行，进行A/Btest 测试，设置num-excutors 参数为1，executor-cores 参数为4，测试轨迹数量与计算性能的关系。比较了单机情况下运行结果和并行计算结果运行速度，发现Spark 并行化后的Canopy+K-means++模型计算速度明显优于串行模型计算（单机环境）速度，说明Spark 引擎提高了计算效率，并行化处理后该聚类方法适用于海量数据处理情况。

2.4 并行计算加速比实验

并行计算方式下，定义加速比计算如公式（5）所示：

其中Ts表示单机运行时间，n表示并行计算时numexcutors 取值，分别取约5k 和3k 条轨迹，测试算法在Spark 并行计算情况下，设置num-excutors 为1。随着executor-cores 数目的增加，Canopy+K-means++算法并行计算加速比越来越大。但随着Cores 数目超过6 时，加速比随Cores 节点增加变化不大，这也与节点数目无节制增多反而会影响计算性能经验一致。另外，随着数据量增加，Cores 数目也增加，其加速效果也就更为明显，说明Spark 并行化后的算法计算性能更适合于海量数据。

3 结语

本文主要研究了轨迹大数据聚类的实现方案，以Jaccard_L 为轨迹相似性度，利用Canopy+K-means++算法进行轨迹聚类，然后利用Spark 计算将数据集分区后分发给多个子节点，实现轨迹聚类算法的并行化设计，并给出Canopy+K-means++的并行化步骤。通过在可穿戴设备上采集的轨迹数据集分别在单机和Spark 集群运行，并进行A/B Test 实验，验证了改进的Canopy+Kmeans++算法相较于其他聚类方法，聚类质量高且时间复杂度较好。另外，基于Spark 并行化的算法模型计算速度明显优于单机环境模型，且随着数据量的增加，该并行化算法具有更好的时效性，综上所述，基于Spark并行化的改进的Canopy+K-means++算法更适用于轨迹大数据聚类场景。

引用

[1] 江红.一种新的时空轨迹聚类算法KST-DBSCAN的研究[D].武汉:华中师范大学,2022.

[2] 俞庆英,赵亚军,叶梓彤,等.基于群组与密度的轨迹聚类算法[J].计算机工程,2021,47(4):100-107.

[3] 严斯柔.基于GPS数据的轨迹聚类算法研究[D].杭州:杭州电子科技大学,2021.