自适应高斯混合模型海上移动对象浮标轨迹聚类研究

葛丽阁，孙伟

（上海海事大学信息工程学院，上海 201306）

0 引言

聚类分析是数据静态分析的一门关键技术，在机器学习、人工智能和数据挖掘等领域应用广泛。聚类是为了提取相同的特征从而对相似度高的事物进行统一分析研究，聚类的评价标准时类内相差越大越好，反之簇间相差愈小愈好。

由于数据统计分析的难度性较大，数据的概率分布往往比较随意，一般地，近年来，高斯混合模型因在复杂环境计算简便、易于实现及本身具有一定的降噪性的优势而得以大面积使用，所以该数据的概率分布可以采用混合的高斯模型来任意的逼近。但是传统的高斯混合模型聚类数需要人工给出，采用简单稳定的期望最大化EM算法求解未知标记的最大似然值，但是EM算法收敛过程慢而且会使参数陷入局部最优值[1]。因此如何设置混合模型的参数对聚类的性能研究亟待解决。

1 聚类研究现状

随着国际经济联系的日益加强，国际分工的日趋明显，海洋运输业发展甚为迅速。在诸多重要应用领域中，如移动导航、地质勘察和货物运输等，用户需要及时查询和分析移动对象的位置信息，移动对象轨迹聚类已渐渐成为移动对象数据库管理的重要研究方向。当前对移动对象研究则通过聚类挖掘轨迹运动模式，将具有相似度较高的轨迹归为一类，以对大量数据进行挖掘分析[1]。对海上移动对象轨迹聚类目的是：一是提高陆上交通信息系统的智能化水平；二是在一定时间内，可以提醒遇有礁石和撞船等不测事件的移动目标绕过危险区域安全航行。海洋航行没有固定的航线限制，运动环境复杂多变，如何对海上移动对象轨迹分析成为亟需解决的难点。当前已有一些研究成果，如移动对象的聚类、异常点检测和位置查询等。其中，对轨迹聚类的研究主要有范敬雅[2]等提出的基于EM算法的高斯混合模型的聚类分析，通过贝叶斯信息准则选取最优类来分析2015年31个省的GDP和人均GDP，证实了算法的实用性和可靠性但是效率不高；张燕杰[3]等的基于高斯混合模型的聚类分析通过研究有限和无穷的高斯混合模型的算法更好的聚类分析，但是时间代价较高；石陆魁[4]等人提出了基于时空模式的轨迹数据聚类算法，但是聚类效率较低；陈英[5]等人提出的高斯混合模型聚类及其优化算法研究，通过增加惩罚项改进EM算法，改善了聚类性能，提高了算法的学习效率和鲁棒性但是需要给定一个惩罚权重并且算法变得更复杂；乔少杰[6]等人提出的一种基于高斯混合模型的轨迹预测模型，主要对停车场轨迹分析。针对以上弊端，加之目前大多的聚类算法的中心主要是研究陆地轨迹，对海上轨迹的聚类工作较少，由于当今海洋运输业的快速发展和层出不穷的安全事故，所以本文就提出了一种基于自适应高斯混合模型的海上浮标轨迹聚类算法，通过对海上浮标得到的轨迹点进行聚类分析，可以更好地掌握海上航线情况减少海上航行事故的发生率，以及对将来轨迹预测，异常点监测等研究提供更好的研究方向。

2 高斯混合模型原理

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

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

令φ(αj,μj),Cj，GMM共有M个单高斯模型。我们需要通过样本集 x来估计 GMM的所有参数[9]：Φ=(φ1,φ2,…,φM)T，样本 x的概率如公式（2）：

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

Step1：初始化

协方差矩阵Cj0设为单位矩阵，每个模型比例的先

Step2：估计步骤[11]（E-step）

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

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

Step4：收敛条件

不断地迭代步骤Step2和Step3，重复更新上面三个值，直到 p(X |Φ)-p(X |Φ )'<ε, 其中 p(X |Φ )'为更新参数后计算的值，即前后两次迭代得到的结果变化小于一定程度则终止迭代，通常ε=10-5。

