论文方法写作-基于Spark的单位车辆异常轨迹检测系统设计实现-CNKI知网查重网站

论文方法写作-基于Spark的单位车辆异常轨迹检测系统设计实现

2021-07-02 09:44:06
作者:杭州千明

论文写作模式-基于Spark的单位车辆异常轨迹检测系统设计实现

  1.1课题背景

  大数据,指的是一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合。在当今这个信息化科技飞速进步的时代,人们生活中方方面面产生的庞大数量的数据,每日每夜在这个社会中不断地产生着,流动着。数据已经渗透到每一行业每一领域当中,而这些庞大的数据海洋中,往往隐含着很多潜在规律。而当下人们对于大数据处理与分析领域已经是越来越重视,大数据技术也在社会的很多领域得到运用,诸如军事领域、金融领域、通信领域、交通领域、乃至互联网购物等等领域,大数据都正在扮演着越来越重要的角色。更多地基于事实与数据做出决策,这样的思维方式正在一步步推动整个世界产生巨大的变革。

  单位车辆,指服务于企事业单位的公车车辆,这些车辆数量庞大,为很多公司企业与事业单位的资源运输的事务提供服务。它们穿梭于街道中,来往于不同的目的地之间,保障着这些企事业单位的正常运作,可以说在整个社会的运转中都起着非常重要的作用。车队的运营与其他类型的车辆也有很大不同,不同于出租车和私家车在线路上的随意性,单位车辆在路径上常常表现为很多车次的出发点与结束点是相同的,也就是说会存在众多次的路径是重复的,单位车辆的任务就是安全且有效率地完成这些固定线路上的运输任务。因而,单位车辆运营的正常与否,以及其运营的效率的高低,关乎这些公司单位的运营是否稳定。然而,在现实生活中,总是会出现很多各种各样的状况干扰着单位车辆的运营。交通道路的复杂,路况的不稳定,以及驾驶员水平与素质的参差不齐,都会成为影响运营的不稳定因素。交通事故、交通堵塞、驾驶员的违规驾驶等等,对于车队的整体运输效率,乃至公司的盈利,都会产生不好的影响。因而分析这些车队运行中的异常状况,总结其异常发生的规律,以便提供规避这些异常的参考方案,都有着很大的价值。

  可以发现,面对海量的单位车辆的轨迹数据,如何利用大数据的相关技术,在现有的技术与算法的基础上,有效的进行对于轨迹数据的异常检测,提升异常检测的效率与效果,便是很有价值的研究。所以本文主要针对上述问题进行研究,旨在搭建一个针对轨迹数据的异常检测系统,并且最终以Web系统和Spark分布式大数据计算实现对于轨迹数据的合理有效的异常检测。

  1.2国内外研究现状

  针对GPS轨迹数据的异常检测相对来说还是一个比较新的课题,但是近些年来还是有很多人对此做出了很多研究与尝试。时下的异常轨迹检测的方法大体上可以分为两类,其中一类需要先对已有的轨迹数据进行聚类,分析出数据的整体规律,再总结出与整体规律相违背的非通常轨迹。另一类是在获得已知的或经过设定的异常轨迹特征后,直接从待处理轨迹数据集中对比出符合异常特征的异常轨迹。虽然两类方法在侧重点上不同,但相对较新的算法大多都需要经过一个最为关键的过程,就是对于时间序列的相似性检测。而不同类型的异常轨迹检测算法,由于侧重点的不同,因而在相似性检测算法的检测上也会存在很大不同。本部分内容主要将从以下这个方面进行阐述:国内外轨迹异常检测技术的研究与发展情况。

  轨迹异常检测是轨迹数据挖掘的一个重要分支,并被广泛运用于多个领域。所谓轨迹是一种时空数据的类型,用以记录移动对象的历史位置[1],而异常轨迹就是指一些没有按照预期的模式出现的表现形式[2]。GPS轨迹是一种时间序列数据,异常轨迹检测旨在从轨迹数据集中找出严重偏离正常模式的对象[3-5]。一般情况下,对于轨迹数据的模式发现,大多是旨在从海量的数据中提取共性特征。而轨迹异常检测则与之相反,即面向轨迹数据发现异常。异常轨迹,可以解释为不遵守某种预期模式的轨迹,也可解释为根据相似性准则与其他轨迹相异的轨迹[6]。目前,虽已有一些检测方法,但总体来说,针对轨迹数据的异常检测的方法相对来说并不多。而且由于轨迹数据属于时间序列类型数据,轨迹点前后具有连贯性,使得最传统的针对离群点异常点的异常检测算法并不适用。早至2000年时,由Knorr等人[7-9]提出了先将轨迹数据转换为由多个相互独立的属性所组成的对象,再利用传统的基于距离的离群点检测的方法对其进行异常轨迹的检测。到2008年时,由Lee等人[10]首次提出了TRAOD算法,这种算法在异常轨迹检测领域里有着很重要的地位,这种算法按照最小长度描述原则,首次引入相似度度量,利用Hausdorff距离检测相似度,该算法是一种轨迹异常检测的经典算法并已经获得深入研究[11-12]。但是这种算法对于海量轨迹的异常轨迹效率较低。后来有多人先后对这种算法进行了进一步提升与优化。Liu等人[13]引入R-Tree用以规避大量不必要的距离计算,很大程度提升了效率。Ge等人[14]引入轨迹方向与轨迹密度,采用演化方式,提出了TOP-EYE算法。Zhu等人[15]提出TPRO算法,便是通过轨迹数据集,按照出发点与目的地分组,提取出特定时间段内的最热门的K条路径,然后对数据集进行筛选,将与其相比差异较大的视为异常。Lei等人[16]提出MT-MAD算法,提取频繁访问区域,将轨迹转变为移动序列,再根据特征总结频繁模式,对相似行为分类,构造模型,综合异常特征分数区分异常。Pang等人[17-18]提出基于似然比较检验统计量,对单位时间内各划分网格的对象数,依靠随机似然函数,进行LRT测试和排序,将与期望行为有较大统计差异的,划为异常。唐梦梦等人[19]利用MapReduce以及网格索引来提高TRAOD算法的效率,提出PTRAOD和,GPTRAOD算法。之后,唐梦梦等人[20]又将TOP-EYE算法与MapReduce结合,提出了PDAT—TOP算法,以提高其对于海量数据的运算效率。之后,唐梦梦等人[21]又融合了TRAOD算法和TOP-EYE算法,并结合兴趣区间检测方法的特点,提出了DATIR算法。ZHANG D等人[22]引入隔离树来计算轨迹的异常程度,提出了iBAT算法。冯贵兰等人[23]选择使用K-NN方法,并结合Spark大数据计算引擎提出SP-KNN异常检测算法。之后他们又在此基础上,利用熵值进行K临近异常值搜索[24]。Fontes V C等人[25]选择从标准路径与兴趣区间出发,来检测异常轨迹。蒋华等人[26]引入时间标准来作为判断异常轨迹的重要因素。胡圆等人[27]则根据轨迹的信息熵分布进行异常检测。

  分析这些已经提出的异常检测算法的研究,可以看出,按照异常标准的获取,可分为从外部获取,或自身分析获取异常标准。多数算法都是从待分析数据自身总结异常标准,因而多数都需要经过聚类过程,通过数据集的潜在规律自行找出离群性的轨迹,但这种方法在实际场景使用中往往存在诸多问题,比如过程复杂耗时更多,以及会把实际行为正常但由于出现次数少的轨迹,误归类为异常轨迹的情况。耿凯[28]为解决误判情况,引入了融合多特征的判断方法,但在速度效率上仍不足快捷。而Chen等人[29]则重新将关注点放回到轨迹点的检测上,结合局部异常点的概念,引入GI-Tree,提出了基于划分的轨迹异常检测。但由于舍弃相似性检测,使得该算法在面对交通场景以及海量数据时效率不足。也有部分算法,选择不从检测数据本身寻找标准,而是从外部获得标准。这类方法一般需要额外的标准集,通过标准集获取标准,将检测轨迹分类为异常或正常。例如ROAM方法[30],通过对移动对象路径提取出与时间与位置相关的移动特征motif,利用K-means算法对分段的轨迹基于motif构建多维特征空间。同时,通过轨迹的模式检查,将其中多层次特征提取出来,以分析不同维或不同粒度的多特征之间的关系。最后构建规则分类器,用来检测异常。由于很多异常只是发生在轨迹局部,所以针对轨迹子段的检测。TRASMIL算法[31]进行了改进。首先,将轨迹划分为子段,利用连续概率模型对各个子段进行建模,在以整段轨迹为包,通过分类检测局部异常。这类方法虽然需要额外的标准集,但是却很大程度提高了检测效率。总而言之,在针对交通数据尤其单位车辆场景下,想要提升速度效率,使得算法更适合实际场景,同时为保证效果和结果又不能轻易舍弃相似性检测环节,针对这些效率与效果不够理想的问题,仍需要在实际用例中不断进行优化。

  通过对算法研究的分析总结,以及对于实际场景的分析可以知道,交通轨迹是一段具有连续性和时空特性的点集,是一种时间序列。因而这种对于时间序列的异常检测,在面对海量数据时,显然是离不开相似性检测的。从以上算法也可看出,其大多数都需要相似性检测过程。可以说,相似性检测是轨迹异常检测的重点部分。将相似性检测方法进行优化,便能很大程度提高异常检测算法的优化程度。最传统的相似性检测方法,是ED方法[32],基于欧式距离,通过计算等长序列的各个时间点所对应的坐标点之间的距离聚集值,来计算相似性,但只能用于等长序列。DTW方法[33]通过将时间维度拉伸,可比较不等长序列,通过计算最小距离,进行相似度的计算。但很易受到噪音影响。为了尽量克服噪音影响,也有将DTW结合DNA校准序列进行优化的方法[34],进行了一定优化。LB改进[35]是对DTW进行低边界改进,从而避免多余计算,进行效率优化。LCSS方法[36]受噪音影响很小,通过计算最长相似子轨迹,来计算相似性,但准确度有所降低。ELCSS方法[37]在此基础上,基于角距离测距,进行了优化。ERP方法[38]基于编辑距离,通过计算两条轨迹相同所需要的最小开销,来计算相似性。该方法对不同尺度的测量适用,但易受噪音影响。EDR方法[39]同样基于编辑距离,通过正态化处理,缩放空间维度。通过阈值设定,使得序列间进行对比的两个元素的距离得以量化,以降低噪音影响。FTSE方法[40]则是在LCSS基础上,通过丰富的阈值评估,获得比LCSS和EDR更快的效率。经典的TRAOD算法[12]通过Hausdorff距离计算相似性。之后也出现多人对相似性检测环节进行优化提升。陈锦阳等人[41-42]改进了Hausdorff距离方法,提出了一种基于特征间距离的轨迹聚类方法。Qingying Yu等人[43]提出了基于多特征距离测量的轨迹相似性聚类。Dodge S等人[44]通过改进欧式距离以提升轨迹相似性度量计算效率。王培等人[45]根据时间维度和空间维度进行了改进,提出了PT-AHD方法。但是对于基于Hausdorff距离的相似性检测,离不开聚类。基于这种相似性检测方法的异常检测便往往是基于聚类的异常检测。但是在面对海量数据规模大,维度高的特性[6],基于聚类的方法往往效率不高。Liu等人[46]则开发了基于Spark的FP-Growth算法,进行伴随车辆的挖掘,这种方法通过频繁树,进行相似性比对。Jinglin Peng等人[47]则根据一般NN搜索的不足,提出STS3算法,这种算法将时间序列转换为集合,选择通过Jaccard计算进行相似性度量。并且提供索引、剪枝和近似三种标准进行进一步改进优化。

  综上所述,在面对类似于单位车辆的轨迹异常检测的实际使用场景中,相关相似性检测的算法由于依赖于聚类,存在着计算量大,速率不足以及对一些特殊情况下轨迹的误判问题,在效率和效果上仍存在问题,虽然不同的基准在优缺点和方向上各有不同,但实际的使用场景却对效率和效果更为看重。另外,虽然一些非聚类方法更重效率,但仍需要进一步提升。而STS3相似度检测算法的速度更快,更适合于追求效率与效果的轨迹异常检测的实际使用场景。因而在通过STS3相似度检测进行异常轨迹检测,并且通过Spark大数据引擎进行实现开发单位车辆的轨迹异常检测系统,可以提升异常轨迹检测的效率与效果。

  1.3本文研究内容及目标

  本文基于某公司的公车GPS交通大数据检测项目,着重研究了解轨迹异常检测领域的相关算法,并在此基础上研究算法在单位车辆的异常轨迹检测方面的适用性,结合更为合适的相似性检测算法,提高轨迹异常检测的效率与效果。同时,通过数据清洗的过程,去除数据集的脏数据,提高检测结果的准确性。而后,通过结合Spark分布式大数据计算引擎技术与Web开发技术结合的方法,开发完成针对于单位车辆的异常轨迹检测系统。本文的主要工作如下:

  (1)异常轨迹算法的研究,针对单位车辆的实际情况与工程背景,本文将算法的着重点选择在效率与效果的提升上,在对异常轨迹的检测过程中,本文选择不通过待检测数据本身筛选异常标准,而是直接从外部获得已有的异常库或设定的异常库,对比待检测轨迹,通过相似性检测,比对出具备异常特征的异常轨迹。在相似性检测过程中,为了达到高性能和平衡搜索精度和效率,通过点集中的近点数目进行相似性度量,将平面划分为小单元,用包含点的小单元代替点本身,因而转换为集合上的相似性搜索,来提高计算效率。

  (2)为了解决面对海量轨迹数据的异常检测问题,本文设计开发了基于Spark大数据计算引擎的异常轨迹检测系统。对于Spark大数据计算引擎以及Hadoop分布式大数据平台的基本计算与运行原理以及特点进行分析,结合对于单位车辆的GPS轨迹的异常检测需求,研究异常轨迹检测算法的设计与实现。通过数据清洗提升结果的准确性。通过web系统连接Spark大数据系统,最终实现对于单位车辆的异常轨迹检测系统。

  本文最后通过实验对上述内容进行评估,通过对单位车辆的异常轨迹检测实验结果分析,计算异常轨迹检测的运行时长与准确率等量化指标,评估异常检测系统性能,验证其对于异常轨迹检测的高效性与实用性。

  1.4论文结构安排

  第一章绪论部分,本文从该课题的背景开始,介绍了国内外对于异常轨迹检测技术的研究与发展现状,以及其关键的技术部分相似性检测的研究现状。同时对本文的主要内容以及论文的结构安排进行了说明。

  第二章对相关的理论和技术进行研究,首先对Hadoop分布式大数据生态系统进行研究,介绍其关键的组成部分HDFS文件存储系统,以及对HBase分布式数据存储系统部分进行介绍。而后介绍Spark生态系统,对Spark计算引擎进行介绍,同时对其可用于Python语言拓展的PySpark工具进行介绍。而后对最关键的异常轨迹检测以及相似性检测部分进行研究,介绍高效的STS3时间序列相似性检测算法,以及基于近似STS3的异常轨迹检测算法。最后对一系列相关工具进行介绍。

  第三章对单位车辆异常轨迹检测系统进行需求分析,对服务端进行需求分析,对数据导入模块的交互需求进行分析,对异常轨迹检测的交互需求进行分析,然后最后对整个系统的计算与存储进行需求分析,明确系统设计方向。

  第四章对系统进行设计,本章说明了异常轨迹检测系统的架构设计,详细地描述了该系统的主要模块设计,业务流程设计,对系统的计算与存储进行设计,对系统的开发实现进行指导。

  第五章对系统进行具体实现和测试,详细说明单位车辆异常轨迹检测系统的环境,各个模块与界面的实现过程,最后设计实验对本系统的异常轨迹检测的性能指标进行测试评估。

  2相关理论与技术

  2.1Hadoop生态系统概述

  Apache Hadoop是一种可以进行海量数据处理,以及分布式文件存储的开源软件框架。其核心的组件是分布式文件存储系统HDFS,以及MapReduce计算框架。本文存储系统需要使用HBase,但计算引擎选择Spark引擎。故而下文仅介绍Hadoop中的存储部分,MapReduce计算框架将在Spark介绍部分进行对比介绍。Hadoop大数据生态系统的结构组成如图2-1所示[48]。

  图2-1 Hadoop生态系统的结构示意图

  2.1.1文件存储系统HDFS概述

  分布式文件存储系统HDFS,是Hadoop大数据生态系统的核心组成之一。HDFS拥有高容错性的特点,并且被设计可用于部署在相对低廉的硬件设备集群上。同时HDFS可提供高吞吐量以访问应用程序的数据,对于有着超大规模数据量的应用程序十分适用。HDFS的体系结构如图2-2所示。

  图2-2 HDFS结构示意图

  HDFS分布式文件存储系统,主要由两个核心的组件构成,NameNode和DataNode。NameNode是HDFS系统的主服务器,也被称为主节点。其主要的职责是负责对文件的元数据信息进行管理,同时将该文件的名字以及存储该文件DataNode的集合进行记录。一般情况下,在一个HDFS集群中,有一台机器设备会被用作NameNode,其余的机器设备则会作为DataNode运行[48]。HDFS系统中的文件在其集群中会被按照不同的DataNode分块进行存储,而其文件块的大小则可以通过相应的参数灵活地进行配置,这样便可保证其数据切分、数据容错以及负载均衡等功能的透明化[49]。此外,HDFS系统同样提供了分区存储的功能,以便于对存储文件进行归档,将查询的效率大大提高。同大多数的文件存储系统相似的是,HDFS存储系统采取了树形的组织方式,这样便可对文件或者目录进行创建、删除、移动等操作[50]。总而言之,HDFS系统可以用来存储超大规模的文件,在实际的使用场景中,HDFS系统甚至可常用于存储PB级别的数据。同时,HDFS系统可以流式地访问数据,其遵循着“一次写入,多次读取”的原则,一旦生成了数据集,便会被复制到不同的节点当中,而且运行于HDFS系统中的程序也必须采取流式访问。而且,HDFS系统对于运行硬件设备的要求很低,由于是分布式运行,低成本的设备集群也可适用,同时对其可能产生的节点故障等问题也做了准备,保证了运行的安全性以及可靠性。

  2.1.2分布式数据库HBase概述

  HBase是一个分布式的,面向列的开源数据数据库。HBase在Hadoop之上提供一种结构化数据的存储能力,是Hadoo的子项目之一。HBase非常适合于非结构化数据存储,而且HBase是基于列的模式,而非基于行。HBase利用HDFS作为文件存储系统,HDFS为其提供高可靠的底层存储支持,HBase则居于结构化存储层。Hbase在Hadoop之中的位置关系如图2-3所示。

  图2-3 Hadoop各层系统示意图

  HBase是一种高可靠的、高性能的、面向列的、可伸缩的分布式存储系统。HBase架构体系采用主从式架构,需要运行在HDFS上,并由Zookeeper提供稳定协调服务以及failover机制。另外Hive和Pig还为其提供高级语言支持。HBase的系统架构如图2-4所示。

  图2-4 HBase架构图

  在HBase系统架构中,Client使用RPC机制进行通信,与HMaste进行管理类的操作,与HRegionServer进行读写类操作。HMaster负责对多个HRegionServer进行协调,侦测其状态,分配Region,调节分布,以及保证负载均衡。在Zookeeper协调下,HBase可以有多个HMaster,但在Zookeeper的协调下,多余主节点处于待命,同时间内只会有一个HMaster提供服务。HRegionServer是核心模块,负责响应上层的I/O请求,并向HDFS读写数据。在其之中,会有一系列的HRegion对象,每个HRegion对应一个Region。HRegion又由多个HStore组成。每个HStore对应一个Column Family,即一个集中存储单元。HStore是HBase的最核心,由MemStore和StoreFiles组成,用户的数据写入过程,其数据会先被放入MemStore,当MemStore满后,会生成一个StoreFile,其底层实现是HFile。当StoreFiles增加至阈值,会进行StoreFile的合并。当一个StoreFile大小超过阈值,当前HRegion会分裂为两个HRegion,并被HMaster重新分配到相应的HRegionServer上。另外,每个HRegionServer都有一个Hlog,负责同步备份MemStore。Hlog也会定期翻新,当HRegionServer意外终止后,HMaster则会读取Hlog,而后对log以及region重新分配,再将Hlog读回MemStore,完成数据恢复。

  HBase将数据存储再HDFS上,主要包括HFile和Hlog[51]。HFile是Hadoop的二进制格式的文件,是StoreFile的底层。在HFile之中,除了Trailer和FileInfo外,都是不定长的。Trailer负责用指针进行起始点的指定,FileInfo则记录Meta信息。DataBlock是I/O的基本单元。每个Data块都由开头的Magic和一个个KeyValue对接而成。HBase的存储模型,由单元格、RowKey、列族和时间戳组成。HBase基于列存储,也可认为每个列族对应一张存储表。HBase主要用于存储非结构化以及半结构化的松散数据。

  2.2Spark生态系统概述

  Spark是一种开源集群计算环境,与Hadoop相似。Spark引擎是一种类似于Hadoop MapReduce的计算引擎,是专门为了大规模的数据计算设计的。Spark引擎拥有MapReduce所具备的全部优点,但不同之处在于,Spark的计算过程中,每个Job的中间结果可以直接保存至内存当中,而不必存至硬盘,大大降低HDFS的访问次数,提高运算效率。Spark可以看作是对于Hadoop的补充,可以在Hadoop系统之中并行运行,形成了一个发展迅速而且应用非常广泛的生态系统。Spark生态系统示意如图2-5所示。

  图2-5 Spark生态系统示意图

  Spark的底层是采用Scala语言开发的,但在Spark2.x版本开始,Spark提供了Java语言、Python语言以及R语言等开发语言的API接口,使得Spark可以兼容以上三种语言环境。Spark框架主要是由SparkCore引擎核心以及用于分析数据的SparkSQL、用于处理实时数据的SparkStreaming、用于机器学习的MLlib、用于并行图计算的GraphX等核心的组件构成的。在存储方面,Spark可支持多种方案,例如HDFS、HBase等等。同时在部署方式方面,Spark也有例如Hadoop YARN、Apache Mesos等多种部署方案可供选择。

  2.2.1Spark引擎概述

  Spark Core是Apache Spark的核心组件,可以实现Spark的基本功能,提供了分布式任务调度、内存管理以及存储系统交互等功能。Spark采用了Master-Slave的分布式计算机制。Master是Spark集群的控制器,调控集群使其正常运行。Worker Node则接收Master的命令并向其进行状态汇报,Executor则负责执行Worker Node的具体的计算任务及调度[52]。Spark分布式计算架构示意如图2-6所示。

  图2-6 Spark分布式计算架构示意图

  RDD是Spark对于其数据的抽象,全称是弹性分布式数据集。RDD是一种可以进行并行操作,且具备容错机制的数据集合[53]。RDD可通过对例如HDFS的外部存储系统的引用进行创建,也可以通过对已有的RDD进行转换而创建。RDD可以支持两种操作,转换操作以及行动操作。RDD的转换操作常用的有例如map()、filter()、join()、flatMap()等,进行转换操作会返回一个新的RDD。RDD的转换操作常用的有例如count()、take()、saveAsTextFile()等,行动操作结束后会返回操作结果,或者直接将结果写入存储系统。

  Shark是在Spark框架的基础上提供的同Hive一样的HiveQL接口,在实现query Parsing和Logic Plan generation过程中,Shark使用了Hive的API,而在PhysicalPlan execution的阶段当中,Shark则使用Spark替代MapReduce部分,这样便最大程度地保持了同Hive的兼容性。通过Shark参数的配置,Shark便可以自行于内存当中对特定RDD进行缓存,以实现重用,加快特定的数据集检索。另外,通过Shark的UDF自定义函数,可使SQL查询与运算结合,将RDD的重用最大化。

  DataFrame是另一种数据结构,原本仅可在R语言环境的单机中使用。Spark环境中的DataFrame源自SparkR。SparkR是一种R语言包,而在1.4版本之后,SparkR便实现了DataFrame的分布式使用,结束了之前DataFrame使用限制的情况。其支持例如查询过滤以及聚合等多种操作,最关键的是,这些操作可以用于处理大规模的数据集。与RDD相比,DataFrame数据结构呈现二维状态,类似于excel表格,且可以提供列名行名的设置,使数据处理更方便。

  2.2.2Spark引擎的优势

  Spark计算引擎经常作为对于Hadoop生态系统中MapReduce并行计算的替代与优化。MapReduce是Hadoop系统的核心组成之一,是一种可以通过Hadoop集群,处理大规模数据的计算工具。MapReduce的原理便是将计算的过程进行抽象,分成Map与Reduce两个部分。其中Map是对数据集之中的独立元素进行指定操作。Map过程会生成键值形式,Reduce过程则是对Map过程所输出的结果当中,相同键所有的值进行规定约束,以便得到最终的结果,将结果写入至各Part文件当中,存储至HDFS。MapReduce过程的底层是通过基于Java编程语言开发而实现的。用户只需要将MapReduce框架当中的Mapper和Reducer的接口实现,便能够实现对于分布式的计算程序的开发。而MapReduce框架则会将计算任务,划分成多个task,在集群的任意节点之中执行,同时对相应的节点进行调度[54]。MapReduce的过程示意如图2-7所示。

  图2-7 MapReduce过程示意图

  在Map与Reduce过程之间,Shuffle过程会处理Map过程输出的中间结果,并输入到下一步的Reduce过程中。在这个过程中,每个Map过程产生的数据结果会被输出至环状缓冲区当中,当对缓冲区的使用度到达一定的阈值时,系统会将缓冲区之中的数据写至磁盘上,该过程会产生很多小的临时文件。在Map过程结束前,系统会将这些小文件进行压缩合并处理,存储至分区当中。而在Reduce过程之中则会将这些Map过程的结果文件复制存到缓冲区之中。同样的,当缓冲区中数据量达到阈值,数据则会被存至本地。之后,Reduce中的合并与排序过程将会执行。由此可见,在MapReduce过程中,中间计算的结果需要存储至HDFS的磁盘当中,这个过程需要频繁地访问磁盘,极大地降低了对数据的计算与处理的效率。同时,MapReduce框架仅仅提供了Map过程与Reduce过程两个操作,这使得大量的操作都需要开发人员的代码重写来进行实现,因而它的使用成本比较高。

  但是相比之下,Spark是一种功能全面且非常丰富的分布式计算框架,可以用于对不同性质的数据进行处理,例如文本数据和图数据等等,还可以对不同数据源的数据进行处理,例如HDFS中的批量数据,或者Kafka等实时系统的流数据。在处理是效率方面,Spark的应用程序的运行速度性比较于Hadoop,在内存中可提升100倍,在磁盘中可提升10倍[55]。Spark可以提供多种语言的API,例如Java、Python、Scala等等,而且Spark还提供了可用以交互式地查询数据的shell。Spark不仅可以进行Map操作和Reduce操作,而且它还支持SQL查询、流数据处理和机器学习等等。与MapReduce相比,Spark的效率更高,但使用成本却低。但是Hadoop与Spark并非互斥关系,而是共生关系,可以看作Spark是对于Hadoop的进一步完善,一般习惯使用Hadoop的HDFS作为Spark的存储系统。

  2.2.3PySpark工具概述

  由于Spark是基于scala语言实现的计算框架,但spark同样支持python和Java等语言。scala在分布式场景下虽然有诸多优势,但相比之下,Python语法简单,有更为标准的程序库,适合简单的逻辑处理,在一些算法的编写中,Python往往更为直接,相比之下,Scala有时会显繁杂。而实际中,Python使用者更多,具有丰富的扩展库。总结而言,Python更面向分析,Scala更面向工程。因而在此情况下,为了支持Python语言,Spark针对Python开发了工具PySpark。利用其Py4j库,便可以通过Python语言实现对于RDD等的操作。通过PySpark可以使得Spark的使用功能,得到巨大的拓展。

  2.3基于近似STS3的异常轨迹检测算法

  异常轨迹检测的核心,是相似性检测。选择合适的相似性检测算法,则非常重要。STS3算法[47],是基于集合的相似性检测算法,在相似性检测中具有更高的效率与效果。下文将分别从STS3时间序列相似性检测,以及基于近似STS3的异常轨迹检测进行介绍。

  2.3.1STS3时间序列相似性检测算法介绍

  STS3算法,将时间序列转化为集合,而后通过Jaccard度量进行相似性的度量。STS3算法将时间序列建模为平面上的点,再进一步将平面划分为单元,将同一单元中的点视作是同一个元素。因而,在处理期间,时间序列被转化为一组单元。这种转变,是将时间序列在二次时间复杂度上的比较,转变为集合之间的比较。而集合之间的比较,可以在线性时间上完成。由于对于集合的相似性搜索效率很高,所以STS3算法拥有很快的速度。同时STS3算法亦可提供索引、剪枝和近似等方法来进一步提升效果。本文即采用STS3算法进行相似性检测。

  由于在时间序列的比较中,如果两个时间序列相似,则它们对应的大部分片段应该相似。以一维时间序列举例,如果把时间序列看作是平面上的一组点,时间为t轴,位置值为x轴时,则对应一对相似的时间序列的点集应有很多近点。因此,便可以使用点集中的近点数目来度量时间序列的相似性。由于近点位于相似区域,便可以将平面划分为小单元,用包含点的小单元代替点本身来表示时间序列进行相似性搜索。两个时间序列共享的单元格越多,它们拥有的近点就越多,相应地,它们的相似性也就越大。这样,将时间序列上的相似性搜索转化为集合上的相似性搜索,计算效率更高。以一维时间序列举例,首先进行如下定义。

  定义1。时间序列S被描述为成对序列,即S=[(t1,s1),(t2,s2),…,(tn,sn)],其中ti是Si的时间戳,如果i<j,则满足ti<tj,si是d维数据点。

  定义2。给定一组时间序列D,其边界为D。bound(D)=[(tmin,xmin),(tmax,xmax)]是覆盖D的t-x平面上的最小边界矩形,其中tmin,xmin,tmax和xmax分别表示D中所有时间序列中的最小t和x值以及最大t和x值。

  定义3。给定一个时间序列S,S的点pi=(ti,xi)属于cellj,或者cellj是pi的对应单元格,如果downx<Si≤upx,leftt<i≤rightt,其中cellj的左下和右上坐标分别为(leftt,downx)和(rightt,upx)。

  给定一个带有bound(D)的时间序列数据库D,bound(D)中的区域被划分为多个单元格,每个单元格被分配一个ID。例如,在图1中,bound(D)是包含两个时间序列的最小矩形。然后将其分成大小为σ×ε、编号为1到6的单元。bound(D)的生成是通过扫描D到tmin、tmax、xmin和xmax中的所有点来完成的。利用生成的界,将单元设置为覆盖大小为σ×ε的界。由于单元划分的目标是测量时间序列,因此有必要确保相似的时间序列具有更多的公共单元,并减少时间偏移和值偏移的影响。在划分平面时,我们需要两个参数,分别是ε和σ来容忍时间偏移和值偏移。这两个参数使该方法具有鲁棒性。分割后,将单元ID分配给生成的单元。根据单元格在网格中的行位置row和列位置column,单元格的ID=(row?1)×COLUMN_NUM+colum,其中COLUMN_NUM为网格中的列数。例如,在图2-8中,列数为3,因此网格第二行和第一列中的单元格ID为(2-1)×3+1=4。示例图如图2-8所示。

  图2-8网格分割示意

  给定一个时间序列S,通过计算所有点的单元ID来生成它的集合表示。对于S中的一个点(t,x),对应单元格的行和列分别是row=(x-xmin)/σ+1和column=(t-tmin)/ε+1。首先,计算网格的列。然后计算S中每个点的单元ID。最后,将所有单元格id添加到集合S′,集合化准备完成。当时间序列被转换成集合时,它们的相似性可以用Jaccard度量来计算,Jaccard度量是集合最常用的相似性之一。以简单的STS3举例,计算公式如下:Jaccard(S,Q)=|S∩Q|S∪Q|。将Q转换为单元集Q′,然后扫描D中的单元集,找到与Q′最相似的单元集。从Q到集Q′的转换代价为O(nlogn)。使用简单的线性合并,合集的Jaccard相似性计算代价为O(|S|+|Q|)。因此,其时间复杂度为O(nlogn+∑S∈D|S|+|Q|)。

  在此基础上,STS3还提供了三种不同的算法版本。基于索引的算法适用于长时间序列,基于剪枝的算法适用于短时间序列,近似算法适用于很长时间序列。

  对于基本的STS3,在查询处理过程中,需要计算数据库D和查询Q中所有时间序列的Jaccard相似性。由于D中的大多数时间序列与Q几乎没有交集,因此不必计算所有时间序列的相似性。避免这种情况的自然方法是使用索引来有效地选择候选对象。这便是基于索引的STS3算法,使用倒排列表作为STS3的索引。在基于索引的STS3算法中,使用一个倒序列表IL,每个条目为一对(c,ILc),其中c是一个单元格,ILc是包含c的时间序列的集合,直观地说,S=∪e∈Q ILe包含与Q相交的时间序列,从而可以限制处理的时间序列。由于S和Q的交集的大小是S在所有ILe(e∈Q)中出现的次数,因此我们使用一个计数器阵列交集,每个入口交集[S]计数S中的时间序列的数量。根据交集计算Jaccard相似性,并相应地进行选择。首先,访问Q中的每个单元格e。扫描文件并为其中的每个元素刷新交叉点中相应的计数器。刷新所有计数器后,直接从交叉点计算Jaccard相似度,并返回相似度最大的时间序列作为结果。

  为了加快处理速度,也可使用剪枝策略来过滤时间序列。目标是找到一个时间序列S与查询Q具有最大的Jaccard相似性。直观地说,当S和Q的长度固定时,越大的Jaccard(S,Q)就越大。为了有效地修剪,需要快速评估|S∩Q|的紧上界。但是,很难达到一个准确和有效的上限评估。为了平衡精度和效率,需要设置了一个参数标度,使其达到一个灵活的上限。将平面分成几个区域,区域的数目是scale×scale。计算每个区域的上限,并求出所有区域的上限。紧密性和高效性之间的权衡是随着区域的数量而调整的。用一个例子来说明这个策略。图2-9(a)显示了两个时间序列。将平面划分为4×4个单元,时间序列1和2的集合表示分别为(3,4,5,6,9,13)和(6,7,9,10,13)。如果设置scale=2,那么将平面划分为2×2区域,如图2-9(b)所示。单元1、2、5、6属于1区,单元3、4、7、8属于2区,单元9、10、13、14属于3区,单元11、12、15、16属于4区。如图2-9(b)所示,时间序列1在区域1中有两个单元,其单元ID分别为5和6,而时间序列2有一个单元(单元ID 6)。因此,它们在1区相交的上界是min(2,1)=1。类似地,区域2、3和4中的此类上界分别为min(2,1)=1、min(2,3)=2和min(0,0)=0。因此,两个时间序列的交集的上界是1+1+2+0=4。示例图如图2-9所示。

  图2-9剪枝STS3示意图

  在整个算法的过程中,首先,平面被划分为几个区域。数据库中每个时间序列的每个区域中的单元格数记录在Dzone中,Dzone生成offline,查询的单元格数记录在Qzone中。每个区域包含时间序列S的子集。使用Si来表示区域i中S的子集。由于在区域中,min{Si|,|Qi|}给出了|Si∩Qi|的上界,因此|S∩Q|的上界被计算为所有min{Si|,|Qi|}的和。在获得上界之后,使用它进行修剪。如果不修剪时间序列,则计算Jaccard相似性。最后,找到结果。

  上述两种算法都能得到准确的结果。然而,对于大型数据库,它们的效率可能并不高。对于这种情况,基于近似的STS3算法更为适用。该算法速度很快,但可能会错过最相似的时间序列。近似算法的概念来源是,如果两个时间序列在一个确定的尺度上是相似的,那么它们在一个粗略的尺度上可能是相似的。例如,在图2-9(a)中,当平面被分成4×4个单元时,时间序列1和时间序列2的集合表示分别为(3,4,5,6,9,13)和(6,7,9,10,13)。它们很相似,Jaccard的相似性为3/8。如图2-9(b)所示,当平面被粗分为2×2时,两个集合表示是(1,2,3),它们仍然相似,甚至相同,Jaccard相似性为1。他们也可以在粗略的范围内选择候选,然后在更详细的范围内重新确定他们。使用这种方法,可以在粗尺度下执行更多的相似性计算。因此,查询处理被加速。首先,将平面按从2到maxScale(输入参数)的比例划分为多个单元格,并计算数据库中每个时间序列在每个比例中的集合表示。候选时间序列的集合搜索集由数据库中的所有时间序列初始化。然后在每个尺度上,计算查询的集合表示,并保持与Q最大相似的所有时间序列,同时从搜索集中删除其他时间序列。如果searchSet的大小为1,则退出循环。最后,扫描搜索集中剩余的所有时间序列,并将具有最大相似性的时间序列返回到Q。由于高效率的代价,粗尺度的计算可能会遗漏最相似的时间序列。例如,在图2-10(a)中,时间序列1是与查询最相似的时间序列。它有五个与查询相同的元素,而时间序列2没有与查询相同的元素。但是,当平面被划分为一个粗略的比例尺时,如图2-10(b)所示,时间序列2更类似于查询,因为时间序列2在此比例尺中与查询共享更多的单元格。在这种情况下,最相似的时间序列被忽略。幸运的是,这种情况很少见。示例图如图2-10所示。

  图2-10近似STS3示例图

  为了显示STS3的效率,将STS3与三种具有代表性的方法:ED、DTW和LCSS进行比较。对于DTW类方法,使用LB[35]测试DTW。对于LCSS类方法,则使用了FTSE[40]。数据集选择CET和ED。STS3选择原始STS3。结果表明,对于这两个数据集,STS3拥有更快的速度。运行时间对比如表2-1所示。

  表2-1运行时间对比表

  STS3 ED LB FTSE

  CET 38 203 2106 739753

  ED 19893 28423 465266 3506902

  2.3.2基于近似STS3算法的升维改进与二维化优化

  在原始的STS3相似性搜素过程中,查询处理需要计算查询时间序列Q与数据库D中所以的Jaccard相似性。但是在实际场景之中,数据库D中的绝大多数时间序列,是与查询时间序列Q没有交集的。计算全部的Jaccard,必定会极大增加计算量的浪费,以及时间的浪费。针对这种情况,前文中提到了三种对于速度与计算量的改良。分别是基于索引,基于剪枝,以及基于近似。三种STS3分别适用于不同的场景。基于索引的STS3适用于长时间序列,基于剪枝的STS3适用于短时间序列,基于近似的STS3适用于大量时间序列。针对大数据的轨迹检测,基于索引于基于剪枝的STS3虽然可以得到准确结果,但是对于海量的数据处理,这两种算法的效率可能并不适合。而基于近似的STS3算法,虽然可能会错过最为相似的时间序列,但在本场景中,两个轨迹一模一样的概率太低,因而基于近似的STS3更适用于轨迹的相似性搜素。但是,由于STS3是针对一维时间序列提出。而轨迹是二维时间序列,若想将STS3算法应用到轨迹场景,需要对算法进行增维改进。而增维改进影响最大的,并未相似性计算部分。这是因为Jaccard计算,是直接计算集合化后的轨迹对象,这与维度无关。因而需要对增维做出改进的部分,是将轨迹转变为集合化表示的部分,也就是集合化处理部分。

  集合化处理,是本算法的第一步,也是最重要一步。在前文中提到的STS3相似性检测算法,是将时间序列转变为以时间作为其中一个维度的曲线,并对曲线进行网格划分变为集合的形式。这样的运算,使得若是一维的时间序列,便会转变为两个维度,即一个是位置维度,一个是时间维度。但是对于轨迹数据,因为其本身的位置表示,便已经包含了两个空间维度,因而在对于轨迹的STS3检测,必须要进行算法的增维改进。

  (1)STS3算法升维改进

  对于轨迹的时间序列,是二维时间序列,在位置表述上本身就包含了X和Y两个维度。因而在加入时间维度之后,其表述便成为三维表述,即X轴维度,Y轴维度,以及时间维度。因而对于初始的STS3算法需要进行增维。例如一个简单的轨迹点集,{(1,1),(2,2),(3,3),(4,4)}对应的时间为{1,2,3,4},那么其二维的显示如图2-11所示。

  图2-11轨迹点二维表示示例图

  若是将时间轴同样维度化,则其显示如图2-12所示。

  图2-12加时间维度的轨迹点二维示例图

  再将时间维度和横纵维度合并为一个三维维度空间,那么这些点的表示如图2-13所示。

  图2-13加时间维度的轨迹点三维示例图

  因而若想将轨迹段进行集合化,则需要在三维空间内进行划分与集合化表示。例如若将这段简单轨迹,将这个长度都为6的空间按照2X2的划分进行集合化表示,并执行例如区域1的X为0<=X<3的标准,即若点在两个区域的临界则归为数值较小区域的标准,则可表示为{7,7,6,2}。其划分的示意图如图2-14所示。

  图2-14直接三维划分示意图

  (2)三维化网格划分的二维化优化

  若是按照以上这种直接对三维空间内数据点进行网格划分的集合表示,由于划分的参照维度变成了三个,其划分过程一定更为复杂,这必然会导致划分效率的低下。因而本文提出了一种新的划分方法,以对三维下划分的效率进行提升。

  三维网格划分的二维化优化,其基本思路是,将对于三维空间的一次性直接划分,拆分成两次对于两个二维空间的划分,以便简化复杂度。已知对于(x,y)这样的二维空间点,在增加了时间维度轴后,会变成(x,y,t)这样的三维点。那么直接的三维划分便要对x,y,t三个维度轴进行划分。但若是把空间维度当作是一个维度,即将(x,y,t)以[(x,y),t]的形式进行表示。xy便成了一个维度。这样对于复杂的三维空间的划分,便又变成了简单的二维划分。划分过程变为两次,首先是将点在空间维度内,即x和y的维度内进行第一次划分,划分为小网格表示。以小网格的ID作为空间维度,再对空间维度和时间维度进行二维空间下的网格划分,将大网格的ID作为集合元素。以两步完成划分过程。例如,依旧是上文的四点轨迹,(1,1),(2,2),(4,4),(6,6)在增加了时间维度后,变为(1,1,1),(2,2,2),(4,4,3),(6,6,4)。首先若只以x和y进行二维划分,划分粒度还是2X2。那么在例如(0<x<=3,0<y<=3)便定义为网格3的划分下,这四个点便可以表示为:(3,1),(3,2),(2,3),(2,4)。其小网格划分的示例图如图2-15所示。

  图2-15二维化优化的第一步划分示例图

  在完成第一步划分之后,三维点便成为了(xy,t)式的二维点,在此基础上,再在xy维度与t维度的二维空间内进行第二步划分,按照例如(0<t<=2,0<t<=2)定义为ID为3的标准,以上四个点在大网格划分之下便可以表示成{4,4,1,1}这样的集合。其大网格划分的示例图如图2-16所示。

  图2-16二维化优化的第二步划分示例图

  在直接三维划分的过程中,三维空间被分成了八个网格。而在二维化优化的划分之中,三维数据最终为划分成四个网格。这样看起来,后者的划分明显粒度更粗。但好在,基于近似的STS3本身就是将划分粒度由最粗逐步细化的过程,因而对于算法整体,二维化优化的三维网格划分方法在提升效率的同时,对于算法整体的质量并没有影响。至于对于网格ID的定义,两个轨迹在相同划分的不同ID定义下的Jaccard计算其实是一致的。只要对每个网格一个固定且唯一的ID,使得每个点都有一个唯一所属的网格,便可以对集合化表示的两个轨迹进行Jaccard计算,算法便可以有效进行下去。

  (3)粗粒度细化的网格划分

  之后,便可以按照近似STS3相似性检测方法,比对网格集合化表示后的,增加时间维度的二维轨迹的Jaccard值,进行相似性检测。以此方法比对待检测数据集,与异常库,从而检测出与异常库相似的异常轨迹。基于近似的STS3算法的精髓在于粗粒度细化。在粗粒度的划分之下,时间序列的集合化划分会更为简洁,集合中的数据更少,计算起来更为简单快捷。而一般情况下,最为相似的两个时间序列,在细粒度下最为相似,那么在粗粒度之下也会相似。例如图4-9,为了减少计算量,本算法会从最粗的粒度,逐步细化粒度。在每一粒度的划分里,找出与查询时间序列相比Jaccard的最大值以及拥有此值的序列。然后再细化粒度划分,进行相同的搜素,直到仅剩唯一一个与之最为相似的序列,便是搜索结果。若直到设定的最细刻度划分时,仍有多数序列与查询序列相似,也不再进行进一步细化,而是直接在这些序列之中找出Jaccard最大,即为最相似。但出于对运算量及处理时间,以及机器性能的考虑,粒度细化层级不应设置过多,否则反而会增加无用的计算负担。基本的粗粒度细化的过程示例如图2-17所示。

  图2-17粗粒度细化示意图

  因此,本算法的过程可以总结为:将待检测轨迹与异常库轨迹,加上时间维度,进行粗粒度的网格划分,按照X-Y维度,以及(XY)-T维度,先后进行两次集合化计算,从而以二维化的方法较快地将三维表示的X-Y-T时间序列进行集合化表示,而后在粗粒度下计算待检测轨迹与异常库轨迹的jaccard值,如果最相似值不唯一,则再进行细化粒度下的计算,直至到达设定的最细粒度,或最相似值唯一时,结束搜索,即找到该检测轨迹在异常库内的最相似轨迹。而后再比较阈值,确定该最相似值是否符合相似要求,大于阈值则可判断为,该轨迹为对应的异常库异常类型。以此方法,完成对待检测数据集内轨迹的异常检测。通过对原近似STS3算法的升维改进,使得该算法可以运用于轨迹场景,而后又通过二维化优化,提高对于二维轨迹的加时间维三维网格划分的速度。而选择近似STS3算法进行相似性检测,与原始STS3相比,通过从粗到细多重粒度的划分,在确保准度的前提下,提高计算速度。统合以上内容,便是基于近似STS3的异常轨迹检测算法。

  2.3.3基于近似STS3的异常轨迹检测算法介绍

  在本小节中,将在结合了上文对近似STS3在异常轨迹场景中的改进与优化的内容后,对基于近似STS3的异常轨迹检测算法进行详细描述。以下,本文将从算法描述,数据清洗,算法流程,算法实现等四个部分进行说明。

  (1)算法描述

  本算法从大体流程上可以分为网格划分集合化,以及相似性检测两个部分。首先是网格划分集合化,由于本文采用了二维化优化的两次划分方法,因而在对加时间维度的三维空间的划分,是分为两次划分的。首先,设空间的经纬两维度分别为x和y,设时间维度为t。设待检测轨迹为Q,异常库为D。设划分粒度为l,则网格宽度(x轴)Sx设定如(2-1)所示:

  (2-1)

  之后便是对轨迹点的划分,设待划分轨迹点的行为row,列为col,则该点的行格划分如式(2-2)所示:

  (2-2)

  同理,对于y的划分与x相似,网格高度(y轴)Sy如式(2-3)所示:

  (2-3)

  则待查询点的列col的划分如式(2-4)所示:

  (2-4)

  经过对于轨迹点的两空间维度轴的划分后,空间小网格的序号便可以进行设定,设空间小网格序号为XY,则XY的设定如式(2-5)所示:

  (2-5)

  此时,XY已经是在空间维度内集合化表示,而对于时间t的设定,由于轨迹采集具有等时性特征,即每相邻两点间的时间差是相同的,于是对于时间维度,直接以按时间排序后轨迹点的序号作为时间维度,以简化计算。由于在此情况下,t时间维度与XY空间维度都变成了从1开始的整数,因而过程更为简化。而后再以相同的方式,将XY与t作为两维度,进行划分。计算出大网格ID。将D与Q在相同的网格划分内集合化表示,便可以进行相似性计算。设D内的一条轨迹为S,设J为Jaccard值。则J的计算如式(2-6)所示:

  (2-6)

  以此方式计算,将Q在D中执行相似性搜索,设搜索结果为A,该过程方法为f,相似性搜索过程如式(2-7)所示:

  (2-7)

  若在粗粒度下最大J唯一,则判定该S为与Q最相似解,若A不唯一,则进行粒度细化的进一步划分。细粒度划分计算,直至A唯一。若直至最细粒度仍无最优解,则以首个异常库标准类型记录,好在这种情况极其少见。对于得出的A,还要进行阈值判断,若A的J大于阈值,则以对应异常库标准记录入结果集。如果A的J小于阈值,或在粗粒度下不唯一A的最大J也小于阈值,则说明该轨迹为正常轨迹,直接进入下一条轨迹检测。

  由于本算法应用于海量轨迹的异常检测,所以一般技术平台无法满足海量数据的计算需求。本算法通过Spark的pyspark工具,利用python语言实现。算法运行通过sh脚本启动py脚本,海量数据的存储通过HBase进行存储,检测结果由于展示与查询的需要,存储在MySQL内。算法实现方式示意图如图2-18所示。

  图2-18算法实现方式示意图

  (2)数据清洗

  由于GPS设备在日常使用中,常常会因为一系列不可控的原因造成数据误差,很多复杂的使用场景因素会影响数据的准确性,这是不可避免的。因而在进行下一步数据处理前,数据清洗是必不可少的。

  格式异常,GPS采集是数据有多条字段属性是存在格式要求的,例如ACC状态,即点火状态,是只存在0和1两种状态,定位方式只存在0123四种状态。故而在数据中出现非状态内的数值,则常常是由于数据在传输或存储中出现故障而产生的。这类情况虽然出现概率较低,但也应当被去除。

  卫星数异常,GPS数据采集需要四颗卫星[56]。但当车辆在道路中行驶时,会遭遇例如高楼建筑遮挡,树木遮挡,隧道遮挡等复杂条件,使得定位卫星信号遭到屏蔽,这种情况下采集到的位置信息是不可靠的,因而卫星数小于4的点信息需要剔除。

  数据重复,一般情况下,出现两条一模一样数据的概率极低,而因为故障的数据重复,可能是由于设备的网络连接异常而引发的数据重复发送导致的,因此在数据清洗过程中需要对数据进行去重。

  数据空缺,在正常的信息采集情况下,各项数据不应为空白,这常常也使因为设备在数据传输过程中的信号故障导致一小段的数据缺失,而例如唯一设备号等关键信息空缺则必定为传输故障。同去重一样,去空值也是必不可少。

  速度异常,由于测量时间限制和设备故障等问题,记录速度信息的测定也可能会出现误差,即在某点会出现速度过高的情况。本文对于速度异常采用阈值法,即车辆在行驶中客观情况是不可能高于某速度,根据车辆本身的速度极限,本文设定阈值为200,高于此值便认定为脏数据。

  本文选择了格式判断、卫星数判断、重复值判断、空缺值判断、速度范围判断、等约束条件。约束条件示意图如图2-19所示。

  图2-19清洗约束结构图

  根据上文总结的清洗约束原则分为两大类共六条判断。根据这些清洗约束原则,在Spark平台进行对存储数据的清洗工作。首先,初始化SparkContext,以绝对路径获取HBase中的导入后的数据集,直接读取为dataframe,简称为DF。对于DF的数据,清洗过程便简便很多。由于在检测过程中,为了便于算法实现,本系统选择了PySpark方式,用python语言实现。对初始的DF进行distanct去重,然后通过dropna进行去空缺。然后利用filter算子对DF根据格式、卫星数、速度范围等标准进行过滤处理。最后再通过map、reduceByKey等算子对数据集进行按照唯一设备号的分组和时间排序处理。在数据清洗结束之后,直接进入异常检测过程。

  (3)算法流程

  从上文可知,异常检测的主要过程,是将待检测的轨迹集,与异常库进行相似性搜素,从而将异常轨迹检测出并归类。大体流程如图2-20所示。

  图2-20相似性检测整体流程示意图

  STS3相似性搜索的基本概念,是将时间序列转化为基于网格的集合表示,将基于集合的时间序列,与同样基于集合的时间序列库,计算Jaccard距离,从而计算相似性,找出相似的时间序列。在本场景下,便是从异常库中,找出与待检测轨迹相似的标准异常轨迹,从而判断该检测轨迹的异常性与异常类型。而从前文可以看出,基于近似的STS3,是在集合的划分上对原始的STS3进行优化,而应用到轨迹当中,要将二维的时间序列,加上时间维度,进行三维表示,而后再通过二维化优化进行快捷的集合化表示,在从粗到细的粒度下,进行待检测轨迹与异常库的Jaccard计算。由于本场景是对轨迹集参照异常库的检测,多数正常轨迹是在异常库里找不到相似的,因而在本算法中要设定阈值,如果在某一粒度之下,最为相似的时间序列的Jaccard值也小于阈值,或是最后检测出的最相似值的Jaccard也小于阈值,则证明查询轨迹在异常库中没有相似,是正常轨迹。算法设计如图2-21所示。

  图2-21相似性搜素算法设计图

  (4)算法实现

  本小节对于基于近似STS3异常轨迹检测算法具体实现进行叙述,异常检测算法的检测过程从大体上看,可以分为网格集合化处理,以及相似性检测。

  网格集合化处理。在对于网格的划分标准,采用了多粒度的划分法,这是近似法的关键。因而需要将数据在多种粒度下进行划分。但同时为了计算速度的要求,尽量避免多于计算,以及避免划分标准过多而造成的弄巧成拙,本文将粗粒度至细粒度的细化的层级设置不多。本算法使用pyspark实现,通过执行py的sh脚本实现在Spark中的计算执行。在网格划分的第一步就是对于边界的设定,以及对于网格的设定。对于每一段轨迹的边界获取,是依照轨迹对象的经纬度范围,即最大最小值决定。而网格大小及数量的设定,是依照待对象轨迹的轨迹点数据决定的。依照这种设定方法,便能对轨迹对象进行较为灵活的网格划分,针对轨迹对象设定对应网格。之后便是对每一个待检测轨迹与异常库进行序列集合化处理。基于近似的STS3检测的精髓在于划分粒度的逐步细化。但出于对计算效率的考虑,本文使用的近似算法仅设置三级粒度,在第一粒度之后,设二倍细化与三倍细化为细化粒度。将轨迹对象转换为基于网格划分的集合,以便进行下一步的相似性检测。

  相似性检测。相似性检测是关键一步,在将轨迹对象转换为集合表示之后,进行Jaccard的计算与比较。与上文三级粒度划分对应,对于轨迹的Jaccard比对,如果在较粗粒度下有唯一解,则直接输出结果,保存为对应的异常轨迹。如果最相似解为多个,则进入下一步细化粒度。Jaccard的阈值为判定条件,本系统定为0.5。以上步骤大多在一个py文件中执行,边界设定与网格划分的方法则写在bound的py文件中。算法的实现,通过sh文件调用py主文件脚本,进而执行。sh文件中写明py主文件与hbase表名。通过执行spark服务器中的sh脚本,sh脚本启动py主脚本,进而启动检测算法。算法读取Hbase中的两表,结果存储到MySQL中的结果表。

  2.3.4算法实验与结果分析

  本文采用的是实际生产中,某大型物联公司车载GPS部门提供的2018年9月中三天的实际采集数据。范围覆盖全国,为所有该平台上登录车辆的轨迹数据。测试使用其中的10个数据包,每个数据包200兆大小。异常库为从该数据集中截取的,人为设定的定义轨迹集。本实验通过总量为2000兆的数据的测试来评估性能。另外,由于本算法需要满足海量数据的检测,之后需要再对逐渐增多的检测数据量进行性能实验。

  (1)测试目的

  通过对比实验数据,评估算法的功能是否达到预期。测试的主要内容分为以下两点:

  ①利用实验数据,对异常检测算法进行测试,分析实验结果,以评价异常轨迹检测的性能。

  ②对检测过程中,检测不同的数据量进行对比实验,以测试算法性能。

  (2)评价指标。

  本文主要是利用某物联公司车载GPS部门的实际采集数据进行检测,并提供对检测结果的展示。由于异常库中标准不唯一,对不同的对比标准能否有效进行检测,会影响用户体验。同时对于大量数据的性能保障也至关重要。具体评价指标如下:

  ①异常轨迹检测性能的测试指标,采用准确率(P)、召回率(R)以及综合指标(F)。

  ②由于实际情况,往往需要检测海量数据。对于系统的增量数据检测实验,性能评价指标是检测时间,以及随数据量增加的,检测用时增率。对比检测不同数据量的所用时间,以及所用时间随数据增量的线性变化情况,评价检测系统是否满足需求。

  (3)测试环境

  本文测试环境,原本设计为两个部分,一个是本地客户端机器,一个是租用的阿里云云服务器ECS。但由于实际操作发现,2c4g的服务器内存性能无法满足运算过程。因而系统决定使用边缘节点的方法,即HBase等安装在原云服务器上,Spark程序与本系统以及MySQL运行在新服务器上,用以分担内存消耗。HBase存储服务器配置如表2-2所示:

  表2-2 HBase存储服务器配置

  项目配置

  CPU 2核

  内存4 GiB

  硬盘一高效云盘40GiB(2120IOPS)

  硬盘二SSD云盘20GiB(2400IOPS)

  硬盘三高效云盘100GiB(2600IOPS)

  操作系统Centos7.6-64

  Hadoop版本2.7.7

  HBase版本2.0.1

  SPark计算服务器配置如表2-3所示:

  表2-3 Spark计算云服务器配置

  项目配置

  CPU 2核

  内存8 GiB

  硬盘高效云盘40GiB(2120IOPS)

  操作系统Centos7.6-64

  Spark版本2.4.5

  本地机配置如表2-4所示:

  表2-4本地机配置

  项目

  处理器Intel(R)Core(TM)i7-7700HQ CPU

  内存容量16.00G

  显卡NVIDIA GeForce GTX 1060

  硬盘一SAMSUNG_MZVLW256HEHP 256GB

  硬盘二SanDisk SSD PLUS 1000GB

  网络适配器Intel(R)Dual Band Wirless-AC 8265

  显示器XMMNT238CB 1920x1080

  当前操作系统Windows 10 64位

  (5)测试实验

  本文中根据核心功能需求,将测试实验分为两部分进行,包括异常轨迹检测实验和增量数据检测性能实验。首先是异常轨迹检测实验。

  实验数据:实验数据为上文提到的十个轨迹数据包,累计2000兆,以及人为设定的异常库数据集。

  实验步骤:

  ①对2000兆级轨迹进行数据清洗以及分段处理,并且对检测数据集进行统计,按照检测标准统计清洗后异常轨迹条数C3。

  ②对轨迹数据集进行异常检测处理,并统计每个唯一设备号对应的检测出的异常轨迹条数C2和正确检测到的异常轨迹条数C1。

  ③根据公式对每个唯一设备号计算准确率P=C1/C2,召回率R=C1/C3。因为异常的唯一设备号众多,所以对P和R指标分别取平均值。综合指标F中的β值这里取为1,假定召回率和准确率重要程度一致,计算F=(β2+1)PR/(β2P+R)。

  数据增量性能实验。由于在实际情况之中,常需要对海量的轨迹数据进行检测。因此在选取最好阈值设定后,通过实验对比逐渐增多的数据量的实验结果,查看所用时间增长情况。拟从十个数据包开始逐步增多检测量,先后对20包、30包、40包连续时间轨迹进行检测,计算运行时间,查看所用时间的增长情况,对比实验结果,评估系统在海量数据下的性能。

  (6)实验结果分析

  本实验对异常轨迹检测中部分异常库标准和综合标准进行结果统计,实验测试数据2000MB量轨迹数据,异常库为人为设定,信息抽取实验结果如表2-5所示。

  表2-5信息抽取实验结果

  准确率(P)/%召回率(R)/%综合指标(F)

  速度型异常1 81.66 81.31 81.48

  线路型异常1 82.03 81.02 81.52

  线路型异常2 81.22 80.45 80.83

  综合标准80.67 81.02 80.84

  实验结果表明,各异常类型之间的准确率和召回率都相差不大,这是因为其检测过程本质是一致的。从整体上来看,综合准确率和召回率能达到80%以上,综合指标F也达到了80.84%,说明异常检测算法比较有效。由于轨迹分布的复杂性,范围的广泛性,数据的庞大性,可能会造成检测过程的漏选、多选,且由于轨迹采集过程可能会出现偏差,这同样会影响检测结果,导致目前的异常检测算法还存在着一些不足,这些问题都是在今后工作中,需要逐渐完善的。异常检测效率方面,检测过程达到了每分钟检测40MB级以上的速度,也达到了预期标准。

  增量数据检测性能试验中,对10包数据量,20包数据量,30包数据量,以及40包数据量先后进行检测实验,其用时对比如图2-22所示:

  图2-22增量检测包的用时对比

  从图中可以看到,增量的数据包,所用时间与增长量的线性关系,基本符合稳定增长。且所用时长不多,基本维持在每200MB级3-5分钟,为可接受范围。通过本次实验,可以看到利用Spark对轨迹数据进行基于近似STS3分类的异常检测,其速度与效率基本符合需求,算法对异常检测的性能基本满足要求。

  2.4相关工具概述

  (1)Vue

  Vue是一种用于构建用户界面的,渐进式的JS框架。与其他重量级的框架不同,Vue采用了自底向上的增量开发的设计。Vue的核心库,仅关注视图层,而且极易于与其他项目整合,通过简单的API,实现响应的数据绑定,以及组合的视图组件。

  (2)高德地图API

  高德地图API,是一种基于JS的接口,兼容多种平台,且免费使用。提供多种需求服务,例如地图展示、点标记添加、矢量图形绘制等等。

  (3)MySQL

  MySQL是一种关系型数据库,将数据保存至不同的表,具有高速读存与高灵活特性。与HBase适合于海量大数据存储场景不同,MySQL应用于在线事务问题。需要注意的是,HBase并非用以取代MySQL,两者适用场景不同。相比之下,MySQL虽然不适合海量数据,但其读性能更好,因而在对于数据量不大,却需要频繁读取的场景时,MySQL更为合适。

  (4)redis

  Redis,即远程字典服务,是一种高性能key-value开源数据库。Redis基于内存,是一种数据结构存储器。可以用为数据库、缓存,以及消息中间件。在Java Web场景中,Redis常常用作缓存,以及高速读写的应用,系统通过Redis存储一些临时的信息。例如,用户登录部分,常常需要使用Redis。

  (5)Spring Boot

  Spring Boot是一种简化Spring开发的框架,只需对相应的Spring Boot进行配置,就可以使用全部Spring组件。该框架采用了“习惯优于配置”的方式,可以快速进行Spring应用的构建,具有简化编码、简化配置、简化部署、简化监控等优点。后端通过Spring Boot为前端提供服务。

  2.5本章小结

  本章首先介绍了分布式大数据hadoop生态系统,介绍了其中的HDFS文件存储系统,以及Hive数据仓库,之后介绍了Spark生态系统,对Saprk计算引擎以及关键部分RDD合Dataframe等进行了介绍,同时对Spark相对于MapReduce的优势进行了分析与说明,以及对于PySpark进行介绍。后半部分,则重点研究了基于集合的时间序列相似性检测STS3以及三种不同的提升优化。而后又针对轨迹二维时间序列的特点,提出对STS3进行的升维改进,以及为提升其速度,对其进行的二维化优化,从而总结出基于近似STS3的异常检测轨迹算法。而后又对基于近似STS3的异常轨迹加测算法进行详细描述,对其实现方法,数据清洗部分,算法流程,算法实现等进行介绍。最后通过实验,证实算法可行性与算法效果。最后,对Vue框架、高德地图API、MySQL、Redis、Spring Boot等相关工具进行了介绍。

  3单位车辆异常轨迹检测系统需求分析

  本系统不仅需要对海量的单位车辆的GPS轨迹进行异常轨迹检测,还需要对海量的GPS轨迹数据进行有效存储,还有前端展示。所以本系统分为基础服务展示与管理模块以及数据导入、异常检测两个核心功能模块。

  3.1展示管理模块需求分析

  展示管理模块按照业务与用户差异,可以分成展示部分与管理部分。普通用户仅可获得数据展示服务,而管理员用户在拥有普通用户完整的展示服务的基础上,还可进行数据导入、异常检测等核心的功能。以下本文将从展示模块,以及管理模块分别进行说明。

  3.1.1展示模块需求分析

  展示模块主要为普通用户提供展示服务,展示功能仅用于展示,不可进行数据导入,以及数据检测等操作,根据对于普通用户角色的需求分析,普通用户的用例图如图3-1所示。

  图3-1普通用户用例图

  进入展示首页,首先需要进行登录,进入用户登录界面,输入登录名与登陆密码进行登录,进入主页。展示需求主要包含系统总览信息模块,异常车辆列表模块以及异常轨迹显示模块。

  (1)用户登录,用户在首页需要进行用户验证,通过输入用户名与用户密码进入。用户分为普通用户和管理员用户两类。普通用户仅可获得展示服务,管理员用户则可进行包括数据导入、数据检测等全部操作。在登录时由用户选择用户类型,如果输入用户名与密码错误会提示错误。由于轨迹数据会涉及商业机密,因而两种用户都需要密码登录。

  (2)系统总览,主要提供系统本身的一些数据的展示,包括近七日系统访问记录,今日访问量,检测结果已有设备数,以及记录数等等。

  (3)异常车辆列表显示,是将检测出的异常轨迹按照唯一设备号进行统计与显示,唯一设备号便可指向车辆号,根据唯一设备号以列表显示该设备号所产生的异常轨迹点数量,从而能使用户在大体上掌握单位车辆以及司机的出现异常情况。

  (4)异常轨迹显示,将异常轨迹按条在地图上显示,使得结果的显示更为详细。

  (5)异常车辆查询,主要提供对异常车辆根据唯一设备号查询的功能。

  (6)用户信息修改,允许用户对个人信息进行修改,包括一些用以显示的基本信息,例如用户名,性别,邮箱等等。

  (7)用户密码修改模块,此模块允许用户对个人登录密码进行修改,并提供两次输入的核对。

  3.1.2管理模块需求分析

  管理模块主要涉及管理员用户角色,管理员角色用例图如图3-2所示。

  图3-2管理员用户用例图

  管理员模块,是系统业务的主要使用者,除了普通用户具有的全部功能外,还可以使用数据导入、数据检测,以及数据展示等主要功能。除此之外,管理员还负责维护,主要包括用户管理和数据删除等。

  (1)用户登录,与普通用户的用户登录一致。

  (2)系统总览,与普通用户的系统总览一致。

  (3)数据导入,主要将待检测的源数据集,以及异常库导入至HBase。

  (4)异常检测,按过程分为数据清洗与异常检测,为核心功能。两个过程只经一次执行操作而后先后完成。检测后结果会存入MySQL。

  (5)数据展示,与普通用户的异常车辆列表展示与查询,地图展示等一致。

  (6)轨迹信息管理,主要为维护作用,分为源数据删除和结果数据删除。前者是对HBase里源数据表进行清空操作,后者是对已检测的数据结果进行选择删除操作。

  (7)用户信息管理,主要为维护作用,对于系统的用户信息进行管理,可以修改用户的信息,也可删除用户。

  (8)个人维护,与普通用户的个人信息修改与密码修改一致。

  本系统按照不同的用户类型,对应不同的用户与可操作界面,来区别普通用户与管理员用户的操作,以实现其不同的权限。用户信息与界面及用户类型的类图如图3-3所示。

  图3-3用户与界面类图

  本系统的核心功能模块是数据导入与异常检测两个模块,分别负责导入数据至HBase,以及进行异常检测并保存结果至MySQL,其主要针对轨迹数据进行操作,包括源数据集、异常库、以及结果数据。轨迹数据的类图如图3-4所示。

  图3-4轨迹类图

  下文将从数据导入与异常检测两大核心功能模块分别进行描述。

  3.2数据导入模块需求分析

  数据导入模块主要是提供给用户导入需要处理的GPS轨迹数据集与异常库的服务,主要需求是为用户提供交互控制的界面。数据导入界面交互部分,主要是给用户提供选择待处理的数据集,或异常库的选择。提供两种数据包的导入选择,为数据集与异常库,且可以多种文件格式导入。而后在导入过程之中进行导入结束的反馈。数据导入交互界面部分,其状态转换图如图3-5所示。

  图3-5数据导入状态图

  数据导入提供两种导入选择,用户可以选择待检测的轨迹数据集进行导入,也可选择异常库进行导入。用户点击之后,弹出文件选择框供选择。导入结束后,系统会进行结束反馈。数据导入的主要功能,是将本地选择的数据包,上传至服务器,而后导入至HBase存储系统。由于导入数据包在格式上存在不同,其格式也会存在不同,因而对不同格式的包采用转换处理。但对于数据包的传输,好在导入HBase的过程对于文件格式不敏感。因而选择后不用进行过多处理,文件会以json的格式读取,而后将json文件存储导至HBase,最终以列的格式存储至HBase存储层,并进行结束反馈。当然,在导入过程中,要保证数据的正确性与完整性。数据导入的活动图如图3-6所示。

  图3-6数据导入活动图

  3.3异常检测模块需求分析

  异常检测模块从功能细分,也可分为数据清洗过程与异常检测过程。数据清洗过程主要提供给用户对于单位车辆轨迹数据的数据清洗服务。异常检测过程主要提供用户对轨迹数据的异常检测服务。主要需求为向用户提供交互控制界面,数据清洗规则和异常检测算法实现。异常检测模块界面交互部分,主要是为用户提供对检测操作的执行控制。整个过程分为数据清洗与异常检测两个过程,但用户交互只需一次操作。之后在清洗过程之后直接进入异常检测过程,在异常检测过程之后会提供异常检测的结束反馈。异常检测模块交互界面部分,其状态图如图3-7所示。

  图3-7检测模块状态图

  提供用户的检测执行操作,执行异常检测操作后,便先后进行数据清洗过程,以及异常检测过程。检测结束后会提供结束反馈。其活动图如图3-8所示。

  图3-8异常检测活动图

  异常检测过程,将通过系统触发检测脚本实现,读取HBase数据后,在Spark服务器内先后进行数据清洗与异常检测,数据清洗后,还需读取异常库,异常检测结束后,结果保存至MySQL,结束检测脚本,并返回sh结束码给前端,前端界面进行结束反馈,进而结束检测过程。下文将从该过程中最核心的数据清洗与异常检测两个过程,进行算法需求分析。

  3.4数据存储需求分析

  由于本系统需要对应海量的轨迹数据进行异常检测处理,需要大量计算要求。因而需要使用Spark大数据计算框架。同时由于本系统需要对海量的轨迹数据进行存储。这需要动用HBase存储系统。同时为方便对结果数据的查询与展示,需要辅助以MySQL。按照数据处理的流程进行分析,通过数据流示意图反应数据的处理与存储过程,数据流向示意如图3-9所示

  图3-9数据流向示意图

  从图中可以看出,整个业务过程需要两次使用存储层进行数据存储,但由于数据特性与使用需求不同,两次存储的介质也不同。下面分步对每个步骤的处理与存储进行分析。

  (1)数据导入:主要导入用以检测的轨迹数据。作为系统的原始数据,无论导入的文件格式为何,都会以json格式读取。本文使用数据为几米公司采集的轨迹数据。

  (2)数据导入的数据存储:是第一步的数据存储,将导入的json格式的数据以结构化的形式存入存储层。由于轨迹数据量巨大,选择使用HBase进行存储。为适应HBase的特性,将json转换为列的格式存储至HBase,源数据集与异常库分别存为两表。存储底层为HDFS。

  (3)数据清洗与异常检测:对应异常检测模块。从过程上分为数据清洗,与异常检测两个部分。两者先后完成。为了保证检测数据的准情性与可靠性,排除一些脏数据对于检测的影响,需要进行数据清洗。该过程需要将已经存入HBase的数据读取至Spark进行清洗。为了应对大量的数据计算,提高计算效率,故而选择Spark大数据计算引擎。之后是异常检测,该环节为核心环节,通过数据包与异常库的相似性搜索过程找出异常数据。因而该过程需要对数据集和异常库,两个数据集进行处理。

  (4)异常检测的数据存储:由于在数据展示阶段需要频繁查询与统计结果集,因而选择使用MySQL对检测结果进行保存。检测结束之后,结果会被保存至MySQL数据库,以作持久化存储。

  (5)数据展示:是对异常检测结果的展示,仅用从MySQL查询与统计异常结果表,读至Web展示界面进行进一步的展示。

  轨迹数据是系统功能实现的重要载体,数据量非常庞大。三种轨迹数据的属性相差不多,由于需要经过源数据集与异常库进行对比检测,从而产生结果集,因此三者联系为三元联系,且属于1:1:1联系,因为按每条轨迹来区分的化,一条源数据轨迹仅可能与一种异常库的异常类型最相似并成为一条结果轨迹,一条结果轨迹仅属于一种异常库的异常类型对应一条源数据轨迹,一种异常类型可以有多条源数据轨迹与其相似,但不同的相似源数据轨迹段对应不同的结果轨迹段。轨迹数据的ER图如图3-10所示。

  图3-10轨迹数据ER图

  而系统处理轨迹数据外,还要存储系统数据。系统数据,指的是系统本身运行需要的数据,例如用户信息等,相比较庞大的轨迹数据,系统数据存储需求则小很多,因而所有系统数据都会存在MySQL之中。另外,系统通过权限表区分管理员界面与普通用户界面。因而,与之相关信息也需要保存。同时系统在用户登录时,需要redis存储用户临时信息。但这小部分数据不需建表。系统数据ER图如图3-11所示。

  图3-11系统数据ER图

  3.5本章小结

  本章主要对单位车辆异常轨迹检测系统的需求进行分析,首先对展示与管理模块进行需求进行分析,而后分别对数据导入模块、异常检测模块进行需求分析。最后对整个系统的数据计算与存储需求进行分析,明确本系统的设计方向。

  4单位车辆异常轨迹检测系统设计

  4.1系统架构设计

  根据第三章的需求分析,整个系统由四个主要功能模块构成。对四个功能模块进行分层设计,以双维度方式进行系统的结构划分。按功能模块划分,系统分为数据导入模块、数据清洗模块、异常检测模块、展示管理模块。按逻辑结构对系统进行分层,可分为应用层、业务层、算法层、存储层四层。系统体系架构图如图4-1所示。

  图4-1系统体系架构图

  (1)应用层,仅负责提供对用户的界面交互功能。应用层只需考虑用户的交互需求。本层主要提供对系统的程序控制窗口,包括系统展示界面,数据导入交互界面,异常检测模块交互界面,以及展示管理界面的登录界面,总览界面,异常车辆列表与查询界面,异常轨迹展示界面,轨迹数据删除功能,用户信息修改界面等。

  (2)业务层,也可称为控制层。主要复杂在获得应用层的用户请求之后,传输其请求,然后向应用层回传其请求结果。业务层所负责的功能,主要是对应用层的相关需求进行功能的设计,包括数据导入模块的数据导入服务,异常检测模块的数据清洗服务与异常检测服务,数据展示模块的用户验证,数据展示服务,数据查询和删改等。

  (3)算法层,本层是系统的核心,对应异常检测模块,主要包括清洗约束设定,以及异常轨迹检测相关算法的实现。本层仅需关注如何设计并实现算法,并将相关的数据与存储层进行交互。

  (4)存储层,存储层主要负责数据的存储。Spark系统的存储使用的存储系统是分布式文件存储系统HDFS。但是面对海量的轨迹数据,为方便算法层计算,以及半结构化的数据存储,选择使用HBase存储海量原始数据集,以及异常库。而对于需要频繁查询与统计的结果数据,为提升展示效率与方便导出,选择使用MySQL存储。检测结束后,系统将结果存储至服务器的MySQL数据库。另外在用户登录环节,需要redis数据库缓存临时信息。

  通过分析,对系统核心功能进行数据流图建模。用户分为普通用户和管理员用户。管理员用户可以进行数据导入与异常检测等核心操作。轨迹数据通过数据导入,存入HBase数据库。再在检测过程中被读取,经过数据清洗与异常检测过程获得结果,存入MySQL,最后在通过展示系统进行展示。展示与管理系统的界面是前端页面,除负责进行结果展示外,还负责导入与检测的执行,是系统的最外层。系统数据流图顶层图,0层图,1层图分别如图4-2、图4-3、图4-4所示。

  图4-2系统数据流图顶层图

  图4-3系统数据流图0层图

  图4-4系统数据流图1层图

  4.2展示与管理系统设计

  单位车辆轨迹异常检测系统采用B/S架构设计,对用户通过浏览器提供访问与控制,后台服务器负责数据的业务与处理。展示与管理系统是系统的交互载体,是最外层,也是执行导入与检测核心模块的触发载体。本小节从普通用户展示流程,以及管理员管理流程的设计方案进行说明。

  4.2.1展示业务流程

  展示业务为普通用户和管理员都可获取的功能部分,是对已检测结果的查询展示。从业务流程角度,展示业务部分流程如图4-5所示。

  图4-5展示业务流程图

  展示管理部分的业务流程按照单位车辆轨迹异常检测的异常车辆与轨迹展示需求进行设计。只看其普通用户与管理员皆可获取的功能界面要有以下部分:

  (1)用户登录主页,用于用户登录。

  (2)系统总览页面,用于展示系统本身的信息,包括近七日访问记录,今日访问,检测结果已有的设备数和记录数等等,其中近七日访问记录可以通过柱状图体现,使信息更直观。

  (3)车辆与轨迹展示,对于车辆信息进行同意展示,按照唯一设备号以列表形式展出,仅表现唯一设备号,以及异常轨迹点数。对于轨迹的进一步展示以唯一设备号为主,在地图上显示,显示唯一设备号对应的异常轨迹点。同时在该界面应包含对唯一设备号的查询功能。

  (4)个人信息维护页面,普通用户可以对自己用户的基本信息进行修改,也可进行密码修改。

  数据展示是该部分的功能核心,是对检测出的异常结果的展示。展示过程分为两步,首先按唯一设备号进行统计,以列表形式在展示界面展出,是第一步的列表展示,以及对应记录的统计数。第二步是地图展示,点击某一唯一设备号,查询对应的记录,将查询到的轨迹点以经纬度在地图显示,地图方法使用高德地图API接口。两次展示需要对MySQL进行两次查询,且第一次要进行统计。展示部分的序列图如图4-6所示。

  图4-6展示序列图

  4.2.2管理业务流程

  通过对展示管理模块的需求分析,从系统功能角度,对本系统的功能总结设计如图4-7所示。

  图4-7功能结构图

  管理模块主要功能是为管理员提供对数据导入,以及异常检测的具体服务,以及对已经导入,以及对数据进行删除的功能。仅看管理功能部分,其业务流程如图4-8所示。

  图4-8管理业务流程图

  管理员用户,登录管理界面,相比于普通用户,管理员可以使用系统的主要功能和管理,即数据的导入,以及异常检测。除了系统的主要功能,管理员还可进行系统的维护管理,包括对用户信息的维护管理,对于轨迹数据的维护管理,对应已经检测出并保存的异常结果的维护管理等。具体功能示意图如图4-9所示。

  图4-9管理功能示意图

  4.3数据导入模块设计

  数据导入业务流程的设计,主要根据数据导入的过程需求,从数据导入用户交互流程,以及数据导入业务流程进行叙述。

  (1)数据导入的用户交互业务流程如图4-10所示。

  图4-10数据导入用户交互业务流程图

  用户进行数据导入,进入主界面,选择需要导入的数据包,弹出选择框在本地目录选择其数据包文件或文件夹,可以单包导入或多包导入,而后进行导入处理。

  (2)数据导入流程图如图4-11所示。

  图4-11数据处理流程图

  数据导入流程设计,根据数据导入的需求进行设计。由于单包导入和多包导入在详细导入过程中是相同的,因而在流程中不做分类。同样由于在对HBase导入Json数据的过程中,系统对于文件格式并不敏感,因而不用分类处理,可以直接导入至存储层。最终数据会以列的格式存储至HBase存储层,存至轨迹数据表中。该过程不用经历Spark计算。该过程序列图如图4-12

  图4-12数据导入序列图

  4.4异常检测模块设计

  异常检测业务流程的设计,可分为数据清洗过程与异常检测过程,两者在一次用户操作后先后完成,主要根据数据清洗与异常检测的过程需求,从数据清洗与异常检测的用户交互流程,以及数据清洗,异常检测的业务流程分别进行叙述。