[0035] 步骤3.使用OPTICS算法获得轨迹点有序可达图。
[0036] 在基于密度的聚类方法的核心思想是用一个点ε邻域内邻居数衡量该点所在空间的密度。常见的基于密度的聚类算法有DBSCAN算法和OPTICS算法,后者是前者的高级演化。DBSCAN聚类的思想,即由密度可达关系导出的最大密度相连的样本集合,即一个簇。算法无须指定聚类个数,可以对任何形状的实现聚类。但DBSCAN存在高参数敏感问题,原因在于,DBSCAN通过手动输入全局参数ε(邻域的最大半径)与MinPts(核心对象的邻域中要求的最少点数),它把选择能产生可接受的聚类结果的参数值的责任留给了用户。全局参数造成算法的参数高敏感性,设置的细微不同可能导致聚类的批量误判。现有针对拖网渔船轨迹进行切分的MSC‑FBI算法即是基于DBSCAN算法。
[0037] OPTICS兼具了DBCSAN的优点,并克服了高参数敏感性缺点。OPTICS算法从任意一个数据对象开始,尽量向着密度大的地方扩张。它并不显示地产生数据集聚类,而是得到的是每个数据对象的可达距离及扩张顺序图,即有序可达图,该排序代表了各数据对象基于密度的聚类簇结构,可达距离数值越大,表明该点处越稀疏,可达距离越小,意味着点处越密集,每个凹陷代表一个聚类,聚类问题转换为有序可达图的凹陷截取问题。
[0038] 从拖网渔船轨迹数据有序可达图可知,见图2,它有着以下特征,凹陷区域内部较低且较平整、凹陷边缘较为陡峭。这说明相同行为拖网渔船的轨迹点的内聚程度很高,主要原因在于拖网渔船行为状态的稳定性与时空局部性,拖网渔船在同种行为下速度、角度基本不变,时间与经纬度距离也相差较小,因此相似度距离相差不大。反之,拖网渔船行为的切变使得切变点与相邻轨迹点之间的距离陡然增大,使得该点在有序可达图中值很大。因此通过识别陡然增大的点,可以实现有序可达图的凹陷分割。
[0039] 若设置参数ε截取有序可达图,其得到的聚类效果,与DBSCAN算法设置全局参数ε得到聚类的效果相同,换句话说,DBSCAN算法是OPTICS算法的一种特例。本发明采用OPTICS算法旨在获得有序可达图,在聚类的过程并不设置全局参数ε,而是采取ξ‑steep自动识别簇的方式截取每个凹陷(聚类簇),以得到更好的聚类效果。因此采用非全局参数的OPTICS克服了现有基于轨迹段聚类方法的强参数依赖问题。
[0040] 步骤4.使用ξ‑steep自动识别簇算法将有序可达图切分得到轨迹子段,实现对轨迹点初步聚类;
[0041] OPTICS算法并没有显式地给出聚类结果,而是用有序可达图来反映簇结构,因此如何在其得到的有序可达图中识别出各个簇也是很重要的一方面。拖网渔船轨迹数据点的有序可达图,它有着以下特征,凹陷区域内部较低且较平整、凹陷边缘较为陡峭。这说明相同行为拖网渔船的轨迹点的内聚程度很高,主要原因在于拖网渔船行为状态的稳定性与时空局部性,拖网渔船在同种行为下速度、角度基本不变,时间与经纬度距离也相差较小,因此相似度距离相差不大。反之,拖网渔船行为的切变使得切变点与相邻轨迹点之间的距离陡然增大,使得该点在有序可达图中值很大。因此通过识别陡然增大的点,可以实现有序可达图的凹陷分割。
[0042] 问题由有序可达图凹陷的识别转换为陡峭点的识别。因此本发明针对有序可达图中陡峭边缘的特点,设计了一种自动识别簇算法,下面引出的定义:
[0043] 定义1:有序可达图中,若点p∈{1,...,n‑1}可达距离r(p)与r(p+1)差值大于可达距离均值avr_r的ξ倍,则称点p为ξ‑steep point,记为Pointξ(p),其中,若前者大则称p为ξ‑up point,若前者小,则称p为ξ‑down point。
[0044]
[0045] 由上式可知,有序可达图中,所有陡峭点程度大于一定值的点将被记录为ξ‑steep point,这些是聚类簇的边界。
[0046] 稀疏点是聚类簇边缘的可达距离较大的点,稀疏点与密集区内的轨迹点同样具有三种行为状态,需要通过二次聚类实现状态的划分,因此本发明将稀疏轨迹点按长度为1的轨迹段处理。下面在有序可达图中给出稀疏点的定义:
[0047] 定义2有序可达图中,若点p∈{1,...,n}的可达距离r(p)大于可达距离均值avr_r的η倍,或点p∈{2,...,n}前一个值为ξ‑up point,且r(p)不小于r(p‑1),则称p点为sparse point。
[0048] 在轨迹切割中,按ξ‑steep point和sparse point将完整轨迹段切割成轨迹子段,即实现了拖网渔船轨迹子段的切割。
[0049] 步骤5.计算轨迹子段的速度平均值,使用k‑means算法实现轨迹段再次聚类,从而实现拖网轨迹点的分类;
[0050] 通过对轨迹子段的切分,将轨迹子段整体考虑,从而减少了波动数据对状态判断的影响。研究发现,在不同行为状态的轨迹子段在平均速度方面存在明显差异。航行状态下的轨迹子段的平均速度较大,捕鱼轨迹子段中平均速度较慢,而停泊状态时的平均速度最低。因此,本发明采用基于子轨迹段平均速度的K‑means算法完成子轨迹段的聚类,实现了拖网渔船轨迹点的分类。
[0051] 从拖网渔船轨迹子段平均速度分布图中可以看出,见图3,在不同行为状态的轨迹子段在平均速度方面存在明显差异。航行状态下的轨迹子段的平均速度较大,捕鱼轨迹子段中平均速度较慢,而停泊状态时的平均速度最低。区别明显,可使用聚类算法加以区分。
[0052] 步骤6.对于多步聚类结果,建立Fisher判别模型,实现拖网渔船轨迹点处行为的快速判别。
[0053] 为了能实现对轨迹数据的实时判别,OMSC‑FBI算法需要建立一个拖网渔船行为判别模型。
[0054] 假设通过OMSC‑FBI算法,将一条长度为n的拖网渔船的轨迹TR的轨迹点分为k组,分别记为G1,G2,…Gk,且每组轨迹的长度分别为n1,n2,…,nk,满足n=n1+n2+…+nk。每个轨迹T点由一个p维的向量(如速度、方向、时间、经纬度等)x=(x1,x2,…xp) 表示。根据轨迹点的p维属性信息,构造拖网渔船行为判别函数如下:
[0055]
[0056] 其中,判别系数向量a=(a1,a2,…,ap)T待求,且能够使得同组内的离差最小。
[0057] 为了表达的方便,假设 代表第i类行为的第a个样品的观测向量。m代表所有轨迹点的均值向量,mi代表第i组Gi的样本均值。组间平方和为SSG,组内平方和为SSE,则在k>1的情况下,Fisher判别准则就是选取合适的判别系数向量a,使得
[0058]
[0059] F取最大值。即求a,使得 为保证取得唯一性,设aTEa=1。因而构造辅助函数得:
[0060] χ(a)=aTBa‑λ(aTEa‑1)
[0061] 求导可得:
[0062]
[0063] 即得
[0064]
[0065] 这说明λ和a分别为矩阵E‑1B的特征根与相应的特征向量。由此可知,拖网渔船行为判别模型总共由m个判别是组成,这m个公式利用轨迹点数据共同完成拖网渔船行为的判别。
[0066] 依据上述设计,本发明的主要部分伪代码如下所示:
[0067]
[0068]
[0069] 应该理解到的是:上述实施例只是对本发明的说明,而不是对本发明的限制,任何不超出本发明实质精神范围内的发明创造,均落入本发明的保护范围之内。