因轨迹数据的概率分布往往较复杂，因此可通过高斯混合模型来任意逼近使之问题简单化，这为轨迹聚类方面的研究打开了一个新天地[15]。但高斯混合模型聚类数目大多根据人们经验任意指定不仅降低了聚类的准确性，而且对海上循环多变的漂浮物轨迹自适应性较差，因此需要对高斯混合模型做进一步的改进工作。

3 自适应GMM聚类算法

3.1 自适应聚类

GMM聚类使用K-means初始化EM的思想，进行自适应确定聚类簇个数的过程中[12]，会对聚类结果进行评判，必然也会确定高斯混合模型的各个参数，若以此时得到的各个高斯元参数作为下一次迭代的参数，如此初始化得到的结果会更接近最优值。

（1）自适应GMM聚类的实现步骤

针对海洋上移动对象非受限性和强波动性等特征的轨迹研究和避免传统的GMM聚类算法的弊端，本文实现了自适应的聚类算法，命名Apdative Gaussian Mix⁃ture Model Clustering（A-GMM）其具体实现步骤如下：

①先假设已经限制有k0个高斯元[13]（即聚类簇，一般取较小值），用普通的EM算法对这个模型进行优化，估计其均值，协方差等参数，计算出聚类结果classoutcome；

②在迭代计算出第i个样本归于第j类的概率w（i,j）后，将第i个样本分入使其概率最大的类。而聚类后类之间差别较大，即样本i归入classoutcome（i）类的概率应当比归入第j类的概率大，故可以用二者的比值衡量聚类的效果。即用D2（i,j）表示第i个样本归入第classoutcome（i,j）的概率与归入第j类的比值。

③对D2（i,j）设定一个最小阈值minp（根据大量实验minp的取值在1.0附近，本文取值为1.03），通过给定minp的值便可以衡量类之间差距的大小。因此计算出D2的最小值后与设定的阈值minp相比较，若小于给定的minp，则聚类簇个数增加，若大于minp则已满足条件，停止增加聚类簇个数。

④在增加聚类簇个数后，就面临着新模型的参数初始化问题，但上一个模型（K未增加时）的参数已经得到确定，这组参数可以说是比较接近最优解的，因此就让添加新模型之前的高斯元参数保持不变，新增加的高斯元对应的协方差矩阵用原来就有的高斯元的均值代替，它在整个高斯混合模型中所占的比例alpha为原来就有的高斯元的比例的平均值。而新增加的高斯元特征均值mu取自D2矩阵中最小值所对应的样本作为新增高斯元的特征均值（因为这个样本的聚类效果不好）。如此循环就完成了新模型的参数初始化即自适应聚类。但有时会出现新增加的高斯元所占的比例十分小（我在程序中取的是小于1/（100×K）），说明新增加的这个类对整个模型的改进效果并不大，故遇到这种情况时可停止增加聚类簇.此外，由于最开始的高斯混合模型还是随机初始化参数的，使得最后得到的结果也具有一定的随机性，解决方法是多次运行程序，取聚类簇个数K较小的一次的计算结果。

（2）自适应GMM（A-GMM）聚类流程图

为了更好地描述自适应GMM聚类的实现过程，其具体的流程图如图1所示：

图1 自适应GMM聚类实现流程图

3.2 实验仿真

本文采用自适应高斯混合模型的聚类算法（AGMM）对海上漂浮物轨迹通过浮标获取，使用浮标是因为它可设置在难以或不宜设立固定航标之处且能实时获取海上移动对象的轨迹数据。实验数据来源于NO⁃AA[15]的 The GDP Drift Data Assembly Center（DAC）的Hourly实时轨迹，连续记录180天。由于轨迹数量较大，本文就任意选取某三个月经度（坐标X轴）、纬度（坐标Y轴）中的500个轨迹点组成数据集进行聚类分析。实验环境为MATLAB 2012a，实验硬件平台为:In⁃tel Core 2 Duo P8700 2.53GHz CPU,2GB内存,操作系统平台为Windows 7。实验仿真如图2所示。

通过高斯混合模型对海上轨迹的聚类研究，我们可以大大减少一些嘈杂且很不规则的轨迹对整个轨迹的影响，使之平滑化，降低航行途中不测事件风险率的发生。

图2 自适应GMM轨迹聚类

4 算法性能分析

4.1 A-GMM聚类算法和传统GMM算法对比

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

