基于Spark平臺的海量AIS數(shù)據(jù)k-means算法聚類分析

初秀民 林 宏 王志遠

(1.閩江學院物理與電子信息工程學院 福州 350108;2.閩江學院福建省船舶智能航行安全控制工程研究中心 福州 350108;3.閩江學院海洋智能船舶裝備福建省高校工程研究中心 福州 350108)

當前，在經(jīng)濟全球化的影響下，低成本和大運輸量的優(yōu)勢使水上運輸成為世界各國之間貿(mào)易和運輸?shù)闹饕绞街?。自動識別系統(tǒng)(automatic identification system, AIS)是用于分析船舶航行狀況的主要工具。隨著水運的發(fā)展，AIS數(shù)據(jù)量呈指數(shù)增長，為了對這些數(shù)據(jù)進行分析，需要一個大數(shù)據(jù)平臺來有效地處理這些數(shù)據(jù)。Spark因其速度快、通用性強等特點，逐步受到智能交通領域的青睞，例如曹磊[1]通過搭建基于Spark的通用型數(shù)據(jù)處理挖掘平臺，以對AIS數(shù)據(jù)進行挖掘。

由于AIS沒有完整的信息驗證機制，在實際應用中AIS數(shù)據(jù)中存在大量的異常數(shù)據(jù)，因此需要進行有效甄別以保障船舶航行安全。目前國內(nèi)外的研究主要集中在AIS數(shù)據(jù)的應用研究，而對AIS數(shù)據(jù)本身的準確性分析缺少。例如，Zhang等[2]使用AIS數(shù)據(jù)來評估遇船風險。Dobrkovic等[3]使用遺傳算法對船舶位置信息進行聚類，并研究了船舶航向的特征。Altan等[4]使用AIS數(shù)據(jù)分析了伊斯坦布爾海峽的航運特征，為船舶航行風險的預測和分析提供了支持。田璐[5]考慮AIS數(shù)據(jù)的特征，設計了其處理流程和存儲策略，并利用AIS數(shù)據(jù)實現(xiàn)船舶航跡重構(gòu)、截面船舶流量統(tǒng)計、船舶出入口區(qū)域識別，以及船舶航行狀態(tài)分析等。Mazzarella等[6]分析AIS數(shù)據(jù)，以確定故意關(guān)閉船載AIS設備的異常行為。LongépéN等[7]分析AIS數(shù)據(jù)以識別非法捕魚。魏照坤[8]利用瓊州海峽的AIS數(shù)據(jù)，獲得行駛于該水域的船舶運動軌跡分布及各類軌跡中轉(zhuǎn)向區(qū)域的分布。

為此，本文設計了一個基于Spark的大數(shù)據(jù)處理平臺，使用k-means算法對AIS數(shù)據(jù)進行聚類分析，并將Spark建立AIS數(shù)據(jù)的聚類所需的時間與在機器上對AIS數(shù)據(jù)進行聚類所需的時間進行比較。

1 AIS數(shù)據(jù)處理平臺設計與實現(xiàn)

1.1 總體框架

AIS數(shù)據(jù)處理平臺主要包括數(shù)據(jù)存儲層、資源管理層、計算引擎及接口、操作語言的運用?？傮w架構(gòu)生態(tài)圖見圖1。

圖1 總體架構(gòu)生態(tài)圖

1.2 數(shù)據(jù)存儲層

AIS數(shù)據(jù)包括船舶的靜態(tài)信息和動態(tài)信息。靜態(tài)信息是船舶在航行過程中保持不變的信息，包括MMSI號、船舶名稱、船舶類型、船舶的長和寬、吃水等信息。動態(tài)信息是船舶在航行過程中隨著時間的推移，不斷變化的信息，包括船速、船舶位置信息、船艏向、船舶狀態(tài)等。

HBase是基于HDFS的NoSQL數(shù)據(jù)庫，它的表是按列存儲的、稀疏的、多維度的、有序的映射表，它的存儲模式是KeyValue鍵值對存儲，與純粹字符串的Key不同的是：HBase的 Key由RowKey、Column Family、Column Qualifier和Timestamp 4個部分共同組成。以上這些特點使得Hbase具有易擴展、適合大量的查詢與寫入工作等特點。

針對AIS數(shù)據(jù)量大、數(shù)據(jù)信息復雜等特征，本文采用基于HBase數(shù)據(jù)庫來存儲AIS數(shù)據(jù)。對AIS數(shù)據(jù)進行分析的時候，一般通過時間和MMSI號進行數(shù)據(jù)的分類與切片，因此將“DateTime and MMSI”作為行，以其他信息為列，具體設計見表1。

表1 AIS數(shù)據(jù)結(jié)構(gòu)表

1.3 資源管理層

為了對平臺資源進行分配與管理，本文搭建了以Mesos、Zookeeper為主體的資源管理層。

Mesos對平臺中CPU、內(nèi)存、存儲和其他計算資源進行合理的分配，使得彈性分布式系統(tǒng)使用起來更加方便。但是Mesos在運行過程中存在單點故障問題，為此本文采用Zookeeper來解決這個問題。ZooKeeper能夠?qū)崿F(xiàn)Master和Slave的容錯。將那些復雜且容易出錯的分布式一致性服務封裝起來，構(gòu)成一個高效可靠的原語集，并以一系列簡單易用的接口提供給用戶使用。資源管理架構(gòu)圖見圖2。

圖2 資源管理架構(gòu)圖

