走一步看一步之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

分享一些个人理解和整理的物海方面有关编程技术的知识，大家一起学习一起进步。