走一步看一步之Python篇：處理AIS數據

前言

在處理全球AIS數據時，遇到一些問題，其中包括了數據量大，數據在時空不連續的問題。在剛開始時，計算效率低，所需時間長，存在重複計算。於是在處理這個問題上，演算法以及計算流程就成了很重要的內容。針對出現的問題和數據特點，來介紹我的處理思路。

其中經歷了三個過程：

表1 三次處理問題情況匯總

1 要做的事情：

粒子碰撞問題

根據DCPA、TCPA的概念，計算兩條船是否有碰撞危險。（DCPA：存在碰撞危險的可能性。）其實就是粒子碰撞問題，

一條船->找到他周圍的某一條船->計算6分鐘內的位置->兩船是否在安全距離

2 問題描述：

數據量大+數據時刻不連續+重複計算

AIS是每條船一份txt，包含了該段時間內的所有信息。但由於出現了數據量大、數據時刻不連續、存在重複計算的。

數據量大：幾十萬份的txt文件，轉成json格式，存入MongDB。

數據時刻不連續：主要採用了list和dict類型，放棄了matrix 。

重複計算：因為每個船在一定的區域中，利用笛卡爾坐標系將區域劃分為矩形網格，建立了網格ID編號，只與對應的網格進行計算。在此基礎上，加入了Flag屬性確定網格所在位置，區分開角、邊和中部的網格，來避免重複計算以及邊界問題。

3 處理思路：

時間劃分+網格劃分+計算距離

3.1 時間劃分問題

因為數據時間範圍是3個月，而計算兩條船是否有碰撞危險，首先需要確保兩條船在同一時間，而AIS數據，常有缺失，在時間上不連續。在這裡，我先按整點時間，從10月1日00:00:00起劃分了2210個時刻。

在時間劃分好後，需要將該時刻的船舶信息對號入座。最初想到兩個辦法

直接讀取txt，按時間存到矩陣中。這就帶來了Matlab內存不足的問題。

每次讀取一個時間，進行計算。但是時間上，效率太低。每份txt對應一條船，數量級在10萬。直接遍歷所有txt，需要9個小時，並行加速後也需要4個小時。

最後，將數據轉換為json格式，存入MongDB資料庫，寫入全部數據需要10個小時。但是再次檢索數據時，一般在0.5s左右。

在解決了上述問題後，需要進行計算船舶之間的相對距離。如果直接計算，假設同一時刻有20萬條數據，需要計算n！次。於是，將區域劃分為更小的區域，使得一個區域內的船舶數量較小，計算量會銳減！網格數量只會增加10的4次方倍。在後面會展示一個測試過程，便於理解網格數增加，卻使得計算量減小的事情。

3.2 網格劃分問題

基於3.1中提到的將區域劃分為網格的思路，在操作時需要解決兩個問題1.網格如何設置。2.與周圍網格進行計算。如果一個船在網格邊，他會與臨近區域之間的船存在碰撞的可能。

為了理解情況2的問題，假設經過劃分網格後，ABC三條船恰巧在這個位置，見圖1，這時他們之間是有碰撞危險的。所以需要與臨近的網格進行計算。

圖1 臨近網格問題示意圖

3.2.1 網格如何設置

先確定了網格間隔，我取了0.5? x 0.5?，於是產生了24*40，共960個網格。注意，必須保證網格距離大於 兩條船+安全距離，（大的船為500m，夜間安全距離為2 nmile）。因為兩個坐標點可以確定一個矩形。我給用dict類型定義了每一區域，包括左下角經緯度，右上角經緯度，ID編號，見圖2。之後又增加了網格識別的Flag和該網格下的碰撞頻數，下面會提到為什麼增加這個兩個key。

圖2 單獨網格圖

圖3 全部網格示意圖

(在獨立網格的基礎上，加入了Flag值。而Flag的1、2、3分別為角、邊、中部)

3.2.2 與周圍網格進行計算

為了避免重複計算，由上面的網格設置發現，有三種不同的情況，見表2。

表2 網格情況

