论文部分内容阅读
[摘 要]由于未考虑轨迹数据的具体特性等问题,传统的目标轨迹预测在预测大数据目标轨迹时会受到很大的限制,对此,为提高轨迹预测在动态大数据目标轨迹规划中的全局预测能力,提出了一种基于双线性流形的动态大数据目标轨迹预测(DLDTPBM)算法。首先采用数据预处理方法处理可能包含重复、噪声和高维度的原始数据,将未加工的原始数据转换成适合分析的形式通过DLDTPBM大数据预测方法实现对目标运动参量的准确估计和预测,由此指导目标轨迹的准确预测,提高预测精度。通过实验结果对比分析,本算法精度较高、双线性流形性能较强、稳健性更好,优于传统轨迹预测算法,能够有效解决轨迹数据的时间等具体特性。
[关键词]轨迹预测 数据预处理 双线性流形 动态大数据 移动对象
中图分类号:TP391.9 文献标识码:A 文章编号:1009-914X(2019)09-0127-04
Dynamic Large Data Target Trajectory Prediction Based on Bilinear Manifolds
HANG Guo-liang, ZHOU Ya, CHAI Wang, HAN Jun-yang
(School of Computer and Information Security, Guilin University of Eletronic Technology, Guilin 541004, China)
Abstract: Due to the lack of consideration of the specific characteristics of trajectory data and other issues, the traditional trajectory prediction in the prediction of big data target trajectory will be greatly limited, in order to improve the trajectory prediction in dynamic large data target trajectory planning of the global prediction ability, A novel dynamic large data target trajectory prediction (DLDTPBM) algorithm is proposed based on bilinear manifold. Firstly, the data preprocessing method is used to process the original data which may contain repetition, noise and high dimension, and the unprocessed raw data is transformed into a form suitable for analysis. The accurate estimation and prediction of the target motion parameters are realized by the DLDTPBM big data prediction method. Guide the accurate prediction of the target trajectory, and improve the prediction accuracy. Compared with the experimental results, the proposed algorithm has higher accuracy, stronger bilinear manifold performance and better robustness than the traditional trajectory prediction algorithm, which can effectively solve the time and other specific characteristics of the trajectory data.
Keywords: Trajectory Prediction; Data preprocessing; Bilinear manifolds; Dynamic big data; Moving object
1.引言
隨着大数据和互联网的迅速发展,出现了动态大数据目标轨迹预测技术[1],人们已经可以对某一特定状态下的信息或资源进行大数据轨迹的计算,而具有相似轨迹的大数据之间非常有可能存在某种联系[2-3]。目前,大数据表达数据预测最常用的方法是目标轨迹预测,将表达水平相近的特征大数据聚在同一个类中[4],从而可以发现未知大数据的信息和具有研究价值的大数据信息[5-6]。
乔少杰[7]等人在对移动对象进行交通流模拟时利用基于隐马尔科夫模型的自适应轨迹预测模型进行位置密度分区和分段处理,从而做出较高的计算准确性。李倩伟[8]等人利用大数据多传感信息融合跟踪,对控制对象描述和约束参量分析,通过大数据分析方法实现对移动目标对象的准确预测,提高预测精度。毛嘉莉[9]等人指出,由于未考虑轨迹数据的时间特性,对此,加入了轨迹异常检测的分类总结,提出轨迹大数据异常检测的系统架构。夏卓群[10]等人认为,轨迹预测在动态环境中预测精度不高,实时效果差,提出一种结合高斯混合模型的环境自适应轨迹预测。刘卉[11]等人提出了一种基于模型预测控制的轨迹跟踪算法,采用线性误差模型作为预测模型,应用非线性模型作为位置解算法,以此来达到算法的良好特性。 但是传统的目标轨迹预测在预测大数据时会受到或多或少的限制[12-13],大数据轨迹预测算法实际上是一种多目标优化的预测算法,对于繁杂的数据矩阵,如果直接对其进行轨迹预测,稍显不太灵活。
本文提出的基于双线性流形的动态大数据目标轨迹预测(Dynamic Large Data Target Trajectory Prediction Based on Bilinear Manifolds,DLDTPBM),并通过贪婪策略逐步增删使得轨迹预测的均方残差达到最优[14-15],采用的方法是先对整个大数据矩阵全局寻优,将找到包含最优解的子矩阵作为种子,再对其进行轨迹预测。
2.相关工作
2.1.轨迹数据
轨迹数据就是时空环境下,通过对一个或多个移动对象运动过程的采样所获得的数据信息,包括采样点位置、采样时间、速度等,这些采样点数据信息根据采样先后顺序构成了轨迹数据。
轨迹挖掘是数据挖掘的一个新兴分支,其研究热点集中于聚类轨迹、分类轨迹、离群点检测、兴趣区域、保护隐私、推荐位置等方面。如果将时间看做是一维数据,大多数传统高维数据聚类算法可以很好的适应于当前的聚类轨迹。
2.2.预处理
轨迹数据作为轨迹大数据的处理对象,预处理效果直接对轨迹预测产生影响,针对不同的应用背景,采用不同的预处理方法,本文使用了轨迹数据预处理中的聚集和维规约的方法:
聚集:是指将两个或多个对象合并成一个对象,聚集的作用是减少数据的个数,突出数据的趋势和轨迹;
维规约:是指降低数据的维度,即减少数据属性的个数,规约的目的是降低数据挖掘算法的时间和内存需求,删除不相关的属性并降低噪声。
其具体实现步骤如下:
第一步:按时间顺序获取目标轨迹数据;
第二步:解析轨迹数据,将数据抽象存储,对轨迹进行编号,加入轨迹点ID;
第三步:查找轨迹遗漏点,分析缺失类型,针对不同类型进行遗漏点处理填充;
第四步:采用误差平方和函数作为聚类准则函数,欧式距离作为相似性检验的评价指标,对所选择轨迹的特征进行计算和提取;
第五步:对于轨迹点聚类,认为簇是由距离靠近的对象组成,因此把得到紧凑且独立的簇作为最终目标,当检测出有单独的点并不属于任何簇时并且与时间序列不匹配时,则认为是异常点,可考虑去除异常点;
第六步:对聚类后的数据集进行处理,每次取三个点作为研究对象,若三个点基本在一条直线上,便可去掉其中的非拐点,最多去掉其中两个点;
第七步:寻找轨迹拐点,并保存其拐点信息,对拐点进行调整,生成轨迹切割集,按切割集进行轨迹切割并保存;
第八步:更新轨迹数据并输出以便进行下一步实验操作。
3.动态大数据优化算法
3.1.随机检测数据集
在大数据目标轨迹预测问题中,给定一个M×N的大数据矩阵A,将M条大数据划分到K个目标轨迹预测中去。通过大数据在预测空间中的轨迹预测,选出代表问题解决方案的最优大数据。每一个大数据Xi=(Mi1,...,Mij,...MiK)代表K个目标轨迹预测的质心向量,Mij表示第i个大数据中第j个目标轨迹预测的中心向量。Pi(t)为个体最好位置,G(t)为全局最好位置,且G(t)= Pg(t),g为处于全局最好位置的大数据的下标。
随机检测数据集(RTDS)算法不需要大数据的速度信息,β为收敛-发散因子,是除了数据库规模和迭代次数外唯一的一个参数,RTDS具有进化方程简单,控制参数少,收敛速度快,运算简单等优点。
3.2.多目标轨迹优化的DPEE算法
对于一个m行n列的矩阵A,Aij为A的一个子矩阵,其中I为行(大数据)的子集,J为列(条件)的子集,若Aij的均方残差值满足一定的条件,则称Aij为一个轨迹预测;其中,均方残差的计算公式为:
(4)
其中,aij为Aij的有效元素,aiJ,aIj和aIJ分別为行平均值、列平均值和矩阵平均值。DPEE算法通过插入或删除具有最高收益的行(列)的方式来提高轨迹预测的质量,进而改进整个轨迹预测种群的质量,最终得到最优轨迹预测集。
多目标优化的DPEE算法的流程为:
第一步:计算大数据矩阵各行(列)的收益值;
第二步:对各行(列)的最高收益进行排序;
第三步:按顺序插入或者删除这些行(列);
第四步:判断执行动作后,轨迹预测的平均容量是否增大,若增大则保存最优轨迹预测作为下一次迭代的初始值,回到第一步继续迭代;否则,算法结束,输出当前最优轨迹预测。
3.3.DLDTPBM轨迹预测算法
3.3.1 双线性流形算法
本文提出实物双线性流形的动态大数据轨迹预测算法。该算法中已知大数据表达矩阵A=(X,Y),包含M条大数据和N个样本条件,该数据集合划分为指定的K类,使所得到的目标轨迹预测划分能使总体类间差异最小。
用Ak表示第k个大数据目标轨迹预测,xin表示在当前目标轨迹预测中第i个大数据在第n个样本条件下的表达水平;ZK为Ak中质心向量的个数,则Ak的质心向量为ck=(ck1,ck2,…,ckn),且 ,定义目标轨迹预测Ak中类内适应度函数WCV为:
则总体差异TWCV可以表示为:
该适应度函数是每种目标轨迹预测的类内适应度函数WCV的和,WCV的值越小说明类内各个目标彼此更紧密,也就是目标轨迹预测质量越好。
大数据双线性流形度量的公式如下:
其中,S表示动态大数据,|L|表示求解空间最长对角线的长度,N表示问题的维数。在DLDTPBM算法中,单个大数据的收敛性是受收敛-发散因子β控制。动态大数据在初始化后会进入收敛状态,这时β会从1.0线性减小到0.5。 以公式(1)为进化方程的RTDS算法中,单个大数据收敛的充分必要条件是 。所以存在 ,当 时,大数据收敛;当 时,大数据进入发散状态。
目标是轨迹预测的剩余值尽可能小,本文使用评价函数F(k,A)来计算一次迭代中产生的轨迹预测的质量,其中F(k,A)的计算公式如下:
F(k,A)表示原大数据矩阵A的第k个轨迹预测矩阵的质量,rk是它的平均平方残差,vk是它的容量,λ1和λ2分别是均方残差和容量的权值。
3.3.2 DLDTPBM算法流程
算法首先使用DLDTPBM算法对原矩阵进行划分;然后对划分后的子矩阵进行DPEE目标轨迹预测,使用公式(9)作为评价函数,基于多目标优化的DPEE的DLDTPBM算法流程如图1所示:
其算法具体描述如下:
第一步:数据初始化,使用双线性流形的RTDS算法产生k个初始矩阵;
第二步:分别计算这k个轨迹预测矩阵每一行和每一列的动作收益;
第三步:比较收益值的大小,得到各行各列的最优动作;
第四步:对这些最优动作排序,并按顺序依次执行;
第五步:执行动作后,根据公式(5)判断轨迹预测的质量是否有所提高,若有,则保存最优轨迹预测作为下一次迭代的初始值,回到第一步继续迭代;否则,算法结束,输出当前最优轨迹预测。
4.实验及讨论
4.1.实验数据与环境
实验使用动态大数据数据集,动态数据集共有38个动态样本和7129个大数据,实验在装有Microsoft Windows 10系统的PC机上运行,CPU为Intel酷睿i5,8G内存,实验语言为Java 1.8,实验环境为IntelliJ IDEA。
本实验随机选取70%的数据作为训练集,30%的数据作为測试集。
4.2.实验结果评判
均方残差是在线性模型中衡量模型拟合程度的一个量,用连续曲线近似地刻画或比拟平面上离散点组,以表示坐标之间函数关系的一种数据处理方法。一组数据的均方残差越小,其拟合程度越好,预测效果也就越好。
为了评价轨迹预测的质量,本文采用均方残差(MSR)、矩阵规模(V)和行变动值(Var)作为大数据矩阵表达一致性的度量标准,行变动值(Var)的计算方法如公式(11)和公式(12)所示:
4.3.实验结果及分析
对比实验中所采用的算法代号及名称说明如下:
(1)RTDS:随机检测数据集;
(2)DPEE:动态规划有效等式法;
(3)DPEE2:多目标优化的动态规划有效等式法;
(4)DLDTPBM:基于双线性流型的动态大叔目标轨迹预测。
实验开始之初,首先进行一组对比实验,分别为:1、对原始数据直接分析计算;2、对可能包含重复、噪声和高维度的原始数据,将未加工的原始数据转换成适合分析的形式带入算法。实验表明做过预处理的这组实验时间明显更顺利,更快,执行时间相对与未进行预处理时优化将近20%左右,如图2所示:
该算法将与RTDS、未改进的DPEE算法,以及多目标优化的DPEE算法进行比较。动态大数据规模为40,迭代次数300次;将动态数据集聚为两类,云环境数据集聚为五类;通过实验确定公式(9)中参数λ1取1,λ2取1.8;d_low设置为0.0005。
实验结果及原始值的走势图如图3所示。
结果分析计算,可以得出如表1所示的性能参数值。
表1是DPEE算法、多目标优化的DPEE算法(DPEE)、RTDS算法和DLDTPBM轨迹预测算法在两个数据集上10次实验的平均值。从表中可以看出,多目标优化的DPEE算法的均方残差值比DPEE算法减少了19%,但是RTDS算法和DLDTPBM算法相比于DPEE2等算法,均方残差值减少了50%左右,优势比较明显。
5.总结
本文提出的DLDTPBM轨迹预测算法,该算法首先利用双线性流形处理数据,根据双线性流形度量函数的值判断大数据的状态,再结合DPEE2算法,修改其迭代目标函数,弥补了DPEE2算法在处理多目标优化问题时的不足,以提高算法的全局预测能力。通过对算法进行比较,实验结果表明,DLDTPBM和RTDS算法的均方残差值与DPEE2算法相比,得到的目标轨迹预测矩阵相似性更集中,总体质量上有很大幅度提高;将DLDTPBM与RTDS算法相比,虽然规模相差不大,但是DLDTPBM均方残差明显减小,说明DLDTPBM相比较于RTDS算法在性能上有所提高,具有更好的全局寻优能力,且目标轨迹预测效果更佳。
参考文献
[1]Trasarti, R., Guidotti, R., Monreale, A., & Giannotti, F. Myway: location prediction via mobility profiling[J]. Information Systems, 2017 , 64, 350-367.
[2]Kristiansen, K. U., & Wulff, C. Exponential estimates of symplectic slow manifolds[J]. Journal of Differential Equations, 2016 , 261(1), 56-101.
[3]Johnson, O. A., Hall, P. S., & Hulme, C. Netimis: dynamic simulation of health economics outcomes using big data[J]. Pharmacoeconomics, 2017 , 34(2), 107-114. [4]Singh, K., Guntuku, S. C., Thakur, A., & Hota, C. Big data analytics framework for peer-to-peer botnet detection using random forests[J]. Information Sciences, 2014 , 278(19), 488-497.
[5]Fan, B., Leng, S., & Yang, K. A dynamic bandwidth allocation algorithm in mobile networks with big data of users and networks[J]. IEEE Network, 2016 , 30(1), 6-10.
[6]K Slavakis, GB Giannakis, G Mateos. Modeling and optimization for big data analytics[J]. IEEE Signal Processing Magazine, 2014 , 31(5), 18-31.
[7]喬少杰, 李天瑞, 韩楠, 高云君, 元昌安, 王晓腾, 唐常杰. 大数据环境下移动对象自适应轨迹预测模型[J]. 软件学报 , 2015 , 26(11): 2869-2883.http://www.jos.org.cn/1000-9825/4889.html
[8]李倩伟, 唐丙寅. 基于大数据分析的移动对象轨迹预测方法[J]. 计算机测量与控制 , 2016 , 24 (10) :198-201
[9]毛嘉莉, 金澈清, 章志刚, 周傲英. 轨迹大数据异常检测:研究进展及系统框架[J]. 软件学报 , 2017 , 28 (1) :17-34
[10]夏卓群, 胡珍珍, 罗君鹏. EAVTP:一种环境自适应车辆轨迹预测方法[J]. 小型微型计算机系统 , 2016 , 37 (10) :2375-2379
[11]刘卉, 张广明, 欧阳慧珉. 基于模型预测控制的轨迹跟踪算法研究[J]. 控制工程 , 2016 (s1) :61-65
[12]Tan, K. C. Grid survey approach to store separation trajectory prediction[J]. 2015 , Journal of Aircraft, 37(4), 736-738.
[13]Neafsey DE. ‘big data’ from shrinking pathogen populations[J]. Molecular Ecology, 2013 , 22(2), 271–272.
[14]Kim, H. W., Park, J. H., & Jeong, Y. S. Human-centric storage resource mechanism for big data on cloud service architecture[J]. Journal of Supercomputing, 2016 , 72(7), 2437-2452.
[15]Clessas, G., Cenko, A., & Feinberg, E. New analysis tool for tow target trajectory predictions[J]. Journal of Aircraft, 2015 , 27(27), 385-386.
基金项目:国家自然科学基金委(61662015)资助;广西科技厅科技开发重点项目(桂科攻1598019);NSFC-广东联合基金重点项目(U1501252)
[关键词]轨迹预测 数据预处理 双线性流形 动态大数据 移动对象
中图分类号:TP391.9 文献标识码:A 文章编号:1009-914X(2019)09-0127-04
Dynamic Large Data Target Trajectory Prediction Based on Bilinear Manifolds
HANG Guo-liang, ZHOU Ya, CHAI Wang, HAN Jun-yang
(School of Computer and Information Security, Guilin University of Eletronic Technology, Guilin 541004, China)
Abstract: Due to the lack of consideration of the specific characteristics of trajectory data and other issues, the traditional trajectory prediction in the prediction of big data target trajectory will be greatly limited, in order to improve the trajectory prediction in dynamic large data target trajectory planning of the global prediction ability, A novel dynamic large data target trajectory prediction (DLDTPBM) algorithm is proposed based on bilinear manifold. Firstly, the data preprocessing method is used to process the original data which may contain repetition, noise and high dimension, and the unprocessed raw data is transformed into a form suitable for analysis. The accurate estimation and prediction of the target motion parameters are realized by the DLDTPBM big data prediction method. Guide the accurate prediction of the target trajectory, and improve the prediction accuracy. Compared with the experimental results, the proposed algorithm has higher accuracy, stronger bilinear manifold performance and better robustness than the traditional trajectory prediction algorithm, which can effectively solve the time and other specific characteristics of the trajectory data.
Keywords: Trajectory Prediction; Data preprocessing; Bilinear manifolds; Dynamic big data; Moving object
1.引言
隨着大数据和互联网的迅速发展,出现了动态大数据目标轨迹预测技术[1],人们已经可以对某一特定状态下的信息或资源进行大数据轨迹的计算,而具有相似轨迹的大数据之间非常有可能存在某种联系[2-3]。目前,大数据表达数据预测最常用的方法是目标轨迹预测,将表达水平相近的特征大数据聚在同一个类中[4],从而可以发现未知大数据的信息和具有研究价值的大数据信息[5-6]。
乔少杰[7]等人在对移动对象进行交通流模拟时利用基于隐马尔科夫模型的自适应轨迹预测模型进行位置密度分区和分段处理,从而做出较高的计算准确性。李倩伟[8]等人利用大数据多传感信息融合跟踪,对控制对象描述和约束参量分析,通过大数据分析方法实现对移动目标对象的准确预测,提高预测精度。毛嘉莉[9]等人指出,由于未考虑轨迹数据的时间特性,对此,加入了轨迹异常检测的分类总结,提出轨迹大数据异常检测的系统架构。夏卓群[10]等人认为,轨迹预测在动态环境中预测精度不高,实时效果差,提出一种结合高斯混合模型的环境自适应轨迹预测。刘卉[11]等人提出了一种基于模型预测控制的轨迹跟踪算法,采用线性误差模型作为预测模型,应用非线性模型作为位置解算法,以此来达到算法的良好特性。 但是传统的目标轨迹预测在预测大数据时会受到或多或少的限制[12-13],大数据轨迹预测算法实际上是一种多目标优化的预测算法,对于繁杂的数据矩阵,如果直接对其进行轨迹预测,稍显不太灵活。
本文提出的基于双线性流形的动态大数据目标轨迹预测(Dynamic Large Data Target Trajectory Prediction Based on Bilinear Manifolds,DLDTPBM),并通过贪婪策略逐步增删使得轨迹预测的均方残差达到最优[14-15],采用的方法是先对整个大数据矩阵全局寻优,将找到包含最优解的子矩阵作为种子,再对其进行轨迹预测。
2.相关工作
2.1.轨迹数据
轨迹数据就是时空环境下,通过对一个或多个移动对象运动过程的采样所获得的数据信息,包括采样点位置、采样时间、速度等,这些采样点数据信息根据采样先后顺序构成了轨迹数据。
轨迹挖掘是数据挖掘的一个新兴分支,其研究热点集中于聚类轨迹、分类轨迹、离群点检测、兴趣区域、保护隐私、推荐位置等方面。如果将时间看做是一维数据,大多数传统高维数据聚类算法可以很好的适应于当前的聚类轨迹。
2.2.预处理
轨迹数据作为轨迹大数据的处理对象,预处理效果直接对轨迹预测产生影响,针对不同的应用背景,采用不同的预处理方法,本文使用了轨迹数据预处理中的聚集和维规约的方法:
聚集:是指将两个或多个对象合并成一个对象,聚集的作用是减少数据的个数,突出数据的趋势和轨迹;
维规约:是指降低数据的维度,即减少数据属性的个数,规约的目的是降低数据挖掘算法的时间和内存需求,删除不相关的属性并降低噪声。
其具体实现步骤如下:
第一步:按时间顺序获取目标轨迹数据;
第二步:解析轨迹数据,将数据抽象存储,对轨迹进行编号,加入轨迹点ID;
第三步:查找轨迹遗漏点,分析缺失类型,针对不同类型进行遗漏点处理填充;
第四步:采用误差平方和函数作为聚类准则函数,欧式距离作为相似性检验的评价指标,对所选择轨迹的特征进行计算和提取;
第五步:对于轨迹点聚类,认为簇是由距离靠近的对象组成,因此把得到紧凑且独立的簇作为最终目标,当检测出有单独的点并不属于任何簇时并且与时间序列不匹配时,则认为是异常点,可考虑去除异常点;
第六步:对聚类后的数据集进行处理,每次取三个点作为研究对象,若三个点基本在一条直线上,便可去掉其中的非拐点,最多去掉其中两个点;
第七步:寻找轨迹拐点,并保存其拐点信息,对拐点进行调整,生成轨迹切割集,按切割集进行轨迹切割并保存;
第八步:更新轨迹数据并输出以便进行下一步实验操作。
3.动态大数据优化算法
3.1.随机检测数据集
在大数据目标轨迹预测问题中,给定一个M×N的大数据矩阵A,将M条大数据划分到K个目标轨迹预测中去。通过大数据在预测空间中的轨迹预测,选出代表问题解决方案的最优大数据。每一个大数据Xi=(Mi1,...,Mij,...MiK)代表K个目标轨迹预测的质心向量,Mij表示第i个大数据中第j个目标轨迹预测的中心向量。Pi(t)为个体最好位置,G(t)为全局最好位置,且G(t)= Pg(t),g为处于全局最好位置的大数据的下标。
随机检测数据集(RTDS)算法不需要大数据的速度信息,β为收敛-发散因子,是除了数据库规模和迭代次数外唯一的一个参数,RTDS具有进化方程简单,控制参数少,收敛速度快,运算简单等优点。
3.2.多目标轨迹优化的DPEE算法
对于一个m行n列的矩阵A,Aij为A的一个子矩阵,其中I为行(大数据)的子集,J为列(条件)的子集,若Aij的均方残差值满足一定的条件,则称Aij为一个轨迹预测;其中,均方残差的计算公式为:
(4)
其中,aij为Aij的有效元素,aiJ,aIj和aIJ分別为行平均值、列平均值和矩阵平均值。DPEE算法通过插入或删除具有最高收益的行(列)的方式来提高轨迹预测的质量,进而改进整个轨迹预测种群的质量,最终得到最优轨迹预测集。
多目标优化的DPEE算法的流程为:
第一步:计算大数据矩阵各行(列)的收益值;
第二步:对各行(列)的最高收益进行排序;
第三步:按顺序插入或者删除这些行(列);
第四步:判断执行动作后,轨迹预测的平均容量是否增大,若增大则保存最优轨迹预测作为下一次迭代的初始值,回到第一步继续迭代;否则,算法结束,输出当前最优轨迹预测。
3.3.DLDTPBM轨迹预测算法
3.3.1 双线性流形算法
本文提出实物双线性流形的动态大数据轨迹预测算法。该算法中已知大数据表达矩阵A=(X,Y),包含M条大数据和N个样本条件,该数据集合划分为指定的K类,使所得到的目标轨迹预测划分能使总体类间差异最小。
用Ak表示第k个大数据目标轨迹预测,xin表示在当前目标轨迹预测中第i个大数据在第n个样本条件下的表达水平;ZK为Ak中质心向量的个数,则Ak的质心向量为ck=(ck1,ck2,…,ckn),且 ,定义目标轨迹预测Ak中类内适应度函数WCV为:
则总体差异TWCV可以表示为:
该适应度函数是每种目标轨迹预测的类内适应度函数WCV的和,WCV的值越小说明类内各个目标彼此更紧密,也就是目标轨迹预测质量越好。
大数据双线性流形度量的公式如下:
其中,S表示动态大数据,|L|表示求解空间最长对角线的长度,N表示问题的维数。在DLDTPBM算法中,单个大数据的收敛性是受收敛-发散因子β控制。动态大数据在初始化后会进入收敛状态,这时β会从1.0线性减小到0.5。 以公式(1)为进化方程的RTDS算法中,单个大数据收敛的充分必要条件是 。所以存在 ,当 时,大数据收敛;当 时,大数据进入发散状态。
目标是轨迹预测的剩余值尽可能小,本文使用评价函数F(k,A)来计算一次迭代中产生的轨迹预测的质量,其中F(k,A)的计算公式如下:
F(k,A)表示原大数据矩阵A的第k个轨迹预测矩阵的质量,rk是它的平均平方残差,vk是它的容量,λ1和λ2分别是均方残差和容量的权值。
3.3.2 DLDTPBM算法流程
算法首先使用DLDTPBM算法对原矩阵进行划分;然后对划分后的子矩阵进行DPEE目标轨迹预测,使用公式(9)作为评价函数,基于多目标优化的DPEE的DLDTPBM算法流程如图1所示:
其算法具体描述如下:
第一步:数据初始化,使用双线性流形的RTDS算法产生k个初始矩阵;
第二步:分别计算这k个轨迹预测矩阵每一行和每一列的动作收益;
第三步:比较收益值的大小,得到各行各列的最优动作;
第四步:对这些最优动作排序,并按顺序依次执行;
第五步:执行动作后,根据公式(5)判断轨迹预测的质量是否有所提高,若有,则保存最优轨迹预测作为下一次迭代的初始值,回到第一步继续迭代;否则,算法结束,输出当前最优轨迹预测。
4.实验及讨论
4.1.实验数据与环境
实验使用动态大数据数据集,动态数据集共有38个动态样本和7129个大数据,实验在装有Microsoft Windows 10系统的PC机上运行,CPU为Intel酷睿i5,8G内存,实验语言为Java 1.8,实验环境为IntelliJ IDEA。
本实验随机选取70%的数据作为训练集,30%的数据作为測试集。
4.2.实验结果评判
均方残差是在线性模型中衡量模型拟合程度的一个量,用连续曲线近似地刻画或比拟平面上离散点组,以表示坐标之间函数关系的一种数据处理方法。一组数据的均方残差越小,其拟合程度越好,预测效果也就越好。
为了评价轨迹预测的质量,本文采用均方残差(MSR)、矩阵规模(V)和行变动值(Var)作为大数据矩阵表达一致性的度量标准,行变动值(Var)的计算方法如公式(11)和公式(12)所示:
4.3.实验结果及分析
对比实验中所采用的算法代号及名称说明如下:
(1)RTDS:随机检测数据集;
(2)DPEE:动态规划有效等式法;
(3)DPEE2:多目标优化的动态规划有效等式法;
(4)DLDTPBM:基于双线性流型的动态大叔目标轨迹预测。
实验开始之初,首先进行一组对比实验,分别为:1、对原始数据直接分析计算;2、对可能包含重复、噪声和高维度的原始数据,将未加工的原始数据转换成适合分析的形式带入算法。实验表明做过预处理的这组实验时间明显更顺利,更快,执行时间相对与未进行预处理时优化将近20%左右,如图2所示:
该算法将与RTDS、未改进的DPEE算法,以及多目标优化的DPEE算法进行比较。动态大数据规模为40,迭代次数300次;将动态数据集聚为两类,云环境数据集聚为五类;通过实验确定公式(9)中参数λ1取1,λ2取1.8;d_low设置为0.0005。
实验结果及原始值的走势图如图3所示。
结果分析计算,可以得出如表1所示的性能参数值。
表1是DPEE算法、多目标优化的DPEE算法(DPEE)、RTDS算法和DLDTPBM轨迹预测算法在两个数据集上10次实验的平均值。从表中可以看出,多目标优化的DPEE算法的均方残差值比DPEE算法减少了19%,但是RTDS算法和DLDTPBM算法相比于DPEE2等算法,均方残差值减少了50%左右,优势比较明显。
5.总结
本文提出的DLDTPBM轨迹预测算法,该算法首先利用双线性流形处理数据,根据双线性流形度量函数的值判断大数据的状态,再结合DPEE2算法,修改其迭代目标函数,弥补了DPEE2算法在处理多目标优化问题时的不足,以提高算法的全局预测能力。通过对算法进行比较,实验结果表明,DLDTPBM和RTDS算法的均方残差值与DPEE2算法相比,得到的目标轨迹预测矩阵相似性更集中,总体质量上有很大幅度提高;将DLDTPBM与RTDS算法相比,虽然规模相差不大,但是DLDTPBM均方残差明显减小,说明DLDTPBM相比较于RTDS算法在性能上有所提高,具有更好的全局寻优能力,且目标轨迹预测效果更佳。
参考文献
[1]Trasarti, R., Guidotti, R., Monreale, A., & Giannotti, F. Myway: location prediction via mobility profiling[J]. Information Systems, 2017 , 64, 350-367.
[2]Kristiansen, K. U., & Wulff, C. Exponential estimates of symplectic slow manifolds[J]. Journal of Differential Equations, 2016 , 261(1), 56-101.
[3]Johnson, O. A., Hall, P. S., & Hulme, C. Netimis: dynamic simulation of health economics outcomes using big data[J]. Pharmacoeconomics, 2017 , 34(2), 107-114. [4]Singh, K., Guntuku, S. C., Thakur, A., & Hota, C. Big data analytics framework for peer-to-peer botnet detection using random forests[J]. Information Sciences, 2014 , 278(19), 488-497.
[5]Fan, B., Leng, S., & Yang, K. A dynamic bandwidth allocation algorithm in mobile networks with big data of users and networks[J]. IEEE Network, 2016 , 30(1), 6-10.
[6]K Slavakis, GB Giannakis, G Mateos. Modeling and optimization for big data analytics[J]. IEEE Signal Processing Magazine, 2014 , 31(5), 18-31.
[7]喬少杰, 李天瑞, 韩楠, 高云君, 元昌安, 王晓腾, 唐常杰. 大数据环境下移动对象自适应轨迹预测模型[J]. 软件学报 , 2015 , 26(11): 2869-2883.http://www.jos.org.cn/1000-9825/4889.html
[8]李倩伟, 唐丙寅. 基于大数据分析的移动对象轨迹预测方法[J]. 计算机测量与控制 , 2016 , 24 (10) :198-201
[9]毛嘉莉, 金澈清, 章志刚, 周傲英. 轨迹大数据异常检测:研究进展及系统框架[J]. 软件学报 , 2017 , 28 (1) :17-34
[10]夏卓群, 胡珍珍, 罗君鹏. EAVTP:一种环境自适应车辆轨迹预测方法[J]. 小型微型计算机系统 , 2016 , 37 (10) :2375-2379
[11]刘卉, 张广明, 欧阳慧珉. 基于模型预测控制的轨迹跟踪算法研究[J]. 控制工程 , 2016 (s1) :61-65
[12]Tan, K. C. Grid survey approach to store separation trajectory prediction[J]. 2015 , Journal of Aircraft, 37(4), 736-738.
[13]Neafsey DE. ‘big data’ from shrinking pathogen populations[J]. Molecular Ecology, 2013 , 22(2), 271–272.
[14]Kim, H. W., Park, J. H., & Jeong, Y. S. Human-centric storage resource mechanism for big data on cloud service architecture[J]. Journal of Supercomputing, 2016 , 72(7), 2437-2452.
[15]Clessas, G., Cenko, A., & Feinberg, E. New analysis tool for tow target trajectory predictions[J]. Journal of Aircraft, 2015 , 27(27), 385-386.
基金项目:国家自然科学基金委(61662015)资助;广西科技厅科技开发重点项目(桂科攻1598019);NSFC-广东联合基金重点项目(U1501252)