图3 A-GMM聚类分析图

图4 传统GMM聚类分析图

通过轨迹仿真可知，GMM聚类中一个类内的数据点聚拢在一块的密度较低，离聚类中心点距离较远，则聚类的总体效果相对来说会变差。而A-GMM是将具有相似特征的数据聚集到一类，不仅类间紧凑性高，类内相差大，而且对异常数据点十分敏感，聚类可靠性较高。通过两者的仿真结果可知GMM不能准确识别多拐点、非线性和波动性强的轨迹，致使聚类误差较大，自适应GMM高斯混合模型比传统GMM聚类效果要好，因为传统GMM聚类需要人工设定聚类个数需要进行多次测试，时间复杂度高，性能下降。而自适应GMM聚类通过不断迭代得出最优聚类个数，精度较高。

4.2 聚类准确率结果分析

该实验数据是从200个浮标中任意抽取5个，然后选取某三个月的轨迹进行每隔72小时切分，选取波动性较大，带有多次循环的轨迹组成了数据集{D1,D2,D3,D4,D5}。为了更好地评价算法的性能优劣和聚类的准确率，在k=4条件下，将本文算法与大数据环境下移动对象自适应轨迹预测模型[18]（简记为HMM算法）、传统高斯混合模型（GMM）算法三者的误差平方和SSE、纯度和F1值进行比较，其定义如下：

定义1（误差平方和SSE）：各数据间的相似性度量是保证聚类效果的关键，此外还须有适当的聚类目标函数来度量聚类效果，所以本文使用误差平方和（SSE）进行相似性度量：

定义2（聚类纯度）：为了更好地衡量本文算法的优势，本文则采用了计算纯度的方法，通过算出各个类i中被正确分配的轨迹数目，然后将各个类别的轨迹数量相加，除以相应的轨迹总数，即为聚类纯度。计算公式如下所示：

其中N表示轨迹数量，k表示聚类数目，Aj表示类别k中最具有代表性类别的轨迹数目。

定义3（F-measure值）：F-measure是轨迹检索中的查准率和查全率这两种指标的综合，对于一个聚类a和一个事实类别b的查准率和查全率的定义如下：

其中N1表示的是聚类a中属于事实类别b的数目，N2是聚类a中所有轨迹的数目，N3为事实类别b中所有轨迹的数目。

本文轨迹分析采用的是F-measure是查准率和查全率的加权平均值，也称为F1值，其定义如下：

具体结果如图5、表1和2所示：

图5 误差平方和

实验结果分析：

（1）通过观察图5可以发现，GMM和HMM的误差平方和均高于A-GMM，而SSE越高说明类间相似性低，类内差别大，致使前两者聚类效果大大降低，而AGMM每组的SSE低于前两者的数值约为10左右，在很大程度上减少了误差，提高了聚类可靠性；

表1 GMM算法、HMM算法和A-GMM算法纯度值对比

（2）通过观察表1可知，A-GMM纯度值平均高于GMM约为10%左右，高于HMM约为9%，因为AGMM能够对拐点多和波动性强的轨迹动态调整并划分到正确的类，而HMM和GMM无法识别特征变化较明显的轨迹致使聚类误差较大；

（3）F1是查全率和准确率的加权平均值，其值越高，聚类性能越佳。通过观察表2可知，GMM和HMM的F1值相近，但低于A-GMM约6%和5%，说明AGMM对噪音轨迹较敏感，聚类可信度较高。

5 结语

海上移动对象不确定性轨迹聚类是一个崭新和充满挑战性的研究课题，针对当前轨迹聚类自适应性差、海上航线不受限制和聚类实时性不佳的不足，本文通过自适应GMM聚类算法可以避免人工设定聚类数的困扰，不仅使得聚类准确率提高并且EM在估计参数值时的精确度也有所提升。该算法的优势是：算法在运行过程中无需指定聚类数目，而是根据不同数据自身的特征进行自适应聚类，提高了聚类的准确性和泛化性。通过对真实浮标轨迹的聚类研究不但能显著地降低因自然环境等不确定因素引发的海洋事故带来生命财产损失，而且有力地促进了中外各国间的贸易往来。

表2 GMM算法、HMM算法和A-GMM算法的F1值对比