1. 研究目的与意义（文献综述）

本文的研究目的在于吸收和借鉴目前已有的相似性度量方法，如dtw、lcss等。基于ais数据流，提出一种新的改进的船舶轨迹相似性查询的方法，使之能获得较高的效率和准确率。

本文设计的意义：

轨迹数据挖掘已经成为研究热点，由文献[4]总结可知，由于无线通信技术和gps定位技术的发展，获取船舶等移动物体的位置数据益发简单，大量的位置数据形成了轨迹数据。从产生的海量轨迹数据中挖掘出有用的信息已经非人力可及，因此轨迹数据挖掘显得尤为重要。分析轨迹的相似性、提取相似移动轨迹在轨迹聚类、路径预测等领域具有广泛用途。比如通过分析轨迹的相似性来预测船舶行为，及时发现并处理船舶异常轨迹行为，从而获得船舶典型航行轨迹，为实现智能船舶交通管理系统打下坚实的基础。[5]

2. 研究的基本内容与方案

基本内容与目标：

1）通过阅读相关文献，AIS、实时流计算、轨迹相似性度量方法DTW和LCSS等相关知识；

2）分析目前常用的轨迹相似性度量方法的优劣，如DTW和LCSS，并基于AIS数据流特点，设计船舶轨迹相似性查询算法。

3）实现所设计的算法，使之能获得较高的效率与准确率，并利用实测数据予以验证和分析。

技术方案及措施：

大体上分为四个步骤：

1）AIS数据流预处理

当今水上船舶航行数据主要来自于船舶自动识别系统AIS，AIS数据能提供船舶的动态和静态信息，如：船舶的位置（经度、纬度）、航速、航向等动态信息，以及船舶的名称、类型、MMSI、IMO、呼号、船籍、船长、船宽及吃水等静态信息。AIS基于TDMA通信技术，将采集到的船舶的动态和静态信息以一定的数据格式，通过甚高频频道以数字编码的形式进行广播、接收，是离散且不易理解的数据。因此，第一步应该是对AIS数据进行解析并将其存储为结构化的数据格式。根据IEC61162标准的相关规定，AIS信息中最常见的语句是VHF数据链电文（VHF Data-Link Message, VDM）。同时，AIS报文有明码和暗码之分，明码信息以“$”开头，可以直观读取其中所包含信息；暗码信息以“!”开头，需要按规则进行解码，解码过程如下：

① 将报文信息中的ASCLL码转换成6bit的二进制数；

② 根据相应的电文编号，分割所转换的二进制字符串；

③ 使用相应的标准文件规则，将分割后的二进制字符串转换成相关信息。解析规则如下表所示：

表 2-1 二进制字符串分割与信息解析

在本文的数据预处理中，用到的AIS信息主要有精度、纬度以及时间UTC等。^[13，14]

2）轨迹特征提取

移动对象的运动特征包括速度、加速度、方向、转角、曲率、位移等等，这些特征能够有效地揭示移动对象的行为。由于AIS数据发送频率较大，导致重点轨迹特征不突出，数据冗余度较大（船舶在静止时信息点完全重复），从而导致查询消耗大、效率低等弊端。因此对采集到的AIS数据进行适当的裁剪可以有效地提高轨迹查询和挖掘分析的效率。例如，当船舶在航行的某一段轨迹区间近似一条直线时，只需要起始点和终点就可以了。具体的特征抽取过程如下：

① 将原始轨迹的起始点ps1作为轨迹的特征点加入至特征点集；

② 计算下一原始轨迹点与最新的特征点之间的航向变化率，若航向变化率超出阈值，则视为航向变化特征点，加入特征点集，若未超出阈值则转入步骤③；

③ 计算原始轨迹点与上一特征点之间的航速变化率，若航速变化率超出阈值，则视为航速变化特征点，加入特征点集，若未超出转入步骤④；

④ 判断是否为轨迹终止点，若为终止点，则直接保存为特征点，完成轨迹特征抽取处理，若不为终止点，则转入步骤②。^[13]

3）相似性查询算法

DTW是使用最广泛的轨迹距离测量函数，经过大量的实验对比，在所有时间序列距离度量函数中，DTW是表现最好的一个。但DTW采样比较苛刻，如果存在完全不相似的区间，由于DTW要求匹配具有连续性，就不会将噪声与不相似区间区别对待，所以必将对噪声敏感。同时，DTW一般计算开销较大，对于数据量较大的情况下，计算效率明显下降。所以基于传统的DTW算法，此次设计的方法拟在提高准确度和计算效率两方面展开一些工作。

① 高准确度的计算方法

DTW算法本质上是欧式距离的计算，而欧式距离的计算对采样和采样率有严格的限制，它要求匹配的连续性，因此对噪声和完全不相似的区间辨别力不强，从而导致噪声敏感，计算结果偏差。受DNA序列校准相关算法的启发，文献[3]中引入了间隔点(gap)的概念，允许存在不和任何点匹配的点，同时对DTW的目标函数进行改进，提高了结果的精确程度，能够分别出轨迹真正相似的部分。