分析每種情況，在Flag為1時有左下角、右下角、左上角、右上角，分別標為1.1、1.2、 1.3、 1.4，見圖4；在Flag為2時，有上下左右四條邊，分別標為2.1、2.2、2.3、2.4，見圖5；當Flag為3時，網格在中部。需要注意的是，進行編號，是為了在之後計算中避免重複。

圖4 網格中四角示意圖

(為了理解避免區域重複計算的處理方法，這裡分成1.1、1.2、1.3、1.4 四種情況。示意圖中沒有標出斜角的網格，周圍網格數應該為3，見表2)

圖5 四邊網格示意圖

(為了理解避免區域重複計算的處理方法，這裡分成2.1、2.2、2.3、2.4 四種情況。示意圖中沒有標出斜角的網格，周圍網格數應該為5，見表2)

以左下角為起始點，進行計算。分析每個網格區域發現：

由圖6可以看出，不同位置的網格與需要計算的臨近網格數量、位置是不同的。雖然有相似的情況，比如1.3與2.3 1.2與2.2 2.4與3。但是在代碼中，依舊按照先Flag判斷位置，再對每種Flag下的不同情況進行計算。這是因為邊角的網格數量很少，通過判斷來理清思路。出於判斷方便的考慮，在區域的字典中又增加了網格識別的Flag。

因為這樣整理後，計算量急劇減少，於是沒有進一步按田字格法進行劃分。

圖6 計算順序

3.3 田字法確定臨近網格

在這裡簡單介紹該方法，該方法是通過對象的位置以及網格間距來確定臨近網格，從而減少計算量的方法：

圖7 田字格法

如果一條船在(2,3)中，除了要與(2,3)區域內的船進行計算，周圍有8個區域。

而如果判斷出該船載區域(2,3)的第二象限，它只需要和(1,2)(1,3)(2,2)(2,3)，進行計算，只就是上面提到注意網格間距設置的原因，間距過小，一條船會跨區域。

3.4 計算距離

在確定網格計算後，就需要處理的是兩個船舶的計算。判斷兩條船有三種方法，我最後選用平方法，這是因為通過網格劃分，網格計算過程的設計，計算量已經很小了。直接兩點的直線距離又是最好理解的。

平方法（計算了求距離公式，但沒開平方，比對的時候跟半徑平方去比）；

矩形法，認為落在X+-R和Y+-R（圓的外接矩形）里的點都為碰撞；

內接矩形法，在X+-R和Y+-R判斷的基礎上，把落到內接矩形內（X+-r,X+-r）的點判斷為碰撞，落到外接矩形和內接矩形之間的點，做平方法再次判斷。

分割的最優份數跟數據量正相關。

圖8 計算距離方法比較

如果數據量大, 內接矩形法其實代表的是排序法的解決問題思路，就是通過x,y方向排序，求交集的辦法來確定兩船是否有危險，在數據量極大時，該演算法複雜度由n！降到了3*n*排序次數。

下面展示一組測試:

做了個試驗，將數據細分成非常細的網格，用網格編號建立索引，直接把所有數據扔到網格里。檢測的時候直接查表找碰撞可能大的鄰居網格，再在鄰居網格里查表搜集鄰居數據，在鄰居的集合內，用什麼方法影響不大（因為數量已經少到幾百或者幾十了）。

由圖9可以看出，存在一個最優的網格間隔設置範圍，在該範圍內。三種計算方法差別不大，效率都很高。

圖9 計算距離方法比較

(圖中指的「分割數」，是將1度（經度或維度）分割成多少份。占內存較多，分20份的時候內存佔用約為2.5g)

回到直接計算兩點直線距離，我採用了haversine公式計算球面兩點間的距離。於是，在確定計算方法與船所在的網格後，就需要根據「3.2.2 與周圍網格進行計算」部分提到的思路來找。

為了找到臨近區域。這裡最開始想到的兩種方案

1.在時間下，建立一個list包含960個區域，然後將每條船舶數據放到區域下。

2.在一個區域下，建立2210個時刻，然後將每條船舶數據放到該區域的時間下。

