葛麗閣，孫偉

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

聚類分析是數(shù)據(jù)靜態(tài)分析的一門關(guān)鍵技術(shù)，在機(jī)器學(xué)習(xí)、人工智能和數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用廣泛。聚類是為了提取相同的特征從而對相似度高的事物進(jìn)行統(tǒng)一分析研究，聚類的評價標(biāo)準(zhǔn)時類內(nèi)相差越大越好，反之簇間相差愈小愈好。

由于數(shù)據(jù)統(tǒng)計分析的難度性較大，數(shù)據(jù)的概率分布往往比較隨意，一般地，近年來，高斯混合模型因在復(fù)雜環(huán)境計算簡便、易于實(shí)現(xiàn)及本身具有一定的降噪性的優(yōu)勢而得以大面積使用，所以該數(shù)據(jù)的概率分布可以采用混合的高斯模型來任意的逼近。但是傳統(tǒng)的高斯混合模型聚類數(shù)需要人工給出，采用簡單穩(wěn)定的期望最大化EM算法求解未知標(biāo)記的最大似然值，但是EM算法收斂過程慢而且會使參數(shù)陷入局部最優(yōu)值[1]。因此如何設(shè)置混合模型的參數(shù)對聚類的性能研究亟待解決。

1 聚類研究現(xiàn)狀

隨著國際經(jīng)濟(jì)聯(lián)系的日益加強(qiáng)，國際分工的日趨明顯，海洋運(yùn)輸業(yè)發(fā)展甚為迅速。在諸多重要應(yīng)用領(lǐng)域中，如移動導(dǎo)航、地質(zhì)勘察和貨物運(yùn)輸?shù)?，用戶需要及時查詢和分析移動對象的位置信息，移動對象軌跡聚類已漸漸成為移動對象數(shù)據(jù)庫管理的重要研究方向。當(dāng)前對移動對象研究則通過聚類挖掘軌跡運(yùn)動模式，將具有相似度較高的軌跡歸為一類，以對大量數(shù)據(jù)進(jìn)行挖掘分析[1]。對海上移動對象軌跡聚類目的是：一是提高陸上交通信息系統(tǒng)的智能化水平；二是在一定時間內(nèi)，可以提醒遇有礁石和撞船等不測事件的移動目標(biāo)繞過危險區(qū)域安全航行。海洋航行沒有固定的航線限制，運(yùn)動環(huán)境復(fù)雜多變，如何對海上移動對象軌跡分析成為亟需解決的難點(diǎn)。當(dāng)前已有一些研究成果，如移動對象的聚類、異常點(diǎn)檢測和位置查詢等。其中，對軌跡聚類的研究主要有范敬雅[2]等提出的基于EM算法的高斯混合模型的聚類分析，通過貝葉斯信息準(zhǔn)則選取最優(yōu)類來分析2015年31個省的GDP和人均GDP，證實(shí)了算法的實(shí)用性和可靠性但是效率不高；張燕杰[3]等的基于高斯混合模型的聚類分析通過研究有限和無窮的高斯混合模型的算法更好的聚類分析，但是時間代價較高；石陸魁[4]等人提出了基于時空模式的軌跡數(shù)據(jù)聚類算法，但是聚類效率較低；陳英[5]等人提出的高斯混合模型聚類及其優(yōu)化算法研究，通過增加懲罰項改進(jìn)EM算法，改善了聚類性能，提高了算法的學(xué)習(xí)效率和魯棒性但是需要給定一個懲罰權(quán)重并且算法變得更復(fù)雜；喬少杰[6]等人提出的一種基于高斯混合模型的軌跡預(yù)測模型，主要對停車場軌跡分析。針對以上弊端，加之目前大多的聚類算法的中心主要是研究陸地軌跡，對海上軌跡的聚類工作較少，由于當(dāng)今海洋運(yùn)輸業(yè)的快速發(fā)展和層出不窮的安全事故，所以本文就提出了一種基于自適應(yīng)高斯混合模型的海上浮標(biāo)軌跡聚類算法，通過對海上浮標(biāo)得到的軌跡點(diǎn)進(jìn)行聚類分析，可以更好地掌握海上航線情況減少海上航行事故的發(fā)生率，以及對將來軌跡預(yù)測，異常點(diǎn)監(jiān)測等研究提供更好的研究方向。