参考文献[9]中使用加权方法控制地理相似度和语义相似度对总的相似度的贡献的方法。在一条轨迹中，每对点的欧式距离对最终的相似性度量的贡献可以是不同的，比如：当船舶航行轨迹接近于直线时，起点和终点的相似性度量已经可以确定其DTW距离，而轨迹上其他点的信息对最终的查询结果贡献度不大。

本次设计中，将尝试通过提高对噪声的识别力和加权距离的方法，提高相似性查询的准确度，并在真实的实验中比较这两种方法查询的准确程度。

② 高效率的计算方法

对于长度为n的轨迹数据而言，如果直接使用动态规划算法计算两条轨迹之间的DTW距离需要O(n²)的时间复杂度。无疑这样的计算方法随着n的增长，计算时间将呈指数倍增长，效率极低，其实用性大大降低。

LCSS算法在克服噪声和数据畸变方面表现优秀，但面对大数据量时，如果直接应用LCSS，效率依然不够理想。LCSS问题的关键在于找到一个最长的相同子序列，规定两条的相似度为最长公共子序列的长度。计算方法如下：设两个长度分别为m和n的轨迹分别为 st1＝＜w₁₁,w₁₂,...,w_1mgt;， st2＝＜w₂₁,w₂₂,...,w_2n＞。L[i,j]为轨迹st1和st2的最大匹配度，则轨迹st1 与st2 的最大匹配度为L[m,n]可以采用动态规划算法得到。动态规划算法的时间复杂度较高，对于离线数据集的查询，我们可以牺牲查询时间以获得高准确率。然而对于在线查询，准确度的要求略微降低，但对于计算效率的要求却更高。

数据流相似性查询的研究目标是：给定查询序列Q= lt;q₁,q₂,…,q_ngt;，数据流S = lt;s₁,s₂,…gt;，当新数据s_{i m-1}到达时，针对由最近m个数据形成的子列S(i,i m-1) = lt;s_i,s_{i 1},…，s_{i m-1}gt;，实时、快速地度量它和Q之间的相似程度，从而找出流上所有满足搜索条件D(Q,S(i,i m-1))≤δ的子列。在文献[2]中，提出了一种基于LCSS算法的数据流相似性查询算法，并将其命名为D2S查询，即根据NA#207;VE算法中动态规划矩阵成员相关的冗余运算存在规律，提出一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询算法。

最后希望针对AIS数据流特点，改进上述算法，使之能获得更高的轨迹查询效率，并通过实验对比，证明这一点。

4）查询准确度与效率评估

在查询性能评估方面，使用真实采集到的长江流域AIS数据集进行实验。

① 准确度评估

借用信息检索领域常用到的准确率、召回率和F值评价查询结果有效性。

准确率(Precision)，又称“精度”、“正确率”、“查准率”，表示在查询到的所有相似轨迹中，查询到的相似轨迹所占比例。

召回率(Recall)，又称“查全率”，表示在所有相似轨迹中，查询到的相似轨迹所占比率。

二者的公式为：

准确率 = 查询到的相似轨迹数量/查询到的所有相似轨迹；

召回率 = 查询到的相似轨迹数量/所有相似轨迹总数。

F值是综合衡量准确率（P）和召回率（R）的，公式为：

F=2*P*RP R

选取4-5个不同规模的数据集，对比其他相似性度量方法，通过评价指标F值在相应数据集中的大小，评估改进的DTW算法的查询准确度。

② 计算效率评估

使用配置相同的PC机，分别输入多个不同规模的AIS数据集进行实验，实验分为两个部分：1）分析相似性查询算法的时间性能；2）分析相似性查询算法的空间消耗情况。

这两部分实验可以从滑动窗口大小、全局相似阈值、查询轨迹序列长度、数据流速大小（在线查询情况下）几个方面比较本次设计中的相似性查询算法与其他算法的查询时效，以验证该算法的效果。

3. 研究计划与安排

1. 2017/1/14—2017/1/30：查阅参考文献，明确选题；

2. 2017/1/31—2017/2/28：进一步阅读文献，并分析和总结；确定技术路线，完成并提交五千字外文翻译和开题报告；

3. 2017/2/28—2017/4/26：需求分析，算法或系统设计，系统实现、分析及测试等；

4. 参考文献（12篇以上）

[1]陈金海,陆 锋,彭国均,等.船舶轨迹数据的geodatabase管理方法[j]地球信息科学学报,2012,14(6):728-735.

[2]王少鹏,闻英友,赵 宏.基于lcss的数据流相似性查询处理算法研究[j]计算机研究与发展,2015,52(9):1976-1991.

[3]郭 岩,罗珞珈,汪 洋,等.一种基于dtw改进的轨迹相似度算法[j]国外电子测量技术,2016,35(9):66-71.