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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180425G1N81400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券