2 高斯混合模型原理

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

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

令φ(αj,μj),Cj，GMM共有M個單高斯模型。我們需要通過樣本集 x來估計 GMM的所有參數(shù)[9]：Φ=(φ1,φ2,…,φM)T，樣本 x的概率如公式（2）：

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

Step1：初始化

協(xié)方差矩陣Cj0設(shè)為單位矩陣，每個模型比例的先

Step2：估計步驟[11]（E-step）

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

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

Step4：收斂條件

不斷地迭代步驟Step2和Step3，重復(fù)更新上面三個值，直到 p(X |Φ)-p(X |Φ )'<ε, 其中 p(X |Φ )'為更新參數(shù)后計算的值，即前后兩次迭代得到的結(jié)果變化小于一定程度則終止迭代，通常ε=10-5。

因軌跡數(shù)據(jù)的概率分布往往較復(fù)雜，因此可通過高斯混合模型來任意逼近使之問題簡單化，這為軌跡聚類方面的研究打開了一個新天地[15]。但高斯混合模型聚類數(shù)目大多根據(jù)人們經(jīng)驗任意指定不僅降低了聚類的準(zhǔn)確性，而且對海上循環(huán)多變的漂浮物軌跡自適應(yīng)性較差，因此需要對高斯混合模型做進(jìn)一步的改進(jìn)工作。

3 自適應(yīng)GMM聚類算法

3.1 自適應(yīng)聚類

GMM聚類使用K-means初始化EM的思想，進(jìn)行自適應(yīng)確定聚類簇個數(shù)的過程中[12]，會對聚類結(jié)果進(jìn)行評判，必然也會確定高斯混合模型的各個參數(shù)，若以此時得到的各個高斯元參數(shù)作為下一次迭代的參數(shù)，如此初始化得到的結(jié)果會更接近最優(yōu)值。

（1）自適應(yīng)GMM聚類的實(shí)現(xiàn)步驟

針對海洋上移動對象非受限性和強(qiáng)波動性等特征的軌跡研究和避免傳統(tǒng)的GMM聚類算法的弊端，本文實(shí)現(xiàn)了自適應(yīng)的聚類算法，命名Apdative Gaussian Mix?ture Model Clustering（A-GMM）其具體實(shí)現(xiàn)步驟如下：

①先假設(shè)已經(jīng)限制有k0個高斯元[13]（即聚類簇，一般取較小值），用普通的EM算法對這個模型進(jìn)行優(yōu)化，估計其均值，協(xié)方差等參數(shù)，計算出聚類結(jié)果classoutcome；

②在迭代計算出第i個樣本歸于第j類的概率w（i,j）后，將第i個樣本分入使其概率最大的類。而聚類后類之間差別較大，即樣本i歸入classoutcome（i）類的概率應(yīng)當(dāng)比歸入第j類的概率大，故可以用二者的比值衡量聚類的效果。即用D2（i,j）表示第i個樣本歸入第classoutcome（i,j）的概率與歸入第j類的比值。

③對D2（i,j）設(shè)定一個最小閾值minp（根據(jù)大量實(shí)驗minp的取值在1.0附近，本文取值為1.03），通過給定minp的值便可以衡量類之間差距的大小。因此計算出D2的最小值后與設(shè)定的閾值minp相比較，若小于給定的minp，則聚類簇個數(shù)增加，若大于minp則已滿足條件，停止增加聚類簇個數(shù)。

