一种基于高斯混合模型的海上浮标轨迹聚类算法

荆晓刚，葛丽阁，孙伟

（1.上海港引航站，上海 200082；2.上海海事大学信息工程学院，上海 201306)

0 引言

随着计算机技术的不断发展和移动对象跟踪技术的不断完善，人们采集到大量的运动目标轨迹数据，为了找出这些数据中隐藏的知识，移动对象轨迹聚类技术应运而生。目前，在轨迹聚类方面的研究，主要有朱燕[1]等基于聚类的出租车异常轨迹检测，通过将单条轨迹划分为若干子段，再计算各轨迹间的相似度，基于距离和密度的聚类来实现出租车异常轨迹检测，但其算法时间代价较高；石陆魁[2]等人提出了基于时空模式的轨迹数据聚类算法，但聚类算法效率较低；吴熙[3]等人提出的基于轨迹聚类的超市顾客运动追踪，对顾客部分遮挡、复杂运动轨迹以及异步运动等多种特殊情况具有较高的鲁棒性，但算法时间复杂度较高。以上研究工作都是针对陆地上的运动目标。海上目标的运动轨迹与陆地不同，其不受道路、轨道的限制，并且海上目标受力复杂，其轨迹点随机性更强，轨迹也更加复杂不规则。本文针对海上目标轨迹的特征，提出一种基于高斯混合模型的浮漂轨迹聚类算法。海上目标轨迹分析的研究工作，可以使人们更好地掌握和预测海上航行轨迹，并应用于海上搜救、航路规划等领域。

1 高斯混合模型

所谓混合高斯模型（GMM）[6]就是指对样本的概率密度分布进行估计，而估计采用的模型（训练模型）是几个高斯模型的加权和（具体是几个要在模型训练前建立好）。每个高斯模型就代表了一个类。高斯混合模型是单一高斯概率密度函数的延伸，对样本中的数据分别在几个高斯模型上投影，就会分别得到在各个类上的概率。然后，可以选取概率最大的类所为判决结果。

假设每个点均由一个单高斯分布生成，而这一批数据共由M个单高斯模型生成，具体某个数据xi属于哪个单高斯模型未知，且每个单高斯模型在混合模型中占的比例αj未知，将所有来自不同分布的数据点混在一起，该分布称为高斯混合分布[7]。高斯混合模型的公式如公式1所示：

GMM 通常用 EM（Expectation Maximum）算法[10]对GMM参数进行估计。算法流程为：

步骤1：初始化

协方差矩阵Cj0设为单位矩阵，每个模型比例的先验概率；均值 μj0设为随机数。

步骤 2：估计步骤（E-step）

令αj的后验概率如公式（3）所示：

步骤3：最大化步骤（M-step）

更新权值:

更新均值：

更新方差矩阵：

步骤4：收敛条件

2 浮标轨迹的GMM聚类算法

2.1 聚类算法实现

下面，针对海上浮标漂移轨迹提出的GMM聚类算法的伪代码如下：

输入：浮标轨迹数据集 Data={d1，d2，，dn}；测试用例轨迹集 TData={D1，D2，…，Dm}。

输出：轨迹聚类结果。

1.D*={T1，T2，…，Tn};//已知轨迹点序列

2.si=GMM_ini（Data，k）;//GMM算法初始化，其中参数k为聚类个数

3.gp=gaussPDF（Data，si）;//计算高斯分布

4.m=EM（Data,gp）;//极大似然估计过程，更新参数

5.for i=1:k

6.ε=10-5//迭代停止条件

7.Px=gaussPDF（Data,si）//得到似然值最大的分类结果

8.End

2.2 算法有效性验证

本文通过高斯混合模型对海上浮标轨迹点进行聚类研究，其数据来源来自于NOAA的The GDP Drift Data Assembly Center（DAC）的 Hourly Data，通过纬度、经度和时间的三维数据进行轨迹点聚类，分别选取2016年1月12日和2016年5月28日两天的数据[11]，通过MATLAB 2012a的实验环境下的实验结果仿真如图1和图2所示。

图1 原始轨迹点集和GMM聚类结果

图2 原始轨迹点集和GMM聚类结果

本文通过高斯混合模型对海上轨迹的聚类研究，提出的GMM算法可以大大减少一些嘈杂且很不规则的轨迹对整个轨迹的影响，可能会增加航行途中不测事件的风险率。

3 GMM算法性能分析

为了更好的衡量高斯混合模型的性能优劣，本文采取了与K-means算法对同一轨迹点进行聚类分析，其结果如图3所示。

通过对上图的轨迹仿真可以看出，高斯混合模型比k-means聚类效果要好，K-means容易将一些处于两个簇的轨迹点错分到另一个簇中。另外，GMM聚类算法的到聚类中心的平均距离较K-means算法更小，说明本文提出的GMM聚类算法优于K-means算法，如图4所示。GMM的优点是投影后样本点不是得到一个确定的分类标记，而是得到每个类的概率，这是一个重要信息。GMM每一步迭代的计算量比较大，大于K-means。GMM的参数估计基于EM算法，效果较为理想。

图3 GMM算法和K-means算法聚类结果对比

4 结语

海上目标的运动轨迹较陆地上具有不受限道路、轨道限制，更不规则等特征，给轨迹分析和轨迹预测带来难题。本文针对海上浮漂的漂移轨迹提出一种基于高斯混合模型的轨迹聚类算法。以NOAA的漂浮浮标数据作为实验数据集，算法实验表明该算法较K-means算法具有更优的聚类结果。GMM算法更适用于海上运动目标复杂且不规则的轨迹，其轨迹聚类结果可进一步用于轨迹预测，未来在海上搜救、航路规划等领域有广泛的应用前景。

图4 两个聚类算法的平均聚类距离比较

[1]朱燕,李宏伟,樊超,等.基于聚类的出租车异常轨迹检测[J].计算机工程,2017,43（2）:16-20.

[2]石陆魁,张延茹,张欣.基于时空模式的轨迹数据聚类算法[J].计算机应用,2017,37（3）:854-859.

[3]王熙,吴为,钱沄涛.基于轨迹聚类的超市顾客运动跟踪[J].智能系统学报,2015（2）:187-192.

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

[5]王田璐.轨迹聚类与基于高斯过程回归模型的轨迹识别算法研究[D].上海交通大学,2013.

[6]Ying J C,Lee W C,Weng T C,et al.Semantic Trajectory Mining for Location Prediction[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems.ACM,2011:34-43.

[7]乔少杰,金琨,韩楠,等.一种基于高斯混合模型的轨迹预测算法[J].软件学报,2015,26（5）:1048-1063.

[8]Song CM,Qu ZH,Blumm N,Barabsi AL.Limits of Predictability in Human Mobility.Science,2010,327（5968）:1018-1021.

[9]徐涛,陈雪蕊,吕宗平.基于航迹聚类的终端区飞行程序轨迹表示[J].四川大学学报（工程科学版）,2016,48（6）:188-196.

[10]翟婷,宋文爱,富丽贞,等.基于路网感知的时空轨迹聚类[J].计算机工程与设计,2016,37（3）:635-642.

[11]冯涛,郭云飞,黄开枝,等.基于隐马尔可夫模型的行为轨迹还原算法[J].计算机工程,2012,38（18）:1-5.