一種基于高斯混合模型的海上浮標(biāo)軌跡聚類算法

荊曉剛，葛麗閣，孫偉

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

0 引言

隨著計算機技術(shù)的不斷發(fā)展和移動對象跟蹤技術(shù)的不斷完善，人們采集到大量的運動目標(biāo)軌跡數(shù)據(jù)，為了找出這些數(shù)據(jù)中隱藏的知識，移動對象軌跡聚類技術(shù)應(yīng)運而生。目前，在軌跡聚類方面的研究，主要有朱燕[1]等基于聚類的出租車異常軌跡檢測，通過將單條軌跡劃分為若干子段，再計算各軌跡間的相似度，基于距離和密度的聚類來實現(xiàn)出租車異常軌跡檢測，但其算法時間代價較高；石陸魁[2]等人提出了基于時空模式的軌跡數(shù)據(jù)聚類算法，但聚類算法效率較低；吳熙[3]等人提出的基于軌跡聚類的超市顧客運動追蹤，對顧客部分遮擋、復(fù)雜運動軌跡以及異步運動等多種特殊情況具有較高的魯棒性，但算法時間復(fù)雜度較高。以上研究工作都是針對陸地上的運動目標(biāo)。海上目標(biāo)的運動軌跡與陸地不同，其不受道路、軌道的限制，并且海上目標(biāo)受力復(fù)雜，其軌跡點隨機性更強，軌跡也更加復(fù)雜不規(guī)則。本文針對海上目標(biāo)軌跡的特征，提出一種基于高斯混合模型的浮漂軌跡聚類算法。海上目標(biāo)軌跡分析的研究工作，可以使人們更好地掌握和預(yù)測海上航行軌跡，并應(yīng)用于海上搜救、航路規(guī)劃等領(lǐng)域。

1 高斯混合模型

所謂混合高斯模型（GMM）[6]就是指對樣本的概率密度分布進(jìn)行估計，而估計采用的模型（訓(xùn)練模型）是幾個高斯模型的加權(quán)和（具體是幾個要在模型訓(xùn)練前建立好）。每個高斯模型就代表了一個類。高斯混合模型是單一高斯概率密度函數(shù)的延伸，對樣本中的數(shù)據(jù)分別在幾個高斯模型上投影，就會分別得到在各個類上的概率。然后，可以選取概率最大的類所為判決結(jié)果。

假設(shè)每個點均由一個單高斯分布生成，而這一批數(shù)據(jù)共由M個單高斯模型生成，具體某個數(shù)據(jù)xi屬于哪個單高斯模型未知，且每個單高斯模型在混合模型中占的比例αj未知，將所有來自不同分布的數(shù)據(jù)點混在一起，該分布稱為高斯混合分布[7]。高斯混合模型的公式如公式1所示：

GMM 通常用 EM（Expectation Maximum）算法[10]對GMM參數(shù)進(jìn)行估計。算法流程為：

步驟1：初始化

協(xié)方差矩陣Cj0設(shè)為單位矩陣，每個模型比例的先驗概率；均值 μj0設(shè)為隨機數(shù)。

步驟 2：估計步驟（E-step）

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

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

更新權(quán)值:

更新均值：

更新方差矩陣：

步驟4：收斂條件

2 浮標(biāo)軌跡的GMM聚類算法

2.1 聚類算法實現(xiàn)

下面，針對海上浮標(biāo)漂移軌跡提出的GMM聚類算法的偽代碼如下：

輸入：浮標(biāo)軌跡數(shù)據(jù)集 Data={d1，d2，，dn}；測試用例軌跡集 TData={D1，D2，…，Dm}。

輸出：軌跡聚類結(jié)果。

1.D*={T1，T2，…，Tn};//已知軌跡點序列

2.si=GMM_ini（Data，k）;//GMM算法初始化，其中參數(shù)k為聚類個數(shù)

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

4.m=EM（Data,gp）;//極大似然估計過程，更新參數(shù)

5.for i=1:k

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

7.Px=gaussPDF（Data,si）//得到似然值最大的分類結(jié)果

8.End

2.2 算法有效性驗證

