荊曉剛，葛麗閣，孫偉

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

0 引言

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

1 高斯混合模型

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

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

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

步驟1：初始化

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

步驟 2：估計(jì)步驟（E-step）

令αj的后驗(yàn)概率如公式（3）所示：

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

更新權(quán)值:

更新均值：

更新方差矩陣：

步驟4：收斂條件

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

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

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

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

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

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

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

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

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

5.for i=1:k

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

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

8.End

2.2 算法有效性驗(yàn)證

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

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

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

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

3 GMM算法性能分析

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

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

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

4 結(jié)語(yǔ)

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

圖4 兩個(gè)聚類算法的平均聚類距離比較

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

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

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

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

[5]王田璐.軌跡聚類與基于高斯過程回歸模型的軌跡識(shí)別算法研究[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ù)測(cè)算法[J].軟件學(xué)報(bào),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é)報(bào)（工程科學(xué)版）,2016,48（6）:188-196.

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

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