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

初秀民 林 宏 王志遠

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

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

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

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

1 AIS數據處理平臺設計與實現

1.1 總體框架

AIS數據處理平臺主要包括數據存儲層、資源管理層、計算引擎及接口、操作語言的運用。總體架構生態圖見圖1。

圖1 總體架構生態圖

1.2 數據存儲層

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

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

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

表1 AIS數據結構表

1.3 資源管理層

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

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

圖2 資源管理架構圖

1.4 計算引擎及接口

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

圖3 Spark框架圖

2 算法概述

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

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

(1)

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

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

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

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

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

(2)

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

(3)

3 試驗

3.1 硬件平臺搭建

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

圖4 架構圖

3.2 軟件環境

4臺計算機搭載的系統均為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。集群搭建內容見表2。

表2 集群搭建內容表

4 實驗結果分析

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

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

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

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

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

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

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

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

圖7 運算時間比較圖

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

5 結語

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