經過測試後，這兩種辦法，在我面對的情況下都很蠢，我按第三個方案來做。通過循環原始傳播數據數據，在每個船的dict下加入了 area_belong_ID的key值。

加入area_belong_ID，優點是十分方便。這是因為，在3.2.2分析後，每個網格與周圍的網格編號關係是確定的，這裡我在程序中利用一個數組need_ID來記錄需要計算的網格編號，只需要先確定area_belong_ID，然後返回該區域的need_ID，最後在同一時刻下，判斷其他船舶的area_belong_ID好是否在need_ID範圍內。如果在，計算距離。

船舶數據又在一個list下，避免重複計算，我通過引入一個計數器，來避免重複計算。

因為有了area_belong_ID，他與區域的ID是一一對應的，如果小於安全距離，在網格的DCPA_frequency上加一。而這裡是list，於是很方便的新添一個key到網格的dict中，見圖2。

至於安全距離，因為每個ship對應的有time這個key值，於是加入判斷，區分白天黑夜，白天安全距離是1 nmile 黑夜安全距離是2nmile。

3.5 回顧整個過程

主要是根據最初的圖 展開的遇到了網格劃分，網格劃分中遇到了如何建立每個網格，距離選取，計算順序的問題。通過紙上畫圖，分析發現加入Flag可以幫助理解。

在之後的船舶距離計算，發現了距離的不同演算法，經過測試，最後選擇了平方法。

通過網格的思想，在船舶中加入了區域ID號，為了避免同一時間下的重複，加入了計數器。

4 收穫

笨辦法+資料庫+list+測試

在第一次處理這個問題時，結果是計算1天的數據需要8個小時。認識到的經驗和教訓：

i) 演算法重要；有了合理的演算法，計算效率。比如在計算碰撞中，細分區域和時間是重要的，因為這樣減少了計算量，而分區域知識進行一個判斷，判斷用的時間少。

ii) 資料庫要學會使用txt最後將r寫成了.js, 導入MongDB。

iii) 並行運算要學習。才能利用好這些工作站，超算等工具。

這次的收穫是

1. MongDB資料庫使用.

熟悉了MongDB語法。12月處理時遍歷txt，讀取20萬份txt中的數據，需要5個小時。

現在寫入資料庫需要4-5個小時，之後使用只需要2.0s左右的檢索時間，大大提高效率。

2. list列表格式的使用。

因為以前常處理的都是海洋上的產品數據，即使argo等，我也按網格化處理。ais數據，時間缺失無規律、數據量大的特點。無法用數組使用。

理解了list與數組的優缺點:

matrix 是為了便於直接查找訪問，他會要求數據項基本整齊。計算時空上連續的數據，十分迅速。

list 則方便增加個體的key，增加特徵。在這次AIS中，做到後面，發現需要一些flag或者ID，用list十分方便解決這個問題。但是他的缺點，在犧牲了空間，將所有內容降維到一個維度，這就需要多次的遍歷。

總之，list與matrix 結合使用，才可以提高效率。只有解決實際問題，能更好理解兩者的限制因素。

3. 演算法

在設計演算法時，結合複雜度的概念，預估了每種分區方案帶來的計算量是多少。所以在設計網格區域，計算距離上花費了大量時間。但在確定之後，寫的代碼較為清晰。

這是基於上次使用Matlab處理過，與兩位老師的交流，與同學多次討論，才體會到的。

4. 測試

我在每個遇到的問題，都單獨建立了test_task.py，進行獨立測試，記錄測試結果。這會對自己做的事情有一個更深入理解，能夠更好地把握自己的準確度。

這就是我處理這個事情的思路。中間遇到了問題，受到了一些高人的指點，還麻煩了師兄，朋友們。其中文財、7號幫我編寫了部分Matlab，大鎚子來幫我理思路，程寫了資料庫。還有找師兄，好朋友進行瘋狂吐槽………

在完全沒思路時，校園裡瞎逛，遇到了幸運草。

微信號：op_programmer

分享一些個人理解和整理的物海方面有關編程技術的知識，大家一起學習一起進步。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！