④在增加聚類簇個數(shù)后，就面臨著新模型的參數(shù)初始化問題，但上一個模型（K未增加時）的參數(shù)已經(jīng)得到確定，這組參數(shù)可以說是比較接近最優(yōu)解的，因此就讓添加新模型之前的高斯元參數(shù)保持不變，新增加的高斯元對應(yīng)的協(xié)方差矩陣用原來就有的高斯元的均值代替，它在整個高斯混合模型中所占的比例alpha為原來就有的高斯元的比例的平均值。而新增加的高斯元特征均值mu取自D2矩陣中最小值所對應(yīng)的樣本作為新增高斯元的特征均值（因為這個樣本的聚類效果不好）。如此循環(huán)就完成了新模型的參數(shù)初始化即自適應(yīng)聚類。但有時會出現(xiàn)新增加的高斯元所占的比例十分?。ㄎ以诔绦蛑腥〉氖切∮?/（100×K）），說明新增加的這個類對整個模型的改進(jìn)效果并不大，故遇到這種情況時可停止增加聚類簇.此外，由于最開始的高斯混合模型還是隨機(jī)初始化參數(shù)的，使得最后得到的結(jié)果也具有一定的隨機(jī)性，解決方法是多次運(yùn)行程序，取聚類簇個數(shù)K較小的一次的計算結(jié)果。

（2）自適應(yīng)GMM（A-GMM）聚類流程圖

為了更好地描述自適應(yīng)GMM聚類的實(shí)現(xiàn)過程，其具體的流程圖如圖1所示：

圖1 自適應(yīng)GMM聚類實(shí)現(xiàn)流程圖

3.2 實(shí)驗仿真

本文采用自適應(yīng)高斯混合模型的聚類算法（AGMM）對海上漂浮物軌跡通過浮標(biāo)獲取，使用浮標(biāo)是因為它可設(shè)置在難以或不宜設(shè)立固定航標(biāo)之處且能實(shí)時獲取海上移動對象的軌跡數(shù)據(jù)。實(shí)驗數(shù)據(jù)來源于NO?AA[15]的 The GDP Drift Data Assembly Center（DAC）的Hourly實(shí)時軌跡，連續(xù)記錄180天。由于軌跡數(shù)量較大，本文就任意選取某三個月經(jīng)度（坐標(biāo)X軸）、緯度（坐標(biāo)Y軸）中的500個軌跡點(diǎn)組成數(shù)據(jù)集進(jìn)行聚類分析。實(shí)驗環(huán)境為MATLAB 2012a，實(shí)驗硬件平臺為:In?tel Core 2 Duo P8700 2.53GHz CPU,2GB內(nèi)存,操作系統(tǒng)平臺為Windows 7。實(shí)驗仿真如圖2所示。

通過高斯混合模型對海上軌跡的聚類研究，我們可以大大減少一些嘈雜且很不規(guī)則的軌跡對整個軌跡的影響，使之平滑化，降低航行途中不測事件風(fēng)險率的發(fā)生。

圖2 自適應(yīng)GMM軌跡聚類

4 算法性能分析

4.1 A-GMM聚類算法和傳統(tǒng)GMM算法對比

為了更好地衡量高斯混合模型的性能優(yōu)劣，本文采取了與傳統(tǒng)GMM算法對同一軌跡點(diǎn)進(jìn)行聚類分析，其結(jié)果如圖3和圖4所示：

圖3 A-GMM聚類分析圖

圖4 傳統(tǒng)GMM聚類分析圖

通過軌跡仿真可知，GMM聚類中一個類內(nèi)的數(shù)據(jù)點(diǎn)聚攏在一塊的密度較低，離聚類中心點(diǎn)距離較遠(yuǎn)，則聚類的總體效果相對來說會變差。而A-GMM是將具有相似特征的數(shù)據(jù)聚集到一類，不僅類間緊湊性高，類內(nèi)相差大，而且對異常數(shù)據(jù)點(diǎn)十分敏感，聚類可靠性較高。通過兩者的仿真結(jié)果可知GMM不能準(zhǔn)確識別多拐點(diǎn)、非線性和波動性強(qiáng)的軌跡，致使聚類誤差較大，自適應(yīng)GMM高斯混合模型比傳統(tǒng)GMM聚類效果要好，因為傳統(tǒng)GMM聚類需要人工設(shè)定聚類個數(shù)需要進(jìn)行多次測試，時間復(fù)雜度高，性能下降。而自適應(yīng)GMM聚類通過不斷迭代得出最優(yōu)聚類個數(shù)，精度較高。

4.2 聚類準(zhǔn)確率結(jié)果分析