1.4 計算引擎及接口

Apache Spark是一種專門處理大數(shù)據(jù)的熱門計算引擎，同時提供了Spark SQL、Spark Streaming、Mllib、GraphX等4個范疇的計算框架，其框架圖見圖3。Spark SQL是實現(xiàn)結(jié)構(gòu)化數(shù)據(jù)操作的程序包，支持用戶以SQL語句的方式來處理數(shù)據(jù)且支持多種數(shù)據(jù)源。Spark Streaming支持對實時數(shù)據(jù)進行流式計算。Mllib為用戶提供了常用機器學習算法的實現(xiàn)庫。GraphX實現(xiàn)了高效的圖計算。Spark以將應用放到內(nèi)存中運行的方式，提高了程序的運行數(shù)據(jù)，且具有計算速度快、易用性好、通用性高等優(yōu)點。

圖3 Spark框架圖

2 算法概述

k-means算法是一種常見的聚類算法，其基本思想是通過迭代找到k個聚類的劃分方案，以便使用這k個聚類的平均值來表示相應類型的樣本。

k-means算法的基礎是最小誤差平方和準則。成本函數(shù)為

(1)

式中：i為第i個簇；x為樣本，μc(i)為第i個簇的平均值。直觀地講，每個類別中的樣本越相似，樣本與類別平均值之間的誤差平方就越小。希望成本函數(shù)最小，如果將每個聚類劃分為k個類別，則可以驗證針對所有類別獲得的誤差平方和。

上式的成本函數(shù)不能通過分析方法最小化，只能使用迭代方法。k-means算法將樣本聚類為k個聚類，其中k由用戶指定。解決過程直觀且簡單。具體算法描述如下。

1) 隨機選擇k個聚類質(zhì)心點。

2) 重復以下過程直到收斂。

①對于每個示例i，計算它應該屬于的類別，計算方法如式(2)所示。

(2)

②對于每個k類，重新計算該類的質(zhì)心，計算方法如式(3)所示。

(3)

3 試驗

3.1 硬件平臺搭建

平臺使用4臺計算機搭建，計算機配置為CPU為Intel(R) Xeon(R) CPU E5-2603 v4@ 1.70G Hz，內(nèi)存為5.0 G，硬盤為200 G。用來搭建hadoop、Spark 集群，另外1臺用來訪問集群。架構(gòu)圖見圖4。

圖4 架構(gòu)圖

3.2 軟件環(huán)境

4臺計算機搭載的系統(tǒng)均為Centos 7，安裝的JDK版本為openjdk version “1.8.0_252”，Hadoop版本為Hadoop 2.10.0，Spark版本為version 3.0.0，Mesos版本為1.10.0，ZooKeeper版本為3.4.6。集群搭建內(nèi)容見表2。

表2 集群搭建內(nèi)容表

4 實驗結(jié)果分析

通過k-means算法分類可獲得不同類型的軌跡點，其AIS軌跡聚類分析圖見圖5。

圖5 基于k-means算法的AIS軌跡聚類分析圖

圖5中紅色點表示正常點，主要落在航道中，其他顏色的點表示異常點。這些異常點中的一些分布在附近的陸地上，而有些則離得很遠，因此無法正確表示船舶的軌跡。

王暢[9]采用Dbscan算法對天津港泊位點進行聚類，并與真實泊位對比，驗證了聚類結(jié)果的準確性，為此本文采用Dbscan算法對k-means算法的有效性進行了驗證。Dbscan算法對同一數(shù)據(jù)樣本的聚類分析結(jié)果圖見圖6。

圖6 基于Dbscan算法的AIS聚類軌跡分析圖

其中，深紫色的點表示表示正常點，主要落在航道中。其他顏色的點表示異常點。這些異常點中的一些分布在附近的陸地上，而有些則相距很遠，因此不能正確地表示船舶的軌跡。

圖5中的紅色軌跡線和圖6中的深紫色軌跡線均表示集群的船只軌跡。2條軌跡高度一致，說明本文的k-means算法可以對AIS數(shù)據(jù)進行有效的聚類分析。

由Spark集群和沒有Spark集群的計算機對AIS船舶軌跡進行聚類的運算時間比較見圖7。

圖7 運算時間比較圖

由圖7可見，未安裝Spark集群的計算時間隨著AIS數(shù)據(jù)量增加大幅度上升，而Spark聚類分析時間隨著AIS數(shù)據(jù)量的增加略微增加，且遠小于未安裝Spark集群的計算時間，并隨著AIS數(shù)據(jù)量的增加差異越大，故Spark聚類分析可大幅度提高運算速度。

5 結(jié)語

針對大量的AIS數(shù)據(jù)和信息處理，本文使用基于Spark、Hadoop和Mesos的大數(shù)據(jù)處理平臺來分析AIS數(shù)據(jù)。通過對船舶航跡點的k-means聚類分析，對不同航跡點進行分類，并將本文構(gòu)建的大數(shù)據(jù)平臺與無大數(shù)據(jù)平臺計算機的分析效率進行了比較分析。測試結(jié)果表明，該平臺可大幅度提高AIS數(shù)據(jù)分析的效率。在AIS數(shù)據(jù)量不斷增加的環(huán)境中，本文構(gòu)建的平臺可以提高數(shù)據(jù)處理效率，對AIS數(shù)據(jù)進行有效的聚類分析，為更深入的AIS數(shù)據(jù)分析奠定基礎。