本文通過高斯混合模型對海上浮標(biāo)軌跡點進(jìn)行聚類研究，其數(shù)據(jù)來源來自于NOAA的The GDP Drift Data Assembly Center（DAC）的 Hourly Data，通過緯度、經(jīng)度和時間的三維數(shù)據(jù)進(jìn)行軌跡點聚類，分別選取2016年1月12日和2016年5月28日兩天的數(shù)據(jù)[11]，通過MATLAB 2012a的實驗環(huán)境下的實驗結(jié)果仿真如圖1和圖2所示。

圖1 原始軌跡點集和GMM聚類結(jié)果

圖2 原始軌跡點集和GMM聚類結(jié)果

本文通過高斯混合模型對海上軌跡的聚類研究，提出的GMM算法可以大大減少一些嘈雜且很不規(guī)則的軌跡對整個軌跡的影響，可能會增加航行途中不測事件的風(fēng)險率。

3 GMM算法性能分析

為了更好的衡量高斯混合模型的性能優(yōu)劣，本文采取了與K-means算法對同一軌跡點進(jìn)行聚類分析，其結(jié)果如圖3所示。

通過對上圖的軌跡仿真可以看出，高斯混合模型比k-means聚類效果要好，K-means容易將一些處于兩個簇的軌跡點錯分到另一個簇中。另外，GMM聚類算法的到聚類中心的平均距離較K-means算法更小，說明本文提出的GMM聚類算法優(yōu)于K-means算法，如圖4所示。GMM的優(yōu)點是投影后樣本點不是得到一個確定的分類標(biāo)記，而是得到每個類的概率，這是一個重要信息。GMM每一步迭代的計算量比較大，大于K-means。GMM的參數(shù)估計基于EM算法，效果較為理想。

圖3 GMM算法和K-means算法聚類結(jié)果對比

4 結(jié)語

海上目標(biāo)的運動軌跡較陸地上具有不受限道路、軌道限制，更不規(guī)則等特征，給軌跡分析和軌跡預(yù)測帶來難題。本文針對海上浮漂的漂移軌跡提出一種基于高斯混合模型的軌跡聚類算法。以NOAA的漂浮浮標(biāo)數(shù)據(jù)作為實驗數(shù)據(jù)集，算法實驗表明該算法較K-means算法具有更優(yōu)的聚類結(jié)果。GMM算法更適用于海上運動目標(biāo)復(fù)雜且不規(guī)則的軌跡，其軌跡聚類結(jié)果可進(jìn)一步用于軌跡預(yù)測，未來在海上搜救、航路規(guī)劃等領(lǐng)域有廣泛的應(yīng)用前景。

圖4 兩個聚類算法的平均聚類距離比較

[1]朱燕,李宏偉,樊超,等.基于聚類的出租車異常軌跡檢測[J].計算機工程,2017,43（2）:16-20.

[2]石陸魁,張延茹,張欣.基于時空模式的軌跡數(shù)據(jù)聚類算法[J].計算機應(yīng)用,2017,37（3）:854-859.

[3]王熙,吳為,錢沄濤.基于軌跡聚類的超市顧客運動跟蹤[J].智能系統(tǒng)學(xué)報,2015（2）:187-192.

[4]肖瀟.基于AIS信息的船舶軌跡聚類模型研究[D].集美大學(xué),2015.

[5]王田璐.軌跡聚類與基于高斯過程回歸模型的軌跡識別算法研究[D].上海交通大學(xué),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]喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預(yù)測算法[J].軟件學(xué)報,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]徐濤,陳雪蕊,呂宗平.基于航跡聚類的終端區(qū)飛行程序軌跡表示[J].四川大學(xué)學(xué)報（工程科學(xué)版）,2016,48（6）:188-196.

[10]翟婷,宋文愛,富麗貞,等.基于路網(wǎng)感知的時空軌跡聚類[J].計算機工程與設(shè)計,2016,37（3）:635-642.

[11]馮濤,郭云飛,黃開枝,等.基于隱馬爾可夫模型的行為軌跡還原算法[J].計算機工程,2012,38（18）:1-5.