該實(shí)驗數(shù)據(jù)是從200個浮標(biāo)中任意抽取5個，然后選取某三個月的軌跡進(jìn)行每隔72小時切分，選取波動性較大，帶有多次循環(huán)的軌跡組成了數(shù)據(jù)集{D1,D2,D3,D4,D5}。為了更好地評價算法的性能優(yōu)劣和聚類的準(zhǔn)確率，在k=4條件下，將本文算法與大數(shù)據(jù)環(huán)境下移動對象自適應(yīng)軌跡預(yù)測模型[18]（簡記為HMM算法）、傳統(tǒng)高斯混合模型（GMM）算法三者的誤差平方和SSE、純度和F1值進(jìn)行比較，其定義如下：

定義1（誤差平方和SSE）：各數(shù)據(jù)間的相似性度量是保證聚類效果的關(guān)鍵，此外還須有適當(dāng)?shù)木垲惸繕?biāo)函數(shù)來度量聚類效果，所以本文使用誤差平方和（SSE）進(jìn)行相似性度量：

定義2（聚類純度）：為了更好地衡量本文算法的優(yōu)勢，本文則采用了計算純度的方法，通過算出各個類i中被正確分配的軌跡數(shù)目，然后將各個類別的軌跡數(shù)量相加，除以相應(yīng)的軌跡總數(shù)，即為聚類純度。計算公式如下所示：

其中N表示軌跡數(shù)量，k表示聚類數(shù)目，Aj表示類別k中最具有代表性類別的軌跡數(shù)目。

定義3（F-measure值）：F-measure是軌跡檢索中的查準(zhǔn)率和查全率這兩種指標(biāo)的綜合，對于一個聚類a和一個事實(shí)類別b的查準(zhǔn)率和查全率的定義如下：

其中N1表示的是聚類a中屬于事實(shí)類別b的數(shù)目，N2是聚類a中所有軌跡的數(shù)目，N3為事實(shí)類別b中所有軌跡的數(shù)目。

本文軌跡分析采用的是F-measure是查準(zhǔn)率和查全率的加權(quán)平均值，也稱為F1值，其定義如下：

具體結(jié)果如圖5、表1和2所示：

圖5 誤差平方和

實(shí)驗結(jié)果分析：

（1）通過觀察圖5可以發(fā)現(xiàn)，GMM和HMM的誤差平方和均高于A-GMM，而SSE越高說明類間相似性低，類內(nèi)差別大，致使前兩者聚類效果大大降低，而AGMM每組的SSE低于前兩者的數(shù)值約為10左右，在很大程度上減少了誤差，提高了聚類可靠性；

表1 GMM算法、HMM算法和A-GMM算法純度值對比

（2）通過觀察表1可知，A-GMM純度值平均高于GMM約為10%左右，高于HMM約為9%，因為AGMM能夠?qū)拯c(diǎn)多和波動性強(qiáng)的軌跡動態(tài)調(diào)整并劃分到正確的類，而HMM和GMM無法識別特征變化較明顯的軌跡致使聚類誤差較大；

（3）F1是查全率和準(zhǔn)確率的加權(quán)平均值，其值越高，聚類性能越佳。通過觀察表2可知，GMM和HMM的F1值相近，但低于A-GMM約6%和5%，說明AGMM對噪音軌跡較敏感，聚類可信度較高。

5 結(jié)語

海上移動對象不確定性軌跡聚類是一個嶄新和充滿挑戰(zhàn)性的研究課題，針對當(dāng)前軌跡聚類自適應(yīng)性差、海上航線不受限制和聚類實(shí)時性不佳的不足，本文通過自適應(yīng)GMM聚類算法可以避免人工設(shè)定聚類數(shù)的困擾，不僅使得聚類準(zhǔn)確率提高并且EM在估計參數(shù)值時的精確度也有所提升。該算法的優(yōu)勢是：算法在運(yùn)行過程中無需指定聚類數(shù)目，而是根據(jù)不同數(shù)據(jù)自身的特征進(jìn)行自適應(yīng)聚類，提高了聚類的準(zhǔn)確性和泛化性。通過對真實(shí)浮標(biāo)軌跡的聚類研究不但能顯著地降低因自然環(huán)境等不確定因素引發(fā)的海洋事故帶來生命財產(chǎn)損失，而且有力地促進(jìn)了中外各國間的貿(mào)易往來。

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